Merkle tree, hay cây Merkle, là cấu trúc dữ liệu dùng hàm băm để gom nhiều phần dữ liệu thành một giá trị đại diện duy nhất gọi là Merkle root. Trong blockchain, dữ liệu đầu vào thường là các giao dịch thuộc một khối.
Nhờ cấu trúc này, một node hoặc ví có thể kiểm tra một giao dịch có nằm trong khối hay không bằng một Merkle proof, thay vì phải tải toàn bộ danh sách giao dịch của khối. Tuy nhiên, bằng chứng này chỉ chứng minh sự hiện diện của dữ liệu trong cây; nó không tự chứng minh giao dịch hợp lệ, khối đã đạt đồng thuận hoặc không thể bị đảo ngược.
Merkle tree là gì?
Merkle tree là một cây băm được tạo theo các bước cơ bản:
- Băm từng phần dữ liệu ở tầng lá, chẳng hạn từng giao dịch.
- Ghép các giá trị băm theo từng cặp và tiếp tục băm.
- Lặp lại quá trình ở các tầng phía trên.
- Thu được một giá trị băm duy nhất ở đỉnh cây: Merkle root.
Trong mô hình cây nhị phân phổ biến, mỗi nút cha được tạo từ hai nút con. Cách xử lý số lượng lá lẻ, cách sắp xếp dữ liệu, định dạng nối và loại hàm băm phụ thuộc vào quy tắc của từng giao thức blockchain.
Merkle tree không mã hóa hay che giấu giao dịch. Vai trò chính của nó là tạo dấu vân tay có cấu trúc cho cả tập dữ liệu. Nếu một giao dịch thay đổi, giá trị băm của giao dịch đó và các nút cha liên quan cũng thay đổi, dẫn đến Merkle root khác.
Để hiểu nền tảng của quá trình này, người mới có thể tìm hiểu thêm về cách hàm băm hoạt động trong blockchain.
Cây Merkle trong blockchain hoạt động như thế nào?
Giả sử một khối chứa bốn giao dịch A, B, C và D. Ký hiệu H() là hàm băm và || là phép ghép dữ liệu theo đúng thứ tự do giao thức quy định.
Đầu tiên, mỗi giao dịch được băm để tạo nút lá:
hA = H(A)hB = H(B)hC = H(C)hD = H(D)
Tiếp theo, các nút lá được ghép thành từng cặp:
hAB = H(hA || hB)hCD = H(hC || hD)
Cuối cùng:
Merkle root = H(hAB || hCD)
Merkle root đại diện cho toàn bộ tập giao dịch và thứ tự của chúng. Nếu giao dịch C bị sửa, hC sẽ thay đổi, kéo theo hCD và Merkle root thay đổi.
Giao dịch thường đi qua nhiều giai đoạn trước khi được đưa vào một khối. Bài viết về hành trình giao dịch từ mempool vào blockchain giúp làm rõ bối cảnh trước khi các giao dịch được gom trong cây Merkle.
Sơ đồ cây Merkle đơn giản
Merkle root
H(hAB || hCD)
/ \
hAB hCD
H(hA || hB) H(hC || hD)
/ \ / \
hA hB hC hD
H(A) H(B) H(C) H(D)
| | | |
Giao dịch A Giao dịch B Giao dịch C Giao dịch D
Sơ đồ cho thấy Merkle root không chứa bản sao đầy đủ của mọi giao dịch. Nó là kết quả của nhiều tầng băm. Chỉ nhìn Merkle root, người dùng không thể khôi phục ngược lại nội dung giao dịch.
Cây trong thực tế có thể lớn hơn nhiều và không phải giao thức nào cũng xử lý tầng lá hoặc số lượng phần tử lẻ giống nhau. Vì vậy, khi tự tính Merkle root, cần tuân thủ chính xác quy tắc tuần tự hóa, thứ tự byte, hàm băm và cách ghép nút của blockchain đang sử dụng.
Merkle proof giúp kiểm chứng dữ liệu ra sao?
Merkle proof là tập hợp các giá trị băm cần thiết để dựng lại đường đi từ một nút lá đến Merkle root. Bằng chứng không cần chứa tất cả giao dịch trong khối.
Ví dụ, để kiểm tra giao dịch C trong cây phía trên, bên kiểm chứng cần:
- Dữ liệu hoặc giá trị băm của giao dịch C.
- Giá trị
hD, là nút cùng cặp vớihC. - Giá trị
hAB, là nhánh còn lại ở tầng tiếp theo. - Vị trí trái hoặc phải của từng giá trị để ghép đúng thứ tự.
- Merkle root kỳ vọng từ tiêu đề khối hoặc nguồn dữ liệu đang được kiểm tra.
Quá trình xác minh diễn ra như sau:
hC = H(C)
hCD = H(hC || hD)
root' = H(hAB || hCD)
Nếu root' trùng với Merkle root kỳ vọng, bằng chứng cho thấy giao dịch C thuộc tập dữ liệu đã tạo ra root đó, với điều kiện hàm băm và quy tắc xây cây được áp dụng đúng.
Khi số lượng giao dịch tăng, Merkle proof chỉ cần các nút cùng cấp nằm trên đường từ giao dịch đến gốc. Vì chiều cao của cây nhị phân tăng theo logarit, bằng chứng thường nhỏ hơn đáng kể so với toàn bộ danh sách giao dịch.
Đây là cơ sở để một số light node kiểm tra dữ liệu bằng thông tin khối và bằng chứng do full node hoặc dịch vụ khác cung cấp. Có thể tham khảo sự khác nhau giữa full node và light node trong blockchain để hiểu mức dữ liệu và mức tự xác minh của từng loại.
Merkle proof chứng minh được điều gì?
Một proof hợp lệ có thể chứng minh dữ liệu cụ thể được đưa vào cây tương ứng với một Merkle root nhất định. Trong blockchain, điều này thường được gọi là bằng chứng bao hàm hoặc bằng chứng thành viên.
Merkle proof không chứng minh được điều gì?
Merkle proof không tự chứng minh rằng:
- Chữ ký của giao dịch hợp lệ.
- Người gửi có đủ tài sản để thực hiện giao dịch.
- Khối tuân thủ toàn bộ quy tắc đồng thuận.
- Merkle root đang dùng thuộc chuỗi chính.
- Khối đã có đủ xác nhận hoặc đạt tính hoàn tất.
Do đó, kiểm tra Merkle proof và kiểm tra trạng thái giao dịch là hai việc liên quan nhưng không đồng nhất. Người dùng cần hiểu thêm về xác nhận giao dịch trên blockchain trước khi kết luận một giao dịch đã hoàn tất.
Phân biệt hàm băm, Merkle root và Merkle proof
| Khái niệm | Bản chất | Vai trò |
|---|---|---|
| Hàm băm | Phép biến đổi dữ liệu đầu vào thành đầu ra có độ dài xác định | Tạo dấu vân tay cho giao dịch hoặc cho cặp nút trong cây |
| Merkle root | Giá trị băm ở đỉnh cây Merkle | Đại diện cho toàn bộ tập dữ liệu và cách sắp xếp của tập đó |
| Merkle proof | Tập các băm lân cận kèm thông tin vị trí | Cho phép dựng lại đường từ một phần tử đến root để kiểm tra sự hiện diện |
Có thể hình dung hàm băm là công cụ, Merkle tree là cấu trúc sử dụng công cụ đó, Merkle root là kết quả đại diện ở đỉnh cây, còn Merkle proof là dữ liệu hỗ trợ kiểm chứng một nhánh cụ thể.
Các khái niệm này không thể thay thế cho nhau. Một giá trị băm đơn lẻ của giao dịch không cho biết giao dịch thuộc khối nào. Merkle root đại diện cho cả tập giao dịch nhưng không đủ để tự xác minh một giao dịch nếu thiếu proof. Merkle proof lại chỉ có ý nghĩa khi được so sánh với root kỳ vọng.
Vì sao blockchain sử dụng cây Merkle?
Kiểm tra dữ liệu mà không tải toàn bộ khối
Nếu người dùng đã có giao dịch cần kiểm tra, họ có thể nhận thêm Merkle proof và so sánh kết quả với root trong thông tin khối. Cách này giảm lượng dữ liệu cần truyền so với việc tải toàn bộ giao dịch chỉ để kiểm tra một phần tử.
Điều đó không có nghĩa thiết bị hoàn toàn không cần thông tin về blockchain. Bên kiểm chứng vẫn phải có cách xác định Merkle root hoặc tiêu đề khối nào đáng tin cậy theo mô hình xác minh của mình.
Phát hiện dữ liệu bị thay đổi
Một thay đổi ở tầng lá sẽ lan lên những nút cha trên cùng nhánh. Nếu kết quả cuối cùng không khớp root kỳ vọng, dữ liệu hoặc bằng chứng đã cung cấp không phù hợp với cây ban đầu.
Đây là khả năng phát hiện sai khác, không phải cơ chế ngăn dữ liệu bị sửa. Việc duy trì lịch sử blockchain còn phụ thuộc vào mạng node, quy tắc đồng thuận và các cơ chế bảo mật khác.
Hỗ trợ node có tài nguyên hạn chế
Thiết bị không vận hành full node có thể sử dụng bằng chứng gọn hơn để kiểm tra một phần dữ liệu. Mức độ tin cậy vẫn tùy thuộc thiết kế của giao thức, cách thiết bị xác minh tiêu đề khối và nguồn cung cấp proof.
Xác minh hiệu quả trong tập dữ liệu lớn
Cấu trúc phân tầng giúp việc chứng minh một phần tử không yêu cầu gửi toàn bộ tập dữ liệu. Đặc điểm này hữu ích không chỉ trong blockchain mà còn trong các hệ thống phân tán cần đối chiếu tính toàn vẹn dữ liệu.
Những giới hạn cần hiểu đúng
Có Merkle proof không đồng nghĩa giao dịch đã hoàn tất
Proof cho biết giao dịch thuộc cây gắn với một root. Trạng thái xác nhận hoặc hoàn tất còn phụ thuộc vị trí của khối trong chuỗi và quy tắc của mạng.
Root đúng chỉ có ý nghĩa khi nguồn root được xác minh
Kẻ xấu có thể tạo một cây riêng, đưa giao dịch bất kỳ vào đó rồi cung cấp root và proof khớp nhau. Nếu người kiểm tra không xác minh root thuộc một khối hợp lệ trên chuỗi mong muốn, phép kiểm tra chỉ chứng minh tính nhất quán của cây do bên kia cung cấp.
Thứ tự ghép băm rất quan trọng
Trong ví dụ trên, H(hC || hD) không mặc nhiên giống H(hD || hC). Merkle proof vì vậy cần chỉ rõ mỗi nút anh em nằm bên trái hay bên phải.
Cách xây cây có thể khác giữa các giao thức
Không nên lấy quy tắc của một blockchain áp dụng nguyên vẹn cho blockchain khác. Những khác biệt có thể nằm ở dữ liệu đầu vào, số lần băm, thứ tự byte, cách xử lý lá lẻ hoặc cấu trúc cây.
Merkle tree không thay thế các lớp bảo mật khác
Cây Merkle không thay thế chữ ký số, cơ chế đồng thuận, quy tắc xác thực giao dịch hay biện pháp bảo vệ khóa riêng. Nó giải quyết chủ yếu bài toán cam kết và kiểm chứng tính toàn vẹn của một tập dữ liệu.
Tóm tắt dành cho người mới
- Merkle tree gom nhiều giao dịch thành một cấu trúc băm phân tầng.
- Merkle root là giá trị ở đỉnh cây, đại diện cho toàn bộ tập dữ liệu và thứ tự của tập đó.
- Merkle proof gồm các băm cần thiết để kiểm tra một giao dịch có thuộc cây hay không.
- Hàm băm là thành phần dùng để tạo nút lá, nút cha và root.
- Proof giúp kiểm chứng mà không cần tải toàn bộ khối, nhưng bên kiểm chứng vẫn phải xác định được root hoặc tiêu đề khối phù hợp.
- Một Merkle proof hợp lệ không tự đảm bảo giao dịch hợp lệ, đã được xác nhận đầy đủ hoặc đã đạt tính hoàn tất.
Cách ghi nhớ ngắn gọn là: hàm băm tạo dấu vân tay, cây Merkle tổ chức các dấu vân tay, Merkle root đại diện cho cả cây và Merkle proof mở ra đúng nhánh cần kiểm tra.