Bukti Merkle untuk integritas data luring

Pendahuluan

Idealnya, kita ingin menyimpan segala sesuatu di penyimpanan Ethereum, yang tersimpan di seluruh ribuan komputer dan memiliki ketersediaan (data tidak dapat disensor) dan integritas (data tidak dapat dimodifikasi dalam cara yang tidak diotorisasi) sangat tinggi, tetapi menyimpan satu kata berukuran 32 bita biasanya memerlukan 20.000 gas. Ketika saya menulis ini, biaya tersebut setara dengan $6,60. Dengan harga 21 sen per bita, penggunaan rutin ini terlalu mahal.

To solve this problem the Ethereum ecosystem developed many alternative ways to store data in a decentralized fashion. Biasanya, berbagai cara tersebut melibatkan pertukaran antara ketersediaan dan harga. Namun, integritas biasanya terjamin.

Dalam artikel ini, Anda belajar cara memastikan integritas data tanpa menyimpan data di rantai blok, menggunakan bukti Merkle(opens in a new tab).

Bagaimana cara kerjanya?

Dalam teori, kita hanya dapat menyimpan hash data di rantai, dan mengirimkan semua data dalam transaksi yang memerlukannya. Namun, masih terlalu mahal. Satu bita data dari transaksi memerlukan sekitar 16 gas, saat ini kira-kira setengah sen, atau $5 per kilobita. Dengan harga $5000 per megabita, masih terlalu mahal untuk penggunaan rutin, bahkan tanpa biaya tambahan pembuatan hash data.

Solusinya adalah membuat hash subset data berbeda secara berulang, sehingga untuk data yang tidak perlu Anda kirimkan, Anda cukup mengirimkan satu hash. Anda melakukannya menggunakan pohon Merkle, struktur data pohon di mana setiap simpul adalah hash dari simpul di bawahnya:

Hash akar adalah satu-satunya bagian yang perlu disimpan di rantai. Untuk membuktikan nilai tertentu, Anda menyediakan semua hash yang perlu digabungkan dengannya untuk mendapatkan akarnya. Contohnya, untuk membuktikan C Anda memberikan nilai D, H(A-B), dan H(E-H).

Penerapan

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

Kode di luar rantai

Dalam artikel ini, kita menggunakan JavaScript untuk komputasi di luar rantai. Sebagian besar aplikasi terdesentralisasi memiliki komponen di luar rantai mereka dalam JavaScript.

Membuat akar Merkle

Pertama, kita perlu menyediakan akar Merkle untuk 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
2// are a user identifier, and the last two bytes the amount of tokens the
3// user owns at present.
4const dataArray = [
5  0x0bad0010, 0x60a70020, 0xbeef0030, 0xdead0040, 0xca110050, 0x0e660060,
6  0xface0070, 0xbad00080, 0x060d0091,
7]

Contohnya, mengodekan setiap entri menjadi satu bilangan bulat 256-bit akan menghasilkan kode yang kurang dapat terbaca dibandingkan dengan penggunaan JSON. Namun, proses ini menyebabkan proses penerimaan data dalam kontrak menjadi sangat berkurang, sehingga biaya gas lebih rendah. Anda dapat membaca JSON pada rantai(opens in a new tab), hanya saja sebaiknya dapat dihindari.

1// The array of hash values, as BigInts
2const hashArray = dataArray

Dalam kasus ini, data kita dimulai dengan nilai 256-bit, sehingga tidak perlu melakukan pemrosesan. Jika kita menggunakan struktur data yang lebih rumit, seperti string, kita perlu memastikan untuk melakukan hash data terlebih dulu untuk mendapatkan susunan hash. Perlu diperhatikan bahwa proses ini juga terjadi sehingga kita tidak peduli jika pengguna mengetahui informasi pengguna lain. Jika tidak, kita harus melakukan hash agar pengguna 1 tidak mengetahui nilai untuk pengguna 0, pengguna 2 tidak mengetahui nilai untuk pengguna 3, dst.

1const pairHash = (a, b) =>
2  BigInt(ethers.utils.keccak256("0x" + (a ^ b).toString(16).padStart(64, 0)))

Fungsi hash ethers diharapkan untuk mendapatkan string JavaScript dengan angka heksadesimal, seperti 0x60A7, dan merespon dengan string lainnya dalam struktur yang sama. Namun, untuk bagian kode lainnya lebih mudah menggunakan BigInt, sehingga kita mengonversi ke string heksadesimal dan sebaliknya.

Fungsi ini bersifat simetris (hash dari a xor(opens in a new tab) b). Artinya, saat kita memeriksa bukti Merkle, kita tidak perlu mengkhawatirkan apakah harus meletakkan nilai bukti sebelum atau sesudah nilai yang dihitung. Pemeriksaan bukti Merkle diselesaikan pada rantai, sehingga semakin sedikit yang perlu kita lakukan di sana, semakin baik.

1// The value to denote that a certain branch is empty, doesn't
2// have a value
3const empty = 0n

Saat angka nilai bukan merupakan pangkat dua dari bilangan bulat, kita perlu menangani cabang-cabang kosongnya. Cara program berikut melakukannya adalah dengan meletakkan nol sebagai pengganti.

1// Calculate one level up the tree of a hash array by taking the hash of
2// each pair in sequence
3const oneLevelUp = (inputArray) => {
4  var result = []
5  var inp = [...inputArray] // To avoid over writing the input
6
7  // Add an empty value if necessary (we need all the leaves to be
8  // paired)
9  if (inp.length % 2 === 1) inp.push(empty)
10
11  for (var i = 0; i < inp.length; i += 2)
12    result.push(pairHash(inp[i], inp[i + 1]))
13
14  return result
15} // oneLevelUp
Tampilkan semua

Fungsi ini "memanjat" satu tingkat dalam pohon Merkle dengan melakukan hash pada pasangan nilai pada lapisan saat ini. Perlu diingat bahwa fungsi ini bukan merupakan penerapan yang paling efisien, kita dapat menghindari menyalin input dan hanya menambahkan hashEmpty apabila memungkinkan dalam perulangan, tetapi kode ini dioptimasi supaya mudah dibaca.

1const getMerkleRoot = (inputArray) => {
2  var result
3
4  result = [...inputArray]
5
6  // Climb up the tree until there is only one value, that is the
7  // root.
8  //
9  // If a layer has an odd number of entries the
10  // code in oneLevelUp adds an empty value, so if we have, for example,
11  // 10 leaves we'll have 5 branches in the second layer, 3
12  // branches in the third, 2 in the fourth and the root is the fifth
13  while (result.length > 1) result = oneLevelUp(result)
14
15  return result[0]
16}
Tampilkan semua

Untuk sampai pada akar, panjat hingga tersisa hanya satu nilai.

Membuat bukti Merkle

Bukti Merkle merupakan nilai untuk melakukan hash secara bersamaan dengan nilai yang dibuktikan untuk mengembalikan akar Merkle. Nilai yang dibuktikan sering kali tersedia dari data lainnya, sehingga saya memilih untuk menyediakannya secara terpisah dibandingkan sebagai bagian dari kode.

1// A merkle proof consists of the value of the list of entries to
2// hash with. Because we use a symmetrical hash function, we don't
3// need the item's location to verify the proof, only to create it
4const getMerkleProof = (inputArray, n) => {
5    var result = [], currentLayer = [...inputArray], currentN = n
6
7    // Until we reach the top
8    while (currentLayer.length > 1) {
9        // No odd length layers
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
15            ? currentLayer[currentN-1]
16               // If it is even, add the value after it
17            : currentLayer[currentN+1])
18
Tampilkan semua

Kita melakukan hash (v[0],v[1]), (v[2],v[3]), dll. Jadi, untuk nilai genap, kita memerlukan nilai selanjutnya, untuk nilai ganjil diperlukan nilai sebelumnya.

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

Kode di dalam rantai

Akhirnya, kita memiliki kode yang memeriksa bukti tersebut. Kode di dalam rantai ditulis dalam Solidity(opens in a new tab). Optimisasi jauh lebih penting di sini karena gas cukup mahal.

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

Saya menulis ini menggunakan lingkungan pengembangan Hardhat(opens in a new tab), sehingga kita dapat memiliki output konsol dari Solidity(opens in a new tab) ketika 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
10    // this function MUST BE strictly limited, probably to an
11    // owner
12    function setRoot(uint _merkleRoot) external {
13      merkleRoot = _merkleRoot;
14    }   // setRoot
Tampilkan semua
 Salin

Atur dan dapatkan fungsi untuk akar Merkle. Letting everybody update the Merkle root is an extremely bad idea in a production system. Saya melakukannya di sini demi menyederhanakan kode sampel. Jangan melakukannya pada sistem di mana integritas data benar-benar penting.

1    function pairHash(uint _a, uint _b) internal pure returns(uint) {
2      return uint(keccak256(abi.encode(_a ^ _b)));
3    }
 Salin

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

Catatan: Ini merupakan kasus optimisasi lain untuk keterbacaan. Didasarkan pada definisi fungsi(opens in a new tab), kasus ini mungkin dapat terjadi untuk menyimpan data sebagai nilai bytes32(opens in a new tab) dan menghindari konversi.

1    // Verify a Merkle proof
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
Tampilkan semua
 Salin

Dalam notasi matematis, 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 menerapkan hal tersebut.

Bukti Merkle dan rollups tidak bercampur

Bukti Merkle tidak bekerja baik dengan rollups. Alasannya, karena rollups menulis seluruh data transaksi di L1, tetapi memprosesnya di L2. Biaya untuk mengirimkan bukti Merkle dengan transaksi rata-rata hingga 638 gas per lapisan (saat ini, satu bita dalam data panggilan seharga 16 gas jika bukan nol, dan 4 gas jika nol). Jika kita memiliki 1024 kata pada data, bukti Merkle memerlukan 10 lapisan, atau totalnya 6380 gas.

Seperti dilihat pada contoh di Optimism(opens in a new tab), menulis gas L1 berbiaya sekitar 100 gwei dan gas L2 berbiaya 0.001 gwei (itu adalah harga normal, dapat naik saat arus padat). Jadi, dengan biaya satu gas L1, kita dapat membelanjakan ratusan ribu gas pada pemrosesan L2. Asumsikan kita tidak menimpa penyimpanan, artinya kita dapat menulis sekitar lima kata ke penyimpanan pada L2 dengan harga satu gas L1. Untuk satu bukti Merkle, kita dapat menulis seluruh 1024 kata ke penyimpanan (dengan anggapan kata-kata tersebut sejak awal dapat dihitung pada rantai, daripada disediakan dalam transaksi) dan masih memiliki banyak gas yang tersisa.

Kesimpulan

Dalam kehidupan nyata, Anda mungkin tidak pernah menerapkan pohon Merkle sendiri. Ada pustaka-pustaka terkenal dan teraudit yang dapat Anda gunakan dan secara umum, paling baik untuk tidak menerapkan primitif kriptografik sendiri. Namun, saya harap bahwa sekarang Anda memahami bukti Merkle lebih baik dan dapat memutuskan waktu bukti tersebut dapat digunakan.

Perhatikan bahwa ketika bukti-bukti Merkle mempertahankan integritas, bukti-bukti tersebut tidak mempertahankan ketersediaan. Mengetahui bahwa tidak seorang pun dapat mengambil aset Anda adalah sedikit penghiburan jika penyimpanan data memutuskan untuk menolak akses dan Anda juga tidak dapat membangun pohon Merkle untuk mengaksesnya. Jadi, pohon Merkle paling baik digunakan dengan beberapa jenis penyimpanan terdesentralisasi, seperti IPFS.