Analisis Prinsip Binius STARKs dan Pemikiran Optimalisasinya

1. Pendahuluan

Salah satu alasan utama efisiensi STARKs yang rendah adalah: sebagian besar nilai dalam program nyata cukup kecil, tetapi untuk memastikan keamanan bukti berbasis pohon Merkle, ketika data diperluas menggunakan pengkodean Reed-Solomon, banyak nilai redundan tambahan akan mengambil seluruh domain, meskipun nilai asli itu sendiri sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.

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

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

• Standar Enkripsi Lanjutan (AES), berbasis domain F28
• Galois Message Authentication Code ( GMAC ), berbasis pada bidang F2128
• QR kode, menggunakan pengkodean 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 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. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam perluasan bidang, dan hanya perlu beroperasi di 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 praktis: ukuran domain yang digunakan saat menghitung representasi jejak dalam STARKs harus lebih besar dari derajat polinomial; saat komitmen pohon Merkle dalam STARKs, perlu melakukan pengkodean Reed-Solomon, ukuran domain yang digunakan harus lebih besar dari ukuran setelah ekstensi pengkodean.

Binius mengajukan solusi inovatif untuk menangani kedua masalah ini secara terpisah, dan mewakili data yang sama dengan dua cara berbeda: pertama, dengan menggunakan polinomial multivariat ( yang secara khusus adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan merepresentasikan seluruh jejak komputasi melalui nilai-nilainya pada "hiperkubus" ( hypercubes ); kedua, karena setiap dimensi hiperkubus memiliki panjang 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti STARKs, tetapi hiperkubus dapat dipandang sebagai kotak ( square ), dan perluasan Reed-Solomon dapat dilakukan berdasarkan kotak tersebut. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.

2. Analisis Prinsip

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

• Bukti Oracle Interaktif Polinomial Teoritis Informasi (: PIOP) sebagai inti 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 memeriksa hasil evaluasi sejumlah kecil polinomial. Protokol PIOP yang ada termasuk: PIOP PLONK, PIOP Spartan, dan PIOP HyperPlonk, yang masing-masing memiliki cara penanganan ekspresi polinomial yang berbeda, yang pada gilirannya mempengaruhi kinerja dan efisiensi seluruh sistem SNARK.

• Skema Komitmen Polin(Polynomial Commitment Scheme, PCS): Skema komitmen polin digunakan untuk membuktikan apakah persamaan polin yang dihasilkan oleh PIOP adalah valid. PCS adalah alat kriptografi, melalui mana, pembuktian dapat mengkomit sebuah polin dan kemudian memverifikasi hasil evaluasi polin tersebut, sambil menyembunyikan informasi lain tentang polin tersebut. Skema komitmen polin yang umum antara lain 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 bidang terbatas atau kurva elips yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Contohnya:

• Halo2: Dikembangkan dari kombinasi PLONK PIOP dan Bulletproofs PCS, serta berbasis pada kurva Pasta. Halo2 dirancang dengan fokus pada skalabilitas dan penghapusan trusted setup dalam protokol ZCash.

• Plonky2: Menggunakan PLONK PIOP dan FRI PCS yang digabungkan, dan berbasis pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Saat 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. Pilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti SNARK dan efisiensi verifikasi, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa perlu pengaturan tepercaya, serta apakah dapat mendukung fungsi-fungsi tambahan seperti bukti rekursif atau bukti agregasi.

Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, aritmetika berbasis menara bidang biner (towers of binary fields) membentuk dasar perhitungan, memungkinkan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol pembuktian Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol memperkenalkan pembuktian pergeseran multilinier baru, mengoptimalkan efisiensi verifikasi hubungan multilinier 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 berbasis menara bidang biner

Domain biner tower adalah kunci untuk mewujudkan komputasi yang cepat dan dapat diverifikasi, terutama karena dua aspek: komputasi yang efisien dan aritmetika yang efisien. Domain biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang peka terhadap kinerja. Selain itu, struktur domain biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan di atas domain biner dapat direpresentasikan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya sifat hierarkis melalui struktur tower, membuat domain biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.

Di mana "canonical" merujuk pada cara unik dan langsung untuk merepresentasikan elemen di dalam domain biner. Misalnya, dalam domain biner paling dasar F2, string dengan panjang k dapat dipetakan langsung ke elemen domain biner dengan panjang k. Ini berbeda dengan domain bilangan prima, di mana domain bilangan prima tidak dapat memberikan representasi yang sesuai dalam jumlah bit tertentu. Meskipun domain bilangan prima 32-bit dapat diakomodasi dalam 32 bit, tidak semua string 32-bit dapat secara unik berkorespondensi dengan elemen domain, sementara domain biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam domain bilangan prima Fp, metode reduksi yang 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, baik operasi penjumlahan maupun perkalian tidak memerlukan pembawaan, dan operasi kuadrat di 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 bidang biner. Ini dapat dianggap sebagai elemen unik dalam bidang biner 128-bit, atau diuraikan menjadi 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 apapun, hanya konversi tipe string bit (typecast), yang merupakan atribut yang sangat menarik dan berguna. Pada saat yang sama, 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 untuk perkalian, kuadrat, dan operasi invers dalam bidang tower biner n-bit yang dapat direduksi menjadi subfield 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 Adaptasi Produk HyperPlonk dan PermutationCheck------Cocok untuk domain biner

Desain PIOP dalam protokol Binius mengadopsi HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi keakuratan polinomial dan kumpulan variabel multivariabel. Mekanisme pemeriksaan inti ini mencakup:

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

2. PermutationCheck: Memverifikasi apakah hasil evaluasi dari dua polinomial multivariat f dan g di hiper-kubus Boolean adalah hubungan permutasi f)x( = f)π(x(), untuk memastikan konsistensi pengaturan antara variabel polinomial.

3. LookupCheck: Memverifikasi apakah nilai polinomial ada dalam tabel pencarian yang diberikan, yaitu f)Bµ( ⊆ T)Bµ(, memastikan bahwa 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 memastikan konsistensi antar beberapa kumpulan.

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

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

7. SumCheck: Memeriksa apakah jumlah polinomial multivariat sesuai dengan nilai yang dinyatakan ∑x∈Hµ f)x( = s. Dengan mengubah masalah evaluasi polinomial multivariat menjadi evaluasi polinomial variabel tunggal, mengurangi kompleksitas perhitungan pihak yang memverifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan bilangan acak, membangun kombinasi linear untuk memproses beberapa contoh pemeriksaan 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 di 3 bidang berikut:

• Optimasi ProductCheck: Di 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 gagal menangani situasi pembagian dengan nol secara memadai, yang menyebabkan ketidakmampuan untuk menyatakan masalah non-nol U di hiperkubus; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebut adalah nol, ProductCheck Binius masih dapat melanjutkan pemrosesan, memungkinkan untuk diperluas ke nilai produk mana pun.

• PermutationCheck antar kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung PermutationCheck di antara beberapa kolom, yang memungkinkan Binius untuk menangani situasi pengaturan polinomial yang lebih kompleks.

Oleh karena itu, Binius telah meningkatkan fleksibilitas dan efisiensi protokol melalui perbaikan pada mekanisme PIOPSumCheck yang ada, terutama dalam menangani verifikasi polinomial multivariat yang lebih kompleks, menyediakan dukungan fungsi yang lebih kuat. Perbaikan ini tidak hanya mengatasi batasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem bukti yang berbasis pada domain biner di masa depan.

![Bitlayer Research：Analisis Prinsip STARKs Binius dan Pemikiran Optimisasinya])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(

) 2.3 PIOP: argumen pergeseran multilinear baru ------ berlaku 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 mengemas elemen-elemen yang lebih kecil yang berdekatan dalam urutan kamus menjadi elemen yang lebih besar.