Analisis Prinsip Binius STARKs dan Pikirannya tentang Optimasi

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, banyak nilai redundan tambahan akan mengisi seluruh domain saat menggunakan pengkodean Reed-Solomon untuk memperluas data, meskipun nilai aslinya sendiri sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.

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

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

• Standar Enkripsi Lanjutan ( AES ), berdasarkan domain F28;

• Kode otentikasi pesan Galois ( GMAC ), berdasarkan bidang F2128;

• Kode QR, 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.

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 cukup beroperasi di bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih memerlukan pendalaman ke dalam perluasan yang lebih besar untuk memastikan keamanan yang diperlukan.

Ada 2 masalah praktis saat membangun sistem bukti berdasarkan domain biner: saat menghitung representasi jejak dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; saat berkomitmen Merkle tree dalam STARKs, perlu melakukan pengkodean Reed-Solomon, ukuran domain yang digunakan harus lebih besar dari ukuran setelah perluasan 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 multilinear ) sebagai pengganti polinomial univariat, dengan mewakili seluruh jejak perhitungan melalui nilai-nilainya pada "hypercube" ( hypercubes ); kedua, karena panjang setiap dimensi hypercube adalah 2, maka tidak mungkin melakukan perluasan Reed-Solomon standar seperti STARKs, tetapi hypercube dapat dilihat sebagai persegi ( square ), dan berdasarkan persegi tersebut dilakukan perluasan Reed-Solomon. Metode ini memastikan keamanan sambil secara signifikan meningkatkan efisiensi pengkodean dan kinerja perhitungan.

2 Analisis Prinsip

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

• Bukti Oracle Interaktif Polinomial Teori Informasi (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti dari sistem bukti, mengubah hubungan perhitungan yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Protokol PIOP yang berbeda melalui interaksi dengan verifier, memungkinkan penjamin untuk secara bertahap mengirimkan polinomial, sehingga verifier dapat memverifikasi apakah perhitungan benar hanya dengan menanyakan sedikit hasil evaluasi 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 Polinomial (Polynomial Commitment Scheme, PCS): Skema komitmen polinomial digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP adalah benar. 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 polinomial 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: menggabungkan PLONK PIOP dan Bulletproofs PCS, serta 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, serta berdasarkan domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem ini, PIOP dan PCS yang dipilih harus cocok 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 yang dapat dipercaya, serta apakah dapat mendukung fungsi ekspansi seperti bukti rekursif atau bukti agregat.

Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, berdasarkan aritmetika bidang biner (towers of binary fields) yang membentuk dasar perhitungan, mampu melakukan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol pembuktian Oracle interaktifnya (PIOP), telah mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol memperkenalkan bukti pergeseran multilinear baru, mengoptimalkan efisiensi verifikasi hubungan multilinear pada bidang kecil. Keempat, Binius menggunakan versi perbaikan dari bukti pencarian Lasso, 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 berdasarkan menara bidang biner

Domain biner bertingkat adalah kunci untuk mewujudkan perhitungan yang dapat diverifikasi dengan cepat, 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 sensitif terhadap kebutuhan kinerja. Selain itu, struktur domain biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan di atas domain biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkis melalui struktur bertingkat, membuat domain biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.

"Canonical" merujuk pada cara representasi yang unik dan langsung dari elemen dalam bidang biner. Misalnya, dalam bidang biner paling dasar F2, string k-bit mana pun dapat langsung dipetakan ke elemen bidang biner k-bit. Ini berbeda dengan bidang prima, yang tidak dapat menyediakan representasi standar ini dalam jumlah bit tertentu. Meskipun bidang prima 32-bit dapat diakomodasi dalam 32-bit, tidak setiap string 32-bit dapat secara unik berkorelasi dengan elemen bidang, sementara bidang biner memiliki kenyamanan 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 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 bidang biner tidak memerlukan pembawa dalam operasi penjumlahan dan perkalian, serta operasi kuadrat dalam bidang biner sangat efisien, karena mengikuti aturan penyederhanaan (X + Y )2 = X2 + Y 2.

Seperti yang ditunjukkan dalam Gambar 1, sebuah string 128-bit: string ini dapat diinterpretasikan dengan berbagai cara dalam konteks domain biner. Ini dapat dianggap sebagai elemen unik dalam domain biner 128-bit, atau dapat 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, hanya konversi tipe string bit (typecast), adalah atribut yang sangat menarik dan berguna. Pada saat yang sama, elemen domain kecil dapat dikemas menjadi elemen domain yang lebih besar tanpa 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 biner tower n-bit ( yang dapat diuraikan menjadi subdomain m-bit ).

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

Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan himpunan 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 multivariat f dan g pada hiperkubus Boolean adalah hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi pengurutan antara variabel polinomial.

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

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 di hiperkubus Boolean sama dengan nilai yang dinyatakan ∏x∈Hµ f(x) = s, untuk memastikan keakuratan produk polinomial.

6. ZeroCheck: Memverifikasi apakah suatu polinomial multivariat di hiper kubus Boolean pada 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 variabel tunggal, mengurangi kompleksitas komputasi bagi pihak yang memverifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan bilangan acak, membangun kombinasi linear untuk melakukan pemrosesan batch pada beberapa instance verifikasi jumlah.

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

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

• Optimasi ProductCheck: Dalam HyperPlonk, ProductCheck mengharuskan penyebut U tidak nol di seluruh hiperkubus, 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 secara memadai, yang mengakibatkan ketidakmampuan untuk menyatakan masalah non-nol U pada hiperkubus; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius tetap dapat melanjutkan proses, memungkinkan perluasan 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 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 di HyperPlonk, tetapi juga meletakkan dasar untuk sistem bukti berbasis domain biner di masa depan.

2.3 PIOP: argumen shift 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:

• Pengemasan: Metode ini mengoptimalkan operasi dengan mengemas elemen yang lebih kecil di posisi berdekatan dalam urutan kamus menjadi elemen yang lebih besar. Operator Pack ditujukan untuk operasi blok berukuran 2κ, dan menggabungkannya menjadi dimensi yang lebih tinggi.