Analisis Prinsip STARKs Binius dan Pemikiran Optimisasi
1 Pendahuluan
Salah satu alasan utama efisiensi STARKs yang rendah adalah sebagian besar nilai dalam program aktual cukup kecil, namun untuk memastikan keamanan pembuktian berbasis pohon Merkle, penggunaan pengkodean Reed-Solomon untuk memperluas data menyebabkan banyak nilai redundan tambahan 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 yang terbuang, yaitu generasi keempat STARKs.
Ketika menggunakan domain yang lebih kecil, operasi perluasan menjadi semakin penting untuk memastikan keamanan. Domain biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam perluasan, dan hanya perlu beroperasi di bawah domain dasar, sehingga mencapai efisiensi tinggi dalam domain kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu masuk ke dalam perluasan yang lebih besar untuk memastikan keamanan yang diperlukan.
Ketika membangun sistem pembuktian berdasarkan bidang biner, terdapat 2 masalah praktis: saat menghitung representasi trace di STARKs, ukuran bidang yang digunakan harus lebih besar dari derajat polinomial; saat melakukan komitmen Merkle tree di STARKs, perlu dilakukan pengkodean Reed-Solomon, ukuran bidang yang digunakan harus lebih besar dari ukuran setelah pengembangan pengkodean.
Binius telah mengajukan solusi inovatif yang secara terpisah menangani kedua masalah ini dan mewakili data yang sama dengan dua cara yang berbeda: pertama, menggunakan polinomial multivariat (khususnya polinomial multilinear) sebagai pengganti polinomial univariat, dengan mewakili seluruh jejak perhitungan melalui nilai-nilainya di "hypercube"; kedua, karena setiap dimensi hypercube memiliki panjang 2, maka tidak dapat melakukan ekstensi Reed-Solomon standar seperti STARKs, tetapi dapat menganggap hypercube sebagai persegi, dan melakukan ekstensi Reed-Solomon berdasarkan persegi tersebut. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.
2 Analisis Prinsip
Sebagian besar sistem SNARKs saat ini biasanya terdiri dari dua bagian berikut:
Bukti Oracle Interaktif Polinomial Teori Informasi (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP)
Binius: HyperPlonk PIOP + Brakedown PCS + domain biner. Secara spesifik, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan yang tinggi:
Aritmetika berbasis domain biner tower
Versi adaptasi HyperPlonk produk dan pemeriksaan pertukaran
Pembuktian pergeseran multilinier yang baru
Versi Perbaikan Lasso Mencari Bukti
Skema Komitmen Polin Kecil
2.1 Ruang Terbatas: Aritmetika berbasis towers of binary fields
Domain biner berbasis tower adalah kunci untuk mencapai komputasi yang dapat diverifikasi dengan cepat, terutama karena dua aspek: perhitungan yang efisien dan aritmetika yang efisien. Domain biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur domain biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan di atas domain biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi.
Di bidang bilangan prima Fp, metode reduksi yang umum digunakan termasuk reduksi Barrett, reduksi Montgomery, dan metode reduksi khusus untuk bidang terbatas tertentu seperti Mersenne-31 atau Goldilocks-64. Di bidang biner F2k, metode reduksi yang umum digunakan termasuk reduksi khusus (seperti yang digunakan dalam AES), reduksi Montgomery (seperti yang digunakan dalam POLYVAL), dan reduksi rekursif (seperti Tower).
Bidang biner tidak memerlukan pengenalan carry dalam operasi penjumlahan dan perkalian, dan operasi kuadrat dalam bidang biner sangat efisien karena mengikuti aturan penyederhanaan (X + Y )2 = X2 + Y 2.
2.2 PIOP: versi modifikasi Produk HyperPlonk dan PermutationCheck
Desain PIOP dalam protokol Binius mengadopsi HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi keakuratan polinomial dan himpunan multivariat. Mekanisme pemeriksaan inti ini meliputi:
GateCheck
PermutationCheck
LookupCheck
MultisetCheck
ProductCheck
ZeroCheck
SumCheck
BatchCheck
Binius telah melakukan perbaikan berikut dibandingkan dengan HyperPlonk:
Optimasi ProductCheck
Penanganan masalah pembagian dengan nol
Pemeriksaan Permutasi Lintas Kolom
2.3 PIOP: argumen pergeseran multilinear baru
Dalam protokol Binius, konstruksi dan pemrosesan polinomial virtual adalah salah satu teknologi kunci, yang dapat secara efektif menghasilkan dan mengoperasikan polinomial yang diturunkan dari pegangan input atau polinomial virtual lainnya. Berikut adalah dua metode kunci:
Pengemasan
Operator pergeseran
2.4 PIOP: versi adaptasi argumen pencarian Lasso
Protokol Lasso memungkinkan pihak pembuktian untuk mengkomit sebuah vektor a ∈ Fm, dan membuktikan bahwa semua elemennya terdapat dalam sebuah tabel yang telah ditentukan sebelumnya t ∈ Fn. Protokol Lasso terdiri dari tiga komponen berikut:
Abstraksi Polinomial Virtual Tabel Besar
Pencarian tabel kecil
Pemeriksaan multi-kumpulan
Protokol Binius mengadaptasi Lasso untuk operasi dalam domain biner, memperkenalkan versi perkalian dari protokol Lasso.
2.5 PCS：versi modifikasi Brakedown PCS
Gagasan inti dari membangun BiniusPCS adalah packing. Makalah Binius menyediakan 2 skema janji polinomial Brakedown berbasis domain biner:
Menggunakan kode concatenated untuk menginstansikan
Menggunakan teknologi encoding tingkat blok, mendukung penggunaan kode Reed-Solomon secara terpisah
Komitmen polinomial Binius terutama menggunakan teknologi berikut:
Komitmen polinomial kecil dan evaluasi bidang yang diperluas
Konstruksi Umum Domain Kecil
Pengkodean blok dan kode Reed-Solomon
3 Pemikiran yang Dioptimalkan
Untuk lebih meningkatkan kinerja protokol Binius, artikel ini mengusulkan empat poin optimasi kunci:
PIOP berbasis GKR: untuk operasi perkalian domain biner
Optimasi ZeroCheck PIOP: Menyeimbangkan biaya komputasi antara Prover dan Verifier
Optimasi PIOP Sumcheck: Optimasi untuk Sumcheck pada domain kecil
Optimasi PCS: Melalui optimasi FRI-Binius
3.1 PIOP berbasis GKR: Perkalian domain biner berbasis GKR
Algoritma operasi perkalian integer berbasis GKR, dengan mengubah "memeriksa apakah 2 integer 32-bit A dan B memenuhi A·B =? C" menjadi "memeriksa apakah (gA)B =? gC berlaku" menggunakan protokol GKR untuk secara signifikan mengurangi biaya komitmen.
3.2 ZeroCheck PIOP optimalisasi: Perimbangan biaya kalkulasi Prover dan Verifier
Makalah "Some Improvements for the PIOP for ZeroCheck" mengusulkan berbagai solusi optimasi untuk menyesuaikan distribusi beban kerja antara pihak pembuktian (P) dan pihak verifikasi (V), dengan tujuan untuk menyeimbangkan pengeluaran. Optimasi utama meliputi:
Mengurangi transfer data pihak yang membuktikan
Mengurangi jumlah titik evaluasi pihak yang membuktikan
Optimasi Interpolasi Aljabar
3.3 Optimasi PIOP Sumcheck: Protokol Sumcheck berbasis domain kecil
Ingonyama mengajukan perbaikan untuk protokol Sumcheck berbasis domain kecil pada tahun 2024 dan merilis kode implementasinya sebagai open source. Optimasi utama termasuk:
Pengaruh dan faktor perbaikan dari pergantian putaran
Pengaruh ukuran basis terhadap kinerja
Keuntungan optimisasi algoritma Karatsuba
Peningkatan efisiensi memori
3.4 PCS Optimasi: FRI-Binius mengurangi ukuran bukti Binius
Makalah "Bukti Polylogarithmic untuk Multilinears di Atas Menara Biner", disingkat FRI-Binius, mewujudkan mekanisme lipatan FRI di bidang biner, menghadirkan 4 inovasi dalam aspek:
Polinomial datar
Polinomial hilangnya subruang
Paket Basis Aljabar
Pertukaran SumCheck
Dengan FRI-Binius, ukuran bukti Binius dapat dikurangi satu urutan besar.
4 Ringkasan
Binius adalah "solusi desain kolaboratif yang menggunakan hardware, software, dan protokol Sumcheck yang dipercepat dengan FPGA", yang dapat membuktikan dengan sangat cepat dengan penggunaan memori yang sangat rendah. Di dalam Binius, hambatan komitmen Prover pada dasarnya telah dihilangkan sepenuhnya, dan hambatan baru terletak pada protokol Sumcheck, di mana banyak masalah evaluasi polinomial dan perkalian bidang dapat diselesaikan secara efisien dengan bantuan perangkat keras khusus.
FRI-Binius adalah solusi untuk varian FRI, yang menawarkan pilihan yang sangat menarik—menghilangkan overhead embedding dari lapisan bukti domain tanpa menyebabkan lonjakan biaya pada lapisan bukti agregat. Saat ini, tim Irreducible sedang mengembangkan lapisan rekursifnya dan mengumumkan kerja sama dengan tim Polygon untuk membangun zkVM berbasis Binius; JoltzkVM beralih dari Lasso ke Binius untuk meningkatkan kinerja rekursifnya; tim Ingonyama sedang mengimplementasikan versi FPGA dari Binius.
Halaman ini mungkin berisi konten pihak ketiga, yang disediakan untuk tujuan informasi saja (bukan pernyataan/jaminan) dan tidak boleh dianggap sebagai dukungan terhadap pandangannya oleh Gate, atau sebagai nasihat keuangan atau profesional. Lihat Penafian untuk detailnya.
26 Suka
Hadiah
26
8
Posting ulang
Bagikan
Komentar
0/400
AirdropF5Bro
· 19jam yang lalu
Oh ho, tampilan starknet kali ini ya.
Lihat AsliBalas0
¯\_(ツ)_/¯
· 08-12 16:41
Optimasi ini terlalu hebat, dari 252 ke binary.
Lihat AsliBalas0
SerumSquirter
· 08-10 20:16
Efisiensi semakin tinggi, area semakin kecil
Lihat AsliBalas0
GateUser-afe07a92
· 08-10 09:35
Sangat membosankan, berikutnya
Lihat AsliBalas0
ForkTongue
· 08-10 09:20
Ditulis dengan sangat baik tapi yang profesional tidak mengerti...
Lihat AsliBalas0
NullWhisperer
· 08-10 09:16
hmm... optimasi bidang biner tampaknya secara teoretis elegan tetapi mari kita bicarakan tentang kasus-kasus tepi dalam operasi bidang ekstensi...
Lihat AsliBalas0
HalfBuddhaMoney
· 08-10 09:15
Sudah berapa lama tidak menerjemahkan domain lebar nol? Kali ini saya akan menjelaskannya dengan jelas.
Lihat AsliBalas0
NonFungibleDegen
· 08-10 09:08
ser ini barang mencolok ini berdasarkan af... biner = angka naik, akhirnya beberapa alpha nyata bukan ini cope pohon merkle
Analisis Prinsip STARKs Binius: Optimasi Domain Biner dan Komitmen Polinomial yang Efisien
Analisis Prinsip STARKs Binius dan Pemikiran Optimisasi
1 Pendahuluan
Salah satu alasan utama efisiensi STARKs yang rendah adalah sebagian besar nilai dalam program aktual cukup kecil, namun untuk memastikan keamanan pembuktian berbasis pohon Merkle, penggunaan pengkodean Reed-Solomon untuk memperluas data menyebabkan banyak nilai redundan tambahan 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 yang terbuang, yaitu generasi keempat STARKs.
Ketika menggunakan domain yang lebih kecil, operasi perluasan menjadi semakin penting untuk memastikan keamanan. Domain biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam perluasan, dan hanya perlu beroperasi di bawah domain dasar, sehingga mencapai efisiensi tinggi dalam domain kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu masuk ke dalam perluasan yang lebih besar untuk memastikan keamanan yang diperlukan.
Ketika membangun sistem pembuktian berdasarkan bidang biner, terdapat 2 masalah praktis: saat menghitung representasi trace di STARKs, ukuran bidang yang digunakan harus lebih besar dari derajat polinomial; saat melakukan komitmen Merkle tree di STARKs, perlu dilakukan pengkodean Reed-Solomon, ukuran bidang yang digunakan harus lebih besar dari ukuran setelah pengembangan pengkodean.
Binius telah mengajukan solusi inovatif yang secara terpisah menangani kedua masalah ini dan mewakili data yang sama dengan dua cara yang berbeda: pertama, menggunakan polinomial multivariat (khususnya polinomial multilinear) sebagai pengganti polinomial univariat, dengan mewakili seluruh jejak perhitungan melalui nilai-nilainya di "hypercube"; kedua, karena setiap dimensi hypercube memiliki panjang 2, maka tidak dapat melakukan ekstensi Reed-Solomon standar seperti STARKs, tetapi dapat menganggap hypercube sebagai persegi, dan melakukan ekstensi Reed-Solomon berdasarkan persegi tersebut. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.
2 Analisis Prinsip
Sebagian besar sistem SNARKs saat ini biasanya terdiri dari dua bagian berikut:
Binius: HyperPlonk PIOP + Brakedown PCS + domain biner. Secara spesifik, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan yang tinggi:
2.1 Ruang Terbatas: Aritmetika berbasis towers of binary fields
Domain biner berbasis tower adalah kunci untuk mencapai komputasi yang dapat diverifikasi dengan cepat, terutama karena dua aspek: perhitungan yang efisien dan aritmetika yang efisien. Domain biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur domain biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan di atas domain biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi.
Di bidang bilangan prima Fp, metode reduksi yang umum digunakan termasuk reduksi Barrett, reduksi Montgomery, dan metode reduksi khusus untuk bidang terbatas tertentu seperti Mersenne-31 atau Goldilocks-64. Di bidang biner F2k, metode reduksi yang umum digunakan termasuk reduksi khusus (seperti yang digunakan dalam AES), reduksi Montgomery (seperti yang digunakan dalam POLYVAL), dan reduksi rekursif (seperti Tower).
Bidang biner tidak memerlukan pengenalan carry dalam operasi penjumlahan dan perkalian, dan operasi kuadrat dalam bidang biner sangat efisien karena mengikuti aturan penyederhanaan (X + Y )2 = X2 + Y 2.
2.2 PIOP: versi modifikasi Produk HyperPlonk dan PermutationCheck
Desain PIOP dalam protokol Binius mengadopsi HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi keakuratan polinomial dan himpunan multivariat. Mekanisme pemeriksaan inti ini meliputi:
Binius telah melakukan perbaikan berikut dibandingkan dengan HyperPlonk:
2.3 PIOP: argumen pergeseran multilinear baru
Dalam protokol Binius, konstruksi dan pemrosesan polinomial virtual adalah salah satu teknologi kunci, yang dapat secara efektif menghasilkan dan mengoperasikan polinomial yang diturunkan dari pegangan input atau polinomial virtual lainnya. Berikut adalah dua metode kunci:
2.4 PIOP: versi adaptasi argumen pencarian Lasso
Protokol Lasso memungkinkan pihak pembuktian untuk mengkomit sebuah vektor a ∈ Fm, dan membuktikan bahwa semua elemennya terdapat dalam sebuah tabel yang telah ditentukan sebelumnya t ∈ Fn. Protokol Lasso terdiri dari tiga komponen berikut:
Protokol Binius mengadaptasi Lasso untuk operasi dalam domain biner, memperkenalkan versi perkalian dari protokol Lasso.
2.5 PCS：versi modifikasi Brakedown PCS
Gagasan inti dari membangun BiniusPCS adalah packing. Makalah Binius menyediakan 2 skema janji polinomial Brakedown berbasis domain biner:
Komitmen polinomial Binius terutama menggunakan teknologi berikut:
3 Pemikiran yang Dioptimalkan
Untuk lebih meningkatkan kinerja protokol Binius, artikel ini mengusulkan empat poin optimasi kunci:
3.1 PIOP berbasis GKR: Perkalian domain biner berbasis GKR
Algoritma operasi perkalian integer berbasis GKR, dengan mengubah "memeriksa apakah 2 integer 32-bit A dan B memenuhi A·B =? C" menjadi "memeriksa apakah (gA)B =? gC berlaku" menggunakan protokol GKR untuk secara signifikan mengurangi biaya komitmen.
3.2 ZeroCheck PIOP optimalisasi: Perimbangan biaya kalkulasi Prover dan Verifier
Makalah "Some Improvements for the PIOP for ZeroCheck" mengusulkan berbagai solusi optimasi untuk menyesuaikan distribusi beban kerja antara pihak pembuktian (P) dan pihak verifikasi (V), dengan tujuan untuk menyeimbangkan pengeluaran. Optimasi utama meliputi:
3.3 Optimasi PIOP Sumcheck: Protokol Sumcheck berbasis domain kecil
Ingonyama mengajukan perbaikan untuk protokol Sumcheck berbasis domain kecil pada tahun 2024 dan merilis kode implementasinya sebagai open source. Optimasi utama termasuk:
3.4 PCS Optimasi: FRI-Binius mengurangi ukuran bukti Binius
Makalah "Bukti Polylogarithmic untuk Multilinears di Atas Menara Biner", disingkat FRI-Binius, mewujudkan mekanisme lipatan FRI di bidang biner, menghadirkan 4 inovasi dalam aspek:
Dengan FRI-Binius, ukuran bukti Binius dapat dikurangi satu urutan besar.
4 Ringkasan
Binius adalah "solusi desain kolaboratif yang menggunakan hardware, software, dan protokol Sumcheck yang dipercepat dengan FPGA", yang dapat membuktikan dengan sangat cepat dengan penggunaan memori yang sangat rendah. Di dalam Binius, hambatan komitmen Prover pada dasarnya telah dihilangkan sepenuhnya, dan hambatan baru terletak pada protokol Sumcheck, di mana banyak masalah evaluasi polinomial dan perkalian bidang dapat diselesaikan secara efisien dengan bantuan perangkat keras khusus.
FRI-Binius adalah solusi untuk varian FRI, yang menawarkan pilihan yang sangat menarik—menghilangkan overhead embedding dari lapisan bukti domain tanpa menyebabkan lonjakan biaya pada lapisan bukti agregat. Saat ini, tim Irreducible sedang mengembangkan lapisan rekursifnya dan mengumumkan kerja sama dengan tim Polygon untuk membangun zkVM berbasis Binius; JoltzkVM beralih dari Lasso ke Binius untuk meningkatkan kinerja rekursifnya; tim Ingonyama sedang mengimplementasikan versi FPGA dari Binius.