Analisis Prinsip STARKs Binius dan Pemikiran Optimisasinya

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, ketika menggunakan kode Reed-Solomon untuk memperluas data, banyak nilai redundan tambahan akan mengisi seluruh domain, bahkan jika nilai aslinya 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 ada banyak ruang yang terbuang. Sebaliknya, domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ruang yang terbuang, yaitu STARKs generasi keempat.

Tabel 1: Jalur derivatif STARKs

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

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

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

• QR code, 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 menjadi semakin penting untuk memastikan keamanan. Bidang biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinom yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam perluasan, 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 yang lebih besar untuk memastikan keamanan yang diperlukan.

Saat membangun sistem bukti berdasarkan domain biner, terdapat 2 masalah praktis: ukuran domain yang digunakan untuk menghitung representasi jejak dalam STARKs harus lebih besar dari derajat polinomial; saat berkomitmen pada pohon Merkle dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, dan ukuran domain yang digunakan harus lebih besar dari ukuran setelah pengembangan pengkodean.

Binius mengusulkan solusi inovatif untuk menangani kedua masalah ini secara terpisah, dan mewujudkan data yang sama dengan dua cara berbeda: Pertama, menggunakan multivariat ( yang secara khusus adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan merepresentasikan seluruh jalur komputasi melalui nilainya pada "super kubus" ( hypercubes ); Kedua, karena setiap dimensi super kubus memiliki panjang 2, maka tidak dapat dilakukan perluasan Reed-Solomon yang standar seperti STARKs, tetapi super kubus dapat dipandang sebagai persegi ( square ), yang menjadi dasar untuk melakukan perluasan Reed-Solomon. Metode ini memastikan keamanan sambil secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.

2 Analisis Prinsip

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

• Teori informasi bukti interaktif polinomial (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti sistem bukti, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan penyelenggara untuk mengirimkan polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah perhitungan itu benar hanya dengan menanyakan hasil evaluasi sejumlah kecil polinomial. Protokol PIOP yang ada meliputi: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara berbeda dalam menangani ekspresi polinomial, sehingga mempengaruhi kinerja dan efisiensi keseluruhan sistem SNARK.

• Skema Komitmen Polin ( Polynomial Commitment Scheme, PCS ): Skema komitmen polin digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP berlaku. 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 polin yang umum meliputi 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 pembuktian dengan atribut yang berbeda. Misalnya:

• Halo2: dikombinasikan dari PLONK PIOP dan Bulletproofs PCS, dan 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 rekursi yang efisien. Dalam merancang sistem ini, PIOP dan PCS yang dipilih harus sesuai dengan bidang hingga atau kurva eliptik 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 ekspansi seperti bukti rekursif atau bukti agregat.

Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mewujudkan efisiensi dan keamanan. Pertama, berdasarkan aritmetika bidang biner bertingkat (towers of binary fields) yang menjadi dasar perhitungan, memungkinkan 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, mengoptimalkan efisiensi verifikasi hubungan multilinear di bidang kecil. Keempat, Binius menggunakan versi yang ditingkatkan 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 bukti yang efisien di bidang biner dan mengurangi biaya yang biasanya terkait dengan bidang besar.

2.1 Ruang terbatas: aritmetika berdasarkan towers of binary fields

Bidang biner berbasis tower adalah kunci untuk menerapkan perhitungan yang dapat diverifikasi dengan cepat, 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 direpresentasikan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur tower, 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 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, di mana bidang prima tidak dapat memberikan representasi standar ini dalam jumlah bit yang ditentukan. Meskipun bidang prima 32-bit dapat diwakili dalam 32-bit, tidak setiap string 32-bit dapat secara unik dikaitkan dengan elemen bidang, sementara bidang biner memiliki kemudahan 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 perlu memperkenalkan pembawa dalam operasi penjumlahan dan perkalian, dan operasi kuadrat dalam 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 dalam konteks domain biner dengan berbagai cara. Ini dapat dilihat 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 apa pun, 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 di domain tower biner n-bit ( yang dapat dipecah menjadi subdomain m-bit ).

Gambar 1: Domain Biner Bertingkat

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 himpunan multivariabel. Mekanisme pemeriksaan inti ini mencakup:

1. GateCheck: Memverifikasi apakah saksi rahasia ω dan input publik x memenuhi hubungan operasi sirkuit C(x,ω)=0, untuk memastikan sirkuit berjalan dengan benar.

2. PermutationCheck: Memverifikasi apakah hasil evaluasi dari dua polinomial multivariat f dan g di hiperkubus Boolean merupakan hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi pengaturan antara variabel polinomial.

3. LookupCheck: Memverifikasi apakah nilai polinomial berada dalam tabel lookup yang diberikan, yaitu f(Bµ) ⊆ T(Bµ), memastikan 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 antara beberapa himpunan.

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

6. ZeroCheck: Memverifikasi apakah suatu 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 multivariabel sama dengan nilai yang dinyatakan ∑x∈Hµ f(x) = s. Dengan mengubah masalah evaluasi polinomial multivariabel menjadi evaluasi polinomial variabel tunggal, mengurangi kompleksitas komputasi pihak verifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch dengan memperkenalkan bilangan acak, membangun kombinasi linear untuk melakukan pemrosesan batch terhadap beberapa contoh verifikasi 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 mengharuskan penyebut U tidak nol di seluruh hypercube, dan hasil kali harus sama dengan nilai tertentu; Binius menyederhanakan proses pengecekan ini dengan mengkhususkan nilai tersebut menjadi 1, sehingga mengurangi kompleksitas komputasi.

• Penanganan masalah pembagian dengan nol: HyperPlonk tidak berhasil menangani kasus pembagian dengan nol dengan baik, sehingga tidak dapat dipastikan bahwa U tidak sama dengan nol di hiperkubus; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya nol, ProductCheck Binius tetap dapat melanjutkan pemrosesan, memungkinkan perluasan ke nilai produk mana pun.

• Periksa Permutasi Lintas Kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung pemeriksaan permutasi 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, 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