Analisis Prinsip STARKs Binius dan Pemikiran Optimisasi

1 Pendahuluan

Salah satu alasan utama efisiensi STARKs yang rendah adalah: sebagian besar nilai dalam program nyata cukup kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dll. Namun, untuk memastikan keamanan pembuktian berbasis pohon Merkle, saat menggunakan pengkodean Reed-Solomon untuk memperluas data, banyak nilai redundan tambahan akan mengisi seluruh domain, meskipun nilai aslinya sendiri sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.

Lebar bit encoding STARKs generasi pertama adalah 252bit, lebar bit encoding STARKs generasi kedua adalah 64bit, lebar bit encoding STARKs generasi ketiga adalah 32bit, tetapi lebar bit encoding 32bit masih ada banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, encoding yang padat dan efisien tanpa ada ruang yang terbuang, yaitu STARKs generasi keempat.

Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian baru yang ditemukan dalam beberapa tahun terakhir tentang bidang terbatas, penelitian tentang 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), berdasarkan bidang F28;

• Kode Autentikasi Pesan Galois ( GMAC ), berdasarkan bidang F2128;

• QR code, 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 bidang F28, adalah algoritma hash yang sangat cocok untuk rekursi.

Saat 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. Kebanyakan polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke perluasan bidang, tetapi cukup beroperasi di 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 bukti berdasarkan bidang biner, terdapat 2 masalah praktis: Saat menghitung representasi jejak dalam STARKs, ukuran bidang yang digunakan harus lebih besar dari derajat polinomial; Saat melakukan komitmen pohon Merkle dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, ukuran bidang 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, dengan menggunakan multivariat ( yang secara khusus adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan merepresentasikan seluruh jejak komputasi melalui nilai-nilainya di "hiperkubus" (; kedua, karena panjang setiap dimensi hiperkubus adalah 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti STARKs, tetapi hiperkubus dapat dianggap sebagai persegi ), dan perluasan Reed-Solomon dilakukan berdasarkan persegi tersebut. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.

2 Analisis Prinsip

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

• Teori informasi bukti oracle interaktif polinomial (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 hanya 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 seluruh sistem SNARK.

• Skema Komitmen Polin (Polynomial Commitment Scheme, PCS): Skema komitmen polin 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 mengenai polinomial. Beberapa skema komitmen polin yang umum digunakan adalah 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 bidang terbatas atau kurva elips yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Contoh:

• Halo2: digabungkan dari PLONK PIOP dan Bulletproofs PCS, dan berbasis pada kurva Pasta. Halo2 dirancang dengan fokus pada skalabilitas, serta menghilangkan setup terpercaya dalam protokol ZCash.

• Plonky2: Mengadopsi PLONK PIOP dan FRI PCS yang digabungkan, dan berdasarkan domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem ini, PIOP dan PCS yang dipilih harus cocok dengan bidang hingga atau kurva eliptik 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 tepercaya, dan apakah dapat mendukung fungsi ekspansi 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, aritmatika berbasis menara bidang biner (towers of binary fields) membentuk dasar perhitungan, yang dapat melakukan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol bukti Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan substitusi HyperPlonk, memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan substitusinya. Ketiga, protokol memperkenalkan bukti pergeseran multilinear baru, mengoptimalkan efisiensi dalam memverifikasi hubungan multilinear di bidang kecil. Keempat, Binius menggunakan bukti pencarian Lasso yang ditingkatkan, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), memungkinkan sistem bukti yang efisien di bidang biner, dan mengurangi biaya yang biasanya terkait dengan bidang besar.

( 2.1 Ruang Terbatas: Aritmatika Berdasarkan Menara Bidang Biner

Bidang biner bertingkat adalah kunci untuk mencapai komputasi yang cepat dan dapat diverifikasi, 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 pada bidang biner dapat dinyatakan dalam bentuk aljabar yang padat dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya sifat 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 di dalam bidang biner. Misalnya, dalam bidang biner yang paling dasar F2, sembarang string k-bit 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 dihubungkan dengan elemen bidang, sedangkan bidang biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam bidang prima 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 pengenalan carry 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 diinterpretasikan dalam konteks bidang biner dengan berbagai cara. Ini dapat dianggap sebagai elemen unik dalam bidang biner 128-bit, atau diuraikan menjadi dua elemen bidang tower 64-bit, empat elemen bidang tower 32-bit, enam belas elemen bidang tower 8-bit, atau seratus dua puluh delapan elemen bidang F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi tambahan, hanya konversi tipe dari string bit (typecast), adalah atribut yang sangat menarik dan berguna. Pada saat yang sama, elemen bidang kecil dapat dikemas menjadi elemen bidang yang lebih besar tanpa 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 operasi perkalian, kuadrat, dan invers dalam bidang biner tower n-bit ( yang dapat direduksi menjadi sub-bidang m-bit ).

( 2.2 PIOP: Versi Modifikasi Produk HyperPlonk dan PermutationCheck------Cocok untuk Domain Biner

Desain PIOP dalam protokol Binius mengadopsi HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi keakuratan polinomial dan koleksi multivariat. Pemeriksaan inti ini meliputi:

1. GateCheck: memverifikasi bahwa saksi rahasia ω dan input publik x memenuhi hubungan perhitungan sirkuit C)x, ω###=0, untuk memastikan sirkuit berjalan dengan benar.

2. PermutationCheck: Memverifikasi apakah hasil evaluasi dari dua polinomial multivariat f dan g pada hiperkubus Boolean adalah hubungan permutasi f(x) = f(π)x((, untuk memastikan konsistensi permutasi di antara variabel polinomial.

3. LookupCheck: Memverifikasi apakah evaluasi polinomial ada dalam tabel lookup yang diberikan, yaitu f)Bµ) ⊆ T(Bµ), memastikan bahwa 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 hypercube Boolean sama dengan nilai yang dinyatakan ∏x∈Hµ f(x) = s, untuk memastikan keakuratan produk polinomial.

6. ZeroCheck: Memverifikasi apakah suatu polinom multivariat pada hiper kubus Boolean di titik mana pun adalah nol ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, untuk memastikan distribusi titik nol dari polinom.

7. SumCheck: Memeriksa apakah jumlah dari polinomial multivariat adalah nilai yang dinyatakan ∑x∈Hµ f(x) = s. Dengan mengubah masalah evaluasi polinomial multivariabel menjadi evaluasi polinomial univariat, mengurangi kompleksitas komputasi dari pihak verifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch dengan memperkenalkan bilangan acak, membangun kombinasi linier untuk mengelola 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 melakukan perbaikan dalam 3 aspek berikut:

• Optimasi ProductCheck: Dalam HyperPlonk, ProductCheck mengharuskan penyebut U tidak nol di seluruh hiperkubus, dan produknya harus sama dengan nilai tertentu; Binius menyederhanakan proses pemeriksaan ini dengan mengkhususkan nilai tersebut menjadi 1, sehingga mengurangi kompleksitas perhitungan.

• Penanganan masalah pembagian nol: HyperPlonk tidak dapat menangani situasi pembagian nol dengan baik, yang menyebabkan ketidakmampuan untuk memastikan bahwa U tidak nol di hiperkubus; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya nol, ProductCheck Binius tetap dapat melanjutkan pemrosesan, memungkinkan perluasan ke nilai produk mana pun.

• Pemeriksaan 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 telah meningkatkan fleksibilitas dan efisiensi protokol melalui perbaikan 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 yang berbasis pada domain 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:

• Pengemasan: Metode ini mengoptimalkan operasi dengan mengemas elemen-elemen yang lebih kecil di posisi berurutan dalam urutan kamus menjadi elemen yang lebih besar. Operator Pack menargetkan operasi blok dengan ukuran 2κ dan menggabungkannya menjadi domain berdimensi tinggi.