Analisis Prinsip STARKs Binius dan Pemikiran Optimalisasi

1. Pendahuluan

Salah satu alasan utama efisiensi STARKs yang rendah adalah: sebagian besar nilai dalam program nyata relatif kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dan sebagainya. Namun, untuk memastikan keamanan bukti berbasis pohon Merkle, saat menggunakan pengkodean Reed-Solomon untuk memperluas data, 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 dalam 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, bidang biner memungkinkan operasi langsung pada bit, menghasilkan pengkodean yang kompak dan efisien tanpa ruang yang terbuang, yaitu STARKs generasi keempat.

| Aljabar | Lebar Kode | Implementasi Tipikal | |------|----------|----------| | Generasi 1 | 252bit | StarkWare |
| Generasi ke-2 | 64bit | Plonky2 | | Generasi ke-3 | 32bit | Plonky3 | | Generasi ke-4 | 1bit | Binius |

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 tipikalnya termasuk:

• Standar Enkripsi Tingkat Lanjut (AES), berdasarkan bidang F2^8
• Galois Message Authentication Code ( GMAC ), berbasis pada bidang F2^128
• QR code, menggunakan pengkodean Reed-Solomon berbasis F2^8
• Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk final SHA-3, yang berdasarkan pada bidang F2^8, adalah algoritma hash yang sangat cocok untuk rekursi.

Ketika menggunakan bidang yang lebih kecil, operasi perluasan 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, tetapi hanya perlu beroperasi di bawah bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu mendalami bidang perluasan yang lebih besar untuk memastikan keamanan yang diperlukan.

Ketika membangun sistem bukti berdasarkan domain biner, terdapat 2 masalah praktis: saat menghitung representasi jejak di STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; saat melakukan komitmen pohon Merkle di STARKs, perlu dilakukan pengkodean Reed-Solomon, ukuran domain yang digunakan harus lebih besar dari ukuran setelah pengkodean diperluas.

Binius mengajukan solusi inovatif untuk menangani kedua masalah ini secara terpisah, dan mewujudkannya dengan menyajikan data yang sama dalam dua cara berbeda: pertama, menggunakan multivariat ( yang khususnya adalah polinomial multilinear ) sebagai pengganti polinomial univariat, dengan merepresentasikan seluruh jejak komputasi melalui nilai-nilainya pada "hypercube" ( hypercubes ); kedua, karena panjang setiap dimensi hypercube adalah 2, maka tidak dapat dilakukan ekstensi Reed-Solomon standar seperti pada STARKs, tetapi hypercube dapat dipandang sebagai persegi ( square ), yang digunakan sebagai dasar untuk ekstensi Reed-Solomon. Metode ini sangat meningkatkan efisiensi pengkodean dan kinerja komputasi sambil memastikan keamanan.

2. Analisis Prinsip

Konstruksi sistem SNARKs saat ini umumnya terdiri dari dua bagian berikut:

• Bukti Oracle Interaktif Polinomial Teori Informasi (: PIOP) sebagai inti dari sistem bukti, mengubah hubungan perhitungan yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Protokol PIOP yang berbeda memungkinkan pembuktian untuk mengirimkan polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah perhitungan benar hanya dengan menanyakan hasil evaluasi dari sejumlah kecil polinomial. Protokol PIOP yang ada termasuk: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara penanganan ekspresi polinomial yang berbeda, sehingga mempengaruhi kinerja dan efisiensi seluruh sistem SNARK.

• Skema Komitmen Polinomial (Polynomial Commitment Scheme, PCS): Skema komitmen polinomial digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP valid. PCS adalah alat kriptografi, melalui mana, penjamin dapat mengkomit suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain tentang polinomial. Skema komitmen polinomial yang umum termasuk KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) dan Brakedown, dll. Berbagai PCS memiliki kinerja, keamanan, dan skenario penerapan 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: Mengadopsi PLONK PIOP dan FRI PCS yang digabungkan, dan didasarkan pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem ini, PIOP dan PCS yang dipilih harus sesuai dengan bidang terbatas 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 pengaturan terpercaya, serta apakah dapat mendukung fungsi tambahan seperti bukti rekurif atau bukti agregat.

Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanannya. Pertama, berdasarkan aritmetika bidang biner (towers of binary fields), yang membentuk dasar perhitungan, dapat melakukan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol bukti Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol memperkenalkan bukti pergeseran multilinear baru yang mengoptimalkan efisiensi verifikasi hubungan multilinear di bidang kecil. Keempat, Binius menggunakan bukti pencarian versi yang ditingkatkan, memberikan fleksibilitas dan keamanan yang kuat pada mekanisme pencarian. Terakhir, protokol menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), yang memungkinkannya untuk mewujudkan sistem bukti yang efisien di bidang biner, dan mengurangi overhead yang biasanya terkait dengan bidang besar.

2.1 Ruang Terbatas: Aritmetika berdasarkan towers of binary fields

Bidang biner berbentuk tumpukan adalah kunci untuk mewujudkan perhitungan yang cepat dan dapat diverifikasi, 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 dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Ciri-ciri ini, ditambah kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur tumpukan, menjadikan bidang biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.

Di mana "canonical" merujuk pada cara representasi yang unik dan langsung dari elemen dalam medan biner. Misalnya, dalam medan biner yang paling dasar F2, string k-bit mana pun dapat dipetakan langsung ke elemen medan biner k-bit. Ini berbeda dengan medan prima, yang tidak dapat memberikan representasi normatif ini dalam jumlah bit yang ditentukan. Meskipun medan prima 32-bit dapat diwakili dalam 32-bit, tidak setiap string 32-bit dapat secara unik terkait dengan elemen medan, sementara medan biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam medan prima Fp, metode reduksi yang umum termasuk reduksi Barrett, reduksi Montgomery, serta metode reduksi khusus untuk medan terbatas tertentu seperti Mersenne-31 atau Goldilocks-64. Dalam medan 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 medan biner tidak memerlukan pengenalan carry dalam operasi penjumlahan dan perkalian, dan operasi kuadrat dalam medan biner sangat efisien, karena mengikuti aturan penyederhanaan (X + Y )^2 = X^2 + Y^2.

Seperti yang ditunjukkan pada Gambar 1, sebuah string 128-bit: String ini dapat diinterpretasikan dalam konteks domain biner dengan berbagai cara. Ini 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 konversi tipe string bit (typecast), yang merupakan atribut yang sangat menarik dan berguna. Pada saat yang sama, 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 tower biner n-bit ( yang dapat direduksi menjadi subdomain m-bit ).

( 2.2 PIOP: Versi Modifikasi Produk HyperPlonk dan PermutationCheck ------ Cocok untuk Domain 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 mencakup:

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

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

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

5. 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.

6. ZeroCheck: Memverifikasi apakah suatu polinomial multivariat di hiperkubus Bool pada titik mana pun adalah nol ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, untuk memastikan distribusi titik nol 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 variabel tunggal, mengurangi kompleksitas komputasi bagi pihak yang memverifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan angka acak, membangun kombinasi linier untuk menangani beberapa contoh verifikasi jumlah.

8. BatchCheck: Berdasarkan SumCheck, memvalidasi kebenaran evaluasi beberapa polinomial multivariabel untuk meningkatkan efisiensi protokol.

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

• Optimasi ProductCheck: Dalam HyperPlonk, ProductCheck mengharuskan penyebut U tidak boleh 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 dapat menangani situasi pembagian dengan nol secara memadai, yang menyebabkan ketidakmampuan untuk memastikan bahwa U bukan nol pada hiperkubus; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya nol, ProductCheck Binius masih dapat melanjutkan pemrosesan, memungkinkan perluasan ke nilai hasil kali mana pun.

• PermutationCheck Lintas Kolom: HyperPlonk tidak memiliki fungsi ini; Binius mendukung PermutationCheck di antara beberapa kolom, yang memungkinkan Binius untuk 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 verifikasi polinomial multivariat yang lebih kompleks, menyediakan 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, konstruksi dan pengolahan polinomial virtual adalah salah satu teknologi kunci yang dapat menghasilkan dengan efektif.