Judul asli yang diteruskan 'Vitalik menjelaskan Binius secara rinci: sistem bukti yang efisien berdasarkan bidang biner'

Pos ini sebagian besar ditujukan untuk pembaca yang cukup familiar dengan kriptografi era 2019, terutama SNARKs dan STARKs. Jika Anda tidak, saya sarankan membaca artikel-artikel tersebut terlebih dahulu. Terima kasih khusus kepada Justin Drake, Jim Posen, Benjamin Diamond, dan Radi Cojbasic atas umpan balik dan tinjauan mereka.

Dalam dua tahun terakhir, STARK telah menjadi teknologi penting dan tak tergantikan untuk membuat bukti kriptografis yang mudah diverifikasi dari pernyataan yang sangat rumit (misalnya membuktikan bahwa blok Ethereum valid). Salah satu alasan utamanya adalah ukuran bidang yang kecil: sementara SNARK berbasis kurva eliptis memerlukan Anda untuk bekerja dengan bilangan bulat 256-bit agar cukup aman, STARK memungkinkan Anda menggunakan ukuran bidang yang jauh lebih kecil, yang lebih efisien: pertama bidang Goldilocks (bilangan bulat 64-bit), dan kemudian Mersenne31 dan BabyBear (keduanya 31-bit). Berkat peningkatan efisiensi ini, Plonky2, yang menggunakan Goldilocks, ratusan kali lebih cepat dalam membuktikan banyak jenis komputasi daripada pendahulunya.

Sebuah pertanyaan alami yang patut ditanyakan adalah: apakah kita dapat membawa tren ini ke kesimpulan logisnya, membangun sistem bukti yang berjalan bahkan lebih cepat dengan beroperasi langsung melalui nol dan satu? Ini persis apa yang Binius coba lakukan, menggunakan sejumlah trik matematika yang membuatnya sangat berbeda dari SNARKs dan STARKs tiga tahun yang lalu. Pos ini menjelaskan alasan mengapa lapangan kecil membuat generasi bukti lebih efisien, mengapa lapangan biner sangat kuat, dan trik-trik yang Binius gunakan untuk membuat bukti-bukti di atas lapangan biner bekerja begitu efektif.

Binius. Pada akhir pos ini, Anda harus dapat memahami setiap bagian dari diagram ini.

Ringkasan: lapangan terbatas

Salah satu tugas kunci dari sistem pembuktian kriptografis adalah beroperasi atas jumlah data yang besar, sambil menjaga agar angka-angkanya tetap kecil. Jika Anda dapat mengompres sebuah pernyataan tentang program besar menjadi persamaan matematika yang melibatkan beberapa angka, tetapi angka-angka tersebut sebesar program asli, Anda tidak mendapatkan apa-apa.

Untuk melakukan aritmatika yang rumit sambil menjaga angka tetap kecil, kriptografer umumnya menggunakan aritmatika modular. Kita memilih beberapa “modulus” prima p. Operator % berarti “mengambil sisa dari”: 15 % 7=1, 53 % 10=3, dll (perhatikan bahwa jawabannya selalu non-negatif, jadi misalnya −1 % 10=9).

Anda mungkin sudah melihat aritmetika modular, dalam konteks menambah dan mengurangi waktu (mis. jam berapa empat jam setelah pukul 9:00?). Tetapi di sini, kita tidak hanya menambah dan mengurangi modulo beberapa angka, kita juga mengalikan, membagi, dan mengambil eksponen.

Kami mendefinisikan ulang:

Aturan di atas semuanya saling konsisten. Misalnya, jika p=7, maka:

5+3=1 (karena 8%7=1)

1-3=5 (karena -2%7=5)

2*5=3

3/5=2

Sebuah istilah umum untuk jenis struktur ini adalah medan hingga. Medan hingga adalah struktur matematika yang mematuhi hukum-hukum aritmatika biasa, tetapi di mana ada jumlah nilai yang terbatas, sehingga setiap nilai dapat direpresentasikan dalam ukuran tetap.

Aritmetika modular (atau lapangan prima) adalah jenis lapangan hingga yang paling umum, tetapi ada juga jenis lain: lapangan ekstensi. Anda mungkin sudah pernah melihat lapangan ekstensi sebelumnya: bilangan kompleks. Kita "membayangkan" elemen baru, yang kita labeli 𝑖, dan menyatakan bahwa itu memenuhi 𝑖2=−1. Anda kemudian dapat mengambil kombinasi dari angka biasa dan 𝑖, dan melakukan perhitungan matematika dengannya: (3𝑖+2)∗(2𝑖+4)= 6𝑖2+12𝑖+4𝑖+8=16𝑖+2. Kita juga dapat mengambil ekstensi lapangan prima. Ketika kita mulai bekerja di atas lapangan yang lebih kecil, ekstensi lapangan prima menjadi semakin penting untuk menjaga keamanan, dan lapangan biner (yang digunakan oleh Binius) bergantung pada ekstensi sepenuhnya untuk memiliki utilitas praktis.

Ringkasan: aritmetisasi

Cara SNARKs dan STARKs membuktikan hal-hal tentang program komputer adalah melalui aritmetisasi: Anda mengonversi pernyataan tentang program yang ingin Anda buktikan, menjadi persamaan matematika yang melibatkan polinomial. Solusi valid untuk persamaan tersebut sesuai dengan eksekusi program yang valid.

Sebagai contoh sederhana, misalkan saya menghitung angka Fibonacci ke-100, dan saya ingin membuktikan kepada Anda apa itu. Saya membuat polinomial 𝐹 yang mengodekan angka Fibonacci: jadi 𝐹(0)=𝐹(1)=1, 𝐹(2)=2, 𝐹(3)=3, 𝐹(4)=5, dan seterusnya selama 100 langkah. Kondisi yang perlu saya buktikan adalah bahwa 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) di rentang 𝑥={0,1…98}. Saya bisa meyakinkan Anda tentang hal ini dengan memberi Anda hasil bagi:

di mana Z(x) = (x-0) (x-1) …(x-98). . Jika saya dapat membuktikan bahwa ada F dan H yang memenuhi persamaan ini, maka F harus memenuhi F(x+2)-F(x+1)-F(x) di rentang tersebut. Jika saya juga memeriksa bahwa F dipenuhi, F(0)=F(1)=1, maka F(100) sebenarnya harus menjadi bilangan Fibonacci ke-100.

Jika Anda ingin membuktikan sesuatu yang lebih rumit, maka Anda menggantikan relasi “sederhana” 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) dengan persamaan yang lebih rumit, yang pada dasarnya mengatakan “𝐹(𝑥+1) adalah output dari menginisialisasi mesin virtual dengan keadaan 𝐹(𝑥), dan menjalankan satu langkah komputasi”. Anda juga dapat menggantikan angka 100 dengan angka yang lebih besar, misalnya 100000000, untuk menampung lebih banyak langkah.

Semua SNARK dan STARK didasarkan pada gagasan ini untuk menggunakan persamaan sederhana di atas polinomial (atau kadang-kadang vektor dan matriks) untuk mewakili sejumlah besar hubungan antara nilai-nilai individual. Tidak semuanya melibatkan pemeriksaan kesetaraan antara langkah komputasi yang berdekatan dalam cara yang sama seperti di atas: PLONK tidak, misalnya, begitu juga R1CS. Tetapi banyak dari yang paling efisien melakukannya, karena menegakkan pemeriksaan yang sama (atau beberapa pemeriksaan yang sama) banyak kali membuat lebih mudah untuk meminimalkan overhead.

Plonky2: dari SNARKs 256-bit dan STARKs hingga 64-bit... hanya STARKs

Lima tahun yang lalu, ringkasan yang masuk akal dari berbagai jenis bukti pengetahuan nol adalah sebagai berikut. Ada dua jenis bukti: (berbasis kurva eliptik) SNARK dan (berbasis hash) STARK. Secara teknis, STARK adalah jenis SNARK, tetapi dalam prakteknya umum untuk menggunakan "SNARK" untuk merujuk hanya pada variasi berbasis kurva eliptik, dan "STARK" untuk merujuk pada konstruksi berbasis hash. SNARK kecil, sehingga Anda dapat memverifikasinya dengan cepat dan memasukkannya ke dalam rantai dengan mudah. STARK besar, tetapi tidak memerlukan setup yang terpercaya, dan tahan terhadap kuantum.

STARK bekerja dengan memperlakukan data sebagai polinomial, menghitung evaluasi polinomial itu di sejumlah besar titik, dan menggunakan akar Merkle dari data yang diperluas itu sebagai "komitmen polinomial"

Sedikit sejarah utama di sini adalah bahwa SNARK berbasis kurva eliptik mulai digunakan secara luas terlebih dahulu: butuh waktu hingga sekitar 2018 bagi SARK untuk menjadi cukup efisien untuk digunakan, berkat FRI, dan pada saat itu Zcash telah berjalan selama lebih dari setahun. SNARKs berbasis kurva elips memiliki batasan utama: jika Anda ingin menggunakan SNARKs berbasis kurva elips, maka aritmatika dalam persamaan ini harus dilakukan dengan bilangan bulat modulo jumlah titik pada kurva elips. Ini adalah angka yang besar, biasanya mendekati 2256: misalnya, untuk kurva bn128, itu 21888242871839275222246405745257275088548364400416034343698204186575808495617. Tetapi perhitungan sebenarnya menggunakan angka-angka kecil: jika Anda berpikir tentang program "nyata" dalam bahasa favorit Anda, sebagian besar hal yang bekerja dengannya adalah penghitung, indeks untuk loop, posisi dalam program, bit individual yang mewakili Benar atau Salah, dan hal-hal lain yang hampir selalu hanya beberapa digit.

Bahkan jika data 'asli' Anda terdiri dari angka-angka 'kecil', proses pembuktian memerlukan perhitungan bagi hasil, perpanjangan, kombinasi linear acak, dan transformasi lain dari data, yang menghasilkan jumlah objek yang sama atau lebih besar, yang rata-rata sebesar ukuran penuh bidang Anda. Ini menciptakan ketidakefisienan kunci: untuk membuktikan komputasi atas n nilai kecil, Anda harus melakukan lebih banyak komputasi atas n nilai yang jauh lebih besar. Pada awalnya, STARKs mewarisi kebiasaan menggunakan bidang 256-bit dari SNARKs, dan dengan demikian mengalami ketidakmampuan yang sama.

Sebuah perluasan Reed-Solomon dari beberapa evaluasi polinomial. Meskipun nilai-nilai asli kecil, nilai tambahan semuanya meledak menjadi ukuran penuh bidang (dalam kasus ini 2 pangkat 31 -1)

Pada tahun 2022, Plonky2 dirilis. Inovasi utama Plonky2 adalah melakukan aritmatika modulo dengan bilangan prima yang lebih kecil: 2⁶⁴−2³²+1=18446744069414584321. Sekarang, setiap penambahan atau perkalian selalu dapat dilakukan hanya dalam beberapa instruksi pada CPU, dan menggabungkan semua data bersama-sama 4x lebih cepat dari sebelumnya. Tetapi ini datang dengan syarat: pendekatan ini hanya untuk STARK. Jika Anda mencoba menggunakan SNARK, dengan kurva eliptis berukuran kecil seperti itu, kurva eliptis menjadi tidak aman.

Untuk tetap aman, Plonky2 juga perlu memperkenalkan bidang perpanjangan. Teknik kunci dalam memeriksa persamaan aritmatika adalah “pengambilan sampel pada titik acak”: jika Anda ingin memeriksa apakah 𝐻(𝑥)∗𝑍(𝑥) benar-benar sama dengan 𝐹(𝑥+2)−𝐹(𝑥+1)−𝐹(𝑥), Anda dapat memilih beberapa koordinat acak 𝑟, memberikan bukti pembukaan komitmen polinomial membuktikan 𝐻(𝑟), 𝑍(𝑟), 𝐹(𝑟), 𝐹(𝑟+1) dan 𝐹(𝑟+2), dan kemudian memeriksa apakah 𝐻(𝑟)∗𝑍(𝑟) sama dengan 𝐹(𝑟+2)−𝐹(𝑟+1)−𝐹(𝑟). Jika penyerang dapat menebak koordinat sebelumnya, penyerang dapat menipu sistem bukti - itulah mengapa itu harus acak. Tetapi ini juga berarti bahwa koordinat harus diambil sampel dari himpunan yang cukup besar sehingga penyerang tidak dapat menebaknya secara acak. Jika modulus dekat dengan 2²⁵⁶, ini jelas merupakan kasusnya. Tetapi dengan modulus 2⁶⁴−2³²+1, kita belum sepenuhnya mencapainya, dan jika kita turun ke 2³¹−1, itu pasti bukan kasusnya. Mencoba untuk memalsukan bukti dua miliar kali sampai ada yang beruntung sepenuhnya dalam jangkauan kemampuan seorang penyerang.

Untuk menghentikan ini, kami mengambil sampel 𝑟 dari bidang perpanjangan. Sebagai contoh, Anda dapat mendefinisikan 𝑦 di mana 𝑦³=5, dan mengambil kombinasi dari 1, 𝑦 dan 𝑦². Hal ini meningkatkan jumlah total koordinat kembali hingga sekitar 2⁹³Sebagian besar polinomial yang dihitung oleh pemeriksa tidak masuk ke dalam bidang perluasan ini; mereka hanya menggunakan bilangan bulat modulo 2³¹−1, dan oleh karena itu Anda masih mendapatkan semua efisiensi dari menggunakan bidang kecil. Tetapi pemeriksaan titik acak, dan perhitungan FRI, memang menyelami bidang yang lebih besar ini, untuk mendapatkan keamanan yang diperlukan.

Dari bilangan prima ke biner

Komputer melakukan aritmatika dengan mewakili angka-angka yang lebih besar sebagai urutan nol dan satu, dan membangun 'rangkaian' di atas bit-bit itu untuk menghitung hal-hal seperti penambahan dan perkalian. Komputer dioptimalkan khusus untuk melakukan komputasi dengan bilangan bulat 16-bit, 32-bit, dan 64-bit. Modulus seperti 2⁶⁴−2³²+1 dan 2³¹−1 dipilih bukan hanya karena mereka cocok dalam batasan tersebut, tetapi juga karena mereka sejalan dengan batasan tersebut: Anda dapat melakukan perkalian modulo 2⁶⁴−2³²+1 dengan melakukan perkalian 32-bit reguler, dan menggeser dan menyalin output secara bitwise di beberapa tempat; artikel ini menjelaskan beberapa trik dengan baik.

Apa yang akan lebih baik, bagaimanapun, adalah melakukan perhitungan dalam biner secara langsung. Bagaimana jika penambahan bisa "hanya" XOR, tanpa perlu khawatir tentang "membawa" overflow dari menambahkan 1 + 1 dalam satu posisi bit ke posisi bit berikutnya? Bagaimana jika perkalian bisa lebih paralel dengan cara yang sama? Dan semua keuntungan ini akan datang di atas kemampuan untuk mewakili nilai Benar / Salah hanya dengan satu bit.

Mengambil keuntungan dari melakukan komputasi biner secara langsung adalah hal yang tepat yang ingin dilakukan Binius. Tabel dari presentasi zkSummit tim Binius menunjukkan peningkatan efisiensi:

Meskipun kira-kira "ukuran" yang sama, operasi medan biner 32-bit membutuhkan sumber daya komputasi 5x lebih sedikit daripada operasi di atas bidang Mersenne 31-bit.

Dari polinomial univariat hingga hiperkubus

Misalkan bahwa kita yakin dengan penalaran ini, dan ingin melakukan segalanya melalui bit (nol dan satu). Bagaimana sebenarnya kita mengkomitmenkan diri pada polinom yang mewakili satu miliar bit?

Di sini, kita menghadapi dua masalah praktis:

1. Untuk polinomial mewakili banyak nilai, nilai-nilai tersebut perlu dapat diakses saat evaluasi polinomial: pada contoh Fibonacci di atas, 𝐹(0), 𝐹(1) ... 𝐹(100), dan dalam komputasi yang lebih besar, indeksnya akan mencapai jutaan. Dan bidang yang kita gunakan perlu berisi angka-angka hingga ukuran tersebut.

2. Membuktikan sesuatu tentang nilai yang kami komitmenkan dalam pohon Merkle (seperti halnya semua STARKs lakukan) memerlukan enkode Reed-Solomon: memperluas 𝑛 nilai ke misalnya 8𝑛 nilai, menggunakan redundansi untuk mencegah pemalsuan nilai dalam komputasi. Ini juga memerlukan bidang yang cukup besar: untuk memperluas jutaan nilai menjadi 8 juta, Anda memerlukan 8 juta titik berbeda di mana untuk mengevaluasi polinomial.

Ide kunci dalam Binius adalah menyelesaikan dua masalah ini secara terpisah, dan melakukannya dengan cara mewakili data yang sama dengan dua cara yang berbeda. Pertama, polinomial itu sendiri. SNARK berbasis kurva elips, STARK era 2019, Plonky2, dan sistem lainnya umumnya berurusan dengan polinomial atas satu variabel: 𝐹(𝑥). Binius, di sisi lain, mengambil inspirasi dari protokol Spartan, dan bekerja dengan polinomial multivariat: 𝐹(𝑥1,𝑥2…𝑥𝑘). Sebenarnya, kami mewakili jejak komputasi seluruhnya pada “hiperkubus” evaluasi di mana setiap 𝑥𝑖 adalah 0 atau 1. Sebagai contoh, jika kami ingin mewakili urutan angka Fibonacci, dan kami masih menggunakan bidang yang cukup besar untuk mewakili mereka, kita mungkin memvisualisasikan enam belas angka pertamanya sebagai sesuatu seperti ini:

Yaitu, 𝐹(0,0,0,0) akan menjadi 1, 𝐹(1,0,0,0) juga akan menjadi 1, 𝐹(0,1,0,0) akan menjadi 2, dan seterusnya, hingga kita mencapai 𝐹(1,1,1,1)=987. Diberikan sebuah hiperkubus dari evaluasi, ada tepat satu polinomial multilinear (derajat-1 dalam setiap variabel) yang menghasilkan evaluasi tersebut. Jadi kita dapat menganggap bahwa kumpulan evaluasi tersebut mewakili polinomial; kita sebenarnya tidak perlu repot menghitung koefisien.

Contoh ini tentu saja hanya untuk ilustrasi: dalam praktiknya, inti dari pergi ke hiperkubus adalah untuk memungkinkan kita bekerja dengan bit-bit individual. Cara 'Binius-native' untuk menghitung angka Fibonacci adalah dengan menggunakan kubus berdimensi lebih tinggi, menggunakan setiap set misalnya 16 bit untuk menyimpan sebuah angka. Hal ini memerlukan sedikit kecerdikan untuk menerapkan penambahan bilangan bulat di atas bit-bit tersebut, tetapi dengan Binius hal ini tidak terlalu sulit.

Sekarang, kita sampai pada pengkodean penghapusan. Cara kerja STARK adalah: Anda mengambil nilai n, Reed-Solomon memperluasnya ke sejumlah besar nilai (seringkali 8n, biasanya antara 2n dan 32n), dan kemudian secara acak memilih beberapa cabang Merkle dari ekstensi dan melakukan semacam pemeriksaan pada mereka. Hypercube memiliki panjang 2 di setiap dimensi. Oleh karena itu, tidak praktis untuk memperluasnya secara langsung: tidak ada cukup "ruang" untuk mengambil sampel cabang Merkle dari 16 nilai. Jadi apa yang kita lakukan sebagai gantinya? Kami berpura-pura hypercube adalah persegi!

Simple Binius - contoh

Lihat di siniuntuk implementasi python dari protokol ini.

Mari kita melalui contoh, menggunakan bilangan bulat biasa sebagai bidang kita untuk kenyamanan (dalam implementasi nyata ini akan menjadi elemen bidang biner). Pertama, kita mengambil hiperkubus yang ingin kita komitmenkan, dan mengenkripsikannya sebagai sebuah persegi:

Sekarang, kami memperluas persegi Reed-Solomon. Artinya, kami memperlakukan setiap baris sebagai polinomial derajat-3 dievaluasi pada x = {0, 1, 2, 3}, dan mengevaluasi polinomial yang sama pada x = {4, 5, 6, 7}:

Perhatikan bahwa angka-angka meledak dengan cepat! Inilah mengapa dalam implementasi nyata, kita selalu menggunakan medan terbatas untuk ini, bukan bilangan bulat biasa: jika kita menggunakan bilangan bulat modulo 11, misalnya, perluasan baris pertama hanya akan menjadi [3, 10, 0, 6].

Jika Anda ingin bermain dengan memperluas dan memverifikasi angka-angka di sini sendiri, Anda dapat menggunakankode ekstensi Reed-Solomon sederhana saya di sini.

Selanjutnya, kami memperlakukan ekstensi ini sebagai kolom, dan membuat pohon Merkle dari kolom-kolom tersebut. Akar pohon Merkle adalah komitmen kami.

Sekarang, mari kita asumsikan bahwa pemberi bukti ingin membuktikan evaluasi polinomial ini pada titik tertentu 𝑟={𝑟0,𝑟1,𝑟2,𝑟3}. Ada satu hal kecil dalam Binius yang membuatnya agak lebih lemah daripada skema komitmen polinomial lainnya: pemberi bukti seharusnya tidak mengetahui, atau dapat menebak, 𝑠, sampai setelah mereka berkomitmen pada akar Merkle (dengan kata lain, 𝑟 seharusnya menjadi nilai pseudo-acak yang bergantung pada akar Merkle). Hal ini membuat skema ini tidak berguna untuk “pencarian basis data” (misalnya “oke, Anda memberi saya akar Merkle, sekarang buktikan kepada saya 𝑃(0,0,1,0)!”). Namun, protokol bukti nol pengetahuan aktual yang kami gunakan umumnya tidak memerlukan “pencarian basis data”; mereka hanya perlu memeriksa polinomial pada titik evaluasi acak. Oleh karena itu, pembatasan ini cukup untuk keperluan kami.

Misalkan kita memilih 𝑟={1,2,3,4} (pada titik ini, polinomial mengevaluasi menjadi −137; Anda dapat mengonfirmasinyadengan kode ini). Sekarang, kita masuk ke proses benar-benar membuat bukti. Kita membagi r menjadi dua bagian: bagian pertama {1,2} mewakili kombinasi linear kolom dalam satu baris, dan bagian kedua {3,4} mewakili kombinasi linear baris. Kami menghitung "produk tensor", keduanya untuk bagian kolom:

Dan untuk bagian baris:

Apa artinya adalah: daftar semua kemungkinan produk dari satu nilai dari setiap set. Dalam kasus baris, kita mendapatkan:

[(1-r2)(1-r3), (1-r3), (1-r2)r3, r2*r3]

Gunakan r={1,2,3,4} (jadi r2=3 dan r3=4):

[(1-3)(1-4), 3(1-4),(1-3)4,34] = [6, -9 -8 -12]

Sekarang, kita menghitung “baris” baru 𝑡′, dengan mengambil kombinasi linear dari baris yang ada ini. Artinya, kita mengambil:

Anda dapat melihat apa yang terjadi di sini sebagai evaluasi parsial. Jika kita akan mengalikan produk tensor lengkap ⨂𝑖=03(1−𝑟𝑖,𝑟𝑖) dengan vektor lengkap dari semua nilai, Anda akan mendapatkan evaluasi 𝑃(1,2,3,4)=−137. Di sini kita mengalikan produk tensor parsial yang hanya menggunakan setengah koordinat evaluasi, dan kita mengurangi kisi 𝑁 nilai menjadi baris 𝑁 nilai. Jika Anda memberikan baris ini kepada orang lain, mereka dapat menggunakan produk tensor setengah lainnya dari koordinat evaluasi untuk menyelesaikan sisa perhitungan.

Prover memberikan baris baru ini kepada verifier, 𝑡′, serta bukti Merkle dari beberapa kolom yang dipilih secara acak. Ini adalah data 𝑂(𝑁). Dalam contoh ilustratif kami, kita akan meminta prover untuk hanya memberikan kolom terakhir; dalam kehidupan nyata, prover perlu memberikan beberapa puluh kolom untuk mencapai keamanan yang memadai.

Sekarang, kita memanfaatkan keberurutan kode Reed-Solomon. Sifat kunci yang kita gunakan adalah: mengambil kombinasi linear dari ekstensi Reed-Solomon memberikan hasil yang sama dengan ekstensi Reed-Solomon dari kombinasi linear. Jenis 'kemandirian urutan' seperti ini sering terjadi ketika Anda memiliki dua operasi yang keduanya linear.

Verifikator melakukan hal ini dengan tepat. Mereka menghitung perpanjangan dari 𝑡′, dan mereka menghitung kombinasi linear yang sama dari kolom-kolom yang telah dihitung oleh pembuktian sebelumnya (tetapi hanya pada kolom-kolom yang diberikan oleh pembuktian), dan memverifikasi bahwa kedua prosedur ini memberikan jawaban yang sama.

Dalam kasus ini, memperpanjang 𝑡′, dan menghitung kombinasi linear yang sama ([6,−9,−8,12]) dari kolom, keduanya memberikan jawaban yang sama: −10746. Hal ini membuktikan bahwa akar Merkle dibangun "dengan itikad baik" (atau setidaknya "cukup dekat"), dan sesuai dengan 𝑡′: setidaknya sebagian besar kolom kompatibel satu sama lain dan dengan 𝑡′.

Tetapi pemeriksa masih perlu memeriksa satu hal lagi: sebenarnya memeriksa evaluasi polinomial di {𝑟0..𝑟3}. Sejauh ini, tidak ada langkah pemeriksa yang benar-benar bergantung pada nilai yang diklaim oleh pembuktinya. Jadi inilah bagaimana kita melakukan pemeriksaan itu. Kita mengambil produk tensor dari apa yang kita label sebagai bagian “kolom” dari titik evaluasi:

Dalam contoh kita, di mana r={1,2,3,4} sehingga separuh dari kolom yang dipilih adalah {1,2}), ini sama dengan:

Jadi sekarang kita mengambil kombinasi linear dari 𝑡′ ini:

Yang sama persis dengan jawaban yang Anda dapatkan jika Anda mengevaluasi polinomial secara langsung.

Di atas adalah cukup dekat dengan deskripsi lengkap dari protokol Binius “sederhana”. Ini sudah memiliki beberapa keuntungan menarik: misalnya, karena data dibagi menjadi baris dan kolom, Anda hanya memerlukan setengah ukuran lapangan. Tetapi ini tidak mendekati untuk mewujudkan semua manfaat dari melakukan perhitungan dalam bentuk biner. Untuk ini, kita akan memerlukan protokol Binius lengkap. Tapi pertama, mari kita mendapatkan pemahaman yang lebih dalam tentang bidang biner.

Bidang biner

Bidang terkecil yang mungkin adalah aritmatika modulo 2, yang begitu kecil sehingga kita dapat menuliskan tabel penjumlahan dan perkaliannya:

Kita dapat membuat bidang biner yang lebih besar dengan mengambil ekstensi: jika kita mulai dengan 𝐹2 (bilangan bulat modulo 2) dan kemudian mendefinisikan 𝑥 di mana 𝑥2=𝑥+1, kita mendapatkan tabel penambahan dan perkalian berikut:

Ternyata kita dapat memperluas bidang biner ke ukuran yang sangat besar secara sembarang dengan mengulangi konstruksi ini. Tidak seperti dengan angka kompleks di atas bilangan real, di mana Anda dapat menambahkan satu elemen baru 𝑖, tetapi Anda tidak dapat menambahkan lebih banyak lagi (kuaternion memang ada, tetapi mereka matematika aneh, misalnya 𝑎𝑏≠𝑏𝑎), dengan bidang terbatas Anda dapat terus menambahkan ekstensi baru selamanya. Secara khusus, kami mendefinisikan elemen sebagai berikut:

Dan seterusnya. Hal ini sering disebut sebagai konstruksi menara, karena bagaimana setiap perpanjangan berturut-turut dapat dilihat sebagai penambahan lapisan baru ke menara. Ini bukan satu-satunya cara untuk membangun bidang biner dengan ukuran sembarang, tetapi memiliki beberapa keunggulan unik yang dimanfaatkan oleh Binius.

Kita dapat mewakili angka-angka ini sebagai daftar bit, mis. 1100101010001111. Bit pertama mewakili kelipatan dari 1, bit kedua mewakili kelipatan dari 𝑥0, kemudian bit-bit berikutnya mewakili kelipatan dari: 𝑥1, 𝑥1∗𝑥0, 𝑥2, 𝑥2∗𝑥0, dan seterusnya. Encoding ini bagus karena Anda dapat mendekomposisinya:

Ini adalah notasi yang relatif tidak umum, tetapi saya suka mewakili elemen lapangan biner sebagai bilangan bulat, mengambil representasi bit di mana bit yang lebih signifikan berada di sebelah kanan. Artinya, 1=1, 𝑥₀=01=2, 1+𝑥₀=11=3, 1+𝑥₀+𝑥₂=11001000=19, dan seterusnya. 1100101010001111 adalah, dalam representasi ini, 61779.

Penambahan dalam bidang biner hanyalah XOR (begitu juga pengurangan, by the way); perhatikan bahwa ini berarti x+x=0 untuk setiap x. Untuk mengalikan dua elemen x*y, ada algoritma rekursif yang sangat sederhana: bagi setiap angka menjadi dua bagian:

Kemudian, pisahkan perkalian:

Potongan terakhir adalah satu-satunya yang sedikit sulit, karena Anda harus menerapkan aturan reduksi, dan menggantikan 𝑅𝑥∗𝑅𝑦∗𝑥𝑘2 dengan 𝑅𝑥∗𝑅𝑦∗(𝑥𝑘−1∗𝑥𝑘+1). Ada cara yang lebih efisien untuk melakukan perkalian, analog dari algoritma Karatsuba dan transformasi Fourier cepat, tetapi saya akan membiarkannya sebagai latihan bagi pembaca yang tertarik untuk menemukannya.

Pembagian dalam bidang biner dilakukan dengan menggabungkan perkalian dan inversi. Cara "sederhana tapi lambat" untuk melakukan inversi adalah penerapan teorema kecil Fermat umum. Ada juga algoritma inversi yang lebih rumit namun lebih efisien, yang dapat Anda temukan di siniAnda dapat menggunakan kode di siniuntuk bermain-main dengan penambahan, perkalian, dan pembagian lapangan biner sendiri.

Kiri: tabel penambahan untuk elemen medan biner empat bit (yaitu elemen yang hanya terdiri dari kombinasi dari 1， 𝑥₀，𝑥₁dan 𝑥₀𝑥₁.

Benar: tabel perkalian untuk elemen lapangan biner empat bit.

Hal yang indah tentang jenis bidang biner ini adalah bahwa ia menggabungkan beberapa bagian terbaik dari bilangan bulat 'biasa' dan aritmatika modular. Seperti bilangan bulat biasa, elemen bidang biner tidak terbatas: Anda dapat terus memperluas sejauh yang Anda inginkan. Tetapi seperti aritmatika modular, jika Anda melakukan operasi atas nilai-nilai dalam batas ukuran tertentu, semua jawaban Anda juga tetap dalam batas yang sama. Misalnya, jika Anda mengambil pangkat-pangkat berturut-turut dari 42, Anda akan mendapatkan:

Setelah 255 langkah, Anda kembali ke 42²⁵⁵= 1. Sama seperti bilangan bulat positif dan aritmatika modular, mereka mengikuti hukum matematika biasa: ab=ba, a(b+c)=a b+a*c, ada beberapa hukum baru yang aneh.

Akhirnya, bidang biner membuatnya mudah untuk menangani bit: jika Anda melakukan matematika dengan angka yang cocok 2^kbit, maka semua output Anda juga akan muat 2 k bit. Hal ini menghindari rasa malu. Dalam EIP-4844 Ethereum, setiap "blok" dari blob harus menjadi sebuah modul digital 52435875175126190479447740508185965837690552500527637822603658699938581184513, sehingga mengkodekan data biner memerlukan pembuangan sebagian ruang dan melakukan pemeriksaan tambahan untuk memastikan bahwa setiap elemen menyimpan nilai kurang dari 2²⁴⁸Ini juga berarti bahwa operasi medan biner sangat cepat pada komputer - baik CPU dan desain FPGA dan ASIC secara teoretis optimal.

Apa arti dari semua ini adalah bahwa kita bisa melakukan sesuatu seperti enkoding Reed-Solomon yang kita lakukan di atas, dengan cara yang benar-benar menghindari “ledakan” bilangan bulat, seperti yang kita lihat dalam contoh kita, dan dengan cara yang sangat “meledak”. Cara “asli”, jenis komputasi yang baik dilakukan oleh komputer. Atribut “split” dari bidang biner - bagaimana kita melakukannya 1100101010001111=11001010+10001111*x₃dan kemudian membaginya sesuai dengan kebutuhan kami juga sangat penting untuk mencapai banyak fleksibilitas.

Full Binius

Lihat di siniuntuk implementasi python dari protokol ini.

Sekarang, kita bisa mencapai “Binius penuh”, yang menyesuaikan “Binius sederhana” untuk (i) bekerja di atas bidang biner, dan (ii) memungkinkan kita untuk berkomitmen pada bit-bit individual. Protokol ini sulit untuk dipahami, karena terus-menerus beralih antara berbagai cara untuk melihat matriks bit; tentu saja membutuhkan waktu lebih lama bagi saya untuk memahaminya daripada biasanya saya memahami protokol kriptografi. Tetapi begitu Anda memahami bidang biner, kabar baiknya adalah bahwa tidak ada “matematika yang lebih sulit” yang bergantung pada Binius. Ini bukan pasangan kurva eliptis, di mana ada lubang kelinci aljabar geometri yang lebih dalam dan lebih dalam untuk ditelusuri; di sini, bidang biner adalah semua yang Anda butuhkan.

Mari kita lihat lagi diagram lengkap:

Sekarang, Anda harus terbiasa dengan sebagian besar komponen. Gagasan untuk "meratakan" hypercube menjadi kisi-kisi, gagasan untuk menghitung kombinasi baris dan kombinasi kolom sebagai produk tensor dari titik evaluasi, dan gagasan untuk memeriksa kesetaraan antara "Reed-Solomon memperluas kemudian menghitung kombinasi baris", dan "menghitung kombinasi baris kemudian Reed-Solomon memperluas", semuanya dalam Binius sederhana.

Apa yang baru di “full Binius”? Pada dasarnya ada tiga hal:

• Nilai-nilai individual dalam hiperkubus, dan dalam persegi, harus menjadi bit (0 atau 1)
• Proses perpanjangan memperluas bit menjadi lebih banyak bit, dengan mengelompokkan bit ke dalam kolom dan sementara berpura-pura bahwa mereka adalah elemen lapangan yang lebih besar
• Setelah langkah kombinasi baris, ada langkah "decompose into bits" dari segi elemen, yang mengubah ekstensi kembali menjadi bit

Kami akan menjelaskannya satu per satu. Pertama, prosedur perluasan baru. Sebuah kode Reed-Solomon memiliki batasan mendasar bahwa jika Anda memperluas nilai-nilai 𝑛 menjadi nilai-nilai 𝑘*𝑛, Anda perlu bekerja di dalam sebuah bidang yang memiliki 𝑘*𝑛 nilai yang berbeda yang dapat Anda gunakan sebagai koordinat. Dengan 𝐹₂ (alias, bit), Anda tidak bisa melakukannya. Jadi apa yang kita lakukan adalah, kita “mengemas” 𝐹 yang berdekatan₂menggabungkan elemen-elemen bersama menjadi nilai-nilai yang lebih besar. Dalam contoh di sini, kita mengemas dua bit setiap kali ke dalam elemen-elemen di {0,1,2,3}, karena ekstensi kita hanya memiliki empat titik evaluasi dan itu sudah cukup bagi kita. Dalam bukti “nyata”, kita mungkin mengemas 16 bit sekaligus. Kemudian kita melakukan kode Reed-Solomon atas nilai-nilai yang dikemas ini, dan mengembalikannya menjadi bit-bit lagi.

Sekarang, kombinasi baris. Untuk membuat pemeriksaan "mengevaluasi pada titik acak" menjadi aman secara kriptografis, kita perlu bahwa titik tersebut diambil dari ruang yang cukup besar, jauh lebih besar dari hiperkubus itu sendiri. Oleh karena itu, sementara titik-titik dalam hiperkubus adalah bit, evaluasi di luar hiperkubus akan jauh lebih besar. Dalam contoh kita di atas, "kombinasi baris" akhirnya menjadi [11,4,6,1].

Ini menyajikan sebuah masalah: kita tahu bagaimana menggabungkan pasangan bit menjadi nilai yang lebih besar, dan kemudian melakukan perluasan Reed-Solomon pada nilai tersebut, tetapi bagaimana Anda melakukannya pada pasangan nilai yang jauh lebih besar?

Tip dalam Binius adalah melakukannya secara bit: kita melihat bit-bit individual dari setiap nilai (mis. untuk apa yang kami label sebagai “11”, itu [1,1,0,1]), lalu kita memperluas secara baris. Artinya, kita melakukan prosedur perluasan pada baris 1 dari setiap elemen, kemudian pada baris 𝑥0, kemudian pada “𝑥₁baris, kemudian pada 𝑥₀∗𝑥₁baris, dan seterusnya (nah, dalam contoh mainan kita kita berhenti di sana, tetapi dalam implementasi nyata kita akan mencapai 128 baris (yang terakhir adalah 𝑥₆∗ …∗ 𝑥₀)).

Meringkas:

• Kami mengambil bit dalam hiperkubus, dan mengonversinya menjadi grid
• Kemudian, kami memperlakukan kelompok bit yang berdekatan pada setiap baris sebagai elemen lapangan yang lebih besar, dan melakukan aritmatika pada mereka untuk memperluas baris Reed-Solomon
• Kemudian, kami mengambil kombinasi baris dari setiap kolom bit, dan mendapatkan kolom bit (untuk persegi lebih besar dari 4x4, jauh lebih kecil) untuk setiap baris sebagai output
• Kemudian, kami melihat output sebagai matriks, dan memperlakukan bit-bit tersebut sebagai baris lagi

Kenapa ini berhasil? Dalam matematika “normal”, kemampuan untuk (sering) melakukan operasi linear dalam urutan apa pun dan mendapatkan hasil yang sama berhenti berfungsi jika Anda mulai memotong angka menjadi digit. Misalnya, jika saya mulai dengan angka 345, dan saya mengalikannya dengan 8 dan kemudian dengan 3, saya mendapatkan 8280, dan jika saya lakukan dua operasi tersebut secara terbalik, saya juga mendapatkan 8280. Tetapi jika saya memasukkan operasi “membagi dengan digit” di antara dua langkah tersebut, itu menjadi rusak: jika Anda melakukan 8x kemudian 3x, Anda mendapatkan:

Tapi jika kamu melakukan 3x, dan kemudian 8x, kamu akan mendapatkan:

Namun dalam bidang biner yang dibangun dengan struktur menara, pendekatan ini memang berhasil. Alasannya terletak pada sifat yang dapat dipisahkan: jika Anda mengalikan nilai besar dengan nilai kecil, apa yang terjadi pada setiap segmen tetap berada pada setiap segmen. Jika kita mengalikan 1100101010001111 dengan 11, ini sama seperti faktorisasi pertama dari 1100101010001111, yang adalah

Dan kemudian mengalikan setiap komponen secara terpisah dengan 11.

Menyatukan semuanya

Secara umum, sistem bukti pengetahuan nol bekerja dengan membuat pernyataan tentang polinomial yang secara bersamaan mewakili pernyataan tentang evaluasi yang mendasarinya: sama seperti yang kita lihat dalam contoh Fibonacci, 𝐹(𝑋+2)−𝐹(𝑋+1)−𝐹(𝑋)=𝑍(𝑋)∗𝐻(𝑋) secara bersamaan memeriksa semua langkah perhitungan Fibonacci. Kami memeriksa pernyataan tentang polinomial dengan membuktikan evaluasi di titik acak. Pemeriksaan di titik acak ini mewakili pemeriksaan seluruh polinomial: jika persamaan polinomial tidak cocok, kemungkinan bahwa cocok di koordinat acak tertentu sangat kecil.

Dalam praktik, sumber utama ketidaksempurnaan berasal dari kenyataan bahwa dalam program-program nyata, sebagian besar angka yang kita kerjakan sangat kecil: indeks dalam loop for, nilai Benar/Salah, penghitung, dan hal-hal serupa. Tetapi ketika kita 'memperluas' data menggunakan enkoding Reed-Solomon untuk memberinya redundansi yang diperlukan untuk membuat pemeriksaan berbasis bukti Merkle menjadi aman, sebagian besar nilai 'ekstra' akhirnya menghabiskan ukuran penuh dari sebuah bidang, meskipun nilai aslinya kecil.

Untuk mengatasi hal ini, kami ingin membuat bidang ini sekecil mungkin. Plonky2 menurunkan kami dari angka 256-bit menjadi 64-bit, dan kemudian Plonky3 melangkah lebih jauh menjadi 31 bit. Namun bahkan ini sub-optimal. Dengan bidang biner, kita dapat bekerja pada bit-bit individu. Hal ini membuat encoding “padat”: jika data dasar sebenarnya memiliki n bit, maka encoding Anda akan memiliki n bit, dan ekstensinya akan memiliki 8 * n bit, tanpa overhehead tambahan.

Sekarang, mari kita lihat diagram untuk ketiga kalinya:

Di Binius, kami berkomitmen pada polinomial multilinear: sebuah hiperkubus 𝑃(x₀,x₁,…x_k), di mana evaluasi individu P (0,0 ... 0), P(0,0... 1) hingga P(1,1,... 1) memegang data yang kami pedulikan. Untuk membuktikan evaluasi pada suatu titik, kami "menafsirkan ulang" data yang sama sebagai persegi. Kami kemudian memperluas setiap baris, menggunakan pengkodean Reed-Solomon atas kelompok bit, untuk memberikan data redundansi yang diperlukan untuk kueri cabang Merkle acak agar aman. Kami kemudian menghitung kombinasi baris linier acak, dengan koefisien yang dirancang sehingga baris gabungan baru benar-benar memegang evaluasi yang kami pedulikan. Kedua baris yang baru dibuat ini (yang ditafsirkan ulang sebagai 128 baris bit), dan beberapa kolom yang dipilih secara acak dengan cabang Merkle, diteruskan ke pemverifikasi.

Verifikator kemudian melakukan “kombinasi baris ekstensi” (atau lebih tepatnya, beberapa kolom dari ekstensi), dan “ekstensi dari kombinasi baris”, dan memverifikasi bahwa keduanya cocok. Mereka kemudian menghitung kombinasi kolom, dan memeriksa bahwa itu mengembalikan nilai yang diklaim oleh pemberi bukti. Dan inilah sistem bukti kita (atau lebih tepatnya, skema komitmen polinomial, yang merupakan blok bangunan kunci dari sebuah sistem bukti).

Apa yang belum kita bahas?

• Algoritma yang efisien untuk memperluas baris, yang diperlukan untuk benar-benar meningkatkan efisiensi komputasi verifier. Kami menggunakan transformasi Fourier Cepat di atas lapangan biner, yang dijelaskandi sini (meskipun implementasinya akan berbeda, karena posting ini menggunakan konstruksi yang kurang efisien yang tidak didasarkan pada perpanjangan rekursif).
• Arithmetization. Polinomial univariat nyaman karena Anda dapat melakukan hal-hal seperti F(X+2)-F(X+1)-F(X) = Z(X)*H(X) untuk mengaitkan langkah-langkah berdekatan dalam perhitungan. Dalam hiperkubus, "langkah berikutnya" jauh lebih sulit diinterpretasikan daripada "X+1". Anda bisa menggunakan X+k, pangkat k, tetapi perilaku melompat ini akan mengorbankan banyak keuntungan kunci dari Binius. Solusinya disajikan dalam Kertas Binius(Lihat Bagian 4.3), tetapi ini adalah lubang kelinci yang dalam dalam dirinya sendiri.
• Bagaimana cara melakukan pemeriksaan nilai tertentu dengan aman. Contoh Fibonacci memerlukan pemeriksaan kondisi batas kunci: F(0)=F(1)=1 dan nilai dari F(100). Tetapi dengan Binius “mentah”, tidak aman untuk memeriksa pada titik evaluasi yang sudah diketahui sebelumnya. Ada cara yang cukup sederhana untuk mengonversi pemeriksaan evaluasi yang diketahui menjadi pemeriksaan evaluasi yang tidak diketahui, menggunakan apa yang disebut protokol pemeriksaan jumlah; tetapi kita tidak membahas hal itu di sini.
• Protokol pencarian, teknologi lain yang baru-baru ini mulai digunakan sebagai cara untuk membuat sistem pembuktian ultra-efisien. Binius dapat digabungkan dengan protokol pencarian untuk banyak aplikasi.
• Melampaui waktu verifikasi akar kuadrat. Akar kuadrat mahal: bukti Binius dari bit sekitar 11 MB panjangnya. Anda dapat mengatasi hal ini dengan menggunakan sistem bukti lain untuk membuat "bukti dari bukti Binius", sehingga memperoleh efisiensi Binius dalam membuktikan pernyataan utama dan ukuran bukti yang kecil. Pilihan lainnya adalah protokol FRI-Binius yang jauh lebih rumit, yang menciptakan bukti berukuran polilogaritmik (seperti FRI reguler).
• Bagaimana Binius mempengaruhi apa yang dianggap sebagai 'SNARK-friendly'. Ringkasan dasarnya adalah bahwa, jika Anda menggunakan Binius, Anda tidak perlu lagi terlalu memperhatikan membuat komputasi 'aritmatika ramah': hash 'reguler' tidak lagi lebih efisien dari hash aritmatika tradisional, perkalian modulo atau modulo tidak lagi menjadi masalah besar dibandingkan dengan perkalian modulo, dan sebagainya. Namun ini adalah topik yang rumit; banyak hal berubah ketika semuanya dilakukan dalam biner.

Saya berharap banyak peningkatan lebih lanjut dalam teknik pembuktian berbasis binary di bulan-bulan mendatang.

Disclaimer:

1. Artikel ini diambil dari [GatePanews]. Teruskan Judul Asli 'Vitalik详解Binius：基于二进制字段的高效证明系统'. Seluruh hak cipta dimiliki oleh penulis asli [GateVitalik Buterin*]. Jika ada keberatan terkait pencetakan ulang ini, silakan hubungi Gate Belajartim, dan mereka akan menanganinya dengan cepat.
2. Penyangkalan Tanggung Jawab: Pandangan dan opini yang diungkapkan dalam artikel ini semata-mata milik penulis dan tidak merupakan saran investasi apa pun.
3. Terjemahan artikel ke dalam bahasa lain dilakukan oleh tim Gate Belajar. Kecuali disebutkan, menyalin, mendistribusikan, atau menjiplak artikel yang diterjemahkan dilarang.