Analisis Prinsip STARKs Binius dan Pemikiran Optimisasi

1 Pendahuluan

Salah satu alasan utama rendahnya efisiensi STARKs adalah: sebagian besar nilai dalam program aktual relatif kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dan sebagainya. Namun, untuk memastikan keamanan bukti yang berbasis pada pohon Merkle, saat menggunakan pengkodean Reed-Solomon untuk memperluas data, banyak nilai redundan tambahan akan mengisi seluruh domain, meskipun nilai asli itu sendiri sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.

Lebar kode STARKs generasi pertama adalah 252bit, lebar kode STARKs generasi kedua adalah 64bit, dan lebar kode STARKs generasi ketiga adalah 32bit, tetapi lebar kode 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, bidang biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang terbuang, yaitu STARKs generasi keempat.

Dibandingkan dengan Goldilocks, BabyBear, dan Mersenne31 yang merupakan penemuan terbaru dalam beberapa tahun ini, penelitian tentang bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah banyak digunakan dalam kriptografi, contoh tipikal termasuk:

• Standar Enkripsi Tingkat Lanjut (AES), berbasis pada domain F28;

• Kode Otentikasi Pesan Galois ( GMAC ), berdasarkan bidang F2128;

• QR Code, menggunakan pengkodean Reed-Solomon berbasis F28;

• Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk ke final SHA-3, yang didasarkan pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursi.

Ketika menggunakan bidang yang lebih kecil, operasi perluasan bidang menjadi semakin penting untuk memastikan keamanan. Bidang biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan bidang untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu memasuki perluasan bidang, tetapi hanya perlu beroperasi di bawah bidang dasar, sehingga mencapai efisiensi tinggi di bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu mendalami perluasan bidang yang lebih besar untuk memastikan keamanan yang diperlukan.

Ketika membangun sistem bukti berdasarkan domain biner, terdapat 2 masalah praktis: saat menghitung representasi trace dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; saat melakukan komitmen Merkle tree dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, dan ukuran domain yang digunakan harus lebih besar dari ukuran setelah perluasan pengkodean.

Binius telah mengajukan solusi inovatif yang menangani kedua masalah ini secara terpisah dan mewakili data yang sama dengan dua cara berbeda: pertama, menggunakan polinomial multivariat (khususnya polinomial multilinear) sebagai pengganti polinomial univariat, dengan mewakili seluruh jejak perhitungan melalui nilai-nilainya pada "hypercube"; kedua, karena setiap dimensi hypercube memiliki panjang 2, maka tidak dapat melakukan ekstensi Reed-Solomon standar seperti STARKs, tetapi hypercube dapat dianggap sebagai persegi, dan ekstensi Reed-Solomon dapat dilakukan berdasarkan persegi tersebut. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja perhitungan.

2 Analisis Prinsip

Konstruk sebagian besar sistem SNARKs saat ini biasanya terdiri dari dua bagian berikut:

• Bukti Oracle Interaktif Polinomial Teoritis Informasi (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti dari sistem bukti, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan pembuktian untuk secara bertahap mengirim polinomial melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah perhitungan benar hanya dengan mengajukan sedikit hasil evaluasi polinomial. Protokol PIOP yang ada termasuk: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara yang berbeda dalam menangani ekspresi polinomial, sehingga mempengaruhi kinerja dan efisiensi seluruh sistem SNARK.

• Skema Komitmen Polinomial (Polynomial Commitment Scheme, PCS): Skema komitmen polinomial digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP berlaku. PCS adalah alat kriptografi yang memungkinkan penjamin untuk mengkomit pada suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut di kemudian hari, sambil menyembunyikan informasi lain tentang polinomial tersebut. Skema komitmen polinomial yang umum digunakan antara lain KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP), dan Brakedown. Setiap PCS memiliki kinerja, keamanan, dan skenario aplikasi yang berbeda.

Berdasarkan kebutuhan spesifik, pilih PIOP dan PCS yang berbeda, dan kombinasikan dengan bidang terbatas atau kurva elips yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Contohnya:

• Halo2: Dihasilkan dari penggabungan PLONK PIOP dan Bulletproofs PCS, serta didasarkan pada kurva Pasta. Halo2 dirancang dengan fokus pada skalabilitas dan menghilangkan trusted setup dalam protokol ZCash.

• Plonky2: Menggunakan PLONK PIOP dan FRI PCS yang dikombinasikan, dan berbasis pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem-sistem ini, PIOP dan PCS yang dipilih harus cocok dengan bidang hingga atau kurva elips yang digunakan, untuk memastikan kebenaran, kinerja, dan keamanan sistem. Pilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti SNARK dan efisiensi verifikasi, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa pengaturan yang dapat dipercaya, serta apakah dapat mendukung fungsi ekspansi seperti bukti rekursif atau bukti agregasi.

Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, aritmatika berbasis menara bidang biner (towers of binary fields) membentuk dasar perhitungannya, yang mampu melakukan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol bukti Oracle interaktifnya (PIOP) mengadaptasi pemeriksaan produk dan penggantian HyperPlonk, memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan penggantian mereka. Ketiga, protokol memperkenalkan pembuktian pergeseran multilinear baru, yang mengoptimalkan efisiensi verifikasi hubungan multilinear di bidang kecil. Keempat, Binius menggunakan pembuktian pencarian Lasso yang ditingkatkan, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), yang memungkinkannya untuk mencapai sistem bukti yang efisien di bidang biner dan mengurangi biaya yang biasanya terkait dengan bidang besar.

2.1 Ruang Terbatas: Arithmetisasi berdasarkan menara bidang biner

Bidang biner bertingkat adalah kunci untuk mewujudkan komputasi yang cepat dan dapat diverifikasi, terutama disebabkan oleh dua faktor: perhitungan yang efisien dan aritmetika yang efisien. Bidang biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur bidang biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan di atas bidang biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan secara penuh karakteristik hierarkisnya melalui struktur bertingkat, menjadikan bidang biner sangat cocok untuk sistem pembuktian yang dapat diperluas seperti Binius.

Di mana "canonical" merujuk pada cara representasi yang unik dan langsung dari elemen di bidang biner. Misalnya, dalam bidang biner dasar F2, string berukuran k-bit dapat langsung dipetakan ke elemen bidang biner berukuran k-bit. Ini berbeda dengan bidang prima, yang tidak dapat memberikan representasi yang sesuai dalam jumlah bit yang ditentukan. Meskipun bidang prima berukuran 32-bit dapat dimasukkan dalam 32-bit, tidak semua string berukuran 32-bit dapat secara unik berhubungan dengan elemen bidang, sedangkan bidang biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam bidang prima Fp, metode reduksi yang umum termasuk reduksi Barrett, reduksi Montgomery, serta metode reduksi khusus untuk bidang terbatas tertentu seperti Mersenne-31 atau Goldilocks-64. Dalam bidang biner F2k, metode reduksi yang umum digunakan termasuk reduksi khusus (seperti yang digunakan dalam AES), reduksi Montgomery (seperti yang digunakan dalam POLYVAL), dan reduksi rekursif (seperti Tower). Makalah "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" menunjukkan bahwa bidang biner tidak perlu memperkenalkan carry dalam operasi penjumlahan dan perkalian, dan operasi kuadrat di bidang biner sangat efisien karena mengikuti aturan penyederhanaan (X + Y )2 = X2 + Y 2.

Seperti yang ditunjukkan pada Gambar 1, sebuah string 128-bit: string ini dapat diinterpretasikan dalam berbagai cara dalam konteks domain biner. Itu dapat dianggap sebagai elemen unik dalam domain biner 128-bit, atau diuraikan sebagai dua elemen domain tower 64-bit, empat elemen domain tower 32-bit, 16 elemen domain tower 8-bit, atau 128 elemen domain F2. Fleksibilitas representasi ini tidak memerlukan beban komputasi tambahan, hanya sekadar konversi tipe string bit, yang merupakan atribut yang sangat menarik dan berguna. Selain itu, elemen domain kecil dapat dikemas menjadi elemen domain yang lebih besar tanpa memerlukan beban komputasi tambahan. Protokol Binius memanfaatkan fitur ini untuk meningkatkan efisiensi komputasi. Selain itu, makalah "On Efficient Inversion in Tower Fields of Characteristic Two" membahas kompleksitas komputasi dari operasi perkalian, kuadrat, dan invers dalam domain biner tower n-bit (yang dapat dipecah menjadi subdomain m-bit).

2.2 PIOP: Versi Adaptasi Produk HyperPlonk dan PermutationCheck------Cocok untuk domain biner

Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, dan menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan himpunan multivariat. Mekanisme pemeriksaan inti ini meliputi:

1. GateCheck: Memverifikasi saksi rahasia ω dan input publik x apakah memenuhi hubungan perhitungan sirkuit C(x,ω)=0, untuk memastikan sirkuit berfungsi dengan benar.

2. PermutationCheck: Memverifikasi apakah hasil evaluasi dua polinomial multivariat f dan g di hiperkubus Boolean adalah hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi permutasi antara variabel polinomial.

3. LookupCheck: Memverifikasi apakah evaluasi polinomial berada dalam tabel pencarian yang diberikan, yaitu f(Bµ) ⊆ T(Bµ), memastikan bahwa beberapa nilai berada dalam rentang yang ditentukan.

4. MultisetCheck: Memeriksa apakah dua himpunan multivariat sama, yaitu {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, untuk menjamin konsistensi antar beberapa himpunan.

5. ProductCheck: Memeriksa apakah evaluasi polinomial rasional di hiper kubus Boolean sama dengan nilai yang dinyatakan ∏x∈Hµ f(x) = s, untuk memastikan keakuratan produk polinomial.

6. ZeroCheck: Memverifikasi apakah suatu polinomial multivariat pada hiperkubus Boolean pada titik mana pun adalah nol ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, untuk memastikan distribusi titik nol dari polinomial.

7. SumCheck: Memeriksa apakah jumlah nilai polinomial multivariat sama dengan nilai yang dinyatakan ∑x∈Hµ f(x) = s. Dengan mengubah masalah evaluasi polinomial multivariat menjadi evaluasi polinomial variabel tunggal, mengurangi kompleksitas perhitungan pihak yang memverifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch dengan memperkenalkan angka acak, membangun kombinasi linier untuk mewujudkan pemrosesan batch dari beberapa contoh verifikasi jumlah.

8. BatchCheck: Berdasarkan SumCheck, memverifikasi kebenaran evaluasi beberapa polinomial multivariat untuk meningkatkan efisiensi protokol.

Meskipun Binius dan HyperPlonk memiliki banyak kesamaan dalam desain protokol, Binius telah melakukan perbaikan dalam 3 aspek berikut:

• Optimasi ProductCheck: Dalam HyperPlonk, ProductCheck mengharuskan penyebut U tidak nol di seluruh hiperkubus, dan hasil kali harus sama dengan nilai tertentu; Binius menyederhanakan proses pemeriksaan ini dengan mengkhususkan nilai tersebut menjadi 1, sehingga mengurangi kompleksitas perhitungan.

• Penanganan masalah pembagian dengan nol: HyperPlonk gagal menangani kasus pembagian dengan nol dengan baik, yang menyebabkan ketidakmampuan untuk menyatakan masalah non-nol U di hiperkubus; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebut adalah nol, ProductCheck Binius tetap dapat melanjutkan pemrosesan, memungkinkan perluasan ke nilai produk yang sembarang.

• Pemeriksaan Permutasi Lintas Kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung pemeriksaan permutasi di antara beberapa kolom, yang memungkinkan Binius untuk menangani situasi pengaturan polinomial yang lebih kompleks.

Oleh karena itu, Binius meningkatkan fleksibilitas dan efisiensi protokol melalui perbaikan pada mekanisme PIOPSumCheck yang ada, terutama dalam menangani verifikasi polinomial multivariat yang lebih kompleks, memberikan dukungan fungsional yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem pembuktian yang berbasis pada domain biner di masa depan.

2.3 PIOP: argumen pergeseran multiliniar baru------cocok untuk hypercube boolean

Dalam protokol Binius, konstruksi dan pemrosesan polinom virtual adalah salah satu teknologi kunci, yang dapat secara efektif menghasilkan dan mengoperasikan polinom yang berasal dari pegangan input atau polinom virtual lainnya. Berikut adalah dua metode kunci:

• Packing：Metode ini mengoptimalkan operasi dengan mengemas elemen yang lebih kecil yang berdekatan dalam urutan kamus menjadi elemen yang lebih besar. Operator Pack menargetkan operasi blok berukuran 2κ dan mengemasnya.