Analisis Prinsip STARKs Binius dan Pemikiran Optimisasi

1 Pendahuluan

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

Generasi pertama lebar kode STARKs adalah 252bit, generasi kedua adalah 64bit, dan generasi ketiga adalah 32bit, tetapi lebar kode 32bit masih memiliki banyak ruang yang terbuang. Domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang padat dan efisien tanpa ruang yang terbuang secara sembarangan, yang mungkin menjadi generasi keempat STARKs.

Domain biner telah banyak digunakan dalam kriptografi, seperti AES, GMAC, kode QR, FRI asli, dan protokol zk-STARK.

Saat Binius menggunakan bidang biner, ia harus sepenuhnya bergantung pada perluasan bidang untuk menjamin keamanan dan kegunaan praktis. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu memasuki perluasan bidang, dan hanya perlu beroperasi dalam bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil.

Binius mengusulkan solusi inovatif:

1. menggunakan polinomial multivariat sebagai pengganti polinomial univariat, dengan nilai-nilainya pada "hiperkubus" untuk merepresentasikan seluruh jejak perhitungan.
2. Menganggap hypercube sebagai persegi untuk perluasan Reed-Solomon

2 Analisis Prinsip

Binius = HyperPlonk PIOP + Brakedown PCS + bidang biner

Termasuk lima teknologi kunci:

1. aritmetika berbasis domain biner bertumpuk
2. Mengubah HyperPlonk produk dan pemeriksaan permutasi
3. bukti pergeseran multilinier baru
4. Versi Perbaikan Teori Pencarian Lasso
5. skema komitmen polinomial bidang kecil

2.1 Ruang Terbatas: Aritmetika berbasis tower bidang biner

Domain biner bertingkat mendukung operasi aritmatika yang sangat efisien dan proses aritmatika yang disederhanakan.

String 128-bit dapat dianggap sebagai elemen dalam bidang biner 128-bit, atau dapat diuraikan menjadi dua elemen bidang tower 64-bit, empat elemen bidang tower 32-bit, enam belas elemen bidang tower 8-bit, atau seratus dua puluh delapan elemen bidang F2. Fleksibilitas representasi ini tidak memerlukan biaya perhitungan tambahan.

2.2 PIOP: Versi Adaptasi Produk HyperPlonk dan PermutationCheck

Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti:

• GateCheck
• PermutationCheck
• LookupCheck
• MultisetCheck
• ProductCheck
• ZeroCheck
• SumCheck
• BatchCheck

Binius telah melakukan perbaikan dalam 3 aspek berikut:

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

2.3 PIOP: argumen pergeseran multiliner baru

Metode kunci untuk konstruksi dan pengolahan polinomial virtual dalam protokol Binius:

• Packing
• Operator Pergeseran

2.4 PIOP: argumen pencarian Lasso versi adaptasi

Protokol Lasso terdiri dari tiga komponen:

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

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

2.5 PCS：versi adaptasi Brakedown PCS

Makalah Binius menyediakan 2 skema komitmen polinomial Brakedown berbasis domain biner:

1. menggunakan kode terhubung untuk menginstansikan
2. menggunakan teknologi pengkodean tingkat blok, mendukung penggunaan kode Reed-Solomon secara terpisah

Komitmen polinomial kecil dan evaluasi bidang yang diperluas, konstruksi umum bidang kecil, serta teknik pengkodean blok dengan kode Reed-Solomon digunakan untuk membangun komitmen polinomial Binius.

3 Pemikiran yang Dioptimalkan

Empat poin optimasi kunci:

1. PIOP berbasis GKR: untuk operasi perkalian domain biner, menggunakan protokol GKR untuk menggantikan algoritma Lasso Lookup

2. Optimasi ZeroCheck PIOP: Menyeimbangkan biaya komputasi antara Prover dan Verifier

3. Optimasi PIOP Sumcheck: Optimasi untuk Sumcheck pada domain kecil

4. Optimasi PCS: Mengurangi ukuran bukti melalui optimasi FRI-Binius

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" berhasil mengurangi biaya komitmen secara signifikan dengan bantuan protokol GKR.

3.2 ZeroCheck PIOP optimalisasi: Perimbangan biaya komputasi Prover dan Verifier

Arah optimasi utama:

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

3.3 Optimasi PIOP Sumcheck: Protokol Sumcheck berbasis domain kecil

Poin optimasi utama:

• Pengaruh dan faktor perbaikan dari pergantian putaran
• Pengaruh ukuran domain pada 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 domain biner, membawa 4 inovasi dalam aspek:

• Polinomial datar
• Polinomial Hilang Subruang
• Pembungkusan basis aljabar
• Pertukaran lingkaran SumCheck

4 Ringkasan

Proposisi nilai Binius adalah memungkinkan saksi untuk menggunakan domain power-of-two yang paling minimum. Dalam Binius, hambatan komitmen Prover telah hampir sepenuhnya dihapus, dan hambatan baru terletak pada protokol Sumcheck.

Skema FRI-Binius adalah varian dari FRI, yang dapat menghilangkan overhead embedding dari lapisan bukti domain tanpa menyebabkan lonjakan biaya pada lapisan bukti agregat.

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.