Merkle tree là cấu trúc ghép các giá trị hash theo từng tầng để tạo một giá trị gốc, gọi là Merkle root. Merkle proof là các dữ liệu cần thiết để kiểm tra một phần tử có khớp với cam kết được đại diện bởi root hay không.
Giá trị của cấu trúc này nằm ở việc kiểm tra một thành viên mà không cần gửi toàn bộ tập dữ liệu. Tuy nhiên, điều được chứng minh chỉ có ý nghĩa khi biết root đang đại diện cho tập nào và có căn cứ tin cậy phù hợp đối với root đó.
Từ lá tới root qua bốn bước
Đầu tiên, biểu diễn các phần tử ở tầng lá bằng giá trị hash. Tiếp theo, ghép các cặp theo thứ tự và băm tiếp. Lặp lại để còn một root. Khi muốn chứng minh một thành viên, cung cấp các hash đối ứng cần thiết trên đường từ lá tới root.
Bitcoin reference mô tả cách giao dịch được dùng để xây Merkle tree và cách Merkle root xuất hiện trong header. Cần phân biệt sơ đồ ý tưởng với cách mã hóa, thứ tự byte và phép băm của triển khai thực. Nguồn: Bitcoin Developer Reference, Merkle Trees.
Ví dụ giả định với bốn lá
Giả sử bốn giá trị ở lá được đặt tên A, B, C và D. Ký hiệu H(X,Y) nghĩa là băm phép ghép X với Y theo quy tắc đã xác định. Tầng tiếp theo gồm H(A,B), H(C,D); root là H(H(A,B),H(C,D)).
Để kiểm tra C, bên nhận cần D và H(A,B), cùng thứ tự ghép đúng. Từ C và D, họ tính H(C,D), rồi kết hợp với H(A,B) để tái tạo root. Nếu kết quả không khớp root đối chiếu, bộ bằng chứng không xác minh được như đã trình bày.
Đây là sơ đồ giả định dùng ký hiệu, không phải hash giao dịch thật. Ví dụ chọn bốn lá để làm rõ cơ chế, chưa minh họa cách xử lý tầng có số phần tử lẻ của Bitcoin.
Proof chứng minh điều gì và chưa chứng minh điều gì?
Một proof thành công hỗ trợ kiểm tra quan hệ thành viên đối với root. Nó chưa tự chứng minh mọi giao dịch trong khối đều hợp lệ hoặc lịch sử có root đó là lịch sử người dùng nên chấp nhận. Bitcoin Developer Guide phân biệt điều này khi mô tả mô hình SPV. Nguồn: Operating Modes, SPV.
Ví dụ, cần kiểm tra riêng nguồn của header, quy tắc chọn chuỗi và các giả định về dữ liệu nhận được. Phép kiểm membership và phép kiểm tính hợp lệ toàn bộ khối trả lời những câu hỏi khác nhau.
Ngộ nhận cần tránh
Merkle root không phải tệp nén cho phép khôi phục tất cả giao dịch. Proof cũng không đồng nghĩa một người kiểm tra đã biết toàn bộ lịch sử. Khi thấy một ứng dụng quảng bá “có bằng chứng Merkle”, cần hỏi bằng chứng cho quan hệ nào và cam kết gốc được kiểm tra ra sao.
Kết luận
Merkle tree gom hash của nhiều phần tử thành một Merkle root duy nhất, cho phép kiểm tra một phần tử thuộc tập dữ liệu mà không cần gửi toàn bộ tập đó. Merkle proof chỉ chứng minh quan hệ thành viên với một root cụ thể; nó không khôi phục được dữ liệu và không thay thế việc xét root đó có đáng tin hay không.
Đọc tiếp
Đọc Cấu trúc blockchain, Giao dịch Bitcoin, Hàm băm, Block header, Node và SPV và Thư viện thuật ngữ.