Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi

1 Pendahuluan

Salah satu alasan utama efisiensi STARKs yang rendah adalah: sebagian besar nilai dalam program nyata cukup kecil, tetapi untuk memastikan keamanan pembuktian berbasis pohon Merkle, ketika menggunakan pengkodean 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.

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, bidang biner memungkinkan operasi langsung pada bit, sehingga pengkodean menjadi kompak dan efisien tanpa ruang terbuang, yaitu generasi keempat STARKs.

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

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

• Kode autentikasi pesan Galois ( GMAC ), berbasis pada domain F2128;

• Kode QR, 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 polinomial 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 menyelami perluasan 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 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 ini secara terpisah dan mewakili data yang sama dengan dua cara berbeda: pertama, menggunakan polinomial multivariat (secara khusus polinomial multilinear) sebagai pengganti polinomial univariat, dengan menggambarkan seluruh jejak perhitungan melalui nilai-nilainya di "hiperkubus"; kedua, karena setiap dimensi hiperkubus memiliki panjang 2, tidak mungkin melakukan perluasan Reed-Solomon standar seperti STARKs, tetapi hiperkubus dapat dianggap sebagai persegi, dan perluasan Reed-Solomon dapat dilakukan berdasarkan persegi tersebut. Metode ini secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi sambil memastikan keamanan.

2 Analisis Prinsip

Konstruksi sebagian besar sistem SNARKs saat ini 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 penyaji untuk secara bertahap mengirimkan polinomial melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah perhitungan benar dengan hanya mengquery hasil evaluasi dari sejumlah kecil polinomial. Protokol PIOP yang ada termasuk: PIOP PLONK, PIOP Spartan, dan PIOP HyperPlonk, yang masing-masing memiliki cara pengolahan 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 penjamin untuk mengkomitkan 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 penggunaan 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, dan didasarkan pada kurva Pasta. Saat merancang Halo2, fokus pada skalabilitas dan menghilangkan trusted setup dalam protokol ZCash.

• Plonky2: Menggunakan 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 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, dan apakah dapat mendukung fungsi ekstensi seperti bukti rekursif atau bukti agregat.

Binius: HyperPlonk PIOP + Brakedown PCS + domain biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanannya. Pertama, aritmetika berbasis tower bidang biner (towers of binary fields) membentuk dasar perhitungannya, yang memungkinkan operasi sederhana di dalam bidang biner. Kedua, Binius dalam protokol bukti Oracle interaktifnya (PIOP) mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, yang memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol memperkenalkan bukti pergeseran multilinear baru, yang mengoptimalkan efisiensi verifikasi hubungan multilinear pada bidang kecil. Keempat, Binius menggunakan bukti pencarian versi yang ditingkatkan Lasso, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), memungkinkan untuk menciptakan sistem bukti yang efisien di bidang biner dan mengurangi beban yang biasanya terkait dengan bidang besar.

2.1 Ruang Terbatas: Aritmetika berdasarkan towers of binary fields

Domain biner bertingkat adalah kunci untuk mewujudkan perhitungan yang cepat dan dapat diverifikasi, terutama karena dua aspek: perhitungan yang efisien dan aritmatika yang efisien. Domain biner pada dasarnya mendukung operasi aritmatika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur domain biner mendukung proses aritmatika yang disederhanakan, yaitu operasi yang dilakukan di atas domain biner dapat direpresentasikan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur bertingkat, membuat domain biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.

"Canonical" merujuk pada cara representasi elemen yang unik dan langsung di dalam bidang biner. Misalnya, dalam bidang biner dasar F2, string dengan k bit dapat dipetakan langsung ke elemen bidang biner dengan k bit. Ini berbeda dengan bidang prime, yang tidak dapat memberikan representasi normatif semacam ini dalam jumlah bit yang ditentukan. Meskipun bidang prime 32-bit dapat mencakup 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 prime Fp, metode reduksi yang 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 memerlukan pembawa dalam operasi penjumlahan dan perkalian, dan operasi kuadrat pada 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 dianggap 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. Sementara 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, pemangkatan, dan inversi dalam domain biner tower n-bit (yang dapat dipecah menjadi subdomain m-bit).

2.2 PIOP: Versi Adaptasi HyperPlonk Product dan PermutationCheck------Cocok untuk bidang biner

Desain PIOP dalam protokol Binius mengadopsi HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan himpunan multivariat. 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 merupakan hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi penataan antar variabel polinomial.

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

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

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

6. ZeroCheck: Memverifikasi apakah suatu polinomial multivariabel pada hiperkubus 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 variabel tunggal, mengurangi kompleksitas komputasi untuk pihak yang memverifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch dengan memperkenalkan bilangan acak, membangun kombinasi linear untuk melakukan pemrosesan batch pada beberapa contoh 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 membuat perbaikan dalam 3 aspek berikut:

• Optimasi ProductCheck: Dalam HyperPlonk, ProductCheck mensyaratkan bahwa penyebut U tidak boleh nol di seluruh hypercube, 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 gagal menangani dengan baik situasi pembagian dengan nol, yang menyebabkan ketidakmampuan untuk memastikan bahwa U tidak nol di hiper kubus; Binius menangani masalah ini dengan benar, bahkan ketika penyebut adalah nol, ProductCheck Binius masih dapat melanjutkan pemrosesan, memungkinkan perluasan ke nilai produk apa pun.

• Cek Permutasi Lintas Kolom: HyperPlonk tidak memiliki fungsi ini; Binius mendukung Cek Permutasi di antara beberapa kolom, yang memungkinkan Binius 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 fungsionalitas yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem pembuktian berbasis domain biner di masa depan.

2.3 PIOP: argumen pergeseran multilinear baru------digunakan untuk hiper kubus 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 melibatkan elemen yang lebih kecil di posisi bersebelahan dalam urutan kamus.