Analisis Prinsip Binius STARKs dan Pemikiran Optimalisasi

1 Pendahuluan

Tidak seperti SNARK berbasis kurva elips, STARK dapat dianggap sebagai SNARK berbasis hash. Salah satu alasan utama inefisiensi STARK saat ini adalah bahwa sebagian besar nilai dalam program yang sebenarnya kecil, seperti indeks dalam loop for, nilai benar dan salah, penghitung, dll. Namun, untuk memastikan keamanan bukti berbasis pohon Merkle, ketika data diperluas dengan pengkodean Reed-Solomon, banyak nilai redundan tambahan menempati seluruh domain, meskipun nilai asli itu sendiri sangat kecil. Untuk mengatasi masalah ini, mengurangi ukuran domain menjadi strategi utama.

Seperti yang ditunjukkan pada Tabel 1, STARK generasi pertama adalah 252 bit, STARK generasi kedua adalah 64 bit, dan STARK generasi ketiga adalah 32 bit. Sebaliknya, domain biner memungkinkan operasi penyelarasan bit langsung dan kompak dan efisien dalam pengkodean tanpa membuang-buang ruang, yaitu, STARK generasi ke-4.

Tabel 1: Jalur Evolusi STARK

| Fitur | STARK generasi ke-1 | STARK generasi ke-2 | STARK generasi ke-3 | Generasi ke-4 STARKs(Binius) | |------|-------------|-------------|-------------|---------------------| | Lebar bit kode | 252bit | 64bit | 32bit | 1bit | | Sistem Perwakilan | Bintang Bintang | Plonky2 | Beruang Bayi | Binius |

Dibandingkan dengan domain terbatas yang ditemukan dalam beberapa tahun terakhir, seperti Goldilocks, BabyBear, dan Mersenne31, studi tentang domain biner dapat ditelusuri kembali ke tahun 80-an abad terakhir. Saat ini, domain biner telah banyak digunakan dalam kriptografi, contoh tipikal meliputi:

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

• Kode otentikasi pesan Galois (GMAC), berdasarkan domain F2128;

• Kode QR, menggunakan pengkodean Reed-Solomon berbasis F28;

• Protokol FRI dan zk-STARK asli, serta fungsi hash Grøstl yang berhasil mencapai finalis SHA-3, yang didasarkan pada domain F28 dan merupakan algoritma hashing yang sangat cocok untuk rekursi.

Saat menggunakan domain yang lebih kecil, memperluas operasi domain menjadi semakin penting untuk memastikan keamanan. Domain biner yang digunakan oleh Binius, di sisi lain, perlu sepenuhnya mengandalkan ekspansi domain untuk memastikan keamanan dan ketersediaan aktualnya. Sebagian besar polinomial yang terlibat dalam perhitungan Prover tidak perlu memasuki domain yang diperluas, tetapi hanya perlu beroperasi di bawah domain dasar, sehingga mencapai efisiensi tinggi dalam domain kecil. Namun, pemeriksaan titik acak dan perhitungan FRI masih perlu dibor ke area ekspansi yang lebih besar untuk memastikan keamanan yang diperlukan.

Saat membangun sistem pembuktian berdasarkan domain biner, ada dua masalah praktis: saat menghitung representasi jejak dalam STARK, ukuran domain yang digunakan harus lebih besar dari urutan polinomial; Ketika pohon Merkle dijanjikan dalam STARK, itu perlu dikodekan dalam Reed-Solomon, dan ukuran domain yang digunakan harus lebih besar dari ukuran ekstensi pengkodean.

Binius mengusulkan solusi inovatif yang menangani kedua masalah ini secara terpisah dan melakukannya dengan merepresentasikan data yang sama dalam dua cara berbeda: pertama, menggunakan polinomial multivariat (khususnya, multilinier) alih-alih polinomial univariat, dan mewakili seluruh lintasan komputasi dengan nilainya pada "hiperkubus"; Kedua, karena panjang setiap dimensi hypercube adalah 2, tidak mungkin untuk melakukan ekstensi Reed-Solomon standar seperti STARK, tetapi hypercube dapat diperlakukan sebagai persegi berdasarkan ekstensi Reed-Solomon. Metode ini sangat meningkatkan efisiensi pengkodean dan kinerja komputasi sekaligus memastikan keamanan.

2 Analisis Prinsip

Konstruksi sebagian besar sistem SNARK saat ini biasanya terdiri dari dua bagian berikut:

• Bukti Oracle Interaktif Polinomial Teoritis Informasi (PIOP) :P IOP sebagai inti dari sistem pembuktian, mengubah hubungan komputasi input menjadi persamaan polinomial yang dapat diverifikasi. Protokol PIOP yang berbeda memungkinkan pembuktian untuk mengirim polinomial selangkah demi selangkah dengan berinteraksi dengan validator, memungkinkan validator untuk memverifikasi bahwa perhitungan sudah benar dengan menanyakan hasil evaluasi sejumlah kecil polinomial. Protokol PIOP yang ada termasuk PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, yang semuanya menangani ekspresi polinomial secara berbeda, yang memengaruhi kinerja dan efisiensi seluruh sistem SNARK.

• Skema Komitmen Polinomial (PCS): Skema Komitmen Polinomial digunakan untuk membuktikan apakah persamaan polinomial yang dihasilkan oleh PIOP benar. PCS adalah alat kriptografi di mana pembuktian dapat berkomitmen pada polinomial tertentu dan kemudian memverifikasi hasil evaluasi polinomial tersebut, sambil menyembunyikan informasi lain tentang polinomial tersebut. Skema komitmen polinomial umum termasuk KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP), dan Brakedown. PCS yang berbeda memiliki skenario kinerja, keamanan, dan aplikasi yang berbeda.

Sesuai dengan persyaratan khusus, PIOP dan PCS yang berbeda dapat dipilih, dan dikombinasikan dengan medan hingga atau kurva eliptik yang sesuai, sistem bukti dengan sifat berbeda dapat dibangun. Misalnya:

• Halo2: Didukung oleh PLONK PIOP yang dikombinasikan dengan PCS Antipeluru dan berdasarkan kurva Pasta. Halo2 dirancang dengan mempertimbangkan skalabilitas, serta menghapus pengaturan tepercaya dari protokol ZCash.

• Plonky2: Menggabungkan PLONK PIOP dengan FRI PCS dan didasarkan pada domain Goldilocks. Plonky2 adalah untuk rekursi yang efisien. Saat merancang sistem ini, PIOP dan PCS yang dipilih harus sesuai dengan domain hingga atau kurva eliptik yang digunakan untuk memastikan kebenaran, kinerja, dan keamanan sistem. Pilihan kombinasi ini tidak hanya memengaruhi ukuran bukti dan efisiensi verifikasi SNARK, tetapi juga menentukan apakah sistem dapat mencapai transparansi tanpa memerlukan pengaturan tepercaya, dan apakah dapat mendukung fungsi yang diperluas seperti bukti rekursif atau bukti agregat.

Binius: HyperPlonk PIOP + Brakedown PCS + Domain Biner. Secara khusus, Binius menyertakan lima teknologi utama untuk mencapai efisiensi dan keamanannya. Pertama-tama, aritmatika berdasarkan menara medan biner membentuk dasar perhitungannya, yang dapat mewujudkan operasi yang disederhanakan di bidang biner. Kedua, dalam Oracle Proof Protocol (PIOP) interaktifnya, Binius mengadaptasi produk HyperPlonk dan pemeriksaan permutasi untuk memastikan pemeriksaan konsistensi yang aman dan efisien antara variabel dan permutasinya. Ketiga, protokol memperkenalkan argumen pergeseran multilinier baru untuk mengoptimalkan efisiensi memverifikasi hubungan multilinier pada domain kecil. Keempat, Binius mengadopsi versi yang ditingkatkan dari argumen pencarian Lasso, yang memberikan fleksibilitas dan keamanan yang kuat untuk mekanisme pencarian. Akhirnya, protokol menggunakan skema komitmen polinomial medan kecil (Small-Field PCS), yang memungkinkannya untuk mengimplementasikan sistem pembuktian yang efisien pada domain biner dan mengurangi overhead yang biasanya terkait dengan domain besar.

2.1 Bidang Terbatas: Aritmatika berdasarkan Menara Bidang Biner

Domain biner menara adalah kunci untuk komputasi yang dapat diverifikasi dengan cepat, yang terutama dikaitkan dengan dua aspek: komputasi yang efisien dan aritmatika yang efisien. Domain biner secara inheren mendukung operasi aritmatika yang sangat efisien, menjadikannya ideal untuk aplikasi kriptografi yang sensitif terhadap persyaratan kinerja. Selain itu, struktur domain biner mendukung proses aritmatika yang disederhanakan, yaitu, operasi yang dilakukan pada domain biner dapat direpresentasikan dalam bentuk aljabar yang ringkas dan mudah diverifikasi. Fitur-fitur ini, dikombinasikan dengan kemampuan untuk memanfaatkan sepenuhnya sifat hierarkisnya melalui struktur menara, membuat domain biner sangat cocok untuk sistem bukti yang dapat diskalakan seperti Binius

di mana "kanonik" mengacu pada representasi unik dan langsung dari suatu 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 bidang bilangan prima, yang tidak dapat memberikan representasi kanonik seperti itu dalam posisi yang diberikan. Meskipun bidang bilangan prima 32-bit dapat terkandung dalam sistem 32-bit, tidak setiap string 32-bit secara unik sesuai dengan elemen domain, dan bidang biner memiliki kenyamanan pemetaan satu-ke-satu ini. Dalam domain prima Fp, metode reduksi umum termasuk reduksi Barrett, reduksi Montgomery, dan metode reduksi khusus untuk medan hingga tertentu seperti Mersenne-31 atau Goldilocks-64. Dalam domain biner F2k, metode reduksi yang umum digunakan termasuk reduksi khusus (misalnya, digunakan dalam AES), reduksi Montgomery (misalnya, digunakan dalam POLYVAL), dan reduksi rekursif (misalnya, Tower). Makalah "Menjelajahi Ruang Desain Bidang Utama vs. Implementasi Perangkat Keras ECC Bidang Biner" menunjukkan bahwa domain biner tidak perlu memperkenalkan carry baik dalam penjumlahan maupun perkalian, dan bahwa operasi kuadrat domain biner sangat efisien karena mengikuti (X + Y )2 = X2 + Y 2.

! Penelitian Bitlayer: Analisis Prinsip Binius STARK dan Pemikiran Pengoptimalan

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 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" mengeksplorasi kompleksitas komputasi operasi perkalian, kuadrat, dan inversi dalam domain biner menara n-bit yang dapat diuraikan menjadi subdomain m-bit.

2.2 PIOP: Produk HyperPlonk yang Diadaptasi dan PermutasiPeriksa ------ untuk domain biner

Desain PIOP dalam protokol Binius meminjam dari HyperPlonk dan menggunakan serangkaian mekanisme pemeriksaan inti untuk memverifikasi kebenaran polinomial dan himpunan multivariat. Tes inti ini meliputi:

1. GateCheck: Verifikasi apakah saksi rahasia ω dan input publik x memenuhi hubungan operasi sirkuit C(x, ω)=0 untuk memastikan pengoperasian sirkuit yang benar.

2. PermutasiCheck: Verifikasi bahwa hasil evaluasi dari dua polinomial multivariat f dan g pada hiperkubus Boolean adalah hubungan permutasi f(x) = f(π(x)) untuk memastikan konsistensi dalam pengaturan antara variabel polinomial.

3. LookupCheck: Verifikasi bahwa polinomial mengevaluasi dalam tabel pencarian tertentu, yaitu, f(Bμ) ⊆ T(Bμ), memastikan bahwa nilai tertentu berada dalam rentang yang ditentukan.

4. MultisetCheck: Periksa apakah dua himpunan multivariat sama, yaitu, {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H untuk memastikan konsistensi di antara beberapa himpunan.

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

6. ZeroCheck: Verifikasi bahwa polinomial multivariat adalah nol pada titik mana pun pada hypercube∏x∈Hμ Boolean f(x) = 0,∀x ∈ Bμ untuk memastikan distribusi nol polinomial.

7. SumCheck: Memeriksa apakah nilai jumlah polinomial multivariat adalah nilai yang dinyatakan ∑x∈Hμ f(x) = s. Dengan mengubah masalah evaluasi polinomial multivariat menjadi evaluasi polinomial univariat, kompleksitas komputasi verifikator berkurang. Selain itu, SumCheck juga memungkinkan pemrosesan batch, dengan memperkenalkan angka acak, membangun kombinasi linier untuk mencapai pemrosesan batch dari beberapa instance pemeriksaan jumlah.

8. BatchCheck: Berdasarkan SumCheck, verifikasi kebenaran beberapa evaluasi polinomial multivariat untuk meningkatkan efisiensi protokol.

Meskipun ada banyak kesamaan antara Binius dan HyperPlonk dalam hal desain protokol, Binius telah melakukan perbaikan dalam tiga aspek berikut:

• Pengoptimalan ProductCheck: Di HyperPlonk, ProductCheck mengharuskan penyebut U bukan nol di mana-mana pada hypercube, dan produk harus sama dengan nilai tertentu; Binius menyederhanakan proses pemeriksaan ini dengan mengkhususkan nilai ini menjadi 1, sehingga mengurangi kompleksitas komputasi.

• Penanganan masalah bagi-nol: HyperPlonk gagal menangani kasus pembagi-nol secara memadai, mengakibatkan ketidakmampuan untuk menegaskan masalah bukan nol U pada hypercube; Binius menangani ini dengan benar, dan ProductCheck Binius terus memproses bahkan ketika penyebutnya nol, memungkinkan generalisasi ke nilai produk yang sewenang-wenang.

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

Oleh karena itu, melalui peningkatan mekanisme PIOPSumCheck yang ada, Binius meningkatkan fleksibilitas dan efisiensi protokol, terutama ketika berhadapan dengan verifikasi polinomial multivariat yang lebih kompleks, dan memberikan dukungan fungsional yang lebih kuat. Peningkatan ini tidak hanya mengatasi keterbatasan di HyperPlonk, tetapi juga menyediakan fondasi berbasis biner untuk masa depan