Analisis Prinsip STARKs Binius dan Pemikiran Optimisasi

1. Pendahuluan

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

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

Domain biner banyak digunakan dalam kriptografi, seperti AES(F28), GMAC(F2128), QR code(F28), dll. Ketika menggunakan domain yang lebih kecil, operasi perluasan semakin penting untuk memastikan keamanan. Domain biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan untuk menjamin keamanan dan ketersediaan. Sebagian besar perhitungan Prover dilakukan di bawah bidang dasar, efisien; pemeriksaan titik acak dan perhitungan FRI memerlukan pemahaman yang lebih mendalam tentang perluasan yang lebih besar untuk memastikan keamanan.

Solusi inovatif Binius:

1. menggunakan multivariat ( polinomial linier ) untuk menggantikan polinomial univariat, melalui representasi nilai "hiper kubus" untuk menghitung lintasan.
2. menganggap hypercube sebagai persegi, berdasarkan persegi untuk memperluas Reed-Solomon

2. Analisis Prinsip

Binius = HyperPlonk PIOP + Brakedown PCS + binary field

Lima teknologi kunci:

1. aritmetika berbasis domain biner bertingkat
2. Mengadaptasi pemeriksaan produk dan permutasi HyperPlonk
3. bukti pergeseran multilinear baru
4. versi perbaikan Lasso pencarian bukti
5. Skema Komitmen Polinomial Kecil

2.1 Ruang Terbatas: Aritmetika berbasis towers of binary fields

Keuntungan domain biner bertingkat:

• Perhitungan efisien: domain biner mendukung operasi aritmatika yang efisien
• Aritmatika Efisien: Struktur bidang biner mendukung proses aritmatika yang disederhanakan
• Memanfaatkan sepenuhnya karakteristik hierarkis melalui struktur menara

String 128-bit dapat diinterpretasikan dengan fleksibel:

• Sebuah elemen unik dalam domain 128 bit
• Dua elemen tower domain 64-bit
• Empat elemen domain tower 32-bit
• 16 elemen domain 8-bit
• 128 elemen domain F2

2.2 PIOP: Versi Adaptasi Produk HyperPlonk dan PermutationCheck

Mekanisme pemeriksaan inti Binius:

1. GateCheck
2. PermutationCheck
3. LookupCheck
4. MultisetCheck
5. ProductCheck
6. ZeroCheck
7. SumCheck
8. BatchCheck

Binius untuk perbaikan HyperPlonk:

• Optimasi ProductCheck
• Menangani masalah pembagian dengan nol dengan benar
• Mendukung PermutationCheck lintas kolom

2.3 PIOP: argumen shift multilinear baru

Metode Kunci:

• Packing: Mengemas elemen yang lebih kecil yang berdekatan menjadi elemen yang lebih besar
• Operator pergeseran: mengatur ulang elemen dalam blok

2.4 PIOP: versi modifikasi argumen pencarian Lasso

Keunggulan protokol Lasso:

• Membuktikan efisiensi tinggi: komitmen m+n elemen domain
• Tidak perlu komitmen tabel besar: dapat menangani tabel yang sangat besar

Binius memperkenalkan protokol Lasso versi multiplikasi:

• Menghasilkan "penghitung memori" yang meningkat secara bertahap melalui perkalian domain biner
• Pihak yang membuktikan berkomitmen terhadap vektor hitungan baca non-nol untuk memastikan keamanan

2.5 PCS: versi modifikasi Brakedown PCS

Inti pemikiran: packing

Dua rencana:

1. Menggunakan contoh kode concatenated untuk diinstansiasi
2. Menggunakan encoding level-block, mendukung penggunaan kode Reed-Solomon secara terpisah

Komitmen polinomial kecil dan evaluasi bidang yang diperluas:

• Berkomitmen di domain kecil K
• Mengevaluasi di domain ekstensi yang lebih besar L/K

Pengkodean blok dan kode Reed-Solomon:

• Memungkinkan subdomain ( seperti F2) polinomial menggunakan alfabet besar ( seperti F216) kode Reed-Solomon untuk komitmen yang efisien.

3. Pemikiran Optimalisasi

Empat poin optimasi kunci:

3.1 PIOP berbasis GKR: Perkalian domain biner berbasis GKR

Ubah "periksa A·B =? C" menjadi "periksa (gA)B =? gC"

• Hanya perlu satu komitmen tambahan
• Mengurangi pengeluaran Sumchecks

3.2 ZeroCheck PIOP optimasi: Perimbangan biaya perhitungan Prover dan Verifier

Metode optimasi:

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

3.3 Optimasi PIOP Sumcheck: Protokol Sumcheck Berbasis Domain Kecil

Poin Perbaikan:

• Pilihan untuk beralih putaran t
• Pengaruh ukuran basis
• Optimasi algoritma Karatsuba
• Peningkatan efisiensi memori

3.4 PCS optimasi: FRI-Binius mengurangi ukuran proof

Empat inovasi:

1. Polinomial datar
2. Polinomial Hilang Subruang
3. Pengemasan Basis Aljabar
4. Pertukaran Lingkaran SumCheck

FRI-Binius dapat mengurangi ukuran bukti Binius sebesar satu urutan.

4. Kesimpulan

Keunggulan Binius:

• Dapat digunakan untuk saksi dengan domain power-of-two minimum
• Pembuktian cepat dengan penggunaan memori rendah
• Menghapus hambatan komitmen Prover secara dasar

Bottleneck baru: Protokol Sumcheck

• Dapat menggunakan perangkat keras khusus untuk menyelesaikan dengan efisien

FRI-Binius:

• Menghilangkan biaya penyisipan bukti domain
• Tidak menyebabkan lonjakan biaya lapisan bukti agregasi

Kemajuan saat ini:

• Tim Irreducible mengembangkan lapisan rekursif, bekerja sama dengan Polygon untuk membangun zkVM berbasis Binius
• JoltzkVM beralih dari Lasso ke Binius
• Ingonyama merealisasikan versi FPGA Binius