Analisis Prinsip STARKs Binius dan Pemikiran Optimasi

1 Pendahuluan

Salah satu alasan utama efisiensi STARKs yang rendah adalah: sebagian besar angka dalam program nyata cukup kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dan sebagainya. Namun, untuk memastikan keamanan bukti yang 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 kompak dan efisien tanpa ruang yang terbuang, yaitu generasi keempat STARKs.

Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penemuan baru-baru ini yang lain dalam bidang terbatas, penelitian tentang bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah banyak diterapkan dalam kriptografi, contoh tipikalnya termasuk:

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

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

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

• Protokol FRI dan zk-STARK asli, 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 bidang menjadi semakin penting untuk memastikan keamanan. 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 masuk ke dalam perluasan bidang, tetapi cukup beroperasi di bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu menyelami perluasan bidang yang lebih besar untuk memastikan keamanan yang diperlukan.

Ketika membangun sistem bukti berdasarkan domain biner, terdapat 2 masalah praktis: saat menghitung representasi jejak dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; saat berkomitmen pada pohon Merkle 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 (khususnya polinomial multilinear) sebagai pengganti polinomial univariat, dengan nilai-nilainya pada "hyper-cube" untuk mewakili seluruh jejak perhitungan; kedua, karena setiap dimensi dari hyper-cube memiliki panjang 2, tidak mungkin melakukan perluasan Reed-Solomon standar seperti STARKs, tetapi hyper-cube dapat dianggap sebagai persegi, dan perluasan Reed-Solomon dapat dilakukan berdasarkan persegi tersebut. Metode ini, sambil memastikan keamanan, sangat meningkatkan efisiensi pengkodean dan kinerja perhitungan.

2 Analisis Prinsip

Konstruksi sebagian besar sistem SNARK 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 penjamin untuk secara bertahap mengirimkan polinomial melalui interaksi dengan verifikator, sehingga verifikator dapat memverifikasi apakah perhitungan benar dengan mengajukan sedikit hasil evaluasi polinomial. Protokol PIOP yang ada termasuk: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara penanganan ekspresi polinomial yang berbeda, 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 yang memungkinkan pembuktian untuk mengkomitkan suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain tentang polinomial. Skema komitmen polinomial yang umum digunakan termasuk KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP), dan Brakedown. Berbagai PCS memiliki kinerja, keamanan, dan skenario penggunaan yang berbeda.

Berdasarkan kebutuhan spesifik, pilih PIOP dan PCS yang berbeda, dan kombinasikan dengan domain 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 dan untuk menghilangkan trusted setup dalam protokol ZCash.

• Plonky2: Menggunakan PLONK PIOP dan FRI PCS yang digabungkan, dan didasarkan pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem-sistem ini, PIOP dan PCS yang dipilih harus sesuai dengan finite field 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, serta apakah dapat mendukung fungsi ekstensi seperti bukti rekursif atau bukti agregasi.

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

2.1 Ruang Terbatas: Arithmetisasi berdasarkan menara bidang biner

Bidang biner bertingkat adalah kunci untuk mewujudkan perhitungan yang dapat diverifikasi dengan cepat, terutama karena 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 hierarkisnya melalui struktur bertingkat, menjadikan bidang 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 F2 yang paling dasar, string k-bit mana pun dapat langsung dipetakan ke elemen bidang biner k-bit. Ini berbeda dengan bidang primitif, yang tidak dapat memberikan representasi standar semacam itu dalam jumlah bit yang ditentukan. Meskipun bidang primitif 32-bit dapat dimuat dalam 32 bit, tidak setiap string 32-bit dapat secara unik sesuai dengan elemen bidang, sementara bidang biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam bidang primitif 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 dalam bidang biner, tidak ada kebutuhan untuk 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 dalam Gambar 1, sebuah string 128-bit: string ini dapat diinterpretasikan dengan berbagai cara dalam konteks domain biner. Itu dapat dianggap sebagai elemen unik dalam domain biner 128-bit, atau diuraikan menjadi dua elemen domain menara 64-bit, empat elemen domain menara 32-bit, 16 elemen domain 8-bit, atau 128 elemen domain F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi apa pun, hanya sekadar konversi tipe (typecast) dari string bit, 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 dari operasi perkalian, kuadrat, dan invers dalam domain biner bertingkat dengan n bit (yang dapat diuraikan menjadi subdomain m bit).

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

Desain PIOP dalam protokol Binius mengadopsi HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan koleksi multivariat. Mekanisme pemeriksaan inti ini termasuk:

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 hypercube Boolean adalah hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi pengaturan antar variabel polinomial.

3. LookupCheck: Memverifikasi apakah nilai 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 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 pada hiperkubus Boolean sama dengan nilai yang dinyatakan ∏x∈Hµ f(x) = s, untuk memastikan kebenaran produk polinomial.

6. ZeroCheck: Memverifikasi apakah suatu polinomial multivariat 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 multivariabel sama dengan nilai yang dinyatakan ∑x∈Hµ f(x) = s. Dengan mengubah masalah evaluasi polinomial multivariabel menjadi evaluasi polinomial variabel tunggal, kompleksitas komputasi untuk pihak yang memverifikasi dapat dikurangi. Selain itu, SumCheck juga memungkinkan pemrosesan batch dengan memperkenalkan angka acak, membangun kombinasi linier untuk menangani 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 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 tidak berhasil menangani situasi pembagian dengan nol, yang menyebabkan ketidakmampuan untuk menyatakan masalah non-nol U di hypercube; Binius berhasil menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya adalah nol, ProductCheck Binius tetap dapat melanjutkan pemrosesan, memungkinkan perluasan ke nilai produk mana pun.

• Cek Permutasi Lintas Kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung Cek Permutasi antar beberapa kolom, yang memungkinkan Binius untuk menangani situasi pengaturan 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 mengatasi 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 pengolahan polinomial virtual adalah salah satu teknologi kunci, yang dapat secara efektif menghasilkan dan mengoperasikan polinomial yang diturunkan dari pegangan masukan atau polinomial virtual lainnya. Berikut adalah dua metode kunci:

• Pengemasan: