Analisis Prinsip Binius STARKs dan Pemikiran Optimasi

1 Pendahuluan

Salah satu alasan utama rendahnya efisiensi STARKs adalah: sebagian besar nilai dalam program nyata relatif kecil, seperti indeks dalam perulangan for, nilai boolean, penghitung, dan sebagainya. Namun, untuk memastikan keamanan bukti berbasis pohon Merkle, ketika data diperluas menggunakan pengkodean Reed-Solomon, banyak nilai redundan tambahan akan mengisi seluruh bidang, bahkan jika nilai asli itu sendiri sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran bidang 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 memiliki banyak ruang yang terbuang. Sebagai perbandingan, domain biner memungkinkan operasi langsung pada bit, pengkodean yang kompak dan efisien tanpa ada ruang yang terbuang, yaitu STARKs generasi keempat.

Tabel 1: Jalur derivatif STARKs

| Aljabar | Lebar kode bit | Sistem representasi | |------|----------|----------| | Generasi 1 | 252bit | StarkWare |
| Generasi ke-2 | 64bit | Plonky2 | | Generasi ke-3 | 32bit | Polygon zkEVM | | Generasi ke-4 | 1bit | Binius |

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

• Standar 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 mencapai final SHA-3, yang berbasis pada domain F28, adalah algoritma hash yang sangat cocok untuk rekursi.

Ketika menggunakan domain yang lebih kecil, operasi perluasan domain menjadi semakin penting untuk memastikan keamanan. Domain biner yang digunakan oleh Binius harus sepenuhnya bergantung pada perluasan domain untuk menjamin keamanan dan ketersediaan praktisnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu memasuki perluasan domain, tetapi hanya perlu 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 bidang biner, terdapat 2 masalah praktis: saat menghitung representasi jejak dalam STARKs, ukuran bidang yang digunakan harus lebih besar dari derajat polinomial; saat melakukan komitmen pohon Merkle dalam STARKs, perlu dilakukan pengkodean Reed-Solomon, ukuran bidang yang digunakan harus lebih besar dari ukuran setelah pengkodean diperluas.

Binius mengusulkan solusi inovatif yang menangani kedua masalah ini secara terpisah dan mencapai hal tersebut dengan dua cara yang berbeda untuk merepresentasikan data yang sama: pertama, menggunakan multivariat ( yang secara spesifik adalah polinomial multilinier ) sebagai pengganti polinomial univariat, dengan merepresentasikan seluruh jejak komputasi melalui nilai-nilainya pada "hypercube" (; kedua, karena setiap dimensi hypercube memiliki panjang 2, maka tidak dapat dilakukan ekstensi Reed-Solomon standar seperti STARKs, tetapi hypercube dapat dipandang sebagai persegi ), yang digunakan sebagai dasar untuk ekstensi Reed-Solomon. Metode ini memastikan keamanan sambil secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi.

2 Analisis Prinsip

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

• Teorema 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 verifier, sehingga verifier dapat memverifikasi apakah komputasi benar dengan 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 benar. PCS adalah alat kriptografi, melalui itu, pembuktian dapat mengkomitkan suatu polinomial dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain tentang polinomial tersebut. Beberapa skema komitmen polinomial yang umum digunakan adalah KZG, Bulletproofs, FRI(Fast Reed-Solomon IOPP) dan Brakedown, dll. Berbagai 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 dibangun sistem pembuktian dengan atribut yang berbeda. Misalnya:

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

• Plonky2: Menggunakan kombinasi PLONK PIOP dan FRI PCS, serta berdasarkan bidang Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem-sistem ini, pilihan PIOP dan PCS harus cocok dengan bidang terbatas atau kurva elips 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, serta apakah dapat mendukung bukti rekursif atau bukti agregat dan fungsi perluasan lainnya.

Binius: HyperPlonk PIOP + Brakedown PCS + domain biner. Secara khusus, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanan. Pertama, aritmetika yang didasarkan pada menara domain biner (towers of binary fields) membentuk dasar perhitungannya, yang memungkinkan operasi yang disederhanakan dalam domain biner. Kedua, Binius dalam protokol pembuktian Oracle interaktif (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 verifikasi hubungan multilinear di domain kecil. Keempat, Binius menggunakan pembuktian pencarian Lasso yang ditingkatkan, memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Terakhir, protokol menggunakan skema komitmen polinomial domain kecil (Small-Field PCS), memungkinkan untuk mencapai sistem pembuktian yang efisien di domain biner, dan mengurangi biaya yang biasanya terkait dengan domain besar.

( 2.1 Ruang Terbatas: Aritmetika berbasis menara bidang biner

Bidang biner bertingkat adalah kunci untuk mencapai perhitungan yang dapat diverifikasi dengan cepat, 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 atas bidang biner dapat dinyatakan dalam bentuk aljabar yang ringkas 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 unik dan langsung dari elemen di dalam bidang biner. Misalnya, dalam bidang biner paling dasar F2, string k-bit mana pun dapat langsung dipetakan ke elemen bidang biner k-bit. Ini berbeda dengan bidang prima, yang tidak dapat memberikan representasi standar seperti itu dalam jumlah bit yang ditentukan. Meskipun bidang prima 32-bit dapat terkandung dalam 32-bit, tidak setiap string 32-bit dapat secara unik berkorespondensi dengan elemen bidang, sementara bidang biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam bidang prima Fp, metode reduksi umum termasuk reduksi Barrett, reduksi Montgomery, dan metode reduksi khusus untuk bidang terbatas tertentu seperti Mersenne-31 atau Goldilocks-64. Dalam bidang 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 bidang biner tidak perlu memperkenalkan pembawa dalam operasi penjumlahan dan perkalian, dan operasi kuadrat di bidang 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 menjadi 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), 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 fitur 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 tower n-bit ( yang dapat diuraikan menjadi subdomain m-bit ).

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

Desain PIOP dalam protokol Binius mengadopsi HyperPlonk, menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi keakuratan polinomial dan kumpulan variabel multivariat. Pemeriksaan inti ini mencakup:

1. GateCheck: Memverifikasi apakah saksi rahasia ω dan input publik x memenuhi hubungan perhitungan sirkuit C)x,ω###=0, untuk memastikan sirkuit berfungsi dengan baik.

2. PermutationCheck: Memvalidasi apakah hasil evaluasi dari dua polinomial multivariat f dan g pada hiper kubus Boolean adalah relasi permutasi f(x) = f(π)x((, untuk memastikan konsistensi permutasi antara variabel polinomial.

3. LookupCheck: Memverifikasi apakah nilai polinomial ada dalam tabel pencarian yang diberikan, yaitu f)Bµ) ⊆ T(Bµ), memastikan bahwa 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 memastikan konsistensi antara 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 suatu polinomial multivariat pada hypercube Boolean di titik mana pun adalah nol ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, untuk memastikan distribusi titik nol dari 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 untuk 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:

• Optimasi ProductCheck: Di HyperPlonk, ProductCheck mengharuskan penyebut U tidak sama dengan 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 dapat menangani situasi pembagian dengan nol dengan baik, yang mengakibatkan ketidakmampuan untuk memastikan apakah U adalah non-nol di hypercube; Binius menangani masalah ini dengan benar, bahkan ketika penyebutnya nol, ProductCheck Binius tetap dapat melanjutkan pemrosesan, memungkinkan untuk diperluas ke nilai produk mana pun.

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

Oleh karena itu, Binius telah meningkatkan fleksibilitas dan efisiensi protokol melalui perbaikan pada mekanisme PIOPSumCheck yang ada, terutama dalam menangani verifikasi polinomial multivariat yang lebih kompleks, menyediakan dukungan fungsional 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, virtual