Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi

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 dari bukti berbasis pohon Merkle, saat 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 encoding STARKs generasi pertama adalah 252bit, lebar encoding STARKs generasi kedua adalah 64bit, lebar encoding STARKs generasi ketiga adalah 32bit, tetapi lebar encoding 32bit masih ada banyak ruang yang terbuang. Sebagai perbandingan, bidang biner memungkinkan operasi langsung pada bit, encoding yang padat dan efisien tanpa ruang yang terbuang sembarangan, yaitu STARKs generasi keempat.

Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian baru-baru ini lainnya tentang domain terbatas, penelitian tentang domain biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, domain biner telah diterapkan secara luas dalam kriptografi, contoh tipikal mencakup:

• Standar 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 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 domain yang lebih kecil, operasi perluasan domain menjadi semakin penting untuk memastikan keamanan. Dan domain biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan domain untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam 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.

Ketika membangun sistem pembuktian berdasarkan domain biner, terdapat 2 masalah praktis: saat menghitung representasi trace dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; saat melakukan komitmen Merkle tree dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, ukuran domain yang digunakan harus lebih besar dari ukuran setelah pengkodean diperluas.

Binius mengusulkan solusi inovatif yang menangani kedua masalah ini secara terpisah dan merepresentasikan data yang sama dengan dua cara berbeda: pertama, menggunakan multivariat ( yang khusus adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan merepresentasikan seluruh jejak perhitungan melalui nilainya di "huperkubus" ( hypercubes ); kedua, karena setiap dimensi dari huperkubus memiliki panjang 2, tidak mungkin untuk melakukan ekstensi Reed-Solomon standar seperti STARKs, tetapi huperkubus dapat dipandang sebagai persegi ( square ), dan berdasarkan persegi tersebut melakukan ekstensi Reed-Solomon. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja perhitungan.

2 Analisis Prinsip

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

• Teori informasi bukti interaksi polinomial oracle (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 penjamin untuk mengirimkan polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah perhitungan benar hanya dengan menanyakan hasil evaluasi sejumlah kecil 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 keseluruhan 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, melalui mana, pembuktian dapat mengkomitkan 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, dan lain-lain. 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: digabungkan dari PLONK PIOP dan Bulletproofs PCS, serta berbasis pada kurva Pasta. Halo2 dirancang dengan fokus pada skalabilitas, serta menghapus trusted setup dalam protokol ZCash.

• Plonky2: mengadopsi PLONK PIOP dan FRI PCS yang dikombinasikan, dan didasarkan pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem-sistem ini, PIOP dan PCS yang dipilih harus cocok 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 yang dapat dipercaya, serta apakah dapat mendukung fungsi tambahan seperti bukti rekursif atau bukti agregasi.

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

2.1 Ruang Terbatas: Aritmetika yang didasarkan pada menara bidang biner

Ruang biner berbentuk tower adalah kunci untuk mewujudkan komputasi yang dapat divalidasi dengan cepat, terutama disebabkan oleh dua aspek: komputasi yang efisien dan aritmetika yang efisien. Ruang biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur ruang biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan pada ruang biner dapat direpresentasikan dalam bentuk aljabar yang ringkas dan mudah divalidasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya sifat hierarkisnya melalui struktur tower, menjadikan ruang biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.

Di mana "canonical" merujuk pada cara unik dan langsung untuk merepresentasikan elemen dalam bidang biner. Misalnya, dalam bidang biner paling dasar F2, string k-bit apa pun dapat langsung dipetakan ke elemen bidang biner k-bit. Ini berbeda dengan bidang prima, yang tidak dapat memberikan representasi standar ini dalam jumlah bit tertentu. Meskipun bidang 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 lawan 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 dengan berbagai cara dalam konteks domain biner. 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 overhead komputasi apapun, hanya konversi tipe dari string bit (typecast), merupakan atribut yang sangat menarik dan berguna. Pada saat yang sama, elemen domain kecil dapat dikemas menjadi elemen domain 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" mengeksplorasi kompleksitas komputasi untuk operasi perkalian, kuadrat, dan invers dalam domain tower biner n-bit ( yang dapat terurai menjadi sub-domain m-bit ).

2.2 PIOP: Versi Adaptasi HyperPlonk Product 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 meliputi:

1. GateCheck: Memverifikasi bahwa 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 hypercube Boolean merupakan hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi pengaturan antara variabel polinomial.

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

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

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 polinomial multivariat di hypercube 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 multivariabel sama dengan nilai yang dinyatakan ∑x∈Hµ f(x) = s. Dengan mengubah masalah evaluasi polinomial multivariabel menjadi evaluasi polinomial univariat, kompleksitas komputasi untuk pihak yang memverifikasi dapat dikurangi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan angka acak, membangun kombinasi linier untuk mengimplementasikan 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 mengharuskan penyebut U tidak nol di seluruh hiperkubus, 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 dapat menangani kasus pembagian dengan nol dengan baik, sehingga tidak dapat dipastikan bahwa U adalah non-nol di hypercube; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius masih dapat melanjutkan pemrosesan, memungkinkan perluasan ke nilai produk apa pun.

• Cek Permutasi Lintas Kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung Cek Permutasi di antara beberapa kolom, yang memungkinkan Binius untuk menangani situasi penyusunan polinomial yang lebih kompleks.

Oleh karena itu, Binius meningkatkan fleksibilitas dan efisiensi protokol dengan memperbaiki mekanisme PIOPSumCheck yang ada, terutama dalam menangani verifikasi polinomial multivariat yang lebih kompleks, memberikan dukungan fungsional yang lebih kuat. Perbaikan ini tidak hanya menyelesaikan 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 mengoptimalkan operasi dengan mengemas elemen yang lebih kecil yang berdekatan dalam urutan kamus menjadi elemen yang lebih besar. Operator Pack menargetkan operasi blok berukuran 2κ dan menggabungkannya menjadi domain berdimensi tinggi.