Analisis Prinsip STARKs Binius dan Pemikiran Optimalisasi

1 Pendahuluan

Berbeda dengan SNARKs berbasis kurva elips, STARKs dapat dianggap sebagai SNARKs 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 memastikan keamanan pembuktian berbasis pohon Merkle, saat menggunakan pengkodean Reed-Solomon untuk memperluas data, banyak nilai redundan tambahan akan menempati seluruh domain, meskipun nilai asli itu sendiri sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.

Generasi pertama lebar kode STARKs adalah 252bit, generasi kedua lebar kode STARKs adalah 64bit, generasi ketiga lebar kode STARKs adalah 32bit, tetapi lebar kode 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, bidang biner memungkinkan operasi langsung pada bit, pengkodean yang padat dan efisien tanpa ruang yang terbuang, yaitu generasi keempat STARKs.

Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian terbatas lainnya yang ditemukan dalam beberapa tahun terakhir, penelitian tentang bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah banyak diterapkan dalam kriptografi, dengan contoh khas termasuk:

• Standar Enkripsi Tingkat Lanjut (AES), berbasis bidang F28;

• Galois Message Authentication Code ( GMAC ), berbasis pada domain F2128;

• Kode QR, menggunakan pengkodean Reed-Solomon berbasis F28;

• Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk ke final SHA-3, yang berbasis pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursi.

Saat menggunakan bidang yang lebih kecil, operasi perluasan bidang menjadi semakin penting untuk memastikan keamanan. Bidang biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan bidang untuk menjamin keamanan dan kegunaan praktisnya. Kebanyakan polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam perluasan bidang, tetapi cukup beroperasi di bawah bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu menyelami perluasan bidang yang lebih besar untuk memastikan keamanan yang diperlukan.

Saat membangun sistem bukti berdasarkan domain biner, ada 2 masalah praktis: saat menghitung representasi jejak dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; saat melakukan komitmen pohon Merkle dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, 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 ( khususnya polinomial multilinier ) sebagai pengganti polinomial univariat, dengan mewakili seluruh lintasan komputasi melalui nilai-nilainya pada "hiperkubus" ( hypercubes ); kedua, karena setiap dimensi hiperkubus memiliki panjang 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti pada STARKs, tetapi hiperkubus dapat dipandang sebagai persegi ( square ), dan melakukan perluasan Reed-Solomon berdasarkan persegi tersebut. Metode ini sangat meningkatkan efisiensi pengkodean dan kinerja komputasi sambil memastikan keamanan.

2 Analisis Prinsip

Konstruksi sebagian besar sistem SNARK saat ini biasanya terdiri dari dua bagian berikut:

• Teori informasi bukti orakel interaktif polinomial (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti dari sistem bukti, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan pembuktian untuk secara bertahap mengirimkan polinomial melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah perhitungan benar dengan hanya menanyakan sejumlah kecil hasil evaluasi polinomial. Protokol PIOP yang ada mencakup: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara berbeda dalam menangani ekspresi polinomial, sehingga mempengaruhi kinerja dan efisiensi keseluruhan sistem SNARK.

• Skema Komitmen Polin (Polynomial Commitment Scheme, PCS): Skema komitmen polin 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, sambil menyembunyikan informasi lain tentang polinomial. Skema komitmen polin yang umum termasuk KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) dan Brakedown, dll. Berbagai PCS memiliki kinerja, keamanan, dan skenario aplikasi yang berbeda.

Berdasarkan kebutuhan spesifik, pilih PIOP dan PCS yang berbeda, dan kombinasikan dengan domain terbatas atau kurva eliptik yang tepat, sehingga dapat membangun sistem pembuktian dengan atribut yang berbeda. Contoh:

• Halo2: dikombinasikan dari PLONK PIOP dan Bulletproofs PCS, dan didasarkan pada kurva Pasta. Dalam desain Halo2, perhatian diberikan pada skalabilitas, serta menghapus trusted setup dalam protokol ZCash.

• Plonky2: Mengadopsi kombinasi PLONK PIOP dan FRI PCS, serta berbasis pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem-sistem ini, PIOP dan PCS yang dipilih harus sesuai dengan bidang hingga atau kurva elips yang digunakan, untuk memastikan kebenaran, kinerja, dan keamanan sistem. Pemilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti SNARK dan efisiensi verifikasi, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa memerlukan pengaturan yang terpercaya, dan apakah dapat mendukung fungsi-fungsi ekstensi seperti bukti rekursif 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 komputasinya, yang memungkinkan untuk melakukan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol pembuktian Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan substitusi HyperPlonk, memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan substitusinya. 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 pada mekanisme pencarian. Terakhir, protokol menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), memungkinkan untuk sistem pembuktian yang efisien di bidang biner dan mengurangi biaya yang biasanya terkait dengan bidang besar.

2.1 Ruang Terbatas: Aritmetika Berdasarkan Towers of Binary Fields

Bidang biner bertingkat adalah kunci untuk mewujudkan perhitungan yang dapat diverifikasi dengan cepat, terutama disebabkan oleh dua aspek: perhitungan yang efisien dan aritmetika yang efisien. Bidang biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur bidang biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan di bidang biner dapat direpresentasikan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkis melalui struktur menara, menjadikan bidang biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.

Di mana "canonical" mengacu pada representasi yang unik dan langsung dari elemen dalam domain biner. Misalnya, dalam domain biner dasar F2, string k-bit mana pun dapat langsung dipetakan ke elemen domain biner k-bit. Ini berbeda dengan domain bilangan prima, di mana domain bilangan prima tidak dapat memberikan representasi standar ini dalam jumlah bit yang ditentukan. Meskipun domain bilangan prima 32-bit dapat disertakan dalam 32-bit, tidak semua string 32-bit dapat secara unik sesuai dengan elemen domain, sedangkan domain biner memiliki kenyamanan pemetaan satu-ke-satu ini. Dalam domain bilangan prima Fp, metode reduksi umum termasuk reduksi Barrett, reduksi Montgomery, serta metode reduksi khusus untuk domain terbatas tertentu seperti Mersenne-31 atau Goldilocks-64. Dalam domain 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 domain biner, operasi penjumlahan dan 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 dalam konteks domain biner dengan berbagai cara. 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 seratus dua puluh delapan elemen domain F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi tambahan, hanya sekadar konversi tipe dari 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 di domain tower biner n-bit yang dapat diuraikan menjadi subdomain m-bit (.

![Bitlayer Research: Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(

) 2.2 PIOP: versi modifikasi HyperPlonk Product dan PermutationCheck------cocok untuk bidang biner

Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan kumpulan multivariat. Mekanisme pemeriksaan inti ini meliputi:

1. GateCheck: Verifikasi bahwa saksi rahasia ω dan input publik x memenuhi hubungan operasi sirkuit C###x, ω(=0, untuk memastikan sirkuit berfungsi dengan benar.

2. PermutationCheck: Memverifikasi apakah hasil evaluasi dari dua polinomial multivariat f dan g di hiperkubus Boolean adalah hubungan permutasi f)x( = f)π(x(), untuk memastikan konsistensi pengurutan antar variabel polinomial.

3. LookupCheck: Memverifikasi apakah evaluasi polinomial ada dalam tabel pencarian yang diberikan, yaitu f)Bµ( ⊆ T)Bµ(, memastikan beberapa nilai berada dalam rentang yang ditentukan.

4. MultisetCheck: Memeriksa apakah dua kumpulan multivariat sama, yaitu {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, untuk menjamin konsistensi antar beberapa kumpulan.

5. ProductCheck: Memeriksa apakah evaluasi polinomial rasional pada hiper kubus Boolean sama dengan nilai yang dinyatakan ∏x∈Hµ f)x( = s, untuk memastikan kebenaran produk polinomial.

6. ZeroCheck: Memverifikasi apakah polinomial multivariat pada hypercube Boolean di titik mana pun adalah nol ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, untuk memastikan distribusi titik nol polinomial.

7. SumCheck: Memeriksa apakah jumlah nilai polinomial multivariat sama dengan nilai yang dinyatakan ∑x∈Hµ f)x( = s. Dengan mengubah masalah evaluasi polinomial multivariabel menjadi evaluasi polinomial univariat, mengurangi kompleksitas komputasi pihak verifikasi. Selain itu, SumCheck juga memungkinkan pengolahan batch dengan memperkenalkan bilangan acak, membangun kombinasi linier untuk mengimplementasikan pengolahan batch pada beberapa contoh verifikasi jumlah.

8. 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 hypercube, dan hasil kali harus sama dengan nilai tertentu; Binius menyederhanakan proses pemeriksaan ini dengan mengkhususkan nilai tersebut menjadi 1, sehingga mengurangi kompleksitas perhitungan.

• Penanganan masalah pembagian dengan nol: HyperPlonk tidak dapat menangani situasi pembagian dengan nol dengan baik, sehingga tidak dapat memastikan bahwa U tidak nol di hypercube; Binius menangani masalah ini dengan benar, bahkan dalam situasi di mana penyebutnya nol, ProductCheck Binius masih dapat melanjutkan proses, memungkinkan untuk diperluas ke nilai produk mana pun.

• Pemeriksaan Permutasi Keterhubungan: HyperPlonk tidak memiliki fungsi ini; Binius mendukung Pemeriksaan Permutasi di antara beberapa kolom, yang memungkinkan Binius menangani situasi pengaturan 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, memberikan dukungan fungsional yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem pembuktian berbasis bidang biner di masa depan.

) 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 menggunakan posisi yang berdekatan dalam urutan kamus yang lebih kecil