Analisis Prinsip Binius STARKs 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 pembuktian 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 pemborosan, yaitu generasi keempat STARKs.

Dibandingkan dengan penelitian dalam beberapa tahun terakhir tentang Goldilocks, BabyBear, Mersenne31 dan bidang terbatas lainnya, penelitian tentang bidang biner dapat ditelusuri kembali ke tahun 1980-an dan telah diterapkan secara luas dalam kriptografi, seperti AES(F28 bidang), GMAC(F2128 bidang), QR kode(F28 bidang Reed-Solomon pengkodean), dan lain-lain.

Binius menggunakan domain biner, yang sepenuhnya bergantung pada perluasan domain untuk menjamin keamanan dan ketersediaan. Sebagian besar perhitungan Prover beroperasi secara efisien di bawah bidang dasar, pemeriksaan titik acak dan perhitungan FRI memerlukan pendalaman perluasan domain untuk memastikan keamanan.

Binius menggunakan polinomial multivariat untuk merepresentasikan jalur perhitungan dengan mengambil nilai pada "hiperkubus", memandang hiperkubus sebagai persegi untuk memperluas Reed-Solomon, dan secara signifikan meningkatkan efisiensi pengkodean dan kinerja perhitungan sambil memastikan keamanan.

2. Analisis Prinsip

Binius: HyperPlonk PIOP + Brakedown PCS + domain biner.

Termasuk lima teknologi kunci:

1. Dasar perhitungan aritmetik berbasis bidang biner bertingkat

2. Modifikasi pemeriksaan produk dan permutasi HyperPlonk, memastikan konsistensi pemeriksaan variabel dan permutasi

3. Pembuktian pergeseran multilinear baru, optimalkan efisiensi verifikasi hubungan multilinear pada domain kecil

4. Versi perbaikan Lasso menemukan argumen, memberikan fleksibilitas dan keamanan untuk mekanisme pencarian

5. Skema komitmen polinomial kecil, mewujudkan sistem bukti efisien di atas bidang biner

2.1 Ruang Terbatas: Aritmetika berbasis menara bidang biner

Domain biner bertingkat mendukung operasi aritmatika yang efisien dan proses aritmatika yang disederhanakan, sangat cocok untuk sistem bukti yang dapat diskalakan seperti Binius.

String 128-bit 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, enam belas elemen domain tower 8-bit, atau seratus dua puluh delapan elemen domain F2. Fleksibilitas ini tidak memerlukan biaya komputasi, hanya konversi tipe dari string bit.

2.2 PIOP: Versi Adaptasi Produk HyperPlonk dan PermutationCheck

Binius PIOP mengadaptasi HyperPlonk, menggunakan mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan himpunan multivariat, termasuk GateCheck, PermutationCheck, LookupCheck, MultisetCheck, ProductCheck, ZeroCheck, SumCheck, BatchCheck.

Binius telah melakukan perbaikan di 3 area berikut:

• Optimasi ProductCheck: mengkhususkan nilai menjadi 1, menyederhanakan proses pemeriksaan untuk mengurangi kompleksitas perhitungan

• Penanganan masalah pembagian dengan nol: menangani dengan benar situasi di mana penyebut adalah nol, diizinkan untuk diperluas ke nilai produk yang mana saja.

• Periksa Permutasi Antar Kolom: Mendukung Periksa Permutasi antar beberapa kolom, menangani kasus susunan polinomial yang lebih kompleks.

2.3 PIOP: argumen pergeseran multilinear baru

Konstruksi dan pengolahan polinomial virtual di Binius adalah teknologi kunci:

• Packing: Mengemas elemen yang berurutan dengan posisi yang lebih kecil menjadi elemen yang lebih besar untuk mengoptimalkan operasi

• Operator pergeseran: mengatur ulang elemen dalam blok, berdasarkan offset yang diberikan untuk pergeseran sirkuler

2.4 PIOP: versi adaptasi argumen pencarian Lasso

Protokol Lasso memungkinkan pihak yang membuktikan untuk berkomitmen pada vektor a ∈ Fm dan membuktikan bahwa semua elemen ada dalam tabel yang telah ditentukan sebelumnya t ∈ Fn.

Binius menyesuaikan Lasso untuk operasi bidang biner, memperkenalkan versi multiplikasi dari protokol Lasso, yang mengharuskan pihak pembuktian dan pihak verifikasi untuk bersama-sama meningkatkan operasi "penghitungan memori", menghasilkan peningkatan melalui perkalian bidang biner.

2.5 PCS: versi adaptasi Brakedown PCS

Inti pemikiran BiniusPCS adalah packing. Menyediakan 2 jenis skema komitmen polinomial Brakedown berbasis domain biner:

1. Menginstansikan kode yang digabungkan

2. Menggunakan teknologi pengkodean tingkat blok, mendukung penggunaan kode Reed-Solomon secara terpisah

Opsi kedua menyederhanakan proses pembuktian dan verifikasi, ukuran bukti sedikit lebih besar tetapi keuntungan dalam penyederhanaan dan implementasi sangat berharga.

3. Optimasi Pemikiran

3.1 PIOP berbasis GKR: Perkalian domain biner berbasis GKR

Ubah "Periksa apakah 2 bilangan bulat 32-bit A dan B memenuhi A·B =? C" menjadi "Periksa apakah (gA)B =? gC" berlaku, dengan memanfaatkan protokol GKR untuk mengurangi biaya komitmen secara signifikan.

Operasi perkalian berbasis GKR hanya memerlukan satu komitmen tambahan, yang membuat algoritme lebih efisien dengan mengurangi biaya Sumchecks, terutama dalam skenario di mana operasi Sumchecks lebih murah dibandingkan dengan pembuatan komitmen.

3.2 ZeroCheck PIOP optimasi: Perimbangan biaya perhitungan Prover dan Verifier

Mengurangi transmisi data pihak yang membuktikan: Memindahkan sebagian pekerjaan ke pihak yang memverifikasi, mengurangi jumlah data yang dikirim oleh pihak yang membuktikan.

Mengurangi jumlah titik evaluasi pihak pembuktian: Mengubah cara pengiriman polinomial, mengurangi jumlah titik evaluasi.

Optimasi Interpolasi Aljabar: membangun dekomposisi terurut melalui pembagian panjang polinomial untuk mencapai optimasi interpolasi.

3.3 Optimasi PIOP Sumcheck: Protokol Sumcheck berbasis domain kecil

Dampak dan faktor perbaikan dari pergantian putaran: Pemilihan putaran t mempengaruhi kinerja, faktor perbaikan titik pergantian terbaik mencapai nilai maksimum.

Dampak ukuran basis terhadap kinerja: basis yang lebih kecil ( seperti GF[2]) memiliki keunggulan algoritma yang lebih jelas.

Optimisasi algoritma Karatsuba: Meningkatkan kinerja Sumcheck berbasis bidang kecil secara signifikan, algoritma 4 lima kali lebih efisien dibandingkan algoritma 3.

Peningkatan efisiensi memori: Kebutuhan memori algoritma 4 O(d·t), algoritma 3 adalah O(2d·t), cocok untuk lingkungan dengan sumber daya terbatas.

3.4 PCS Optimasi: FRI-Binius mengurangi ukuran bukti Binius

FRI-Binius mewujudkan mekanisme lipatan FRI biner, membawa 4 inovasi:

• Polinomial datar
• Polinomial hilang subruang
• Pengemasan basis aljabar
• Pertukaran Suku SumCheck

Dengan bantuan FRI-Binius, ukuran bukti Binius dapat dikurangi satu urutan, mendekati sistem paling canggih.

4. Kesimpulan

Binius telah secara dasar menghilangkan bottleneck komitmen Prover, bottleneck baru terletak pada protokol Sumcheck. Skema FRI-Binius adalah varian FRI yang dapat menghilangkan overhead embedding dari lapisan bukti domain.

Tim Irreducible mengembangkan lapisan rekursif, bekerja sama dengan Polygon untuk membangun zkVM berbasis Binius. JoltzkVM beralih dari Lasso ke Binius untuk meningkatkan kinerja rekursif. Ingonyama mewujudkan versi FPGA dari Binius.