Analisis Prinsip Binius STARKs 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.

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, pengkodean yang kompak dan efisien tanpa ruang terbuang, yaitu STARKs generasi keempat.

Tabel 1: Jalur Derivasi STARKs

| Aljabar | Lebar Bit | Domain | |------|------|------| | Generasi 1 | 252bit | Domain bilangan prima | | Generasi ke-2 | 64bit | Goldilocks | | Generasi ke-3 | 32bit | Domain bilangan prima | | Generasi ke-4 | 1bit | Domain Biner |

Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian terbaru lainnya mengenai bidang terbatas, penelitian bidang biner dapat ditelusuri kembali ke tahun 1980-an. Saat ini, bidang biner telah banyak diterapkan dalam kriptografi, contoh tipikalnya termasuk:

• Standar Enkripsi Lanjutan (AES), berdasarkan domain F28;

• Kode Otentikasi Pesan Galois ( GMAC ), berdasarkan 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, merupakan algoritma hash yang sangat cocok untuk rekursi.

Ketika menggunakan domain yang lebih kecil, operasi perluasan domain menjadi semakin penting untuk memastikan keamanan. Sementara itu, domain biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan domain untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu memasuki perluasan domain, tetapi cukup beroperasi di bawah 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.

Saat membangun sistem bukti berdasarkan domain biner, terdapat 2 masalah praktis: saat menghitung representasi jejak di STARKs, ukuran domain yang digunakan harus lebih besar dari derajat polinomial; saat komitmen pohon Merkle di STARKs, perlu dilakukan pengkodean Reed-Solomon, ukuran domain yang digunakan harus lebih besar dari ukuran setelah diperluas.

Binius mengajukan solusi inovatif yang menangani kedua masalah tersebut secara terpisah, dan mewakili data yang sama dengan dua cara berbeda: pertama, menggunakan multivariat ( yaitu polinomial multilinier ) sebagai pengganti polinomial univariat, dengan mewakili keseluruhan jejak perhitungan melalui nilai-nilainya pada "hypercube" ( hypercubes ); kedua, karena panjang setiap dimensi hypercube adalah 2, maka tidak dapat dilakukan perpanjangan Reed-Solomon standar seperti STARKs, tetapi hypercube dapat dipandang sebagai persegi ( square ), dan perpanjangan Reed-Solomon dapat dilakukan berdasarkan persegi tersebut. Metode ini secara signifikan meningkatkan efisiensi pengkodean dan kinerja perhitungan sambil memastikan keamanan.

2 Analisis Prinsip

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

• Teori informasi bukti orakel 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 penyintas untuk secara bertahap mengirimkan polinomial melalui interaksi dengan validator, sehingga validator dapat memverifikasi apakah komputasi benar hanya dengan menanyakan 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 valid. PCS adalah alat kriptografi, melalui itu, pembuktian dapat berkomitmen pada 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, dan berbagai PCS memiliki kinerja, keamanan, dan skenario aplikasi yang berbeda.

Berdasarkan kebutuhan spesifik, pilih PIOP dan PCS yang berbeda, dan kombinasi dengan bidang terbatas atau kurva elips yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Contohnya:

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

• Plonky2: menggunakan PLONK PIOP dan FRI PCS yang dikombinasikan, dan didasarkan pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekurensi yang efisien. Dalam merancang sistem-sistem ini, pilihan PIOP dan PCS yang digunakan harus sesuai dengan bidang terbatas atau kurva elips yang digunakan, untuk memastikan keakuratan, 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 ekspansi seperti bukti rekurens atau bukti agregasi.

Binius: HyperPlonk PIOP + Brakedown PCS + binary field. Secara spesifik, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, berdasarkan aritmetika tower bidang biner (towers of binary fields) yang membentuk dasar perhitungannya, 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 ini memperkenalkan bukti pergeseran multilinear baru, 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), memungkinkannya untuk mencapai sistem bukti yang efisien di bidang biner dan mengurangi biaya yang biasanya terkait dengan bidang besar.

2.1 Ruang Terbatas: Aritmetika berdasarkan towers of binary fields

Bidang biner bertingkat adalah kunci untuk mewujudkan komputasi yang cepat dan dapat diverifikasi, terutama karena 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 di atas bidang biner dapat diwakili dalam bentuk aljabar yang kompak 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" mengacu pada cara representasi elemen yang unik dan langsung dalam domain biner. Misalnya, dalam domain biner F2 yang paling dasar, setiap string k-bit dapat dipetakan langsung ke elemen domain biner k-bit. Ini berbeda dengan domain bilangan prima, di mana domain bilangan prima tidak dapat memberikan representasi standar ini dalam jumlah bit yang ditentukan. Meskipun domain bilangan prima 32-bit dapat dimuat dalam 32-bit, tidak setiap string 32-bit dapat secara unik sesuai dengan elemen domain, sementara domain biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam domain bilangan prima Fp, metode reduksi yang umum termasuk reduksi Barrett, reduksi Montgomery, serta metode reduksi khusus untuk domain terbatas tertentu seperti Mersenne-31 atau Goldilocks-64. Dalam domain 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 domain biner, tidak perlu memperkenalkan pembawa dalam operasi penjumlahan dan perkalian, dan operasi kuadrat dalam domain 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 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, enam belas elemen domain tower 8-bit, atau seratus dua puluh delapan elemen domain F2. Fleksibilitas representasi ini tidak memerlukan biaya komputasi tambahan, hanya konversi tipe string bit (typecast), 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 karakteristik 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 tower biner n-bit yang ( dapat terurai menjadi subdomain m-bit ).

Gambar 1: Domain biner bertingkat

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

Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi keakuratan polinomial dan himpunan multivariabel. Mekanisme pemeriksaan inti ini mencakup:

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

3. LookupCheck: Memverifikasi apakah nilai polinomial berada dalam tabel pencarian yang diberikan, yaitu f(Bµ) ⊆ T(Bµ), memastikan bahwa nilai-nilai tertentu 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 kebenaran produk polinomial.

6. ZeroCheck: memverifikasi apakah 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 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 pihak yang memverifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan bilangan acak, membangun kombinasi linier untuk mewujudkan pemrosesan batch dari 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 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 tidak berhasil menangani situasi pembagian dengan nol, yang menyebabkan ketidakmampuan untuk menyatakan masalah non-nol U di hiperkubus; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya nol, ProductCheck Binius masih dapat melanjutkan pemrosesan, memungkinkan perluasan ke nilai produk mana pun.

• Cek Permutasi Lintas Kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung Cek Permutasi di antara beberapa kolom, yang memungkinkan Binius untuk menangani situasi susunan polinomial yang lebih kompleks.

Oleh karena itu, Binius meningkatkan fleksibilitas dan efisiensi protokol melalui perbaikan terhadap mekanisme PIOPSumCheck yang ada, terutama dalam menangani verifikasi polinomial multivariabel yang lebih kompleks, sehingga memberikan dukungan fungsi yang lebih kuat. Perbaikan ini tidak hanya menyelesaikan keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar bagi sistem pembuktian berbasis bidang biner di masa depan.

2.3 PIOP: argumen pergeseran multiliner baru------cocok untuk hypercube boolean

Dalam protokol Binius, konstruksi dan pengolahan polinomial virtual adalah kunci.