Merkle Tree (Cây Merkle) là gì?

Câu chuyện về Merkle Tree bắt đầu từ năm 1979 với một thanh niên tên Ralph Merkle. Khi còn học tại trường đại học Stanford, Merkle đã viết một bài báo học thuật có tên là “Chữ ký số được chứng nhận” “A Certified Digital Signature”. Nói cách khác, anh ta đã thiết kế một quy trình xác minh dữ liệu cho phép máy tính thực hiện công việc của mình nhanh hơn nhiều so với trước đây.

Ý tưởng của Merkle, hiện được biết đến với tên Merkle Tree, đã cách mạng hóa thế giới mã hóa bằng cách mở rộng cách thức mà giao thức máy tính mã hóa hoạt động. Trên thực tế, Merkle Tree được nhắc đến nhiều lần trong bài luận năm 2008 của Satoshi Nakamoto để giới thiệu Bitcoin với thế giới. Chúng cũng được sử dụng rộng rãi trong mã Bitcoin.

Mục đích của bài đăng này là cung cấp cái nhìn khái quát về cấu trúc dữ liệu cây Merkle (Merkle Tree) cơ bản và cũng là điểm khởi đầu cho các chủ đề chuyên sâu hơn liên quan đến Merkle Tree.

Merkle Tree là gì?

Cây Merkle là một cấu trúc dữ liệu dạng cây trong đó mọi nút lá được dán nhãn bằng giá trị băm của khối dữ liệu và mọi nút không phải là nút lá được dán nhãn bằng giá trị băm của nhãn của các nút con của nó. Cây băm cho phép xác minh hiệu quả và an toàn nội dung của các cấu trúc dữ liệu lớn. Cây băm là một dạng tổng quát của danh sách băm và chuỗi băm.

Khái niệm “cây” là một khái niệm phổ biến trong khoa học máy tính, đề cập đến một cấu trúc bao gồm các nút cha và các nút con phân nhánh từ các nút cha này.

Nhìn ở trên hình ta thấy rằng nút lá Hash 0-0 và Hash 0-1 có nhãn là giá trị băm của hai khối dữ liệu L1 và L2, và nút không phải là nút lá Hash 0 có nhãn là giá trị băm của Hash 0-0 và Hash 0-1.

Với dạng cây băm merkle tree này, số lượng phép tính toán hàm băm tỷ lệ với logarit của số nút là của cây. Trong khi với các danh sách băm thì số lượng này tỷ lệ với số lượng nút của chính nó.

Chính điều này làm cho việc tính toán và xác minh, tìm kiếm giá trị băm trên khối diễn ra nhanh hơn trên các khối dữ liệu lớn.

Cây Merkle, theo cách hiểu đơn giản, lấy rất nhiều dữ liệu, nén nó thành một chuỗi ký tự đơn giản có thể chứng minh tính xác thực của dữ liệu được giữ trong đó, mà không tiết lộ dữ liệu đó là gì. Tương tự như một tệp nén (.ZIP hoặc .RAR), nếu được đặt tên chính xác theo một tiêu chuẩn nhất định, người dùng có thể nhận ra nội dung mà không cần phải giải nén và mở các tệp chứa. Chuỗi ký tự (tiêu đề) này được gọi là giá trị băm. Giá trị băm được tạo ra từ hàm băm là một hàm một chiều, có nghĩa là nếu bạn đặt cùng một dữ liệu, bạn sẽ luôn nhận được cùng một giá trị băm, nhưng bạn không thể lấy giá trị băm đó và trích xuất ra được dữ liệu gốc.

Cách thức hoạt động

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ì.

Độ phức tạp của Merkle Tree

Chúng ta xem xét độ phức tạp của một số thao tác cơ bản đối với cấu trúc dữ liệu để thấy được lợi thế của Merkle tree về tốc độ:

trong đó, n là số nút của cây hay số lượng dữ liệu trong khối.

Lợi ích của Merkle Tree

Việc sử dụng cấu trúc Merkle tree có thể làm giảm đáng kể lượng dữ liệu cần thiết phải duy trì cho mục đích xác minh giao dịch hoặc xem xét tính toàn vẹn của từng nội dung trong dữ liệu. Cây Merkle có thể được lưu trữ cục bộ hoặc trên các hệ thống phân tán.

Merkle tree có ba lợi ích chính:

• Merkle tree cung cấp một phương tiện để chứng minh tính toàn vẹn và hợp lệ của dữ liệu. Cấu trúc của cây cho phép xác định những thay đổi dù là nhỏ nhất đối với dữ liệu một cách dễ dàng.
• Đòi hỏi ít bộ nhớ hoặc dung lượng ổ đĩa vì các bằng chứng được tính toán dễ dàng và nhanh chóng. Nếu chúng ta muốn biết sự thay đổi dữ liệu đã xảy ra ở đâu thì chúng ta có thể kiểm tra xem dữ liệu có phù hợp với Hash Root hay không và tiến hành duyệt cây theo chiều rộng là có thể xác định được những vị trí mà dữ liệu bị thay đổi.
• Chỉ yêu cầu một lượng nhỏ thông tin được truyền tải qua các mạng.

Cấu trúc của cây cho phép biểu diễn hiệu quả lượng dữ liệu lớn tùy ý và cho phép dễ dàng xác định vị trí xảy ra thay đổi trong dữ liệu đó. Điều này cho phép bất kỳ ai cũng có thể xác minh rằng việc băm dữ liệu là nhất quán và chính xác mà không cần phải thực sự xem xét toàn bộ cây.

Trên các mạng ngang hàng Torrent, khi bạn tải xuống một torrent, bạn sẽ nhận được các tệp từ những người khác trên mạng, nhưng làm thế nào bạn có thể chắc chắn rằng các tệp đó thực sự là một phần của những gì bạn muốn tải xuống và không phải là rác hay các phần mềm độc hại? Cây Merkle có thể xác thực dữ liệu nhận được trong trường hợp này.

Tương tự, trong các loại tiền điện tử như Bitcoin và Ethereum: Nếu ai đó tuyên bố rằng trong một số giao dịch nào đó, họ nhận được tiền từ một ai đó, thì làm thế nào các nút trên mạng có thể xác minh rằng giao dịch đó thực sự xảy ra?

Để xác minh điều này, các nút có thể lưu trữ toàn bộ lịch sử của mọi giao dịch đã từng xảy ra. Tuy nhiên, mỗi khối chứa hàng trăm thậm trí hàng ngàn giao dịch. Do đó sẽ rất mất thời gian để lưu trữ tất cả dữ liệu bên trong mỗi khối dưới dạng một chuỗi đầy đủ. Làm như vậy sẽ làm cho việc tìm kiếm bất kỳ giao dịch cụ thể nào vô cùng cồng kềnh và tốn thời gian. Cây Merkle cung cấp một giải pháp giúp tiết kiệm thời gian và không gian cho các nút trên mạng. Bằng cách tạo Cây Merkle từ dữ liệu giao dịch trong mỗi khối, các giao dịch có thể được kiểm tra với độ phức tạp thời gian logarit thay vì thời gian tuyến tính. Ngoài ra, nó giúp cho một số nút ngang hàng có thể tiết kiệm dung lượng bằng cách chỉ lưu trữ Merkle root mà không cần lưu trữ mọi giao dịch đã từng xảy ra trong lịch sử!

Mekle Tree trong Bitcoin

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

Hình ảnh dưới đây được lấy từ whitepaper của Bitcoin và minh họa cấu trúc Merkle tree với từng khối.

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.

Các ứng dụng khác của Merkle tree

Mặc dù Bitcoin là blockchain đầu tiên triển khai cây Merkle, nhưng nhiều blockchain khác cũng có các cấu trúc cây Merkle tương tự hoặc các phiên bản thậm chí phức tạp hơn. Hơn nữa, ứng dụng của cây Merkle không chỉ giới hạn ở các chuỗi khối mà còn được áp dụng cho nhiều hệ thống khác.

Ethereum, là loại tiền điện tử phổ biến khác, cũng sử dụng Merkle tree để tăng hiệu quả xác nhận giao dịch. Do Ethereum được xây dựng như một nền tảng để triển khai các ứng dụng phức tạp hơn nhiều, vì vậy nó sử dụng một phiên bản phức tạp hơn của cây Merkle có tên là Merkle Patricia Tree. Cấu trúc này thực ra là sự kết hợp của 3 cây Merkle riêng biệt được sử dụng cho ba loại đối tượng khác nhau trong các nền tảng Ethereum. Mỗi khối bao gồm ba Merkle root đặc trưng tương ứng cho 3 cây con khác nhau này:

1. stateRoot: đại diện cho trạng thái của khối, được cập nhật theo thời gian.
2. ReceiptsRoot: chứa các biên lai giao dịch trong khối.
3. Transaction Root chứa toàn bộ các giao dịch.

Ngoài ra StorageRoot chứa toàn bộ các dữ liệu về hợp đồng. Mỗi tài khoản có một cây lưu trữ storage riêng biệt.

Cây Merkle là công cụ mạnh mẽ và không thể thiếu trên blockchain. Chúng cực kỳ mạnh mẽ và là trung tâm của một số mạng ngang hàng như BitTorrent, Git, Bitcoin và Ethereum.

Nó còn là thành phần quan trọng của các hệ thống kiểm soát phiên bản phân tán như Git và Mercurial; hay các hệ thống tệp tin như IPFS, Btrfs và ZFS giúp đảm bảo tính toàn vẹn và chống mất mát sửa đổi dữ liệu cho các hệ thống này. Do tính dễ dàng trong việc sử dụng để đảm bảo và xác minh tính toàn vẹn của dữ liệu được chia sẻ giữa các máy tính ở định dạng P2P khiến chúng trở nên vô giá đối với các hệ thống này. Nó được sử dụng trong Giao thức Dat; Giao thức Apache Wave; hệ thống dự phòng Tahoe-LAFS; Zeronet; và một số hệ thống NoQuery như Apache Cassandra, Riak và Dynamo DB.

Ngoài blockchain và torrent, Merkle Tree còn có thể sử dụng trong bất kỳ hệ thống nào cần phát hiện sự không nhất quán về dữ liệu một cách hiệu quả chẳng hạn như:

• Cơ quan cấp chứng chỉ (CA) sử dụng Cây Merkle làm phương tiện để minh bạch chứng chỉ. Ở đây, các cặp khóa công khai và khóa riêng được coi là lá của Merkle tree. Đây là một cơ chế mà CA sử dụng để ngăn chặn các tình huống trong đó một CA có thể đi lừa đảo và cố gắng chứng nhận một tên miền mà không phải là chủ sở hữu của tên miền đó.
• Chữ ký số thay thế cho RSA. Trong trường hợp này, gốc của Cây Merkle hoạt động như một khóa chung và các nút riêng lẻ được sử dụng làm chữ ký một lần. Gần đây, một số nghiên cứu khác đã được thực hiện để cải tiến các kỹ thuật này vì nó được chứng minh lý thuyết là có tiềm năng chống lại các cuộc tấn công dựa trên các thuật toán thám mã lượng tử (không giống như RSA).

Kết luận

Cây Merkle là một thành phần không thể thiếu của blockchain. Merkle tree cho phép blockchain hoạt động hiệu quả trong việc đảm bảo tính bất biến và chứng minh tính toàn vẹn của giao dịch. Hiểu được vai trò của chúng trong các mạng phân tán và công nghệ cơ bản của các hàm băm mật mã là rất quan trọng để nắm bắt các khái niệm cơ bản trong tiền điện tử hay blockchain. Hiện nay các kiến trúc cây Merkle vẫn đang tiếp tục được phát triển thành các hệ thống lớn hơn và phức tạp hơn, cũng như được ứng dụng nhiều hơn trong các hệ thống blockchain trong thực tế.

Chia sẻ