Analisis Prinsip STARKs Binius dan Pemikiran Optimisasinya

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 bukti 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.

Lebar kode STARKs generasi pertama adalah 252bit, lebar kode STARKs generasi kedua adalah 64bit, lebar kode STARKs generasi ketiga adalah 32bit, tetapi lebar kode 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, bidang biner memungkinkan operasi langsung pada bit, dengan pengkodean yang padat dan efisien tanpa 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 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 pada domain F28;

• Galois Message Authentication Code ( GMAC ), berdasarkan bidang 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. Domain biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan domain untuk menjamin keamanan dan kegunaannya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu memasuki perluasan domain, tetapi hanya perlu beroperasi dalam 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 nyata: saat menghitung representasi jejak dalam STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; saat melakukan komitmen Merkle tree dalam STARKs, diperlukan pengkodean Reed-Solomon, ukuran domain yang digunakan harus lebih besar dari ukuran setelah ekstensi pengkodean.

Binius mengusulkan solusi inovatif untuk menangani kedua masalah ini secara terpisah dan mewakili data yang sama dengan dua cara berbeda: pertama, menggunakan multivariat ( yang khusus adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan menggunakan nilai-nilainya di "hyper-cube" ( hypercubes ) untuk mewakili seluruh jejak perhitungan; kedua, karena panjang setiap dimensi hyper-cube adalah 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti STARKs, tetapi hyper-cube dapat dilihat sebagai persegi ( square ), yang didasarkan pada persegi tersebut untuk melakukan perluasan Reed-Solomon. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja perhitungan.

2 Analisis Prinsip

Kebanyakan sistem SNARKs saat ini biasanya terdiri dari dua bagian berikut:

• Teorema 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 mengirimkan polinomial secara bertahap melalui interaksi dengan verifikator, sehingga verifikator dapat memverifikasi apakah komputasi benar dengan hanya menanyakan hasil evaluasi beberapa polinomial. Protokol PIOP yang ada termasuk: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara berbeda dalam menangani ekspresi polinomial, sehingga memengaruhi kinerja dan efisiensi keseluruhan sistem SNARK.

• Polinomi Komitmen Skema (Polynomial Commitment Scheme, PCS): Skema komitmen polinomi digunakan untuk membuktikan apakah persamaan polinomi yang dihasilkan oleh PIOP adalah benar. PCS adalah alat kriptografi, melalui mana, pembuktian dapat mengkomitmenkan suatu polinomi dan kemudian memverifikasi hasil evaluasi polinomi tersebut, sambil menyembunyikan informasi lain tentang polinomi. Skema komitmen polinomi yang umum termasuk KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) dan Brakedown. 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 dibangun sistem bukti dengan atribut yang berbeda. Misalnya:

• Halo2: dikombinasikan dari PLONK PIOP dan Bulletproofs PCS, dan berbasis pada kurva Pasta. Halo2 dirancang dengan fokus pada skalabilitas, serta menghilangkan trusted setup 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 sesuai dengan bidang terbatas 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 tepercaya, apakah dapat mendukung bukti rekursif atau fitur ekspansi lainnya seperti bukti agregasi.

Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, dasar aritmatika yang dibangun di atas menara bidang biner (towers of binary fields) menjadi dasar perhitungan, yang memungkinkan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol pembuktian Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan permutasi HyperPlonk untuk memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan permutasi mereka. Ketiga, protokol ini memperkenalkan bukti pergeseran multilinear baru, yang mengoptimalkan efisiensi verifikasi hubungan multilinear di bidang kecil. Keempat, Binius menggunakan bukti pencarian Lasso yang ditingkatkan, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol ini menggunakan skema komitmen polinomial bidang kecil (Small-Field PCS), yang memungkinkannya untuk mencapai sistem pembuktian yang efisien di bidang biner, dan mengurangi biaya yang biasanya terkait dengan bidang besar.

2.1 Ruang Terbatas: Aritmetika berdasarkan menara bidang biner

Bidang biner bertingkat adalah kunci untuk mewujudkan komputasi yang dapat diverifikasi dengan cepat, terutama disebabkan oleh 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 kompak dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkis 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 di bidang biner. Misalnya, di bidang biner paling dasar F2, string k-bit mana pun dapat langsung dipetakan ke elemen bidang biner k-bit. Ini berbeda dengan bidang prima, di mana bidang prima tidak dapat memberikan representasi normatif seperti itu dalam jumlah bit tertentu. Meskipun bidang prima 32-bit dapat dimasukkan dalam 32-bit, tidak setiap string 32-bit dapat secara unik mengacu pada elemen bidang, sedangkan bidang biner memiliki kenyamanan 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 penerapan 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 string bit (typecast), yang merupakan atribut yang sangat menarik dan berguna. Pada saat yang sama, elemen bidang kecil dapat dikemas menjadi elemen bidang 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 operasi invers di bidang tower biner n-bit ( yang dapat terurai menjadi sub-bidang m-bit ).

2.2 PIOP: versi modifikasi HyperPlonk Product 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 variabel multivariat. Mekanisme pemeriksaan inti ini meliputi:

1. GateCheck: Memverifikasi apakah saksi rahasia ω dan input publik x memenuhi hubungan perhitungan 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 Bool adalah relasi permutasi f(x) = f(π(x)), untuk memastikan konsistensi pengaturan antar variabel polinomial.

3. LookupCheck: Memverifikasi apakah evaluasi 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 kumpulan multivariabel sama, yaitu {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, untuk menjamin konsistensi antar beberapa kumpulan.

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

6. ZeroCheck: Memverifikasi apakah polinomial multivariat pada hypercube 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 univariat, kompleksitas perhitungan untuk pihak yang memverifikasi dapat dikurangi. 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 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 hiper-kubus, 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 situasi pembagian dengan nol dengan baik, sehingga tidak dapat dipastikan bahwa U tidak nol pada hiperkubus; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius masih 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 meningkatkan fleksibilitas dan efisiensi protokol melalui perbaikan pada mekanisme PIOPSumCheck yang ada, terutama dalam menangani verifikasi polinomial multivariat yang lebih kompleks, memberikan dukungan fungsi 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 perpindahan multilinear baru------cocok untuk hypercube boolean

Dalam protokol Binius, konstruksi dan pemrosesan polinomial virtual adalah salah satu teknologi kunci, yang mampu 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 ditujukan untuk operasi blok berukuran 2κ dan menggabungkannya menjadi domain berdimensi tinggi.