Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi

1 Pendahuluan

Salah satu alasan utama efisiensi STARKs yang rendah adalah karena sebagian besar nilai dalam program nyata cukup kecil, tetapi untuk memastikan keamanan pembuktian berbasis pohon Merkle, penggunaan pengkodean Reed-Solomon untuk memperluas data menghasilkan banyak nilai redundan tambahan yang mengisi seluruh domain, meskipun nilai asli itu sendiri sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi kunci.

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

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

• Standar Enkripsi Tingkat Lanjut (AES), berdasarkan bidang F28;

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

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

• Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk ke final SHA-3, yang didasarkan pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursi.

Ketika menggunakan domain yang lebih kecil, operasi perluasan menjadi semakin penting untuk memastikan keamanan. Dan domain biner yang digunakan oleh Binius sepenuhnya bergantung pada perluasan untuk menjamin keamanan dan kegunaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu masuk ke dalam perluasan, dan hanya perlu beroperasi di bawah domain dasar, sehingga mencapai efisiensi tinggi dalam domain kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu masuk ke dalam perluasan yang lebih besar untuk memastikan keamanan yang diperlukan.

Ketika membangun sistem bukti berdasarkan domain biner, ada 2 masalah praktis: ukuran domain yang digunakan saat menghitung representasi jejak dalam STARKs harus lebih besar dari derajat polinomial; saat melakukan komitmen Merkle tree dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, ukuran domain yang digunakan harus lebih besar dari ukuran setelah perpanjangan pengkodean.

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

2 Analisis Prinsip

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

• Bukti Oracle Interaktif Polinomial Teoretis Informasi (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP sebagai inti dari sistem bukti, mengubah hubungan komputasi input menjadi persamaan polinomial yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan penunjuk bukti untuk secara bertahap mengirimkan polinomial melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah komputasi benar dengan menanyakan hasil evaluasi dari sejumlah kecil polinomial. Protokol PIOP yang ada termasuk: PIOP PLONK, PIOP Spartan, dan PIOP HyperPlonk, 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, melalui mana, pembuktian dapat mengkomit suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain dari polinomial. Beberapa skema komitmen polinomial yang umum digunakan adalah KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP), dan Brakedown. Berbagai PCS memiliki performa, keamanan, dan skenario aplikasi yang berbeda.

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

• Halo2: Digabungkan dari PLONK PIOP dan Bulletproofs PCS, dan didasarkan pada kurva Pasta. Saat merancang Halo2, fokus pada skalabilitas, serta menghapus trusted setup dalam protokol ZCash.

• Plonky2: Menggunakan kombinasi PLONK PIOP dan FRI PCS, serta berbasis 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 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 yang dapat dipercaya, dan apakah dapat mendukung fungsi tambahan seperti bukti rekursif atau bukti agregasi.

Binius: HyperPlonk PIOP + Brakedown PCS + domain biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. 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 pembuktian Oracle interaktifnya (PIOP) telah mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, yang memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol memperkenalkan pembuktian pergeseran multilinear baru, yang mengoptimalkan efisiensi verifikasi hubungan multilinear pada domain kecil. Keempat, Binius menggunakan pembuktian pencarian versi ditingkatkan Lasso, yang memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol menggunakan skema komitmen polinomial domain kecil (Small-Field PCS), yang memungkinkannya untuk mewujudkan sistem pembuktian yang efisien dalam 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 mencapai komputasi yang cepat dan dapat diverifikasi, terutama karena 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 bidang biner dapat direpresentasikan 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" merujuk pada cara representasi elemen yang unik dan langsung dalam domain biner. Misalnya, dalam domain biner paling dasar F2, string k-bit mana pun dapat dipetakan langsung ke elemen domain biner k-bit. Ini berbeda dengan domain prima, di mana domain prima tidak dapat memberikan representasi standar ini dalam jumlah bit tertentu. Meskipun domain prima 32-bit dapat terkandung dalam 32 bit, tidak setiap string 32-bit dapat secara unik terkait dengan satu elemen domain, sementara domain biner memiliki kenyamanan pemetaan satu-ke-satu ini. Di domain prima Fp, metode reduksi umum termasuk reduksi Barrett, reduksi Montgomery, dan 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 operasi penjumlahan dan perkalian di domain biner tidak perlu memperkenalkan pembawa, dan operasi kuadrat di 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 ditafsirkan dalam konteks domain biner dengan berbagai cara. Ini dapat dianggap sebagai elemen unik dalam domain biner 128-bit, atau ditafsirkan sebagai 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 (typecast) dari string bit, 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 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 biner menara n-bit (yang dapat dipecah menjadi subdomain m-bit).

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

Desain PIOP dalam protokol Binius mengacu pada HyperPlonk, mengadopsi serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan kumpulan multivariat. Pemeriksaan inti ini mencakup:

1. GateCheck: Memverifikasi bahwa 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 pada hiperkubus Boolean merupakan hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi penyusunan antara variabel polinomial.

3. LookupCheck: Memverifikasi apakah evaluasi polinomial ada dalam tabel lookup yang diberikan, yaitu f(Bµ) ⊆ T(Bµ), memastikan bahwa nilai-nilai tertentu berada dalam rentang yang ditentukan.

4. MultisetCheck: Memeriksa apakah dua kumpulan variabel multiset sama, yaitu {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, untuk menjamin konsistensi antara beberapa kumpulan.

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

6. ZeroCheck: Memverifikasi apakah sebuah polinomial multivariat di hypercube Boolean pada sembarang titik 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 variabel tunggal, mengurangi kompleksitas komputasi pihak yang memverifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch dengan memperkenalkan angka acak, membangun kombinasi linier 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:

• ProductCheck dioptimalkan: 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 dapat menangani situasi pembagian dengan nol dengan baik, yang mengakibatkan ketidakmampuan untuk memastikan bahwa U adalah non-nol pada hiperkubus; Binius 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 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 multivariabel yang lebih kompleks, menyediakan 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 ------ berlaku 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:

• 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 satu elemen dalam domain berdimensi tinggi. Melalui perluasan multilinear.