Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi
1. Pendahuluan
Salah satu alasan utama rendahnya efisiensi STARKs 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, saat melakukan perluasan data dengan kode Reed-Solomon, banyak nilai redundan tambahan akan mengisi seluruh domain, meskipun nilai asli itu sendiri sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.
Generasi pertama lebar kode STARKs adalah 252bit, generasi kedua lebar kode STARKs adalah 64bit, generasi ketiga lebar kode STARKs adalah 32bit, tetapi lebar kode 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang yang terbuang, yaitu generasi keempat STARKs.
Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian terbaru lainnya tentang bidang terbatas, penelitian tentang bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah diterapkan secara luas dalam kriptografi, contoh tipikal termasuk:
Standar Enkripsi Tingkat Lanjut ( AES ), berdasarkan 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 berbasis pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursi.
Ketika menggunakan domain yang lebih kecil, operasi perluasan domain menjadi semakin penting untuk memastikan keamanan. Sementara itu, 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 hanya perlu beroperasi di domain dasar, sehingga mencapai efisiensi tinggi dalam domain kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu masuk ke perluasan domain yang lebih besar untuk memastikan keamanan yang diperlukan.
Ada 2 masalah nyata saat membangun sistem bukti berdasarkan domain biner: Saat menghitung representasi jejak dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; Saat melakukan komitmen Merkle tree dalam STARKs, perlu melakukan pengkodean Reed-Solomon, ukuran domain yang digunakan harus lebih besar dari ukuran setelah perluasan pengkodean.
Binius mengusulkan solusi inovatif yang menangani kedua masalah tersebut secara terpisah, dan mewakili data yang sama dengan dua cara yang berbeda: pertama, menggunakan polinomial multivariat ( yang secara spesifik adalah polinomial multilinear ) sebagai pengganti polinomial univariat, dengan mewakili seluruh jejak perhitungan melalui nilai-nilainya di "hiperkubus" ( hypercubes ); kedua, karena setiap dimensi hiperkubus memiliki panjang 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti pada STARKs, tetapi hiperkubus dapat dianggap sebagai persegi ( square ), dan melakukan perluasan Reed-Solomon berdasarkan persegi tersebut. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.
2. Analisis Prinsip
Konstruksi sebagian besar sistem SNARK saat ini biasanya terdiri dari dua bagian berikut:
Teori informasi bukti oracle interaktif polinomial (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai sistem bukti inti, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Protokol PIOP yang berbeda memungkinkan penunjuk untuk mengirim polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah komputasi benar hanya dengan memeriksa hasil evaluasi sejumlah kecil polinomial. Protokol PIOP yang ada mencakup: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara berbeda dalam menangani ekspresi polinomial, sehingga mempengaruhi kinerja dan efisiensi keseluruhan sistem SNARK.
Polinomi Komitmen Skema (Polynomial Commitment Scheme, PCS): Polinomi komitmen skema digunakan untuk membuktikan apakah persamaan polinomi yang dihasilkan oleh PIOP adalah benar. PCS adalah alat kriptografi, melalui mana, pembuktian dapat berkomitmen pada suatu polinomi dan kemudian memverifikasi hasil evaluasi polinomi tersebut, sambil menyembunyikan informasi lain tentang polinomi. Skema polinomi komitmen yang umum termasuk KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) dan Brakedown, dll. Berbagai PCS memiliki kinerja, keamanan, dan skenario penggunaan 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. Contohnya:
• Halo2: dikombinasikan dari PLONK PIOP dan Bulletproofs PCS, dan berbasis pada kurva Pasta. Saat merancang Halo2, fokus pada skalabilitas dan menghilangkan trusted setup dalam protokol ZCash.
• Plonky2: Mengadopsi PLONK PIOP dan FRI PCS yang digabungkan, serta berbasis 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. Pemilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti SNARK dan efisiensi verifikasi, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa pengaturan terpercaya, serta apakah dapat mendukung bukti rekursif atau fungsi ekstensi lainnya seperti bukti agregasi.
Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara spesifik, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, aritmetika yang berbasis pada (towers of binary fields) membentuk dasar perhitungan, yang dapat 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 bukti pergeseran multilinier baru, mengoptimalkan efisiensi verifikasi hubungan multilinier di 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 sistem pembuktian yang efisien di bidang biner dan mengurangi overhead yang biasanya terkait dengan bidang besar.
2.1 Ruang Terbatas: Aritmetika berdasarkan menara bidang biner
Domain biner bertingkat adalah kunci untuk mewujudkan komputasi yang dapat diverifikasi dengan cepat, terutama karena dua aspek: perhitungan yang efisien dan aritmetika yang efisien. Domain biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur domain biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan pada domain biner dapat direpresentasikan dalam bentuk aljabar yang ringkas dan mudah untuk diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur menara, membuat domain biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.
Di mana "canonical" merujuk pada cara unik dan langsung untuk mewakili elemen dalam bidang biner. Misalnya, dalam bidang biner paling dasar F2, sembarang string k-bit dapat dipetakan langsung ke elemen bidang biner k-bit. Ini berbeda dengan bidang prima, di mana bidang prima tidak dapat memberikan representasi standar semacam itu dalam jumlah bit tertentu. Meskipun bidang prima 32-bit dapat dimuat dalam 32 bit, tidak setiap string 32-bit dapat secara unik terkait dengan elemen bidang, sementara bidang biner memiliki kenyamanan pemetaan satu ke satu semacam itu. Dalam bidang prima Fp, metode reduksi umum termasuk reduksi Barrett, reduksi Montgomery, dan metode reduksi khusus untuk bidang hingga 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 bidang biner tidak memerlukan pengenalan carry dalam operasi penjumlahan dan perkalian, dan operasi kuadrat dalam bidang biner sangat efisien, karena mengikuti aturan penyederhanaan (X + Y )2 = X2 + Y 2.
Seperti yang ditunjukkan pada Gambar 1, sebuah string 128-bit: string ini dapat ditafsirkan dengan berbagai cara dalam konteks bidang biner. Itu dapat dianggap sebagai elemen unik dalam bidang biner 128-bit, atau dapat diuraikan menjadi dua elemen bidang menara 64-bit, empat elemen bidang menara 32-bit, 16 elemen bidang menara 8-bit, atau 128 elemen bidang F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi apa pun, 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 sifat ini untuk meningkatkan efisiensi komputasi. Selain itu, makalah "On Efficient Inversion in Tower Fields of Characteristic Two" membahas kompleksitas komputasi untuk operasi perkalian, pemangkatan, dan invers dalam bidang biner bertingkat n-bit ( yang dapat dipecah menjadi subfield m-bit ).
2.2 PIOP: versi modifikasi HyperPlonk Product dan PermutationCheck------cocok untuk bidang biner
Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi keakuratan 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 pada hiperkubus Boolean adalah hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi permutasi antara variabel polinomial.
LookupCheck: Memverifikasi apakah evaluasi polinomial ada dalam tabel lookup yang diberikan, yaitu f(Bµ) ⊆ T(Bµ), memastikan beberapa nilai berada dalam rentang yang ditentukan.
MultisetCheck: Memeriksa apakah dua himpunan multivariat sama, yaitu {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, memastikan konsistensi antara 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 polinomial.
SumCheck: Memeriksa apakah jumlah nilai 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 pihak verifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan bilangan acak, membangun kombinasi linier untuk melakukan pemrosesan batch pada 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:
Optimisasi ProductCheck: Dalam HyperPlonk, ProductCheck mensyaratkan bahwa penyebut U tidak boleh nol di seluruh hypercube, dan hasil kali 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 mengakibatkan ketidakmampuan untuk menyatakan masalah non-nol U di hiperkubus; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya nol, ProductCheck Binius dapat terus memproses, memungkinkan perluasan ke nilai produk mana pun.
Pemeriksaan Permutasi Lintas Kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung pemeriksaan 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 multivariat yang lebih kompleks, menyediakan dukungan fungsional yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan di HyperPlonk, tetapi juga meletakkan dasar untuk sistem bukti berbasis 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 salah satu teknologi kunci, yang dapat secara efektif menghasilkan dan mengoperasikan polinomial yang diturunkan dari pegangan input atau polinomial virtual lainnya. Berikut adalah dua metode kunci:
Packing: Metode ini
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: Aplikasi inovatif dan optimasi kinerja di domain biner
Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi
1. Pendahuluan
Salah satu alasan utama rendahnya efisiensi STARKs 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, saat melakukan perluasan data dengan kode Reed-Solomon, banyak nilai redundan tambahan akan mengisi seluruh domain, meskipun nilai asli itu sendiri sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.
Generasi pertama lebar kode STARKs adalah 252bit, generasi kedua lebar kode STARKs adalah 64bit, generasi ketiga lebar kode STARKs adalah 32bit, tetapi lebar kode 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang yang terbuang, yaitu generasi keempat STARKs.
Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian terbaru lainnya tentang bidang terbatas, penelitian tentang bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah diterapkan secara luas dalam kriptografi, contoh tipikal termasuk:
Standar Enkripsi Tingkat Lanjut ( AES ), berdasarkan 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 berbasis pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursi.
Ketika menggunakan domain yang lebih kecil, operasi perluasan domain menjadi semakin penting untuk memastikan keamanan. Sementara itu, 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 hanya perlu beroperasi di domain dasar, sehingga mencapai efisiensi tinggi dalam domain kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu masuk ke perluasan domain yang lebih besar untuk memastikan keamanan yang diperlukan.
Ada 2 masalah nyata saat membangun sistem bukti berdasarkan domain biner: Saat menghitung representasi jejak dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; Saat melakukan komitmen Merkle tree dalam STARKs, perlu melakukan pengkodean Reed-Solomon, ukuran domain yang digunakan harus lebih besar dari ukuran setelah perluasan pengkodean.
Binius mengusulkan solusi inovatif yang menangani kedua masalah tersebut secara terpisah, dan mewakili data yang sama dengan dua cara yang berbeda: pertama, menggunakan polinomial multivariat ( yang secara spesifik adalah polinomial multilinear ) sebagai pengganti polinomial univariat, dengan mewakili seluruh jejak perhitungan melalui nilai-nilainya di "hiperkubus" ( hypercubes ); kedua, karena setiap dimensi hiperkubus memiliki panjang 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti pada STARKs, tetapi hiperkubus dapat dianggap sebagai persegi ( square ), dan melakukan perluasan Reed-Solomon berdasarkan persegi tersebut. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.
2. Analisis Prinsip
Konstruksi sebagian besar sistem SNARK saat ini biasanya terdiri dari dua bagian berikut:
Teori informasi bukti oracle interaktif polinomial (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai sistem bukti inti, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Protokol PIOP yang berbeda memungkinkan penunjuk untuk mengirim polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah komputasi benar hanya dengan memeriksa hasil evaluasi sejumlah kecil polinomial. Protokol PIOP yang ada mencakup: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara berbeda dalam menangani ekspresi polinomial, sehingga mempengaruhi kinerja dan efisiensi keseluruhan sistem SNARK.
Polinomi Komitmen Skema (Polynomial Commitment Scheme, PCS): Polinomi komitmen skema digunakan untuk membuktikan apakah persamaan polinomi yang dihasilkan oleh PIOP adalah benar. PCS adalah alat kriptografi, melalui mana, pembuktian dapat berkomitmen pada suatu polinomi dan kemudian memverifikasi hasil evaluasi polinomi tersebut, sambil menyembunyikan informasi lain tentang polinomi. Skema polinomi komitmen yang umum termasuk KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) dan Brakedown, dll. Berbagai PCS memiliki kinerja, keamanan, dan skenario penggunaan 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. Contohnya:
• Halo2: dikombinasikan dari PLONK PIOP dan Bulletproofs PCS, dan berbasis pada kurva Pasta. Saat merancang Halo2, fokus pada skalabilitas dan menghilangkan trusted setup dalam protokol ZCash.
• Plonky2: Mengadopsi PLONK PIOP dan FRI PCS yang digabungkan, serta berbasis 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. Pemilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti SNARK dan efisiensi verifikasi, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa pengaturan terpercaya, serta apakah dapat mendukung bukti rekursif atau fungsi ekstensi lainnya seperti bukti agregasi.
Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara spesifik, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, aritmetika yang berbasis pada (towers of binary fields) membentuk dasar perhitungan, yang dapat 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 bukti pergeseran multilinier baru, mengoptimalkan efisiensi verifikasi hubungan multilinier di 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 sistem pembuktian yang efisien di bidang biner dan mengurangi overhead yang biasanya terkait dengan bidang besar.
2.1 Ruang Terbatas: Aritmetika berdasarkan menara bidang biner
Domain biner bertingkat adalah kunci untuk mewujudkan komputasi yang dapat diverifikasi dengan cepat, terutama karena dua aspek: perhitungan yang efisien dan aritmetika yang efisien. Domain biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur domain biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan pada domain biner dapat direpresentasikan dalam bentuk aljabar yang ringkas dan mudah untuk diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur menara, membuat domain biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.
Di mana "canonical" merujuk pada cara unik dan langsung untuk mewakili elemen dalam bidang biner. Misalnya, dalam bidang biner paling dasar F2, sembarang string k-bit dapat dipetakan langsung ke elemen bidang biner k-bit. Ini berbeda dengan bidang prima, di mana bidang prima tidak dapat memberikan representasi standar semacam itu dalam jumlah bit tertentu. Meskipun bidang prima 32-bit dapat dimuat dalam 32 bit, tidak setiap string 32-bit dapat secara unik terkait dengan elemen bidang, sementara bidang biner memiliki kenyamanan pemetaan satu ke satu semacam itu. Dalam bidang prima Fp, metode reduksi umum termasuk reduksi Barrett, reduksi Montgomery, dan metode reduksi khusus untuk bidang hingga 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 bidang biner tidak memerlukan pengenalan carry dalam operasi penjumlahan dan perkalian, dan operasi kuadrat dalam bidang biner sangat efisien, karena mengikuti aturan penyederhanaan (X + Y )2 = X2 + Y 2.
Seperti yang ditunjukkan pada Gambar 1, sebuah string 128-bit: string ini dapat ditafsirkan dengan berbagai cara dalam konteks bidang biner. Itu dapat dianggap sebagai elemen unik dalam bidang biner 128-bit, atau dapat diuraikan menjadi dua elemen bidang menara 64-bit, empat elemen bidang menara 32-bit, 16 elemen bidang menara 8-bit, atau 128 elemen bidang F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi apa pun, 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 sifat ini untuk meningkatkan efisiensi komputasi. Selain itu, makalah "On Efficient Inversion in Tower Fields of Characteristic Two" membahas kompleksitas komputasi untuk operasi perkalian, pemangkatan, dan invers dalam bidang biner bertingkat n-bit ( yang dapat dipecah menjadi subfield m-bit ).
2.2 PIOP: versi modifikasi HyperPlonk Product dan PermutationCheck------cocok untuk bidang biner
Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi keakuratan 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 pada hiperkubus Boolean adalah hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi permutasi antara variabel polinomial.
LookupCheck: Memverifikasi apakah evaluasi polinomial ada dalam tabel lookup yang diberikan, yaitu f(Bµ) ⊆ T(Bµ), memastikan beberapa nilai berada dalam rentang yang ditentukan.
MultisetCheck: Memeriksa apakah dua himpunan multivariat sama, yaitu {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, memastikan konsistensi antara 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 polinomial.
SumCheck: Memeriksa apakah jumlah nilai 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 pihak verifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan bilangan acak, membangun kombinasi linier untuk melakukan pemrosesan batch pada 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:
Optimisasi ProductCheck: Dalam HyperPlonk, ProductCheck mensyaratkan bahwa penyebut U tidak boleh nol di seluruh hypercube, dan hasil kali 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 mengakibatkan ketidakmampuan untuk menyatakan masalah non-nol U di hiperkubus; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya nol, ProductCheck Binius dapat terus memproses, memungkinkan perluasan ke nilai produk mana pun.
Pemeriksaan Permutasi Lintas Kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung pemeriksaan 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 multivariat yang lebih kompleks, menyediakan dukungan fungsional yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan di HyperPlonk, tetapi juga meletakkan dasar untuk sistem bukti berbasis 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 salah satu teknologi kunci, yang dapat secara efektif menghasilkan dan mengoperasikan polinomial yang diturunkan dari pegangan input atau polinomial virtual lainnya. Berikut adalah dua metode kunci: