Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi
1 Pendahuluan
Berbeda dengan SNARKs yang didasarkan pada kurva elips, STARKs dapat dianggap sebagai SNARKs yang berbasis hash. Salah satu alasan utama mengapa STARKs saat ini tidak efisien adalah: sebagian besar nilai dalam program nyata cukup kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dan sebagainya. Namun, untuk memastikan keamanan bukti yang berbasis pohon Merkle, saat menggunakan pengkodean Reed-Solomon untuk memperluas data, banyak nilai redundan tambahan akan mengisi seluruh domain, bahkan jika nilai asli itu sendiri sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.
Seperti yang ditunjukkan pada Tabel 1, lebar encoding STARKs generasi pertama adalah 252bit, lebar encoding STARKs generasi kedua adalah 64bit, lebar encoding STARKs generasi ketiga adalah 32bit, tetapi lebar encoding 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, dengan encoding yang padat dan efisien tanpa ruang yang terbuang, yaitu STARKs generasi keempat.
Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian baru-baru ini lainnya tentang bidang terbatas, penelitian tentang bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah secara luas diterapkan dalam kriptografi, contoh tipikal termasuk:
Standar Enkripsi Tingkat Lanjut (AES), berbasis pada domain F28
Kode otentikasi pesan Galois ( GMAC ), berbasis pada 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 berbasis pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursi.
Ketika menggunakan bidang yang lebih kecil, operasi perluasan semakin penting untuk memastikan keamanan. Bidang 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 memasuki perluasan, tetapi cukup beroperasi di bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu masuk ke dalam perluasan yang lebih besar untuk memastikan keamanan yang diperlukan.
Ada 2 masalah praktis dalam membangun sistem bukti berdasarkan domain biner: Ketika menghitung representasi trace dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; Ketika melakukan komitmen Merkle tree dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, dan ukuran domain yang digunakan harus lebih besar dari ukuran setelah pengkodean diperluas.
Binius mengusulkan solusi inovatif untuk menangani kedua masalah ini secara terpisah, dan mewakili data yang sama dengan dua cara berbeda: pertama, menggunakan polinomial multivariat ( yang khususnya adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan mewakili seluruh jalur perhitungan melalui nilai-nilainya pada "hypercube" ( hypercubes ); kedua, karena setiap dimensi hypercube memiliki panjang 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti STARKs, tetapi hypercube dapat dipandang sebagai persegi ( square ), dan perluasan Reed-Solomon dapat dilakukan berdasarkan persegi tersebut. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.
2 Analisis Prinsip
Konstruksi sebagian besar sistem SNARKs saat ini biasanya terdiri dari dua bagian berikut:
Teorema informasi bukti interaktif polinomial (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti sistem bukti, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan penyaji untuk mengirimkan polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah perhitungan benar hanya dengan meminta hasil evaluasi sejumlah kecil polinomial. Protokol PIOP yang ada termasuk: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara penanganan ekspresi polinomial yang berbeda, sehingga mempengaruhi kinerja dan efisiensi seluruh sistem SNARK.
Skema Komitmen Polin ( Polynomial Commitment Scheme, PCS ): Skema komitmen polin digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP benar. PCS adalah alat kriptografi, melalui ini, penjamin dapat mengkomit sebuah polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain tentang polinomial. Skema komitmen polin yang umum digunakan termasuk KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) dan Brakedown. Berbagai PCS memiliki kinerja, keamanan, dan skenario aplikasi yang berbeda.
Berdasarkan kebutuhan spesifik, pilih PIOP dan PCS yang berbeda, dan padukan dengan domain terbatas atau kurva elips yang sesuai, dapat membangun sistem pembuktian dengan atribut yang berbeda. Contohnya:
• Halo2: dikombinasikan dari PLONK PIOP dan Bulletproofs PCS, dan berdasarkan kurva Pasta. Halo2 dirancang dengan fokus pada skalabilitas, serta menghilangkan trusted setup dalam protokol ZCash.
• Plonky2: Mengadopsi PLONK PIOP dan FRI PCS yang dikombinasikan, serta didasarkan pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem ini, PIOP dan PCS yang dipilih harus cocok dengan bidang hingga 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 yang dapat dipercaya, serta apakah dapat mendukung fungsi tambahan seperti bukti rekursif atau bukti agregasi.
Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara spesifik, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, aritmetika yang didasarkan pada menara bidang biner (towers of binary fields) membentuk dasar perhitungannya, yang dapat melakukan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol bukti Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol memperkenalkan bukti pergeseran multilinear baru, yang mengoptimalkan efisiensi verifikasi hubungan multilinear pada bidang kecil. Keempat, Binius menggunakan bukti pencarian Lasso yang ditingkatkan, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), memungkinkan untuk membangun sistem bukti yang efisien di bidang biner, dan mengurangi biaya yang biasanya terkait dengan bidang besar.
2.1 Ruang Terbatas: Aritmetisasi berdasarkan menara bidang biner
Domain biner bertower adalah kunci untuk mencapai komputasi yang cepat dan dapat diverifikasi, terutama karena dua aspek: komputasi yang efisien dan aritmatika yang efisien. Domain biner pada dasarnya mendukung operasi aritmatika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur domain biner mendukung proses aritmatika yang disederhanakan, yaitu operasi yang dilakukan di atas domain biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur menara, menjadikan domain biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.
"Canonical" merujuk pada cara representasi elemen yang unik dan langsung dalam domain biner. Misalnya, dalam domain biner paling dasar F2, string dengan k bit dapat langsung dipetakan ke elemen domain biner dengan k bit. Ini berbeda dengan domain bilangan prima, di mana domain bilangan prima tidak dapat memberikan representasi standar dalam jumlah bit tertentu. Meskipun domain bilangan prima 32 bit dapat dimasukkan dalam 32 bit, tidak setiap string 32 bit dapat secara unik sesuai dengan elemen domain, sedangkan domain biner memiliki kenyamanan pemetaan satu-ke-satu ini. Dalam domain bilangan prima Fp, metode reduksi yang umum termasuk reduksi Barrett, reduksi Montgomery, serta metode reduksi khusus untuk domain terbatas tertentu seperti Mersenne-31 atau Goldilocks-64. Dalam domain 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 domain biner, tidak perlu memperkenalkan carry, dan operasi kuadrat di domain 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 dengan berbagai cara dalam konteks domain biner. Ini dapat dianggap sebagai elemen unik dalam domain biner 128-bit, atau diuraikan menjadi dua elemen domain tower 64-bit, empat elemen domain tower 32-bit, 16 elemen domain tower 8-bit, atau 128 elemen domain F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi tambahan, hanya konversi tipe string bit (typecast), yang merupakan atribut yang sangat menarik dan berguna. Selain itu, 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 untuk perkalian, kuadrat, dan operasi invers dalam domain tower biner n-bit yang dapat diuraikan menjadi subdomain m-bit (.
) 2.2 PIOP: Versi Adaptasi Produk HyperPlonk dan PermutationCheck------Cocok untuk domain biner
Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan sekumpulan variabel. Pemeriksaan inti ini meliputi:
GateCheck: Memverifikasi apakah saksi rahasia ω dan input publik x memenuhi hubungan operasi sirkuit C###x,ω(=0, untuk memastikan sirkuit berjalan 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 penataan antar variabel polinomial.
LookupCheck: Memverifikasi apakah nilai polinomial ada dalam tabel pencarian 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 hiper kubus Boolean sama dengan nilai yang dinyatakan ∏x∈Hµ f)x( = s, untuk memastikan kebenaran produk polinomial.
ZeroCheck: Memverifikasi apakah polinomial multivariabel pada hiper kubus Boolean di 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 multivariabel menjadi evaluasi polinomial univariat, mengurangi kompleksitas komputasi untuk pihak yang memverifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan bilangan acak, membangun kombinasi linear untuk menangani beberapa contoh verifikasi 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:
Optimasi ProductCheck: Dalam HyperPlonk, ProductCheck mengharuskan penyebut U tidak boleh nol di semua titik pada 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 dapat menangani situasi pembagian dengan nol dengan baik, menyebabkan ketidakmampuan untuk menyatakan masalah non-nol U di hypercube; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya nol, ProductCheck Binius dapat terus beroperasi, memungkinkan perluasan ke nilai produk mana pun.
Cek Permutasi Lintas Kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung Cek Permutasi 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 multivariabel yang lebih kompleks, memberikan dukungan fungsional yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem bukti berbasis bidang biner di masa depan.
) 2.3 PIOP: argumen pergeseran multilinear baru------cocok untuk hypercube boolean
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.
17 Suka
Hadiah
17
8
Bagikan
Komentar
0/400
SigmaBrain
· 07-07 02:10
Terlalu mendalam, tidak bisa dipahami dengan baik...
Lihat AsliBalas0
MetaMuskRat
· 07-06 12:34
Ini terlalu rumit, saya tidak mengerti
Lihat AsliBalas0
SerumSurfer
· 07-05 14:39
Kebaikan dihargai
Lihat AsliBalas0
WagmiOrRekt
· 07-04 02:50
Jujur saja, lebih baik langsung menggunakan web2 murni.
Inovasi Binius STARKs: Optimasi domain biner untuk meningkatkan efisiensi dan keamanan
Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi
1 Pendahuluan
Berbeda dengan SNARKs yang didasarkan pada kurva elips, STARKs dapat dianggap sebagai SNARKs yang berbasis hash. Salah satu alasan utama mengapa STARKs saat ini tidak efisien adalah: sebagian besar nilai dalam program nyata cukup kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dan sebagainya. Namun, untuk memastikan keamanan bukti yang berbasis pohon Merkle, saat menggunakan pengkodean Reed-Solomon untuk memperluas data, banyak nilai redundan tambahan akan mengisi seluruh domain, bahkan jika nilai asli itu sendiri sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.
Seperti yang ditunjukkan pada Tabel 1, lebar encoding STARKs generasi pertama adalah 252bit, lebar encoding STARKs generasi kedua adalah 64bit, lebar encoding STARKs generasi ketiga adalah 32bit, tetapi lebar encoding 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, dengan encoding yang padat dan efisien tanpa ruang yang terbuang, yaitu STARKs generasi keempat.
Tabel 1: Jalur Derivatif STARKs
| Aljabar | Lebar Bit | Perwakilan | |------|------|------| | Generasi 1 | 252bit | StarkWare |
| Generasi 2 | 64bit | Plonky2 | | Generasi ke-3 | 32bit | BabyBear | | Generasi ke-4 | 1bit | Binius |
Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian baru-baru ini lainnya tentang bidang terbatas, penelitian tentang bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah secara luas diterapkan dalam kriptografi, contoh tipikal termasuk:
Ketika menggunakan bidang yang lebih kecil, operasi perluasan semakin penting untuk memastikan keamanan. Bidang 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 memasuki perluasan, tetapi cukup beroperasi di bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu masuk ke dalam perluasan yang lebih besar untuk memastikan keamanan yang diperlukan.
Ada 2 masalah praktis dalam membangun sistem bukti berdasarkan domain biner: Ketika menghitung representasi trace dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; Ketika melakukan komitmen Merkle tree dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, dan ukuran domain yang digunakan harus lebih besar dari ukuran setelah pengkodean diperluas.
Binius mengusulkan solusi inovatif untuk menangani kedua masalah ini secara terpisah, dan mewakili data yang sama dengan dua cara berbeda: pertama, menggunakan polinomial multivariat ( yang khususnya adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan mewakili seluruh jalur perhitungan melalui nilai-nilainya pada "hypercube" ( hypercubes ); kedua, karena setiap dimensi hypercube memiliki panjang 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti STARKs, tetapi hypercube dapat dipandang sebagai persegi ( square ), dan perluasan Reed-Solomon dapat dilakukan berdasarkan persegi tersebut. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.
2 Analisis Prinsip
Konstruksi sebagian besar sistem SNARKs saat ini biasanya terdiri dari dua bagian berikut:
Teorema informasi bukti interaktif polinomial (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti sistem bukti, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan penyaji untuk mengirimkan polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah perhitungan benar hanya dengan meminta hasil evaluasi sejumlah kecil polinomial. Protokol PIOP yang ada termasuk: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara penanganan ekspresi polinomial yang berbeda, sehingga mempengaruhi kinerja dan efisiensi seluruh sistem SNARK.
Skema Komitmen Polin ( Polynomial Commitment Scheme, PCS ): Skema komitmen polin digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP benar. PCS adalah alat kriptografi, melalui ini, penjamin dapat mengkomit sebuah polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain tentang polinomial. Skema komitmen polin yang umum digunakan termasuk KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) dan Brakedown. Berbagai PCS memiliki kinerja, keamanan, dan skenario aplikasi yang berbeda.
Berdasarkan kebutuhan spesifik, pilih PIOP dan PCS yang berbeda, dan padukan dengan domain terbatas atau kurva elips yang sesuai, dapat membangun sistem pembuktian dengan atribut yang berbeda. Contohnya:
• Halo2: dikombinasikan dari PLONK PIOP dan Bulletproofs PCS, dan berdasarkan kurva Pasta. Halo2 dirancang dengan fokus pada skalabilitas, serta menghilangkan trusted setup dalam protokol ZCash.
• Plonky2: Mengadopsi PLONK PIOP dan FRI PCS yang dikombinasikan, serta didasarkan pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem ini, PIOP dan PCS yang dipilih harus cocok dengan bidang hingga 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 yang dapat dipercaya, serta apakah dapat mendukung fungsi tambahan seperti bukti rekursif atau bukti agregasi.
Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara spesifik, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, aritmetika yang didasarkan pada menara bidang biner (towers of binary fields) membentuk dasar perhitungannya, yang dapat melakukan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol bukti Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol memperkenalkan bukti pergeseran multilinear baru, yang mengoptimalkan efisiensi verifikasi hubungan multilinear pada bidang kecil. Keempat, Binius menggunakan bukti pencarian Lasso yang ditingkatkan, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), memungkinkan untuk membangun sistem bukti yang efisien di bidang biner, dan mengurangi biaya yang biasanya terkait dengan bidang besar.
2.1 Ruang Terbatas: Aritmetisasi berdasarkan menara bidang biner
Domain biner bertower adalah kunci untuk mencapai komputasi yang cepat dan dapat diverifikasi, terutama karena dua aspek: komputasi yang efisien dan aritmatika yang efisien. Domain biner pada dasarnya mendukung operasi aritmatika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur domain biner mendukung proses aritmatika yang disederhanakan, yaitu operasi yang dilakukan di atas domain biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur menara, menjadikan domain biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.
"Canonical" merujuk pada cara representasi elemen yang unik dan langsung dalam domain biner. Misalnya, dalam domain biner paling dasar F2, string dengan k bit dapat langsung dipetakan ke elemen domain biner dengan k bit. Ini berbeda dengan domain bilangan prima, di mana domain bilangan prima tidak dapat memberikan representasi standar dalam jumlah bit tertentu. Meskipun domain bilangan prima 32 bit dapat dimasukkan dalam 32 bit, tidak setiap string 32 bit dapat secara unik sesuai dengan elemen domain, sedangkan domain biner memiliki kenyamanan pemetaan satu-ke-satu ini. Dalam domain bilangan prima Fp, metode reduksi yang umum termasuk reduksi Barrett, reduksi Montgomery, serta metode reduksi khusus untuk domain terbatas tertentu seperti Mersenne-31 atau Goldilocks-64. Dalam domain 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 domain biner, tidak perlu memperkenalkan carry, dan operasi kuadrat di domain 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 dengan berbagai cara dalam konteks domain biner. Ini dapat dianggap sebagai elemen unik dalam domain biner 128-bit, atau diuraikan menjadi dua elemen domain tower 64-bit, empat elemen domain tower 32-bit, 16 elemen domain tower 8-bit, atau 128 elemen domain F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi tambahan, hanya konversi tipe string bit (typecast), yang merupakan atribut yang sangat menarik dan berguna. Selain itu, 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 untuk perkalian, kuadrat, dan operasi invers dalam domain tower biner n-bit yang dapat diuraikan menjadi subdomain m-bit (.
) 2.2 PIOP: Versi Adaptasi Produk HyperPlonk dan PermutationCheck------Cocok untuk domain biner
Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan sekumpulan variabel. Pemeriksaan inti ini meliputi:
GateCheck: Memverifikasi apakah saksi rahasia ω dan input publik x memenuhi hubungan operasi sirkuit C###x,ω(=0, untuk memastikan sirkuit berjalan 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 penataan antar variabel polinomial.
LookupCheck: Memverifikasi apakah nilai polinomial ada dalam tabel pencarian 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 hiper kubus Boolean sama dengan nilai yang dinyatakan ∏x∈Hµ f)x( = s, untuk memastikan kebenaran produk polinomial.
ZeroCheck: Memverifikasi apakah polinomial multivariabel pada hiper kubus Boolean di 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 multivariabel menjadi evaluasi polinomial univariat, mengurangi kompleksitas komputasi untuk pihak yang memverifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan bilangan acak, membangun kombinasi linear untuk menangani beberapa contoh verifikasi 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:
Optimasi ProductCheck: Dalam HyperPlonk, ProductCheck mengharuskan penyebut U tidak boleh nol di semua titik pada 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 dapat menangani situasi pembagian dengan nol dengan baik, menyebabkan ketidakmampuan untuk menyatakan masalah non-nol U di hypercube; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya nol, ProductCheck Binius dapat terus beroperasi, memungkinkan perluasan ke nilai produk mana pun.
Cek Permutasi Lintas Kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung Cek Permutasi 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 multivariabel yang lebih kompleks, memberikan dukungan fungsional yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem bukti berbasis bidang biner di masa depan.
) 2.3 PIOP: argumen pergeseran multilinear baru------cocok untuk hypercube boolean