Kekuatan Bukti Tanpa Pengetahuan: Menyelami lebih dalam zk-SNARK

Artikel ini akan menguraikan teknologi ini menggunakan matematika, mengilustrasikan bagaimana teknologi ini dapat membuktikan kebenaran pengetahuan tanpa mengungkapkan informasi apa pun.

Disusun oleh: Penelitian DODO

Penulis: Salah satu pendiri 0xAlpha @DeriProtocol

Pengantar

Zk-SNARK, atau argumen pengetahuan non-interaktif ringkas tanpa pengetahuan, memungkinkan verifikator mengonfirmasi bahwa pembukti memiliki pengetahuan tertentu (disebut saksi) yang memenuhi hubungan tertentu tanpa mengungkapkan informasi apa pun tentang pengetahuan itu sendiri.

Menghasilkan zk-SNARK untuk masalah tertentu melibatkan empat tahap berikut:

• Ubah suatu masalah (atau fungsi) menjadi rangkaian aritmatika.
• Rangkaian ini kemudian diterjemahkan ke dalam persamaan matriks.
• Persamaan matriks ini selanjutnya diubah menjadi polinomial yang harus habis dibagi polinomial minimum tertentu.
• Akhirnya, pembagian ini dinyatakan dalam titik-titik kurva elips di atas bidang berhingga, tempat pembuktian dilakukan.

Tiga langkah pertama hanya mengubah representasi pernyataan asli. Langkah terakhir memproyeksikan pernyataan dari langkah ketiga ke dalam ruang terenkripsi menggunakan enkripsi homomorfik, sehingga pembukti dapat memverifikasi pernyataan yang dicerminkan di dalamnya. Mengingat proyeksi ini menggunakan enkripsi asimetris, tidak mungkin untuk mundur dari pernyataan di langkah 3 ke pernyataan awal, sehingga memastikan paparan tanpa pengetahuan.

Latar belakang matematika yang diperlukan untuk membaca artikel ini sebanding dengan tingkat aljabar yang diharapkan dari mahasiswa STEM tahun pertama. Satu-satunya konsep yang mungkin menantang adalah kriptografi kurva elips. Bagi mereka yang belum terbiasa dengan hal ini, Anda dapat menganggapnya sebagai fungsi eksponensial dengan basis khusus, mengingat kebalikannya masih belum terpecahkan.

Artikel ini akan mengikuti aturan notasi berikut:

Matriks: Huruf besar tebal, mis A; ditulis dalam bentuk eksplisit \
Vektor: Huruf kecil dengan tanda panah, ditulis dalam bentuk eksplisit [ ]; semua vektor adalah vektor kolom secara default \
Skalar: Diwakili dengan huruf biasa

Mari kita ambil pertanyaan berikut sebagai contoh:

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

Misalkan Alice ingin membuktikan bahwa dia mengetahui suatu kebenaran. Kami akan membahas seluruh prosedur yang perlu dilakukan Alice untuk menghasilkan zk-SNARK sebagai buktinya.
Pertanyaan ini mungkin tampak terlalu sederhana karena tidak melibatkan aliran kendali (misalnya, jika-maka-lainnya). Namun, tidak sulit untuk mengubah fungsi dengan aliran kontrol menjadi ekspresi aritmatika. Misalnya, perhatikan masalah berikut (atau “fungsi” dalam bahasa pemrograman):

f(x, z):
jika(z==1):
kembalikan xxx+xx+5
kalau tidak:
kembalikan xx+5

Menulis ulang soal ini ke dalam ekspresi aritmatika berikut (dengan asumsi z termasuk dalam (0,1)) tidak lebih rumit dari persamaan (1) .

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

Pada artikel kali ini kita akan terus menggunakan persamaan (1) sebagai dasar pembahasan kita.

Langkah 1: Sirkuit Aritmatika

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

Hal ini sesuai dengan rangkaian aritmatika berikut:

Kita juga menyebut persamaan (2) sebagai himpunan yang terdiri dari 4 “batasan primer”, masing-masing batasan menggambarkan hubungan gerbang aritmatika dalam rangkaian. Secara umum himpunan n batasan utama dapat diringkas sebagai program aritmatika kuadrat (QAP) yang akan dijelaskan selanjutnya.

Langkah 2: Matriks

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

dimana y, s1, s2, dan s3 didefinisikan seperti pada persamaan (2).
Biasanya, untuk masalah dengan m masukan dan n gerbang aritmatika (mis n-1 langkah perantara dan hasil akhir), vektor saksi ini akan berdimensi (m+n+1). Dalam kasus dunia nyata, angka n bisa sangat besar. Misalnya, untuk fungsi hash, n biasanya berjumlah ribuan.

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

Persamaan (3) hanyalah representasi lain dari persamaan (2): setiap himpunan (ai, bi, ci) berhubungan dengan gerbang dalam rangkaian. Kita dapat melihatnya dengan memperluas persamaan matriks secara eksplisit:

Jadi LHS=RHS sama persis dengan persamaan (2), dan setiap baris persamaan matriks berhubungan dengan batasan primer (yaitu, gerbang aritmatika dalam rangkaian).

Kami melewatkan langkah-langkah membangun (A, B, C), yang sebenarnya relatif mudah. Kita hanya perlu mengubahnya menjadi matriks sesuai dengan batasan utama yang bersangkutan untuk menentukan isi setiap baris (A, B, C), yaitu (ai, bi, ci). Ambil baris pertama sebagai contoh: kita dapat dengan mudah melihat bahwa untuk membuat batasan utama pertama x dikalikan x sama dengan s1, kita perlu mengalikan [0,1,0,0,0], [0, 1,0, 0,0] dan [0,0,0,1,0,0] dengan vektor s.

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

Langkah 3: Polinomial

Sekarang, mari kita buat matriks PA n(n+m+*1), yang mendefinisikan himpunan polinomial mengenai z:

Memastikan bahwa fungsinyamengambil nilai berikut di {1, 2, 3, 4} memenuhi ketentuan:

Kemudian kita dapat menulis ulang A menjadi:

Ini adalah empat kumpulan persamaan linier yang melibatkan enam variabel yang dapat diselesaikan dengan menggunakan metode tradisional. Namun, cara yang lebih efisien untuk menyelesaikan PA dalam kasus ini adalah interpolasi Lagrangian, yang mengeksploitasi kekhasan permasalahan. Di sini kita melewatkan proses penyelesaian PA, yang agak membosankan namun mudah.

Demikian pula, kita membuat PB dan PC secara terpisah untuk B dan C. Kemudian kita dapat menulis ulang persamaan matriksnyasebagai berikut:

Mengamati setiap baris secara terpisah, terlihat jelas bahwa keempat baris ini berhubungan dengan ekspresi yang sama yang dievaluasi pada empat titik berbeda. Oleh karena itu, persamaan matriks di atas ekuivalen dengan:

Langkah 3: Titik Kurva Elips

Tulis ulang persamaan (4) menjadi:

di mana i(z)=1 hanyalah polinomial derajat nol sepele di z yang digunakan untuk menyatukan persamaan - semua suku bersifat kuadrat. Pentingnya hal ini akan segera menjadi jelas. Perhatikan bahwa persamaan ini hanya berisi penjumlahan dan perkalian polinomial di z.

Harap dicatat bahwa operasi aritmatika, penjumlahan (+) dan perkalian (X), juga dipetakan ke operasi yang bersesuaian di bidang berhingga titik kurva elips. Simbol-simbolnya Dan digunakan untuk menghindari kebingungan dan menunjukkan bahwa ini adalah operasi lapangan yang didefinisikan ulang.

Selanjutnya kami akan menjelaskan langkah praktisnya lebih detail.

Kriptografi Kurva Elips

Teori umum kurva elips jauh melampaui cakupan artikel ini. Untuk tujuan di sini, kurva elips didefinisikan sebagai pemetaan dari bidang prima Fp ke fungsi E, di mana E mencakup titik-titik sedemikian rupa sehingga y^2=x^3+ax+b (disebut titik kurva elips, atau disingkat ECP) .

Harap dicatat bahwa meskipun kita telah membahas aritmatika reguler sejauh ini, ketika bertransisi ke bidang prima, operasi aritmatika pada bilangan dilakukan menggunakan aritmatika modular. Misalnya, a+b=a+b(mod p), dengan p adalah orde dari Fp.

Sebaliknya, penjumlahan dua titik kurva elips didefinisikan seperti gambar di bawah ini:

Secara khusus, penambahan P dan Q dari dua ECP:

Temukan perpotongan garis PQ dan kurva R dan definisikan sebagai -(P+Q)
Balik ke titik “cermin” R' dari R pada kurva.
Oleh karena itu kita mendefinisikan penjumlahan titik kurva elips P+Q=R':

Perhatikan bahwa aturan ini juga berlaku untuk kasus khusus dimana penambahan satu ECP digunakan, dalam hal ini garis singgung ke titik tersebut akan digunakan.

Sekarang misalkan kita memilih titik G secara acak dan memetakan angka 1 ke titik tersebut. (“Pemetaan awal” ini terdengar agak sewenang-wenang. Kita akan membahasnya nanti). Dan untuk setiap n yang termasuk dalam Fp, kita definisikan:

E(N)=G+G+G+…..+G=G dikalikan n

Ada ekspresi operasi. Definisikan operasi +G sebagai “generator”, dilambangkan dengan g. Maka definisi di atas setara dengan:

Setelah mendefinisikan penjumlahan, hubungan linier berikut menjadi jelas:

Oleh karena itu, setiap hubungan linier (atau batasan) di Fp akan dipertahankan di ruang terenkripsi B melalui pemetaan ini. Misalnya, persamaan l + m = n di Fp akan menghasilkan

Namun, karena persamaan (5) yang ingin dibuktikan Alice berbentuk kuadrat, maka persamaan tersebut tidak cukup linier. Untuk menangani suku kuadrat, kita perlu mendefinisikan perkalian dalam ruang terenkripsi. Ini disebut peta berpasangan, atau peta bilinear, yang akan saya jelaskan di bagian berikut.

Peta Bilinear

Misalkan G1, G2 dan GT adalah kelompok orde prima g. Fungsi berpasangan, atau peta bilinear, didefinisikan sebagai berikut:

String Referensi Umum

Keseluruhan ini disebut dengan “kunci pembuktian” (PK). Perhatikan bahwa representasi vektor dalam E() harus dipahami sebagai vektor titik kurva elips, di mana setiap titik dipetakan dari elemen vektor yang sesuai. Jadi, ke-11 vektor ini sebenarnya terdiri dari 62 (=42+63+63+63) titik kurva elips. 62 ECP ini akan diberikan kepada Alice, sang pembuktian. Dalam skenario umum, untuk masalah dengan m masukan dan n kendala utama, PK akan berisi 2n + 3(m+n+1)*3 = 11n + 9m + 9 ECP.

Secara bersamaan, perhitungan berikut akan dilakukan:

Seluruh proses disebut “kunci verifikasi” (VK). Hanya 7 titik kurva elips (ECP) yang terlibat di sini, yang perlu diberikan kepada verifikator. Perlu dicatat bahwa tidak peduli berapa banyak masukan dan kendala utama yang terlibat dalam masalah, VK selalu terdiri dari 7 ECP.

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

Pembuktian dan Verifikasi

Sekarang setelah memiliki kunci publik (PK), Alice akan menghitung titik kurva elips (ECP) berikut:

9 titik kurva elips ini sangat penting untuk argumen pengetahuan non-interaktif ringkas tanpa pengetahuan (zk-SNARK)!

Perhatikan bahwa Alice pada dasarnya hanya melakukan kombinasi linier pada titik kurva elips di kunci publik. Hal ini sangat penting dan akan diperiksa secara ketat selama verifikasi.

Sekarang, Alice menyajikan bukti zk-SNARK, yang akhirnya mengarahkan kita ke proses verifikasi, yang terjadi dalam tiga langkah.

Pertama, perlu dipastikan bahwa 8 titik kurva elips pertama memang merupakan kombinasi linier dari titik-titik tersebut dalam string referensi umum.

Penafian:

1. Artikel ini dicetak ulang dari[chaincatcher]. Semua hak cipta milik penulis asli [0xAlpha Co-founder @ DeriProtocol]. Jika ada keberatan terhadap cetak ulang ini, silakan menghubungi tim Gate Learn , dan mereka akan segera menanganinya.
2. Penafian Tanggung Jawab: Pandangan dan pendapat yang diungkapkan dalam artikel ini adalah sepenuhnya milik penulis dan bukan merupakan nasihat investasi apa pun.
3. Terjemahan artikel ke bahasa lain dilakukan oleh tim Gate Learn. Kecuali disebutkan, dilarang menyalin, mendistribusikan, atau menjiplak artikel terjemahan.