Bukti Merkle untuk integritas data offchain

penyimpanan

Lanjutan

Ori Pomerantz

30 Desember 2021

11 menit baca

Pengantar

Idealnya kita ingin menyimpan semuanya di penyimpanan Ethereum, yang disimpan di ribuan komputer dan memiliki ketersediaan yang sangat tinggi (data tidak dapat disensor) dan integritas (data tidak dapat dimodifikasi dengan cara yang tidak sah), tetapi menyimpan kata 32-byte biasanya membutuhkan biaya 20.000 gas. Saat saya menulis ini, biaya tersebut setara dengan $6,60. Pada 21 sen per byte, ini terlalu mahal untuk banyak penggunaan.

Untuk memecahkan masalah ini, ekosistem Ethereum mengembangkan banyak cara alternatif untuk menyimpan data secara terdesentralisasi. Biasanya cara-cara ini melibatkan pertukaran antara ketersediaan dan harga. Namun, integritas biasanya terjamin.

Dalam artikel ini Anda akan mempelajari cara memastikan integritas data tanpa menyimpan data di blockchain, menggunakan bukti Merkle (opens in a new tab).

Bagaimana cara kerjanya?

Secara teori kita bisa saja menyimpan hash data secara onchain, dan mengirimkan semua data dalam transaksi yang membutuhkannya. Namun, ini masih terlalu mahal. Satu byte data untuk sebuah transaksi membutuhkan biaya sekitar 16 gas, saat ini sekitar setengah sen, atau sekitar $5 per kilobyte. Pada $5000 per megabyte, ini masih terlalu mahal untuk banyak penggunaan, bahkan tanpa biaya tambahan untuk melakukan hash pada data.

Solusinya adalah dengan berulang kali melakukan hash pada subset data yang berbeda, sehingga untuk data yang tidak perlu Anda kirim, Anda cukup mengirimkan hash. Anda melakukan ini menggunakan pohon Merkle (Merkle tree), sebuah struktur data pohon di mana setiap node adalah hash dari node-node di bawahnya:

Hash akar (root hash) adalah satu-satunya bagian yang perlu disimpan secara onchain. Untuk membuktikan nilai tertentu, Anda memberikan semua hash yang perlu digabungkan dengannya untuk mendapatkan akar. Misalnya, untuk membuktikan C Anda memberikan D, H(A-B), dan H(E-H).

Implementasi

Kode sampel disediakan di sini (opens in a new tab).

Kode offchain

Dalam artikel ini kita menggunakan JavaScript untuk komputasi offchain. Sebagian besar aplikasi terdesentralisasi memiliki komponen offchain mereka dalam JavaScript.

Membuat akar Merkle

Pertama kita perlu memberikan akar Merkle ke rantai.

1const ethers = require("ethers")

Kita menggunakan fungsi hash dari paket ethers (opens in a new tab).

1// The raw data whose integrity we have to verify. The first two bytes a // Data mentah yang integritasnya harus kita verifikasi. Dua byte pertama a
2// are a user identifier, and the last two bytes the amount of tokens the // adalah pengidentifikasi pengguna, dan dua byte terakhir adalah jumlah token yang
3// user owns at present. // dimiliki pengguna saat ini.
4const dataArray = [
5  0x0bad0010, 0x60a70020, 0xbeef0030, 0xdead0040, 0xca110050, 0x0e660060,
6  0xface0070, 0xbad00080, 0x060d0091,
7]

Mengodekan setiap entri ke dalam bilangan bulat 256-bit tunggal menghasilkan kode yang kurang dapat dibaca dibandingkan menggunakan JSON, misalnya. Namun, ini berarti pemrosesan yang jauh lebih sedikit untuk mengambil data dalam kontrak, sehingga biaya gas jauh lebih rendah. Anda dapat membaca JSON secara onchain (opens in a new tab), hanya saja itu ide yang buruk jika bisa dihindari.

1// The array of hash values, as BigInts // Array nilai hash, sebagai BigInt
2const hashArray = dataArray

Dalam kasus ini, data kita pada awalnya adalah nilai 256-bit, jadi tidak diperlukan pemrosesan. Jika kita menggunakan struktur data yang lebih rumit, seperti string, kita perlu memastikan kita melakukan hash pada data terlebih dahulu untuk mendapatkan array hash. Perhatikan bahwa ini juga karena kita tidak peduli jika pengguna mengetahui informasi pengguna lain. Jika tidak, kita harus melakukan hash sehingga pengguna 1 tidak akan mengetahui nilai untuk pengguna 0, pengguna 2 tidak akan mengetahui nilai untuk pengguna 3, dll.

1// Convert between the string the hash function expects and the // Konversi antara string yang diharapkan oleh fungsi hash dan
2// BigInt we use everywhere else. // BigInt yang kita gunakan di tempat lain.
3const hash = (x) =>
4  BigInt(ethers.utils.keccak256("0x" + x.toString(16).padStart(64, 0)))

Fungsi hash ethers mengharapkan untuk mendapatkan string JavaScript dengan angka heksadesimal, seperti 0x60A7, dan merespons dengan string lain dengan struktur yang sama. Namun, untuk sisa kode, lebih mudah menggunakan BigInt, jadi kita mengonversi ke string heksadesimal dan kembali lagi.

1// Symmetrical hash of a pair so we won't care if the order is reversed. // Hash simetris dari sebuah pasangan sehingga kita tidak akan peduli jika urutannya dibalik.
2const pairHash = (a, b) => hash(hash(a) ^ hash(b))

Fungsi ini simetris (hash dari a xor (opens in a new tab) b). Ini berarti bahwa ketika kita memeriksa bukti Merkle, kita tidak perlu khawatir tentang apakah akan meletakkan nilai dari bukti sebelum atau sesudah nilai yang dihitung. Pemeriksaan bukti Merkle dilakukan secara onchain, jadi semakin sedikit yang perlu kita lakukan di sana, semakin baik.

Peringatan: Kriptografi lebih sulit daripada kelihatannya. Versi awal artikel ini memiliki fungsi hash hash(a^b). Itu adalah ide yang buruk karena itu berarti jika Anda mengetahui nilai sah dari a dan b, Anda dapat menggunakan b' = a^b^a' untuk membuktikan nilai a' apa pun yang diinginkan. Dengan fungsi ini Anda harus menghitung b' sedemikian rupa sehingga hash(a') ^ hash(b') sama dengan nilai yang diketahui (cabang berikutnya dalam perjalanan menuju akar), yang mana jauh lebih sulit.

1// The value to denote that a certain branch is empty, doesn't // Nilai untuk menunjukkan bahwa cabang tertentu kosong, tidak
2// have a value // memiliki nilai
3const empty = 0n

Ketika jumlah nilai bukan bilangan bulat pangkat dua, kita perlu menangani cabang yang kosong. Cara program ini melakukannya adalah dengan meletakkan nol sebagai tempat penampung (placeholder).

1// Calculate one level up the tree of a hash array by taking the hash of // Hitung satu tingkat ke atas pohon dari array hash dengan mengambil hash dari
2// each pair in sequence // setiap pasangan secara berurutan
3const oneLevelUp = (inputArray) => {
4  var result = []
5  var inp = [...inputArray] // To avoid over writing the input // Add an empty value if necessary (we need all the leaves to be // paired) // Untuk menghindari menimpa input // Tambahkan nilai kosong jika perlu (kita membutuhkan semua daun untuk // dipasangkan)
6
7  if (inp.length % 2 === 1) inp.push(empty)
8
9  for (var i = 0; i < inp.length; i += 2)
10    result.push(pairHash(inp[i], inp[i + 1]))
11
12  return result
13} // oneLevelUp // oneLevelUp
Tampilkan semua

Fungsi ini "memanjat" satu tingkat di pohon Merkle dengan melakukan hash pada pasangan nilai di lapisan saat ini. Perhatikan bahwa ini bukan implementasi yang paling efisien, kita bisa saja menghindari menyalin input dan hanya menambahkan hashEmpty jika sesuai dalam loop, tetapi kode ini dioptimalkan untuk keterbacaan.

1const getMerkleRoot = (inputArray) => {
2  var result
3
4  result = [...inputArray] // Climb up the tree until there is only one value, that is the // root. // // If a layer has an odd number of entries the // code in oneLevelUp adds an empty value, so if we have, for example, // 10 leaves we'll have 5 branches in the second layer, 3 // branches in the third, 2 in the fourth and the root is the fifth // Naik ke atas pohon sampai hanya ada satu nilai, yaitu // akar. // // Jika sebuah lapisan memiliki jumlah entri ganjil, // kode di oneLevelUp menambahkan nilai kosong, jadi jika kita memiliki, misalnya, // 10 daun kita akan memiliki 5 cabang di lapisan kedua, 3 // cabang di lapisan ketiga, 2 di lapisan keempat dan akarnya adalah yang kelima
5
6  while (result.length > 1) result = oneLevelUp(result)
7
8  return result[0]
9}
Tampilkan semua

Untuk mendapatkan akar, panjat terus sampai hanya tersisa satu nilai.

Membuat bukti Merkle

Bukti Merkle adalah nilai-nilai yang akan di-hash bersama dengan nilai yang dibuktikan untuk mendapatkan kembali akar Merkle. Nilai yang akan dibuktikan sering kali tersedia dari data lain, jadi saya lebih suka menyediakannya secara terpisah daripada sebagai bagian dari kode.

1// A merkle proof consists of the value of the list of entries to // Bukti merkle terdiri dari nilai daftar entri untuk
2// hash with. Because we use a symmetrical hash function, we don't // di-hash. Karena kita menggunakan fungsi hash simetris, kita tidak
3// need the item's location to verify the proof, only to create it // membutuhkan lokasi item untuk memverifikasi bukti, hanya untuk membuatnya
4const getMerkleProof = (inputArray, n) => {
5    var result = [], currentLayer = [...inputArray], currentN = n
6
7    // Until we reach the top // Sampai kita mencapai puncak
8    while (currentLayer.length > 1) {
9        // No odd length layers // Tidak ada lapisan dengan panjang ganjil
10        if (currentLayer.length % 2)
11            currentLayer.push(empty)
12
13        result.push(currentN % 2
14               // If currentN is odd, add with the value before it to the proof // Jika currentN ganjil, tambahkan dengan nilai sebelumnya ke bukti
15            ? currentLayer[currentN-1]
16               // If it is even, add the value after it // Jika genap, tambahkan nilai setelahnya
17            : currentLayer[currentN+1])
18
Tampilkan semua

Kita melakukan hash pada (v[0],v[1]), (v[2],v[3]), dll. Jadi untuk nilai genap kita membutuhkan nilai berikutnya, untuk nilai ganjil kita membutuhkan nilai sebelumnya.

1        // Move to the next layer up // Pindah ke lapisan berikutnya di atas
2        currentN = Math.floor(currentN/2)
3        currentLayer = oneLevelUp(currentLayer)
4    }   // while currentLayer.length > 1 // while currentLayer.length > 1
5
6    return result
7}   // getMerkleProof // getMerkleProof

Kode onchain

Terakhir kita memiliki kode yang memeriksa bukti tersebut. Kode onchain ditulis dalam Solidity (opens in a new tab). Optimasi jauh lebih penting di sini karena gas relatif mahal.

1//SPDX-License-Identifier: Public Domain // SPDX-License-Identifier: Public Domain
2pragma solidity ^0.8.0;
3
4import "hardhat/console.sol";

Saya menulis ini menggunakan lingkungan pengembangan Hardhat (opens in a new tab), yang memungkinkan kita untuk memiliki output konsol dari Solidity (opens in a new tab) saat mengembangkan.

1
2contract MerkleProof {
3    uint merkleRoot;
4
5    function getRoot() public view returns (uint) {
6      return merkleRoot;
7    }
8
9    // Extremely insecure, in production code access to // Sangat tidak aman, dalam kode produksi akses ke
10    // this function MUST BE strictly limited, probably to an // fungsi ini HARUS sangat dibatasi, mungkin untuk
11    // owner // pemilik
12    function setRoot(uint _merkleRoot) external {
13      merkleRoot = _merkleRoot;
14    }   // setRoot // setRoot
Tampilkan semua

Fungsi set dan get untuk akar Merkle. Membiarkan semua orang memperbarui akar Merkle adalah ide yang sangat buruk dalam sistem produksi. Saya melakukannya di sini demi kesederhanaan untuk kode sampel. Jangan lakukan ini pada sistem di mana integritas data benar-benar penting.

1    function hash(uint _a) internal pure returns(uint) {
2      return uint(keccak256(abi.encode(_a)));
3    }
4
5    function pairHash(uint _a, uint _b) internal pure returns(uint) {
6      return hash(hash(_a) ^ hash(_b));
7    }

Fungsi ini menghasilkan hash pasangan. Ini hanyalah terjemahan Solidity dari kode JavaScript untuk hash dan pairHash.

Catatan: Ini adalah kasus lain dari optimasi untuk keterbacaan. Berdasarkan definisi fungsi (opens in a new tab), mungkin saja untuk menyimpan data sebagai nilai bytes32 (opens in a new tab) dan menghindari konversi.

1    // Verify a Merkle proof // Verifikasi bukti Merkle
2    function verifyProof(uint _value, uint[] calldata _proof)
3        public view returns (bool) {
4      uint temp = _value;
5      uint i;
6
7      for(i=0; i<_proof.length; i++) {
8        temp = pairHash(temp, _proof[i]);
9      }
10
11      return temp == merkleRoot;
12    }
13
14}  // MarkleProof // MarkleProof
Tampilkan semua

Dalam notasi matematika, verifikasi bukti Merkle terlihat seperti ini: H(proof_n, H(proof_n-1, H(proof_n-2, ... H(proof_1, H(proof_0, value))...))). Kode ini mengimplementasikannya.

Bukti Merkle dan rollup tidak bisa dicampur

Bukti Merkle tidak bekerja dengan baik dengan rollup. Alasannya adalah bahwa rollup menulis semua data transaksi di L1, tetapi memprosesnya di L2. Biaya untuk mengirimkan bukti Merkle dengan sebuah transaksi rata-rata mencapai 638 gas per lapisan (saat ini satu byte dalam data panggilan membutuhkan biaya 16 gas jika bukan nol, dan 4 jika nol). Jika kita memiliki 1024 kata data, bukti Merkle membutuhkan sepuluh lapisan, atau total 6380 gas.

Melihat contoh pada Optimism (opens in a new tab), menulis gas L1 membutuhkan biaya sekitar 100 gwei dan gas L2 membutuhkan biaya 0,001 gwei (itu adalah harga normal, bisa naik saat terjadi kepadatan). Jadi untuk biaya satu gas L1 kita dapat menghabiskan seratus ribu gas pada pemrosesan L2. Dengan asumsi kita tidak menimpa penyimpanan, ini berarti kita dapat menulis sekitar lima kata ke penyimpanan di L2 dengan harga satu gas L1. Untuk satu bukti Merkle, kita dapat menulis seluruh 1024 kata ke penyimpanan (dengan asumsi kata-kata tersebut dapat dihitung secara onchain sejak awal, daripada disediakan dalam sebuah transaksi) dan masih memiliki sebagian besar sisa gas.

Kesimpulan

Dalam kehidupan nyata, Anda mungkin tidak akan pernah mengimplementasikan pohon Merkle sendiri. Ada pustaka yang terkenal dan telah diaudit yang dapat Anda gunakan dan secara umum, yang terbaik adalah tidak mengimplementasikan primitif kriptografi sendiri. Namun saya harap sekarang Anda memahami bukti Merkle dengan lebih baik dan dapat memutuskan kapan bukti tersebut layak digunakan.

Perhatikan bahwa meskipun bukti Merkle menjaga integritas, mereka tidak menjaga ketersediaan. Mengetahui bahwa tidak ada orang lain yang dapat mengambil aset Anda adalah penghiburan kecil jika penyimpanan data memutuskan untuk melarang akses dan Anda juga tidak dapat membangun pohon Merkle untuk mengaksesnya. Jadi pohon Merkle paling baik digunakan dengan semacam penyimpanan terdesentralisasi, seperti IPFS.

Lihat di sini untuk karya saya yang lain (opens in a new tab).

Pembaruan terakhir halaman: 3 Maret 2026