Analisis Prinsip STARKs Binius dan Pemikiran Optimisasi

1 Pendahuluan

Salah satu alasan utama ketidakefisienan STARKs adalah: sebagian besar nilai dalam program aktual berukuran kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dan lain-lain. Namun, untuk memastikan keamanan bukti berbasis pohon Merkle, saat menggunakan pengkodean Reed-Solomon untuk memperluas data, banyak nilai redundan tambahan akan mengisi seluruh domain, bahkan jika 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, lebar kode STARKs generasi ketiga adalah 32bit, tetapi lebar kode 32bit masih terdapat 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 Turunan STARKs

| Generasi | Lebar Kode | Sistem Perwakilan | |------|----------|----------| | Generasi 1 | 252 bit | StarkWare STARKs | | Generasi ke-2 | 64 bit | Plonky2 | | Generasi ke-3 | 32 bit | BabyBear | | Generasi ke-4 | 1 bit | Binius |

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

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

• Kode Autentikasi Pesan Galois ( GMAC ), berbasis pada 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.

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

Ketika membangun sistem pembuktian berdasarkan bidang biner, terdapat 2 masalah nyata: saat menghitung representasi trace dalam STARKs, ukuran bidang yang digunakan harus lebih besar dari derajat polinom; saat berkomitmen pada pohon Merkle dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, ukuran bidang yang digunakan harus lebih besar dari ukuran setelah perluasan pengkodean.

Binius mengusulkan solusi inovatif yang menangani kedua masalah ini secara terpisah, dan mewakili data yang sama dengan dua cara berbeda: pertama, menggunakan multivariat ( yaitu polinomial multilinier ) sebagai pengganti polinomial univariat, dengan mewakili seluruh jejak komputasi melalui nilai-nilainya di "superkubus" ( hypercubes ); kedua, karena panjang setiap dimensi superkubus adalah 2, maka tidak mungkin melakukan perluasan Reed-Solomon standar seperti STARKs, tetapi superkubus dapat dianggap sebagai kotak ( square ), dan perluasan Reed-Solomon dapat dilakukan berdasarkan kotak tersebut. Metode ini menjaga keamanan sekaligus secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.

2 Analisis Prinsip

Konstruksi sebagian besar sistem SNARKs saat ini umumnya 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 input menjadi persamaan polinomial yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan pembuktian untuk secara bertahap mengirimkan polinomial melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah komputasi benar dengan hanya menanyakan sedikit hasil evaluasi polinomial. Protokol PIOP yang ada termasuk: PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang masing-masing memiliki cara berbeda dalam menangani ekspresi polinomial, sehingga mempengaruhi 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, melalui itu, pembuktian dapat mengkomit sebuah polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain dari polinomial. Skema komitmen polinomial yang umum digunakan termasuk KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) dan Brakedown, dan 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 elips yang sesuai, dapat membangun sistem bukti dengan atribut yang berbeda. Contohnya:

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

• Plonky2: Menggunakan PLONK PIOP dan FRI PCS yang dikombinasikan, serta berdasarkan domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem ini, pilihan PIOP dan PCS yang digunakan 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 terpercaya, serta apakah dapat mendukung fungsi ekstensi seperti bukti rekursif atau bukti agregat.

Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, aritmetika berbasis menara bidang biner (towers of binary fields) membentuk dasar perhitungan, yang mampu melakukan operasi yang disederhanakan dalam bidang biner. Kedua, Binius dalam protokol bukti Oracle interaktifnya (PIOP), mengadaptasi pemeriksaan produk dan permutasi HyperPlonk, memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol memperkenalkan bukti pergeseran multilinear baru, mengoptimalkan efisiensi dalam memverifikasi hubungan multilinear di 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 untuk menerapkan 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

Domain biner bertingkat adalah kunci untuk menerapkan perhitungan yang cepat dan dapat diverifikasi, terutama disebabkan oleh dua aspek: perhitungan yang efisien dan aritmetika yang efisien. Domain biner pada dasarnya mendukung operasi aritmetika yang sangat efisien, menjadikannya pilihan ideal untuk aplikasi kriptografi yang sensitif terhadap kinerja. Selain itu, struktur domain biner mendukung proses aritmetika yang disederhanakan, yaitu operasi yang dilakukan di atas domain biner dapat diwakili dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah dengan kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur bertingkat, membuat domain biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.

Di mana "canonical" merujuk pada cara representasi unik dan langsung dari elemen di dalam domain biner. Misalnya, dalam domain biner dasar F2, sembarang string sepanjang k dapat langsung dipetakan ke elemen domain biner sepanjang k. Ini berbeda dengan domain bilangan prima, yang tidak dapat memberikan representasi normatif dalam jumlah bit tertentu. Meskipun domain bilangan prima 32-bit dapat dimuat dalam 32-bit, tidak setiap string 32-bit dapat secara unik dipetakan ke elemen domain, sedangkan domain biner memiliki kemudahan pemetaan satu lawan 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 domain biner tidak perlu memperkenalkan carry 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 dengan berbagai cara dalam konteks domain biner. Ini dapat dianggap sebagai elemen unik dalam domain biner 128-bit, atau diuraikan menjadi 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 beban 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 beban 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 direduksi menjadi subdomain m-bit ).

Gambar 1: Domain Biner Bertingkat

2.2 PIOP: versi modifikasi HyperPlonk Product dan PermutationCheck------cocok untuk bidang biner

Desain PIOP dalam protokol Binius mengadopsi HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti, untuk memverifikasi keakuratan polinomial dan kumpulan multivariat. Mekanisme 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 hiperkubus Boolean adalah hubungan permutasi f(x) = f(π(x)), untuk memastikan konsistensi permutasi antar variabel polinomial.

3. LookupCheck: Memverifikasi apakah nilai polinomial berada 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, 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 multivariabel di hiper kubus Bool 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 multivariabel adalah nilai yang dinyatakan ∑x∈Hµ f(x) = s. Dengan mengubah masalah evaluasi polinomial multivariabel menjadi evaluasi polinomial variabel tunggal, mengurangi kompleksitas perhitungan pihak yang memverifikasi. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan bilangan acak, membangun kombinasi linier untuk melakukan pemrosesan batch terhadap 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 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 menyebabkan ketidakmampuan untuk menyatakan masalah non-nol dari U pada hiperkubus; Binius menangani masalah ini dengan benar, bahkan dalam kasus di mana penyebutnya nol, ProductCheck Binius dapat terus beroperasi, memungkinkan perluasan ke nilai produk mana pun.

• Cek Permutasi Lintas Kolom: HyperPlonk tidak memiliki fungsi 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, memberikan 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------dapat diterapkan