Analisis Prinsip Binius STARKs dan Pemikiran Optimalisasi

1 Pendahuluan

Salah satu alasan utama efisiensi STARKs yang rendah adalah: sebagian besar nilai dalam program nyata cukup kecil, seperti indeks dalam loop for, nilai boolean, penghitung, dan sebagainya. Namun, untuk memastikan keamanan pembuktian 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.

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

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

• Standar Enkripsi Lanjutan (AES), berbasis domain F28;

• Kode autentikasi pesan Galois ( 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 mencapai babak final SHA-3, yang didasarkan 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. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu memasuki perluasan, tetapi hanya perlu beroperasi di bawah bidang dasar, sehingga mencapai efisiensi tinggi dalam bidang kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu masuk ke perluasan yang lebih besar untuk memastikan keamanan yang diperlukan.

Ketika membangun sistem pembuktian berdasarkan domain biner, terdapat 2 masalah praktis: ukuran domain yang digunakan saat menghitung representasi jejak di STARKs harus lebih besar dari derajat polinomial; saat berkomitmen pada pohon Merkle di STARKs, perlu dilakukan pengkodean Reed-Solomon, dan ukuran domain yang digunakan harus lebih besar dari ukuran setelah perpanjangan pengkodean.

Binius telah mengajukan solusi inovatif yang menangani kedua masalah ini secara terpisah dan merepresentasikan data yang sama dengan dua cara yang berbeda: pertama, menggunakan polinomial multivariat (khususnya polinomial multilinear) sebagai pengganti polinomial univariat, dengan merepresentasikan seluruh jejak komputasi melalui nilai-nilainya di "hyperkuadrat" (hypercubes); kedua, karena panjang setiap dimensi hyperkuadrat adalah 2, tidak mungkin untuk melakukan perluasan Reed-Solomon standar seperti STARKs, namun hyperkuadrat dapat dipandang sebagai persegi (square), dan perluasan Reed-Solomon dilakukan berdasarkan persegi tersebut. Metode ini secara signifikan meningkatkan efisiensi pengkodean dan kinerja komputasi sambil memastikan keamanan.

2 Analisis Prinsip

Saat ini, sebagian besar konstruk sistem SNARKs 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 yang dimasukkan 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 dengan hanya menanyakan hasil evaluasi dari sejumlah kecil 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 Polinomial (Polynomial Commitment Scheme, PCS): Skema komitmen polinomial digunakan untuk membuktikan apakah kesetaraan polinomial yang dihasilkan oleh PIOP berlaku. PCS adalah alat kriptografi yang memungkinkan pihak pembuktian untuk mengkomit sebuah 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. 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: Dihasilkan 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: Menggunakan PLONK PIOP dan FRI PCS yang digabungkan, dan berdasarkan domain Goldilocks. Plonky2 dirancang untuk mencapai rekursi yang efisien. Dalam merancang sistem-sistem ini, pilihan PIOP dan PCS yang digunakan harus sesuai dengan medan hingga 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 yang dapat dipercaya, dan apakah dapat mendukung fungsi ekstensi seperti bukti rekursif atau bukti agregasi.

Binius: HyperPlonk PIOP + Brakedown PCS + bidang biner. Secara spesifik, Binius mencakup lima teknologi kunci untuk mencapai efisiensi dan keamanannya. Pertama, aritmetika yang didasarkan pada menara bidang biner (towers of binary fields) membentuk dasar perhitungannya, 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 verifikasi hubungan multilinear di 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), memungkinkannya untuk mewujudkan sistem pembuktian yang efisien di bidang biner, dan mengurangi biaya yang biasanya terkait dengan bidang besar.

2.1 Ruang Terbatas: Arithmetisasi berdasarkan menara bidang biner

Bidang biner bertingkat adalah kunci untuk mewujudkan 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 atas bidang biner dapat dinyatakan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, ditambah kemampuan untuk memanfaatkan sepenuhnya karakteristik hierarkisnya melalui struktur menara, menjadikan bidang biner sangat cocok untuk sistem pembuktian yang dapat diskalakan seperti Binius.

Di mana "kanonik" mengacu pada representasi unik dan langsung dari elemen dalam bidang biner. Sebagai contoh, dalam bidang biner paling dasar F2, sembarang string k-bit dapat dipetakan langsung ke elemen bidang biner k-bit. Ini berbeda dengan bidang prima, di mana bidang prima tidak dapat memberikan representasi normatif semacam itu dalam jumlah bit yang ditentukan. Meskipun bidang prima 32-bit dapat dimasukkan dalam 32-bit, tidak setiap string 32-bit dapat secara unik diasosiasikan dengan elemen bidang, sementara bidang biner memiliki kemudahan pemetaan satu-ke-satu ini. Dalam bidang prima Fp, metode reduksi yang umum termasuk reduksi Barrett, reduksi Montgomery, dan metode reduksi khusus untuk bidang berhingga 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 "Menjelajahi Ruang Desain Implementasi Perangkat Keras ECC Bidang Prima vs. Bidang Biner" menunjukkan bahwa dalam operasi penjumlahan dan perkalian bidang biner tidak perlu memperkenalkan pembawa, dan operasi kuadrat dalam 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 ditafsirkan dengan berbagai cara dalam konteks bidang biner. Itu dapat dianggap sebagai elemen unik dalam bidang biner 128-bit, atau diuraikan menjadi dua elemen bidang menara 64-bit, empat elemen bidang menara 32-bit, 16 elemen bidang 8-bit, atau 128 elemen bidang F2. Fleksibilitas representasi ini tidak memerlukan beban perhitungan tambahan, hanya sekadar konversi tipe (typecast) dari string bit, merupakan atribut yang sangat menarik dan berguna. Selain itu, elemen bidang kecil dapat dikemas menjadi elemen bidang yang lebih besar tanpa memerlukan beban perhitungan tambahan. Protokol Binius memanfaatkan fitur ini untuk meningkatkan efisiensi perhitungan. Selain itu, makalah "On Efficient Inversion in Tower Fields of Characteristic Two" membahas kompleksitas perhitungan dari operasi perkalian, kuadrat, dan invers di bidang biner bertingkat n-bit (yang dapat dipecah menjadi sub-bidang m-bit).

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

Desain PIOP dalam protokol Binius mengacu pada 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 multivariat f dan g di hypercube Boolean adalah relasi permutasi f(x) = f(π(x)), untuk memastikan konsistensi penyusunan antara variabel polinomial.

3. LookupCheck: Memverifikasi apakah evaluasi polinomial ada dalam tabel pencarian yang diberikan, yaitu f(Bµ) ⊆ T(Bµ), memastikan beberapa nilai ada 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 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 kebenaran hasil kali polinomial.

6. ZeroCheck: Memverifikasi apakah suatu polinomial multivariat pada hiperkubus Boolean di titik mana pun adalah nol ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, untuk memastikan distribusi titik nol dari polinomial tersebut.

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 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 seluruh hypercube, dan hasil kali 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 secara memadai, yang menyebabkan ketidakmampuan untuk menegaskan bahwa U tidak nol pada hiperkubus; Binius dengan benar menangani masalah ini, bahkan ketika penyebutnya nol, ProductCheck Binius dapat terus memproses, memungkinkan untuk diperluas ke nilai produk apa pun.

• Pemeriksaan Permutasi Lintas Kolom: HyperPlonk tidak memiliki fitur 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 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 multiliniar baru------cocok untuk hypercube boolean

Dalam protokol Binius, konstruksi dan pemrosesan polinomial virtual adalah salah satu teknologi utama, yang secara efisien dapat menghasilkan dan memanipulasi polinomial yang berasal dari pegangan input atau polinomial virtual lainnya. Berikut adalah dua metode utama:

• Pengemasan：Metode ini mengoptimalkan operasi dengan mengemas elemen-elemen yang lebih kecil yang berdekatan dalam urutan kamus menjadi elemen yang lebih besar. Operator Pack menargetkan operasi blok dengan ukuran 2κ dan menggabungkannya