Merkle Tree là công nghệ quan trọng trong việc xác minh nhanh chóng, an toàn các giao dịch trong các block trên các hệ thống blockchain. Trong bài viết này chúng ta cùng nhau đi tìm hiểu về công nghệ Merkle Tree là gì và tầm quan trọng của công nghệ Merkle Tree trong Blockchain.
Xem thêm: Funding rate là gì? Hướng dẫn chi tiết Funding rate dành cho người mới
Merkle Tree là gì?
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.
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.
Cách cây Merkle hoạt động
Dưới đây là một ví dụ đơn giản giúp bạn hình dung cách hoạt động của cây Merkle:
Block xyz có A, B, C và D là bốn giao dịch, tất cả đều được thực hiện trên cùng một block. Mỗi giao dịch sau đó được hashed như sau:
- Hash A.
- Hash B.
- Hash C.
- Hash D.
Các hash được ghép nối với nhau, dẫn đến:
- Hash AB.
- Hash CD.
Và do đó, Merkle Tree của block được hình thành bằng cách kết hợp hai hàm hash này – hash ABCD. Giá trị hash cuối cùng này gọi là Merkle root, nó cung cấp một bản tóm tắt về tất cả các giao dịch mà nó chứa trong một block.
Merkle tree tóm tắt toàn bộ các giao dịch trong một khối bằng phương pháp tạo dấu hiệu đặc trưng ( trị giá băm ) của toàn thể các giao dịch, từ đó cho phép người dùng dễ dàng xác minh làm rõ xem một giao dịch có hiện hữu trong một khối hay không.
Merkle tree được tạo bằng phương pháp triền miên băm các cặp nút cho đến khi chỉ còn lại một trị giá băm ( trị giá băm này có tên là hash root hoặc merkle root ) . Các trị giá băm được tính từ dưới lên, bắt đầu từ các mua bán riêng lẻ ( được biết với tên các ID giao dịch ).
Mỗi nút lá là một trị giá băm của thông tin thương vụ và mỗi nút không phải là nút lá là một trị giá băm của các trị giá băm liền trước đây.
Hầu hết các merkle tree là các cây nhị phân , có thể hiểu là mỗi nút cha có thể có lớn nhất hai nhánh con. Về phương diện kỹ thuật , bạn nhiều khả năng tăng tăng số nút con của cây lên, và tạo nên những dạng cây merkle không phải dạng nhị phân. Ngoài ra trên thực tế cây nhị phân vẫn được dùng nhiều nhất. Với merkle tree nhị phân thỉnh cầu số nút lá chẵn . Nếu lượng thương vụ là số lẻ, hàm băm sau cùng sẽ được nhân đôi 1 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.
Tất cả dữ liệu trong giao dịch sẽ được Merkle Root tóm tắt lại và được lưu trữ trong tiêu đề khối. Nó sẽ duy trì toàn bộ tính toàn vẹn của dữ liệu. Nếu có thay đổi 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 giao dịch. Do đó khi sử dụng Merkle Tree sẽ cho phép bạn kiểm tra nhanh chóng và đơn giản xem liệu giao dịch có nằm trong 1 khối hay không?
Kể từ khi được xây dựng , cây merkle có khả năng đồng thuận mọi người điều tra tính vẹn toàn của thông tin chỉ bằng giải pháp duyệt cây merkle từ hash root với độ phức tạp logarit ( sau một thời gian này còn có tên gọi là chứng cứ merkle ). Chứng cứ merkle vận hành bằng giải pháp tạo lại nhánh chứa đoạn thông tin từ gốc đến đoạn thông tin cần được xác nhận. Trong chẳng hạn trên , nếu mọi người muốn xác nhận khối thông tin l3, mọi người có nguồn gốc từ hash root, và cần được đưa các trị giá h 1-1 và h0. Mọi người sẽ băm l3 để lấy trị giá h 1-0, tiếp theo ghép và băm h 1-1 với h 1-0 để hợp thành h1, về sau ghép và băm hệ quả của điều này với h 0. nếu kết quả là cùng một quần thể với trị giá tại hash root, điều này có thể hiểu là l3 thật sự là 1 phần của thông tin trong cây merkle và không bị thay đổi.
Nguồn: https://danchoitienao.com/merkle-tree-la-gi/
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ì.
Tại sao Merkle Tree lại cần thiết cho sự phát triển của Blockchain?
Merkle Tree 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 (hash) của nhiều block dữ liệu khác nhau, nó tóm tắt tất cả các giao dịch trong một block, từ đó Merkle Tree cho phép xác minh nội dung nhanh chóng và an toàn trên các bộ dữ liệu lớn và xác minh tính nhất quán của dữ liệu.
Hãy tưởng tượng nếu Bitcoin không áp dụng Merkle trees, thì mọi node trên mạng internet buộc phải chưa bỏ đi một phiên bản phát triển hoàn thiện của mọi mua bán bitcoin từng được làm. Những người có khả năng hình dung lượng tin tức đó rất đồ sộ. Merkle trees là một phương án cho chuyện này, merkle tree tách thông tin chứng cớ ( proof ) khỏi chính thông tin gốc, từ đó giảm lượng dữ liệu phải gìn giữ nguyên lành trên blockchain.
Ích lợi của Merkle Tree trong Blockchain
Cây Merkle có nhiều cách sử dụng khác nhau, trong bài viết này, mình sẽ tập trung vào tầm quan trọng của cấu trúc này đối với các blockchain. Cây Merkle rất quan trọng đối với Bitcoin và nhiều loại cryptocurrency khác.
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.
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ử!
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:
- StateRoot: đại diện cho trạng thái của khối, được cập nhật theo thời gian.
- ReceiptsRoot: chứa các biên lai giao dịch trong khối.
- 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).
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 mua bán đượ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, sau cùng các trị giá băm này được xây dựng thành cây merkle chỉnh chu với Merkle root được tích trữ trong đầu đề khối. Xây dựng này tạo nên vài ba quyền lợi riêng biệt.
Thứ nhất, nó đồng thuận hiện hữu các nút xác minh làm rõ chi trả giản dị ( SPV ) , còn được biết với tên một vài ứng dụng khách hạng nhẹ. Các nút này không phải tải xuống tất cả blockchain Bitcoin, mà chỉ cần tải về các tít khối của hệ thống dài nhất. Chuyện này giúp tránh lãng phí khá nhiều tiến trình nhân diện và tích trữ blockchain bởi khối lượng thông tin của blockchain được tính với cuối tháng tám năm 2017 đã trở thành 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 tìm thấy rằng các title khối được dự trữ mà chúng vẫn đang hoạt động là 1 phần của hệ thống dài nhất. Về sau, một nút spv có khả năng định vị tình trạng của thương vụ bằng giải pháp dùng chứng cứ merkle để ánh xạ mua bán đến một cây merkle chi tiết với merkle root tương xứng trong đầu đề khối là 1 phần của hệ thống dài nhất.
Không những vậy, cây merkle trong bitcoin còn đồng thuận cắt tỉa hệ thống khối để tiết kiệm không gian lưu trữ . điều đó là vì chỉ có hash root được tích trữ trong title khối, trên cơ sở đó, các khối cũ nhiều khả năng được tỉa tót bằng giải pháp xóa bỏ những nhánh không cần phải có của cây merkle nhưng chỉ không vứt đi những thứ thiết yếu cho chứng cứ merkle.
Kết luận
Merkle Tree là một thành phần phải có của blockchain. Merkle tree đồng ý blockchain công tác hữu hiệu trong lĩnh vực bảo đảm tính bất biến và chỉ ra tính vẹn toàn của giao dịch. Thấy được rằng chức năng vai trò của chúng trong các mạng chia nhỏ và kỹ thuật chủ đạo của các hàm băm mật mã là cực kỳ quan trọng để am hiểu các khái niệm căn bản trong tiền điện tử hay blockchain. Ngày nay các kiến trúc cây merkle vẫn đang tiếp tục được tiến triển thành những hệ thống to hơn và phức tạp hơn và được sử dụng phần nhiều hơn trong những hệ thống blockchain trong thực tế.