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, seperti indeks dalam loop for, nilai boolean, penghitung, dan sebagainya. 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 asli itu sendiri sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.

Seperti yang ditunjukkan pada Tabel 1, lebar kode STARKs generasi pertama adalah 252bit, lebar kode STARKs generasi kedua adalah 64bit, dan lebar kode STARKs generasi ketiga adalah 32bit, namun lebar kode 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, sehingga kode menjadi kompak, efisien, dan tanpa ruang terbuang, yaitu STARKs generasi keempat.

Tabel 1: Jalur Turunan STARKs

Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian baru lainnya tentang bidang terbatas dalam beberapa tahun terakhir, 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), berbasis pada domain F28;

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

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

• Protokol FRI dan zk-STARK yang asli, serta fungsi hash Grøstl yang masuk final SHA-3, yang berbasis 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. Sementara bidang biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan untuk menjamin keamanan dan kegunaan praktisnya. Kebanyakan polinomial yang terlibat dalam perhitungan Prover tidak perlu memasuki perluasan, tetapi cukup beroperasi di bawah bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu mendalami perluasan yang lebih besar untuk memastikan keamanan yang diperlukan.

Ketika membangun sistem bukti berdasarkan domain biner, ada 2 masalah praktis: saat menghitung representasi trace 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 pengkodean diperluas.

Binius mengusulkan solusi inovatif untuk menangani kedua masalah ini secara terpisah, dan mewujudkannya dengan menyajikan data yang sama dengan dua cara berbeda: pertama, menggunakan polinomial multivariat (khususnya polinomial multilinear) sebagai pengganti polinomial univariat, dengan nilai-nilainya pada "hyperCube" (hypercubes) untuk merepresentasikan seluruh jejak perhitungan; kedua, karena setiap dimensi dari hypercube memiliki panjang 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti STARKs, namun hypercube dapat dianggap sebagai persegi (square), dan perluasan Reed-Solomon dapat dilakukan berdasarkan persegi tersebut. Metode ini, sambil memastikan keamanan, secara signifikan meningkatkan efisiensi pengkodean dan kinerja perhitungan.

2 Analisis Prinsip

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

• Pembuktian Oracle Interaktif Polinomial Teori Informasi (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti dari sistem pembuktian, mengubah hubungan komputasi yang dimasukkan menjadi persamaan polinomial yang dapat diverifikasi. Berbagai protokol PIOP, melalui interaksi dengan verifier, memungkinkan prover untuk secara bertahap mengirimkan polinomial, 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, yang masing-masing memiliki cara yang berbeda dalam menangani ekspresi polinomial, sehingga memengaruhi 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 di mana, penjamin dapat mengkomit sebuah polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain tentang polinomial itu. 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 eliptik yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Misalnya:

• Halo2: Menggabungkan PLONK PIOP dan Bulletproofs PCS, serta berbasis pada kurva Pasta. Saat merancang Halo2, fokus pada skalabilitas dan menghilangkan trusted setup dalam protokol ZCash.

• Plonky2: Menggunakan kombinasi PLONK PIOP dan FRI PCS, dan berbasis pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem ini, PIOP dan PCS yang dipilih harus sesuai dengan finite field atau kurva elips 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 yang dapat dipercaya, serta apakah dapat mendukung fungsi ekspansi 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, aritmetika berbasis menara domain biner (towers of binary fields) membentuk dasar komputasinya, yang memungkinkan operasi yang disederhanakan dalam domain 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 ini memperkenalkan bukti pergeseran multilinear baru, yang mengoptimalkan efisiensi verifikasi hubungan multilinear di domain kecil. Keempat, Binius menggunakan bukti pencarian Lasso yang diperbaiki, memberikan fleksibilitas dan keamanan yang kuat pada mekanisme pencariannya. Terakhir, protokol ini menggunakan skema komitmen polinomial domain kecil (Small-Field PCS), yang memungkinkannya untuk mewujudkan sistem bukti yang efisien di domain biner dan mengurangi biaya yang biasanya terkait dengan domain besar.

2.1 Ruang terbatas: Aritmetika berdasarkan towers of binary fields

Bidang biner bertingkat adalah kunci untuk mewujudkan perhitungan yang cepat dan dapat diverifikasi, terutama berkat dua aspek: perhitungan yang efisien dan aritmatika yang efisien. Bidang biner pada dasarnya mendukung operasi aritmatika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur bidang biner mendukung proses aritmatika yang disederhanakan, yaitu operasi yang dilakukan di atas bidang biner dapat dinyatakan dalam bentuk aljabar yang kompak dan mudah diverifikasi. Karakteristik ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya sifat hierarkisnya melalui struktur menara, membuat bidang biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.

"Canonical" mengacu pada representasi yang unik dan langsung dari elemen dalam bidang biner. Misalnya, dalam bidang biner paling dasar F2, string dengan panjang k dapat langsung dipetakan ke elemen bidang biner dengan panjang k. Ini berbeda dengan bidang prima, yang tidak dapat memberikan representasi yang sesuai dalam jumlah bit tertentu. Meskipun bidang prima 32-bit dapat diwakili dalam 32-bit, tidak setiap string 32-bit dapat secara unik sesuai dengan satu elemen bidang, sementara bidang biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam bidang prima Fp, metode reduksi yang umum termasuk reduksi Barrett, reduksi Montgomery, serta 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, baik operasi penjumlahan maupun perkalian tidak memerlukan pembawaan, 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 dengan cara yang berbeda dalam konteks domain biner. Ini 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 tambahan, hanya konversi tipe string bit (typecast), yang merupakan atribut yang sangat menarik dan berguna. Pada saat yang sama, 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 operasi perkalian, kuadrat, dan invers dalam domain biner tower n-bit (yang dapat dipecah menjadi subdomain m-bit).

Gambar 1: Domain biner berbentuk menara

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 kebenaran polinomial dan kumpulan multivariabel. 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 multivariabel f dan g di hyperkubus Boolean adalah hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi penyusunan variabel polinomial.

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

6. ZeroCheck: Memverifikasi apakah polinomial multivariat pada hiperkubus Boolean di setiap titik adalah nol ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, untuk memastikan distribusi titik nol dari polinomial.

7. SumCheck: Memeriksa apakah jumlah dari polinomial multivariat sama dengan nilai yang dinyatakan ∑x∈Hµ f(x) = s. Dengan mengubah masalah evaluasi polinomial multivariabel menjadi evaluasi polinomial variabel tunggal, mengurangi kompleksitas komputasi dari pihak verifikator. Selain itu, SumCheck juga memungkinkan pemrosesan batch dengan memperkenalkan angka acak, membentuk kombinasi linear untuk merealisasikan pemrosesan batch dari 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 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, yang mengakibatkan tidak dapat memastikan bahwa U tidak nol di hiper kubus; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya adalah nol, ProductCheck Binius dapat terus diproses, memungkinkan untuk diperluas ke nilai perkalian apa 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 dengan memperbaiki mekanisme PIOPSumCheck yang ada, terutama dalam menangani verifikasi polinomial multivariabel yang lebih kompleks, memberikan dukungan fungsionalitas yang lebih kuat. Peningkatan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem pembuktian berbasis domain biner di masa depan.

2.3 PIOP: pergeseran multilinear baru