Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi
1 Pendahuluan
Berbeda dengan SNARKs yang berbasis kurva elips, STARKs dapat dianggap sebagai SNARKs yang berbasis hash. Salah satu alasan utama efisiensi STARKs saat ini rendah adalah: sebagian besar nilai dalam program nyata relatif kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dan sebagainya. Namun, untuk menjamin keamanan bukti 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 kode STARKs generasi pertama adalah 252bit, lebar kode STARKs generasi kedua adalah 64bit, lebar kode STARKs generasi ketiga adalah 32bit, tetapi lebar kode 32bit masih menyisakan banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang yang terbuang, yaitu STARKs generasi keempat.
Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian baru-baru ini tentang bidang terbatas, penelitian tentang bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah banyak digunakan dalam kriptografi, contoh tipikal termasuk:
Advanced Encryption Standard ( AES ), berdasarkan bidang F28
Galois Message Authentication Code ( GMAC ), berbasis pada domain F2128
QR code, 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. 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 masuk ke dalam 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.
Saat membangun sistem pembuktian berdasarkan domain biner, terdapat 2 masalah praktis: ketika menghitung representasi trace dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; saat melakukan komitmen Merkle tree dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, ukuran domain yang digunakan harus lebih besar dari ukuran setelah pengkodean diperluas.
Binius mengusulkan solusi inovatif yang menangani kedua masalah tersebut secara terpisah, dan mewakili data yang sama dengan dua cara yang berbeda: pertama, menggunakan multivariat ( yang secara khusus adalah polinomial multilinier ) menggantikan polinomial univariat, dengan mewakili seluruh jejak komputasi melalui nilainya di "hyper-cube" ( hypercubes ); kedua, karena panjang setiap dimensi hyper-cube adalah 2, maka tidak dapat melakukan ekstensi Reed-Solomon standar seperti STARKs, tetapi dapat memandang hyper-cube sebagai persegi ( square ), dan melakukan ekstensi Reed-Solomon berdasarkan persegi tersebut. Metode ini secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi sambil memastikan keamanan.
2 Analisis Prinsip
Kebanyakan sistem SNARK saat ini biasanya terdiri dari dua bagian berikut:
Bukti Oracle Interaktif Polinomial Teori Informasi (: PIOP) sebagai inti dari sistem bukti, mengubah hubungan komputasi yang diberikan menjadi persamaan polinomial yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan pembuktian secara bertahap mengirimkan polinomial melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah perhitungan tersebut benar dengan menanyakan hasil evaluasi dari sejumlah kecil polinomial. Protokol PIOP yang ada termasuk: PIOP PLONK, PIOP Spartan, dan PIOP HyperPlonk, yang masing-masing memiliki cara yang berbeda dalam menangani ekspresi polinomial, sehingga memengaruhi kinerja dan efisiensi keseluruhan sistem SNARK.
Skema Komitmen Polin ( Polynomial Commitment Scheme, PCS ): Skema komitmen polin digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP valid. PCS adalah alat kriptografi yang memungkinkan pembuktian untuk mengkomitmenkan suatu 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, dan masing-masing PCS memiliki kinerja, keamanan, dan skenario penerapan yang berbeda.
Berdasarkan kebutuhan spesifik, pilih PIOP dan PCS yang berbeda, dan kombinasikan dengan bidang terbatas atau kurva elips yang sesuai, dapat membangun sistem pembuktian dengan atribut yang berbeda. Contohnya:
• Halo2: digabungkan dari PLONK PIOP dan Bulletproofs PCS, serta berbasis pada kurva Pasta. Halo2 dirancang dengan 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 rekurensi yang efisien. Dalam merancang sistem-sistem ini, pemilihan PIOP dan PCS yang digunakan harus sesuai dengan field terbatas atau kurva elips yang digunakan, untuk memastikan kebenaran, kinerja, dan keamanan sistem. Pilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti SNARK dan efisiensi verifikasi, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa pengaturan tepercaya, serta apakah dapat mendukung fungsi-fungsi perluasan seperti bukti rekurensi atau bukti agregasi.
Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanannya. Pertama, aritmetika yang dibangun di atas menara bidang biner (towers of binary fields) menjadi dasar perhitungan, yang 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 memperkenalkan pembuktian pergeseran multilinear baru, yang 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), yang memungkinkannya untuk mewujudkan sistem pembuktian yang efisien di bidang biner dan mengurangi overhead yang biasanya terkait dengan bidang besar.
2.1 Ruang Terbatas: Arithmetisasi berdasarkan menara bidang biner
Domain biner bertingkat adalah kunci untuk mewujudkan komputasi yang cepat dan dapat diverifikasi, terutama karena dua aspek: komputasi 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 direpresentasikan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Karakteristik ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya sifat 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 bidang biner. Misalnya, dalam bidang biner paling dasar F2, string k-bit mana pun dapat langsung dipetakan ke elemen bidang biner k-bit. Ini berbeda dengan bidang prima, yang tidak dapat memberikan representasi standar ini dalam jumlah bit tertentu. Meskipun bidang prima 32-bit dapat dimasukkan dalam 32 bit, tidak setiap string 32-bit dapat secara unik sesuai dengan elemen bidang, sedangkan bidang biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam bidang prima Fp, metode reduksi yang umum termasuk reduksi Barrett, reduksi Montgomery, serta metode reduksi khusus untuk bidang terbatas tertentu seperti Mersenne-31 atau Goldilocks-64. Dalam bidang biner F2k, metode reduksi yang umum digunakan termasuk reduksi khusus ( seperti yang digunakan dalam AES ), reduksi Montgomery ( seperti yang digunakan dalam POLYVAL ), dan reduksi rekursif ( seperti Tower ). Makalah "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" menunjukkan bahwa bidang biner tidak memerlukan pelaksanaan 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 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 overhead komputasi, hanya sekadar 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 overhead 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 di domain biner tower n-bit ( yang dapat dipecah menjadi subdomain m-bit ).
2.2 PIOP: versi modifikasi Produk HyperPlonk dan PermutationCheck------cocok untuk domain biner
Desain PIOP dalam protokol Binius mengadopsi 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 hypercube boolean merupakan hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi permutasi antar variabel polinomial.
LookupCheck: Memverifikasi apakah evaluasi polinomial ada dalam tabel pencarian 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 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 suatu polinomial multivariat pada hypercube 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 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 terhadap beberapa contoh verifikasi jumlah.
BatchCheck: Berdasarkan SumCheck, memverifikasi kebenaran evaluasi beberapa polinomial multivariabel untuk meningkatkan efisiensi protokol.
Meskipun Binius dan HyperPlonk memiliki banyak kesamaan dalam desain protokol, Binius telah melakukan perbaikan di 3 aspek berikut:
Optimasi ProductCheck: Dalam HyperPlonk, ProductCheck mengharuskan penyebut U tidak sama dengan nol di seluruh hypercube, dan produk harus sama dengan nilai tertentu; Binius menyederhanakan proses pemeriksaan ini dengan mengkhususkan nilai tersebut menjadi 1, sehingga mengurangi kompleksitas perhitungan.
Penanganan masalah pembagian dengan nol: HyperPlonk tidak berhasil menangani kasus pembagian dengan nol, yang mengakibatkan ketidakmampuan untuk memastikan bahwa U tidak nol pada hiperkubus; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius dapat terus memproses, memungkinkan untuk diperluas 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 susunan polinomial yang lebih kompleks.
Oleh karena itu, Binius meningkatkan fleksibilitas dan efisiensi protokol dengan memperbaiki 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 dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem bukti berbasis domain biner di masa depan.
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.
10 Suka
Hadiah
10
5
Bagikan
Komentar
0/400
ZkSnarker
· 07-29 13:22
sebenarnya starks hanyalah makanan ringan tetapi dengan hash lmao
Lihat AsliBalas0
PebbleHander
· 07-26 15:33
Bengbu tinggal, ternyata ada yang berbicara tentang hal yang sekeras ini.
Lihat AsliBalas0
SmartContractPhobia
· 07-26 15:26
Ini adalah pekerjaan teknis yang membuat kita sebagai pemula merasa tidak nyaman.
Lihat AsliBalas0
LootboxPhobia
· 07-26 15:23
Sangat maju ya, dari tiga digit turun ke dua digit.
Lihat AsliBalas0
notSatoshi1971
· 07-26 15:18
Apa ini masih ingin melampaui snark? Optimasi ini terlalu konservatif, bukan?
Binius STARKs: Optimasi dan Analisis Prinsip Domain Biner
Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi
1 Pendahuluan
Berbeda dengan SNARKs yang berbasis kurva elips, STARKs dapat dianggap sebagai SNARKs yang berbasis hash. Salah satu alasan utama efisiensi STARKs saat ini rendah adalah: sebagian besar nilai dalam program nyata relatif kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dan sebagainya. Namun, untuk menjamin keamanan bukti 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 kode STARKs generasi pertama adalah 252bit, lebar kode STARKs generasi kedua adalah 64bit, lebar kode STARKs generasi ketiga adalah 32bit, tetapi lebar kode 32bit masih menyisakan banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang yang terbuang, yaitu STARKs generasi keempat.
Tabel 1: Jalur Derivasi STARKs
| Generasi | Lebar Kode | Sistem Perwakilan | |------|----------|----------| | Generasi 1 | 252bit | STARK | | Generasi ke-2 | 64bit | Plonky2 | | Generasi ke-3 | 32bit | Mina | | Generasi ke-4 | 1bit | Binius |
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 banyak digunakan dalam kriptografi, contoh tipikal termasuk:
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 masuk ke dalam 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.
Saat membangun sistem pembuktian berdasarkan domain biner, terdapat 2 masalah praktis: ketika menghitung representasi trace dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; saat melakukan komitmen Merkle tree dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, ukuran domain yang digunakan harus lebih besar dari ukuran setelah pengkodean diperluas.
Binius mengusulkan solusi inovatif yang menangani kedua masalah tersebut secara terpisah, dan mewakili data yang sama dengan dua cara yang berbeda: pertama, menggunakan multivariat ( yang secara khusus adalah polinomial multilinier ) menggantikan polinomial univariat, dengan mewakili seluruh jejak komputasi melalui nilainya di "hyper-cube" ( hypercubes ); kedua, karena panjang setiap dimensi hyper-cube adalah 2, maka tidak dapat melakukan ekstensi Reed-Solomon standar seperti STARKs, tetapi dapat memandang hyper-cube sebagai persegi ( square ), dan melakukan ekstensi Reed-Solomon berdasarkan persegi tersebut. Metode ini secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi sambil memastikan keamanan.
2 Analisis Prinsip
Kebanyakan sistem SNARK saat ini biasanya terdiri dari dua bagian berikut:
Bukti Oracle Interaktif Polinomial Teori Informasi (: PIOP) sebagai inti dari sistem bukti, mengubah hubungan komputasi yang diberikan menjadi persamaan polinomial yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan pembuktian secara bertahap mengirimkan polinomial melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah perhitungan tersebut benar dengan menanyakan hasil evaluasi dari sejumlah kecil polinomial. Protokol PIOP yang ada termasuk: PIOP PLONK, PIOP Spartan, dan PIOP HyperPlonk, yang masing-masing memiliki cara yang berbeda dalam menangani ekspresi polinomial, sehingga memengaruhi kinerja dan efisiensi keseluruhan sistem SNARK.
Skema Komitmen Polin ( Polynomial Commitment Scheme, PCS ): Skema komitmen polin digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP valid. PCS adalah alat kriptografi yang memungkinkan pembuktian untuk mengkomitmenkan suatu 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, dan masing-masing PCS memiliki kinerja, keamanan, dan skenario penerapan yang berbeda.
Berdasarkan kebutuhan spesifik, pilih PIOP dan PCS yang berbeda, dan kombinasikan dengan bidang terbatas atau kurva elips yang sesuai, dapat membangun sistem pembuktian dengan atribut yang berbeda. Contohnya:
• Halo2: digabungkan dari PLONK PIOP dan Bulletproofs PCS, serta berbasis pada kurva Pasta. Halo2 dirancang dengan 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 rekurensi yang efisien. Dalam merancang sistem-sistem ini, pemilihan PIOP dan PCS yang digunakan harus sesuai dengan field terbatas atau kurva elips yang digunakan, untuk memastikan kebenaran, kinerja, dan keamanan sistem. Pilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti SNARK dan efisiensi verifikasi, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa pengaturan tepercaya, serta apakah dapat mendukung fungsi-fungsi perluasan seperti bukti rekurensi atau bukti agregasi.
Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanannya. Pertama, aritmetika yang dibangun di atas menara bidang biner (towers of binary fields) menjadi dasar perhitungan, yang 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 memperkenalkan pembuktian pergeseran multilinear baru, yang 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), yang memungkinkannya untuk mewujudkan sistem pembuktian yang efisien di bidang biner dan mengurangi overhead yang biasanya terkait dengan bidang besar.
2.1 Ruang Terbatas: Arithmetisasi berdasarkan menara bidang biner
Domain biner bertingkat adalah kunci untuk mewujudkan komputasi yang cepat dan dapat diverifikasi, terutama karena dua aspek: komputasi 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 direpresentasikan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Karakteristik ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya sifat 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 bidang biner. Misalnya, dalam bidang biner paling dasar F2, string k-bit mana pun dapat langsung dipetakan ke elemen bidang biner k-bit. Ini berbeda dengan bidang prima, yang tidak dapat memberikan representasi standar ini dalam jumlah bit tertentu. Meskipun bidang prima 32-bit dapat dimasukkan dalam 32 bit, tidak setiap string 32-bit dapat secara unik sesuai dengan elemen bidang, sedangkan bidang biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam bidang prima Fp, metode reduksi yang umum termasuk reduksi Barrett, reduksi Montgomery, serta metode reduksi khusus untuk bidang terbatas tertentu seperti Mersenne-31 atau Goldilocks-64. Dalam bidang biner F2k, metode reduksi yang umum digunakan termasuk reduksi khusus ( seperti yang digunakan dalam AES ), reduksi Montgomery ( seperti yang digunakan dalam POLYVAL ), dan reduksi rekursif ( seperti Tower ). Makalah "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" menunjukkan bahwa bidang biner tidak memerlukan pelaksanaan 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 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 overhead komputasi, hanya sekadar 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 overhead 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 di domain biner tower n-bit ( yang dapat dipecah menjadi subdomain m-bit ).
2.2 PIOP: versi modifikasi Produk HyperPlonk dan PermutationCheck------cocok untuk domain biner
Desain PIOP dalam protokol Binius mengadopsi 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 hypercube boolean merupakan hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi permutasi antar variabel polinomial.
LookupCheck: Memverifikasi apakah evaluasi polinomial ada dalam tabel pencarian 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 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 suatu polinomial multivariat pada hypercube 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 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 terhadap beberapa contoh verifikasi jumlah.
BatchCheck: Berdasarkan SumCheck, memverifikasi kebenaran evaluasi beberapa polinomial multivariabel untuk meningkatkan efisiensi protokol.
Meskipun Binius dan HyperPlonk memiliki banyak kesamaan dalam desain protokol, Binius telah melakukan perbaikan di 3 aspek berikut:
Optimasi ProductCheck: Dalam HyperPlonk, ProductCheck mengharuskan penyebut U tidak sama dengan nol di seluruh hypercube, dan produk harus sama dengan nilai tertentu; Binius menyederhanakan proses pemeriksaan ini dengan mengkhususkan nilai tersebut menjadi 1, sehingga mengurangi kompleksitas perhitungan.
Penanganan masalah pembagian dengan nol: HyperPlonk tidak berhasil menangani kasus pembagian dengan nol, yang mengakibatkan ketidakmampuan untuk memastikan bahwa U tidak nol pada hiperkubus; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius dapat terus memproses, memungkinkan untuk diperluas 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 susunan polinomial yang lebih kompleks.
Oleh karena itu, Binius meningkatkan fleksibilitas dan efisiensi protokol dengan memperbaiki 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 dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem bukti berbasis domain biner di masa depan.