Merkle Tree là gì?

Merkle Tree là một cấu trúc dữ liệu nén một tập lớn bản ghi thành một dấu vân tay ngắn. Nó cho phép bạn chứng minh một mục nằm trong một danh sách rất lớn bằng cách kiểm tra chỉ vài phần nhỏ, không phải toàn bộ. Hãy tưởng tượng một cây gia đình nơi mỗi nút cha là tóm tắt của các nút con, rồi tất cả hợp lại thành một tổ tiên cuối cùng.

Lầm tưởng

Merkle Tree “lưu trữ” tất cả giao dịch. Không hẳn. Nó chỉ giữ các dấu vân tay gọn của chúng, và cây có thể được dựng lại từ các bản ghi thô khi cần.

Merkle Tree hoạt động như thế nào

Hãy tưởng tượng một khối giao dịch cần một bản tóm tắt nhanh và có thể xác minh. Đây là cách Merkle Tree hoạt động, diễn giải đơn giản:

Bước 1: Bắt đầu với danh sách các mục như giao dịch, mỗi mục là một lá trong cây.
Bước 2: Biến mỗi mục thành một dấu vân tay ngắn bằng cách dùng một hàm băm.
Bước 3: Ghép từng cặp dấu vân tay kế cận, kết hợp mỗi cặp rồi băm lại để tạo nút cha.
Bước 4: Lặp lại việc ghép và băm lên trên cho đến khi chỉ còn một dấu vân tay đỉnh. Đó là Merkle root của tập này.
Bước 5: Để chứng minh một mục thuộc tập, bạn chỉ cần mục đó cộng với một đường dẫn ngắn gồm các dấu vân tay anh chị em. Nhanh và gọn.

Ý tưởng là: bằng chứng nhỏ, độ tin cậy cao.

Tại sao Merkle Tree lại quan trọng

Bằng cách tóm tắt một lượng lớn dữ liệu giao dịch vào một dấu vân tay gọn, Merkle Tree giúp việc xác minh trở nên nhanh và tiết kiệm.

Lợi ích: Bạn có thể kiểm tra tính bao gồm mà không phải tải toàn bộ khối, tiết kiệm thời gian và băng thông.
Góc nhìn: Điều này phù hợp với tinh thần internet hiện nay: tin nhưng phải xác minh, Rolex gặp các chủ đề trên Reddit.
Tính ứng dụng: Bạn sẽ gặp nó trong các khối Bitcoin, biên lai Ethereum, danh sách được phép NFT, airdrop và rollups.

Mẹo

Nếu số lá là lẻ, nhiều thiết kế sẽ nhân đôi lá cuối trước khi băm lên cây. Ngoài ra, hãy kiểm tra kỹ quy trình băm chính xác mà chuỗi hoặc thư viện bạn dùng áp dụng, vì những khác biệt nhỏ về quy tắc có thể thay đổi bằng chứng.

Đặc điểm chính của Merkle Tree

Đây là những điểm khiến nó đặc biệt và hữu ích:

Hiệu quả: Các bằng chứng vẫn nhỏ ngay cả khi tập dữ liệu rất lớn, nên ví nhẹ vẫn giữ được nhẹ.
Tính toàn vẹn: Thay đổi một byte ở một lá sẽ truyền lên tới đỉnh, làm việc sửa đổi trở nên rõ ràng.
Gốc: Mọi thứ hội tụ thành một Merkle root duy nhất có thể lưu hoặc ký để kiểm tra sau.

Các biến thể

Merkle Tree có một vài biến thể phổ biến mà bạn sẽ gặp:

Nhị phân: Cây ghép đôi kinh điển, dùng trong các khối Bitcoin.
Merkle Patricia: Dạng trie cho dữ liệu khóa và giá trị, dùng trong trạng thái và biên lai Ethereum.
Sparse: Một cây đánh chỉ mục rất lớn nơi hầu hết lá trống, phù hợp cho bằng chứng thành viên và không thành viên ngắn gọn.
Verkle: Một “họ” mới hơn với bằng chứng ngắn hơn cho cây có độ phân nhánh lớn, được nghiên cứu cho các nâng cấp tương lai.

Lưu ý

Bằng chứng Merkle Tree chỉ đáng tin cậy tương ứng với header hoặc checkpoint bạn chấp nhận. Nếu bạn tin vào gốc sai, thì bằng chứng tốt nhất cũng vô nghĩa.

Ví dụ

Một ví nhẹ theo kiểu Bitcoin có thể xác minh thanh toán của bạn bằng cách kiểm tra một đường dẫn ngắn các hàm băm từ giao dịch lên tới header khối, mà không cần tải toàn bộ lịch sử giao dịch.

Sự thật thú vị

Ralph Merkle phác thảo ý tưởng này vào cuối những năm bảy mươi khi còn là sinh viên, và nó tồn tại trong các vòng học thuật nhiều năm trước khi Satoshi dùng trong Bitcoin. Minh chứng rằng ý tưởng hay có tuổi thọ dài.

Tổng kết

Tóm lại? Merkle Tree cung cấp các bằng chứng nhanh và nhỏ cho thấy một mục thuộc một tập lớn, không rườm rà, không cần tải xuống nhiều.

Merkle Tree