Analisis Prinsip dan Pemikiran Optimasi STARKs Binius

1. Pendahuluan

Salah satu alasan utama efisiensi STARKs yang rendah adalah bahwa sebagian besar nilai dalam program nyata relatif kecil, tetapi untuk memastikan keamanan bukti berbasis pohon Merkle, saat menggunakan pengkodean Reed-Solomon untuk memperluas data, banyak nilai redundan tambahan akan mengisi seluruh domain. Mengurangi ukuran domain menjadi strategi kunci.

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

Binius menggunakan domain biner, yang sepenuhnya bergantung pada perluasan domain untuk memastikan keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam perluasan domain, dan hanya perlu beroperasi di bawah domain dasar, sehingga mencapai efisiensi tinggi dalam domain kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu mendalami ke dalam perluasan domain yang lebih besar untuk memastikan keamanan yang diperlukan.

Binius mengusulkan solusi inovatif: pertama, menggunakan polinomial multivariat (khususnya polinomial multilinier) sebagai pengganti polinomial univariat, dengan menggunakan nilai-nilainya pada "hypercube" untuk merepresentasikan seluruh lintasan perhitungan; kedua, menganggap hypercube sebagai persegi, dan melakukan perluasan Reed-Solomon berdasarkan persegi tersebut. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja perhitungan.

2. Analisis Prinsip

Binius mencakup lima teknologi kunci:

1. Aritmetika berbasis domain biner tumpukan
2. Versi Adaptasi HyperPlonk Produk dan Pemeriksaan Permutasi
3. Bukti Perpindahan Multilinear Baru
4. Versi Perbaikan Bukti Pencarian Lasso
5. Skema Komitmen Polinomi Kecil

2.1 Ruang Terbatas: Aritmetisasi berdasarkan towers of binary fields

Domain biner bertipe tower mendukung operasi aritmatika yang sangat efisien, mendukung proses aritmatika yang disederhanakan. Elemen dari domain biner memiliki cara representasi yang unik dan langsung, dan dapat dengan fleksibel mengonversi dan mengemas antara domain dengan ukuran yang berbeda.

2.2 PIOP: Versi Adaptasi Produk HyperPlonk dan PermutationCheck

Binius menggunakan serangkaian mekanisme pemeriksaan inti, termasuk GateCheck, PermutationCheck, LookupCheck, MultisetCheck, ProductCheck, ZeroCheck, SumCheck, dan BatchCheck.

Dibandingkan dengan HyperPlonk, Binius telah melakukan perbaikan di bidang berikut:

• Optimasi ProductCheck
• Penanganan masalah pembagian dengan nol
• Cek Permutasi Lintas Kolom

2.3 PIOP: argumen pergeseran multilinear baru

Binius menggunakan dua metode kunci Packing dan operator pergeseran untuk menangani polinomial virtual.

2.4 PIOP: versi adaptasi argumen pencarian Lasso

Protokol Lasso terdiri dari tiga komponen:

• Abstraksi polinomial virtual dari tabel besar
• Pencarian tabel kecil
• Pemeriksaan banyak kumpulan

Binius memperkenalkan versi perkalian dari protokol Lasso, yang mengharuskan pihak yang membuktikan dan pihak yang memverifikasi untuk bersama-sama meningkatkan operasi "penghitungan memori" dari protokol, bukan dengan penambahan sederhana 1, tetapi dengan peningkatan menggunakan elemen generator perkalian dalam bidang biner.

2.5 PCS: versi modifikasi Brakedown PCS

Komitmen polinomial Binius terutama menggunakan:

• Komitmen polinomial kecil dan evaluasi domain yang diperluas
• Konstruksi Umum Kecil
• Kode blok dan teknologi kode Reed-Solomon

3. Optimalisasi Pemikiran

3.1 PIOP berbasis GKR: Perkalian domain biner berbasis GKR

Algoritma operasi perkalian integer berbasis GKR, dengan mengubah "memeriksa apakah 2 integer 32-bit A dan B memenuhi A·B =? C", menjadi "memeriksa apakah (gA)B =? gC berlaku", secara signifikan mengurangi biaya komitmen dengan bantuan protokol GKR.

3.2 ZeroCheck PIOP optimalisasi: Perimbangan biaya perhitungan Prover dan Verifier

• Mengurangi transmisi data dari pihak yang membuktikan
• Mengurangi jumlah titik evaluasi pihak yang membuktikan
• Optimasi Interpolasi Aljabar

3.3 Optimisasi PIOP Sumcheck: Protokol Sumcheck berbasis domain kecil

• Pengaruh dan faktor perbaikan dari pergantian putaran
• Pengaruh ukuran basis terhadap kinerja
• Keuntungan optimasi algoritma Karatsuba
• Peningkatan efisiensi memori

3.4 PCS Optimasi: FRI-Binius mengurangi ukuran bukti Binius

FRI-Binius telah mengimplementasikan mekanisme lipatan FRI di bidang biner, membawa 4 inovasi:

• Polinomial datar
• Polinomial hilangnya subruang
• Paket Basis Aljabar
• Pertukaran lingkaran SumCheck

4. Kesimpulan

Binius secara dasar telah sepenuhnya menghapus hambatan komitmen Prover, hambatan baru terletak pada protokol Sumcheck. Skema FRI-Binius adalah varian FRI yang dapat menghilangkan biaya penyisipan dari lapisan bukti domain. Saat ini, tim Irreducible sedang mengembangkan lapisan rekursifnya dan bekerja sama dengan tim Polygon untuk membangun zkVM berbasis Binius; JoltzkVM sedang beralih dari Lasso ke Binius; tim Ingonyama sedang mengimplementasikan versi FPGA dari Binius.