Analisis Prinsip STARKs Binius dan Pemikiran Optimisasi

1 Pendahuluan

Salah satu alasan utama efisiensi STARKs yang rendah adalah: 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. Sebaliknya, bidang biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang yang terbuang, yaitu generasi keempat STARKs.

Domain biner telah banyak digunakan dalam kriptografi, contoh tipikal termasuk:

• Standar Enkripsi Lanjutan ( AES ), berbasis pada domain F28
• Kode autentikasi pesan Galois ( GMAC ), berbasis pada bidang F2128
• QR code, menggunakan pengkodean Reed-Solomon berbasis F28
• Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk final SHA-3

Ketika menggunakan domain yang lebih kecil, operasi perluasan domain menjadi semakin penting untuk memastikan keamanan. Domain biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan domain untuk menjamin keamanan dan kegunaannya yang sebenarnya.

Binius mengajukan solusi inovatif:

• Menggunakan polinomial multivariat (khususnya polinomial multilinier) sebagai pengganti polinomial univariat, dengan nilai-nilainya pada "hiper kubus" untuk merepresentasikan seluruh lintasan perhitungan.
• Anggap hypercube sebagai persegi, lakukan perluasan Reed-Solomon berdasarkan persegi tersebut.

2 Analisis Prinsip

Binius = HyperPlonk PIOP + Brakedown PCS + bidang biner

Binius mencakup lima teknologi kunci:

1. Aritmetika berbasis domain biner tower
2. Versi adaptasi pemeriksaan produk dan permutasi HyperPlonk
3. Bukti Perpindahan Multilinear Baru
4. Versi Perbaikan Lasso Temuan Argumen
5. Skema Komitmen Polinial Kecil

2.1 Ruang Terbatas: Aritmetika yang berbasis pada menara bidang biner

Keuntungan domain biner bertingkat:

• Perhitungan efisien: Domain biner pada dasarnya mendukung operasi aritmatika yang sangat efisien.
• Proses aritmetika yang efisien: Struktur bidang biner mendukung proses aritmetika yang disederhanakan
• Representasi fleksibel: Sebuah string yang sama dapat diinterpretasikan dengan berbagai cara dalam konteks domain biner.
• Tanpa reduksi: bidang biner tidak perlu memperkenalkan carry dalam operasi penjumlahan dan perkalian.
• Perhitungan kuadrat yang efisien:(X + Y)2 = X2 + Y2

2.2 PIOP: Versi Adaptasi Produk HyperPlonk dan PermutationCheck

Mekanisme pemeriksaan inti:

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

Perbaikan dibandingkan HyperPlonk:

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

2.3 PIOP: argumen pergeseran multilinear baru

Metode kunci:

• Packing: Mengoptimalkan operasi dengan mengemas elemen yang lebih kecil yang bersebelahan dalam urutan kamus menjadi elemen yang lebih besar.
• Operator pergeseran: menyusun ulang elemen dalam blok berdasarkan offset yang diberikan untuk pergeseran melingkar

2.4 PIOP: versi adaptasi argumen pencarian Lasso

Keunggulan protokol Lasso:

• Pembuktian efisien: Untuk m pencarian dalam tabel dengan ukuran n, hanya perlu menjanjikan m+n elemen domain.
• Tanpa komitmen tabel besar: Jika tabel t terstruktur, maka tidak perlu berkomitmen padanya, dapat memproses tabel super besar

Komponen dari Protokol Lasso:

• Abstraksi polinomial virtual dari tabel besar
• Pencarian tabel kecil
• Banyak pemeriksaan koleksi

Adaptasi Binius terhadap Lasso:

• Memperkenalkan versi perkalian dari protokol Lasso
• Memerlukan bukti bahwa pihak yang membuktikan berkomitmen pada vektor penghitung baca yang tidak nol di mana-mana

2.5 PCS: versi modifikasi Brakedown PCS

Inti pemikiran: packing

Dua jenis solusi:

1. Menggunakan kode yang terhubung
2. Menggunakan teknologi encoding tingkat blok, mendukung penggunaan kode Reed-Solomon secara terpisah

Teknologi Utama:

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

3 Pemikiran Optimasi

Empat poin optimasi kunci:

1. PIOP berbasis GKR: terkait dengan operasi perkalian domain biner
2. ZeroCheck PIOP optimasi: Penimbangan biaya komputasi Prover dan Verifier
3. Optimasi PIOP Sumcheck: Protokol Sumcheck berbasis domain kecil
4. Optimasi PCS: FRI-Binius mengurangi ukuran bukti Binius

3.1 PIOP berbasis GKR: perkalian domain biner berbasis GKR

Inti pemikiran:

Periksa apakah "2 buah integer 32-bit A dan B memenuhi A·B =? C" Konversi ke
"Memeriksa (gA)B =? gC apakah valid"

Keuntungan:

• Hanya perlu satu janji bantu
• Mengurangi biaya Sumchecks

3.2 ZeroCheck PIOP optimalisasi

Arah optimasi:

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

3.3 Sumcheck PIOP optimasi

Poin Perbaikan:

• Pilihan untuk beralih putaran
• Pengaruh ukuran domain dasar terhadap kinerja
• Keuntungan optimasi algoritma Karatsuba
• Peningkatan efisiensi memori

Hasil konkret:

• Dalam kasus basis bidang GF[2], kinerja algoritma 4 lebih tinggi hampir 30 kali dibandingkan dengan algoritma naif.
• Algoritma 4 hanya membutuhkan 0,26MB memori, sementara algoritma 3 membutuhkan 67MB

3.4 PCS optimalisasi:FRI-Binius

Empat poin inovasi:

1. Polinomial datar
2. Polinomial Hilang Subruang
3. Kemasan basis aljabar
4. Pertukaran Lingkaran SumCheck

Hasil: Kurangi ukuran bukti Binius satu tingkat.

4 Ringkasan

Keunggulan Binius:

• Dapat digunakan oleh saksi dengan domain power-of-two terkecil
• Penggunaan memori rendah, bukti cepat
• Komitmen Prover yang menjadi kendala hampir sepenuhnya dihilangkan

FRI-Binius方案: Menghilangkan overhead embedding dari lapisan bukti domain tanpa menyebabkan lonjakan biaya pada lapisan bukti agregat.

Perkembangan terbaru:

• Tim Irreducible sedang mengembangkan lapisan rekursifnya, dan bekerja sama dengan tim Polygon untuk membangun zkVM berbasis Binius
• JoltzkVM sedang beralih dari Lasso ke Binius untuk meningkatkan kinerja rekursifnya
• Tim Ingonyama sedang mengimplementasikan versi FPGA dari Binius