Analisis Prinsip STARKs Binius dan Pemikiran Optimalisasinya

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, dll. Namun, untuk memastikan keamanan bukti berbasis pohon Merkle, penggunaan pengkodean Reed-Solomon untuk memperluas data akan menyebabkan banyak nilai redundan tambahan 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, generasi ketiga STARKs memiliki lebar kode 32bit, namun lebar kode 32bit masih menyisakan banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang kompak dan efisien tanpa ada ruang yang terbuang, yaitu generasi keempat STARKs.

Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian baru-baru ini yang ditemukan dalam bidang terbatas, penelitian bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah banyak digunakan dalam kriptografi, contoh tipikal termasuk:

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

• Galois Message Authentication Code ( GMAC ), berdasarkan domain F2128;

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

• Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk ke final SHA-3, yang berdasarkan 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. Dan 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, dan hanya perlu 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.

Saat membangun sistem pembuktian berbasis domain biner, ada 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 perluasan pengkodean.

Binius mengusulkan solusi inovatif yang menangani kedua masalah tersebut secara terpisah, dan merepresentasikan data yang sama dengan dua cara berbeda: pertama, menggunakan multivariat ( yaitu polinomial multilinear ) sebagai pengganti polinomial univariat, dengan merepresentasikan seluruh jejak komputasi melalui nilai-nilainya pada "hypercube" ( hypercubes ); kedua, karena panjang setiap dimensi hypercube adalah 2, maka tidak dapat dilakukan perpanjangan Reed-Solomon standar seperti pada STARKs, tetapi hypercube dapat dipandang sebagai kotak ( square ), dan perpanjangan Reed-Solomon dapat dilakukan berdasarkan kotak tersebut. 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:

• Teori informasi bukti interaktif polinomial oracle (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 penyaji untuk secara bertahap mengirimkan polinomial melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah komputasi benar dengan menanyakan hasil evaluasi dari sejumlah kecil polinomial. Protokol PIOP yang ada termasuk: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, masing-masing memiliki cara yang berbeda dalam menangani ekspresi polinomial, yang 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, melalui mana, 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 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: Dikembangkan dari kombinasi 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 kombinasi PLONK PIOP dan FRI PCS, serta 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 keakuratan, 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-fungsi tambahan 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 yang dibangun di atas menara bidang biner (towers of binary fields) menjadi dasar perhitungannya, memungkinkan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol pembuktian Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan penggantian HyperPlonk, memastikan konsistensi pemeriksaan yang aman dan efisien antara variabel dan penggantian mereka. Ketiga, protokol memperkenalkan pembuktian pergeseran multilinear baru, mengoptimalkan efisiensi dalam memverifikasi hubungan multilinear pada bidang kecil. Keempat, Binius mengadopsi pembuktian pencarian Lasso yang ditingkatkan, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencariannya. Terakhir, protokol menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), memungkinkan sistem pembuktian yang efisien di atas bidang biner dan mengurangi overhead yang biasanya terkait dengan bidang besar.

2.1 Ruang Terbatas: Aritmetika berdasarkan towers of binary fields

Bidang biner bertingkat adalah kunci untuk mewujudkan komputasi yang dapat diverifikasi dengan cepat, terutama disebabkan oleh dua aspek: komputasi 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 dinyatakan dalam bentuk aljabar yang kompak dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur menara, membuat bidang biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.

Di mana "canonical" merujuk pada representasi unik dan langsung dari elemen dalam domain biner. Misalnya, dalam domain biner F2 yang paling mendasar, string k bit mana pun dapat langsung dipetakan ke elemen domain biner k bit. Ini berbeda dengan domain prima, yang tidak dapat memberikan representasi standar ini dalam jumlah bit tertentu. Meskipun domain prima 32 bit dapat terdapat dalam 32 bit, tidak setiap string 32 bit dapat secara unik sesuai dengan elemen domain, sedangkan domain biner memiliki kenyamanan pemetaan satu ke satu 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 pengenalan 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 konteks domain biner dengan berbagai cara. Ini dapat dilihat sebagai elemen unik dalam domain biner 128-bit, atau diuraikan sebagai 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 konversi tipe string bit (typecast), 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 untuk perkalian, pemangkatan, dan inversi dalam domain biner tower n-bit ( yang dapat diuraikan menjadi subdomain m-bit ).

2.2 PIOP: Versi Modifikasi Produk HyperPlonk dan PermutationCheck------Cocok untuk domain biner

Desain PIOP dalam protokol Binius mengacu pada HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi keakuratan polinomial dan kumpulan multivariat. Mekanisme pemeriksaan inti ini meliputi:

1. GateCheck: Memverifikasi bukti kerahasiaan ω dan input publik x apakah 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 nilai polinomial ada dalam tabel pencarian yang diberikan, yaitu f(Bµ) ⊆ T(Bµ), memastikan bahwa nilai tertentu berada dalam kisaran yang ditentukan.

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

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

6. ZeroCheck: Memverifikasi apakah polinomial multivariat pada hiperkubus 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 multivariabel sama dengan nilai yang dinyatakan ∑x∈Hµ f(x) = s. Dengan mengubah masalah evaluasi polinomial multivariat menjadi evaluasi polinomial univariat, mengurangi kompleksitas komputasi bagi pihak verifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan angka acak, membangun kombinasi linear untuk melakukan pemrosesan batch dari 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 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, menyebabkan ketidakmampuan untuk memastikan U dalam hiperkubus bukan nol; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya nol, ProductCheck Binius dapat terus diproses, memungkinkan perluasan ke nilai produk mana pun.

• Pemeriksaan Permutasi Lintas: 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------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 mengoptimalkan operasi dengan mengemas elemen yang lebih kecil di posisi berdekatan dalam urutan kamus menjadi elemen yang lebih besar. Operator Pack menargetkan operasi blok dengan ukuran 2κ dan menggabungkannya menjadi domain berdimensi tinggi.