Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs

Penulis: 0xAlpha Co-founder @DeriProtocol; Kompiler: Penelitian DODO

Pendahuluan

zk-SNARKs, atau “zero-knowledge concise non-interactive arguments of knowledge”, memungkinkan verifikator untuk mengkonfirmasi bahwa seorang prover memiliki pengetahuan khusus tertentu, yang dikenal sebagai saksi, yang memuaskan hubungan tertentu tanpa mengungkapkan apa pun tentang saksi itu sendiri.

Menghasilkan zk-SNARKs untuk masalah tertentu terdiri dari empat fase berikut:

• Mengubah masalah (atau fungsi) menjadi sirkuit gerbang aritmatika.
• Rangkaian ini kemudian diterjemahkan ke dalam rumus matriks.
• Rumus matriks ini selanjutnya diubah menjadi polinomial, yang harus dibagi dengan polinomial minimum tertentu. Akhirnya, pembagian ini diwakili dalam titik kurva eliptik di bidang terbatas, di mana bukti terjadi.

Tiga langkah pertama hanya mengubah representasi dari pernyataan asli. Langkah terakhir menggunakan enkripsi homomorfik untuk memproyeksikan pernyataan langkah 3 ke dalam ruang kriptografi, memungkinkan prover untuk memverifikasi pernyataan cermin di dalamnya. Mengingat bahwa proyeksi ini menggunakan kriptografi asimetris, tidak mungkin untuk melacak kembali ke pernyataan asli dari langkah ketiga, memastikan paparan tanpa pengetahuan.

Latar belakang matematika yang diperlukan untuk membaca artikel ini setara dengan tingkat mahasiswa baru aljabar untuk jurusan STEM. Satu-satunya konsep yang dapat menantang mungkin adalah enkripsi kurva eliptik. Bagi mereka yang tidak terbiasa dengan ini, ini dapat dianggap sebagai fungsi eksponensial dengan kardinalitas khusus, sambil mengingat bahwa kebalikannya tetap belum terpecahkan.

Artikel ini akan mengikuti aturan notasi berikut:

• Matriks: huruf kapital tebal, misalnya A; Tulis secara eksplisit dalam bentuk
• Vektor: huruf kecil dengan panah, ditulis dalam bentuk eksplisit [ ] ; Secara default, semua vektor adalah vektor kolumnar
• Skalar: Representasi huruf biasa

Mari kita gunakan pertanyaan ini sebagai contoh:

f(x)=x^3+x^2+5 (1)

Katakanlah Alice ingin membuktikan bahwa dia mengetahuinya. Kami akan berjalan melalui seluruh prosedur yang perlu diambil Alice untuk menghasilkan zk-SNARKs untuk buktinya.

Pertanyaan ini mungkin tampak terlalu sederhana karena tidak melibatkan aliran kontrol (misalnya, jika-maka-lain). Namun, tidak sulit untuk mengubah fungsi dengan aliran kontrol menjadi ekspresi aritmatika. Sebagai contoh, mari kita pertimbangkan pertanyaan berikut (atau “fungsi” dalam bahasa pemrograman):

f(x, z):

jika (z == 1):

mengembalikan x*x*x+x*x+5

lain:

mengembalikan x*x+5

Sangat mudah untuk menulis ulang masalah ini ke dalam ekspresi aritmatika berikut (dengan asumsi z milik (0,1)), yang tidak jauh lebih rumit daripada persamaan (1).

f(x,z)=(z-1)(x^2+5)+z(x^3+x^2+5)

Pada artikel ini, kita akan terus menggunakan persamaan (1) sebagai dasar diskusi.

Langkah 1: Rangkaian gerbang aritmatika

Persamaan (1) dapat dipecah menjadi operasi aritmatika dasar berikut:

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128057_watermarknone.png)

Ini sesuai dengan rangkaian gerbang aritmatika berikut:

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7127628_watermarknone.png)

Kami juga menyebut persamaan (2) sebagai satu set 4 “kendala orde pertama”, yang masing-masing menggambarkan hubungan gerbang aritmatika dalam suatu rangkaian. Secara umum, satu set n kendala orde pertama dapat digeneralisasikan sebagai prosedur aritmatika kuadrat (QAP), yang akan dijelaskan selanjutnya.

Langkah 2: Matriks

Pertama, mari kita definisikan vektor “saksi” sebagai berikut:

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128058_watermarknone.png)

di mana y, s1, s2, s3 sama dengan yang didefinisikan dalam persamaan (2).

Secara umum, untuk masalah dengan input m dan gerbang aritmatika n (yaitu, langkah menengah n-1 dan output akhir), vektor saksi ini akan berdimensi (m + n + 1). Dalam masalah praktis, angka n bisa sangat besar. Misalnya, untuk fungsi hash, n biasanya beberapa ribu.

Selanjutnya, mari kita buat tiga matriks n*(m+n+*1) A,B,C sehingga kita dapat menulis ulang persamaan (2) sebagai berikut:

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128059_watermarknone.png)

Persamaan (3) hanyalah representasi lain dari Persamaan (2): setiap kelompok (ai, bi, ci) sesuai dengan gerbang di sirkuit. Kita hanya perlu memperluas rumus matriks dengan jelas untuk melihat ini:

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128060_watermarknone.png)

Jadi LHS = RHS persis sama dengan persamaan (2), dan setiap baris persamaan matriks sesuai dengan batasan orde pertama (yaitu, gerbang aritmatika di rangkaian).

Kami melewatkan langkah-langkah build (A, B, C), yang relatif mudah. Kita hanya perlu mengubahnya menjadi bentuk matriks sesuai dengan batasan tingkat pertama yang sesuai, untuk menentukan konten setiap baris (A, B, C), YAITU (AI, BI, CI). Ambil baris pertama sebagai contoh: mudah untuk melihat bahwa agar batasan orde pertama x dikalikan dengan x sama dengan s1 untuk bertahan, kita perlu mengalikan [0,1,0,0,0,0], [0,1,0,0,0] dan [0,0,0,1,0,0] dengan vektor s.

Dengan demikian, kami telah berhasil mengubah rangkaian gerbang aritmatika menjadi rumus matriks, yaitu persamaan (3). Pada saat yang sama, kami juga telah mengubah objek yang perlu dibuktikan untuk dikuasai dari vektor saksi s.

Langkah 3: Polinomial

Sekarang, mari kita buat matriks n * (* n + m + * 1) PA yang mendefinisikan satu set polinomial tentang z:

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128061_watermarknone.png)

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128062_watermarknone.png)

Ini adalah empat set persamaan linear untuk enam variabel yang dapat diselesaikan dengan metode tradisional. Namun, cara yang lebih efisien untuk menyelesaikan PA dalam kasus ini adalah interpolasi Lagrangian, yang mengambil keuntungan dari kekhususan masalah. Di sini kita melewatkan proses penyelesaian untuk PA, yang agak membosankan tetapi mudah.

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128063_watermarknone.png)

Ke dalamnya:

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128064_watermarknone.png)

Langkah 4: Titik Kurva Elips

Tulis ulang persamaan (4) ke:

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128065_watermarknone.png)

di mana i(z)=1 hanyalah polinomial orde nol trivial untuk z, yang digunakan untuk menyatukan persamaan - semua suku adalah kuadrat. Kebutuhan untuk melakukannya akan segera menjadi jelas. Perhatikan bahwa persamaan ini hanya berisi penambahan dan perkalian polinomial z.

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128066_watermarknone.png)

Selanjutnya, kami akan menjelaskan langkah-langkah sebenarnya secara lebih rinci.

Enkripsi kurva elips

Teori umum kurva eliptik jauh melampaui cakupan artikel ini. Untuk keperluan makalah ini, kurva elips didefinisikan sebagai pemetaan dari domain prima Fp ke fungsi E, di mana E mencakup titik-titik yang memuaskan y ^ 2 = x ^ 3 + ax + b (disebut titik kurva eliptik, atau ECP untuk jangka pendek).

Perhatikan bahwa sementara kita telah berbicara tentang aritmatika reguler sejauh ini, sekarang ketika kita mengkonversi ke bidang prima, operasi aritmatika pada angka dilakukan dengan cara modular. Misalnya, a + b = a + b (mod p), di mana p adalah urutan Fp.

Di sisi lain, definisi penambahan dua titik kurva eliptik ditunjukkan pada gambar berikut:

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128067_watermarknone.png)

Secara khusus, penambahan dua ECP, P dan Q:

Temukan perpotongan garis PQ dan kurva R, yang didefinisikan sebagai -(P+Q)

Balik ke titik ‘cermin’ R’ pada kurva untuk R.

Jadi kita mendefinisikan penambahan titik kurva eliptik P + Q = R ':

Perhatikan bahwa aturan ini juga berlaku untuk kasus-kasus khusus, yaitu di mana aditif diri ECP, di mana garis singgung titik akan digunakan.

Sekarang anggaplah kita memilih titik G acak dan memetakan angka 1 untuk itu. (“Pemetaan awal” ini terdengar agak sewenang-wenang.) Lebih lanjut tentang itu nanti). Kemudian untuk setiap n menjadi milik Fp, kami mendefinisikan:

E(N)=G+G+G+…+G=G

Ini memiliki ekspresi tindakan. Tindakan yang mendefinisikan +G adalah “generator” dan dilambangkan sebagai g. Maka definisi di atas setara dengan:

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128068_watermarknone.png)

Bagi mereka yang tidak terbiasa dengan kurva elips, Anda dapat menganalogikan pemetaan ini dengan fungsi eksponensial reguler di mana kardinal g menggantikan bilangan real. Operasi aritmatika berperilaku sama. Namun, perbedaan utama adalah bahwa fungsi invers g ^ n tidak layak secara komputasi. Artinya, tidak ada cara untuk menghitung versi kurva elips! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128069_watermarknone.png)。 Ini, tentu saja, dasar kriptografi kurva eliptik. Pemetaan semacam itu dikenal sebagai enkripsi satu arah.

Perhatikan bahwa mengingat kurva elips, karena memilih G (dan karena itu Generator g) adalah arbitrer (kecuali untuk titik-titik pada sumbu x), ada banyak cara untuk memetakannya. Memilih (G atau g) dapat dianalogikan dengan memilih kardinalitas fungsi eksponensial (2^x, 10^x, e^x, dll.) sebagai bagian dari akal sehat.

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128070_watermarknone.png)

Namun, persamaan (5) yang ingin dibuktikan Alice adalah kuadrat dan karenanya tidak cukup linier. Untuk menangani istilah kuadrat, kita perlu mendefinisikan perkalian dalam ruang kriptografi. Ini dikenal sebagai fungsi pasangan, atau peta bilinear, dan akan dijelaskan selanjutnya.

Pemetaan bilinear

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128071_watermarknone.png)

String referensi umum

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128072_watermarknone.png)

Seluruh proses disebut “kunci verifikasi”, atau disingkat VK. Hanya ada 7 titik kurva eliptik (ECP) yang terlibat di sini, yang perlu diberikan kepada verifikator. Penting untuk dicatat bahwa tidak peduli berapa banyak input dan kendala tingkat pertama yang terlibat dalam masalah, VK selalu terdiri dari 7 ECP.

Selain itu, perlu disebutkan bahwa “pengaturan tepercaya” dan proses menghasilkan PK dan VK dapat dilakukan sekali untuk masalah tertentu.

Bukti & Verifikasi

Sekarang dengan kunci publik (PK), Alice akan menghitung titik kurva eliptik (ECP) berikut:

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128073_watermarknone.png)

9 titik kurva elips ini adalah kunci untuk zero-knowledge concise non-interactive proofs (zk-SNARKs)!

Perhatikan bahwa Alice sebenarnya hanya melakukan beberapa operasi kombinatorial linier pada titik kurva eliptik di kunci publik. Ini sangat penting dan akan diperiksa selama validasi.

Sekarang Alice telah menyerahkan bukti zk-SNARK, akhirnya mari kita masuk ke proses verifikasi, yang merupakan proses tiga langkah.

Pertama-tama, penting untuk memastikan bahwa 8 titik kurva elips pertama benar-benar merupakan kombinasi linier dari titik-titik tersebut dalam string referensi generik.

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128074_watermarknone.png)

Jika ketiga pemeriksaan itu benar, maka persamaan (5) diverifikasi, jadi kami percaya bahwa Alice mengenal saksinya.

Mari kita jelaskan alasan di balik persamaan tersebut. Ambil persamaan pertama di bagian pertama sebagai contoh, yang berlaku karena sifat bilinear:

! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128075_watermarknone.png)

Namun, karena Alice tidak mengetahui nilai simbol alfa, dia tidak dapat menghitung penambahan ini secara eksplisit. Satu-satunya cara dia bisa menemukan pasangan yang memenuhi persamaan (EA, EA’) adalah dengan menggunakan set vektor yang sama masing-masing, hitung! [Kekuatan Bukti Tanpa Pengetahuan: Decoding Matematis zk-SNARKs] (https://img.jinse.cn/7128076_watermarknone.png).

Referensi

“Zk-SNARKs: Di Bawah Tenda” (Vitalik Buterin)

“Tinjauan Bukti Pengetahuan Nol” (Thomas Chen, Abby Lu, Jern Kunpittaya, dan Alan Luo)

“Mengapa dan Bagaimana zk-SNARK Bekerja: Penjelasan Definitif” (Maksym Petkus)

Situs Web: Bukti Tanpa Pengetahuan

Wikipedia: Kurva elips

Wikipedia: Bidang terbatas

Wikipedia: Kriptografi berbasis pasangan