Merkle Tree

Merkle Tree (hay Cây Merkle) là một cấu trúc dữ liệu được sử dụng trong các ứng dụng khoa học máy tính. Đó là một cấu trúc dữ liệu toán học được tạo thành từ các hàm băm của nhiều block dữ liệu khác nhau tóm tắt tất cả các giao dịch trong một block. Nó cũng cho phép xác minh nội dung nhanh chóng, an toàn và nhất quán trên các bộ dữ liệu lớn.


Cây Merkle. (Nguồn: coin98.net)

Trong Bitcoin và các loại Cryptocurrency khác, Merkle tree được dùng để mã hóa dữ liệu blockchain một cách hiệu quả và an toàn hơn vì cấu trúc Merkle tree cung cấp một bản ghi dễ dàng truy cập về các giao dịch trong một block.

Vì vậy, rất đơn giản để kiểm tra xem dữ liệu trong một block có bị thay đổi hoặc giả mạo hay không. Điều này đúng vì bất kỳ thay đổi nào đối với giao dịch (hoặc bất kỳ dữ liệu liên quan nào khác) trong Merkle tree sẽ dẫn đến một Merkle root tương ứng hoàn toàn khác.

Merkle tree tóm tắt tất cả các giao dịch trong một khối bằng cách tạo dấu hiệu đặc trưng (giá trị băm) của toàn bộ các giao dịch, từ đó cho phép người dùng dễ dàng xác minh xem một giao dịch có tồn tại trong một khối hay không.

Merkle tree được tạo bằng cách liên tục băm các cặp nút cho đến khi chỉ còn lại một giá trị băm (giá trị băm này được gọi là Hash Root hoặc Merkle Root). Các giá trị băm được tính từ dưới lên, bắt đầu từ các giao dịch riêng lẻ (được gọi là các ID giao dịch).

Mỗi nút lá là một giá trị băm của dữ liệu giao dịch và mỗi nút không phải là nút lá là một giá trị băm của các giá trị băm liền trước đó.

Đa phần các Merkle tree là các cây nhị phân, có nghĩa là mỗi nút cha có thể có tối đa hai nhánh con. Về mặt kỹ thuật, bạn có thể tăng tăng số nút con của cây lên, và tạo thành những dạng cây Merkle không phải dạng nhị phân. Tuy nhiên trên thực tế cây nhị phân vẫn được sử dụng phổ biến nhất. Với Merkle tree nhị phân yêu cầu số nút lá chẵn. Nếu số lượng giao dịch là số lẻ, hàm băm cuối cùng sẽ được nhân đôi một lần để tạo số nút chẵn.

Chúng ta quay trở lại ví dụ ở phần trên. Khối dữ liệu ở đây chứa bốn giao dịch là: L1, L2, L3 và L4. Merkle tree khi đó được tạo như sau:

  • Các giao dịch L1, L2, L3, L4 được băm và giá trị băm được lưu trữ trong các nút lá H 0-0, H 0-1, H 1-0, H 1-1.
  • Các nút lá sau đó được tóm tắt trong một nút cha bằng cách băm H 0-0 và H 0-1, tạo thành Hash 0 và H 1-0 và H 1-1 tạo thành H 1.
  • Hai giá trị băm (Hash 0 và Hash 1) sau đó được băm một lần nữa để tạo ra Hash Root (Merkle Root) là giá trị đại diện cho tính toàn vẹn của toàn bộ các giao dịch bên trong.

Quá trình này diễn ra tương tự trên các khối dữ liệu lớn hơn: các khối liên tiếp có thể được băm cho đến khi chỉ có một nút còn lại ở trên cùng.

Merkle Root tóm tắt tất cả dữ liệu trong các giao dịch liên quan và được lưu trữ trong tiêu đề khối. Nó duy trì tính toàn vẹn của dữ liệu. Nếu một chi tiết nhỏ nhất trong bất kỳ giao dịch hoặc có sự thay đổi nào đó trong thứ tự giao dịch, thì Merkle Root cũng sẽ thay đổi. Do đó sử dụng Merkle tree sẽ cho phép chúng ta kiểm tra một cách nhanh chóng và đơn giản xem liệu một giao dịch cụ thể có nằm trong một khối hay không.

Sau khi được xây dựng, cây Merkle có thể cho phép chúng ta kiểm tra tính toàn vẹn của dữ liệu chỉ bằng cách duyệt cây Merkle từ Hash Root với độ phức tạp logarit (quá trình này còn được gọi là Bằng chứng Merkle). Bằng chứng Merkle hoạt động bằng cách tạo lại nhánh chứa đoạn dữ liệu từ gốc đến đoạn dữ liệu cần được kiểm chứng. Trong ví dụ trên, nếu chúng ta muốn kiểm chứng khối dữ liệu L3, chúng ta xuất phát từ Hash root, và cần được cung cấp các giá trị H 1-1 và H0. Chúng ta sẽ băm L3 để lấy giá trị H 1-0, sau đó ghép và băm H 1-1 với H 1-0 để tạo thành H1, sau đó ghép và băm kết quả của điều đó với H 0. Nếu kết quả là cùng một chuỗi với giá trị tại Hash root, điều đó có nghĩa là L3 thực sự là một phần của dữ liệu trong Cây Merkle và không bị thay đổi.

Merkle tree khác với danh sách băm ở chỗ, với Merkle tree, chúng ta có thể xem xét từng nhánh trên cây tại một thời điểm và do đó có thể xác minh tính toàn vẹn của mỗi nhánh ngay lập tức, ngay cả khi không quan tâm đến phần còn lại của cây. Các tệp có thể được chia thành các khối dữ liệu rất nhỏ, do đó chỉ các khối nhỏ cần được tải xuống lại để xác minh nếu phiên bản gốc bị hỏng. Như chúng ta thấy ở ví dụ trên, để xác minh L3, chúng ta chỉ cần biết H 0 và H 1 mà không cần biết các giá trị băm bên dưới tạo nên nó là gì.

Cây Merkle cung cấp bốn lợi thế đáng kể:

  • Xác thực tính toàn vẹn của dữ liệu: Merkle Tree có thể được sử dụng để xác thực tính toàn vẹn của dữ liệu một cách hiệu quả.
  • Tốn ít dung lượng lưu trữ: Khi một giao dịch tiền điện tử được thực hiện theo cấu trúc Merkle Tree, nó sẽ được hash và sau đó đưa ra một giá trị hash tương đương. Sau mỗi giao dịch được hash trong Merkle tree, các giá trị hash được tạo ra sẽ được ghép nối với một giá trị hash khác và sau đó được hash lại. So với các cấu trúc dữ liệu khác, cấu trúc Merkle Tree chiếm rất ít dung lượng lưu trữ.
  • Dữ liệu được sắp xếp và cấu trúc để xác minh dễ dàng: Cây Merkle có thể được chia thành các phần dữ liệu nhỏ để xác minh. các giá trị Hash ‘AB’ và ‘AC’ được kết hợp để tạo ra ‘ABC’. Quá trình ghép nối các giá trị hash này được lặp lại cho đến khi tạo ra giá trị hash cuối cùng. Giá trị hash cuối cùng cung cấp một bản tóm tắt về tất cả các giao dịch có trong block.
  • Xác minh hiệu quả: Định dạng dữ liệu hiệu quả và việc xác minh tính toàn vẹn của dữ liệu chỉ mất vài phút.

Hàm băm mật mã được sử dụng trong Bitcoin là thuật toán băm SHA-256. Đây là viết tắt của Thuật toán băm bảo mật, có đầu ra là 256 bit cố định. Chức năng cơ bản của Merkle tree trong Bitcoin là lưu trữ và cuối cùng cắt tỉa các giao dịch trong mỗi khối.

Như đã đề cập trước đó, các khối trong một blockchain được kết nối với nhau thông qua các giá trị băm của khối trước đó. Trong Bitcoin, mỗi khối chứa tất cả các giao dịch trong khối đó cũng như tiêu đề khối bao gồm:

  • Số phiên bản khối.
  • Giá trị băm của khối trước.
  • Dấu thời gian (time stamp).
  • Độ khó của mục tiêu dùng trong quá trình khai thác.
  • Giá trị ngẫu nhiên Nonce là lời giải của bài toán Proof of Work.
  • Merkle Root.


Minh họa cấu trúc Merkle tree với từng khối. (Ảnh: whitepaper của Bitcoin)

Các giao dịch được thêm vào trong các khối bởi các thợ mỏ và được băm như một phần của Merkle tree, cuối cùng các giá trị băm này được xây dựng thành cây Merkle hoàn chỉnh với Merkle root được lưu trữ trong tiêu đề khối. Thiết kế này tạo ra một số lợi ích riêng biệt.

Đầu tiên, nó cho phép tồn tại các nút Xác minh thanh toán đơn giản (SPV), còn được gọi là các ứng dụng khách hạng nhẹ. Các nút này không phải tải xuống toàn bộ blockchain Bitcoin, mà chỉ cần tải về các tiêu đề khối của chuỗi dài nhất. Điều này giúp tiết kiệm đáng kể quá trình xác thực và lưu trữ blockchain bởi khối lượng dữ liệu của blockchain được tính với cuối tháng 8 năm 2017 đã là 130GB. Các nút SPV sẽ truy vấn đến các nút ngang hàng của chúng cho đến khi xác định được rằng các tiêu đề khối được lưu trữ mà chúng đang hoạt động là một phần của chuỗi dài nhất. Sau đó, một nút SPV có thể xác định trạng thái của giao dịch bằng cách sử dụng bằng chứng Merkle để ánh xạ giao dịch đến một cây Merkle cụ thể với Merkle root tương ứng trong tiêu đề khối là một phần của chuỗi dài nhất.

Ngoài ra, cây Merkle trong Bitcoin còn cho phép cắt xén chuỗi khối để tiết kiệm không gian lưu trữ. Điều này là do chỉ có hash root được lưu trữ trong tiêu đề khối, do đó, các khối cũ có thể được cắt tỉa bằng cách loại bỏ các nhánh không cần thiết của cây Merkle trong khi chỉ giữ lại những thứ cần thiết cho bằng chứng Merkle.