Merkle Tree

Cấu trúc

Cây Merkle là một cấu trúc cây nhị phân, trong đó:

• Mỗi lá của cây Merkle là giá trị hash của một phần dữ liệu gốc.

• Các nút cha được hình thành bằng cách ghép các giá trị hash của hai nút con và sau đó lấy hash của chuỗi kết quả.

• Nút gốc của cây (Merkle Root) là giá trị hash cuối cùng của cây, được tạo ra từ tất cả các phần dữ liệu lá.

Hình bên trên chính là một ví dụ về Merkle Tree có các nút lá có dữ liệu là \(a,b,c,\dots,o,p\). Merkle tree được xây dựng bằng cách lần lượt ghép cặp hai nút lá để tạo ra một nút parent cho để khi đạt đến nút gốc.

Xác minh dữ liệu

Cấu trúc của Merkle Tree giúp tạo ra một giá trị hash duy nhất (merkle root) đại diện cho toàn bộ tập dữ liệu, nhưng chỉ cần một phần nhỏ của cây để xác minh tính toàn vẹn của bất kỳ phần nào của dữ liệu thông qua Merkle Path.

Merkle Path là gì?

Khi xác cần xác minh một nút lá có giá trị hash \(h_x\) có thuộc Merkle Tree \(T\) với Merkle Root \(r\) hay không, người ta dùng Merkle Path. Merkle Path là một chuỗi các giá trị hash \(h_0, h_1, \dots, h_k\) kết hợp với \(h_x\) để tạo ra Merkle Root \(r\). Nghĩa là, để xác minh ta cần kiểm tra:

$$r \overset{?}{=} Hash(h_k, \dots Hash(h_2,Hash(h_1, Hash(h_x, h_0)))\dots)$$

Như vậy, có thể thấy, giả sử ta có tập hợp \(n\) phần tử, chỉ cần dùng \(1\) giá trị Merkle Root là đủ để xác minh một phần tử bất kỳ có phải là con tập hợp ấy không thông qua Merkle Path độ lớn \(\log n\).

Demo

Ở demo này, mình dùng hàm hash Murmur, nhưng trong thực tế công nghệ blockchain người ta thường dùng SHA256.