Analisis Prinsip STARKs Binius dan Pemikiran Optimalisasi

1 Pendahuluan

Salah satu alasan utama rendahnya efisiensi STARKs adalah: sebagian besar angka 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, tetapi lebar kode 32bit masih memiliki banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, dengan kode yang kompak dan efisien tanpa ruang yang terbuang, yaitu STARKs generasi keempat.

Tabel 1: Jalur Derivasi STARKs

| Aljabar | Lebar Kode | Contoh | |------|----------|------| | Generasi 1 | 252bit | Ethereum STARKs | | Generasi ke-2 | 64bit | Plonky2 | | Generasi ke-3 | 32bit | BabyBear | | Generasi ke-4 | 1bit | Binius |

Dibandingkan dengan Goldilocks, BabyBear, Mersenne31, dan temuan penelitian terbaru dalam beberapa tahun terakhir 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 termasuk:

• Standard Enkripsi Tingkat Tinggi (AES), berbasis pada domain F28
• Kode autentikasi pesan Galois ( GMAC ), berdasarkan domain F2128
• QR Code, menggunakan pengkodean Reed-Solomon berbasis F28
• Protokol FRI asli dan zk-STARK, serta fungsi hash Grøstl yang masuk ke final SHA-3, yang berbasis pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursi.

Ketika menggunakan bidang yang lebih kecil, operasi perluasan semakin penting untuk memastikan keamanan. 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, 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 bidang perluasan yang lebih besar untuk memastikan keamanan yang diperlukan.

Saat membangun sistem bukti berdasarkan domain biner, terdapat 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 perluasan pengkodean.

Binius mengajukan solusi inovatif yang menangani kedua masalah ini secara terpisah dan mewakili data yang sama dengan dua cara berbeda: pertama, menggunakan multivariat ( yang secara khusus adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan menggunakan nilai-nilainya di "hypercube" ( untuk mewakili seluruh jalur perhitungan; kedua, karena setiap dimensi hypercube memiliki panjang 2, maka tidak dapat dilakukan perluasan Reed-Solomon standar seperti STARKs, tetapi hypercube dapat dianggap sebagai persegi ), yang berdasarkan persegi tersebut dilakukan perluasan Reed-Solomon. Metode ini memastikan keamanan sambil 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 Teori 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 penjamin untuk mengirimkan polinomial secara bertahap melalui interaksi dengan verifier, sehingga verifier dapat memverifikasi apakah perhitungan benar hanya dengan menanyakan hasil evaluasi beberapa 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 Polin ( Polynomial Commitment Scheme, PCS ): Skema komitmen polin digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP valid. PCS adalah alat kriptografi yang memungkinkan penjamin untuk mengkomit ke suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain tentang polinomial tersebut. Skema komitmen polin yang umum digunakan termasuk KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) dan Brakedown. Setiap PCS memiliki kinerja, keamanan, dan skenario aplikasi 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 oleh PLONK PIOP dan Bulletproofs PCS, berdasarkan kurva Pasta. Halo2 dirancang dengan fokus pada kemampuan skala, serta menghilangkan trusted setup dalam protokol ZCash.

• Plonky2: menggunakan PLONK PIOP yang dikombinasikan dengan 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 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 tepercaya, serta apakah dapat mendukung fungsi ekstensi seperti bukti rekursif atau bukti agregasi.

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

( 2.1 Ruang Terbatas: Aritmetika berdasarkan menara bidang biner

Bidang biner berbentuk tower adalah kunci untuk mencapai komputasi yang cepat dan dapat diverifikasi, terutama disebabkan oleh 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 dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Karakteristik ini, ditambah dengan kemampuan untuk memanfaatkan karakteristik hierarkisnya sepenuhnya melalui struktur tower, menjadikan bidang biner sangat cocok untuk sistem bukti yang dapat diskalakan seperti Binius.

Di mana "canonical" merujuk pada representasi unik dan langsung dari elemen dalam domain biner. Misalnya, dalam domain biner paling dasar F2, setiap string k-bit dapat dipetakan langsung ke elemen domain biner k-bit. Ini berbeda dengan domain prima, yang tidak dapat memberikan representasi standar ini dalam jumlah bit tertentu. Meskipun domain prima 32-bit dapat disimpan 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 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 umum 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 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, string 128-bit: string ini dapat ditafsirkan dalam berbagai cara dalam konteks domain biner. Ini dapat dilihat sebagai elemen unik dalam domain biner 128-bit, atau dapat diselesaikan sebagai dua elemen menara 64-bit, empat elemen menara 32-bit, 16 elemen menara 8-bit, atau 128 elemen domain F2. Fleksibilitas representasi ini tidak memerlukan overhead komputasi, hanya (typecast) konversi jenis ke string bitwise, yang merupakan properti yang sangat menarik dan berguna. Pada saat yang sama, elemen domain kecil dapat dikemas ke dalam elemen domain yang lebih besar tanpa overhead 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 operasi perkalian, kuadrat, dan inversi dalam domain biner menara n-bit ( yang dapat diuraikan menjadi subdomain m-bit ) subdomain m-bit.

( 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 multivariat. Pemeriksaan inti ini mencakup:

1. GateCheck: Memverifikasi kesaksian rahasia ω 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 di hiperkubus Boolean adalah relasi permutasi f(x) = f(π)x((, untuk memastikan konsistensi permutasi antara variabel polinomial.

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

4. MultisetCheck: memeriksa apakah dua himpunan multivariat sama, yaitu {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, memastikan 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 kebenaran produk polinomial.

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

7. SumCheck: Memeriksa apakah jumlah 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 angka acak, membangun kombinasi linier untuk melakukan pemrosesan batch pada 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:

• Optimisasi ProductCheck: Dalam HyperPlonk, ProductCheck mengharuskan penyebut U tidak nol di seluruh hiperkubus, 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 kasus pembagian dengan nol dengan baik, yang mengakibatkan ketidakmampuan untuk memastikan bahwa U tidak nol di hypercube; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius dapat terus beroperasi, memungkinkan untuk diperluas ke nilai produk apa pun.

• Cek Permutasi Lintas Kolom: HyperPlonk tidak memiliki fitur ini; Binius mendukung Cek Permutasi antar beberapa kolom, yang memungkinkan Binius untuk menangani situasi permutasi 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 multivariat yang lebih kompleks, memberikan dukungan fungsi yang lebih kuat. Perbaikan ini tidak hanya mengatasi keterbatasan dalam HyperPlonk, tetapi juga meletakkan dasar untuk sistem bukti berbasis bidang biner di masa depan.

( 2.3 PIOP: argumen pergeseran multilinear baru------cocok untuk hypercube boolean

Dalam protokol Binius, multi-virtual