Bằng chứng Merkle cho tính toàn vẹn dữ liệu ngoại tuyến
Giới thiệu
Lý tưởng nhất là chúng ta muốn lưu trữ mọi thứ trong bộ nhớ lưu trữ của Ethereum, được lưu trữ trên hàng nghìn máy tính và có tính khả dụng cực cao (dữ liệu không thể bị kiểm duyệt) và tính toàn vẹn (dữ liệu không thể bị sửa đổi một cách trái phép), nhưng việc lưu trữ một từ 32 byte thường tốn 20.000 gas. Tại thời điểm tôi viết bài này, chi phí đó tương đương 6,60 USD. Với 21 xu cho mỗi byte, chi phí này là quá đắt cho nhiều mục đích sử dụng.
Để giải quyết vấn đề này, hệ sinh thái Ethereum đã phát triển nhiều cách thay thế để lưu trữ dữ liệu theo cách phi tập trung. Thông thường, chúng bao gồm sự đánh đổi giữa tính khả dụng và giá cả. Tuy nhiên, tính toàn vẹn thường được đảm bảo.
Trong bài viết này, bạn sẽ học cách đảm bảo tính toàn vẹn của dữ liệu mà không cần lưu trữ dữ liệu trên chuỗi khối, bằng cách sử dụng bằng chứng Merkle (opens in a new tab).
Nó hoạt động như thế nào?
Về lý thuyết, chúng ta có thể chỉ cần lưu trữ hàm băm của dữ liệu trên chuỗi và gửi tất cả dữ liệu trong các giao dịch yêu cầu nó. Tuy nhiên, cách này vẫn quá tốn kém. Một byte dữ liệu cho một giao dịch tốn khoảng 16 gas, hiện tại khoảng nửa xu, hoặc khoảng 5 USD cho mỗi kilobyte. Với 5000 USD cho mỗi megabyte, chi phí này vẫn quá đắt cho nhiều mục đích sử dụng, ngay cả khi không tính thêm chi phí băm dữ liệu.
Giải pháp là băm liên tục các tập hợp con khác nhau của dữ liệu, vì vậy đối với dữ liệu bạn không cần gửi, bạn có thể chỉ cần gửi một hàm băm. Bạn làm điều này bằng cách sử dụng cây Merkle, một cấu trúc dữ liệu cây trong đó mỗi nút là một hàm băm của các nút bên dưới nó:
Hàm băm gốc là phần duy nhất cần được lưu trữ trên chuỗi. Để chứng minh một giá trị nhất định, bạn cung cấp tất cả các hàm băm cần được kết hợp với nó để có được gốc. Ví dụ: để chứng minh C, bạn cung cấp D, H(A-B), và H(E-H).
Triển khai
Mã mẫu được cung cấp tại đây (opens in a new tab).
Mã ngoài chuỗi
Trong bài viết này, chúng tôi sử dụng JavaScript cho các tính toán ngoài chuỗi. Hầu hết các ứng dụng phi tập trung có thành phần ngoài chuỗi bằng JavaScript.
Tạo gốc Merkle
Đầu tiên, chúng ta cần cung cấp gốc Merkle cho chuỗi.
1const ethers = require("ethers")Chúng tôi sử dụng hàm băm từ gói ethers (opens in a new tab).
1// Dữ liệu thô mà chúng ta phải xác minh tính toàn vẹn. Hai byte đầu tiên2// là mã định danh người dùng và hai byte cuối cùng là số lượng token mà3// người dùng sở hữu tại thời điểm hiện tại.4const dataArray = [5 0x0bad0010, 0x60a70020, 0xbeef0030, 0xdead0040, 0xca110050, 0x0e660060,6 0xface0070, 0xbad00080, 0x060d0091,7]Việc mã hóa mỗi mục nhập thành một số nguyên 256-bit duy nhất sẽ tạo ra mã khó đọc hơn so với việc sử dụng JSON, ví dụ vậy. Tuy nhiên, điều này có nghĩa là xử lý ít hơn đáng kể để truy xuất dữ liệu trong hợp đồng, do đó chi phí gas thấp hơn nhiều. Bạn có thể đọc JSON trên chuỗi (opens in a new tab), nhưng đó là một ý tưởng tồi nếu có thể tránh được.
1// Mảng các giá trị hàm băm, dưới dạng BigInts2const hashArray = dataArrayTrong trường hợp này, dữ liệu của chúng ta ban đầu là các giá trị 256-bit, do đó không cần xử lý. Nếu chúng ta sử dụng một cấu trúc dữ liệu phức tạp hơn, chẳng hạn như chuỗi, chúng ta cần đảm bảo rằng chúng ta băm dữ liệu trước để có được một mảng các hàm băm. Lưu ý rằng điều này cũng là do chúng tôi không quan tâm liệu người dùng có biết thông tin của những người dùng khác hay không. Nếu không, chúng ta sẽ phải băm để người dùng 1 không biết giá trị của người dùng 0, người dùng 2 không biết giá trị của người dùng 3, v.v.
1// Chuyển đổi giữa chuỗi mà hàm băm mong đợi và2// BigInt mà chúng ta sử dụng ở mọi nơi khác.3const hash = (x) =>4 BigInt(ethers.utils.keccak256("0x" + x.toString(16).padStart(64, 0)))Hàm băm ethers mong đợi nhận được một chuỗi JavaScript với một số thập lục phân, chẳng hạn như 0x60A7, và trả về một chuỗi khác có cùng cấu trúc. Tuy nhiên, đối với phần còn lại của mã, việc sử dụng BigInt sẽ dễ dàng hơn, vì vậy chúng ta chuyển đổi sang chuỗi thập lục phân và ngược lại.
1// Băm đối xứng của một cặp để chúng ta không quan tâm nếu thứ tự bị đảo ngược.2const pairHash = (a, b) => hash(hash(a) ^ hash(b))Hàm này là đối xứng (hàm băm của a xor (opens in a new tab) b). Điều này có nghĩa là khi chúng ta kiểm tra bằng chứng Merkle, chúng ta không cần lo lắng về việc đặt giá trị từ bằng chứng trước hay sau giá trị được tính toán. Việc kiểm tra bằng chứng Merkle được thực hiện trên chuỗi, vì vậy chúng ta càng cần làm ít việc ở đó càng tốt.
Cảnh báo:
Mật mã học khó hơn vẻ ngoài của nó.
Phiên bản ban đầu của bài viết này có hàm băm hash(a^b).
Đó là một ý tưởng tồi vì nó có nghĩa là nếu bạn biết các giá trị hợp pháp của a và b, bạn có thể sử dụng b' = a^b^a' để chứng minh bất kỳ giá trị a' mong muốn nào.
Với hàm này, bạn sẽ phải tính toán b' sao cho hash(a') ^ hash(b') bằng một giá trị đã biết (nhánh tiếp theo trên đường đến gốc), điều này khó hơn rất nhiều.
1// Giá trị để biểu thị rằng một nhánh nào đó trống, không2// có giá trị3const empty = 0nKhi số lượng giá trị không phải là lũy thừa nguyên của hai, chúng ta cần xử lý các nhánh trống. Cách chương trình này thực hiện là đặt số không làm trình giữ chỗ.
1// Tính toán một cấp trên cây của một mảng băm bằng cách lấy hàm băm của2// mỗi cặp theo trình tự3const oneLevelUp = (inputArray) => {4 var result = []5 var inp = [...inputArray] // Để tránh ghi đè lên đầu vào // Thêm một giá trị trống nếu cần (chúng ta cần tất cả các lá phải được // ghép cặp)67 if (inp.length % 2 === 1) inp.push(empty)89 for (var i = 0; i < inp.length; i += 2)10 result.push(pairHash(inp[i], inp[i + 1]))1112 return result13} // oneLevelUpHiện tất cảHàm này "leo" lên một cấp trong cây Merkle bằng cách băm các cặp giá trị ở lớp hiện tại. Lưu ý rằng đây không phải là cách triển khai hiệu quả nhất, chúng ta có thể đã tránh sao chép đầu vào và chỉ cần thêm hashEmpty khi thích hợp trong vòng lặp, nhưng mã này được tối ưu hóa để dễ đọc.
1const getMerkleRoot = (inputArray) => {2 var result34 result = [...inputArray] // Leo lên cây cho đến khi chỉ còn một giá trị, đó là // gốc. // // Nếu một lớp có số lượng mục nhập lẻ, // mã trong oneLevelUp sẽ thêm một giá trị trống, vì vậy nếu chúng ta có, ví dụ, // 10 lá, chúng ta sẽ có 5 nhánh ở lớp thứ hai, 3 // nhánh ở lớp thứ ba, 2 ở lớp thứ tư và gốc là lớp thứ năm56 while (result.length > 1) result = oneLevelUp(result)78 return result[0]9}Hiện tất cảĐể có được gốc, hãy leo lên cho đến khi chỉ còn lại một giá trị.
Tạo bằng chứng Merkle
Bằng chứng Merkle là các giá trị cần băm cùng với giá trị đang được chứng minh để lấy lại gốc Merkle. Giá trị cần chứng minh thường có sẵn từ dữ liệu khác, vì vậy tôi thích cung cấp nó một cách riêng biệt thay vì là một phần của mã.
1// Bằng chứng Merkle bao gồm giá trị của danh sách các mục nhập để2// băm cùng. Bởi vì chúng ta sử dụng một hàm băm đối xứng, chúng ta không3// cần vị trí của mục để xác minh bằng chứng, chỉ cần để tạo ra nó4const getMerkleProof = (inputArray, n) => {5 var result = [], currentLayer = [...inputArray], currentN = n67 // Cho đến khi chúng ta lên đến đỉnh8 while (currentLayer.length > 1) {9 // Không có lớp nào có độ dài lẻ10 if (currentLayer.length % 2)11 currentLayer.push(empty)1213 result.push(currentN % 214 // Nếu currentN là số lẻ, hãy thêm giá trị trước nó vào bằng chứng15 ? currentLayer[currentN-1]16 // Nếu nó là số chẵn, hãy thêm giá trị sau nó17 : currentLayer[currentN+1])18Hiện tất cảChúng ta băm (v[0],v[1]), (v[2],v[3]), v.v. Vì vậy, đối với các giá trị chẵn, chúng ta cần giá trị tiếp theo, đối với các giá trị lẻ, chúng ta cần giá trị trước đó.
1 // Di chuyển lên lớp tiếp theo2 currentN = Math.floor(currentN/2)3 currentLayer = oneLevelUp(currentLayer)4 } // while currentLayer.length > 156 return result7} // getMerkleProofMã trên chuỗi
Cuối cùng, chúng ta có mã kiểm tra bằng chứng. Mã trên chuỗi được viết bằng Solidity (opens in a new tab). Tối ưu hóa quan trọng hơn nhiều ở đây vì gas tương đối đắt.
1//SPDX-License-Identifier: Public Domain2pragma solidity ^0.8.0;34import "hardhat/console.sol";Tôi đã viết mã này bằng cách sử dụng môi trường phát triển Hardhat (opens in a new tab), cho phép chúng tôi có đầu ra bảng điều khiển từ Solidity (opens in a new tab) trong khi phát triển.
12contract MerkleProof {3 uint merkleRoot;45 function getRoot() public view returns (uint) {6 return merkleRoot;7 }89 // Cực kỳ không an toàn, trong mã sản xuất, quyền truy cập vào10 // hàm này PHẢI được giới hạn nghiêm ngặt, có thể là đối với một11 // chủ sở hữu12 function setRoot(uint _merkleRoot) external {13 merkleRoot = _merkleRoot;14 } // setRootHiện tất cảCác hàm Set và get cho gốc Merkle. Việc cho phép mọi người cập nhật gốc Merkle là một ý tưởng cực kỳ tồi trong một hệ thống sản xuất. Tôi làm điều đó ở đây vì sự đơn giản cho mã mẫu. Đừng làm điều đó trên một hệ thống mà tính toàn vẹn của dữ liệu thực sự quan trọng.
1 function hash(uint _a) internal pure returns(uint) {2 return uint(keccak256(abi.encode(_a)));3 }45 function pairHash(uint _a, uint _b) internal pure returns(uint) {6 return hash(hash(_a) ^ hash(_b));7 }Hàm này tạo ra một hàm băm cặp. Nó chỉ là bản dịch Solidity của mã JavaScript cho hash và pairHash.
Lưu ý: Đây là một trường hợp khác của việc tối ưu hóa để dễ đọc. Dựa trên định nghĩa hàm (opens in a new tab), có thể lưu trữ dữ liệu dưới dạng giá trị bytes32 (opens in a new tab) và tránh các chuyển đổi.
1 // Xác minh bằng chứng Merkle2 function verifyProof(uint _value, uint[] calldata _proof)3 public view returns (bool) {4 uint temp = _value;5 uint i;67 for(i=0; i<_proof.length; i++) {8 temp = pairHash(temp, _proof[i]);9 }1011 return temp == merkleRoot;12 }1314} // MerkleProofHiện tất cảTrong ký hiệu toán học, việc xác minh bằng chứng Merkle trông như thế này: H(proof_n, H(proof_n-1, H(proof_n-2, ... H(proof_1, H(proof_0, value))...)))`. Mã này thực hiện nó.
Bằng chứng Merkle và các rollup không kết hợp được với nhau
Bằng chứng Merkle không hoạt động tốt với các rollup. Lý do là các rollup ghi tất cả dữ liệu giao dịch trên L1, nhưng xử lý trên L2. Chi phí để gửi một bằng chứng Merkle với một giao dịch trung bình là 638 gas cho mỗi lớp (hiện tại một byte trong dữ liệu cuộc gọi tốn 16 gas nếu nó không phải là số không, và 4 nếu nó là số không). Nếu chúng ta có 1024 từ dữ liệu, một bằng chứng Merkle yêu cầu mười lớp, hoặc tổng cộng 6380 gas.
Ví dụ, khi xem xét Optimism (opens in a new tab), chi phí gas ghi L1 khoảng 100 gwei và chi phí gas L2 là 0,001 gwei (đó là giá thông thường, nó có thể tăng lên khi có tắc nghẽn). Vì vậy, với chi phí của một gas L1, chúng ta có thể chi tiêu một trăm nghìn gas cho việc xử lý L2. Giả sử chúng ta không ghi đè lên bộ nhớ, điều này có nghĩa là chúng ta có thể ghi khoảng năm từ vào bộ nhớ trên L2 với giá của một gas L1. Đối với một bằng chứng Merkle duy nhất, chúng ta có thể ghi toàn bộ 1024 từ vào bộ nhớ (giả sử chúng có thể được tính toán trên chuỗi ngay từ đầu, thay vì được cung cấp trong một giao dịch) và vẫn còn thừa hầu hết gas.
Kết luận
Trong thực tế, bạn có thể không bao giờ tự mình triển khai cây Merkle. Có những thư viện nổi tiếng và đã được kiểm toán mà bạn có thể sử dụng và nói chung, tốt nhất là không nên tự mình triển khai các nguyên hàm mật mã. Nhưng tôi hy vọng rằng bây giờ bạn đã hiểu rõ hơn về bằng chứng Merkle và có thể quyết định khi nào chúng đáng được sử dụng.
Lưu ý rằng trong khi bằng chứng Merkle bảo toàn tính toàn vẹn, chúng không bảo toàn tính khả dụng. Việc biết rằng không ai khác có thể lấy tài sản của bạn chỉ là sự an ủi nhỏ nhoi nếu bộ nhớ dữ liệu quyết định không cho phép truy cập và bạn cũng không thể xây dựng một cây Merkle để truy cập chúng. Vì vậy, cây Merkle được sử dụng tốt nhất với một số loại lưu trữ phi tập trung, chẳng hạn như IPFS.
Xem thêm công việc của tôi tại đây (opens in a new tab).
Lần cập nhật trang lần cuối: 18 tháng 12, 2025
