Analisis Prinsip STARKs Binius dan Pemikiran Optimisasinya
1 Pendahuluan
Salah satu alasan utama efisiensi STARKs yang rendah adalah: sebagian besar nilai dalam program sebenarnya cukup kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dll. Namun, untuk memastikan 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.
Lebar bit encoding STARKs generasi pertama adalah 252bit, lebar bit encoding STARKs generasi kedua adalah 64bit, lebar bit encoding STARKs generasi ketiga adalah 32bit, tetapi lebar bit encoding 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang terbuang, yaitu STARKs generasi keempat.
Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian baru lainnya yang ditemukan dalam beberapa tahun terakhir, 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), berbasis bidang F28;
Kode Autentikasi Pesan Galois ( GMAC ), berbasis pada bidang F2128;
Kode QR, menggunakan pengkodean Reed-Solomon berbasis F28;
Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk final SHA-3, yang berbasis pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursi.
Ketika menggunakan bidang yang lebih kecil, operasi perluasan menjadi semakin penting untuk memastikan keamanan. Bidang biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam perluasan, dan cukup beroperasi di bawah bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu mendalami perluasan yang lebih besar untuk memastikan keamanan yang diperlukan.
Ketika membangun sistem bukti berdasarkan domain biner, terdapat 2 masalah praktis: Ukuran domain yang digunakan untuk menghitung representasi trace dalam STARKs harus lebih besar dari derajat polinomial; Saat berkomitmen ke Merkle tree dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, dan ukuran domain 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 spesifik adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan merepresentasikan seluruh jejak perhitungan melalui nilai-nilainya di "hypercube" ( hypercubes ); kedua, karena setiap dimensi hypercube memiliki panjang 2, maka tidak dapat dilakukan perpanjangan Reed-Solomon standar seperti STARKs, tetapi hypercube dapat dipandang sebagai ( square ), dan berdasarkan persegi tersebut dilakukan perpanjangan Reed-Solomon. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja perhitungan.
2 Analisis Prinsip
Konstruksi sebagian besar sistem SNARK saat ini biasanya terdiri dari dua bagian berikut:
Teorema Informasi Bukti Interaktif Polinomial Oracle (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 penjamin untuk mengirimkan polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah komputasi benar hanya dengan menanyakan hasil evaluasi dari sejumlah kecil polinomial. Protokol PIOP yang ada mencakup: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara penanganan ekspresi polinomial yang berbeda, sehingga mempengaruhi 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 berlaku. PCS adalah alat kriptografi, melalui mana, pembuktian dapat berkomitmen pada suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sekaligus menyembunyikan informasi lainnya tentang polinomial. Skema komitmen polinomial yang umum digunakan termasuk KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) dan Brakedown, dan lain-lain. Berbagai PCS memiliki performa, 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 dan penghapusan trusted setup dalam protokol ZCash.
• Plonky2: mengadopsi PLONK PIOP dan FRI PCS yang digabungkan, serta berbasis pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem-sistem ini, pilihan PIOP dan PCS yang digunakan harus cocok dengan finite field atau kurva elips yang digunakan, untuk memastikan kebenaran, kinerja, dan keamanan sistem. Pilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti SNARK dan efisiensi verifikasi, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa pengaturan yang tepercaya, dan apakah dapat mendukung bukti rekursif atau bukti agregat sebagai fungsi ekspansi.
Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, berdasarkan aritmetika bidang biner (towers of binary fields) yang membentuk dasar perhitungannya, mampu melakukan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol pembuktian Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, memastikan konsistensi pemeriksaan yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol 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 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
Bidang biner bertingkat adalah kunci untuk mewujudkan perhitungan yang cepat dan dapat diverifikasi, terutama disebabkan oleh dua aspek: perhitungan yang efisien dan aritmatika yang efisien. Bidang biner pada dasarnya mendukung operasi aritmatika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur bidang biner mendukung proses aritmatika yang disederhanakan, yaitu operasi yang dilakukan di bidang biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Ciri-ciri ini, ditambah dengan kemampuan untuk memanfaatkan karakteristik hierarkisnya sepenuhnya melalui struktur bertingkat, membuat bidang biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.
Di mana "canonical" merujuk pada cara representasi elemen yang unik dan langsung dalam domain biner. Misalnya, dalam domain biner F2 yang paling dasar, setiap string k-bit dapat langsung dipetakan ke elemen domain biner k-bit. Ini berbeda dengan domain prima, di mana domain prima tidak dapat memberikan representasi yang standar dalam jumlah bit tertentu. Meskipun domain prima 32-bit dapat diwakili dalam 32-bit, tidak setiap string 32-bit dapat secara unik sesuai dengan elemen domain, sementara domain biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam domain prima Fp, metode reduksi yang umum termasuk reduksi Barrett, reduksi Montgomery, dan metode reduksi khusus untuk domain hingga tertentu seperti Mersenne-31 atau Goldilocks-64. Dalam domain biner F2k, metode reduksi yang umum 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 domain biner, baik dalam operasi penjumlahan maupun perkalian, tidak perlu memperkenalkan carry, 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 dengan berbagai cara dalam konteks domain biner. Itu 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, enam belas elemen domain tower 8-bit, atau 128 elemen domain F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi apa pun, 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 terurai menjadi subdomain m-bit (.
) 2.2 PIOP: Versi Adaptasi HyperPlonk Product dan PermutationCheck------Cocok untuk bidang biner
Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan himpunan multivariat. Mekanisme 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 dua polinomial multivariat f dan g di hiperkubus Boolean adalah hubungan permutasi f)x( = f)π(x(), untuk memastikan konsistensi pengaturan antara variabel polinomial.
LookupCheck: Memverifikasi apakah evaluasi polinomial berada dalam tabel pencarian yang diberikan, yaitu f)Bµ( ⊆ T)Bµ(, memastikan bahwa nilai-nilai tertentu 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 hiper kubus Boolean sama dengan nilai yang dinyatakan ∏x∈Hµ f)x( = s, untuk memastikan keakuratan produk polinomial.
ZeroCheck: Memverifikasi apakah sebuah polinomial multivariabel pada hiper kubus Boole di titik mana pun adalah nol ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, untuk memastikan distribusi titik nol dari polinomial tersebut.
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 pihak yang memverifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan angka acak, membangun kombinasi linier untuk memproses beberapa instance verifikasi jumlah.
BatchCheck: Berdasarkan SumCheck, memverifikasi kebenaran evaluasi banyak polinomial multivariat untuk meningkatkan efisiensi protokol.
Meskipun Binius dan HyperPlonk memiliki banyak kesamaan dalam desain protokol, Binius telah melakukan perbaikan dalam 3 aspek berikut:
Optimalisasi ProductCheck: Dalam HyperPlonk, ProductCheck mengharuskan penyebut U tidak 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 situasi pembagian dengan nol, yang mengakibatkan ketidakmampuan untuk memastikan bahwa U bukan nol di hiperkubus; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius masih dapat melanjutkan proses, memungkinkan untuk diperluas ke nilai produk mana pun.
Cek Permutasi Lintas Kolom: HyperPlonk tidak memiliki fungsi ini; Binius mendukung cek permutasi di antara beberapa kolom, yang memungkinkan Binius menangani kasus pengaturan polinomial yang lebih kompleks.
Oleh karena itu, Binius meningkatkan fleksibilitas dan efisiensi protokol melalui perbaikan pada mekanisme PIOPSumCheck yang ada, terutama dalam menangani validasi polinomial multivariat yang lebih kompleks, memberikan dukungan fungsionalitas yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem bukti berbasis bidang biner di masa depan.
![Bitlayer Research: Analisis Prinsip STARKs Binius 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 pemrosesan 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 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.
7 Suka
Hadiah
7
7
Bagikan
Komentar
0/400
OnChain_Detective
· 20jam yang lalu
ngl pola optimasi ini terlihat mencurigakan... kita perlu pemeriksaan lebih dekat pada klaim domain biner tersebut
Lihat AsliBalas0
0xTherapist
· 08-07 06:36
32 bit juga bagaimana, masih membuang ruang
Lihat AsliBalas0
CryptoCrazyGF
· 08-07 03:55
Penelitian begitu banyak ada gunanya, on-chain tetap tidak bisa berjalan cepat.
Lihat AsliBalas0
MemeCurator
· 08-07 03:52
Jika tidak mengerti, maka mengertilah!
Lihat AsliBalas0
LiquidityWhisperer
· 08-07 03:40
Pengurangan redundansi biner, cukup pintar bermain
Lihat AsliBalas0
AirdropHunter007
· 08-07 03:35
starks juga bisa diet luar biasa!
Lihat AsliBalas0
TopEscapeArtist
· 08-07 03:28
Oh ya, ini lagi ingin menembus batas bawah teknologi? Pengalaman sejarah memberi tahu saya bahwa ini semua adalah jebakan~
Analisis protokol Binius: Implementasi STARKs yang efisien di domain biner
Analisis Prinsip STARKs Binius dan Pemikiran Optimisasinya
1 Pendahuluan
Salah satu alasan utama efisiensi STARKs yang rendah adalah: sebagian besar nilai dalam program sebenarnya cukup kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dll. Namun, untuk memastikan 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.
Lebar bit encoding STARKs generasi pertama adalah 252bit, lebar bit encoding STARKs generasi kedua adalah 64bit, lebar bit encoding STARKs generasi ketiga adalah 32bit, tetapi lebar bit encoding 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang terbuang, yaitu STARKs generasi keempat.
Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian baru lainnya yang ditemukan dalam beberapa tahun terakhir, 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), berbasis bidang F28;
Kode Autentikasi Pesan Galois ( GMAC ), berbasis pada bidang F2128;
Kode QR, menggunakan pengkodean Reed-Solomon berbasis F28;
Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk final SHA-3, yang berbasis pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursi.
Ketika menggunakan bidang yang lebih kecil, operasi perluasan menjadi semakin penting untuk memastikan keamanan. Bidang biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam perluasan, dan cukup beroperasi di bawah bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu mendalami perluasan yang lebih besar untuk memastikan keamanan yang diperlukan.
Ketika membangun sistem bukti berdasarkan domain biner, terdapat 2 masalah praktis: Ukuran domain yang digunakan untuk menghitung representasi trace dalam STARKs harus lebih besar dari derajat polinomial; Saat berkomitmen ke Merkle tree dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, dan ukuran domain 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 spesifik adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan merepresentasikan seluruh jejak perhitungan melalui nilai-nilainya di "hypercube" ( hypercubes ); kedua, karena setiap dimensi hypercube memiliki panjang 2, maka tidak dapat dilakukan perpanjangan Reed-Solomon standar seperti STARKs, tetapi hypercube dapat dipandang sebagai ( square ), dan berdasarkan persegi tersebut dilakukan perpanjangan Reed-Solomon. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja perhitungan.
2 Analisis Prinsip
Konstruksi sebagian besar sistem SNARK saat ini biasanya terdiri dari dua bagian berikut:
Teorema Informasi Bukti Interaktif Polinomial Oracle (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 penjamin untuk mengirimkan polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah komputasi benar hanya dengan menanyakan hasil evaluasi dari sejumlah kecil polinomial. Protokol PIOP yang ada mencakup: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara penanganan ekspresi polinomial yang berbeda, sehingga mempengaruhi 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 berlaku. PCS adalah alat kriptografi, melalui mana, pembuktian dapat berkomitmen pada suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sekaligus menyembunyikan informasi lainnya tentang polinomial. Skema komitmen polinomial yang umum digunakan termasuk KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) dan Brakedown, dan lain-lain. Berbagai PCS memiliki performa, 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 dan penghapusan trusted setup dalam protokol ZCash.
• Plonky2: mengadopsi PLONK PIOP dan FRI PCS yang digabungkan, serta berbasis pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem-sistem ini, pilihan PIOP dan PCS yang digunakan harus cocok dengan finite field atau kurva elips yang digunakan, untuk memastikan kebenaran, kinerja, dan keamanan sistem. Pilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti SNARK dan efisiensi verifikasi, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa pengaturan yang tepercaya, dan apakah dapat mendukung bukti rekursif atau bukti agregat sebagai fungsi ekspansi.
Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, berdasarkan aritmetika bidang biner (towers of binary fields) yang membentuk dasar perhitungannya, mampu melakukan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol pembuktian Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, memastikan konsistensi pemeriksaan yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol 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 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
Bidang biner bertingkat adalah kunci untuk mewujudkan perhitungan yang cepat dan dapat diverifikasi, terutama disebabkan oleh dua aspek: perhitungan yang efisien dan aritmatika yang efisien. Bidang biner pada dasarnya mendukung operasi aritmatika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur bidang biner mendukung proses aritmatika yang disederhanakan, yaitu operasi yang dilakukan di bidang biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Ciri-ciri ini, ditambah dengan kemampuan untuk memanfaatkan karakteristik hierarkisnya sepenuhnya melalui struktur bertingkat, membuat bidang biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.
Di mana "canonical" merujuk pada cara representasi elemen yang unik dan langsung dalam domain biner. Misalnya, dalam domain biner F2 yang paling dasar, setiap string k-bit dapat langsung dipetakan ke elemen domain biner k-bit. Ini berbeda dengan domain prima, di mana domain prima tidak dapat memberikan representasi yang standar dalam jumlah bit tertentu. Meskipun domain prima 32-bit dapat diwakili dalam 32-bit, tidak setiap string 32-bit dapat secara unik sesuai dengan elemen domain, sementara domain biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam domain prima Fp, metode reduksi yang umum termasuk reduksi Barrett, reduksi Montgomery, dan metode reduksi khusus untuk domain hingga tertentu seperti Mersenne-31 atau Goldilocks-64. Dalam domain biner F2k, metode reduksi yang umum 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 domain biner, baik dalam operasi penjumlahan maupun perkalian, tidak perlu memperkenalkan carry, 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 dengan berbagai cara dalam konteks domain biner. Itu 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, enam belas elemen domain tower 8-bit, atau 128 elemen domain F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi apa pun, 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 terurai menjadi subdomain m-bit (.
![Bitlayer Research：Binius STARKs原理解析及其优化思考])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 2.2 PIOP: Versi Adaptasi HyperPlonk Product dan PermutationCheck------Cocok untuk bidang biner
Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan himpunan multivariat. Mekanisme 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 dua polinomial multivariat f dan g di hiperkubus Boolean adalah hubungan permutasi f)x( = f)π(x(), untuk memastikan konsistensi pengaturan antara variabel polinomial.
LookupCheck: Memverifikasi apakah evaluasi polinomial berada dalam tabel pencarian yang diberikan, yaitu f)Bµ( ⊆ T)Bµ(, memastikan bahwa nilai-nilai tertentu 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 hiper kubus Boolean sama dengan nilai yang dinyatakan ∏x∈Hµ f)x( = s, untuk memastikan keakuratan produk polinomial.
ZeroCheck: Memverifikasi apakah sebuah polinomial multivariabel pada hiper kubus Boole di titik mana pun adalah nol ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, untuk memastikan distribusi titik nol dari polinomial tersebut.
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 pihak yang memverifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan angka acak, membangun kombinasi linier untuk memproses beberapa instance verifikasi jumlah.
BatchCheck: Berdasarkan SumCheck, memverifikasi kebenaran evaluasi banyak polinomial multivariat untuk meningkatkan efisiensi protokol.
Meskipun Binius dan HyperPlonk memiliki banyak kesamaan dalam desain protokol, Binius telah melakukan perbaikan dalam 3 aspek berikut:
Optimalisasi ProductCheck: Dalam HyperPlonk, ProductCheck mengharuskan penyebut U tidak 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 situasi pembagian dengan nol, yang mengakibatkan ketidakmampuan untuk memastikan bahwa U bukan nol di hiperkubus; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius masih dapat melanjutkan proses, memungkinkan untuk diperluas ke nilai produk mana pun.
Cek Permutasi Lintas Kolom: HyperPlonk tidak memiliki fungsi ini; Binius mendukung cek permutasi di antara beberapa kolom, yang memungkinkan Binius menangani kasus pengaturan polinomial yang lebih kompleks.
Oleh karena itu, Binius meningkatkan fleksibilitas dan efisiensi protokol melalui perbaikan pada mekanisme PIOPSumCheck yang ada, terutama dalam menangani validasi polinomial multivariat yang lebih kompleks, memberikan dukungan fungsionalitas yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem bukti berbasis bidang biner di masa depan.
![Bitlayer Research: Analisis Prinsip STARKs Binius 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 pemrosesan 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: