Merkle Tree

Merkle Tree, hay còn gọi là Cây Merkle, là một cấu trúc dữ liệu quan trọng trong lĩnh vực mật mã học và khoa học máy tính, được phát minh bởi nhà mật mã học Ralph Merkle vào năm 1979. Merkle Tree đóng vai trò thiết yếu trong nhiều hệ thống lưu trữ phân tán và blockchain, giúp xác minh tính toàn vẹn và an toàn của dữ liệu mà không cần lưu trữ hoặc xử lý tất cả dữ liệu đó.

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 đôi một với nhau khởi đầu từ $h_x$ để tạo ra Merkle Root $r$. Nghĩa là, để xác minh ta cần kiểm tra:

Như hình dưới đây:

Merkle root $r=2cd27f19$, ta muốn chứng minh rằng $D$ với giá trị hash $65df0b71$ là 1 node lá của merkle tree, ta cần đưa bằng chứng Merkle Path tương ứng là: $(151d934,98a95407,c7427b4b,88d4a162)$. Để verify ta lần lượt tính:

• $Hash(D) = 65df0b71$

• Kết hợp với hash đầu tiên trong merkle path:$Hash(65df0b71 + 151d934) = 18bbf38e$

• Tiếp tục $Hash(18bbf38e + 98a95407) = 1d94780b$

• ... cứ tiếp diễn như vậy cho đến giá trị cuối cùng. Nếu giá trị ấy match với Merkle Root thì hợp lệ. Như vậy, có thể thấy, giả sử ta có tập hợp $n$ phần tử, chỉ cần dùng 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 độ phức tạp $\log n$.

Thuật toán xây dựng Merkle Tree

Về cơ bản, mình dùng cấu trúc dữ liệu queue quen thuộc. Input là list $S =\{s_0, s_1, \dots, s_n\}$ các phần tử đơn lẻ, có thể là 1 danh sách tên người, các giao dịch, …

• Bước 1: Lần lượt chuyển các phần tử trong $S$ thành list $L=\{l_0,l_1,\dots,l_n\}$ là các TreeNode. Mỗi node có $l.hashValue = Hash(s_i)$ và 2 con là $l.left$ và $l.right$.

• Bước 2: Nếu $Nodes.length > 1$ thì qua Bước 3, nếu không qua Bước 6

• Bước 3: Gỡ hai phần tử đầu tiên của $L$ ra: $l = l_0, r= l_1$.

• Bước 4: Tạo TreeNode mới $p$ với $p.hashValue = Hash(l_0.hashValue + l_1.)hashValue$, gán 2 con cho $p$: $p.left = l; p.right = r$

• Bước 5: Đưa $p$ vào cuối của $L$. Quay lại Bước 2.

• Bước 6: trả về $l_0$ chính là Merkle Root

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.