Analisis Prinsip Binius STARKs dan Pemikiran Optimisasinya
1. Pendahuluan
Berbeda dengan SNARKs yang berbasis kurva elips, STARKs dapat dianggap sebagai SNARKs yang berbasis hash. Salah satu alasan utama mengapa efisiensi STARKs saat ini rendah adalah: sebagian besar nilai dalam program sebenarnya cukup kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dan lain-lain. Namun, untuk memastikan keamanan bukti berbasis pohon Merkle, saat melakukan ekstensi data menggunakan pengkodean Reed-Solomon, banyak nilai redundan tambahan akan mengisi seluruh domain, meskipun nilai aslinya sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.
Generasi 1 STARKs memiliki lebar kode 252bit, generasi 2 STARKs memiliki lebar kode 64bit, generasi 3 STARKs memiliki lebar kode 32bit, tetapi lebar kode 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, bidang biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang yang terbuang, yaitu generasi 4 STARKs.
Jika dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian terbaru tentang bidang terbatas dalam beberapa tahun terakhir, penelitian tentang bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah banyak digunakan dalam kriptografi, contoh tipikalnya termasuk:
Standar Enkripsi Tingkat Lanjut ( AES ), berbasis pada domain F28;
Kode otentikasi 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 ke final SHA-3, yang didasarkan pada domain F28, adalah algoritma hash yang sangat cocok untuk rekurensi.
Ketika menggunakan domain yang lebih kecil, operasi perluasan domain menjadi semakin penting untuk memastikan keamanan. Domain biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan domain untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu memasuki perluasan domain, melainkan 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.
Ketika membangun sistem bukti berdasarkan bidang biner, terdapat 2 masalah praktis: ukuran bidang yang digunakan saat menghitung representasi trace dalam STARKs harus lebih besar dari derajat polinomial; saat melakukan komitmen Merkle tree dalam STARKs, diperlukan pengkodean Reed-Solomon, dan 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, menggunakan multivariat ( yang secara khusus adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan mewakili seluruh jejak komputasi 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 dianggap 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
Sebagian besar sistem SNARK saat ini biasanya terdiri dari dua bagian berikut:
Teori informasi bukti interaktif polinomial oracle (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti dari sistem bukti, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan penyaji untuk secara bertahap mengirimkan polinomial melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah perhitungan tersebut benar hanya 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 yang berbeda dalam menangani ekspresi polinomial, sehingga memengaruhi kinerja dan efisiensi keseluruhan sistem SNARK.
Skema Komitmen Polinomial (Polynomial Commitment Scheme, PCS): Skema komitmen polinomial digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP valid. PCS adalah alat kriptografi, melalui yang mana, pembuktian dapat mengkomit suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sekaligus menyembunyikan informasi lain tentang polinomial itu. Skema komitmen polinomial yang umum meliputi KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) dan Brakedown. Berbagai PCS memiliki performa, keamanan, dan skenario aplikasi yang berbeda.
Berdasarkan kebutuhan spesifik, pilih PIOP dan PCS yang berbeda, dan kombinasikan dengan domain terbatas atau kurva elips yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Contohnya:
• Halo2: Menggabungkan PLONK PIOP dan Bulletproofs PCS, serta berdasarkan kurva Pasta. Saat merancang Halo2, fokus pada skalabilitas dan menghilangkan trusted setup dalam protokol ZCash.
• Plonky2: mengadopsi PLONK PIOP dan FRI PCS yang dipadukan, serta berbasis pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekurensi 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. 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 fungsi ekspansi seperti bukti rekurensi atau bukti agregasi.
Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, aritmetika yang dibangun di atas menara bidang biner (towers of binary fields) menjadi dasar perhitungan, memungkinkan 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 ini 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 ini menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), memungkinkan sistem pembuktian yang efisien di bidang biner, dan mengurangi biaya yang biasanya terkait dengan bidang besar.
2.1 Ruang terbatas: aritmetika berbasis towers of binary fields
Domain biner bertingkat adalah kunci untuk mewujudkan perhitungan yang cepat dan dapat diverifikasi, 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. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur bertingkat, menjadikan domain biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.
Di mana "canonical" merujuk pada cara unik dan langsung untuk merepresentasikan elemen dalam domain biner. Misalnya, dalam domain biner paling dasar F2, string k-bit mana pun dapat langsung dipetakan ke elemen domain biner k-bit. Ini berbeda dengan domain bilangan prima, yang tidak dapat memberikan representasi standar seperti itu dalam jumlah bit yang ditentukan. 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 kemudahan 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 ( yang digunakan dalam AES ), reduksi Montgomery ( 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 domain biner tidak perlu memperkenalkan carry dalam operasi penjumlahan dan perkalian, dan operasi kuadrat dalam 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 dalam berbagai cara dalam konteks domain biner. Itu dapat dianggap sebagai elemen unik dalam domain biner 128 bit, atau dipecahkan 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 operasi perkalian, kuadrat, dan invers dalam domain biner tower n bit ( yang dapat dipecah menjadi subdomain m bit ).
2.2 PIOP: Versi Adaptasi HyperPlonk Product dan PermutationCheck------Cocok untuk domain biner
Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi keakuratan polinomial dan kumpulan multivariat. Mekanisme pemeriksaan inti ini mencakup:
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 relasi permutasi f(x) = f(π(x)), untuk memastikan konsistensi penataan antara variabel polinomial.
LookupCheck: Memverifikasi apakah evaluasi polinomial berada dalam tabel pencarian yang diberikan, yaitu f(Bμ) ⊆ T(Bμ), memastikan bahwa beberapa nilai 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 hiperkubus Boolean sama dengan nilai yang dinyatakan ∏x∈Hμ f(x) = s, untuk memastikan kebenaran produk polinomial.
ZeroCheck: Memverifikasi apakah sebuah polinomial multivariat di hypercube Boolean pada titik mana pun adalah nol ∏x∈Hμ f(x) = 0, ∀x ∈ Bμ, untuk memastikan distribusi titik nol dari 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 variabel tunggal, mengurangi kompleksitas komputasi bagi pihak yang melakukan verifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan angka acak, membangun kombinasi linier untuk melakukan pemrosesan batch terhadap beberapa contoh verifikasi jumlah.
BatchCheck: Berdasarkan SumCheck, memverifikasi kebenaran evaluasi beberapa polinomial multivariat untuk meningkatkan efisiensi protokol.
Meskipun Binius memiliki banyak kesamaan dalam desain protokol dengan HyperPlonk, Binius telah melakukan perbaikan dalam 3 aspek berikut:
ProductCheck dioptimalkan: Dalam HyperPlonk, ProductCheck mensyaratkan bahwa penyebut U tidak boleh nol di seluruh hiperkubus, dan produk harus sama dengan nilai tertentu; Binius menyederhanakan proses pemeriksaan ini dengan mengkhususkan nilai tersebut menjadi 1, sehingga mengurangi kompleksitas komputasi.
Penanganan masalah pembagian dengan nol: HyperPlonk gagal menangani situasi pembagian dengan nol secara memadai, mengakibatkan tidak dapat memastikan bahwa U tidak nol di hypercube; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius masih dapat melanjutkan pemrosesan, memungkinkan perpanjangan ke nilai produk apa pun.
Cek Permutasi Kelas Silang: HyperPlonk tidak memiliki fitur ini; Binius mendukung Cek Permutasi antara beberapa kolom, yang memungkinkan Binius untuk menangani situasi pengaturan polinomial yang lebih kompleks.
Oleh karena itu, Binius melalui
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.
Binius STARKs: Sistem pembuktian nol pengetahuan yang efisien dalam domain biner
Analisis Prinsip Binius STARKs dan Pemikiran Optimisasinya
1. Pendahuluan
Berbeda dengan SNARKs yang berbasis kurva elips, STARKs dapat dianggap sebagai SNARKs yang berbasis hash. Salah satu alasan utama mengapa efisiensi STARKs saat ini rendah adalah: sebagian besar nilai dalam program sebenarnya cukup kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dan lain-lain. Namun, untuk memastikan keamanan bukti berbasis pohon Merkle, saat melakukan ekstensi data menggunakan pengkodean Reed-Solomon, banyak nilai redundan tambahan akan mengisi seluruh domain, meskipun nilai aslinya sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.
Generasi 1 STARKs memiliki lebar kode 252bit, generasi 2 STARKs memiliki lebar kode 64bit, generasi 3 STARKs memiliki lebar kode 32bit, tetapi lebar kode 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, bidang biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang yang terbuang, yaitu generasi 4 STARKs.
Jika dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian terbaru tentang bidang terbatas dalam beberapa tahun terakhir, penelitian tentang bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah banyak digunakan dalam kriptografi, contoh tipikalnya termasuk:
Standar Enkripsi Tingkat Lanjut ( AES ), berbasis pada domain F28;
Kode otentikasi 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 ke final SHA-3, yang didasarkan pada domain F28, adalah algoritma hash yang sangat cocok untuk rekurensi.
Ketika menggunakan domain yang lebih kecil, operasi perluasan domain menjadi semakin penting untuk memastikan keamanan. Domain biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan domain untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu memasuki perluasan domain, melainkan 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.
Ketika membangun sistem bukti berdasarkan bidang biner, terdapat 2 masalah praktis: ukuran bidang yang digunakan saat menghitung representasi trace dalam STARKs harus lebih besar dari derajat polinomial; saat melakukan komitmen Merkle tree dalam STARKs, diperlukan pengkodean Reed-Solomon, dan 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, menggunakan multivariat ( yang secara khusus adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan mewakili seluruh jejak komputasi 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 dianggap 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
Sebagian besar sistem SNARK saat ini biasanya terdiri dari dua bagian berikut:
Teori informasi bukti interaktif polinomial oracle (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti dari sistem bukti, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan penyaji untuk secara bertahap mengirimkan polinomial melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah perhitungan tersebut benar hanya 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 yang berbeda dalam menangani ekspresi polinomial, sehingga memengaruhi kinerja dan efisiensi keseluruhan sistem SNARK.
Skema Komitmen Polinomial (Polynomial Commitment Scheme, PCS): Skema komitmen polinomial digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP valid. PCS adalah alat kriptografi, melalui yang mana, pembuktian dapat mengkomit suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sekaligus menyembunyikan informasi lain tentang polinomial itu. Skema komitmen polinomial yang umum meliputi KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) dan Brakedown. Berbagai PCS memiliki performa, keamanan, dan skenario aplikasi yang berbeda.
Berdasarkan kebutuhan spesifik, pilih PIOP dan PCS yang berbeda, dan kombinasikan dengan domain terbatas atau kurva elips yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Contohnya:
• Halo2: Menggabungkan PLONK PIOP dan Bulletproofs PCS, serta berdasarkan kurva Pasta. Saat merancang Halo2, fokus pada skalabilitas dan menghilangkan trusted setup dalam protokol ZCash.
• Plonky2: mengadopsi PLONK PIOP dan FRI PCS yang dipadukan, serta berbasis pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekurensi 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. 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 fungsi ekspansi seperti bukti rekurensi atau bukti agregasi.
Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, aritmetika yang dibangun di atas menara bidang biner (towers of binary fields) menjadi dasar perhitungan, memungkinkan 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 ini 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 ini menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), memungkinkan sistem pembuktian yang efisien di bidang biner, dan mengurangi biaya yang biasanya terkait dengan bidang besar.
2.1 Ruang terbatas: aritmetika berbasis towers of binary fields
Domain biner bertingkat adalah kunci untuk mewujudkan perhitungan yang cepat dan dapat diverifikasi, 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. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur bertingkat, menjadikan domain biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.
Di mana "canonical" merujuk pada cara unik dan langsung untuk merepresentasikan elemen dalam domain biner. Misalnya, dalam domain biner paling dasar F2, string k-bit mana pun dapat langsung dipetakan ke elemen domain biner k-bit. Ini berbeda dengan domain bilangan prima, yang tidak dapat memberikan representasi standar seperti itu dalam jumlah bit yang ditentukan. 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 kemudahan 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 ( yang digunakan dalam AES ), reduksi Montgomery ( 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 domain biner tidak perlu memperkenalkan carry dalam operasi penjumlahan dan perkalian, dan operasi kuadrat dalam 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 dalam berbagai cara dalam konteks domain biner. Itu dapat dianggap sebagai elemen unik dalam domain biner 128 bit, atau dipecahkan 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 operasi perkalian, kuadrat, dan invers dalam domain biner tower n bit ( yang dapat dipecah menjadi subdomain m bit ).
2.2 PIOP: Versi Adaptasi HyperPlonk Product dan PermutationCheck------Cocok untuk domain biner
Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi keakuratan polinomial dan kumpulan multivariat. Mekanisme pemeriksaan inti ini mencakup:
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 relasi permutasi f(x) = f(π(x)), untuk memastikan konsistensi penataan antara variabel polinomial.
LookupCheck: Memverifikasi apakah evaluasi polinomial berada dalam tabel pencarian yang diberikan, yaitu f(Bμ) ⊆ T(Bμ), memastikan bahwa beberapa nilai 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 hiperkubus Boolean sama dengan nilai yang dinyatakan ∏x∈Hμ f(x) = s, untuk memastikan kebenaran produk polinomial.
ZeroCheck: Memverifikasi apakah sebuah polinomial multivariat di hypercube Boolean pada titik mana pun adalah nol ∏x∈Hμ f(x) = 0, ∀x ∈ Bμ, untuk memastikan distribusi titik nol dari 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 variabel tunggal, mengurangi kompleksitas komputasi bagi pihak yang melakukan verifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan angka acak, membangun kombinasi linier untuk melakukan pemrosesan batch terhadap beberapa contoh verifikasi jumlah.
BatchCheck: Berdasarkan SumCheck, memverifikasi kebenaran evaluasi beberapa polinomial multivariat untuk meningkatkan efisiensi protokol.
Meskipun Binius memiliki banyak kesamaan dalam desain protokol dengan HyperPlonk, Binius telah melakukan perbaikan dalam 3 aspek berikut:
ProductCheck dioptimalkan: Dalam HyperPlonk, ProductCheck mensyaratkan bahwa penyebut U tidak boleh nol di seluruh hiperkubus, dan produk harus sama dengan nilai tertentu; Binius menyederhanakan proses pemeriksaan ini dengan mengkhususkan nilai tersebut menjadi 1, sehingga mengurangi kompleksitas komputasi.
Penanganan masalah pembagian dengan nol: HyperPlonk gagal menangani situasi pembagian dengan nol secara memadai, mengakibatkan tidak dapat memastikan bahwa U tidak nol di hypercube; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius masih dapat melanjutkan pemrosesan, memungkinkan perpanjangan ke nilai produk apa pun.
Cek Permutasi Kelas Silang: HyperPlonk tidak memiliki fitur ini; Binius mendukung Cek Permutasi antara beberapa kolom, yang memungkinkan Binius untuk menangani situasi pengaturan polinomial yang lebih kompleks.
Oleh karena itu, Binius melalui