1. Perkenalan
ZK-SNARK adalah sistem pembuktian kriptografi yang memungkinkan suatu entitas membuktikan bahwa sesuatu itu benar tanpa mengungkapkan informasi lain.
ZK-SNARK berguna dalam berbagai aplikasi dan bidang, seperti blockchain dan komputasi yang dapat diverifikasi. Salah satu aplikasi blockchain terkenal digunakan di ZK-Rollups.
ZK-Rollup adalah blockchain lapis kedua yang dibangun di atas blockchain lain (seperti Ethereum) yang memanfaatkan ZK-SNARK (atau sistem bukti kriptografi lainnya) untuk membuktikan validitas transisi negara. Artinya, setiap kali pembaruan jaringan baru dilakukan (batch transaksi baru ditambahkan), status jaringan baru dihitung dan bukti validitas status ini dihasilkan. Intinya adalah, hanya satu entitas yang diperlukan untuk menghasilkan bukti ini, dan siapa pun dapat mempercayai validitasnya.
Properti yang diinginkan yang disediakan oleh ZK-Rollups biasanya adalah (i) skalabilitas dan/atau (ii) perlindungan privasi. ZK-Rollup terkadang disebut Rollup efektivitas ketika hanya skalabilitas yang diperlukan.
Untuk menghitung bukti di ZK-Rollup yang dirancang untuk memperluas EVM Ethereum, ZK-EVM dapat digunakan. Didefinisikan secara ketat, ZK-EVM adalah sekumpulan program kriptografi (sirkuit) yang bertanggung jawab untuk menghasilkan bukti tanpa pengetahuan (ZKP), meskipun terkadang dalam bahasa sehari-hari ini juga merujuk pada keseluruhan ZK-Rollup universal berkemampuan EVM.
2. Definisi ZK-SNARK
SNARK adalah bukti singkat bahwa pernyataan tertentu benar. Secara formal, ini menunjukkan pengetahuan tentang jejak eksekusi suatu algoritma yang menghasilkan solusi yang tepat untuk masalah tertentu. Sebaliknya, ini menunjukkan pengetahuan tentang nilai-nilai non-publik dan non-konstan yang melakukan pelacakan. Nilai-nilai tersebut secara keseluruhan sering disebut sebagai saksi. Unsur-unsur saksi, yaitu bagian-bagian yang dimasukkan ke dalam algoritma, merupakan saksi yang independen karena mereka ada sebelum algoritma dieksekusi dan tidak ditentukan oleh elemen-elemen lain dari jejak eksekusi. Nilai non-konstanta publik dari jejak eksekusi, yang menentukan contoh masalah yang dipecahkan oleh algoritma, disebut pernyataan publik.
ZK-SNARK adalah singkatan dari Argumen Pengetahuan Non-Interaktif Ringkas Pengetahuan Nol.
S - Kesederhanaan
Kesederhanaan - pembuktiannya "singkat" dan waktu verifikasinya "cepat":
Pembuktian “pendek” berarti besarnya pembuktian bersifat sublinear, relatif terhadap besarnya saksi.
Waktu verifikasi yang “cepat” berarti bahwa waktu berjalannya verifikator harus (i) sublinear dalam jumlah saksi, dan (ii) linier dalam tuntutan publik.
Namun pada kenyataannya, kami menginginkannya tidak hanya "ringkas" tetapi juga "tingkat log polinomial".
Artinya, jumlah pembuktian dan waktu verifikasi hampir tidak bergantung pada jumlah saksi.
Buktikan bahwa ukuran π tidak boleh bertambah lebih cepat dari kelipatan konstan kuadrat logaritma ukuran saksi w (untuk w yang cukup besar):
Ukuran buktinya bergantung pada protokol ZK-SNARK tertentu. Untuk Plonky2 itu O(log^2(|w|)), tapi itu kasus "terburuk". Misalnya, untuk PLONK klasik dan Groth16, ukuran pembuktiannya adalah O(1), yang merupakan sebuah konstanta.
Waktu verifikasi t_v tidak boleh lebih dari beberapa kali konstan kuadrat logaritma saksi w, dan linier dalam ukuran deklarasi publik x (x dan w cukup besar jika hanya salah satu dari keduanya yang mengubah ukurannya).
N - Non-Interaktif - Pembuatan bukti terjadi tanpa menerima data apa pun dari verifikator.
ARK - Bukti Pengetahuan - Mirip dengan pembuktian biasa, namun suara hanya berlaku terhadap pembuktian yang dibatasi secara polinomial, sedangkan dalam pembuktian, suara berlaku terhadap pembuktian yang tidak dibatasi secara komputasi. Kita akan membahas konsep bunyi pada bagian selanjutnya.
ZK - Pengetahuan Nol - Tidak ada pengungkapan saksi.
3. Properti ZK-SNARK
ZK-SNARK memiliki tiga properti utama, seperti dijelaskan di bawah ini:
Kelengkapan: Jika pembukti mengetahui lintasan eksekusi algoritma yang benar, maka pemverifikasi harus yakin bahwa pembukti memiliki pengetahuan ini.
Tingkat pengetahuan yang baik: Kecuali jika pemeriksa benar-benar mengetahui alur pelaksanaan yang benar, pembukti tidak dapat meyakinkan pemeriksa bahwa ia mengetahuinya, namun kemungkinannya sangat kecil.
Pengetahuan nol: Verifikator tidak mengetahui apa pun tentang lintasan eksekusi kecuali bahwa lintasan tersebut benar.
4. Sistem pembuktian PLONKish ZK-SNARK
4.1 Pengenalan PLONKish ZK-SNARK dan fungsinya
Untuk dapat diterapkan pada suatu algoritma tertentu, sistem pembuktian ZK-SNARK perlu mengetahui sistem persamaan pada bidang berhingga. Persamaan tersebut menggambarkan hubungan antar nilai pada tabel lintasan eksekusi algoritma (the struktur data yang menyimpan lintasan eksekusi) untuk memastikan bahwa perhitungannya adalah Integritas. Bahasa yang digunakan untuk menyatakan sistem persamaan ini (disebut juga sistem kendala) disebut aritmatika.
Sistem pembuktian PLONKish ZK-SNARK menggunakan aritmatika dengan kekuatan ekspresi lebih tinggi dibandingkan sistem pembuktian lama. Yang pertama memungkinkan kita untuk menggunakan persamaan sistem kendala bentuk polinomial sewenang-wenang atas variabel kendala, sedangkan untuk sistem pembuktian yang lebih tua (yaitu sistem berdasarkan R1CS) persamaan ini berbentuk polinomial linier dan kuadrat. Fitur ini membuat sistem pembuktian PLONKish ZK-SNARK memberikan dampak positif pada efisiensi komputasi pembuktian dan membuatnya lebih mudah untuk diterapkan ke berbagai algoritma. Oleh karena itu, banyak sistem bukti PLONKish ZK-SNARK telah muncul dalam beberapa tahun terakhir, seperti PLONK klasik, Halo2, Kimchi, Plonky2, HyperPlonk, dll.
Di Taiko, kami menggunakan varian sistem bukti Halo2 berdasarkan skema komitmen polinomial KZG.
Sistem pembuktian PLONKish ZK-SNARK terdiri dari tiga komponen:
4.2 Rencana komitmen
Skema janji mengijinkan seorang committer untuk mempublikasikan sebuah nilai, yang disebut dengan sebuah janji, yang mengikat committer ke sebuah pesan tanpa mengungkapkan pesan itu sendiri. Pengimplementasi kemudian dapat membuka komitmen dan memaparkan pesan yang dikomit, atau sebagian darinya, kepada verifikator, yang dapat memeriksa apakah informasi yang diekspos konsisten dengan komitmen.
Penulis yang berbeda menjelaskan sejumlah algoritma berbeda yang membentuk skema komitmen. Namun, kami harus menyebutkan setidaknya empat algoritma berikut:
Pengaturan: mengambil beberapa parameter awal sebagai masukan dan menghasilkan parameter pengaturan. Pengaturan tersebut menentukan (i) apa yang kita komitmenkan (misalnya, untuk skema komitmen polinomial unary, kita menentukan domain koefisien dan derajat maksimum polinomial yang kita komitmenkan), dan (ii) tingkat keamanan dalam bit. Secara sederhana kita dapat mendefinisikan tingkat keamanan sebagai berikut: Jika diperlukan waktu O(2^n) untuk memecahkan suatu sistem enkripsi, maka sistem enkripsi tersebut mempunyai tingkat keamanan sebesar n bit.
Janji: Janji yang menghasilkan pesan berdasarkan parameter yang ditetapkan.
Pembukaan sebagian: Menghasilkan bukti pembukaan sebagian khusus untuk bagian pesan yang dipilih (misalnya, nilai polinomial unary yang dilakukan untuk beberapa parameter), serta mengatur parameternya.
Validasi: Gunakan pengesahan terbuka sebagian dan atur parameter untuk memeriksa apakah informasi yang diungkapkan oleh pembukti adalah bagian tertentu dari pesan yang sesuai dengan komitmen yang ditentukan.
*Untuk beberapa skema komitmen, algoritma "setup" dan "open" mungkin tidak ada (misalnya, saat menggunakan fungsi hash untuk melakukan nilai besar).
Rencana komitmen harus memiliki karakteristik berikut:
Mengikat: Sekali pepatah berkomitmen pada pesan tertentu, ia akan terikat pada pesan yang dikomitnya;
Menyembunyikan: Janji untuk tidak mengungkapkan informasi apa pun tentang pesan tersebut. Penyembunyian bisa sempurna, yaitu bukti yang sebagian terbuka tidak mengungkapkan informasi apa pun tentang bagian pesan yang tidak ditanyakan (misalnya komitmen KZG), atau tidak sempurna, yaitu bukti yang sebagian terbuka mengungkapkan beberapa bagian dari informasi yang disebutkan di atas (misalnya berdasarkan FRI komitmen polinomial).
Skema komitmen dapat dibagi menjadi beberapa jenis berdasarkan objek sasarannya: komitmen elemen tunggal; komitmen vektor komitmen;
Skema komitmen polinomial adalah satu-satunya jenis yang langsung digunakan dalam sistem pembuktian PLONKish ZK-SNARK. Untuk sistem pembuktian di atas (seperti PLONK klasik, Halo2, Kimchi, Plonky2, dll.), skema komitmen polinomial univariat sangat penting. Namun, kini ada beberapa metode PLONKish ZK-SNARK baru yang didasarkan pada skema komitmen polinomial multilinear (misalnya HyperPlonk).
4.3 Bukti Oracle Interaktif
Bukti oracle interaktif adalah bukti interaktif di mana verifikator memiliki "akses ke oracle" untuk memperoleh pesan-pesan peribahasa, dapat menanyakannya secara probabilistik, dan tidak perlu membaca keseluruhan pesan-pesan peribahasa.
4.4 Heuristik Fiat-Shamir
Heuristik Fiat-Shamir menyediakan cara untuk mengubah argumen interaktif (koin publik) menjadi argumen non-interaktif. Secara intuitif, idenya adalah mengganti tantangan acak validator dengan hash dari pesan sebelumnya, namun secara spesifik umumnya tidak ditentukan.
*Protokol Koin Publik adalah protokol di mana validator hanya mengirimkan elemen acak.
4.5 Prinsip kerja sistem pembuktian ZK-SNARK gaya PLONK
Dalam sistem pembuktian ZK-SNARK, metode pembuktian Oracle interaktif yang dimodifikasi digunakan untuk membuktikan pengetahuan saksi, yang menggunakan komitmen polinomial untuk memberikan Oracle akses ke pesan pembukti dan menjadikannya bebas interaksi melalui heuristik Fiat-Shamir. Di bagian ini, kami akan menjelaskan konstruktor yang diberikan secara detail.
Ingatlah bahwa menerapkan sistem pembuktian ZK-SNARK ke suatu algoritma memerlukan pembangunan sistem batasan yang sesuai. Untuk dapat membangunnya, kita mendefinisikan struktur tabel jejak eksekusi algoritma dan nilai konstanta di dalamnya. Kami menggunakan istilah "rangkaian" untuk merujuk pada struktur kompleks dari tabel jejak eksekusi yang hanya diisi dengan konstanta dan sistem batasan yang sesuai. Untuk menghasilkan bukti ZK-SNARK untuk contoh eksekusi suatu algoritma, kita perlu mensintesis contoh rangkaian untuk itu yang merupakan contoh yang sesuai dari rangkaian algoritma dan tabel jejak eksekusi (yaitu, tabel yang menentukan konstanta, saksi, dan nilai deklarasi publik) kombinasi.
Mari kita perhatikan struktur tabel pelacakan yang digunakan oleh sistem pembuktian ZK-SNARK gaya PLONK. Semua kolom dalam tabel tersebut termasuk dalam salah satu dari tiga jenis, yang kami beri nama sesuai dengan terminologi yang digunakan di Halo2 dan dijelaskan sebagai berikut:
Kolom tetap - selnya berisi konstanta dari tabel jejak eksekusi;
Kolom Instance - digunakan untuk menyimpan nilai deklarasi publik;
Kolom Saran - tempat menyimpan semua data saksi (termasuk nilai saksi independen dan hasil rahasia yang dihitung).
Untuk meringkas, kami mencatat hal berikut:
Tabel jejak eksekusi (tipe PLONKish) = kolom tetap + kolom instance + kolom saran; sirkuit = tabel jejak eksekusi yang hanya berisi konstanta + sistem batasan instance = sirkuit + saksi di tabelnya + deklarasi publik di tabelnya; pernyataan publik, nilai saksi independen) → Contoh sirkuit; Terapkan sistem pembuktian ZK-SNARK ke algoritma tertentu = jelaskan sirkuit + tentukan proses sintesis.
Mengapa istilah "sirkuit" banyak digunakan dalam konteks ini? Awalnya, ketika hanya sistem pembuktian ZK-SNARK berbasis R1CS yang tersedia, akan lebih mudah untuk merepresentasikan sistem kendala dalam bentuk rangkaian aritmatika, yang keluarannya harus nol. Kami percaya bahwa dalam konteks SNARK PLONKish, istilah "sirkuit" digunakan karena alasan historis. Bagaimanapun, mari kita pertimbangkan secara singkat rangkaian aritmatika yang digunakan untuk ZK-SNARK versi lama.
Rangkaian aritmatika untuk SNARK berbasis R1CS mendefinisikan polinomial n-variabel pada bidang berhingga dan memiliki skema evaluasi. Awalnya, ini direpresentasikan sebagai grafik asiklik berarah (DAG):
itu termasuk:
Input publik x, digunakan untuk menentukan nilai deklarasi publik;
Input rahasia w, digunakan untuk menentukan nilai saksi independen;
Gerbang aritmatika untuk menentukan penjumlahan dan perkalian pada bidang berhingga.
Mari kita lihat contoh rangkaian aritmatika pada bidang bilangan rasional.
Kita mulai dari bawah dan bekerja dengan gerbang terendah pada diagram, yaitu (2 x 4 = 8) dan (4 + 11 = 15), menyimpan nilai-nilai ini sebagai nilai perantara;
Kemudian kita naik satu baris (ke baris kedua) dan menghitung jumlah kedua nilai perantara (yang kita peroleh pada tahap sebelumnya), yaitu (8 + 15 = 23);
Karena kami hanya memiliki tiga gerbang dan kami melewati semuanya, 23 adalah hasil akhir kami.
Setelah sistem pembuktian PLONKish ZK-SNARK mensintesis instance sirkuit, kolom dari setiap tabel jejak eksekusi instance dikodekan sebagai polinomial pada bidang berhingga dengan cara berikut. Misalkan C_j(x) adalah kolom deskripsi polinomial j dan ω adalah akar primitif ke-2^k, di mana k dipilih sedemikian rupa sehingga 2^k sedikit lebih besar dari tinggi awal contoh tabel. Contoh tabel diisi dengan baris acak (hanya dengan sel bukan nol di kolom yang disarankan) untuk memuat 2^k baris, dan C_j(ω^i) diatur ke nilai baris ke-i dari baris ke-j kolom contoh tabel yang diberikan. Peran padding untuk atribut tanpa pengetahuan akan dijelaskan nanti.
Pernyataan "ω adalah akar primitif 2^k-th" berarti ω^(2^k) = 1, dan kita mempunyai ω^t ≠ 1 untuk bilangan bulat positif t yang kurang dari 2^k.
Sistem kendala diubah menjadi bentuk persamaan polinomial dengan mengganti variabel-variabel di dalamnya dengan polinomial terkait yang diperoleh dari polinomial kolom, dengan mensubstitusi "x dikalikan ω dipangkatkan" sebagai pengganti x.
Sebagai contoh, mari kita perhatikan persamaan sistem kendala s(i) * (a(i) * b(i) - c(i+1)) = 0. Artinya jika s(i) bukan nol, maka a(i) * b(i) harus sama dengan c(i+1). Di sini, a, b dan c adalah kolom yang disarankan, s adalah kolom tetap dan i adalah nomor baris saat ini.
Batasan ini dapat diterapkan ke semua 2^k baris sebagai berikut. Misalkan S(x), A(x), B(x), dan C(x) berturut-turut adalah polinomial pada kolom a, b, c, dan s. Oleh karena itu, kami berharap:
Artinya semua elemen dalam himpunan ini harus merupakan akar dari S(x) * (A(x) * B(x) - C(x * ω)). Oleh karena itu, polinomial ini harus habis dibagi:
Karena ω adalah akar primitif berorde 2^k.
Z(x) = x^(2^k) - 1 disebut "polinomial hilang" karena semua x yang merupakan elemen grup perkalian siklik dihasilkan oleh ω adalah 0. Oleh karena itu, S(x) * (A(x) * B(x) - C(x * ω)) mod Z(x) = 0 berarti batasan di atas berlaku untuk semua 2^k baris.
Misalkan P_0(x), P_1(x), ... , P_m(x) adalah batasan yang diterapkan pada semua 2^k baris dan konsisten dengan polinomial S(x) * (A(x) * B(x) yang dipertimbangkan di atas ) - C(x * ω)) memiliki bentuk serupa. Jika α dipilih secara acak oleh pemverifikasi dari bidang berhingga, maka
Ini berarti bahwa dengan probabilitas yang sangat tinggi semua batasan ini terpenuhi untuk semua 2^k baris. Persamaan ini berarti kita dapat menemukan hasil bagi polinomial T(x) sedemikian rupa
Oleh karena itu, agar verifikator yakin bahwa pembukti mengetahui isi tabel jejak eksekusi yang memenuhi semua batasan m dengan probabilitas yang sangat tinggi, hanya perlu dibuktikan bahwa untuk α yang dipilih secara acak, pembukti memiliki kejadian P_0 (x), P_1(x ),..., polinomial kolom yang disarankan dan polinomial hasil bagi T(x) dalam P_m(x) memenuhi persamaan polinomial ini. Verifikator dapat melakukan hal ini dengan meminta pembuktian untuk mencari nilai suatu polinomial tertentu pada suatu titik acak yang dipilih oleh verifikator dari antara titik-titik yang bukan akar ζ dari Z(x), dan mengevaluasi kedua ruas persamaan tersebut pada titik tersebut. ζ. Saya percaya bahwa pembuktian mungkin mengetahui polinomial ini. Cara ini dapat dibuktikan dengan lemma Schwartz-Zippel.
Untuk membuat pembuatan bukti menjadi non-interaktif, semua nilai acak yang dihasilkan oleh verifikator dalam versi interaktif harus diperoleh menggunakan heuristik Fiat-Shamir.
Untuk mengikat pembuktian ke polinomial usulannya dan hasil bagi polinomial T(x), digunakan skema komitmen polinomial. Pepatah membuat komitmen pada polinomial ini, membuka komitmen ini di ζ (atau pada ζ * ω^q jika beberapa kendala mempengaruhi baris i dan i + q), dan membuat bukti yang mencakup (I) komitmen ini, (II) Nilai dari polinomial di ζ (atau lebih ζ * ω^q jika perlu) dan (III) bukti terbuka yang sesuai. Sebenarnya untuk mempersingkat pembuktian, gunakan beberapa pembukaan, yaitu menghasilkan pembuktian kecil untuk nilai semua titik polinomial. Oleh karena itu, buktinya ringkas.
Untuk memenuhi properti tanpa pengetahuan, baris yang dipilih secara acak oleh pembuktian ditambahkan ke instance tabel jejak eksekusi, sehingga tingginya 2^k baris. Baris-baris ini hanya memiliki sel bukan nol pada kolom saran karena hanya kolom saran yang berisi data yang ingin kita sembunyikan. Lakukan ini sebelum menyusun polinomial kolom proposal sehingga jumlah pasangan "nilai parameter" yang terungkap selama periode pembukaan komitmen lebih kecil daripada jumlah pasangan yang ditambahkan secara acak untuk setiap polinomial. Oleh karena itu, untuk setiap polinomial kolom proposal, jumlah informasi yang diperlukan untuk memulihkannya setelah komitmen dibuka lebih besar daripada jumlah informasi saksi. Situasi ini mengakibatkan nol pengetahuan.
Selama fase prapemrosesan, semua instance dari rangkaian pelaksana melakukan beberapa penghitungan yang sama, termasuk menyiapkan dan menghitung polinomial kolom tetap dan komitmennya untuk skema komitmen polinomial. Bagian data yang dihasilkan dari perhitungan ini digunakan oleh verifikator dan sering disebut kunci verifikasi. Demikian pula, konsep kunci pembuktian dapat didefinisikan. Skema komitmen polinomial yang mendasari menentukan apakah pengaturan kepercayaan dibuat selama fase pra-pemrosesan.