Analisis Prinsip STARKs Binius dan Pemikiran Optimisasinya

1 Pendahuluan

Salah satu alasan utama efisiensi STARKs yang rendah adalah karena 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.

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, domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang padat dan efisien tanpa ruang yang terbuang, yaitu generasi keempat STARKs.

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

• Standar Enkripsi Lanjutan (AES), berbasis bidang F28;

• Kode autentikasi pesan Galois ( GMAC ), berbasis pada 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 berbasis pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursi.

Ketika menggunakan domain yang lebih kecil, operasi perluasan domain menjadi semakin penting untuk memastikan keamanan. Sedangkan domain biner yang digunakan oleh Binius sangat bergantung pada perluasan domain untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu memasuki perluasan domain, melainkan cukup beroperasi di bawah domain dasar, sehingga mencapai efisiensi tinggi dalam domain kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu mendalami perluasan domain yang lebih besar untuk memastikan keamanan yang diperlukan.

Ada 2 masalah praktis ketika membangun sistem bukti berdasarkan domain biner: saat menghitung representasi trace dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; saat komitmen 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 merepresentasikan data yang sama dengan dua cara berbeda: pertama, menggunakan polinomial multivariabel (khususnya polinomial multilinear) sebagai pengganti polinomial univariat, dengan nilai-nilainya pada "hyper kubus" untuk merepresentasikan seluruh jejak perhitungan; kedua, karena panjang setiap dimensi hyper kubus adalah 2, maka tidak mungkin melakukan ekstensi Reed-Solomon standar seperti pada STARKs, tetapi hyper kubus dapat dipandang sebagai persegi, yang memungkinkan ekstensi Reed-Solomon berdasarkan persegi tersebut. Metode ini secara signifikan meningkatkan efisiensi pengkodean dan kinerja perhitungan sambil memastikan keamanan.

2 Analisis Prinsip

Saat ini, sebagian besar sistem SNARKs biasanya terdiri dari dua bagian berikut:

• Bukti Orakel 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 pembuktian secara bertahap mengirimkan polinomial melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah komputasi benar hanya dengan menanyakan sedikit hasil evaluasi polinomial. Protokol PIOP yang ada termasuk: PIOP PLONK, PIOP Spartan, dan PIOP HyperPlonk, 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 berlaku. PCS adalah alat kriptografi yang memungkinkan pembuktian untuk mengkomit ke suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain dari polinomial itu. Skema komitmen polinomial yang umum digunakan antara lain KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP), dan Brakedown. 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: Dikombinasikan dari PLONK PIOP dan Bulletproofs PCS, dan berbasis pada kurva Pasta. Halo2 dirancang dengan fokus pada skalabilitas dan menghilangkan trusted setup dalam protokol ZCash.

• Plonky2: Mengadopsi PLONK PIOP dan FRI PCS yang digabungkan, dan didasarkan pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekurensi yang efisien. Dalam merancang sistem-sistem ini, pilihan PIOP dan PCS yang digunakan harus sesuai dengan finite field atau kurva elips yang digunakan, untuk memastikan keakuratan, 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 yang tepercaya, serta apakah dapat mendukung fitur-fitur ekstensi seperti bukti rekurensi atau bukti agregat.

Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara spesifik, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanannya. Pertama, aritmatika berbasis bidang biner bertingkat (towers of binary fields) membentuk dasar perhitungan, memungkinkan operasi yang disederhanakan dilakukan 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 bukti pencarian Lasso yang ditingkatkan, memberikan fleksibilitas dan keamanan yang kuat pada mekanisme pencarian. Terakhir, protokol menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), memungkinkannya untuk menerapkan sistem bukti yang efisien di bidang biner dan mengurangi biaya yang biasanya terkait dengan bidang besar.

2.1 Ruang Terbatas: Arithmetisasi berdasarkan towers of binary fields

Bidang biner bertingkat adalah kunci untuk menghasilkan komputasi yang cepat dan dapat diverifikasi, yang 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 atas bidang biner dapat direpresentasikan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur 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" merujuk pada cara representasi yang unik dan langsung dari elemen dalam bidang biner. Misalnya, dalam bidang biner paling dasar F2, setiap string k-bit dapat dipetakan langsung ke elemen bidang biner k-bit. Ini berbeda dengan bidang bilangan prima, di mana bidang bilangan prima tidak dapat memberikan representasi standar seperti itu dalam jumlah bit yang ditentukan. Meskipun bidang bilangan prima 32-bit dapat dimasukkan dalam 32-bit, tidak setiap string 32-bit dapat secara unik sesuai dengan elemen bidang, sedangkan bidang biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam bidang bilangan prima Fp, metode reduksi umum termasuk reduksi Barrett, reduksi Montgomery, dan 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 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 ditafsirkan 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, 16 elemen domain tower 8-bit, atau 128 elemen domain F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi tambahan, hanya sekadar konversi tipe (typecast) dari string bit, 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" mengeksplorasi kompleksitas komputasi dari operasi perkalian, kuadrat, dan invers di domain tower biner n-bit (yang dapat dipecah menjadi subdomain m-bit).

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

Desain PIOP dalam protokol Binius mengacu pada HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan himpunan multivariat. Pemeriksaan inti ini mencakup:

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 di hiperkubus Boolean adalah hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi penataan antara 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 multivariabel sama, yaitu {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, untuk memastikan konsistensi antar beberapa himpunan.

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

6. ZeroCheck: Memverifikasi apakah suatu polinomial multivariat di hypercube Boolean 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 perhitungan untuk pihak verifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch dengan memperkenalkan bilangan acak untuk membangun kombinasi linear yang memungkinkan pemrosesan beberapa instance verifikasi jumlah.

8. BatchCheck: Berdasarkan SumCheck, memverifikasi kebenaran evaluasi banyak 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 hyperkubus, 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 berhasil menangani situasi pembagian dengan nol secara memadai, yang menyebabkan ketidakmampuan untuk menyatakan masalah non-nol U di hypercube; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya adalah nol, ProductCheck Binius masih dapat melanjutkan pemrosesan, memungkinkan untuk diperluas ke nilai produk apa pun.

• Periksa Permutasi Lintas Kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung pemeriksaan 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, memberikan dukungan fungsional yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem bukti berbasis bidang biner di masa depan.

2.3 PIOP: argumen pergeseran multilinear baru------berlaku 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-elemen yang lebih kecil yang berdekatan dalam urutan kamus menjadi elemen yang lebih besar. Operator Pack ditujukan untuk operasi blok berukuran 2κ dan mengelompokkannya.