Analisis Prinsip Binius STARKs dan Pemikiran Optimalisasinya
1 Pendahuluan
Berbeda dengan SNARKs berbasis kurva elips, STARKs dapat dianggap sebagai SNARKs berbasis hash. Salah satu alasan utama mengapa STARKs saat ini tidak efisien adalah: sebagian besar nilai dalam program nyata relatif kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dll. Namun, untuk menjamin keamanan bukti berbasis pohon Merkle, saat memperluas data dengan pengkodean Reed-Solomon, banyak nilai redundan tambahan akan mengisi seluruh domain, bahkan jika nilai aslinya sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.
Generasi pertama kode STARKs memiliki lebar bit 252, generasi kedua 64 bit, dan generasi ketiga 32 bit, tetapi lebar bit 32 masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang padat dan efisien tanpa ruang yang terbuang sembarangan, dapat dianggap sebagai generasi keempat STARKs.
Dibandingkan dengan penelitian baru-baru ini yang ditemukan seperti Goldilocks, BabyBear, Mersenne31 dan bidang terbatas lainnya, 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 Lanjutan (AES), berbasis bidang F28
Kode otentikasi pesan Galois ( GMAC ), berdasarkan domain F2128
Kode QR, menggunakan pengodean Reed-Solomon berbasis F28
Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk final SHA-3, yang didasarkan pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursif.
Ketika menggunakan bidang yang lebih kecil, operasi perluasan bidang menjadi semakin penting untuk memastikan keamanan. Dan bidang biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan bidang untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam perluasan bidang, tetapi hanya perlu beroperasi di bawah bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu mendalami perluasan bidang yang lebih besar untuk memastikan keamanan yang diperlukan.
Saat membangun sistem bukti berdasarkan domain biner, terdapat 2 masalah nyata: saat menghitung representasi trace dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; saat berkomitmen pada Merkle tree dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, ukuran domain yang digunakan harus lebih besar dari ukuran setelah perluasan pengkodean.
Binius mengajukan solusi inovatif yang menangani kedua masalah ini secara terpisah, dan mewujudkan data yang sama melalui dua cara berbeda: pertama, menggunakan multivariat ( yaitu polinomial multilinier ) sebagai pengganti polinomial univariat, dengan mewakili seluruh jejak komputasi melalui nilai-nilainya di "hyper-cube" ( hypercubes ); kedua, karena panjang setiap dimensi hyper-cube adalah 2, maka tidak dapat dilakukan ekstensi Reed-Solomon standar seperti STARKs, tetapi hyper-cube dapat dipandang sebagai persegi ( square ), yang menjadi dasar untuk melakukan ekstensi Reed-Solomon. Metode ini, sambil memastikan keamanan, juga secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.
2 Analisis Prinsip
Kebanyakan sistem SNARK saat ini biasanya terdiri dari dua bagian berikut:
Bukti Oracle Interaktif Polinom Teori Informasi (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti sistem bukti, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinom yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan penyedia bukti untuk mengirimkan polinom secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah komputasi benar hanya dengan menanyakan hasil evaluasi dari sejumlah kecil polinom. Protokol PIOP yang ada termasuk: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, masing-masing memiliki cara yang berbeda dalam menangani ekspresi polinom, 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 valid. PCS adalah alat kriptografi yang memungkinkan pembuktian untuk mengkomit sebuah polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lainnya tentang polinomial. Skema komitmen polin yang umum 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 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, serta berdasarkan kurva Pasta. Halo2 dirancang dengan fokus pada skalabilitas, serta menghilangkan trusted setup dalam protokol ZCash.
• Plonky2: Mengadopsi PLONK PIOP dan FRI PCS yang digabungkan, dan berdasarkan domain Goldilocks. Plonky2 dirancang untuk mencapai rekurensi yang efisien. Dalam merancang sistem-sistem ini, PIOP dan PCS yang dipilih harus cocok dengan finite field atau kurva elips yang digunakan untuk memastikan kebenaran, performa, dan keamanan sistem. Pilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti dan efisiensi verifikasi SNARK, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa pengaturan terpercaya, serta kemampuan untuk mendukung fungsi-fungsi ekstensi seperti bukti rekurensi atau bukti agregat.
Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanannya. Pertama, berdasarkan aritmetika menara bidang biner (towers of binary fields) membentuk dasar dari 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 ini memperkenalkan pembuktian pergeseran multilinear baru yang mengoptimalkan efisiensi verifikasi hubungan multilinear di bidang kecil. Keempat, Binius menggunakan pembuktian pencarian versi yang ditingkatkan, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol ini menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), yang memungkinkannya untuk mencapai sistem pembuktian yang efisien di bidang biner dan mengurangi biaya yang biasanya terkait dengan bidang besar.
2.1 Ruang Terbatas: Aritmetika berbasis towers of binary fields
Field biner berbentuk tower adalah kunci untuk mencapai komputasi yang dapat diverifikasi dengan cepat, terutama disebabkan oleh dua aspek: komputasi yang efisien dan aritmetika yang efisien. Field biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur field biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan di atas field biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Karakteristik ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur tower, membuat field biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.
Di mana "canonical" mengacu pada cara unik dan langsung untuk merepresentasikan elemen dalam bidang biner. Sebagai contoh, 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 yang ditentukan. Meskipun bidang prima 32 bit dapat dimuat dalam 32 bit, tidak semua string 32 bit dapat secara unik dikaitkan dengan elemen bidang, sementara 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 dalam bidang biner, tidak perlu memperkenalkan 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 bidang biner. Ini dapat dianggap sebagai elemen unik dalam bidang biner 128-bit, atau diuraikan sebagai dua elemen bidang tower 64-bit, empat elemen bidang tower 32-bit, 16 elemen bidang tower 8-bit, atau 128 elemen bidang F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi tambahan, hanya konversi tipe string bit (typecast), yang merupakan atribut yang sangat menarik dan berguna. Selain itu, elemen bidang kecil dapat dikemas menjadi elemen bidang yang lebih besar tanpa memerlukan biaya komputasi tambahan. Protokol Binius memanfaatkan fitur ini untuk meningkatkan efisiensi komputasi. Selain itu, makalah "On Efficient Inversion in Tower Fields of Characteristic Two" membahas kompleksitas komputasi dari operasi perkalian, kuadrat, dan invers dalam bidang tower biner n-bit yang dapat diuraikan menjadi subbidang m-bit (.
![Bitlayer Research：Binius STARKs prinsip analisis dan pemikiran optimisasi])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: Versi Adaptasi 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 himpunan multivariat. Pemeriksaan inti ini mencakup:
GateCheck: Memverifikasi apakah saksi rahasia ω dan input publik x memenuhi hubungan perhitungan rangkaian C###x,ω(=0, untuk memastikan rangkaian berfungsi dengan benar.
PermutationCheck: Memverifikasi apakah hasil evaluasi dari dua polinomial multivariat f dan g pada hiperkubus Boolean merupakan hubungan permutasi f)x( = f)π(x(), untuk memastikan konsistensi susunan variabel polinomial.
LookupCheck: Memverifikasi apakah evaluasi polinomial berada dalam tabel lookup yang diberikan, yaitu f)Bµ( ⊆ T)Bµ(, memastikan bahwa 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, untuk menjamin konsistensi antar beberapa himpunan.
ProductCheck: Memeriksa apakah nilai polinomial rasional pada hiperkubus Boolean sama dengan nilai yang dinyatakan ∏x∈Hµ f)x( = s, untuk memastikan kebenaran produk polinomial.
ZeroCheck: Memvalidasi apakah nilai dari suatu polinomial multivariat di titik mana pun pada hiperkubus Boolean 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, SumCheck mengurangi kompleksitas komputasi pihak verifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch dengan memperkenalkan angka acak, membangun kombinasi linier untuk melakukan pemrosesan batch pada beberapa instance pemeriksaan jumlah.
BatchCheck: Berdasarkan SumCheck, memverifikasi kebenaran evaluasi beberapa polinomial multivariat untuk meningkatkan efisiensi protokol.
Meskipun Binius dan HyperPlonk memiliki banyak kesamaan dalam desain protokol, Binius telah melakukan perbaikan dalam 3 aspek berikut:
ProductCheck dioptimalkan: Dalam HyperPlonk, ProductCheck mengharuskan 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 tidak dapat menangani situasi pembagian dengan nol dengan baik, yang mengakibatkan ketidakmampuan untuk menyatakan masalah non-nol U pada hypercube; Binius menangani masalah ini dengan benar, meskipun dalam situasi di mana penyebut adalah nol, ProductCheck Binius masih dapat melanjutkan pemrosesan, memungkinkan perluasan ke nilai produk yang sembarang.
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 multivariat 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 domain biner di masa depan.
![Bitlayer Research: Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.3 PIOP: argumen pergeseran multilinear baru------cocok untuk hypercube boolean
Dalam protokol Binius, konstruksi dan pengolahan polinomial virtual adalah salah satu teknologi kunci, yang dapat secara efektif menghasilkan dan mengoperasikan polinomial yang diturunkan dari pegangan input atau polinomial virtual lainnya.
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.
Analisis Prinsip STARKs Binius: Inovasi Domain Biner dan Optimasi Kinerja
Analisis Prinsip Binius STARKs dan Pemikiran Optimalisasinya
1 Pendahuluan
Berbeda dengan SNARKs berbasis kurva elips, STARKs dapat dianggap sebagai SNARKs berbasis hash. Salah satu alasan utama mengapa STARKs saat ini tidak efisien adalah: sebagian besar nilai dalam program nyata relatif kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dll. Namun, untuk menjamin keamanan bukti berbasis pohon Merkle, saat memperluas data dengan pengkodean Reed-Solomon, banyak nilai redundan tambahan akan mengisi seluruh domain, bahkan jika nilai aslinya sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.
Generasi pertama kode STARKs memiliki lebar bit 252, generasi kedua 64 bit, dan generasi ketiga 32 bit, tetapi lebar bit 32 masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang padat dan efisien tanpa ruang yang terbuang sembarangan, dapat dianggap sebagai generasi keempat STARKs.
Dibandingkan dengan penelitian baru-baru ini yang ditemukan seperti Goldilocks, BabyBear, Mersenne31 dan bidang terbatas lainnya, penelitian tentang bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah banyak digunakan dalam kriptografi, contoh tipikalnya termasuk:
Ketika menggunakan bidang yang lebih kecil, operasi perluasan bidang menjadi semakin penting untuk memastikan keamanan. Dan bidang biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan bidang untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam perluasan bidang, tetapi hanya perlu beroperasi di bawah bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu mendalami perluasan bidang yang lebih besar untuk memastikan keamanan yang diperlukan.
Saat membangun sistem bukti berdasarkan domain biner, terdapat 2 masalah nyata: saat menghitung representasi trace dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; saat berkomitmen pada Merkle tree dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, ukuran domain yang digunakan harus lebih besar dari ukuran setelah perluasan pengkodean.
Binius mengajukan solusi inovatif yang menangani kedua masalah ini secara terpisah, dan mewujudkan data yang sama melalui dua cara berbeda: pertama, menggunakan multivariat ( yaitu polinomial multilinier ) sebagai pengganti polinomial univariat, dengan mewakili seluruh jejak komputasi melalui nilai-nilainya di "hyper-cube" ( hypercubes ); kedua, karena panjang setiap dimensi hyper-cube adalah 2, maka tidak dapat dilakukan ekstensi Reed-Solomon standar seperti STARKs, tetapi hyper-cube dapat dipandang sebagai persegi ( square ), yang menjadi dasar untuk melakukan ekstensi Reed-Solomon. Metode ini, sambil memastikan keamanan, juga secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.
2 Analisis Prinsip
Kebanyakan sistem SNARK saat ini biasanya terdiri dari dua bagian berikut:
Bukti Oracle Interaktif Polinom Teori Informasi (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti sistem bukti, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinom yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan penyedia bukti untuk mengirimkan polinom secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah komputasi benar hanya dengan menanyakan hasil evaluasi dari sejumlah kecil polinom. Protokol PIOP yang ada termasuk: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, masing-masing memiliki cara yang berbeda dalam menangani ekspresi polinom, 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 valid. PCS adalah alat kriptografi yang memungkinkan pembuktian untuk mengkomit sebuah polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lainnya tentang polinomial. Skema komitmen polin yang umum 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 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, serta berdasarkan kurva Pasta. Halo2 dirancang dengan fokus pada skalabilitas, serta menghilangkan trusted setup dalam protokol ZCash.
• Plonky2: Mengadopsi PLONK PIOP dan FRI PCS yang digabungkan, dan berdasarkan domain Goldilocks. Plonky2 dirancang untuk mencapai rekurensi yang efisien. Dalam merancang sistem-sistem ini, PIOP dan PCS yang dipilih harus cocok dengan finite field atau kurva elips yang digunakan untuk memastikan kebenaran, performa, dan keamanan sistem. Pilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti dan efisiensi verifikasi SNARK, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa pengaturan terpercaya, serta kemampuan untuk mendukung fungsi-fungsi ekstensi seperti bukti rekurensi atau bukti agregat.
Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanannya. Pertama, berdasarkan aritmetika menara bidang biner (towers of binary fields) membentuk dasar dari 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 ini memperkenalkan pembuktian pergeseran multilinear baru yang mengoptimalkan efisiensi verifikasi hubungan multilinear di bidang kecil. Keempat, Binius menggunakan pembuktian pencarian versi yang ditingkatkan, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol ini menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), yang memungkinkannya untuk mencapai sistem pembuktian yang efisien di bidang biner dan mengurangi biaya yang biasanya terkait dengan bidang besar.
2.1 Ruang Terbatas: Aritmetika berbasis towers of binary fields
Field biner berbentuk tower adalah kunci untuk mencapai komputasi yang dapat diverifikasi dengan cepat, terutama disebabkan oleh dua aspek: komputasi yang efisien dan aritmetika yang efisien. Field biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur field biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan di atas field biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Karakteristik ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur tower, membuat field biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.
Di mana "canonical" mengacu pada cara unik dan langsung untuk merepresentasikan elemen dalam bidang biner. Sebagai contoh, 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 yang ditentukan. Meskipun bidang prima 32 bit dapat dimuat dalam 32 bit, tidak semua string 32 bit dapat secara unik dikaitkan dengan elemen bidang, sementara 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 dalam bidang biner, tidak perlu memperkenalkan 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 bidang biner. Ini dapat dianggap sebagai elemen unik dalam bidang biner 128-bit, atau diuraikan sebagai dua elemen bidang tower 64-bit, empat elemen bidang tower 32-bit, 16 elemen bidang tower 8-bit, atau 128 elemen bidang F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi tambahan, hanya konversi tipe string bit (typecast), yang merupakan atribut yang sangat menarik dan berguna. Selain itu, elemen bidang kecil dapat dikemas menjadi elemen bidang yang lebih besar tanpa memerlukan biaya komputasi tambahan. Protokol Binius memanfaatkan fitur ini untuk meningkatkan efisiensi komputasi. Selain itu, makalah "On Efficient Inversion in Tower Fields of Characteristic Two" membahas kompleksitas komputasi dari operasi perkalian, kuadrat, dan invers dalam bidang tower biner n-bit yang dapat diuraikan menjadi subbidang m-bit (.
![Bitlayer Research：Binius STARKs prinsip analisis dan pemikiran optimisasi])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: Versi Adaptasi 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 himpunan multivariat. Pemeriksaan inti ini mencakup:
GateCheck: Memverifikasi apakah saksi rahasia ω dan input publik x memenuhi hubungan perhitungan rangkaian C###x,ω(=0, untuk memastikan rangkaian berfungsi dengan benar.
PermutationCheck: Memverifikasi apakah hasil evaluasi dari dua polinomial multivariat f dan g pada hiperkubus Boolean merupakan hubungan permutasi f)x( = f)π(x(), untuk memastikan konsistensi susunan variabel polinomial.
LookupCheck: Memverifikasi apakah evaluasi polinomial berada dalam tabel lookup yang diberikan, yaitu f)Bµ( ⊆ T)Bµ(, memastikan bahwa 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, untuk menjamin konsistensi antar beberapa himpunan.
ProductCheck: Memeriksa apakah nilai polinomial rasional pada hiperkubus Boolean sama dengan nilai yang dinyatakan ∏x∈Hµ f)x( = s, untuk memastikan kebenaran produk polinomial.
ZeroCheck: Memvalidasi apakah nilai dari suatu polinomial multivariat di titik mana pun pada hiperkubus Boolean 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, SumCheck mengurangi kompleksitas komputasi pihak verifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch dengan memperkenalkan angka acak, membangun kombinasi linier untuk melakukan pemrosesan batch pada beberapa instance pemeriksaan jumlah.
BatchCheck: Berdasarkan SumCheck, memverifikasi kebenaran evaluasi beberapa polinomial multivariat untuk meningkatkan efisiensi protokol.
Meskipun Binius dan HyperPlonk memiliki banyak kesamaan dalam desain protokol, Binius telah melakukan perbaikan dalam 3 aspek berikut:
ProductCheck dioptimalkan: Dalam HyperPlonk, ProductCheck mengharuskan 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 tidak dapat menangani situasi pembagian dengan nol dengan baik, yang mengakibatkan ketidakmampuan untuk menyatakan masalah non-nol U pada hypercube; Binius menangani masalah ini dengan benar, meskipun dalam situasi di mana penyebut adalah nol, ProductCheck Binius masih dapat melanjutkan pemrosesan, memungkinkan perluasan ke nilai produk yang sembarang.
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 multivariat 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 domain biner di masa depan.
![Bitlayer Research: Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.3 PIOP: argumen pergeseran multilinear baru------cocok untuk hypercube boolean
Dalam protokol Binius, konstruksi dan pengolahan polinomial virtual adalah salah satu teknologi kunci, yang dapat secara efektif menghasilkan dan mengoperasikan polinomial yang diturunkan dari pegangan input atau polinomial virtual lainnya.