Cách triển khai cây Merkle một cách vững chắc

Cây Merkle là cây nhị phân giúp xác minh nội dung của các cấu trúc dữ liệu lớn một cách hiệu quả và an toàn. Khái niệm về cây này được đề xuất và cấp bằng sáng chế vào năm 1982 bởi Ralph Merkle, một nhà mật mã người Mỹ.

Độ dài của hàm băm vẫn giữ nguyên đối với bất kỳ lượng dữ liệu đầu vào nào. Các đỉnh lá chứa các giá trị băm từ các khối dữ liệu, trong khi các đỉnh bên trong bao gồm các giá trị băm từ việc cộng các giá trị ở hai đỉnh con. Đổi lại, đỉnh gốc bao gồm hàm băm của toàn bộ tập dữ liệu.

Lý thuyết

Ban đầu, có một tập hợp dữ liệu không liên quan đến nhau dưới bất kỳ hình thức nào. Đối với mỗi khối dữ liệu (trong bối cảnh chuỗi khối giao dịch), chúng ta cần tính toán hàm băm của khối. Số lượng khối dữ liệu phải là 2^N , vì khi cây được xây dựng, các khối trước đó sẽ được băm theo cặp ở mỗi lần lặp. Sau đó, một cặp băm được nhóm lại với nhau và một hàm băm mới được tạo dựa trên chúng. Quá trình băm sẽ tiếp tục miễn là có thứ gì đó để nhóm ở mỗi cấp và nó sẽ dừng khi chỉ còn một cặp mà từ đó thu được hàm băm gốc – gốc Merkle –.

H(1-2) = keccak256(H(1) + H(2))

H(3-4) = keccak256(H(3) + H(4))

H(5-6) = keccak256(H(5) + H(6))

H(7-8) = keccak256(H(7) + H(8))

H(1-2-3-4) = keccak256(H(1-2) + H(3-4))

H(5-6-7-8) = keccak256(H(5-6) + H(7-8))

H(1-2-3-4-5-6-7-8) = keccak256(H(1-2-3-4) + H(5-6-7-8))

Khi đã có root, chúng ta có thể xác thực dữ liệu. Nếu hàm băm gốc khớp với hàm băm ban đầu thì mọi thứ đều ổn, dữ liệu hợp lệ. Cũng có thể kiểm tra một cách hiệu quả xem liệu dữ liệu nhất định có trong cấu trúc cây hay không.

Giả sử chúng ta muốn kiểm tra xem hàm băm H2 có trong cây hay không. Bằng chứng sẽ là một mảng dữ liệu: H1 , H3-4 , H5-6-7-8 . Nhờ những giá trị băm này, chúng ta có thể xây dựng lại hàm băm gốc:

H(1-2-3-4-5-6-7-8) = keccak256(keccak256(keccak256(H(1) + H(2)) + H(3-4)) + H(5-6-7-8))

Sau đó, chúng tôi so sánh hàm băm kết quả với hàm băm ban đầu. Nếu chúng khớp nhau, điều đó có nghĩa là hàm băm H2 có trong cây.

Luyện tập

Bây giờ chúng ta hãy xem cách triển khai cây Merkle và xác thực dữ liệu trong Solidity.

Để đơn giản, chúng tôi sẽ viết mảng giao dịch trực tiếp vào blockchain, cũng như mảng băm. Vì chúng ta sẽ sử dụng hàm keccak256 tích hợp sẵn, hàm này trả về giá trị băm 32 byte nên kiểu dữ liệu của mảng băm sẽ là bytes32 . Mảng cũng sẽ có độ dài động. Nói chung, độ dài của mảng băm sẽ không bằng độ dài của mảng giao dịch, vì nó sẽ chứa các giá trị băm được tạo ra. Chúng tôi có thể tính toán trước độ dài, nhưng để đơn giản hóa mã, chúng tôi sẽ không làm như vậy. Nếu muốn, bạn có thể đặt từng mảng này public và đọc giá trị băm của các giao dịch.

Chúng tôi sẽ tạo ra hashes trong hàm tạo. Bước đầu tiên là đếm số băm cho các khối có transactions trong vòng lặp. Sau đó, ở mỗi cấp độ của cây, số lượng giá trị băm giảm đi hệ số 2. Vì chúng ta sẽ lưu trữ các giá trị băm trong mảng băm nên độ lệch chỉ số phải được lưu trữ riêng. Trình vòng lặp trong vòng lặp bên trong được tăng thêm 2 vì chúng ta sẽ lấy một vài phần tử khi tính toán và thêm các giá trị băm. Trong abi.encodePacked lần này, chúng tôi sẽ thêm 2 giá trị băm, mỗi giá trị này chúng tôi sẽ đặt các chỉ mục chính xác: đối với phần tử bên trái – giá trị của độ lệch dịch chuyển hiện tại + chỉ mục ở cấp cây hiện tại và đối với phần tử bên phải – tương tự + 1.

Vì vậy, chúng tôi đã xây dựng cây, nhưng mối quan tâm bao gồm việc xác thực dữ liệu. Để làm điều này, hãy viết một hàm validateTransaction nhận một giao dịch và chỉ mục của nó. Thật không may, Solidity không có phương thức find mảng, do đó việc chuyển chỉ mục giao dịch sẽ dễ dàng hơn.

Đầu tiên, hãy tính hàm băm của giao dịch và tạo một loạt bằng chứng. Chúng tôi tìm số lượng bằng chứng tùy thuộc vào độ dài của mảng giao dịch và đặt độ dài của proofsIndexes . Sau đó, ở mỗi cấp độ của cây, chúng ta tìm phần tử cần thiết, tùy thuộc vào chỉ mục, lấy phần tử bên phải hoặc bên trái, có tính đến phần bù trong hashes . Sau đó, chúng ta xem qua mảng các chỉ số chứng minh, kiểm tra chỉ số về tính chẵn lẻ và tính toán hàm băm tùy thuộc vào phần tử ở bên trái hay bên phải trong cặp. Cuối cùng, chúng tôi so sánh hàm băm kết quả với hàm băm gốc và trả về kết quả.

Ứng dụng

Có một số ứng dụng của cây Merkle trong blockchain.

• Lưu trữ giao dịch : Ví dụ: trong Bitcoin, một khối giao dịch chỉ lưu trữ merkle_root của các giao dịch của nó. Điều này làm giảm kích thước của khối và tải trên mạng. Sau khi tích lũy một số lượng giao dịch nhất định, có thể xóa các giao dịch cũ để tiết kiệm dung lượng nhưng bản thân các khối vẫn không thay đổi vì chúng chỉ lưu trữ phần gốc của cây.
• Khai thác : Khối bitcoin bao gồm hai phần – tiêu đề khối và danh sách giao dịch. Để tránh phải tính toán lại các giá trị băm giao dịch mỗi lần, chúng được xếp thành hàng trong cây Merkle, sau đó tiêu đề khối được băm thay vì toàn bộ khối và một số nonce ngẫu nhiên được lấy. Khi khối được gửi đến các nút khác, gốc của danh sách giao dịch sẽ được tính toán và nếu nó không khớp với gốc trong tiêu đề thì khối sẽ bị từ chối.
• Xác minh : Bản chất của xác minh là kiểm tra mà không cần phải tải xuống toàn bộ blockchain. Quá trình này được đơn giản hóa rất nhiều và cũng cho phép xác nhận sự tồn tại của dữ liệu mà không tiết lộ thông tin về dữ liệu, điều này có thể hữu ích cho việc xác minh thông tin nhạy cảm.

Bản tóm tắt

Nếu không có cây Merkle, chuỗi khối sẽ quá cồng kềnh và bằng chứng Merkle cho phép xác minh tính xác thực của dữ liệu một cách hiệu quả về mặt chi phí.

Cây Merkle được sử dụng tích cực trong các chuỗi khối (ví dụ: Bitcoin, Ethereum) để lưu trữ các giao dịch một cách hiệu quả, nhưng đây không phải là ứng dụng duy nhất. Ví dụ: sau sự sụp đổ của sàn giao dịch FTX, nhiều sàn giao dịch đã triển khai cơ chế Bằng chứng dự trữ, sử dụng cây Merkle.