Analisis Prinsip Binius STARKs dan Pemikiran Optimisasinya
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 252 bit, lebar kode STARKs generasi kedua adalah 64 bit, dan lebar kode STARKs generasi ketiga adalah 32 bit, namun lebar kode 32 bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, bidang biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang terbuang, yaitu STARKs generasi keempat.
Dibandingkan dengan Goldilocks, BabyBear, Mersenne31, dan penelitian baru-baru ini tentang bidang terbatas, penelitian tentang bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah digunakan secara luas dalam kriptografi, contoh tipikalnya termasuk:
Standar Enkripsi Tingkat Lanjut (AES), berbasis pada domain F28;
Kode Autentikasi Pesan Galois ( GMAC ), berdasarkan bidang F2128;
Kode QR, menggunakan pengkodean Reed-Solomon berbasis F28;
Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk final SHA-3, yang didasarkan pada domain F28, merupakan algoritma hash yang sangat cocok untuk rekursi.
Ketika menggunakan domain yang lebih kecil, operasi perluasan domain semakin penting untuk memastikan keamanan. Domain biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan domain untuk menjamin keamanan dan kegunaannya yang sebenarnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam perluasan domain, tetapi cukup beroperasi di bawah domain dasar, sehingga mencapai efisiensi tinggi dalam domain kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu mendalami perluasan domain yang lebih besar, untuk memastikan keamanan yang diperlukan.
Saat membangun sistem bukti berdasarkan bidang biner, terdapat 2 masalah praktis: Dalam STARKs, saat menghitung representasi jejak, ukuran bidang yang digunakan harus lebih besar dari derajat polinomial; Dalam STARKs, saat melakukan komitmen Merkle tree, perlu dilakukan pengkodean Reed-Solomon, ukuran bidang yang digunakan harus lebih besar dari ukuran setelah pengkodean diperluas.
Binius mengajukan solusi inovatif yang menangani kedua masalah ini secara terpisah dan mewakili data yang sama dengan dua cara berbeda: pertama, dengan menggunakan multivariat ( yang secara khusus adalah polinomial multilinier ) sebagai pengganti polinomial univariat, yang mewakili seluruh lintasan komputasi melalui nilainya di "hypercube" ( hypercubes ); kedua, karena panjang setiap dimensi hypercube adalah 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti STARKs, tetapi hypercube dapat dipandang sebagai persegi ( square ), dan perluasan Reed-Solomon dilakukan berdasarkan persegi tersebut. Metode ini memastikan keamanan sambil secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.
2 Analisis Prinsip
Konstruk sistem SNARKs saat ini sebagian besar biasanya terdiri dari dua bagian berikut:
Teori informasi bukti interaktif polinomial oracle (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti sistem bukti, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Protokol PIOP yang berbeda memungkinkan penyiar untuk mengirimkan polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah perhitungan benar hanya dengan meng-query hasil evaluasi sejumlah kecil polinomial. Protokol PIOP yang ada antara lain: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara berbeda dalam menangani ekspresi polinomial, sehingga mempengaruhi kinerja dan efisiensi sistem SNARK secara keseluruhan.
Skema Komitmen Polinomial ( Polynomial Commitment Scheme, PCS ): Skema komitmen polinomial digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP benar. PCS adalah alat kriptografi, melalui mana, pembuktian dapat mengkomit suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain tentang polinomial. Skema komitmen polinomial yang umum termasuk KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) dan Brakedown, dll. Berbagai PCS memiliki kinerja, keamanan, dan skenario aplikasi yang berbeda.
Berdasarkan kebutuhan spesifik, pilih PIOP dan PCS yang berbeda, dan gabungkan dengan bidang terbatas atau kurva elips yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Contohnya:
• Halo2: dikombinasikan dari PLONK PIOP dan Bulletproofs PCS, dan didasarkan pada kurva Pasta. Halo2 dirancang dengan fokus pada skalabilitas, serta menghilangkan trusted setup dalam protokol ZCash.
• Plonky2: Mengadopsi PLONK PIOP dan FRI PCS yang digabungkan, dan berdasarkan domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem-sistem ini, PIOP dan PCS yang dipilih harus cocok dengan finite field atau kurva elips yang digunakan, untuk memastikan kebenaran, kinerja, dan keamanan sistem. Pemilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti SNARK dan efisiensi verifikasi, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa pengaturan yang dapat dipercaya, serta apakah dapat mendukung fitur-fitur tambahan seperti bukti rekursif atau bukti agregat.
Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, berdasarkan aritmetika bidang biner (towers of binary fields) yang membentuk dasar perhitungan, mampu melakukan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol pembuktian Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, memastikan konsistensi pemeriksaan yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol memperkenalkan pembuktian pergeseran multilinear baru, mengoptimalkan efisiensi verifikasi hubungan multilinear di bidang kecil. Keempat, Binius menggunakan pembuktian pencarian Lasso yang ditingkatkan, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), memungkinkannya untuk mencapai sistem pembuktian yang efisien di bidang biner, dan mengurangi biaya yang biasanya terkait dengan bidang besar.
2.1 Ruang Terbatas: Aritmetika berbasis menara bidang biner
Ruang biner bertingkat adalah kunci untuk mencapai perhitungan yang dapat diverifikasi dengan cepat, terutama karena dua alasan: perhitungan yang efisien dan aritmetika yang efisien. Ruang biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur ruang biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan di ruang biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya sifat hierarkis melalui struktur bertingkat, menjadikan ruang biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.
Di mana "canonical" merujuk pada cara representasi yang unik dan langsung dari elemen dalam bidang biner. Misalnya, dalam bidang biner dasar F2, string k-bit mana pun dapat dipetakan langsung ke elemen bidang biner k-bit. Ini berbeda dengan bidang bilangan prima, yang tidak dapat memberikan representasi standar seperti itu dalam jumlah bit tertentu. Meskipun bidang bilangan prima 32-bit dapat diwakili dalam 32-bit, tidak semua string 32-bit dapat secara unik dipetakan ke satu elemen bidang, sedangkan bidang biner memiliki kemudahan pemetaan satu-satu seperti itu. Dalam bidang bilangan prima Fp, metode reduksi yang umum meliputi reduksi Barrett, reduksi Montgomery, dan 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 operasi penjumlahan dan perkalian di bidang biner, tidak perlu memperkenalkan pembawa, dan operasi kuadrat di bidang biner sangat efisien, karena mengikuti aturan penyederhanaan (X + Y )2 = X2 + Y2.
Seperti yang ditunjukkan pada Gambar 1, sebuah string 128-bit: string ini dapat diinterpretasikan dalam konteks bidang biner dengan berbagai cara. Ini dapat dianggap sebagai elemen unik dalam bidang biner 128-bit, atau diuraikan menjadi dua elemen bidang tower 64-bit, empat elemen bidang tower 32-bit, enam belas elemen bidang tower 8-bit, atau seratus dua puluh delapan elemen bidang F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi tambahan, hanya konversi tipe string bit (typecast), yang merupakan atribut yang sangat menarik dan berguna. Pada saat yang sama, elemen bidang kecil dapat dikemas menjadi elemen bidang 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 dalam bidang tower biner n-bit yang dapat direduksi menjadi subbidang m-bit (.
) 2.2 PIOP: versi modifikasi HyperPlonk Product dan PermutationCheck------cocok untuk bidang biner
Desain PIOP dalam protokol Binius mengacu pada HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan kumpulan multivariat. Pemeriksaan inti ini meliputi:
GateCheck: Memverifikasi apakah saksi rahasia ω dan input publik x memenuhi hubungan operasi sirkuit C###x,ω(=0, untuk memastikan sirkuit berfungsi dengan benar.
PermutationCheck: Memverifikasi apakah hasil evaluasi dari dua polinomial multivariat f dan g di hiperkubus Boolean adalah hubungan permutasi f)x( = f)π(x(), untuk memastikan konsistensi penyusunan variabel polinomial.
LookupCheck: Memverifikasi apakah nilai polinomial berada dalam tabel pencarian yang diberikan, yaitu f)Bµ( ⊆ T)Bµ(, memastikan nilai-nilai tertentu berada dalam rentang yang ditentukan.
MultisetCheck: Memeriksa apakah dua himpunan multivariabel sama, yaitu {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, untuk menjamin konsistensi antar beberapa himpunan.
ProductCheck: Memeriksa apakah evaluasi polinomial rasional pada kubus hiper Boolean sama dengan nilai yang dinyatakan ∏x∈Hµ f)x( = s, untuk memastikan kebenaran produk polinomial.
ZeroCheck: Memverifikasi apakah polinomial multivariat pada hiperkubus Boolean di titik mana pun adalah nol ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, untuk memastikan distribusi titik nol polinomial.
SumCheck: Memeriksa apakah jumlah polinomial multivariat sama dengan nilai yang dinyatakan ∑x∈Hµ f)x( = s. Dengan mengubah masalah evaluasi polinomial multivariat menjadi evaluasi polinomial univariat, mengurangi kompleksitas komputasi pihak verifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan angka acak, membangun kombinasi linier untuk melakukan pemrosesan batch pada 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 aspek berikut:
Optimisasi ProductCheck: Di HyperPlonk, ProductCheck mengharuskan penyebut U tidak nol di semua titik pada hiperkubus, 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 dapat menangani situasi pembagian dengan nol dengan baik, yang menyebabkan ketidakmampuan untuk memastikan bahwa U tidak nol di hypercube; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius juga dapat terus memproses, memungkinkan untuk diperluas ke nilai produk apa pun.
Pemeriksaan Permutasi Lintas Kolom: HyperPlonk tidak memiliki fungsi ini; Binius mendukung pemeriksaan permutasi di antara beberapa kolom, yang memungkinkan Binius untuk menangani kasus susunan polinomial yang lebih kompleks.
Oleh karena itu, Binius telah meningkatkan fleksibilitas dan efisiensi protokol dengan memperbaiki mekanisme PIOPSumCheck yang ada, terutama dalam menangani verifikasi polinomial multivariat yang lebih kompleks, memberikan dukungan fungsionalitas yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem pembuktian yang berbasis pada domain biner di masa depan.
) 2.3 PIOP: argumen pergeseran multilinear baru------cocok untuk hypercube boolean
Dalam protokol Binius, konstruksi dan penanganan polinomial virtual adalah penting.
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.
11 Suka
Hadiah
11
6
Bagikan
Komentar
0/400
MissedTheBoat
· 4jam yang lalu
Kompak adalah jalan yang terbaik! Terjun bebas!
Lihat AsliBalas0
GasBandit
· 17jam yang lalu
Lalu bagaimana bisa terpikir untuk mengoptimalkan starks?
Lihat AsliBalas0
CryptoComedian
· 17jam yang lalu
Menulis makalah menekan lebar posisi, sudah ditulis tiga generasi tetapi belum memenuhi standar.
Lihat AsliBalas0
BlockchainThinkTank
· 17jam yang lalu
Kami percaya bahwa optimasi zkp masih berada pada tahap awal, dan perlu dengan hati-hati memandang solusi peningkatan efisiensi jenis proyek ini.
Lihat AsliBalas0
MentalWealthHarvester
· 18jam yang lalu
Ini adalah masa keemasan STARKs saya lagi, bisa挖掘 lagi.
Lihat AsliBalas0
LayoffMiner
· 18jam yang lalu
Apa yang dipikirkan, gas tidak bisa turun tapi masih dibuat sedemikian dalam.
Pemikiran baru untuk optimasi STARKs: Binius mendorong perkembangan domain biner
Analisis Prinsip Binius STARKs dan Pemikiran Optimisasinya
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 252 bit, lebar kode STARKs generasi kedua adalah 64 bit, dan lebar kode STARKs generasi ketiga adalah 32 bit, namun lebar kode 32 bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, bidang biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang terbuang, yaitu STARKs generasi keempat.
| Waktu | STARKs | Lebar Kode | |------|--------|----------| | 2018 | Generasi Pertama | 252bit | | 2021 | Generasi ke-2 | 64bit | | 2022 | Generasi ke-3 | 32bit | | 2023 | Generasi ke-4 | 1bit |
Tabel 1: Jalur Turunan STARKs
Dibandingkan dengan Goldilocks, BabyBear, Mersenne31, dan penelitian baru-baru ini tentang bidang terbatas, penelitian tentang bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah digunakan secara luas dalam kriptografi, contoh tipikalnya termasuk:
Standar Enkripsi Tingkat Lanjut (AES), berbasis pada domain F28;
Kode Autentikasi Pesan Galois ( GMAC ), berdasarkan bidang F2128;
Kode QR, menggunakan pengkodean Reed-Solomon berbasis F28;
Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk final SHA-3, yang didasarkan pada domain F28, merupakan algoritma hash yang sangat cocok untuk rekursi.
Ketika menggunakan domain yang lebih kecil, operasi perluasan domain semakin penting untuk memastikan keamanan. Domain biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan domain untuk menjamin keamanan dan kegunaannya yang sebenarnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam perluasan domain, tetapi cukup beroperasi di bawah domain dasar, sehingga mencapai efisiensi tinggi dalam domain kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu mendalami perluasan domain yang lebih besar, untuk memastikan keamanan yang diperlukan.
Saat membangun sistem bukti berdasarkan bidang biner, terdapat 2 masalah praktis: Dalam STARKs, saat menghitung representasi jejak, ukuran bidang yang digunakan harus lebih besar dari derajat polinomial; Dalam STARKs, saat melakukan komitmen Merkle tree, perlu dilakukan pengkodean Reed-Solomon, ukuran bidang yang digunakan harus lebih besar dari ukuran setelah pengkodean diperluas.
Binius mengajukan solusi inovatif yang menangani kedua masalah ini secara terpisah dan mewakili data yang sama dengan dua cara berbeda: pertama, dengan menggunakan multivariat ( yang secara khusus adalah polinomial multilinier ) sebagai pengganti polinomial univariat, yang mewakili seluruh lintasan komputasi melalui nilainya di "hypercube" ( hypercubes ); kedua, karena panjang setiap dimensi hypercube adalah 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti STARKs, tetapi hypercube dapat dipandang sebagai persegi ( square ), dan perluasan Reed-Solomon dilakukan berdasarkan persegi tersebut. Metode ini memastikan keamanan sambil secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.
2 Analisis Prinsip
Konstruk sistem SNARKs saat ini sebagian besar biasanya terdiri dari dua bagian berikut:
Teori informasi bukti interaktif polinomial oracle (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti sistem bukti, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Protokol PIOP yang berbeda memungkinkan penyiar untuk mengirimkan polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah perhitungan benar hanya dengan meng-query hasil evaluasi sejumlah kecil polinomial. Protokol PIOP yang ada antara lain: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara berbeda dalam menangani ekspresi polinomial, sehingga mempengaruhi kinerja dan efisiensi sistem SNARK secara keseluruhan.
Skema Komitmen Polinomial ( Polynomial Commitment Scheme, PCS ): Skema komitmen polinomial digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP benar. PCS adalah alat kriptografi, melalui mana, pembuktian dapat mengkomit suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain tentang polinomial. Skema komitmen polinomial yang umum termasuk KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) dan Brakedown, dll. Berbagai PCS memiliki kinerja, keamanan, dan skenario aplikasi yang berbeda.
Berdasarkan kebutuhan spesifik, pilih PIOP dan PCS yang berbeda, dan gabungkan dengan bidang terbatas atau kurva elips yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Contohnya:
• Halo2: dikombinasikan dari PLONK PIOP dan Bulletproofs PCS, dan didasarkan pada kurva Pasta. Halo2 dirancang dengan fokus pada skalabilitas, serta menghilangkan trusted setup dalam protokol ZCash.
• Plonky2: Mengadopsi PLONK PIOP dan FRI PCS yang digabungkan, dan berdasarkan domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem-sistem ini, PIOP dan PCS yang dipilih harus cocok dengan finite field atau kurva elips yang digunakan, untuk memastikan kebenaran, kinerja, dan keamanan sistem. Pemilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti SNARK dan efisiensi verifikasi, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa pengaturan yang dapat dipercaya, serta apakah dapat mendukung fitur-fitur tambahan seperti bukti rekursif atau bukti agregat.
Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, berdasarkan aritmetika bidang biner (towers of binary fields) yang membentuk dasar perhitungan, mampu melakukan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol pembuktian Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, memastikan konsistensi pemeriksaan yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol memperkenalkan pembuktian pergeseran multilinear baru, mengoptimalkan efisiensi verifikasi hubungan multilinear di bidang kecil. Keempat, Binius menggunakan pembuktian pencarian Lasso yang ditingkatkan, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), memungkinkannya untuk mencapai sistem pembuktian yang efisien di bidang biner, dan mengurangi biaya yang biasanya terkait dengan bidang besar.
2.1 Ruang Terbatas: Aritmetika berbasis menara bidang biner
Ruang biner bertingkat adalah kunci untuk mencapai perhitungan yang dapat diverifikasi dengan cepat, terutama karena dua alasan: perhitungan yang efisien dan aritmetika yang efisien. Ruang biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur ruang biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan di ruang biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya sifat hierarkis melalui struktur bertingkat, menjadikan ruang biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.
Di mana "canonical" merujuk pada cara representasi yang unik dan langsung dari elemen dalam bidang biner. Misalnya, dalam bidang biner dasar F2, string k-bit mana pun dapat dipetakan langsung ke elemen bidang biner k-bit. Ini berbeda dengan bidang bilangan prima, yang tidak dapat memberikan representasi standar seperti itu dalam jumlah bit tertentu. Meskipun bidang bilangan prima 32-bit dapat diwakili dalam 32-bit, tidak semua string 32-bit dapat secara unik dipetakan ke satu elemen bidang, sedangkan bidang biner memiliki kemudahan pemetaan satu-satu seperti itu. Dalam bidang bilangan prima Fp, metode reduksi yang umum meliputi reduksi Barrett, reduksi Montgomery, dan 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 operasi penjumlahan dan perkalian di bidang biner, tidak perlu memperkenalkan pembawa, dan operasi kuadrat di bidang biner sangat efisien, karena mengikuti aturan penyederhanaan (X + Y )2 = X2 + Y2.
Seperti yang ditunjukkan pada Gambar 1, sebuah string 128-bit: string ini dapat diinterpretasikan dalam konteks bidang biner dengan berbagai cara. Ini dapat dianggap sebagai elemen unik dalam bidang biner 128-bit, atau diuraikan menjadi dua elemen bidang tower 64-bit, empat elemen bidang tower 32-bit, enam belas elemen bidang tower 8-bit, atau seratus dua puluh delapan elemen bidang F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi tambahan, hanya konversi tipe string bit (typecast), yang merupakan atribut yang sangat menarik dan berguna. Pada saat yang sama, elemen bidang kecil dapat dikemas menjadi elemen bidang 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 dalam bidang tower biner n-bit yang dapat direduksi menjadi subbidang m-bit (.
![塔式二进制域])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(
Gambar 1: Domain Biner Bertingkat
) 2.2 PIOP: versi modifikasi HyperPlonk Product dan PermutationCheck------cocok untuk bidang biner
Desain PIOP dalam protokol Binius mengacu pada HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan kumpulan multivariat. Pemeriksaan inti ini meliputi:
GateCheck: Memverifikasi apakah saksi rahasia ω dan input publik x memenuhi hubungan operasi sirkuit C###x,ω(=0, untuk memastikan sirkuit berfungsi dengan benar.
PermutationCheck: Memverifikasi apakah hasil evaluasi dari dua polinomial multivariat f dan g di hiperkubus Boolean adalah hubungan permutasi f)x( = f)π(x(), untuk memastikan konsistensi penyusunan variabel polinomial.
LookupCheck: Memverifikasi apakah nilai polinomial berada dalam tabel pencarian yang diberikan, yaitu f)Bµ( ⊆ T)Bµ(, memastikan nilai-nilai tertentu berada dalam rentang yang ditentukan.
MultisetCheck: Memeriksa apakah dua himpunan multivariabel sama, yaitu {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, untuk menjamin konsistensi antar beberapa himpunan.
ProductCheck: Memeriksa apakah evaluasi polinomial rasional pada kubus hiper Boolean sama dengan nilai yang dinyatakan ∏x∈Hµ f)x( = s, untuk memastikan kebenaran produk polinomial.
ZeroCheck: Memverifikasi apakah polinomial multivariat pada hiperkubus Boolean di titik mana pun adalah nol ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, untuk memastikan distribusi titik nol polinomial.
SumCheck: Memeriksa apakah jumlah polinomial multivariat sama dengan nilai yang dinyatakan ∑x∈Hµ f)x( = s. Dengan mengubah masalah evaluasi polinomial multivariat menjadi evaluasi polinomial univariat, mengurangi kompleksitas komputasi pihak verifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan angka acak, membangun kombinasi linier untuk melakukan pemrosesan batch pada 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 aspek berikut:
Optimisasi ProductCheck: Di HyperPlonk, ProductCheck mengharuskan penyebut U tidak nol di semua titik pada hiperkubus, 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 dapat menangani situasi pembagian dengan nol dengan baik, yang menyebabkan ketidakmampuan untuk memastikan bahwa U tidak nol di hypercube; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius juga dapat terus memproses, memungkinkan untuk diperluas ke nilai produk apa pun.
Pemeriksaan Permutasi Lintas Kolom: HyperPlonk tidak memiliki fungsi ini; Binius mendukung pemeriksaan permutasi di antara beberapa kolom, yang memungkinkan Binius untuk menangani kasus susunan polinomial yang lebih kompleks.
Oleh karena itu, Binius telah meningkatkan fleksibilitas dan efisiensi protokol dengan memperbaiki mekanisme PIOPSumCheck yang ada, terutama dalam menangani verifikasi polinomial multivariat yang lebih kompleks, memberikan dukungan fungsionalitas yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem pembuktian yang berbasis pada domain biner di masa depan.
) 2.3 PIOP: argumen pergeseran multilinear baru------cocok untuk hypercube boolean
Dalam protokol Binius, konstruksi dan penanganan polinomial virtual adalah penting.