Analisis Prinsip Binius STARKs dan Pemikiran Optimisasi

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 true/false, penghitung, dan sebagainya. Namun, untuk memastikan keamanan bukti berbasis pohon Merkle, saat memperluas data menggunakan pengkodean Reed-Solomon, 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.

Generasi pertama STARKs memiliki lebar kode 252bit, generasi kedua STARKs memiliki lebar kode 64bit, dan generasi ketiga STARKs memiliki lebar kode 32bit, namun lebar kode 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, dengan pengkodean yang padat dan efisien tanpa ruang yang terbuang, yaitu generasi keempat STARKs.

Dibandingkan dengan Goldilocks, BabyBear, Mersenne31 dan penelitian terbaru lainnya 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 meliputi:

• Standar Enkripsi Tingkat Lanjut (AES), berbasis domain F28;

• Galois Message Authentication Code ( GMAC ), berbasis pada bidang 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 berbasis pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursi.

Ketika menggunakan domain yang lebih kecil, operasi perluasan semakin penting untuk memastikan keamanan. 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, melainkan hanya beroperasi di bawah domain dasar, sehingga mencapai efisiensi tinggi dalam domain kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu mendalami domain perluasan yang lebih besar untuk memastikan keamanan yang diinginkan.

Ada 2 masalah praktis saat membangun sistem bukti berdasarkan domain biner: dalam STARKs, ukuran domain yang digunakan saat menghitung representasi jejak harus lebih besar dari derajat polinomial; dalam STARKs, saat berkomitmen pada pohon Merkle, perlu dilakukan pengkodean Reed-Solomon, di mana ukuran domain yang digunakan harus lebih besar dari ukuran setelah perluasan pengkodean.

Binius mengajukan solusi inovatif yang menangani kedua masalah ini secara terpisah dan mewakili data yang sama dengan dua cara berbeda: pertama, menggunakan polinomial multivariat (secara spesifik polinomial multilinear) sebagai pengganti polinomial univariat, dengan nilai-nilainya pada "hyper-cube" untuk mewakili seluruh jejak komputasi; kedua, karena panjang setiap dimensi hyper-cube adalah 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti pada STARKs, tetapi dapat dianggap bahwa hyper-cube adalah persegi, dan melakukan perluasan Reed-Solomon 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:

• Bukti Oracle Interaktif Polinomial Teoretis Informasi (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 verifier, sehingga verifier dapat memverifikasi apakah komputasi benar dengan mengajukan 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 memengaruhi 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 yang memungkinkan pemberi bukti untuk berkomitmen pada suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain tentang polinomial. Skema komitmen polinomial yang umum digunakan antara lain KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP), dan Brakedown. Berbagai PCS memiliki kinerja, keamanan, dan skenario penerapan yang berbeda.

Berdasarkan kebutuhan spesifik, pilih berbagai PIOP dan PCS, serta gunakan bidang terbatas atau kurva elips yang sesuai, Anda dapat membangun sistem pembuktian dengan atribut yang berbeda. Contohnya:

• Halo2: Dikembangkan dari kombinasi 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 dipadukan, serta berbasis pada domain Goldilocks. Plonky2 dirancang untuk mencapai rekurensi yang efisien. Dalam merancang sistem-sistem ini, pilihan PIOP dan PCS yang digunakan harus cocok dengan bidang hingga atau kurva eliptik yang digunakan, untuk memastikan kebenaran, 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 perluasan seperti bukti rekurensif atau bukti agregasi.

Binius: HyperPlonk PIOP + Brakedown PCS + domain biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, berdasarkan bidang biner bertingkat (towers of binary fields), aritmatika membentuk dasar komputasinya, memungkinkan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol bukti Oracle interaktifnya (PIOP) mengadaptasi pemeriksaan produk dan penggantian HyperPlonk, memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan penggantian mereka. Ketiga, protokol memperkenalkan bukti pergeseran multilinear baru, mengoptimalkan efisiensi verifikasi hubungan multilinear pada 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 overhead yang biasanya terkait dengan bidang besar.

2.1 Ruang Terbatas: Aritmetika berbasis towers of binary fields

Bidang biner bertingkat adalah kunci untuk mencapai perhitungan yang cepat dan dapat diverifikasi, terutama karena 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 bidang biner dapat direpresentasikan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur bertingkat, membuat bidang biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.

Di mana "canonical" merujuk pada cara unik dan langsung untuk merepresentasikan elemen dalam domain biner. Misalnya, dalam domain biner paling dasar F2, string k-bit apa 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 yang ditentukan. Meskipun domain prima 32-bit dapat dicakup dalam 32-bit, tidak setiap string 32-bit dapat secara unik berhubungan dengan satu elemen domain, sedangkan domain biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam domain prima Fp, metode reduksi yang 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 carry, 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 konteks domain biner dengan berbagai cara. 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, 16 elemen domain tower 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. Sementara itu, elemen domain kecil dapat dikemas menjadi elemen domain 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 dari operasi perkalian, kuadrat, dan invers dalam domain biner tower n-bit (yang dapat dipecah menjadi subdomain m-bit).

2.2 PIOP: Versi Adaptasi HyperPlonk Product dan PermutationCheck------Cocok untuk domain biner

Desain PIOP dalam protokol Binius terinspirasi oleh HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan kumpulan multivariat. Pemeriksaan inti ini meliputi:

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

3. LookupCheck: Memverifikasi apakah nilai polinomial ada dalam tabel pencarian yang diberikan, yaitu f(Bµ) ⊆ T(Bµ), memastikan 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, untuk menjamin konsistensi antar banyak kumpulan.

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

6. ZeroCheck: Memverifikasi apakah suatu polinomial multivariat di hypercube Boolean pada 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 sesuai dengan nilai yang dinyatakan ∑x∈Hµ f(x) = s. Dengan mengubah masalah evaluasi polinomial multivariat menjadi evaluasi polinomial variabel tunggal, kompleksitas perhitungan untuk pihak verifikasi 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 mana saja di hiperkubus, dan produk harus sama dengan nilai tertentu; Binius menyederhanakan proses pemeriksaan ini dengan mempersempit nilai tersebut menjadi 1, sehingga mengurangi kompleksitas perhitungan.

• Penanganan masalah pembagian dengan nol: HyperPlonk tidak dapat menangani kasus pembagian dengan nol dengan baik, sehingga tidak dapat memastikan bahwa U tidak nol di hiperkubus; Binius berhasil menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya adalah nol, ProductCheck dari Binius dapat terus beroperasi, memungkinkan perluasan ke nilai hasil kali mana pun.

• Pemeriksaan Permutasi Lintas Kolom: HyperPlonk tidak memiliki fungsi 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 multivariat yang lebih kompleks, memberikan dukungan fungsionalitas yang lebih kuat. Peningkatan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga membangun dasar untuk sistem bukti berbasis bidang 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 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-elemen terkecil yang berdekatan dalam urutan kamus menjadi elemen yang lebih besar. Operator Pack ditujukan untuk blok berukuran 2κ dan mengelompokkannya.