1. Pengantar

Berbeda dari SNARK berbasis kurva eliptik, STARK dapat dilihat sebagai SNARK berbasis hash. Salah satu tantangan utama yang berkontribusi pada ketidakefisienan STARK saat ini adalah bahwa sebagian besar nilai dalam program aktual relatif kecil, seperti indeks dalam loop for, nilai boolean, dan penghitung. Namun, untuk memastikan keamanan bukti berbasis pohon Merkle, encoding Reed-Solomon digunakan untuk memperpanjang data, menghasilkan banyak nilai redundan yang menempati seluruh bidang, bahkan ketika nilai asli itu sendiri kecil. Untuk mengatasi ketidaksempurnaan ini, mengurangi ukuran bidang telah menjadi strategi utama.

Seperti yang ditunjukkan dalam Tabel 1, generasi pertama STARKs memiliki lebar pengodean 252 bit, generasi kedua 64 bit, dan generasi ketiga 32 bit. Meskipun lebar pengodean yang lebih kecil pada generasi ketiga, tetap ada ruang yang terbuang secara signifikan. Sebaliknya, bidang biner memungkinkan manipulasi bit langsung, memungkinkan pengodean yang ringkas dan efisien dengan pemborosan minimal. Efisiensi ini terwujud dalam generasi keempat STARKs.

Tabel 1: Jalur Derivasi STARKs

Dibandingkan dengan lapangan terbatas seperti Goldilocks, BabyBear, dan Mersenne31 yang baru-baru ini mendapat perhatian, penelitian lapangan biner sudah ada sejak tahun 1980-an. Saat ini, lapangan biner secara luas digunakan dalam kriptografi, dengan contoh terkenal termasuk:

• Advanced Encryption Standard (AES), berdasarkan pada
• 𝐹28
• bidang;
• Kode Otentikasi Pesan Galois (GMAC), berdasarkan pada
• F2128
• field;
• Kode QR, yang menggunakan encoding Reed-Solomon berdasarkan pada
• 𝐹28
• lapangan;
• Protokol asli FRI dan zk-STARK, serta fungsi hash Grøstl, finalis dalam kompetisi SHA-3, yang didasarkan pada
• 𝐹28
• field dan cocok untuk algoritma hash rekursif.

Ketika lapangan yang lebih kecil digunakan, operasi perluasan lapangan menjadi semakin penting untuk menjamin keamanan. Lapangan biner yang digunakan oleh Binius sepenuhnya mengandalkan perluasan lapangan untuk menjamin keamanan dan kegunaan praktis. Sebagian besar komputasi polinomial yang terlibat dalam operasi Prover tidak perlu memasuki lapangan yang diperluas, karena mereka hanya perlu beroperasi di lapangan dasar, sehingga mencapai efisiensi tinggi dalam lapangan kecil. Namun, pemeriksaan titik acak dan komputasi FRI masih harus dilakukan dalam lapangan yang lebih besar untuk memastikan tingkat keamanan yang diperlukan.

Ada dua tantangan praktis saat membangun sistem bukti berdasarkan bidang biner: Pertama, ukuran bidang yang digunakan untuk representasi jejak dalam STARKs harus lebih besar dari derajat polinomial. Kedua, ukuran bidang yang digunakan untuk komitmen pohon Merkle dalam STARKs harus lebih besar dari ukuran setelah ekstensi encoding Reed-Solomon.

Binius adalah solusi inovatif untuk mengatasi dua masalah ini dengan mewakili data yang sama dengan dua cara berbeda: Pertama, dengan menggunakan polinomial multivariat (khususnya polinomial multilinear) alih-alih polinomial univariat, mewakili jejak komputasi keseluruhan melalui evaluasi mereka di atas "hiperkubus." Kedua, karena setiap dimensi dari hiperkubus memiliki panjang 2, tidak mungkin untuk melakukan ekstensi Reed-Solomon standar seperti dalam STARKs, tetapi hiperkubus dapat dianggap sebagai persegi, dan ekstensi Reed-Solomon dapat dilakukan berdasarkan persegi ini. Metode ini tidak hanya menjamin keamanan tetapi juga sangat meningkatkan efisiensi pengkodean dan kinerja komputasi.

2. Prinsip Binius

Konstruksi dari sebagian besar sistem SNARK modern umumnya terdiri dari dua komponen berikut:

• Bukti Orakel Interaktif Polinomial Teoretis Informasi (PIOP): Sebagai inti dari sistem bukti, PIOP mengubah hubungan komputasi dari input menjadi persamaan polinomial yang dapat diverifikasi. Berbagai protokol PIOP memungkinkan pembuktian untuk mengirimkan polinomial secara bertahap melalui interaksi dengan pemeriksa. Hal ini memungkinkan pemeriksa untuk mengonfirmasi kebenaran suatu komputasi dengan hanya melakukan kueri terhadap sejumlah kecil evaluasi polinomial. Berbagai protokol PIOP, seperti PLONK PIOP, Spartan PIOP, dan HyperPlonk PIOP, menangani ekspresi polinomial secara berbeda, memengaruhi kinerja dan efisiensi dari sistem SNARK secara keseluruhan.
• Polynomial Commitment Scheme (PCS): PCS adalah alat kriptografi yang digunakan untuk membuktikan bahwa persamaan polinomial yang dihasilkan oleh PIOP valid. Ini memungkinkan pihak yang membuktikan untuk berkomitmen pada polinomial dan memverifikasi evaluasinya tanpa mengungkapkan informasi tambahan tentang polinomial tersebut. Skema PCS umum meliputi KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP), dan Brakedown, masing-masing menawarkan karakteristik kinerja yang berbeda, jaminan keamanan, dan skenario yang dapat diterapkan.

Dengan memilih skema PIOPs dan PCS yang berbeda, dan menggabungkannya dengan lapangan terbatas atau kurva eliptik yang sesuai, seseorang dapat membangun sistem bukti dengan properti yang berbeda. Misalnya:

• Halo2: Menggabungkan PLONK PIOP dengan Bulletproofs PCS dan beroperasi pada kurva Pasta. Halo2 dirancang dengan skalabilitas dalam pikiran dan menghilangkan setup terpercaya yang sebelumnya digunakan dalam protokol ZCash.
• Plonky2: Menggabungkan PLONK PIOP dengan FRI PCS dan didasarkan pada lapangan Goldilocks. Plonky2 dioptimalkan untuk rekursi yang efisien.

Ketika merancang sistem-sistem ini, kesesuaian antara PIOP, PCS, dan lapangan hingga atau kurva eliptik yang dipilih sangat penting untuk memastikan kebenaran, kinerja, dan keamanan. Kombinasi-kombinasi ini mempengaruhi ukuran bukti SNARK, efisiensi verifikasi, dan menentukan apakah sistem dapat mencapai transparansi tanpa setup yang dipercayai, serta mendukung fitur-fitur canggih seperti bukti rekursif atau agregasi bukti.

Binius menggabungkan HyperPlonk PIOP dengan Brakedown PCS dan beroperasi di bidang biner. Secara khusus, Binius menggabungkan lima teknologi kunci untuk mencapai efisiensi dan keamanan:

1. Aritmatika berdasarkan menara medan biner: Ini membentuk dasar komputasi Binius, memungkinkan operasi yang disederhanakan dalam medan biner.
2. Produk HyperPlonk dan pemeriksaan permutasi: Binius menyesuaikan pemeriksaan produk dan permutasi HyperPlonk dalam PIOP-nya untuk memastikan konsistensi yang aman dan efisien antara variabel dan permutasi mereka.
3. Argumen pergeseran multilinear baru: Optimisasi ini meningkatkan verifikasi hubungan multilinear dalam bidang-bidang kecil, meningkatkan efisiensi secara keseluruhan.
4. Argumen pencarian Lasso yang diperbaiki: Protokol ini menggabungkan mekanisme pencarian yang lebih fleksibel dan aman dengan argumen canggih ini.
5. Skema Komitmen Polinomial Small-Field (PCS): Binius menggunakan PCS yang disesuaikan untuk lapangan kecil, mengurangi overhead yang biasanya terkait dengan lapangan yang lebih besar dan memungkinkan sistem bukti yang efisien di lapangan biner.

Inovasi-inovasi ini memungkinkan Binius untuk menawarkan sistem SNARK yang kompak dan berkualitas tinggi, dioptimalkan untuk bidang biner sambil tetap menjaga keamanan dan skalabilitas yang kuat.

2.1 Lapangan Hingga: Aritmatika Berdasarkan Menara Lapangan Binari

Menara medan biner memainkan peran penting dalam mencapai komputasi yang cepat dan dapat diverifikasi karena dua faktor utama: komputasi yang efisien dan aritmetika yang efisien. Medan biner secara inheren mendukung operasi aritmetika yang sangat efisien, membuatnya ideal untuk aplikasi kriptografi yang sensitif terhadap performa. Selain itu, struktur mereka memungkinkan proses aritmetika yang disederhanakan, di mana operasi yang dilakukan dalam medan biner dapat direpresentasikan dalam bentuk aljabar yang kompak dan mudah diverifikasi. Karakteristik ini, dikombinasikan dengan struktur hierarkis dari menara medan biner, membuatnya sangat cocok untuk sistem bukti yang dapat diskalakan seperti Binius.

Istilah 'canonical' mengacu pada representasi unik dan langsung dari elemen-elemen dalam bidang biner. Misalnya, dalam bidang biner paling dasar $\mathbb{F}2

,anyk−bitstringcanbedirectlymappedtoak−bitbinaryfieldelement.Thisdiffersfromprimefields,whichdonotoffersuchacanonicalrepresentationwithinagivennumberofbits.Althougha32−bitprimefieldcanfitwithin32bits,notevery32−bitstringcanuniquelycorrespondtoafieldelement,whereasbinaryfieldsprovidethisone−to−onemapping.Inprimefields

\mathbb{F}_p$ , metode pengurangan umum meliputi pengurangan Barrett, pengurangan Montgomery, serta metode pengurangan khusus untuk lapangan hingga tertentu seperti Mersenne-31 atau Goldilocks-64 . Dalam lapangan biner $\mathbb{F}{2^k}$ , metode pengurangan umum meliputi pengurangan khusus (seperti yang digunakan dalam AES), pengurangan Montgomery (seperti yang digunakan dalam POLYVAL), dan pengurangan rekursif (seperti yang digunakan dalam lapangan Tower). Kertas ini Menjelajahi Ruang Desain Implementasi Perangkat Keras ECC Bidang Utama vs. Bidang Binercatatan bahwa bidang biner tidak memerlukan propagasi carry dalam penjumlahan atau perkalian, dan pengkuadratan dalam bidang biner sangat efisien karena aturan penyederhanaan

(𝑋+𝑌)2=𝑋2+𝑌2

.

Gambar 1. Menara Lapangan Biner

Seperti yang ditunjukkan dalam Gambar 1, sebuah string 128-bit dapat diinterpretasikan dalam beberapa cara dalam konteks bidang biner. Ini dapat dilihat sebagai elemen unik dalam bidang biner 128-bit, atau dapat diuraikan sebagai dua elemen bidang menara 64-bit, empat elemen bidang menara 32-bit, enam belas elemen bidang menara 8-bit, atau 128 elemen dari

𝐹2

. Fleksibilitas dalam representasi ini tidak menimbulkan beban komputasi, karena itu hanya merupakan pengubahan jenis dari rangkaian bit. Ini adalah properti yang sangat menarik dan berguna, karena elemen bidang yang lebih kecil bisa dikemas ke dalam elemen bidang yang lebih besar tanpa biaya komputasi tambahan. Protokol Binius memanfaatkan properti ini untuk meningkatkan efisiensi komputasi. Selain itu, kertas ini Pada Inversi Efisien di Bidang Menara dengan Karakteristik Duamenjelajahi kompleksitas komputasi perkalian, pengkuadratan, dan inversi dalam

𝑛

bidang biner menara-bit (dapat diurai menjadi

𝑚

-bit subfields).

2.2 PIOP: Produk HyperPlonk yang Diadaptasi dan Pemeriksaan Permutasi - Sesuai untuk Lapangan Biner

Desain PIOP dalam protokol Binius terinspirasi dari HyperPlonk dan menggabungkan serangkaian pemeriksaan inti untuk memverifikasi kebenaran polinomial dan himpunan multivariat. Pemeriksaan ini penting untuk memastikan integritas komputasi dalam sistem bukti, terutama saat beroperasi di bidang biner. Pemeriksaan kunci termasuk:

1. gateCheck: Memastikan bahwa saksi pribadi
2. 𝜔
3. dan input publik
4. 𝑥
5. memuaskan hubungan operasi sirkuit
6. 𝐶(𝑥,𝜔)=0
7. , memverifikasi eksekusi yang benar dari sirkuit.
8. PermutationCheck: Memverifikasi hasil evaluasi dua polinomial multivariat
9. 𝑓
10. dan
11. 𝑔
12. pada bentuk kubus Boolean hyper memperoleh hubungan permutasi
13. 𝑓(𝑥)=𝑓(𝜋(𝑥))
14. , memastikan konsistensi antara variabel polinomial.
15. LookupCheck: Memeriksa apakah evaluasi polinomial berada dalam tabel pencarian yang diberikan, yaitu,
16. 𝑓(𝐵𝜇)⊆𝑇(𝐵𝜇)
17. , memastikan bahwa nilai-nilai tertentu jatuh dalam rentang yang ditentukan.
18. MultisetCheck: Mengonfirmasi apakah dua set multivariat sama, yaitu, ${(x{1,i},x{2,i})}{i \in H} = {(y{1,i},y{2,i})}{i \in H}$, memastikan konsistensi antara himpunan yang berbeda.
19. ProductCheck: Memastikan bahwa evaluasi polinomial rasional pada hiperkubus Boolean sama dengan nilai yang dinyatakan, yaitu,
20. ∏𝑥∈𝐻𝜇𝑓(𝑥)=𝑠
21. , mengkonfirmasi kebenaran dari hasil perkalian polinomial.
22. ZeroCheck: Memverifikasi apakah polinom multivariat menghasilkan nilai nol pada titik mana pun pada hiperkubus Boolean, yaitu,
23. ∏𝑥∈𝐻𝜇𝑓(𝑥)=0
24. untuk semua
25. 𝑥∈𝐵𝜇
26. , memastikan distribusi nol yang tepat dalam polinomial.
27. SumCheck: Mengkonfirmasi apakah jumlah evaluasi polinomial multivariat sama dengan nilai yang dinyatakan, yaitu,
28. ∑𝑥∈𝐻𝜇𝑓(𝑥)=𝑠
29. Dengan mengurangi evaluasi polinomial multivariat menjadi evaluasi polinomial univariat, SumCheck menurunkan kompleksitas komputasi verifikator. SumCheck juga memungkinkan untuk penggabungan, yang membangun kombinasi linear menggunakan angka acak untuk memproses beberapa instansi sekaligus.
30. BatchCheck: Sebuah perluasan dari SumCheck, ia memverifikasi kebenaran dari beberapa evaluasi polinomial multivariat, meningkatkan efisiensi protokol.

Sementara Binius dan HyperPlonk memiliki beberapa kesamaan dalam desain protokol mereka, Binius memperkenalkan peningkatan kunci berikut:

1. Optimisasi ProductCheck: Dalam HyperPlonk, ProductCheck membutuhkan penyebut
2. 𝑈
3. untuk menjadi non-nol di seluruh hiperkubus, dan bahwa produknya cocok dengan nilai tertentu. Binius menyederhanakan pemeriksaan ini dengan mengatur nilai produk menjadi 1, mengurangi kompleksitas komputasi secara keseluruhan.
4. Penanganan Masalah Pembagian Nol: HyperPlonk tidak efektif dalam menangani masalah pembagian nol, sehingga sulit untuk menjamin bahwa
5. 𝑈
6. tetap non-nol di atas hiperkubus. Binius menyelesaikan ini dengan menangani skenario pembagian nol dengan benar, memungkinkan ProductCheck berfungsi bahkan ketika penyebutnya nol, memungkinkan untuk perluasan ke nilai produk sembarang.
7. Cross-Column PermutationCheck: HyperPlonk tidak mendukung pemeriksaan permutasi lintas kolom. Binius mengatasi keterbatasan ini dengan memperkenalkan dukungan untuk PermutationCheck lintas kolom, memungkinkan protokol untuk mengelola permutasi polinomial yang lebih kompleks di beberapa kolom.

Dengan demikian, Binius meningkatkan fleksibilitas dan efisiensi protokol dengan memperbaiki mekanisme PIOP SumCheck yang ada, terutama dengan menyediakan fungsi yang lebih kuat untuk memverifikasi polinomial multivariat yang lebih kompleks. Peningkatan ini tidak hanya mengatasi batasan HyperPlonk tetapi juga membentuk dasar bagi sistem masa depan yang terbukti berdasarkan bidang biner.

2.3 PIOP: Argumen Pergeseran Multilinear Baru - Berlaku untuk Hiperkubus Boolean

Dalam protokol Binius, manipulasi dan konstruksi polinomial virtual memainkan peran penting dalam memungkinkan penanganan polinomial yang efisien. Dua teknik utama digunakan untuk operasi-operasi ini:

• Packing: Metode pengemasan mengoptimalkan penanganan elemen-elemen lebih kecil dengan mengelompokkannya bersama di dalam domain yang lebih besar. Secara khusus, elemen-elemen yang berdekatan dalam urutan leksikografis dikemas dalam blok-blok yang lebih besar, biasanya dengan ukuran
• 2𝜅
• Dengan memanfaatkan Multilinear Extension (MLE), elemen-elemen yang dikemas diubah menjadi polinomial virtual baru, yang kemudian dapat dievaluasi dan diproses dengan efisien. Metode ini meningkatkan kinerja operasi pada hiperkubus Boolean dengan memperbarui fungsi secara struktural.
• 𝑡
• menjadi bentuk yang efisien secara komputasional.
• Operator Shift: Operator shift mengatur ulang elemen dalam sebuah blok dengan menggeser siklik mereka berdasarkan offset yang diberikan
• 𝑜
• . Perubahan ini berlaku untuk blok dengan ukuran
• 2b
• , memastikan bahwa semua elemen dalam blok digeser secara seragam sesuai dengan offset yang telah ditentukan. Operator ini sangat berguna saat menangani polinomial virtual dalam ruang berdimensi tinggi, karena kompleksitasnya meningkat secara linear dengan ukuran blok, menjadikannya teknik yang ideal untuk dataset besar atau perhitungan hiperkubus Boolean yang kompleks.

2.4 PIOP: Suatu Argumen Pencarian Lasso yang Disesuaikan - Berlaku untuk Bidang Biner

Protokol Lasso di Binius menawarkan metode yang sangat efisien untuk membuktikan bahwa elemen-elemen dalam sebuah vektor

𝑎∈𝐹𝑚

terkandung dalam tabel yang telah ditentukan

𝑡∈𝐹𝑛

Argumen pencarian ini memperkenalkan konsep "Lookup Singularity" dan sangat cocok untuk skema komitmen polinomial multilinear. Efisiensi dari Lasso dijelaskan dalam dua aspek utama:

• Efisiensi Bukti: Saat melakukan
• 𝑚
• pencarian dalam tabel dengan ukuran
• 𝑛
• , si pemberi bukti hanya perlu berkomitmen kepada
• m+n
• elemen lapangan kecil, dengan ukuran lapangan diambil dari himpunan
• 0,...,𝑚
• . Dalam skema kriptografi yang mengandalkan pemangkatan, biaya pembuktian adalah
• 𝑂(𝑚+𝑛)
• operasi grup (misalnya, penambahan titik kurva eliptik). Efisiensi ini datang sebagai tambahan biaya untuk memverifikasi apakah polinomial multilinear dievaluasi pada hypercube Boolean cocok dengan elemen tabel.
• Tidak Ada Komitmen untuk Tabel Besar: Jika tabel
• 𝑡
• Terstruktur, Lasso tidak memerlukan komitmen langsung ke tabel, sehingga memungkinkan untuk menangani tabel yang sangat besar (misalnya,
• 2128
• atau lebih). Waktu prosesor tergantung hanya pada entri khusus yang diakses dalam tabel. Untuk parameter integer apa pun
• 𝑐>1
• , biaya utama melibatkan ukuran bukti, yang bertambah seiring dengan
• 3⋅𝑐⋅𝑚+𝑐⋅𝑛1/𝑐
• elemen lapangan yang berkomitmen. Elemen-elemen ini juga kecil, diambil dari set
• 0, …, max𝑚, 𝑛1/𝑐, 𝑞−1
• , di mana
• 𝑞
• adalah nilai terbesar dalam vektor
• 𝑎
• .

Protokol Lasso terdiri dari tiga komponen inti:

1. Abstraksi Polinomial Virtual dari Tabel Besar: Protokol Lasso menggabungkan polinomial virtual untuk memungkinkan pencarian dan operasi efisien pada tabel besar, memastikan skalabilitas tanpa degradasi kinerja.
2. Pencarian Tabel Kecil: Di tengah Lasso terdapat pencarian tabel kecil, yang memverifikasi apakah polinomial virtual yang dievaluasi pada hiperkubus Boolean merupakan subset dari evaluasi polinomial virtual lainnya. Proses ini mirip dengan deteksi memori offline dan berubah menjadi tugas deteksi multiset.
3. Pengecekan Multiset : Protokol ini juga mencakup mekanisme virtual untuk melakukan pengecekan multiset, memastikan bahwa dua set elemen entah cocok atau memenuhi kondisi yang telah ditentukan.

Protokol Binius menyesuaikan Lasso untuk operasi lapangan biner, dengan asumsi lapangan saat ini adalah lapangan prima dengan karakteristik besar (jauh lebih besar dari panjang kolom yang dicari). Binius memperkenalkan versi perkalian dari protokol Lasso, yang mengharuskan pembuktian dan verifikator untuk meningkatkan operasi 'penghitung memori' protokol bukan hanya dengan menambahkan 1 tetapi dengan menambahkan menggunakan generator perkalian dalam lapangan biner. Namun, adaptasi perkalian ini memperkenalkan kompleksitas tambahan: tidak seperti peningkatan aditif, generator perkalian tidak selalu meningkat dalam semua kasus, tetapi memiliki satu orbit tunggal di 0, yang dapat menjadi vektor serangan. Untuk mengurangi potensi serangan ini, pembuktian harus berkomitmen pada vektor penghitung baca yang tidak nol di mana pun untuk memastikan keamanan protokol.

2.5 PCS: Adaptasi Brakedown PCS - Berlaku untuk Lapangan Kecil

Ide inti di balik konstruksi Binius PCS (Polynomial Commitment Scheme) adalah pengemasan. Binius paper menyajikan dua skema Brakedown PCS berdasarkan bidang biner: satu diwujudkan menggunakan kode yang disatukan, dan yang lain menggunakan pengkodean tingkat blok, yang mendukung penggunaan mandiri dari kode Reed-Solomon. Skema PCS Brakedown kedua menyederhanakan proses bukti dan verifikasi, meskipun menghasilkan ukuran bukti yang sedikit lebih besar daripada yang pertama; namun, pengorbanan ini sepadan dengan manfaat penyederhanaan dan implementasi yang ditawarkannya.

Komitmen polinomial Binius secara utama menggunakan komitmen polinomial lapangan kecil dengan evaluasi dalam lapangan yang diperluas, konstruksi universal lapangan kecil, dan pengkodean level blok dengan teknik kode Reed-Solomon.

Komitmen Polinomial Lapangan Kecil dengan Evaluasi Lapangan Diperpanjang Dalam protokol Binius, komitmen polinomial dilakukan di atas lapangan kecil

𝐾

, dengan evaluasi dilakukan di lapangan yang luas

𝐿/𝐾

Teknik ini memastikan bahwa polinomial multilinear

𝑡(𝑋0,…,𝑋ℓ−1)

termasuk ke dalam domain

𝐾[𝑋0,…,𝑋ℓ−1]

, sementara poin evaluasi berada di lapangan yang lebih besar

𝐿

. Struktur komitmen ini memungkinkan kueri yang efisien dalam bidang yang diperluas, menjaga keseimbangan keamanan dan efisiensi komputasi.

Konstruksi Universal Small-Field Konstruksi ini mendefinisikan parameter utama seperti bidang

𝐾

, dimensinya

ℓ

, dan kode blok linear yang terkait

C

, sambil memastikan bahwa bidang yang diperluas

𝐿

cukup besar untuk evaluasi yang aman. Dengan memanfaatkan sifat lapangan yang diperluas, Binius mencapai komitmen yang kuat melalui kode blok linear, menjaga keseimbangan antara efisiensi komputasi dan keamanan.

Pengkodean Level Blok dengan Kode Reed-Solomon untuk polinomial yang didefinisikan di atas lapangan kecil seperti $\mathbb{F}2

,theBiniusprotocolemploysblock−levelencodingusingReed−Solomoncodes.Thisschemeallowsefficientcommitmentofsmall−fieldpolynomialsbyencodingthemrow−by−rowintolargerfields(seperti

\mathbb{F}{2^{16}}$ ), memanfaatkan efisiensi dan sifat pemisahan jarak maksimum dari kode Reed-Solomon. Setelah pengodean, baris-baris ini dikomit menggunakan pohon Merkle, yang menyederhanakan kompleksitas operasional dari komitmen polinomial di bidang kecil. Pendekatan ini memungkinkan penanganan yang efisien terhadap polinomial di bidang kecil tanpa beban komputasi yang biasanya terkait dengan bidang yang lebih besar.

3. Optimisasi Binius

Untuk meningkatkan kinerja lebih lanjut, Binius menyertakan empat optimisasi utama:

1. PIOP berbasis GKR : Protokol GKR (Goldreich-Kalai-Rothblum) digunakan untuk menggantikan algoritma Pencarian Lasso dalam perkalian lapangan biner, secara signifikan mengurangi overhead dalam proses komitmen.
2. Optimasi ZeroCheck PIOP: Optimasi ini menangani keseimbangan antara biaya komputasi Prover dan Verifier, membuat operasi ZeroCheck lebih efisien dengan mendistribusikan beban kerja secara lebih efektif.
3. Optimisasi PIOP Sumcheck : Dengan mengoptimalkan proses Sumcheck pada bidang kecil, Binius mengurangi beban komputasi secara keseluruhan ketika beroperasi pada bidang kecil.
4. Optimasi PCS: Dengan menggunakan optimasi FRI-Binius (Fast Reed-Solomon Interactive Oracle Proofs of Proximity), Binius mengurangi ukuran bukti dan meningkatkan kinerja protokol, meningkatkan efisiensi keseluruhan dalam pembuatan dan verifikasi bukti.

3.1 GKR berbasis PIOP: Perkalian Bidang Biner Menggunakan GKR

Dalam protokol Binius asli, perkalian lapangan biner ditangani melalui skema berbasis lookup, yang mengikat perkalian ke operasi penambahan linear berdasarkan jumlah tungkai dalam sebuah kata. Meskipun metode ini mengoptimalkan perkalian biner sampai batas tertentu, namun masih memperkenalkan komitmen tambahan yang berhubungan secara linear dengan jumlah tungkai. Dengan mengadopsi pendekatan berbasis GKR, protokol Binius dapat secara signifikan mengurangi jumlah komitmen yang diperlukan, menghasilkan efisiensi lebih lanjut dalam operasi perkalian lapangan biner.

Ide inti dari protokol GKR (Goldwasser-Kalai-Rothblum) adalah untuk mencapai kesepakatan antara Prover (P) dan Verifier (V) atas rangkaian aritmatika berlapis pada lapangan terbatas

𝐹

Setiap node dalam rangkaian ini memiliki dua input untuk menghitung fungsi yang diperlukan. Untuk mengurangi kompleksitas komputasi Verifier, protokol ini menggunakan protokol SumCheck, yang secara progresif mengurangi klaim tentang nilai gerbang output rangkaian ke nilai gerbang lapisan bawah, akhirnya menyederhanakan klaim menjadi pernyataan tentang input. Dengan cara ini, Verifier hanya perlu memverifikasi kebenaran input rangkaian.

The Algoritma perkalian bilangan bulat berbasis GKR di Binius mengubah pemeriksaan apakah dua bilangan bulat 32-bit

𝐴

dan

𝐵

memuaskan

𝐴⋅𝐵=?𝐶

ke dalam memverifikasi apakah

(𝑔𝐴)𝐵=?𝑔𝐶

memegang di

F264∗

Transformasi ini, dikombinasikan dengan protokol GKR, secara signifikan mengurangi biaya yang terkait dengan komitmen polinomial. Dibandingkan dengan skema berbasis lookup Binius sebelumnya, pendekatan perkalian berbasis GKR hanya memerlukan satu komitmen tambahan dan mengurangi biaya SumChecks, membuat algoritma lebih efisien, terutama dalam kasus di mana SumChecks lebih ekonomis daripada komitmen tambahan. Metode ini menjadi solusi yang menjanjikan untuk meminimalkan biaya komitmen polinomial bidang biner seiring kemajuan optimasi Binius.

3.2 Optimisasi ZeroCheck PIOP: Menyeimbangkan Biaya Komputasi antara Pemberi dan Verifikasi

KertasBeberapa Perbaikan untuk PIOP untuk ZeroCheckmengusulkan strategi untuk menyeimbangkan biaya komputasi antara Prover (P) dan Verifier (V), dengan fokus pada pengurangan transmisi data dan kompleksitas komputasi. Berikut ini adalah teknik optimisasi kunci:

• Mengurangi Transmisi Data Prover

Dengan memindahkan sebagian beban komputasi ke Verifier, transmisi data Prover dapat diminimalkan. Misalnya, di putaran

i

, Prover mengirim

vi+1(X)

untuk

𝑋=0,…,𝑑+1

, dan Verifier memeriksa apakah

𝑣𝑖 = 𝑣𝑖+1(0) + 𝑣𝑖+1(1)

holds.

Pengoptimalan: Prover dapat menghindari pengiriman

𝑣𝑖+1(1)

, karena Verifier dapat menghitungnya sebagai

𝑣𝑖+1(1)=𝑣𝑖−𝑣𝑖+1(0)

.

Dalam putaran awal, Prover mengirimkan

𝑣1(0)=𝑣1(1)=0

menghilangkan beberapa perhitungan evaluasi, yang mengurangi biaya komputasi dan transmisi

𝑑2𝑛−1𝐶𝐹+(𝑑+1)2𝑛−1𝐶𝐺

.

• Mengurangi Jumlah Titik Evaluasi untuk Prover

Selama putaran

𝑖

, Prover harus mengirimkan

vi+1(X)

, dihitung sebagai

𝑣𝑖+1(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼,(𝑟,𝑋,𝑥))𝐶(𝑟,𝑋,𝑥)

.

Optimisasi: Sebagai gantinya, Prover dapat mengirimkan

𝑣𝑖+1′(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼𝑖+1,…,𝛼𝑛−1,𝑥)𝐶(𝑟,𝑋,𝑥),

dimana $v_i(X) = v_i'(X) \cdot \hat{\delta}{i+1}((\alpha_0, \dots, \alpha_i), (r, X))

.𝐴𝑠𝑡ℎ𝑒𝑉𝑒𝑟𝑖𝑓𝑖𝑒𝑟ℎ𝑎𝑠𝑎𝑐𝑐𝑒𝑠𝑠𝑡𝑜

\Alpha

dan

r

,𝑡ℎ𝑒𝑑𝑒𝑑𝑟𝑒𝑒𝑜𝑓

v_i’(X)

𝑖𝑠𝑙𝑜𝑤𝑒𝑟𝑡ℎ𝑎𝑛𝑑ℎ𝑎𝑡𝑜𝑓

v_i(X)

,𝑟𝑒𝑑𝑢𝑐𝑖𝑛𝑔𝑡ℎ𝑒𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑𝑒𝑣𝑎𝑙𝑢𝑎𝑡𝑖𝑜𝑛𝑝𝑜𝑖𝑛𝑡𝑠.𝑇ℎ𝑒𝑖𝑛𝑡𝑒𝑟−𝑟𝑜𝑢𝑛𝑑𝑐ℎ𝑒𝑐𝑘𝑐𝑎𝑛𝑡ℎ𝑒𝑛𝑏𝑒𝑠𝑖𝑚𝑝𝑙𝑖𝑓𝑖𝑒𝑑𝑎𝑠

(1 - \alphai)v{i+1}'(0) + \alpha_i v{i+1}’(1) = v_i’(X),

dengan demikianmenurunkan transmisi datakebutuhanandenhancingefficiency.Withtheseimprovements,theoverallcostisabout

2^{n-1}(d - 1)C_F + 2^{n-1}dC_G.

𝐹𝑜𝑟

d = 3$, optimasi-optimasi ini menghasilkan pengurangan biaya sebesar faktor 5/3.

• Optimisasi Interpolasi Aljabar

Untuk Prover yang jujur, polinomial

𝐶(𝑥0,…,𝑥𝑛−1)

adalah nol pada

𝐻𝑛

dan dapat diungkapkan sebagai

𝐶(𝑥0,…,𝑥𝑛−1)=∑𝑖=0𝑛−1𝑥𝑖(𝑥𝑖−1)𝑄𝑖(𝑥0,…,𝑥𝑛−1)

. Di mana

𝑄𝑖

diakses melalui pembagian polinomial yang diurutkan, dimulai dari

𝑅𝑛=𝐶

. Pembagian berurutan dengan

𝑥𝑖(𝑥𝑖−1)

Menghitung

𝑄𝑖

dan

𝑅𝑖

, dengan

R0

mewakili ekstensi multilinear dari

𝐶

pada

Hn

, diasumsikan nol.

Menganalisis Tingkat Ke

QI

. Untuk

j>i

,

𝑄𝑗

tetap mempertahankan tingkat yang sama di

Xi

sebagai

𝐶

. Untuk

j=i

, tingkatnya dikurangi 2, dan untuk

𝑗<𝑖

, derajatnya paling banyak 1. Diberikan sebuah vektor

𝑟=(𝑟0,…,𝑟𝑖)

,

Qj(r,X)

adalah multilinear untuk semua

j≤i

. Selain itu,

𝑄𝑖(𝑟,𝑋)=∑𝑗=0𝑖𝑟𝑗(𝑟𝑗−1)𝑄𝑗(𝑟,𝑋)

adalah polinomial multilinear unik yang cocok

𝐶(𝑟,𝑋)

di atas

𝐻𝑛−𝑖

. Untuk apa pun

𝑋

dan

𝑥∈𝐻𝑛−𝑖−1

, itu dapat diwakili sebagai

𝐶(𝑟,𝑋,𝑥)−𝑄𝑖(𝑟,𝑋,𝑥)=𝑋(𝑋−1)𝑄𝑖+1(𝑟,𝑋,𝑥).

Oleh karena itu, selama setiap putaran protokol, ada yang baru

𝑄

diperkenalkan, dan evaluasinya dapat diperoleh dari

𝐶

dan sebelumnya

𝑄

, memungkinkan untuk optimisasi interpolasi.

3.3 Optimisasi PIOP Sumcheck: Protokol Sumcheck Lapangan Kecil

Dalam protokol STARKs yang diimplementasikan oleh Binius, bottleneck utama bagi pemberi bukti seringkali adalah protokol pemeriksaan jumlah daripada Skema Komitmen Polinomial (PCS), karena biaya komitmen yang rendah.

Gambar 2. Hubungan antara putaran Switchover dan peningkatan Faktor

Pada tahun 2024, Ingonyama mengusulkan peningkatan untuk protokol Sumcheck berbasis small-field, berfokus pada Algoritma 3 dan 4. Peningkatan-peningkatan ini telah diimplementasikan dan tersedia untuk umum di sini. Algoritma 4 menggabungkan algoritma Karatsuba ke dalam Algoritma 3, mengurangi jumlah perkalian lapangan perluasan sebagai gantinya dengan lebih banyak perkalian lapangan dasar. Pendekatan ini lebih efisien ketika perkalian lapangan perluasan lebih mahal daripada lapangan dasar.

1. Dampak Putaran Alih dan Faktor Peningkatan Optimasi protokol Sumcheck bidang kecil tergantung pada pemilihan putaran peralihan optimal

𝑡

, yang menandai kapan protokol kembali dari versi yang dioptimalkan ke algoritma naif. Eksperimen menunjukkan bahwa faktor perbaikan mencapai puncaknya pada titik peralihan optimal dan kemudian mengikuti tren parabola. Ketika titik ini terlampaui, efisiensi menurun karena rasio antara perkalian bidang dasar dan bidang perluasan lebih besar pada bidang yang lebih kecil, sehingga memerlukan pengembalian ke algoritma naif tepat waktu.

Untuk aplikasi tertentu, seperti Cubic Sumcheck (

𝑑=3

), protokol Sumcheck bidang kecil memberikan peningkatan sepuluh kali lipat dibandingkan pendekatan naif. Misalnya, dalam bidang dasar

𝐺𝐹[2]2. Dampak Ukuran Lapangan Dasar pada Kinerja Lapangan dasar yang lebih kecil (misalnya,

, Algoritma 4 berhasil mengungguli algoritma naif hingga hampir 30 kali lipat.

𝐺𝐹[2]

) secara signifikan meningkatkan efisiensi algoritma yang dioptimalkan karena adanya disparitas yang lebih besar antara biaya perkalian bidang perluasan dan bidang dasar. Hal ini menghasilkan faktor perbaikan yang lebih substansial untuk algoritma yang dioptimalkan.

1. Keuntungan Optimisasi dari Algoritma Karatsuba Algoritma Karatsuba memainkan peran penting dalam meningkatkan kinerja protokol Sumcheck di lapangan kecil. Untuk lapangan dasar dari

𝐺𝐹[2]

, Algoritma 4 mencapai faktor peningkatan puncak sebesar 6 untuk Algoritma 3 dan 30 untuk Algoritma 4, menunjukkan bahwa Algoritma 4 lebih efisien lima kali lipat dibandingkan Algoritma 3. Algoritma Karatsuba meningkatkan efisiensi waktu proses dan mengoptimalkan titik pergantian untuk kedua algoritma, dengan titik optimal di

t=5

untuk Algoritma 3 dan

𝑡=8

untuk Algoritma 4.

1. Peningkatan Efisiensi Memori Protokol Sumcheck small-field juga meningkatkan efisiensi memori. Algoritma 4 memerlukan

𝑂(𝑑⋅𝑡)

memori, sementara Algoritma 3 membutuhkan

O(2d⋅t)

memori. Untuk

𝑡=8

, Algoritma 4 hanya menggunakan 0,26 MB memori, dibandingkan dengan 67 MB yang dibutuhkan oleh Algoritma 3. Hal ini membuat Algoritma 4 sangat cocok untuk lingkungan yang dibatasi memori, seperti pembuktian sisi klien dengan sumber daya terbatas.

3,4 Optimisasi PCS: FRI-Binius Mengurangi Ukuran Bukti Binius

Salah satu tantangan utama dari protokol Binius adalah ukuran bukti yang relatif besar, yang meningkat seiring dengan akar kuadrat dari ukuran saksi pada

𝑂(𝑁)

. Skala akar kuadrat ini membatasi daya saingnya jika dibandingkan dengan sistem yang menawarkan bukti yang lebih ringkas. Sebaliknya, ukuran bukti polilogaritmik, seperti yang dicapai oleh sistem canggih seperti Plonky3 melalui teknik seperti FRI, penting untuk memastikan verifikasi yang benar-benar “ringkas”. Optimisasi FRI-Binius bertujuan untuk mengurangi ukuran bukti Binius dan meningkatkan kinerjanya secara keseluruhan dibandingkan dengan sistem yang lebih efisien.

Kertas Bukti Polilogaritmik untuk Multilinear di atas Menara Biner, yang disebut FRI-Binius, memperkenalkan mekanisme lipatan FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) berbasis bidang biner yang baru dengan empat inovasi kunci:

• Polinomial Datar: Mengubah polinomial multilinear awal menjadi dasar polinomial Kode Rendah (LCH) untuk komputasi yang dioptimalkan.
• Polinomial Menguap Subspace: Memanfaatkan polinomial ini bersama dengan NTT (Transformasi Teori Bilangan) aditif untuk memungkinkan dekomposisi FFT-like, mengoptimalkan operasi di atas lapangan koefisien.
• Pengemasan Dasar Aljabar: Memfasilitasi pengemasan data yang efisien, meminimalkan overhead protokol terkait dengan penyisipan.
• Ring-Switching SumCheck: Sebuah optimasi SumCheck baru yang menggunakan teknik ring-switching untuk meningkatkan performa lebih lanjut.

Proses inti dari Skema Komitmen Polinomial Multilinear FRI-Binius (PCS)

Protokol FRI-Binius mengoptimalkan skema komitmen polinomial multilinear (PCS) bidang biner dengan mentransformasi polinomial multilinear awal, yang didefinisikan di atas bidang biner.

𝐹2

, menjadi polinomial multilinear atas lapangan yang lebih besar

𝐾

.

1. Fase Komitmen Fase komitmen mengubah sebuah
2. ℓ
3. -polinomial multilinear variabel (di atas $\mathbb{F}2
4. )𝑖𝑛𝑡𝑜𝑎𝑐𝑜𝑚𝑚𝑖𝑡𝑚𝑒𝑛𝑡𝑓𝑜𝑟𝑎𝑝𝑎𝑐𝑘𝑒𝑑
5. \ell'
6. −𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑚𝑢𝑙𝑡𝑖𝑙𝑖𝑛𝑒𝑎𝑟𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙(𝑜𝑣𝑒𝑟
7. \mathbb{F}{2^{128}}$ ). Proses ini mengurangi jumlah koefisien sebanyak 128, sehingga memungkinkan pembuatan bukti yang lebih efisien.
8. Fase Evaluasi Dalam fase ini, prover dan verifier melakukan eksekusi
9. ℓ′
10. putaran protokol SumCheck switching cross-ring dikombinasikan dengan FRI interactive oracle proofs of proximity (IOPP). Detail utama meliputi:
    • Bukti Pembukaan FRI: Ini merupakan sebagian besar dari ukuran bukti dan ditangani dengan cara yang sama seperti bukti FRI standar di atas lapangan besar.
    • Biaya Prover's SumCheck: Sebanding dengan biaya menjalankan SumCheck dalam bidang yang besar.
    • Biaya FRI Prover: Sesuai dengan biaya FRI standar yang terlihat dalam implementasi lapangan besar.
    • Operasi Pemeriksa: Pemeriksa menerima 128 elemen dari
    • 𝐹2128
    • dan melakukan 128 perkalian tambahan, memungkinkan verifikasi yang efisien.

Manfaat dari FRI-Binius

Dengan menerapkan metode ini, Binius dapat mengurangi ukuran buktinya dengan satu orde besar, mendekatkannya dengan kinerja sistem kriptografi terkini, sambil tetap kompatibel dengan lapangan biner. Metode lipatan FRI, yang dioptimalkan untuk lapangan biner, dikombinasikan dengan pengemasan aljabar dan optimasi SumCheck, membantu Binius menghasilkan bukti yang lebih kecil tanpa mengorbankan efisiensi verifikasi.

Transformasi ini menandai langkah signifikan menuju peningkatan ukuran bukti di Binius, memastikan bahwa sistem ini menjadi lebih kompetitif dengan sistem-sistem terbaru lainnya, terutama yang fokus pada ukuran bukti polilogaritmik.

Tabel 2: Perbandingan Ukuran Bukti Binius vs. FRI-Binius

Tabel 3: Perbandingan Plonky3 FRI vs FRI-Binius

4. Kesimpulan

Seluruh proposisi nilai Binius terletak pada kemampuannya untuk menggunakan kekuatan terkecil dari dua ukuran bidang untuk saksi, memilih ukuran bidang sesuai kebutuhan. Binius adalah skema desain bersama untuk "perangkat keras, perangkat lunak, dan protokol Sumcheck yang dipercepat FPGA," memungkinkan bukti cepat dengan penggunaan memori yang sangat rendah.

Sistem bukti seperti Halo2 dan Plonky3 melibatkan empat langkah yang membutuhkan komputasi intensif: menghasilkan data saksi, berkomitmen pada data saksi, melakukan argumen yang menghilang, dan menghasilkan bukti pembuka.

Sebagai contoh, dengan fungsi hash Keccak dalam Plonky3 dan fungsi hash Grøstl dalam Binius, distribusi komputasi untuk empat langkah kunci ini diilustrasikan dalam Gambar 3.

Gambar 3. Biaya Komit Kecil

Perbandingan ini menunjukkan bahwa Binius pada dasarnya telah menghilangkan bottleneck komitmen pembuktian. Bottleneck baru adalah protokol Sumcheck, di mana masalah seperti evaluasi polinomial yang banyak dan perkalian lapangan dapat ditangani dengan efisien menggunakan perangkat keras khusus.

Skema FRI-Binius, sebuah varian dari FRI, menawarkan opsi yang sangat menarik dengan menghilangkan biaya overhead penyisipan dari lapisan bukti lapangan tanpa menyebabkan peningkatan biaya yang signifikan di lapisan bukti yang terakumulasi.

Saat ini, tim Irreducible sedang mengembangkan lapisan rekursifnya dan memiliki mengumumkan kemitraan dengan tim Polygon untuk membangun zkVM berbasis Binius; yang Jolt zkVM sedang beralih dari Lasso ke Binius untuk meningkatkan kinerja rekursifnya; dan gateTim Ingonyama sedang mengimplementasikan versi FPGA dari Binius.

Referensi

1. 2024.04 Argumen Singkat Binius tentang Menara Lapangan Biner
2. 2024.07 Jumat-Binius Bukti Polilogaritmik untuk Multilinear di atas Menara Binari
3. Pembagian Integer 2024.08 dalam Binius: Pendekatan berbasis GKR
4. 2024.06 zkStudyClub - FRI-Binius: Bukti Polilogaritmik untuk Multilinear di atas Menara Binari
5. 2024.04 ZK11: Binius: SNARK yang dioptimalkan perangkat keras - Jim Posen
6. 2023.12 Episode 303: A Dive into Binius with Ulvetanna
7. 2024.09 Merancang zkVMs yang berkualitas tinggi
8. 2024.07 Sumcheck dan Open-Binius
9. 2024.04 Binius: bukti yang sangat efisien di atas bidang biner
10. 2023.12 SNARKs pada bidang biner: Binius - Bagian 1
11. 2024.06 SNARKs pada bidang biner: Binius - Bagian 2
12. @espressosys/hyperplonk-a-zk-proof-system-for-zkevms-d45fd077bfba">2022.10 HyperPlonk, sebuah sistem bukti-zk untuk ZKEVM

Penafian:

1. Artikel ini dicetak ulang dari [bitlayer]. Semua hak cipta milik penulis asli [lynndell]. Jika ada keberatan terhadap cetakan ini, silakan hubungi Gate Pelajaritim, dan mereka akan menanganinya dengan segera.
2. Penyangkalan Tanggung Jawab: Pandangan dan opini yang terdapat dalam artikel ini sepenuhnya milik penulis dan tidak merupakan nasihat investasi apa pun.
3. Terjemahan artikel ke dalam bahasa lain dilakukan oleh tim Pembelajaran gate. Kecuali disebutkan, menyalin, mendistribusikan, atau menjiplak artikel yang diterjemahkan dilarang.