Analisis Prinsip dan Pemikiran Optimisasi Binius STARKs
1. Pendahuluan
Salah satu alasan utama efisiensi STARKs yang rendah adalah karena sebagian besar nilai dalam program aktual cukup 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. Untuk mengatasi masalah ini, 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 langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang terbuang, yaitu generasi keempat STARKs.
Domain biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan domain untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam perluasan domain, melainkan cukup beroperasi di dalam domain dasar, sehingga mencapai efisiensi tinggi dalam domain kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu mendalami ke dalam perluasan domain yang lebih besar untuk memastikan keamanan yang dibutuhkan.
Binius mengusulkan solusi inovatif: pertama, menggunakan polinomial multivariabel (khususnya polinomial multilinear) sebagai pengganti polinomial univariat, dengan nilai-nilainya pada "hyper kubus" untuk mewakili seluruh jejak perhitungan; kedua, karena panjang setiap dimensi hyper kubus adalah 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti pada STARKs, tetapi hyper kubus dapat dipandang sebagai persegi, dan berdasarkan persegi tersebut dilakukan perluasan Reed-Solomon.
2. Analisis Prinsip
Binius mencakup lima teknologi kunci:
Aritmetika berbasis bidang biner bertingkat
Versi modifikasi pemeriksaan produk dan permutasi HyperPlonk
Bukti Perpindahan Multilinear Baru
Versi Perbaikan Lasso Mencari Bukti
Skema komitmen polinomial kecil
2.1 Ruang Terbatas: Aritmetika berdasarkan towers of binary fields
Keuntungan dari domain biner bertingkat:
Komputasi Efisien: Bidang biner pada dasarnya mendukung operasi aritmatika yang sangat efisien.
Arithmetika Efisien: Struktur bidang biner mendukung proses arithmetika yang disederhanakan
Representasi yang standar: Elemen dalam domain biner memiliki satu cara representasi yang unik dan langsung.
Keuntungan domain biner:
Operasi penjumlahan dan perkalian tidak perlu membawa angka.
Operasi kuadrat sangat efisien, mengikuti aturan penyederhanaan (X + Y)^2 = X^2 + Y^2
Menunjukkan fleksibilitas: String 128 bit dapat dianggap sebagai elemen unik dalam domain biner 128 bit, atau diuraikan sebagai kombinasi berbagai elemen domain tower.
2.2 PIOP: versi modifikasi Produk HyperPlonk dan PermutationCheck
Mekanisme Pemeriksaan Inti PIOP Binius:
GateCheck
PermutationCheck
LookupCheck
MultisetCheck
ProductCheck
ZeroCheck
SumCheck
BatchCheck
Perbaikan Binius terhadap HyperPlonk:
Optimasi ProductCheck
Penanganan masalah pembagian dengan nol
Dukungan PermutationCheck lintas kolom
2.3 PIOP: argumen pergeseran multilinear baru
Metode kunci:
Pengemasan: Mengoptimalkan operasi dengan mengemas elemen yang berdekatan
Operator pergeseran: menyusun ulang elemen dalam blok
2.4 PIOP: versi modifikasi argumen pencarian Lasso
Komponen protokol Lasso:
Abstraksi Polinomial Virtual dari Tabel Besar
Pencarian tabel kecil
Pemeriksaan banyak kumpulan
Adaptasi Binius terhadap Lasso:
Memperkenalkan versi multiplikasi dari protokol Lasso
Memerlukan bukti bahwa pihak yang membuktikan berkomitmen pada vektor penghitung baca yang tidak nol di mana saja.
2.5 PCS: versi modifikasi Brakedown PCS
Inti pemikiran: packing
Dua skema komitmen polinomial Brakedown berbasis bidang biner:
Menggunakan contoh kode yang digabungkan
Menggunakan teknologi encoding block-level, mendukung penggunaan kode Reed-Solomon secara terpisah
Teknologi Utama:
Komitmen polinomial kecil dan evaluasi domain yang diperluas
Struktur Umum Kecil
Kode blok dan kode Reed-Solomon
3. Pemikiran Optimalisasi
Empat titik optimasi kunci:
3.1 PIOP berbasis GKR: Perkalian domain biner berbasis GKR
Keunggulan dibandingkan solusi Binius lookup:
Hanya perlu satu janji pendukung
Mengurangi biaya 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 kunci:
Pengaruh dan faktor perbaikan untuk berganti putaran
Pengaruh ukuran basis terhadap kinerja
Manfaat optimasi algoritma Karatsuba
Peningkatan efisiensi memori
3.4 PCS optimasi: FRI-Binius mengurangi ukuran bukti Binius
Empat inovasi FRI-Binius:
Polinomial datar
Polinomial Hilang Subruang
Pengemasan basis aljabar
Pertukaran Ring SumCheck
FRI-Binius PCS proses:
Tahap janji
Tahap evaluasi
4. Kesimpulan
Proposisi nilai Binius:
Dapat digunakan untuk saksi dengan domain power-of-two terkecil
Rancangan kolaboratif, penggunaan memori rendah untuk pembuktian cepat
Menghapus dasar dari hambatan komitmen Prover
Bottleneck baru terletak pada protokol Sumcheck, yang dapat diatasi secara efisien dengan perangkat keras khusus.
FRI-Binius方案:
Menghilangkan overhead embedding dari lapisan bukti domain
Tidak akan menyebabkan lonjakan biaya lapisan bukti agregat
Kemajuan saat ini:
Tim Irreducible mengembangkan lapisan rekursif, berkolaborasi dengan Polygon untuk membangun zkVM berbasis Binius
JoltzkVM beralih dari Lasso ke Binius
Tim Ingonyama berhasil mengimplementasikan versi FPGA Binius
Lihat Asli
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
16 Suka
Hadiah
16
7
Bagikan
Komentar
0/400
hodl_therapist
· 9jam yang lalu
Kemajuan yang benar-benar terobosan
Lihat AsliBalas0
GateUser-e51e87c7
· 07-11 16:42
Membuat kode lebih ringkas
Lihat AsliBalas0
ForkLibertarian
· 07-10 22:45
Optimasi kinerja telah mengalami terobosan
Lihat AsliBalas0
ConfusedWhale
· 07-10 22:44
Perlu Drop nilai domain yang berlebihan
Lihat AsliBalas0
AlphaLeaker
· 07-10 22:43
Keamanan perlu dipertimbangkan dalam perluasan domain
Lihat AsliBalas0
MetaverseLandlord
· 07-10 22:41
Lebih baik dibandingkan dengan generasi sebelumnya.
Binius STARKs: Analisis Mendalam Teknologi Bukti Tanpa Pengetahuan Generasi Baru yang Efisien
Analisis Prinsip dan Pemikiran Optimisasi Binius STARKs
1. Pendahuluan
Salah satu alasan utama efisiensi STARKs yang rendah adalah karena sebagian besar nilai dalam program aktual cukup 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. Untuk mengatasi masalah ini, 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 langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang terbuang, yaitu generasi keempat STARKs.
Domain biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan domain untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam perluasan domain, melainkan cukup beroperasi di dalam domain dasar, sehingga mencapai efisiensi tinggi dalam domain kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu mendalami ke dalam perluasan domain yang lebih besar untuk memastikan keamanan yang dibutuhkan.
Binius mengusulkan solusi inovatif: pertama, menggunakan polinomial multivariabel (khususnya polinomial multilinear) sebagai pengganti polinomial univariat, dengan nilai-nilainya pada "hyper kubus" untuk mewakili seluruh jejak perhitungan; kedua, karena panjang setiap dimensi hyper kubus adalah 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti pada STARKs, tetapi hyper kubus dapat dipandang sebagai persegi, dan berdasarkan persegi tersebut dilakukan perluasan Reed-Solomon.
2. Analisis Prinsip
Binius mencakup lima teknologi kunci:
2.1 Ruang Terbatas: Aritmetika berdasarkan towers of binary fields
Keuntungan dari domain biner bertingkat:
Keuntungan domain biner:
2.2 PIOP: versi modifikasi Produk HyperPlonk dan PermutationCheck
Mekanisme Pemeriksaan Inti PIOP Binius:
Perbaikan Binius terhadap HyperPlonk:
2.3 PIOP: argumen pergeseran multilinear baru
Metode kunci:
2.4 PIOP: versi modifikasi argumen pencarian Lasso
Komponen protokol Lasso:
Adaptasi Binius terhadap Lasso:
2.5 PCS: versi modifikasi Brakedown PCS
Inti pemikiran: packing
Dua skema komitmen polinomial Brakedown berbasis bidang biner:
Teknologi Utama:
3. Pemikiran Optimalisasi
Empat titik optimasi kunci:
3.1 PIOP berbasis GKR: Perkalian domain biner berbasis GKR
Keunggulan dibandingkan solusi Binius lookup:
3.2 ZeroCheck PIOP optimasi: Perimbangan biaya perhitungan Prover dan Verifier
Metode optimasi:
3.3 Optimasi PIOP Sumcheck: Protokol Sumcheck berbasis domain kecil
Poin kunci:
3.4 PCS optimasi: FRI-Binius mengurangi ukuran bukti Binius
Empat inovasi FRI-Binius:
FRI-Binius PCS proses:
4. Kesimpulan
Proposisi nilai Binius:
FRI-Binius方案:
Kemajuan saat ini: