Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi

1 Pendahuluan

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

Seperti yang ditunjukkan pada Tabel 1, 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, domain biner memungkinkan operasi langsung pada bit, pengkodean yang kompak dan efisien tanpa ruang yang terbuang, yaitu STARKs generasi keempat.

Tabel 1: Jalur Derivasi STARKs

| Urutan | Lebar Bit | Deskripsi | |------|------|------| | Generasi 1 | 252bit | Berdasarkan bidang bilangan prima | | Generasi 2 | 64bit | Domain Goldilocks | | Generasi ke-3 | 32bit | Domain Babybear | | Generasi ke-4 | 1bit | Domain biner |

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

• Standard Enkripsi Tingkat Lanjut ( AES ), berbasis pada domain 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 memasuki final SHA-3, yang didasarkan pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursi.

Ketika menggunakan bidang yang lebih kecil, operasi perpanjangan bidang menjadi semakin penting untuk memastikan keamanan. Bidang biner yang digunakan oleh Binius sepenuhnya bergantung pada perpanjangan bidang untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu memasuki perpanjangan bidang, dan hanya perlu beroperasi di bawah bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu mendalami perpanjangan bidang yang lebih besar untuk memastikan keamanan yang diperlukan.

Saat membangun sistem bukti berdasarkan domain biner, terdapat 2 masalah praktis: saat menghitung representasi trace dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; saat melakukan komitmen Merkle tree dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, ukuran domain yang digunakan harus lebih besar dari ukuran setelah perpanjangan pengkodean.

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 khusus adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan menyatakan seluruh jejak perhitungan melalui nilai-nilainya di "hiperkubus" ( hypercubes ); kedua, karena setiap dimensi hiperkubus memiliki panjang 2, maka tidak dapat dilakukan perpanjangan Reed-Solomon standar seperti STARKs, tetapi hiperkubus dapat dipandang sebagai persegi ( square ), dan perpanjangan Reed-Solomon dapat dilakukan berdasarkan persegi tersebut. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja perhitungan.

2 Analisis Prinsip

Kebanyakan sistem SNARK saat ini biasanya terdiri dari dua bagian berikut:

• Teori informasi bukti interaktif polinomial oracle (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti sistem bukti, mengubah hubungan komputasi input menjadi persamaan polinomial yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan penyintas untuk mengirimkan polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah komputasi benar hanya dengan menanyakan hasil evaluasi sedikit polinomial. Protokol PIOP yang ada termasuk: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara yang berbeda dalam menangani ekspresi polinomial, sehingga 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 valid. PCS adalah alat kriptografi, melalui mana, pembuktian dapat berkomitmen pada polin tertentu dan kemudian memverifikasi hasil evaluasi polin tersebut, sambil menyembunyikan informasi lain tentang polin. 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 bidang terbatas atau kurva elips yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Contohnya:

• Halo2: dikombinasikan dari PLONK PIOP dan Bulletproofs PCS, dan 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 rekursif 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. Pilihan kombinasi ini tidak hanya mempengaruhi ukuran bukti SNARK dan efisiensi verifikasi, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa pengaturan yang dapat dipercaya, dan apakah dapat mendukung bukti rekursif atau bukti agregasi dan fungsi ekstensi lainnya.

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 dari komputasinya, yang memungkinkan operasi yang disederhanakan di dalam bidang biner. Kedua, Binius dalam protokol bukti Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, yang memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol ini memperkenalkan bukti pergeseran multilinear baru, yang mengoptimalkan efisiensi verifikasi hubungan multilinear di bidang kecil. Keempat, Binius menggunakan bukti pencarian Lasso yang ditingkatkan, yang 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 bukti yang efisien di atas bidang biner dan mengurangi biaya yang biasanya terkait dengan bidang besar.

2.1 Ruang Terbatas: Aritmetika berdasarkan menara bidang biner

Bidang biner bertingkat adalah kunci untuk mewujudkan komputasi yang cepat dan dapat diverifikasi, terutama karena dua aspek: komputasi yang efisien dan aritmetika 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 aritmetika yang disederhanakan, yaitu operasi yang dilakukan di atas bidang biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur bertingkat, menjadikan bidang biner sangat cocok untuk sistem pembuktian yang dapat diperluas seperti Binius.

"Canonical" mengacu pada cara unik dan langsung untuk merepresentasikan elemen dalam bidang biner. Misalnya, dalam bidang biner paling dasar F2, string k-bit mana pun dapat dipetakan langsung ke elemen bidang biner k-bit. Ini berbeda dengan bidang prima, yang tidak dapat memberikan representasi standar semacam itu dalam jumlah bit yang ditentukan. Meskipun bidang prima 32-bit dapat dimasukkan dalam 32-bit, tidak semua string 32-bit dapat secara unik dikaitkan dengan elemen bidang, sementara bidang biner memiliki kenyamanan pemetaan satu-ke-satu semacam 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 ada kebutuhan untuk membawa dalam operasi penjumlahan dan perkalian, dan operasi kuadrat dalam bidang biner sangat efisien, karena mengikuti aturan penyederhanaan (X + Y )2 = X2 + Y2.

Seperti yang ditunjukkan pada Gambar 1, sebuah string 128-bit: string ini dapat diinterpretasikan dalam konteks bidang biner dengan berbagai cara. Ini dapat dianggap sebagai elemen unik dalam bidang biner 128-bit, atau diuraikan menjadi dua elemen bidang menara 64-bit, empat elemen bidang menara 32-bit, enam belas elemen bidang menara 8-bit, atau 128 elemen bidang F2. Fleksibilitas representasi ini tidak memerlukan beban 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 membutuhkan beban 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 invers dalam bidang biner menara n-bit yang dapat diuraikan 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 modifikasi Produk HyperPlonk dan PermutationCheck------cocok untuk bidang biner

Desain PIOP dalam protokol Binius mengacu pada HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi keakuratan polinomial dan kumpulan multivariat. Mekanisme pemeriksaan inti ini meliputi:

1. GateCheck: Memverifikasi apakah 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 multivariabel f dan g di hiperkubus Boolean merupakan hubungan permutasi f)x( = f)π(x(), untuk memastikan konsistensi pengurutan antara variabel polinomial.

3. LookupCheck: Memverifikasi apakah evaluasi 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 di antara beberapa kumpulan.

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

6. ZeroCheck: Memverifikasi apakah sebuah polinomial multivariat pada hiper kubus 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 dari polinomial multivariat sama dengan nilai yang dinyatakan ∑x∈Hµ f)x( = s. Dengan mengubah masalah evaluasi polinomial multivariat menjadi evaluasi polinomial univariat, mengurangi kompleksitas komputasi pihak yang memverifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan angka acak, membangun kombinasi linear untuk melakukan pemrosesan batch pada beberapa contoh verifikasi jumlah.

8. BatchCheck: Berdasarkan SumCheck, memverifikasi kebenaran evaluasi banyak polinomial multivariat untuk meningkatkan efisiensi protokol.

Meskipun Binius dan HyperPlonk memiliki banyak kesamaan dalam desain protokol, Binius melakukan perbaikan dalam 3 aspek berikut:

• Optimasi ProductCheck: Dalam HyperPlonk, ProductCheck mengharuskan penyebut U tidak nol di seluruh hiperkubus, dan produknya 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, yang mengakibatkan tidak dapat memastikan bahwa U tidak nol pada hypercube; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius tetap dapat melanjutkan pemrosesan, memungkinkan perpanjangan 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 untuk 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 domain biner di masa depan.

) 2.3 PIOP: argumen pergeseran multilinear baru------cocok untuk hypercube boolean

Dalam protokol Binius, multi virtual