Analisis dan Optimasi Binius STARKs

1. Pendahuluan

Salah satu alasan utama rendahnya efisiensi STARKs adalah bahwa sebagian besar nilai dalam program yang sebenarnya cukup kecil, tetapi untuk memastikan keamanan bukti berbasis pohon Merkle, saat menggunakan kode 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. Domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang terbuang, yang mungkin merupakan generasi keempat STARKs.

Binius menggunakan teknologi seperti aritmetisasi berbasis domain biner bertower, versi HyperPlonk yang ditingkatkan untuk pemeriksaan produk dan permutasi, serta komitmen polinomial subdomain untuk meningkatkan efisiensi dari berbagai sudut.

2. Analisis Prinsip

Binius terdiri dari lima teknologi kunci:

1. Arithmetisasi berdasarkan domain biner bertingkat
2. Versi adaptasi HyperPlonk pemeriksaan produk dan permutasi
3. Bukti Perpindahan Multilinear Baru
4. Versi Perbaikan Lasso Temukan Bukti
5. Skema Komitmen Polinomial Kecil

2.1 Arithmetisasi Berdasarkan Domain Biner Bertingkat

Bidang biner bertingkat mendukung operasi aritmetika yang efisien dan proses aritmetika yang disederhanakan. Elemen bidang biner dapat langsung dipetakan ke string k-bit, dengan kemudahan pemetaan satu-ke-satu.

2.2 Versi Adaptasi Pemeriksaan Jumlah dan Permutasi HyperPlonk

Binius mengadopsi mekanisme pemeriksaan inti HyperPlonk, termasuk GateCheck, PermutationCheck, LookupCheck, dan melakukan perbaikan dalam aspek-aspek berikut:

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

2.3 Bukti Perpindahan Multilinear Baru

Binius memperkenalkan dua metode kunci, Packing dan operator pergeseran, untuk membangun dan memproses polinomial virtual.

2.4 Versi Modifikasi Teori Pencarian Lasso

Binius menyesuaikan Lasso untuk operasi di domain biner, memperkenalkan versi perkalian dari protokol Lasso.

2.5 Komitmen Polin Kecil

Binius menyediakan dua jenis skema komitmen polinomial Brakedown berbasis bidang biner, yang terutama menggunakan komitmen polinomial bidang kecil dan evaluasi bidang yang diperluas, konstruksi umum bidang kecil, serta pengkodean tingkat blok dan teknik kode Reed-Solomon.

3. Optimasi Pemikiran

3.1 PIOP berbasis GKR

Algoritma operasi perkalian dalam domain biner berbasis GKR, dengan mengubah "memeriksa apakah 2 bilangan bulat 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 dioptimalkan

Dengan menyesuaikan pembagian beban kerja antara pihak pembuktian dan pihak verifikasi, berbagai solusi optimasi diajukan:

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

3.3 Sumcheck PIOP optimasi

Ingonyama mengusulkan perbaikan untuk protokol Sumcheck berbasis domain kecil, berfokus pada pemilihan putaran t.

3.4 PCS optimalisasi:FRI-Binius

FRI-Binius menerapkan mekanisme lipatan FRI dalam domain biner, membawa 4 inovasi dalam berbagai aspek:

• Polinomial datar
• Polinomial hilangnya subruang
• Pembungkusan basis aljabar
• Pertukaran SumCheck

4. Kesimpulan

Binius adalah "solusi desain kolaboratif yang menggunakan perangkat keras, perangkat lunak, dan protokol Sumcheck yang dipercepat dalam FPGA", yang dapat membuktikan dengan sangat cepat dengan penggunaan memori yang sangat rendah. Dalam Binius, hambatan komitmen Prover telah hampir sepenuhnya dihapus, dan hambatan baru terletak pada protokol Sumcheck, yang dapat diatasi secara efisien dengan perangkat keras khusus.

FRI-Binius adalah varian dari FRI yang dapat menghilangkan overhead embedding dari lapisan bukti domain tanpa menyebabkan lonjakan biaya lapisan bukti agregat. Saat ini, beberapa tim sedang mengembangkan teknologi terkait Binius, termasuk lapisan rekursif, zkVM, dan lainnya.