1. Pengenalan

Pada hari terakhir tahun 2023, Vitalik membagikan roadmap Ethereum untuk 2023 di Twitter, merangkum kemajuan Ethereum selama tahun tersebut. Bagian roadmap “The Verge” menjelaskan bagaimana teknologi Ethereum dapat memverifikasi status blockchain dengan lebih sederhana dan efisien. Konsep inti yang disebutkan di sana adalah Verkle Trees. Jadi, apa itu Verkle Trees, mengapa Ethereum membutuhkannya, dan bagaimana Verkle Trees memecahkan masalah? Tujuan artikel ini adalah menjawab pertanyaan-pertanyaan tersebut bagi pembaca tanpa terlalu mendalam ke dalam kriptografi dan matematika, membantu mereka yang memiliki pemahaman tentang Ethereum untuk dengan cepat memahami konsep Verkle Trees.

2. Kueri yang Dapat Diverifikasi

Teknologi kueri yang dapat diverifikasi banyak diteliti dalam bidang basis data tradisional, terutama digunakan untuk memecahkan masalah kepercayaan dengan basis data eksternal. Dalam banyak skenario, pemilik data mungkin memilih untuk tidak menyimpan data mereka sendiri tetapi mempercayakan kebutuhan basis data mereka kepada pihak ketiga untuk menyediakan layanan basis data (seperti basis data cloud). Namun, karena pihak ketiga tidak selalu dapat dipercaya, kepercayaan hasil kueri yang mereka kembalikan kepada pengguna sulit untuk dijamin. Solusi kueri yang dapat diverifikasi saat ini untuk basis data tradisional umumnya terbagi menjadi dua kategori: yang didasarkan pada ADS (Struktur Data yang Terverifikasi) dan yang didasarkan pada komputasi yang dapat diverifikasi.

ADS adalah teknik kueri yang dapat diverifikasi yang banyak digunakan dalam basis data tradisional, sebagian besar dibangun berdasarkan struktur seperti Pohon Merkle atau struktur akumulatif serupa. Dengan evolusi alat kriptografis, banyak peneliti secara bertahap mulai menjelajahi penggunaan teknik komputasi yang dapat diverifikasi untuk mengatasi masalah dengan kueri yang tidak dapat dipercaya. Beberapa skema komputasi yang dapat diverifikasi berdasarkan protokol Bukti Pengetahuan Nol, seperti SNARK, dapat secara tidak langsung mendukung kueri yang dapat diverifikasi untuk basis data eksternal. Skema-skema ini mendukung berbagai jenis kueri dan menghasilkan informasi verifikasi yang lebih sedikit, tetapi memiliki overhead komputasi yang lebih tinggi.

Saat ini, Ethereum menggunakan Pohon Merkle untuk menerapkan kueri yang dapat diverifikasi, dan teknologi Pohon Verkle juga didasarkan pada teknologi Pohon Merkle. Oleh karena itu, mari kita pertama-tama memperkenalkan Pohon Merkle untuk membantu pembaca memahami peran kueri yang dapat diverifikasi dengan menggunakan mereka sebagai contoh.

3. Pohon Merkle

3.1. Definisi dan Karakteristik Pohon Merkle

Pohon Merkle adalah struktur mirip pohon yang umum digunakan dalam kriptografi, cocok untuk memecahkan masalah integritas data. Di bawah ini adalah struktur Pohon Merkle yang khas: simpul daun mewakili data asli atau nilai hashnya, dan setiap simpul non-daun (internal) berisi hash gabungan dari simpul anaknya.

Merkle Trees memiliki dua karakteristik penting:

1. Ketahanan Terhadap Pencurian: Pohon Merkle biasanya dibangun menggunakan fungsi hash tahan-tabrak, sehingga menjadi sulit secara komputasi untuk menemukan dua pesan yang berbeda namun menghasilkan nilai hash yang sama. Dari struktur Pohon Merkle, jelas bahwa setiap modifikasi data transaksi dalam simpul daun akan mengakibatkan perubahan pada hash root dari pohon.
2. Verifikasi Integritas Efisien dari Kumpulan Data Besar: Verifikator hanya perlu menyimpan root hash dari Pohon Merkle untuk memverifikasi integritas data apa pun. Hal ini dicapai tanpa mentransmisikan rangkaian data lengkap, melainkan dengan menggunakan simpul-simpul saudara sepanjang jalur dari daun ke root, yang dikenal sebagai Jalur Merkle. Simpul-simpul saudara ini dapat digunakan untuk merekonstruksi root hash untuk tujuan verifikasi.

3.2. Bagaimana cara membuat bukti Merkle?

Dalam skenario kueri yang dapat diverifikasi umum, ada pemberi bukti dan pemeriksa. Pemberi bukti perlu menghasilkan bukti dan mengirimkannya ke pemeriksa. Sehubungan dengan jaringan Ethereum, skenario aplikasi khas adalah ketika node ringan (klien yang hanya menyimpan header blok) mengajukan kueri data transaksi dari node penuh atau node arsip (klien dengan semua data) dan mendapatkan bukti Merkle untuk memverifikasi secara lokal apakah hasil kueri tersebut benar.

Bukti Merkle terdiri dari tiga bagian berikut:

1. Hash akar dari pohon Merkle untuk kumpulan data lengkap.
2. Blok data yang integritasnya perlu dibuktikan.
3. Jalur Merkle, yang mencakup nilai dari semua simpul saudara di jalur dari simpul daun ke simpul akar.

Di antara ini, hash akar dari pohon Merkle perlu dikirimkan ke verifikator sebelumnya melalui cara yang dapat dipercaya, dan verifikator harus mempercayai nilai ini. Dalam Ethereum, kehandalan data blok dipastikan oleh algoritma konsensus, dan hash akar dari pohon Merkle terdapat dalam header blok.

Berikut adalah contoh spesifik: ketika pembuktian perlu membuktikan ke verifikator bahwa “4” adalah blok data yang ada dalam kumpulan data, dan verifikator memegang hash root terpercaya “1d25” dari pohon Merkle kumpulan data yang lengkap, maka pembuktian hanya perlu menyediakan semua data yang ditandai dengan warna biru. Dengan asumsi ada n potongan data dalam set tersebut, paling banyak 𝘭𝘰𝘨₂(𝘯) perhitungan hash diperlukan untuk memverifikasi kebenaran blok data apa pun.

Node ringan Ethereum hanya menyinkronkan header blok, yang berisi root Pohon Merkle untuk berbagai set data (pohon status, pohon transaksi, pohon tanda terima). Ketika node ringan meminta node penuh untuk data simpul daun tertentu dalam pohon, node penuh mengembalikan data asli bersama dengan jalur bukti Merkle yang sesuai. Ini memungkinkan node ringan untuk mempercayai kebenaran hasil kueri.

3.3. Varian Pohon Merkle

Berdasarkan fondasi Pohon Merkle, mereka dapat digabungkan dan dimodifikasi dengan struktur data lain untuk mencapai karakteristik baru berdasarkan tujuan yang berbeda. Untuk memenuhi berbagai skenario kueri yang dapat diverifikasi, Pohon Merkle dapat diperluas ke berbagai struktur data yang terindeks, seperti Pohon Merkle-B (MBT). Untuk eksekusi operasi yang efisien seperti penyisipan, penghapusan, dan kueri, tim Ethereum mengusulkan Pohon Patricia Merkle (MPT).

3.3.1. Pohon Merkle-B

Pohon Merkle-B (MBT) terutama digunakan untuk menangani kueri rentang yang dapat diverifikasi. Biarkan 𝑓 menjadi keluaran dari MBT (jumlah node anak untuk setiap node). Berdasarkan struktur pohon B+, setiap node internal dari MBT, selain menyimpan 𝑓 — 1 kunci indeks dan penunjuk ke 𝑓 node anak, juga mempertahankan nilai hash dari semua node anaknya dalam bentuk ringkasan. Di bawah ini adalah representasi struktur node daun dan node internal dalam MBT.

Ketika perlu membuktikan bahwa data yang dikembalikan dari kueri rentang tertentu sesuai dengan rentang yang ditentukan, server yang menghitung Objek Verifikasi (VO) harus terlebih dahulu melakukan dua operasi pencarian dari atas ke bawah untuk menemukan batas kiri dan kanan. Server juga harus mengembalikan semua data dalam batas ini serta hash dari semua cabang yang diperlukan untuk membangun jalur ke hash root.

Kekurangan struktur data ini adalah bahwa VO yang dikembalikan hanya dapat membuktikan bahwa hasil kueri berada dalam rentang kueri yang diminta, tetapi tidak dapat membuktikan bahwa hasil yang dikembalikan lengkap.

3.3.2. Pohon Merkle Patricia

Jika Pohon Merkle naif digunakan untuk menyediakan kueri yang dapat diverifikasi, proses yang memakan waktu untuk membangun kembali akar Pohon Merkle setelah setiap penyisipan atau penghapusan data dapat menjadi signifikan. Selain itu, itu memerlukan pemeliharaan pohon pencarian data tambahan untuk penyimpanan. Pohon Patricia Merkle (MPT) menggabungkan atribut Pohon Radiks (pohon awalan kompak) dan Pohon Merkle, memungkinkannya untuk melakukan penyisipan, penghapusan, dan kueri dalam waktu O(log(N)). Untuk pemahaman yang lengkap tentang MPT, pembaca dapat merujuk ke artikel teknis terperinci tentang subjek tersebut. Artikel ini hanya akan memperkenalkan beberapa definisi dasar dan memberikan contoh untuk membantu pembaca memahami MPT dengan cepat.

Struktur dasar Ethereum menggunakan database key-value untuk penyimpanan, artinya data disimpan dalam bentuk pasangan key-value. MPT juga dipecah menjadi pasangan key-value untuk penyimpanan. Kami mendefinisikan struktur logis simpul MPT sebagai berikut:

• indeks
• jalur
• data

Dalam konteks Pohon Merkle Patricia (MPT), “indeks” mengacu pada kunci dari pasangan kunci-nilai, sedangkan “jalur” yang digabungkan dengan “data” membentuk nilai dari pasangan kunci-nilai. Indeks sebenarnya menyimpan hash dari node pohon Merkle, dan jalur sesuai dengan string jalur yang digunakan dalam pohon awalan untuk menemukan node target. Ethereum menggunakan string heksadesimal sebagai string jalur, dan oleh karena itu lebar MPT adalah 16. Data adalah data target yang sesuai dengan jalur.

Di bawah ini adalah contoh MPT yang telah dioptimalkan dengan awalan yang terkompresi, menyimpan data pasangan kunci-nilai berikut:

{

'cab8': 'anjing',

‘cabe’: ‘kucing’,

‘39’: ‘ayam’,

'395': 'bebek',

'56f0': 'kuda'

}

Untuk menemukan data 'duck' menggunakan jalur '395,' Anda akan memulai dari hash root dan melanjutkan melalui hashA, hashC, dan hashD untuk akhirnya mencapai data target. Berikut adalah panduan langkah demi langkah:

1. Root Hash: Ini adalah titik masuk Pohon Merkle Patricia (MPT), dan Anda akan menggunakannya untuk menemukan node pertama.
2. hashA: Berdasarkan hash akar, Anda akan mendapatkan node atau konten yang diidentifikasi oleh hashA. Karena jalurnya adalah “395,” Anda mencari bagian pohon yang akan membawa Anda ke “3”.
3. hashC: Setelah mengakses konten dari hashA, Anda melanjutkan untuk mengikuti jalur. Segmen selanjutnya, “9”, membawa Anda ke hashC.
4. hashD: Akhirnya, melanjutkan perjalanan, segmen terakhir “5” mengarahkan Anda ke hashD, yang berisi nilai “duck”.

Pada setiap langkah dalam jalur, MPT memanfaatkan sifat-sifat dari Radix Tree, untuk menemukan jalur yang benar berdasarkan kunci, dan Merkle Tree, untuk memastikan integritas data melalui tautan hash. "Jalur-jalur" dalam pohon umumnya direpresentasikan dengan enkoding heksadesimal, yang sesuai dengan faktor percabangan pohon sebesar 16. Setiap simpul dalam jalur mencakup pointer hash yang cukup (ke simpul anak) dan nilai-nilai untuk memverifikasi integritas data dan untuk menavigasi melalui pohon.

Harap dicatat bahwa dalam MPT nyata, jalur-jalur dan data akan dienkripsi dan disimpan dalam format tertentu, dan jenis node tambahan (seperti node ekstensi dan node daun) membantu mengoptimalkan struktur untuk efisiensi dalam skenario yang berbeda.

4. Komitmen Vektor

Skema komitmen[1] adalah primitif kriptografi yang memastikan privasi dan integritas data. Mereka banyak digunakan dalam skenario seperti bukti tanpa pengetahuan dan komputasi multipihak yang aman. Skema komitmen dasar terbagi menjadi dua tahap: tahap komit dan tahap ungkap (atau buka).

1. Fase Commit: Pada fase ini, komiter menggunakan algoritma kriptografis untuk mengikat pesan ke nilai komitmen dan mengirim nilai komitmen ini ke penerima. Pada tahap ini, komitmen memiliki dua properti: menyembunyikan dan mengikat. Menyembunyikan memastikan bahwa konten pesan yang dikomitmen tidak diketahui oleh siapa pun kecuali komiter. Mengikat memastikan bahwa setelah komitmen dibuat, itu tidak dapat diubah oleh siapapun, termasuk komiter.
2. Fase Pengungkapan (Buka): Selama fase ini, pihak yang melakukan komitmen dapat membuktikan kepada penerima bahwa nilai komitmen yang mereka terima adalah komitmen valid terhadap pesan asli. Komitmen memiliki sifat kebenaran, yang berarti bahwa jika baik pihak yang melakukan komitmen maupun penerima mengikuti protokol dengan benar, penerima akan yakin bahwa nilai komitmen yang mereka terima selama fase komitmen adalah komitmen valid terhadap pesan asli.

Vector Commitment adalah jenis skema komitmen khusus yang diusulkan oleh Catalano et al. [2] yang memungkinkan pihak yang mengikat untuk membuat komitmen terhadap kumpulan pesan yang diurutkan 𝑚 = ⟨𝑚1 , 𝑚2 , …, 𝑚𝑞 ⟩ dan untuk mengungkapkan (membuka) pada posisi tertentu untuk membuktikan bahwa pesan 𝑚𝑖 adalah pesan yang dikirimkan ke-i. Dalam komitmen vektor, pengikatan berarti bahwa tidak ada orang yang dapat membuka posisi yang sama untuk mengungkapkan pesan yang berbeda.

Skema komitmen vektor biasanya terdiri dari algoritma-algoritma berikut:

5. Pohon Verkle

5.1. Definisi dan Karakteristik Pohon Verkle

Definisi: Pohon Verkle = Komitmen Vektor + Pohon Merkle.

Harap dicatat: Vitalik Buterin, salah satu pendiri Ethereum, memiliki blogkiriman yang secara khusus didedikasikan untuk memperkenalkan pohon Verkle. Bab ini menambahkan beberapa latar belakang dan pengetahuan matematika berdasarkan blognya. Sebagian data dan ilustrasi dalam teks berikut berasal dari blognya.

Pohon Verkle (VTs) ditandai dengan memberikan bukti yang lebih kecil dibandingkan dengan Pohon Merkle. Untuk data dalam skala miliaran entri, pohon Merkle mungkin menghasilkan bukti sekitar 1KB, sedangkan bukti pohon Verkle dapat kurang dari 150 byte. Ukuran bukti yang kompak ini menguntungkan untuk mengimplementasikanklien tanpa negara”.

Struktur pohon Verkle agak mirip dengan Pohon Merkle Patricia (MPT). Berikut contoh strukturnya. Node-node pohon Verkle bisa: (i) Kosong, (ii) Node daun yang berisi kunci dan nilainya, atau (iii) Node internal dengan jumlah node anak yang tetap. Jumlah anak ini juga disebut sebagai “lebar” dari pohon.

Perbedaan antara VT (Verkle Trees) dan MPT (Merkle Patricia Trees) terutama terletak pada bagaimana lebar pohon (atau fan-out, yang mengacu pada jumlah simpul anak yang dimiliki oleh sebuah simpul dalam pohon) memengaruhi efisiensinya. Dalam kasus MPT, jika lebarnya lebih besar, cenderung kurang efisien karena lebar yang lebih besar berarti lebih banyak simpul saudara, yang bisa menyebabkan waktu pembaruan yang lebih lama untuk MPT dan ukuran bukti yang lebih besar. Sebaliknya, untuk VT, lebar pohon yang lebih besar menghasilkan bukti yang lebih kecil. Satu-satunya pembatasannya adalah jika lebarnya terlalu tinggi, waktu yang dibutuhkan untuk menghasilkan bukti bisa menjadi lebih lama.

Pada Ethereum@vbuterin/verkle_tree_eip">susulan desain untuk VT, lebar 256 disarankan, yang jauh lebih besar dari 16 saat ini untuk MPT. Lebar yang begitu besar dapat diimplementasikan dalam VT karena penggunaan teknik kriptografi canggih, seperti komitmen vektor, yang memungkinkan bukti kompak terlepas dari lebar pohon. Teknik kompresi ini memungkinkan Pohon Verkle untuk meningkatkan efisiensi dalam hal ukuran bukti. Teks selanjutnya akan menjelaskan fitur yang disebutkan di atas dengan lebih detail.

5.2. Komitmen dan Bukti Pohon Verkle

Mari kita lihat bagaimana bukti-bukti dibuat dalam MPT: Bukti perlu mencakup nilai hash dari semua node samping (atau node saudara) di jalur dari node root ke node leaf target. Mengambil "4ce" sebagai contoh, bagian yang ditandai merah dalam diagram di bawah ini adalah node-node yang perlu disertakan dalam bukti yang dikembalikan.

Pada pohon Verkle, Anda tidak perlu menyediakan node saudara; sebaliknya, Anda hanya perlu menyediakan jalur bersama dengan beberapa data tambahan sebagai bukti.

Jadi bagaimana cara menghasilkan komitmen untuk sebuah VT? Fungsi hash yang digunakan untuk perhitungan bukanlah hash konvensional tetapi menggunakan komitmen vektor.

Setelah mengganti fungsi hash dengan algoritma generasi komitmen dari komitmen vektor, maka hash akar yang disebut sekarang menjadi komitmen akar. Jika data node mana pun dimanipulasi, itu pada akhirnya akan memengaruhi komitmen akar.

Bagaimana cara menghasilkan bukti? Seperti yang ditunjukkan dalam diagram di bawah ini, Anda hanya perlu menyediakan tiga sub-bukti, masing-masing dapat membuktikan bahwa sebuah node pada jalur tersebut ada pada posisi tertentu dalam node induknya. Semakin lebar lebarnya, semakin sedikit lapisan, dan akibatnya, semakin sedikit sub-bukti yang diperlukan.

Dalam implementasi praktis, komitmen polinomial digunakan (yang dapat diimplementasikan secara sederhana dan efisien untuk komitmen vektor), memungkinkan untuk komitmen terhadap polinomial. Skema komitmen polinomial yang paling ramah pengguna adalah “komitmen KZG” dan “komitmen polinomial gaya anti-peluru(yang pertama memiliki ukuran komitmen 48 byte, sementara yang terakhir adalah 32 byte).

Jika Anda menggunakan komitmen dan bukti KZG, bukti untuk setiap node perantara hanya sekitar 96 byte, yang mewakili penghematan ruang hampir tiga kali lipat dibandingkan dengan pohon Merkle dasar (dengan asumsi lebar 256).

Kompleksitas waktu teoritis untuk operasi pada pohon Merkle dan pohon Verkle adalah sebagai berikut:

Skema bukti Verkle yang diperkenalkan sejauh ini cukup dasar; bahkan, ada strategi optimisasi lanjutan yang lebih tersedia.

5.3. Optimisasi: Penggabungan Bukti

5.3.1. ide

Dibandingkan dengan menghasilkan bukti untuk setiap layer komitmen pada suatu path, karakteristik dari komitmen polinomial dapat dimanfaatkan untuk mencapai “membuktikan hubungan induk-anak antara semua komitmen pada path dengan bukti berukuran tetap, yang dapat mencakup jumlah elemen yang tidak terbatas.” Untuk memahami secara khusus bagaimana hal ini dicapai, perlu memperkenalkan beberapa pengetahuan matematika untuk penjelasan. Artikel ini akan melibatkan beberapa rumus matematika tetapi tidak akan menutupi bagian kriptografi dari bukti pada prinsipnya. Untuk metode spesifik, silakan merujuk ke skema yang menerapkan multiproofs melalui evaluasi acak.

5.3.2. Turunan matematika

Pertama, mari kita memperkenalkan beberapa konsep dasar tentang polinomial dalam matematika: bagaimana kita melakukan reduksi polinomial, juga dikenal sebagai reduksi derajat polinomial?

Dengan asumsi bahwa kita mengetahui sebuah polinomial 𝑃(𝑥) dan nilainya 𝑦₁ pada 𝑥₁, yaitu 𝑃(𝑥₁) = 𝑦₁ .

Sekarang, pertimbangkan polinomial baru 𝑃(𝑥) - 𝑦₁ , yang memiliki nilai nol pada (𝑥 = 𝑥₁) , karena 𝑃(𝑥₁) - 𝑦₁ =𝑦₁ - 𝑦₁ = 0.

Oleh karena itu, Polinomial 𝑃(𝑥) - 𝑦₁ memiliki akar di 𝑥 = 𝑥₁, yang berarti bahwa (𝑥 - 𝑥₁) adalah faktor dari 𝑃(𝑥) - 𝑦₁.

Dengan kata lain, kita dapat mengekspresikannya dalam bentuk berikut: [ 𝑃(𝑥) - 𝑦₁ = (𝑥 - 𝑥₁ )𝑄(𝑥)]

𝑄(𝑥) adalah polinomial lain yang derajatnya satu kurang dari 𝑃(𝑥). Hal ini karena (𝑥 -𝑥₁) adalah faktor berderajat pertama, yang mengurangi derajat total polinomial tersebut.

Bagaimana menggunakan KZG untuk membuktikan satu nilai dalam sebuah vektor?

Ambil komitmen KZG10 sebagai contoh, untuk polinomial 𝑃(𝑥), anggap komitmen polinomialnya adalah [ 𝑃(𝑠) ]₁.

Seperti yang telah dijelaskan sebelumnya, untuk polinomial 𝑃(𝑥), jika 𝑃(𝑧) = 𝑦, maka kita memiliki 𝑄(𝑥) = (𝑃(𝑥) - 𝑦)/(𝑥 - 𝑧)

Sekarang, pemberi bukti dapat menghasilkan bukti bahwa polinom 𝑃(𝑥) memenuhi 𝑃(𝑧) = 𝑦: hitung [ 𝑄(𝑠) ]₁ dan kirimkan ke verifikator.

Verifikator perlu memverifikasi 𝑒( [ 𝑄(𝑠) ]₁, [ 𝑠 - 𝑧]₂ ) = 𝑒( [ 𝑃(𝑠) ]₁- [𝑦]₁, [1]₂) .

Bagaimana menggunakan KZG untuk membuktikan nilai-nilai ganda dalam sebuah vektor?

Kita dapat membuat bukti untuk menunjukkan beberapa nilai dalam vektor sebagai berikut:

Dengan menggunakan metode ini, tidak peduli berapa banyak titik data dalam vektor yang sama yang perlu diverifikasi, hanya diperlukan bukti berukuran konstan.

Sekarang mari kita lihat skema Pohon Verkle tanpa optimisasi dari sudut pandang algoritma komitmen KZG.

Dengan menggunakan metode konstruksi dari bagian 'Bagaimana menggunakan KZG untuk membuktikan satu nilai dalam vektor,' pemeriksa dapat membuat komitmen untuk polinomial asli dan bagi setiap polinomial 𝑓ᵢ(𝑥) , menghasilkan total 𝟐﹡𝑚 komitmen KZG. Pemeriksa mengirim semua komitmen ini sebagai bukti untuk verifikasi.

Namun, seperti yang disebutkan sebelumnya, pendekatan ini memerlukan pembangkitan bukti yang banyak, dan pemeriksa juga perlu melakukan beberapa komputasi verifikasi. Kita perlu menemukan cara untuk mengompres bukti komitmen ganda.

Menggabungkan Bukti

Pemberi bukti mengirimkan bukti [ 𝑞( 𝑠 )]₁ ke pemeriksa untuk verifikasi.

Bukti yang dihasilkan oleh skema ini terdiri dari satu komitmen, dua bukti, dan satu nilai, dengan ukuran data yang konstan. Akhirnya, setelah optimisasi penggabungan bukti pada pohon Verkle, objek data yang dapat diverifikasi yang dikirimkan ke pemeriksa mencakup hal berikut:

1. Bukti ukuran konstan
2. Data daun yang akan dibuktikan (pasangan kunci-nilai)
3. Nilai komitmen dari semua node di jalur dari daun ke akar (dengan asumsi lebar pohon 256 dengan 2³² node, maka rata-rata kedalamannya adalah 4, hanya memerlukan 3 nilai komitmen)

Perhatikan bahwa 𝑥ᵢ dan 𝑦ᵢ tidak perlu secara eksplisit disediakan; semuanya dapat dihitung.

5.3.3. performa

Mengenai skema penggabungan bukti untuk pohon Verkle, ukuran spesifik dari bukti yang dihasilkan adalah sebagai berikut（Satuan baris adalah miliar.）:

Data di atas mengasumsikan penggunaan pohon lebar 256, menggunakan skema komitmen KZG (dengan ukuran komitmen 48 byte), dan memaksimalkan pemanfaatan pohon. Dalam praktiknya, untuk distribusi informasi yang benar-benar acak, kedalaman pohon akan meningkat sekitar 60%, dan ukuran setiap elemen akan bertambah sebesar 30 byte. Jika skema bulletproof digunakan, maka ukuran komitmen akan menjadi 32 byte.

5.4. Beban komputasi prover dan verifikasi

1. Generasi Bukti: Biaya menghasilkan bukti oleh pemberi bukti terkait dengan lebar pohon, tetapi setiap operasi atom memerlukan biaya komputasi yang relatif rendah, sehingga pohon Verkle dengan lebar antara 256 dan 1024 berperforma baik dalam hal algoritma.
2. Verifikasi Bukti: Vitalik telah menunjukkan bahwa algoritma verifikasi sangat cepat dan biasanya dapat diselesaikan dalam waktu kurang dari 100ms, bahkan ketika ada beberapa ribu nilai yang harus diverifikasi.
3. Saat Memperbarui Pohon Verkle: Memperbarui pohon memerlukan perhitungan ulang semua nilai komitmen intermediate sepanjang jalur karena perubahan nilai atau struktur. Namun, Vitalik menyebutkan bahwa, berkat beberapa sifat algoritma komitmen polinomial, memungkinkan untuk merancang metode yang memprediksi nilai komitmen alternatif dan menyimpannya, sehingga mengurangi biaya waktu komputasi selama pembaruan, yang pada dasarnya menukar ruang dengan waktu.

6. Kesimpulan

Berikut adalah kata-kata asli dari blog vitalik, kami menambahkan satu paragraf di akhir sebagai tambahan.

Pohon Verkle merupakan upgrade yang kuat untuk bukti Merkle yang memungkinkan ukuran bukti yang jauh lebih kecil. Alih-alih perlu menyediakan semua “simpul saudara” di setiap level, pembuktian hanya perlu menyediakan satu bukti tunggal yang membuktikan semua hubungan induk-anak antara semua komitmen sepanjang jalur dari setiap simpul daun ke akar. Ini memungkinkan ukuran bukti untuk berkurang sebesar ~6–8 dibandingkan dengan pohon Merkle ideal, dan sebesar lebih dari 20–30 dibandingkan dengan pohon Patricia hexary yang digunakan Ethereum saat ini (!!).

Mereka memerlukan kriptografi yang lebih kompleks untuk diimplementasikan, namun mereka memberikan kesempatan untuk keuntungan besar dalam hal skalabilitas. Pada jangka menengah, SNARK dapat meningkatkan hal-hal lebih lanjut: kita dapat menggunakan SNARK verifier bukti Verkle yang sudah efisien untuk mengurangi ukuran saksi hampir menjadi nol, atau beralih kembali ke bukti Merkle yang sudah di-SNARK jika/kapan SNARK menjadi jauh lebih baik (misalnya melalui GKR, atau fungsi hash yang sangat ramah terhadap SNARK, atau ASICs). Lebih jauh ke depan, munculnya komputasi kuantum akan memaksa perubahan ke bukti Merkle yang di-STARK dengan hash karena membuat homomorfisme linear yang bergantung pada pohon Verkle menjadi tidak aman. Namun untuk saat ini, mereka memberikan kita keuntungan skalabilitas yang sama dengan teknologi yang lebih canggih tersebut, dan kita sudah memiliki semua alat yang diperlukan untuk mengimplementasikannya dengan efisien.

Saat ini, banyak klien Ethereum telah menyediakan implementasi pohon Verkle dan jaringan uji terkait. Komunitas masih membahas waktu peluncuran Pohon Verkle di jaringan utama. Kemungkinan akan diimplementasikan dalam upgrade hard fork pada tahun 2024 atau 2025. Untuk informasi terperinci tentang pohon Verkle di Ethereum, lihat https://verkle.info/ .

7. Referensi

[1]. BRASSARD G, CHAUM D, CRÉPEAU C. Bukti minimum pengetahuan pengungkapan[J]. Jurnal ilmu komputer dan sistem, 1988, 37(2): 156–189.

[2]. CATALANO D, FIORE D. Komitmen vektor dan aplikasi-aplikasinya[C]//Public-KeyCryptography–PKC 2013: Konferensi Internasional ke-16 tentang Praktik dan Teori dalam Kriptografi Kunci Publik, Nara, Jepang, 26 Februari–1 Maret 2013. Prosiding 16. Springer, 2013: 55–72.

Disclaimer：

1. Artikel ini dipublikasi ulang dari [ZAN], Semua hak cipta milik penulis asli [AntChain Open Labs dan ZAN]. Jika ada keberatan terhadap cetakan ulang ini, silakan hubungi Gate Pelajaritim, dan mereka akan menanganinya dengan cepat.
2. Penyangkalan Tanggung Jawab: Pandangan dan opini yang diungkapkan dalam artikel ini semata-mata milik penulis dan tidak merupakan saran investasi apa pun.
3. Terjemahan artikel ke dalam bahasa lain dilakukan oleh tim Gate Learn. Kecuali disebutkan, menyalin, mendistribusikan, atau menjiplak artikel yang diterjemahkan dilarang.