Analisis Prinsip Binius STARKs dan Pemikiran Optimasi
1 Pendahuluan
Berbeda dengan SNARKs yang berbasis kurva elips, STARKs dapat dianggap sebagai SNARKs yang berbasis hash. Salah satu alasan utama efisiensi STARKs yang rendah saat ini adalah: sebagian besar nilai dalam program praktis cukup kecil, seperti indeks loop, nilai boolean, penghitung, dan sebagainya. Namun, untuk memastikan keamanan pembuktian berbasis pohon Merkle, saat menggunakan pengkodean Reed-Solomon untuk memperluas data, banyak nilai redundan akan memakan seluruh domain, bahkan jika nilai asli sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.
Generasi pertama STARKs memiliki lebar kode 252 bit, generasi kedua 64 bit, dan generasi ketiga 32 bit, tetapi kode 32 bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, bidang biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa pemborosan, dapat dianggap sebagai generasi keempat STARKs.
Dibandingkan dengan bidang terbatas yang ditemukan dalam beberapa tahun terakhir seperti Goldilocks, BabyBear, dan Mersenne31, penelitian bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah banyak diterapkan dalam kriptografi, seperti AES(F28 field), GMAC(F2128 field), dan pengkodean Reed-Solomon QR code(F28, dan lain-lain. Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk final SHA-3 juga didasarkan pada bidang F28.
Saat 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 ketersediaan. Kebanyakan polinomial yang terlibat dalam perhitungan Prover hanya perlu dioperasikan di bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu dilakukan di bidang perluasan yang lebih besar untuk memastikan keamanan yang diperlukan.
Ada dua masalah praktis saat membangun sistem bukti berdasarkan domain biner:
Ukuran domain yang digunakan saat menghitung jejak dalam STARKs harus lebih besar dari derajat polinomial.
Saat berkomitmen Merkle tree dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, ukuran domain yang digunakan harus lebih besar dari ukuran setelah perpanjangan pengkodean.
Binius mengusulkan solusi inovatif untuk menangani kedua masalah ini:
Menggunakan polinomial multivariat ) sebagai pengganti polinomial univariat, dengan nilai-nilainya di "hiperkubus" untuk mewakili seluruh jejak perhitungan.
Karena setiap dimensi dari hiperkubus memiliki panjang 2, tidak dapat melakukan perpanjangan Reed-Solomon standar seperti STARKs, tetapi dapat menganggap hiperkubus sebagai persegi, dan melakukan perpanjangan Reed-Solomon berdasarkan persegi tersebut.
Metode ini secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi sambil memastikan keamanan.
2 Analisis Prinsip
Saat ini, sebagian besar sistem SNARKs biasanya terdiri dari dua bagian:
Bukti interaksi polinomial teori informasi oracle ( PIOP ):
Sebagai inti dari sistem bukti, mengubah hubungan perhitungan yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Melalui interaksi dengan verifier, prover secara bertahap mengirimkan polinomial, sehingga verifier dapat memverifikasi kebenaran perhitungan dengan mengquery sedikit hasil evaluasi polinomial. Protokol PIOP yang ada mencakup PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP.
Skema komitmen polinomial (PCS):
Digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP valid. PCS adalah alat kriptografi, di mana pembuktinya dapat berkomitmen pada suatu polinomial dan kemudian memverifikasi hasil evaluasinya, sambil menyembunyikan informasi lain tentang polinomial tersebut. PCS yang umum digunakan meliputi KZG, Bulletproofs, FRI, dan Brakedown.
Berdasarkan kebutuhan, pilih PIOP dan PCS yang berbeda, dan menggabungkannya dengan bidang terbatas atau kurva elips yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Contoh:
Aritmetisasi berbasis domain biner bertower: membentuk dasar perhitungan, mewujudkan operasi yang disederhanakan dalam domain biner
Modifikasi pemeriksaan produk dan permutasi HyperPlonk: memastikan pemeriksaan konsistensi yang efisien antara variabel dan permutasi
Bukti pergeseran multilinear baru: Mengoptimalkan efisiensi verifikasi hubungan multilinear di bidang kecil
Meningkatkan bukti pencarian Lasso: memberikan fleksibilitas dan keamanan pada mekanisme pencarian
Skema komitmen polinomial kecil: Mewujudkan sistem bukti yang efisien di atas bidang biner, mengurangi biaya terkait bidang besar.
( 2.1 Ruang Terbatas: Arithmetisasi berdasarkan towers of binary fields
Domain biner bertingkat adalah kunci untuk mencapai perhitungan yang cepat dan dapat diverifikasi, terutama karena perhitungan yang efisien dan aritmatika yang efisien. Domain biner pada dasarnya mendukung operasi aritmatika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Struktur domain biner mendukung proses aritmetisasi yang disederhanakan, di mana operasi yang dilakukan di atas domain biner dapat direpresentasikan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkis melalui struktur menara, membuat domain biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.
"canonical" merujuk pada cara unik dan langsung untuk merepresentasikan elemen dalam domain biner. Misalnya, dalam domain biner dasar F2, 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 standar dalam jumlah bit tertentu. Meskipun domain prima 32-bit dapat dimasukkan dalam 32-bit, tidak setiap string 32-bit dapat secara unik sesuai dengan satu elemen domain, sementara domain 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 oleh AES ###, reduksi Montgomery ( seperti yang digunakan oleh 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 perlu memperkenalkan carry dalam operasi penjumlahan dan perkalian, dan operasi kuadrat pada bidang biner sangat efisien karena mengikuti aturan penyederhanaan (X + Y)2 = X2 + Y2.
Sebuah string 128-bit dapat diinterpretasikan dalam konteks domain biner dengan berbagai cara. Ini dapat dianggap sebagai elemen unik dalam domain biner 128-bit, atau diurai menjadi dua elemen domain tower 64-bit, empat elemen domain tower 32-bit, enam belas elemen domain tower 8-bit, atau seratus dua puluh delapan elemen domain F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi tambahan, hanya konversi tipe string bit, adalah atribut yang sangat menarik dan berguna. Sementara itu, elemen domain kecil dapat dikemas menjadi elemen domain yang lebih besar tanpa biaya komputasi tambahan. Protokol Binius memanfaatkan fitur ini untuk meningkatkan efisiensi komputasi.
Makalah "On Efficient Inversion in Tower Fields of Characteristic Two" membahas kompleksitas komputasi untuk operasi perkalian, kuadrat, dan invers dalam bidang biner tower n-bit yang dapat direduksi menjadi subbidang m-bit (.
![Bitlayer Research：Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(
) 2.2 PIOP: Versi Adaptasi HyperPlonk Product dan PermutationCheck------Cocok untuk bidang biner
Desain PIOP dalam protokol Binius mengacu pada HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan kumpulan multivariat:
GateCheck: Memverifikasi apakah saksi rahasia ω dan input publik x memenuhi hubungan operasi sirkuit C(x,ω)=0, memastikan sirkuit berfungsi dengan benar.
PermutationCheck: Memverifikasi apakah hasil evaluasi dari dua polinomial multivariat f dan g di kubus Boolean adalah hubungan permutasi f###x( = f)π(x)(, memastikan konsistensi permutasi antar variabel polinomial.
LookupCheck: Memverifikasi apakah nilai polinomial berada dalam tabel pencarian yang diberikan, yaitu f(Bμ) ⊆ T)Bμ(, memastikan bahwa beberapa nilai berada dalam rentang yang ditentukan.
MultisetCheck: Memeriksa apakah dua himpunan 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, memastikan kebenaran produk polinomial.
ZeroCheck: Memverifikasi apakah suatu polinomial multivariat pada hiperkubus Boolean di titik mana pun adalah nol ∏x∈Hμ f)x( = 0, ∀x ∈ Bμ, memastikan distribusi titik nol dari polinomial tersebut.
SumCheck: Memeriksa apakah jumlah dari polinomial multivariat sesuai dengan nilai yang dinyatakan ∑x∈Hμ f)x( = s. Dengan mengubah masalah evaluasi polinomial multivariat menjadi evaluasi polinomial variabel tunggal, kompleksitas perhitungan pihak yang memverifikasi dapat dikurangi. Selain itu, SumCheck juga memungkinkan pemrosesan batch dengan memperkenalkan angka acak, membangun kombinasi linier untuk merealisasikan pemrosesan batch dari 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 di 3 bidang berikut:
Optimasi ProductCheck: Di HyperPlonk, ProductCheck mengharuskan penyebut U selalu tidak nol di seluruh hiperkubus, dan produk harus sama dengan nilai tertentu; Binius menyederhanakan proses pemeriksaan ini dengan mengkhususkan nilai tersebut menjadi 1, mengurangi kompleksitas perhitungan.
Penanganan masalah pembagian dengan nol: HyperPlonk tidak dapat menangani kasus pembagian dengan nol secara memadai, yang mengakibatkan ketidakmampuan untuk menyatakan bahwa U tidak nol di hypercube; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya adalah nol, ProductCheck Binius tetap dapat melanjutkan pemrosesan, memungkinkan untuk diperluas ke nilai produk mana pun.
Periksa Permutasi Lintas Kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung pemeriksaan permutasi antara beberapa kolom, memungkinkan Binius untuk menangani situasi susunan polinomial yang lebih kompleks.
Oleh karena itu, Binius meningkatkan fleksibilitas dan efisiensi protokol melalui perbaikan mekanisme PIOP SumCheck 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 bagi sistem pembuktian berbasis domain biner di masa depan.
![Bitlayer Research: Analisis Prinsip STARKs Binius dan Pemikiran Optimisasi])https://img-cdn.gateio.im/webp-social/moments-d74bdd8bc21dcfc05e21f9c0074461c3.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. Berikut adalah dua metode kunci:
Packing: Metode ini mengoptimalkan operasi dengan mengemas elemen-elemen kecil yang bersebelahan dalam urutan kamus menjadi elemen yang lebih besar. Operator Pack menargetkan operasi blok berukuran 2κ dan menggabungkannya menjadi satu elemen dalam domain berdimensi tinggi. Dengan memperluas secara multiliner (Multilinear Extension, MLE), polinom virtual ini dapat dievaluasi dan diproses secara efisien, mengubah fungsi t menjadi polinom lain, sehingga meningkatkan kinerja komputasi.
Operator pergeseran: Operator pergeseran menyusun ulang elemen dalam blok, berdasarkan offset yang diberikan o untuk melakukan pergeseran siklik. Metode ini berlaku untuk blok berukuran 2b, di mana setiap blok melakukan pergeseran berdasarkan offset. Operator pergeseran didefinisikan melalui dukungan fungsi untuk memastikan konsistensi dan efisiensi saat memproses polinomial virtual. Evaluasi kompleksitas konstruksi ini meningkat secara linier seiring dengan ukuran blok, sangat cocok untuk menangani kumpulan data besar atau skenario berdimensi tinggi dalam hiperkubus Bool.
![Bitlayer Research: Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi]###https://img-cdn.gateio.im/webp-social/moments-7f96976952fd0f8da0e93ff1042a966d.webp(
) 2.4 PIOP: versi modifikasi argumen Lasso lookup------cocok untuk domain biner
Protokol Lasso memungkinkan pihak yang membuktikan untuk berkomitmen pada sebuah vektor a ∈ Fm, dan membuktikan bahwa semua elemennya ada dalam tabel yang ditentukan sebelumnya t ∈ Fn. Lasso membuka konsep "mencari singularitas" (lookup singularities) dan dapat diterapkan pada skema komitmen polinomial multilinier. Efisiensinya terwujud dalam dua aspek berikut:
Efisiensi bukti: Untuk m pencarian dalam tabel berukuran n, pihak pembuktian hanya perlu menjanjikan m+n elemen domain. Elemen-elemen domain ini sangat kecil, semuanya berada dalam himpunan {0,...,m}. Dalam skema komitmen yang berbasis pada beberapa operasi pangkat, biaya komputasi pihak pembuktian adalah O###m + n( kali operasi grup) seperti
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
4
Posting ulang
Bagikan
Komentar
0/400
DeadTrades_Walking
· 9jam yang lalu
Kompresi domain sudah dimainkan ya
Lihat AsliBalas0
zkProofInThePudding
· 9jam yang lalu
Tidak ada kemampuan, hanya membuang sedikit ruang.
Binius: Optimalisasi dan Inovasi STARKs Berbasis Domain Biner
Analisis Prinsip Binius STARKs dan Pemikiran Optimasi
1 Pendahuluan
Berbeda dengan SNARKs yang berbasis kurva elips, STARKs dapat dianggap sebagai SNARKs yang berbasis hash. Salah satu alasan utama efisiensi STARKs yang rendah saat ini adalah: sebagian besar nilai dalam program praktis cukup kecil, seperti indeks loop, nilai boolean, penghitung, dan sebagainya. Namun, untuk memastikan keamanan pembuktian berbasis pohon Merkle, saat menggunakan pengkodean Reed-Solomon untuk memperluas data, banyak nilai redundan akan memakan seluruh domain, bahkan jika nilai asli sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.
Generasi pertama STARKs memiliki lebar kode 252 bit, generasi kedua 64 bit, dan generasi ketiga 32 bit, tetapi kode 32 bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, bidang biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa pemborosan, dapat dianggap sebagai generasi keempat STARKs.
Dibandingkan dengan bidang terbatas yang ditemukan dalam beberapa tahun terakhir seperti Goldilocks, BabyBear, dan Mersenne31, penelitian bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah banyak diterapkan dalam kriptografi, seperti AES(F28 field), GMAC(F2128 field), dan pengkodean Reed-Solomon QR code(F28, dan lain-lain. Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk final SHA-3 juga didasarkan pada bidang F28.
Saat 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 ketersediaan. Kebanyakan polinomial yang terlibat dalam perhitungan Prover hanya perlu dioperasikan di bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu dilakukan di bidang perluasan yang lebih besar untuk memastikan keamanan yang diperlukan.
Ada dua masalah praktis saat membangun sistem bukti berdasarkan domain biner:
Binius mengusulkan solusi inovatif untuk menangani kedua masalah ini:
Metode ini secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi sambil memastikan keamanan.
2 Analisis Prinsip
Saat ini, sebagian besar sistem SNARKs biasanya terdiri dari dua bagian:
Bukti interaksi polinomial teori informasi oracle ( PIOP ): Sebagai inti dari sistem bukti, mengubah hubungan perhitungan yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Melalui interaksi dengan verifier, prover secara bertahap mengirimkan polinomial, sehingga verifier dapat memverifikasi kebenaran perhitungan dengan mengquery sedikit hasil evaluasi polinomial. Protokol PIOP yang ada mencakup PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP.
Skema komitmen polinomial (PCS): Digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP valid. PCS adalah alat kriptografi, di mana pembuktinya dapat berkomitmen pada suatu polinomial dan kemudian memverifikasi hasil evaluasinya, sambil menyembunyikan informasi lain tentang polinomial tersebut. PCS yang umum digunakan meliputi KZG, Bulletproofs, FRI, dan Brakedown.
Berdasarkan kebutuhan, pilih PIOP dan PCS yang berbeda, dan menggabungkannya dengan bidang terbatas atau kurva elips yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Contoh:
Binius mencakup lima teknologi kunci:
Aritmetisasi berbasis domain biner bertower: membentuk dasar perhitungan, mewujudkan operasi yang disederhanakan dalam domain biner
Modifikasi pemeriksaan produk dan permutasi HyperPlonk: memastikan pemeriksaan konsistensi yang efisien antara variabel dan permutasi
Bukti pergeseran multilinear baru: Mengoptimalkan efisiensi verifikasi hubungan multilinear di bidang kecil
Meningkatkan bukti pencarian Lasso: memberikan fleksibilitas dan keamanan pada mekanisme pencarian
Skema komitmen polinomial kecil: Mewujudkan sistem bukti yang efisien di atas bidang biner, mengurangi biaya terkait bidang besar.
( 2.1 Ruang Terbatas: Arithmetisasi berdasarkan towers of binary fields
Domain biner bertingkat adalah kunci untuk mencapai perhitungan yang cepat dan dapat diverifikasi, terutama karena perhitungan yang efisien dan aritmatika yang efisien. Domain biner pada dasarnya mendukung operasi aritmatika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Struktur domain biner mendukung proses aritmetisasi yang disederhanakan, di mana operasi yang dilakukan di atas domain biner dapat direpresentasikan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkis melalui struktur menara, membuat domain biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.
"canonical" merujuk pada cara unik dan langsung untuk merepresentasikan elemen dalam domain biner. Misalnya, dalam domain biner dasar F2, 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 standar dalam jumlah bit tertentu. Meskipun domain prima 32-bit dapat dimasukkan dalam 32-bit, tidak setiap string 32-bit dapat secara unik sesuai dengan satu elemen domain, sementara domain 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 oleh AES ###, reduksi Montgomery ( seperti yang digunakan oleh 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 perlu memperkenalkan carry dalam operasi penjumlahan dan perkalian, dan operasi kuadrat pada bidang biner sangat efisien karena mengikuti aturan penyederhanaan (X + Y)2 = X2 + Y2.
Sebuah string 128-bit dapat diinterpretasikan dalam konteks domain biner dengan berbagai cara. Ini dapat dianggap sebagai elemen unik dalam domain biner 128-bit, atau diurai menjadi dua elemen domain tower 64-bit, empat elemen domain tower 32-bit, enam belas elemen domain tower 8-bit, atau seratus dua puluh delapan elemen domain F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi tambahan, hanya konversi tipe string bit, adalah atribut yang sangat menarik dan berguna. Sementara itu, elemen domain kecil dapat dikemas menjadi elemen domain yang lebih besar tanpa biaya komputasi tambahan. Protokol Binius memanfaatkan fitur ini untuk meningkatkan efisiensi komputasi.
Makalah "On Efficient Inversion in Tower Fields of Characteristic Two" membahas kompleksitas komputasi untuk operasi perkalian, kuadrat, dan invers dalam bidang biner tower n-bit yang dapat direduksi menjadi subbidang m-bit (.
![Bitlayer Research：Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(
) 2.2 PIOP: Versi Adaptasi HyperPlonk Product dan PermutationCheck------Cocok untuk bidang biner
Desain PIOP dalam protokol Binius mengacu pada HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan kumpulan multivariat:
GateCheck: Memverifikasi apakah saksi rahasia ω dan input publik x memenuhi hubungan operasi sirkuit C(x,ω)=0, memastikan sirkuit berfungsi dengan benar.
PermutationCheck: Memverifikasi apakah hasil evaluasi dari dua polinomial multivariat f dan g di kubus Boolean adalah hubungan permutasi f###x( = f)π(x)(, memastikan konsistensi permutasi antar variabel polinomial.
LookupCheck: Memverifikasi apakah nilai polinomial berada dalam tabel pencarian yang diberikan, yaitu f(Bμ) ⊆ T)Bμ(, memastikan bahwa beberapa nilai berada dalam rentang yang ditentukan.
MultisetCheck: Memeriksa apakah dua himpunan 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, memastikan kebenaran produk polinomial.
ZeroCheck: Memverifikasi apakah suatu polinomial multivariat pada hiperkubus Boolean di titik mana pun adalah nol ∏x∈Hμ f)x( = 0, ∀x ∈ Bμ, memastikan distribusi titik nol dari polinomial tersebut.
SumCheck: Memeriksa apakah jumlah dari polinomial multivariat sesuai dengan nilai yang dinyatakan ∑x∈Hμ f)x( = s. Dengan mengubah masalah evaluasi polinomial multivariat menjadi evaluasi polinomial variabel tunggal, kompleksitas perhitungan pihak yang memverifikasi dapat dikurangi. Selain itu, SumCheck juga memungkinkan pemrosesan batch dengan memperkenalkan angka acak, membangun kombinasi linier untuk merealisasikan pemrosesan batch dari 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 di 3 bidang berikut:
Optimasi ProductCheck: Di HyperPlonk, ProductCheck mengharuskan penyebut U selalu tidak nol di seluruh hiperkubus, dan produk harus sama dengan nilai tertentu; Binius menyederhanakan proses pemeriksaan ini dengan mengkhususkan nilai tersebut menjadi 1, mengurangi kompleksitas perhitungan.
Penanganan masalah pembagian dengan nol: HyperPlonk tidak dapat menangani kasus pembagian dengan nol secara memadai, yang mengakibatkan ketidakmampuan untuk menyatakan bahwa U tidak nol di hypercube; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya adalah nol, ProductCheck Binius tetap dapat melanjutkan pemrosesan, memungkinkan untuk diperluas ke nilai produk mana pun.
Periksa Permutasi Lintas Kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung pemeriksaan permutasi antara beberapa kolom, memungkinkan Binius untuk menangani situasi susunan polinomial yang lebih kompleks.
Oleh karena itu, Binius meningkatkan fleksibilitas dan efisiensi protokol melalui perbaikan mekanisme PIOP SumCheck 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 bagi sistem pembuktian berbasis domain biner di masa depan.
![Bitlayer Research: Analisis Prinsip STARKs Binius dan Pemikiran Optimisasi])https://img-cdn.gateio.im/webp-social/moments-d74bdd8bc21dcfc05e21f9c0074461c3.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. Berikut adalah dua metode kunci:
Packing: Metode ini mengoptimalkan operasi dengan mengemas elemen-elemen kecil yang bersebelahan dalam urutan kamus menjadi elemen yang lebih besar. Operator Pack menargetkan operasi blok berukuran 2κ dan menggabungkannya menjadi satu elemen dalam domain berdimensi tinggi. Dengan memperluas secara multiliner (Multilinear Extension, MLE), polinom virtual ini dapat dievaluasi dan diproses secara efisien, mengubah fungsi t menjadi polinom lain, sehingga meningkatkan kinerja komputasi.
Operator pergeseran: Operator pergeseran menyusun ulang elemen dalam blok, berdasarkan offset yang diberikan o untuk melakukan pergeseran siklik. Metode ini berlaku untuk blok berukuran 2b, di mana setiap blok melakukan pergeseran berdasarkan offset. Operator pergeseran didefinisikan melalui dukungan fungsi untuk memastikan konsistensi dan efisiensi saat memproses polinomial virtual. Evaluasi kompleksitas konstruksi ini meningkat secara linier seiring dengan ukuran blok, sangat cocok untuk menangani kumpulan data besar atau skenario berdimensi tinggi dalam hiperkubus Bool.
![Bitlayer Research: Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi]###https://img-cdn.gateio.im/webp-social/moments-7f96976952fd0f8da0e93ff1042a966d.webp(
) 2.4 PIOP: versi modifikasi argumen Lasso lookup------cocok untuk domain biner
Protokol Lasso memungkinkan pihak yang membuktikan untuk berkomitmen pada sebuah vektor a ∈ Fm, dan membuktikan bahwa semua elemennya ada dalam tabel yang ditentukan sebelumnya t ∈ Fn. Lasso membuka konsep "mencari singularitas" (lookup singularities) dan dapat diterapkan pada skema komitmen polinomial multilinier. Efisiensinya terwujud dalam dua aspek berikut: