Analisis Prinsip STARKs Binius dan Pemikiran Optimisasi

1. Pendahuluan

Berbeda dengan SNARK yang berbasis kurva elips, STARK dapat dianggap sebagai SNARK berbasis hash. Saat ini, salah satu alasan utama ketidakefisienan STARK adalah: sebagian besar nilai dalam program nyata relatif kecil, seperti indeks dalam loop for, nilai benar/salah, penghitung, dan sebagainya. Namun, untuk memastikan keamanan bukti berbasis pohon Merkle, ketika menggunakan pengkodean Reed-Solomon untuk memperluas data, banyak nilai redundan tambahan akan mengisi seluruh domain, bahkan jika 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, dan 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 padat dan efisien tanpa ruang yang terbuang, yaitu STARKs generasi keempat.

Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian terbaru lainnya dalam beberapa tahun terakhir mengenai bidang terbatas, penelitian mengenai bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah digunakan secara luas dalam kriptografi, contoh tipikal meliputi:

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

• Kode Autentikasi Pesan Galois ( GMAC ), berdasarkan domain F2128;

• QR code, menggunakan pengkodean Reed-Solomon berbasis F28;

• Protokol FRI dan zk-STARK yang asli, serta fungsi hash Grøstl yang masuk ke 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. Sedangkan 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 memasuki perluasan bidang, tetapi cukup beroperasi di bawah 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.

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

Binius mengusulkan solusi inovatif untuk menangani kedua masalah ini secara terpisah, dan mewujudkan data yang sama melalui dua cara berbeda: pertama, menggunakan polinomial multivariat (khususnya polinomial multilinear) sebagai pengganti polinomial univariat dengan mewakili keseluruhan jejak komputasi melalui nilai-nilainya di "hiperkubus"; kedua, karena panjang setiap dimensi hiperkubus adalah 2, maka tidak dapat melakukan perpanjangan Reed-Solomon standar seperti STARKs, tetapi hiperkubus dapat dipandang sebagai persegi, berdasarkan persegi tersebut untuk melakukan perpanjangan Reed-Solomon. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.

2. Analisis Prinsip

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

• Bukti Oracle Interaktif Polinomial Teoritis 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 penyedia bukti untuk secara bertahap mengirimkan polinomial melalui interaksi dengan verifier, 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 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, yang memungkinkan pembuktian untuk mengkomit suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain tentang polinomial tersebut. Skema komitmen polinomial yang umum digunakan termasuk KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP), dan Brakedown. Setiap 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. Misalnya:

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

• Plonky2: Menggunakan PLONK PIOP dan FRI PCS yang digabungkan, dan berbasis pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekursif yang efisien. Dalam merancang sistem ini, PIOP dan PCS yang dipilih harus sesuai dengan bidang hingga 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, aritmetika berbasis menara bidang biner (towers of binary fields) membentuk dasar komputasinya, yang mampu melakukan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol pembuktian Oracle interaktifnya (PIOP) telah mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, yang memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol ini memperkenalkan bukti pergeseran multilinier baru, yang mengoptimalkan efisiensi verifikasi hubungan multilinier di bidang kecil. Keempat, Binius menggunakan versi perbaikan dari bukti pencarian Lasso, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol ini menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), memungkinkan untuk merealisasikan sistem pembuktian yang efisien dalam bidang biner dan mengurangi biaya yang biasanya terkait dengan bidang besar.

2.1 Ruang Terbatas: Aritmetika berbasis towers of binary fields

Bidang biner bertingkat adalah kunci untuk mencapai komputasi yang cepat dan dapat diverifikasi, terutama karena 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 peka 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 dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkis melalui struktur bertingkat, menjadikan bidang biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.

Di mana "canonical" mengacu pada cara representasi elemen yang unik dan langsung dalam domain biner. Misalnya, dalam domain biner paling dasar F2, string k-bit mana pun dapat dipetakan langsung ke elemen domain biner k-bit. Ini berbeda dengan domain prima, di mana domain prima tidak dapat memberikan representasi yang standar dalam jumlah bit yang ditentukan. Meskipun domain prima 32-bit dapat diakomodasi dalam 32-bit, tidak setiap string 32-bit dapat secara unik dipasangkan dengan elemen domain, sedangkan domain biner menawarkan kemudahan pemetaan satu-ke-satu semacam ini. Dalam domain prima Fp, metode reduksi umum termasuk reduksi Barrett, reduksi Montgomery, dan 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 penambahan carry, dan operasi kuadrat dalam 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 dalam berbagai cara dalam konteks domain biner. Ini dapat dianggap sebagai elemen unik dalam domain biner 128-bit, atau diuraikan menjadi dua elemen domain menara 64-bit, empat elemen domain menara 32-bit, enam belas elemen domain menara 8-bit, atau 128 elemen domain F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi tambahan, hanya konversi tipe string bit, yang merupakan atribut yang sangat menarik dan berguna. Selain itu, 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 dari operasi perkalian, kuadrat, dan invers dalam domain biner bertingkat n-bit (yang dapat dipecah menjadi subdomain m-bit).

2.2 PIOP: Versi Adaptasi Produk HyperPlonk dan PermutationCheck------Cocok untuk Domain Biner

Desain PIOP dalam protokol Binius mengacu pada HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran 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 multivariat f dan g pada hiperkubus Boolean adalah hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi permutasi antar 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 himpunan multivariat adalah sama, yaitu {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, menjamin konsistensi antar himpunan.

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

6. ZeroCheck: Memverifikasi apakah sebuah polinomial multivariabel pada hypercube 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 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 linier untuk merealisasikan pemrosesan batch dari 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 dalam 3 aspek berikut:

• Optimasi ProductCheck: Dalam HyperPlonk, ProductCheck mensyaratkan penyebut U tidak boleh nol di seluruh hypercube, 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 dengan baik, yang mengakibatkan ketidakmampuan untuk memastikan bahwa U bukan nol di hypercube; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya nol, ProductCheck Binius tetap dapat melanjutkan, memungkinkan generalisasi ke nilai hasil kali apa pun.

• pemeriksaan Permutasi Lintas: HyperPlonk tidak memiliki fitur ini; Binius mendukung pemeriksaan Permutasi di antara beberapa kolom, yang memungkinkan Binius 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, memberikan dukungan fungsional yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem bukti 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 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 mengurutkan posisi yang berdekatan dalam urutan kamus.