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.

Bitlayer Research:Analisis prinsip Binius STARKs dan pemikiran optimasinya

2. Analisis Prinsip

Binius mencakup lima teknologi kunci:

  1. Aritmetika berbasis bidang biner bertingkat
  2. Versi modifikasi pemeriksaan produk dan permutasi HyperPlonk
  3. Bukti Perpindahan Multilinear Baru
  4. Versi Perbaikan Lasso Mencari Bukti
  5. 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.

Bitlayer Research: Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi

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

Bitlayer Research: Analisis Prinsip STARKs Binius dan Pemikiran Optimasi

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:

  1. Menggunakan contoh kode yang digabungkan
  2. 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

Bitlayer Research: Analisis Prinsip Binius STARKs dan Pemikiran Optimasi

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

Bitlayer Research: Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi

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

Bitlayer Research:Binius STARKs prinsip analisis dan pemikiran optimisasi

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

Bitlayer Research: Analisis Prinsip STARKs Binius dan Pemikiran Optimisasi

Bitlayer Research: Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi

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.
  • Hadiah
  • 7
  • Bagikan
Komentar
0/400
hodl_therapistvip
· 9jam yang lalu
Kemajuan yang benar-benar terobosan
Lihat AsliBalas0
GateUser-e51e87c7vip
· 07-11 16:42
Membuat kode lebih ringkas
Lihat AsliBalas0
ForkLibertarianvip
· 07-10 22:45
Optimasi kinerja telah mengalami terobosan
Lihat AsliBalas0
ConfusedWhalevip
· 07-10 22:44
Perlu Drop nilai domain yang berlebihan
Lihat AsliBalas0
AlphaLeakervip
· 07-10 22:43
Keamanan perlu dipertimbangkan dalam perluasan domain
Lihat AsliBalas0
MetaverseLandlordvip
· 07-10 22:41
Lebih baik dibandingkan dengan generasi sebelumnya.
Lihat AsliBalas0
AirdropBuffetvip
· 07-10 22:19
Efisiensi adalah kebenaran yang keras
Lihat AsliBalas0
  • Sematkan
Perdagangkan Kripto Di Mana Saja Kapan Saja
qrCode
Pindai untuk mengunduh aplikasi Gate
Komunitas
Bahasa Indonesia
  • 简体中文
  • English
  • Tiếng Việt
  • 繁體中文
  • Español
  • Русский
  • Français (Afrique)
  • Português (Portugal)
  • Bahasa Indonesia
  • 日本語
  • بالعربية
  • Українська
  • Português (Brasil)