Merkle Tree là gì? Cây Merkle hoạt động như thế nào?

ByLengkeng13/05/2020
Cây Merkle (Merkle Tree) 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. Trong bitcoin và các loại tiền mã hóa khác, cây Merkle phục vụ để mã hóa dữ liệu blockchain hiệu quả và an toàn hơn. Chúng cũng được gọi là cây băm nhị phân (binary hash trees). 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 ...

1. Merkle Tree là gì?

Cây Merkle, theo một 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.

Merkle Trees là gì?
Merkle Trees là gì?

2. Cây Merkle (Merkle Tree) hoạt động như thế nào?

Tất cả các giao dịch mà người khai thác đã chọn được đặt hàng liên tiếp; trước tiên là giao dịch tạo hoặc coinbase, nếu số lượng giao dịch là số lẻ thì giao dịch cuối cùng được thêm hai lần để tạo số chẵn; số cấp của cây phụ thuộc vào số lượng giao dịch.

Giao dịch đầu tiên được băm thông qua SHA-256 rồi đến giao dịch thứ hai và thứ ba, v.v. Thuật toán băm SHA-256 tạo ra chuỗi 32 byte, vì vậy khi bạn nối chuỗi 32byte với chuỗi 32 byte, bạn sẽ tạo ra chuỗi 64 byte. Điều này sau đó được băm bởi SHA-256 để tạo ra chuỗi 32 byte ngay trên cây merkle cho đến khi tất cả các giao dịch được kết nối.

Câu trả lời tương ứng sau khi cây merkle đã được tính là gốc merkle lại là số 32 byte. Đối với mỗi công cụ khai thác, gốc Merkle thường khác nhau vì cách mỗi công cụ khai thác đặt hàng các giao dịch là khác nhau và do đó, giá trị băm là khác nhau. Điều này có nghĩa là tất cả những người khai thác không chạy qua cùng một bộ tính toán khi họ đang áp dụng ASIC thông qua lực lượng vũ phu để giải quyết bằng chứng công việc (PoS).

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

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

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.

4. 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 cho 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.

Đọc thêm:

Disclaimer: Bài viết mang mục đích cung cấp thông tin, không phải lời khuyên tài chính.

Thảo luận thêm tại

Facebook:https://www.facebook.com/groups/bigcoincommunity

Telegram: https://t.me/Bigcoinnews

Twitter: https://twitter.com/Theblock101_ 

Lengkeng

Lengkeng

"Money is made by sitting, not trading"

5 / 5 (1Bình chọn)

Bài viết liên quan