Analisis Prinsip Binius STARKs dan Pemikiran Optimasi
1 Pendahuluan
Salah satu alasan utama efisiensi STARKs yang rendah adalah: sebagian besar nilai dalam program nyata cukup kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dan sebagainya. Namun, untuk memastikan keamanan bukti berbasis pohon Merkle, ketika menggunakan pengkodean Reed-Solomon untuk memperluas data, banyak nilai redundan tambahan akan mengisi seluruh bidang, meskipun nilai asli itu sendiri sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran bidang menjadi strategi kunci.
Seperti yang ditunjukkan pada Tabel 1, lebar kode STARKs generasi pertama adalah 252bit, lebar kode STARKs generasi kedua adalah 64bit, lebar kode STARKs generasi ketiga adalah 32bit, tetapi lebar kode 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, bidang biner memungkinkan operasi langsung pada bit, pengkodean yang kompak dan efisien tanpa ruang yang terbuang, yaitu STARKs generasi keempat.
Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian baru-baru ini tentang bidang terbatas, penelitian bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah digunakan secara luas dalam kriptografi, contoh tipikal termasuk:
Standar Enkripsi Tingkat Lanjut (AES), berbasis bidang F28;
Kode Otentikasi Pesan Galois ( GMAC ), berdasarkan domain F2128;
Kode QR, menggunakan pengkodean Reed-Solomon berbasis F28;
Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk ke final SHA-3, yang berbasis pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursi.
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, tetapi cukup 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 dibutuhkan.
Ketika membangun sistem bukti berdasarkan domain biner, ada 2 masalah praktis: ukuran domain yang digunakan untuk menghitung representasi jejak dalam STARKs harus lebih besar dari derajat polinomial; saat melakukan komitmen pohon Merkle dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, dan ukuran domain yang digunakan harus lebih besar dari ukuran setelah pengkodean diperluas.
Binius mengajukan solusi inovatif untuk menangani kedua masalah tersebut, dan mewujudkannya dengan cara yang berbeda untuk merepresentasikan data yang sama: pertama, menggunakan multivariat ( yang secara khusus adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan merepresentasikan seluruh jejak perhitungan melalui nilai-nilainya di "hypercube" ( hypercubes ); kedua, karena panjang setiap dimensi hypercube adalah 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti pada STARKs, tetapi hypercube dapat dipandang sebagai persegi ( square ), dan perluasan Reed-Solomon dapat dilakukan berdasarkan persegi tersebut. Metode ini sangat meningkatkan efisiensi pengkodean dan kinerja komputasi sambil memastikan keamanan.
2 Analisis Prinsip
Konstruksi sebagian besar sistem SNARKs saat ini biasanya terdiri dari dua bagian berikut:
Teori informasi bukti orakel interaktif polinomial (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti dari sistem bukti, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Protokol PIOP yang berbeda memungkinkan penyedia bukti untuk mengirim polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah komputasi itu benar dengan menanyakan hasil evaluasi dari sejumlah kecil polinomial. Protokol PIOP yang ada termasuk: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara berbeda dalam menangani ekspresi polinomial, sehingga mempengaruhi kinerja dan efisiensi seluruh sistem SNARK.
Skema Janji Polinomial ( Polynomial Commitment Scheme, PCS ): Skema janji polinomial digunakan untuk membuktikan apakah kesetaraan polinomial yang dihasilkan oleh PIOP berlaku. PCS adalah alat kriptografi, melalui mana, pembuktian dapat berjanji pada suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain tentang polinomial. Skema janji polinomial yang umum digunakan adalah KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) dan Brakedown, dll. Berbagai PCS memiliki kinerja, keamanan, dan skenario penerapan yang berbeda.
Berdasarkan kebutuhan spesifik, pilih PIOP dan PCS yang berbeda, dan kombinasikan dengan bidang terbatas atau kurva elips yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Misalnya:
• Halo2: dikombinasikan dari PLONK PIOP dan Bulletproofs PCS, serta didasarkan pada kurva Pasta. Desain Halo2 berfokus pada skalabilitas dan menghilangkan trusted setup dalam protokol ZCash.
• Plonky2: Mengadopsi PLONK PIOP dan FRI PCS yang digabungkan, serta berdasarkan domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem-sistem ini, pilihan PIOP dan PCS yang digunakan harus sesuai dengan finite field atau kurva elips yang digunakan, untuk memastikan kebenaran, kinerja, dan keamanan sistem. Pilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti SNARK dan efisiensi verifikasi, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa pengaturan tepercaya, serta apakah dapat mendukung fungsi-fungsi tambahan seperti bukti rekursif atau bukti agregasi.
Binius: HyperPlonk PIOP + Brakedown PCS + binary field. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, aritmetika berbasis menara bidang biner (towers of binary fields) menjadi dasar perhitungan, yang mampu melakukan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol pembuktian Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol memperkenalkan sebuah pembuktian pergeseran multilinear baru, yang mengoptimalkan efisiensi dalam memverifikasi hubungan multilinear di bidang kecil. Keempat, Binius menggunakan versi yang ditingkatkan dari pembuktian pencarian Lasso, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), yang memungkinkannya untuk mencapai sistem pembuktian yang efisien di bidang biner, dan mengurangi biaya yang biasanya terkait dengan bidang besar.
2.1 Ruang Terbatas: Aritmetika berdasarkan menara bidang biner
Bidang biner bertingkat adalah kunci untuk mewujudkan komputasi yang dapat diverifikasi dengan cepat, terutama disebabkan oleh dua aspek: komputasi yang efisien dan aritmetika yang efisien. Bidang biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur bidang biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan pada bidang biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Karakteristik ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya fitur hierarkisnya melalui struktur bertingkat, menjadikan bidang biner sangat cocok untuk sistem bukti yang dapat diskalakan seperti Binius.
Di mana "canonical" merujuk pada representasi unik dan langsung dari elemen dalam bidang biner. Misalnya, dalam bidang biner paling dasar F2, string dengan k bit mana pun dapat langsung dipetakan ke elemen bidang biner dengan k bit. Ini berbeda dengan bidang prima, yang tidak dapat memberikan representasi normatif semacam itu dalam bit yang ditentukan. Meskipun bidang prima 32-bit dapat terkandung dalam 32 bit, tidak setiap string 32-bit dapat secara unik berhubungan dengan elemen bidang, sementara bidang biner memiliki kenyamanan pemetaan satu-ke-satu tersebut. Dalam bidang prima Fp, metode reduksi umum termasuk reduksi Barrett, reduksi Montgomery, serta metode reduksi khusus untuk bidang terbatas tertentu seperti Mersenne-31 atau Goldilocks-64. Dalam 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 ). Makalah "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" menunjukkan bahwa dalam bidang biner, operasi penjumlahan dan perkalian tidak perlu membawa, dan operasi kuadrat di bidang biner sangat efisien, karena mengikuti aturan penyederhanaan (X + Y )2 = X2 + Y 2.
Seperti yang ditunjukkan pada Gambar 1, sebuah string 128-bit: String ini dapat diinterpretasikan dalam berbagai cara dalam konteks domain biner. Ini 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 representasi ini tidak memerlukan biaya komputasi apa pun, hanya konversi tipe string bit (typecast), adalah atribut yang sangat menarik dan berguna. Pada saat yang sama, elemen domain kecil dapat dikemas menjadi elemen domain yang lebih besar tanpa memerlukan biaya komputasi tambahan. Protokol Binius memanfaatkan fitur ini untuk meningkatkan efisiensi komputasi. Selain itu, makalah "On Efficient Inversion in Tower Fields of Characteristic Two" membahas kompleksitas komputasi dari operasi perkalian, kuadrat, dan invers di domain tower biner n-bit yang dapat terurai menjadi subdomain m-bit (.
![Bitlayer Research: Analisis Prinsip Binius STARKs dan Pemikiran Optimisasinya])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: Versi Modifikasi HyperPlonk Product dan PermutationCheck------Cocok untuk bidang biner
Desain PIOP dalam protokol Binius mengadopsi HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan kumpulan multivariat. Pemeriksaan inti ini mencakup:
GateCheck: Verifikasi saksi rahasia ω dan input publik x apakah memenuhi hubungan operasi sirkuit C###x, ω(=0, untuk memastikan sirkuit berfungsi dengan benar.
PermutationCheck: Memvalidasi apakah hasil evaluasi dari dua polinomial multivariat f dan g di hiperkubus Boolean merupakan hubungan permutasi f)x( = f)π(x(), untuk memastikan konsistensi pengaturan antara variabel polinomial.
LookupCheck: Memverifikasi apakah evaluasi polinomial berada dalam tabel lookup yang diberikan, yaitu f)Bµ( ⊆ T)Bµ(, memastikan beberapa nilai berada dalam rentang yang ditentukan.
MultisetCheck: Memeriksa apakah dua kumpulan multivariat sama, yaitu {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, menjamin konsistensi antar beberapa kumpulan.
ProductCheck: Memeriksa apakah evaluasi polinomial rasional pada hiperkubus Boolean sama dengan nilai yang dinyatakan ∏x∈Hµ f)x( = s, untuk memastikan kebenaran produk polinomial.
ZeroCheck: Memverifikasi apakah suatu polinomial multivariabel di hypercube Boolean pada titik mana pun adalah nol ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, untuk memastikan distribusi titik nol polinomial.
SumCheck: Memeriksa apakah jumlah dari polinomial multivariat sama dengan nilai yang dinyatakan ∑x∈Hµ f)x( = s. Dengan mengubah masalah evaluasi polinomial multivariat menjadi evaluasi polinomial univariat, mengurangi kompleksitas perhitungan pihak yang memverifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan angka acak, membangun kombinasi linier untuk menangani beberapa contoh pemeriksaan jumlah.
BatchCheck: Berdasarkan SumCheck, memverifikasi kebenaran evaluasi beberapa polinomial multivariat untuk meningkatkan efisiensi protokol.
Meskipun Binius dan HyperPlonk memiliki banyak kesamaan dalam desain protokol, Binius telah melakukan perbaikan dalam 3 hal berikut:
Optimasi ProductCheck: Dalam HyperPlonk, ProductCheck mengharuskan penyebut U tidak nol di seluruh hypercube, dan produk harus sama dengan nilai tertentu; Binius menyederhanakan proses pemeriksaan ini dengan mengkhususkan nilai tersebut menjadi 1, sehingga mengurangi kompleksitas perhitungan.
Penanganan masalah pembagian dengan nol: HyperPlonk tidak berhasil menangani situasi pembagian dengan nol, yang menyebabkan ketidakmampuan untuk memastikan bahwa U tidak nol di hiperkubus; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius dapat terus memproses, memungkinkan untuk memperluas ke nilai hasil kali mana pun.
PermutationCheck lintas kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung PermutationCheck di antara beberapa kolom, yang memungkinkan Binius untuk menangani situasi pengaturan polinomial yang lebih kompleks.
Oleh karena itu, Binius meningkatkan fleksibilitas dan efisiensi protokol melalui perbaikan pada mekanisme PIOPSumCheck yang ada, terutama dalam menangani verifikasi polinomial multivariat yang lebih kompleks, memberikan dukungan fungsional yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem pembuktian berbasis domain biner di masa depan.
) 2.3 PIOP: argumen pergeseran multilinear baru------cocok untuk hypercube boolean
Dalam protokol Binius, maya
Lihat Asli
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.
23 Suka
Hadiah
23
5
Bagikan
Komentar
0/400
zkProofInThePudding
· 07-18 00:38
Optimalkan STARKs sangat memperhatikan, setiap generasi lebih hemat.
Lihat AsliBalas0
MissedTheBoat
· 07-17 06:26
Sebuah lagi bukti nol pengetahuan yang tidak bisa dimengerti
Lihat AsliBalas0
LucidSleepwalker
· 07-17 06:23
Optimasi optimasi tetap optimasi 32bit juga terbuang sia-sia Para devs kali ini tidak bisa!
Lihat AsliBalas0
GateUser-00be86fc
· 07-17 06:23
Saya tidak mengerti, tetapi saya sangat terkejut!
Lihat AsliBalas0
BearMarketLightning
· 07-17 06:14
Efisiensinya setara dengan mobil tua tahun 32 yang melaju di jalan tol!
Binius STARKs: Sistem bukti nol pengetahuan yang efisien berbasis bidang biner
Analisis Prinsip Binius STARKs dan Pemikiran Optimasi
1 Pendahuluan
Salah satu alasan utama efisiensi STARKs yang rendah adalah: sebagian besar nilai dalam program nyata cukup kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dan sebagainya. Namun, untuk memastikan keamanan bukti berbasis pohon Merkle, ketika menggunakan pengkodean Reed-Solomon untuk memperluas data, banyak nilai redundan tambahan akan mengisi seluruh bidang, meskipun nilai asli itu sendiri sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran bidang menjadi strategi kunci.
Seperti yang ditunjukkan pada Tabel 1, lebar kode STARKs generasi pertama adalah 252bit, lebar kode STARKs generasi kedua adalah 64bit, lebar kode STARKs generasi ketiga adalah 32bit, tetapi lebar kode 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, bidang biner memungkinkan operasi langsung pada bit, pengkodean yang kompak dan efisien tanpa ruang yang terbuang, yaitu STARKs generasi keempat.
Tabel 1: Jalur Turunan STARKs
| Aljabar | Lebar Kode | Sistem Perwakilan | |------|----------|----------| | Generasi 1 | 252bit | StarkWare |
| Generasi ke-2 | 64bit | Plonky2 | | Generasi ke-3 | 32bit | BabyBear | | Generasi ke-4 | Domain Biner | Binius |
Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian baru-baru ini tentang bidang terbatas, penelitian bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah digunakan secara luas dalam kriptografi, contoh tipikal termasuk:
Standar Enkripsi Tingkat Lanjut (AES), berbasis bidang F28;
Kode Otentikasi Pesan Galois ( GMAC ), berdasarkan domain F2128;
Kode QR, menggunakan pengkodean Reed-Solomon berbasis F28;
Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk ke final SHA-3, yang berbasis pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursi.
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, tetapi cukup 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 dibutuhkan.
Ketika membangun sistem bukti berdasarkan domain biner, ada 2 masalah praktis: ukuran domain yang digunakan untuk menghitung representasi jejak dalam STARKs harus lebih besar dari derajat polinomial; saat melakukan komitmen pohon Merkle dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, dan ukuran domain yang digunakan harus lebih besar dari ukuran setelah pengkodean diperluas.
Binius mengajukan solusi inovatif untuk menangani kedua masalah tersebut, dan mewujudkannya dengan cara yang berbeda untuk merepresentasikan data yang sama: pertama, menggunakan multivariat ( yang secara khusus adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan merepresentasikan seluruh jejak perhitungan melalui nilai-nilainya di "hypercube" ( hypercubes ); kedua, karena panjang setiap dimensi hypercube adalah 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti pada STARKs, tetapi hypercube dapat dipandang sebagai persegi ( square ), dan perluasan Reed-Solomon dapat dilakukan berdasarkan persegi tersebut. Metode ini sangat meningkatkan efisiensi pengkodean dan kinerja komputasi sambil memastikan keamanan.
2 Analisis Prinsip
Konstruksi sebagian besar sistem SNARKs saat ini biasanya terdiri dari dua bagian berikut:
Teori informasi bukti orakel interaktif polinomial (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti dari sistem bukti, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Protokol PIOP yang berbeda memungkinkan penyedia bukti untuk mengirim polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah komputasi itu benar dengan menanyakan hasil evaluasi dari sejumlah kecil polinomial. Protokol PIOP yang ada termasuk: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara berbeda dalam menangani ekspresi polinomial, sehingga mempengaruhi kinerja dan efisiensi seluruh sistem SNARK.
Skema Janji Polinomial ( Polynomial Commitment Scheme, PCS ): Skema janji polinomial digunakan untuk membuktikan apakah kesetaraan polinomial yang dihasilkan oleh PIOP berlaku. PCS adalah alat kriptografi, melalui mana, pembuktian dapat berjanji pada suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain tentang polinomial. Skema janji polinomial yang umum digunakan adalah KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) dan Brakedown, dll. Berbagai PCS memiliki kinerja, keamanan, dan skenario penerapan yang berbeda.
Berdasarkan kebutuhan spesifik, pilih PIOP dan PCS yang berbeda, dan kombinasikan dengan bidang terbatas atau kurva elips yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Misalnya:
• Halo2: dikombinasikan dari PLONK PIOP dan Bulletproofs PCS, serta didasarkan pada kurva Pasta. Desain Halo2 berfokus pada skalabilitas dan menghilangkan trusted setup dalam protokol ZCash.
• Plonky2: Mengadopsi PLONK PIOP dan FRI PCS yang digabungkan, serta berdasarkan domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem-sistem ini, pilihan PIOP dan PCS yang digunakan harus sesuai dengan finite field atau kurva elips yang digunakan, untuk memastikan kebenaran, kinerja, dan keamanan sistem. Pilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti SNARK dan efisiensi verifikasi, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa pengaturan tepercaya, serta apakah dapat mendukung fungsi-fungsi tambahan seperti bukti rekursif atau bukti agregasi.
Binius: HyperPlonk PIOP + Brakedown PCS + binary field. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, aritmetika berbasis menara bidang biner (towers of binary fields) menjadi dasar perhitungan, yang mampu melakukan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol pembuktian Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol memperkenalkan sebuah pembuktian pergeseran multilinear baru, yang mengoptimalkan efisiensi dalam memverifikasi hubungan multilinear di bidang kecil. Keempat, Binius menggunakan versi yang ditingkatkan dari pembuktian pencarian Lasso, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), yang memungkinkannya untuk mencapai sistem pembuktian yang efisien di bidang biner, dan mengurangi biaya yang biasanya terkait dengan bidang besar.
2.1 Ruang Terbatas: Aritmetika berdasarkan menara bidang biner
Bidang biner bertingkat adalah kunci untuk mewujudkan komputasi yang dapat diverifikasi dengan cepat, terutama disebabkan oleh dua aspek: komputasi yang efisien dan aritmetika yang efisien. Bidang biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur bidang biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan pada bidang biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Karakteristik ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya fitur hierarkisnya melalui struktur bertingkat, menjadikan bidang biner sangat cocok untuk sistem bukti yang dapat diskalakan seperti Binius.
Di mana "canonical" merujuk pada representasi unik dan langsung dari elemen dalam bidang biner. Misalnya, dalam bidang biner paling dasar F2, string dengan k bit mana pun dapat langsung dipetakan ke elemen bidang biner dengan k bit. Ini berbeda dengan bidang prima, yang tidak dapat memberikan representasi normatif semacam itu dalam bit yang ditentukan. Meskipun bidang prima 32-bit dapat terkandung dalam 32 bit, tidak setiap string 32-bit dapat secara unik berhubungan dengan elemen bidang, sementara bidang biner memiliki kenyamanan pemetaan satu-ke-satu tersebut. Dalam bidang prima Fp, metode reduksi umum termasuk reduksi Barrett, reduksi Montgomery, serta metode reduksi khusus untuk bidang terbatas tertentu seperti Mersenne-31 atau Goldilocks-64. Dalam 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 ). Makalah "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" menunjukkan bahwa dalam bidang biner, operasi penjumlahan dan perkalian tidak perlu membawa, dan operasi kuadrat di bidang biner sangat efisien, karena mengikuti aturan penyederhanaan (X + Y )2 = X2 + Y 2.
Seperti yang ditunjukkan pada Gambar 1, sebuah string 128-bit: String ini dapat diinterpretasikan dalam berbagai cara dalam konteks domain biner. Ini 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 representasi ini tidak memerlukan biaya komputasi apa pun, hanya konversi tipe string bit (typecast), adalah atribut yang sangat menarik dan berguna. Pada saat yang sama, elemen domain kecil dapat dikemas menjadi elemen domain yang lebih besar tanpa memerlukan biaya komputasi tambahan. Protokol Binius memanfaatkan fitur ini untuk meningkatkan efisiensi komputasi. Selain itu, makalah "On Efficient Inversion in Tower Fields of Characteristic Two" membahas kompleksitas komputasi dari operasi perkalian, kuadrat, dan invers di domain tower biner n-bit yang dapat terurai menjadi subdomain m-bit (.
![Bitlayer Research: Analisis Prinsip Binius STARKs dan Pemikiran Optimisasinya])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: Versi Modifikasi HyperPlonk Product dan PermutationCheck------Cocok untuk bidang biner
Desain PIOP dalam protokol Binius mengadopsi HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan kumpulan multivariat. Pemeriksaan inti ini mencakup:
GateCheck: Verifikasi saksi rahasia ω dan input publik x apakah memenuhi hubungan operasi sirkuit C###x, ω(=0, untuk memastikan sirkuit berfungsi dengan benar.
PermutationCheck: Memvalidasi apakah hasil evaluasi dari dua polinomial multivariat f dan g di hiperkubus Boolean merupakan hubungan permutasi f)x( = f)π(x(), untuk memastikan konsistensi pengaturan antara variabel polinomial.
LookupCheck: Memverifikasi apakah evaluasi polinomial berada dalam tabel lookup yang diberikan, yaitu f)Bµ( ⊆ T)Bµ(, memastikan beberapa nilai berada dalam rentang yang ditentukan.
MultisetCheck: Memeriksa apakah dua kumpulan multivariat sama, yaitu {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, menjamin konsistensi antar beberapa kumpulan.
ProductCheck: Memeriksa apakah evaluasi polinomial rasional pada hiperkubus Boolean sama dengan nilai yang dinyatakan ∏x∈Hµ f)x( = s, untuk memastikan kebenaran produk polinomial.
ZeroCheck: Memverifikasi apakah suatu polinomial multivariabel di hypercube Boolean pada titik mana pun adalah nol ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, untuk memastikan distribusi titik nol polinomial.
SumCheck: Memeriksa apakah jumlah dari polinomial multivariat sama dengan nilai yang dinyatakan ∑x∈Hµ f)x( = s. Dengan mengubah masalah evaluasi polinomial multivariat menjadi evaluasi polinomial univariat, mengurangi kompleksitas perhitungan pihak yang memverifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan angka acak, membangun kombinasi linier untuk menangani beberapa contoh pemeriksaan jumlah.
BatchCheck: Berdasarkan SumCheck, memverifikasi kebenaran evaluasi beberapa polinomial multivariat untuk meningkatkan efisiensi protokol.
Meskipun Binius dan HyperPlonk memiliki banyak kesamaan dalam desain protokol, Binius telah melakukan perbaikan dalam 3 hal berikut:
Optimasi ProductCheck: Dalam HyperPlonk, ProductCheck mengharuskan penyebut U tidak nol di seluruh hypercube, dan produk harus sama dengan nilai tertentu; Binius menyederhanakan proses pemeriksaan ini dengan mengkhususkan nilai tersebut menjadi 1, sehingga mengurangi kompleksitas perhitungan.
Penanganan masalah pembagian dengan nol: HyperPlonk tidak berhasil menangani situasi pembagian dengan nol, yang menyebabkan ketidakmampuan untuk memastikan bahwa U tidak nol di hiperkubus; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius dapat terus memproses, memungkinkan untuk memperluas ke nilai hasil kali mana pun.
PermutationCheck lintas kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung PermutationCheck di antara beberapa kolom, yang memungkinkan Binius untuk menangani situasi pengaturan polinomial yang lebih kompleks.
Oleh karena itu, Binius meningkatkan fleksibilitas dan efisiensi protokol melalui perbaikan pada mekanisme PIOPSumCheck yang ada, terutama dalam menangani verifikasi polinomial multivariat yang lebih kompleks, memberikan dukungan fungsional yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem pembuktian berbasis domain biner di masa depan.
) 2.3 PIOP: argumen pergeseran multilinear baru------cocok untuk hypercube boolean
Dalam protokol Binius, maya