Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi

1 Pendahuluan

Salah satu alasan utama efisiensi STARKs yang rendah adalah: sebagian besar nilai dalam program nyata cenderung kecil, seperti indeks dalam loop for, nilai benar/salah, 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.

Generasi pertama STARKs memiliki lebar kode 252bit, generasi kedua STARKs memiliki lebar kode 64bit, dan 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 terbaru lainnya tentang bidang terbatas dalam beberapa tahun terakhir, penelitian bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah banyak diterapkan dalam kriptografi, contoh tipikal termasuk:

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

• Kode Autentikasi 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 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, tetapi 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: saat menghitung representasi trace di STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; saat melakukan komitmen Merkle tree di STARKs, perlu dilakukan 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 mencapai ini dengan mewakili data yang sama dengan dua cara yang berbeda: pertama, menggunakan multivariat ( yang secara khusus adalah polinomial multilinier ) untuk menggantikan polinomial univariat, dengan merepresentasikan seluruh jalur komputasi melalui nilai-nilainya di "hypercube" ( hypercubes ); kedua, karena setiap dimensi hypercube memiliki panjang 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti pada STARKs, tetapi hypercube dapat dipandang sebagai persegi ( square ) dan perluasan Reed-Solomon dapat dilakukan berdasarkan persegi tersebut. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.

2 Analisis Prinsip

Konstruksi sebagian besar sistem SNARKs 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 komputasi yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan penjamin untuk mengirimkan polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah komputasi benar dengan menanyakan sedikit hasil evaluasi polinomial. Protokol PIOP yang ada termasuk: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara 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 valid. PCS adalah alat kriptografi, melalui itu, 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 penggunaan yang berbeda.

Berdasarkan kebutuhan spesifik, pilih PIOP dan PCS yang berbeda, dan kombinasikan dengan domain terbatas atau kurva elips yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Contohnya:

• Halo2: Kombinasi dari PLONK PIOP dan Bulletproofs PCS, serta berbasis pada 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 berbasis pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekurensi yang efisien. Dalam merancang sistem-sistem ini, pilihan PIOP dan PCS yang digunakan harus sesuai dengan bidang terbatas 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 tepercaya, dan apakah dapat mendukung fungsi-fungsi ekstensi seperti bukti rekurensi atau bukti agregasi.

Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, aritmatika yang berbasis pada menara bidang biner (towers of binary fields) membentuk dasar perhitungan, yang memungkinkan operasi 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 ini memperkenalkan bukti pergeseran multilinear baru, mengoptimalkan efisiensi verifikasi hubungan multilinear di bidang kecil. Keempat, Binius menggunakan bukti pencarian Lasso yang ditingkatkan, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol ini menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), memungkinkan sistem pembuktian yang efisien di atas bidang biner, dan mengurangi biaya yang biasanya terkait dengan bidang besar.

2.1 Ruang Terbatas: Aritmetika berbasis towers of binary fields

Domain biner berbasis tower adalah kunci untuk mencapai perhitungan yang cepat dan dapat diverifikasi, terutama disebabkan oleh dua aspek: perhitungan 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 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 karakteristik hierarkisnya sepenuhnya melalui struktur tower, membuat domain biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.

Di mana "canonical" mengacu pada cara representasi yang unik dan langsung dari elemen di dalam bidang biner. Sebagai contoh, dalam bidang biner dasar F2, setiap string k-bit dapat langsung dipetakan ke elemen bidang biner k-bit. Ini berbeda dengan bidang prima, yang tidak dapat memberikan representasi standar dalam jumlah bit tertentu. Meskipun bidang prima 32-bit dapat diakomodasi dalam 32-bit, tidak setiap string 32-bit dapat secara unik sesuai dengan satu elemen bidang, sedangkan bidang biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam bidang prima Fp, metode reduksi 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 penambahan carry dalam operasi penjumlahan dan perkalian, serta operasi kuadrat di bidang 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. Itu 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, enam belas elemen bidang tower 8-bit, atau seratus dua puluh delapan elemen bidang F2. Fleksibilitas representasi ini tidak memerlukan overhead komputasi apa pun, 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 memerlukan overhead 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 bidang biner tower n-bit ( yang dapat direduksi menjadi subbidang m-bit ).

2.2 PIOP: Versi Modifikasi 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 multivariat. 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 dua polinomial multivariat f dan g di hiperkubus Boolean merupakan hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi penyusunan antara variabel polinomial.

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

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

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 hiperkubus 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 sesuai dengan nilai yang dinyatakan ∑x∈Hµ f(x) = s. Dengan mengubah masalah evaluasi polinomial multivariat menjadi evaluasi polinomial variabel tunggal, mengurangi kompleksitas komputasi pihak verifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan angka acak, membangun kombinasi linear untuk melakukan pemrosesan batch terhadap beberapa contoh verifikasi jumlah.

8. BatchCheck: Berdasarkan SumCheck, memverifikasi keakuratan 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:

• Optimasi ProductCheck: Dalam HyperPlonk, ProductCheck mengharuskan penyebut U tidak nol di seluruh hypercube, 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 kasus pembagian dengan nol secara memadai, yang mengakibatkan ketidakmampuan untuk memastikan bahwa U tidak sama dengan nol di hiperkubus; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya adalah nol, ProductCheck Binius dapat terus memproses, memungkinkan perluasan ke nilai produk mana pun.

• Cek Permutasi Lintas Kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung Cek Permutasi antar kolom, yang memungkinkan Binius untuk menangani kasus susunan 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, memberikan dukungan fungsionalitas 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 pemrosesan 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 dilakukan dengan menggabungkan