Masalah yang akan Dibuktikan-Aritmetika Sirkuit-R1CS-Polynomials
**Mengapa mengonversi ke polinomial pada akhirnya? **
Karena karakteristik polinomial, waktu verifikasi dipersingkat secara efektif, dan kesederhanaan tercapai.
**Bagaimana cara mencapai nol pengetahuan? **
Sederhananya, dalam proses menurunkan polinomial, dua bilangan acak lagi dipilih, sehingga polinomial yang diturunkan dapat mencegah verifikator mendapatkan koefisien dari polinomial asli, yaitu input rahasia dari pembukti, sehingga sebagai mewujudkan ZK.
**Bagaimana cara mencapai non-interaksi? **
Sebelum pembuktian dimulai, pihak ketiga diperkenalkan, yaitu pengaturan tepercaya, yang menetapkan tugas asli pemverifikasi untuk memilih nomor acak ke pengaturan tepercaya, untuk mewujudkan non-interaksi antara pemverifikasi dan pembukti.
Teknologi ZK telah menarik banyak perhatian di bidang Web3 dalam dua tahun terakhir. Mulai dari Rollup, semakin banyak proyek di jalur berbeda yang mencoba menggunakan teknologi ZK. Diantaranya, SNARK dan STARK adalah dua istilah yang paling sering didengar.Untuk lebih memahami penerapan teknologi ZK di tahap selanjutnya, **artikel ini akan menyederhanakan logika pembuktian SNARK dari perspektif non-teknis, dan kemudian menggunakan * * Scroll's zk Rollup ** digunakan sebagai contoh untuk mengilustrasikan pengoperasian sistem bukti zk. **
Tujuan dari artikel ini adalah untuk menjelaskan logika dasar, yang mudah dibaca. Ini akan mencoba untuk menghindari penggunaan terminologi, dan tidak akan masuk ke detail seperti transformasi matematis. Mohon maafkan saya atas segala kekurangan.
Pada Januari 2012, Alessandro Chiesa, seorang profesor di University of California, Berkeley, ikut menulis makalah tentang SNARK dan mengusulkan istilah zk-SNARK.
zk-SNARK, nama lengkap Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge, adalah sistem pembuktian menggunakan teknologi ZK. **Perlu dicatat bahwa SNARK adalah nama kelas skema, dan ada banyak metode kombinasi berbeda yang dapat mengimplementasikan SNARK. **
Zero-Knowledge (Zero-Knowledge): Konten yang hanya diketahui oleh peribahasa akan disembunyikan, dan tidak ada orang lain yang dapat melihatnya kecuali sang peribahasa.
Pendek (Ringkas): Bukti yang dihasilkan kecil dan waktu verifikasi cepat.
Non-Interaktif (Non-Interaktif): Ada sedikit atau tidak ada interaksi antara pembukti dan pemverifikasi.
Argumen: Verifikasi verifikator hanya valid untuk pembukti dengan daya komputasi terbatas, karena pembukti dengan daya komputasi super dapat memalsukan bukti, artinya, sistem memiliki reliabilitas komputasi.
Pengetahuan: Pembukti hanya dapat menghitung bukti jika dia mengetahui beberapa informasi yang tidak diketahui oleh pemverifikasi.
Yang perlu dipecahkan oleh zk-SNARK adalah "masalah verifikasi kalkulasi", yaitu apakah pemverifikasi dapat secara efisien memverifikasi hasil kalkulasi tanpa mengetahui privasi pembukti.
Berikut ini akan menggunakan proses konstruksi zk-SNARK yang disederhanakan untuk mengilustrasikan bagaimana sistem menggabungkan pengetahuan nol untuk mencapai verifikasi yang efisien. **
Konstruksi Zk-SNARK
Ubah soal yang akan dibuktikan menjadi polinomial
Sederhananya, ide SNARK adalah mengubah bukti apakah pernyataan itu benar atau tidak menjadi bukti apakah persamaan polinomial itu benar atau tidak.
Seluruh proses konversi: masalah yang harus diverifikasi ➡ rangkaian aritmatika ➡ R1CS ➡ polinomial ➡ konversi antar polinomial
Pertanyaan untuk diverifikasi➡Rangkaian aritmatika
Untuk membuktikan benar tidaknya suatu soal melalui perhitungan, soal yang akan dibuktikan terlebih dahulu harus diubah menjadi soal perhitungan, dan setiap perhitungan dapat digambarkan sebagai rangkaian aritmatika.
Sirkuit aritmatika biasanya terdiri dari konstanta, "gerbang penjumlahan", dan "gerbang perkalian".Melalui superposisi gerbang, kita dapat membuat polinomial kompleks.
Polinomial yang dibangun oleh rangkaian aritmatika pada gambar di atas adalah: (Inp1+Inp2)*(-1) = Keluaran
Masalah pada kenyataannya sangat rumit untuk diubah menjadi rangkaian aritmatika, kita dapat dengan mudah memahaminya sebagai: memasukkan beberapa konten, konten diubah oleh sirkuit, dan akhirnya menghasilkan hasil. Sekarang:
Berdasarkan konsep rangkaian aritmatika, kami membuat rangkaian aritmatika untuk membangkitkan bukti, yaitu:
Rangkaian berisi dua set masukan, masukan publik x dan masukan rahasia w. Masukan publik x berarti bahwa isi adalah nilai tetap dari masalah yang akan dibuktikan, yang diketahui baik oleh pemverifikasi maupun pembukti, dan masukan rahasia w berarti bahwa isi hanya diketahui oleh pembukti.
Rangkaian aritmetika yang kita bangun adalah C( x, w ) = 0, yaitu masukan x dan w melalui rangkaian, dan hasil keluaran akhirnya adalah 0. Ketika pembukti dan pemverifikasi mengetahui bahwa keluaran rangkaian adalah 0 dan masukan publik adalah x, pembukti perlu membuktikan bahwa ia mengetahui masukan rahasia w.
Rangkaian aritmatika ➡R1CS
Kita akhirnya membutuhkan polinomial, tetapi rangkaian aritmatika tidak dapat langsung diubah menjadi polinomial, dan diperlukan R1CS sebagai perantara antara keduanya, sehingga rangkaian aritmatika diubah menjadi R1CS terlebih dahulu.
R1CS, nama lengkap Kendala Peringkat-1 (sistem kendala orde pertama), adalah bahasa untuk mendeskripsikan sirkuit, yang pada dasarnya adalah persamaan matriks-vektor. Secara khusus, R1CS adalah urutan tiga vektor (a,b,c), dan solusi untuk R1CS adalah vektor s, di mana s harus memenuhi persamaan:
Diantaranya, mewakili operasi produk dalam.
Konversi matematika khusus di sini dapat ditemukan di Vatalik: Program Aritmatika Kuadrat: dari Nol ke Pahlawan
Kita hanya perlu mengetahui bahwa peran **R1CS adalah membatasi deskripsi setiap gerbang dalam rangkaian aritmatika, sehingga vektor di antara setiap gerbang memenuhi hubungan di atas. **
R1CS➡Polinomial
Setelah mendapatkan media R1CS, kita dapat mengubahnya menjadi polinomial ekuivalen.
Konversi setara antara matriks dan polinomial dapat dilakukan seperti yang ditunjukkan pada gambar berikut:
polinomial
ubah menjadi matriks
Sesuai dengan sifat transformasi ekuivalen di atas, untuk matriks yang memenuhi R1CS, kita dapat menggunakan metode interpolasi Lagrange untuk mengembalikan setiap koefisien polinomial.Berdasarkan hubungan ini, kita dapat menurunkan matriks R1CS sebagai hubungan polinomial, yaitu:
Catatan: A, B, C masing-masing mewakili polinomial
Polinomial sesuai dengan batasan matriks R1CS yang sesuai dengan masalah yang ingin kita buktikan Melalui konversi di atas, kita dapat mengetahui bahwa polinomial memenuhi hubungan di atas, yang berarti bahwa matriks R1CS kita benar, sehingga menunjukkan bahwa pembuktinya adalah di sirkuit aritmatika.Input rahasia untuk juga benar.
Hingga saat ini, masalah kita disederhanakan menjadi: pemverifikasi secara acak memilih angka x, dan meminta pemberi sertifikat untuk membuktikan bahwa A(x) * B(x)=C(x) benar. berarti input rahasia pemberi sertifikat benar.
Konversi antar polinomial
Dalam rangkaian aritmatika kompleks, terdapat puluhan ribu gerbang, dan kita perlu memverifikasi apakah setiap gerbang memenuhi batasan R1CS. Dengan kata lain, kita perlu memverifikasi persamaan A(x) * B(x)=C(x) beberapa kali, tetapi efisiensi verifikasi terpisah satu per satu terlalu rendah. kendala gerbang pada satu waktu?seks?
Kita tahu bahwa polinomial apa pun dapat didekomposisi menjadi polinomial linier asalkan memiliki solusi. Jadi kita membagi P(x) menjadi F(x) dan H(x), yaitu:
Maka F(x) bersifat publik, artinya ada H(x) = P(x)/F(x), sehingga polinomial yang ingin kita verifikasi akhirnya berubah menjadi:
A(x) * B(x) – C(x): Berisi koefisien polinomial, yang hanya diketahui oleh pembukti, yaitu input rahasia.
F(x) : Polinomial publik yang diketahui oleh pemverifikasi dan pembukti, yaitu input publik.
H(x): Pembukti mengetahuinya melalui perhitungan, tetapi pemverifikasi tidak dapat diketahui.
**Masalah terakhir yang akan dibuktikan adalah: persamaan polinomial A(x) * B(x) – C(x) = F(x) * H(x), berlaku untuk semua x. **
Sekarang hanya perlu memverifikasi polinomial satu kali untuk memverifikasi bahwa semua kendala memenuhi hubungan matriks.
**Di sini kita telah menyelesaikan transformasi soal untuk dibuktikan menjadi polinomial yang hanya perlu diverifikasi sekali, menyadari kesederhanaan sistem. **
Namun kesederhanaan implementasi ini adalah untuk mempersingkat waktu verifikasi verifikator, lalu bagaimana dengan ukuran buktinya?
**Sederhananya, dalam protokol bukti, struktur pohon Merkle digunakan, yang secara efektif mengurangi ukuran bukti. **
Setelah seluruh proses konversi selesai, dua masalah akan muncul secara alami:
Mengapa mengonversi ke polinomial?
Karena polinomial memungkinkan kesederhanaan pembuktian. Masalah pembuktian tanpa pengetahuan adalah untuk memverifikasi bahwa perhitungan memenuhi banyak kendala, dan polinomial dapat memverifikasi banyak kendala pada satu titik. Dengan kata lain, pemverifikasi harus memverifikasi n kali untuk mengonfirmasi masalah, tetapi sekarang hanya perlu memverifikasi sekali untuk mengonfirmasi kebenaran bukti dengan probabilitas tinggi.
Mengapa dua polinomial A(x) * B(x) – C(x )= F(x) * H(x) dapat dibentuk dengan memverifikasi sebuah titik pada polinomial?
Hal ini ditentukan oleh karakteristik polinomial, yaitu hasil perhitungan polinomial pada setiap titik dapat dianggap sebagai representasi dari identitas uniknya. Untuk dua polinomial, mereka hanya akan berpotongan pada jumlah titik yang terbatas.
Untuk dua polinomial berderajat d di atas: A(x) * B(x) – C(x) dan F(x) * H(x), jika tidak sama, keduanya hanya akan paling banyak titik d Berpotongan, yaitu solusi pada titik d adalah sama.
Setelah menyelesaikan konversi polinomial, kita akan memasuki tahap pembuktian polinomial.
Buktikan polinomial berlaku
Demi ilustrasi, kami menggunakan polinomial P(x) = F(x) * H(x).
Sekarang, masalah yang ingin dibuktikan oleh pembukti adalah: pada semua x, P(x) = F(x) *H(x).
Proses verifikasi polinomial di atas oleh pembukti dan pemverifikasi adalah sebagai berikut:
Pemverifikasi memilih titik tantangan acak x, dengan asumsi x = s;
Setelah pembukti menerima s, hitung P(s) dan H(s), dan berikan kedua nilai ini ke pemverifikasi;
Pemverifikasi pertama-tama menghitung F(s), lalu menghitung F(s) * H(s), dan menilai apakah F(s) * H(s) = P(s) benar, dan jika benar, verifikasi lulus.
Namun jika kita pikirkan baik-baik, kita akan menemukan bahwa ada beberapa masalah dalam proses di atas:
Pembukti dapat mengetahui informasi dari seluruh persamaan Jika ia menerima titik acak s, ia dapat menghitung F(s), kemudian membuat pasangan palsu P(x) dan H(x), sehingga P(s ) = F(s) * H(s) untuk menipu pemverifikasi.
Prover tidak menggunakan s yang diberikan oleh verifier untuk menghitung F(s) dan H(s), tetapi menghitung dengan nilai lain untuk menipu verifier.
Nilai yang diterima verifikator dihitung dari input publik dan input privat dari pemverifikasi. Jika verifikator memiliki daya komputasi yang besar, ia dapat memecahkan input privat dari pemverifikasi.
Untuk mengatasi masalah di atas, kami melakukan optimasi berikut:
Setelah pemverifikasi memilih titik acak s, ia melakukan enkripsi homomorfik pada s. Enkripsi homomorfik berarti solusi yang dihitung setelah enkripsi = solusi yang dienkripsi setelah perhitungan; dalam bentuk enkripsi ini, pembukti dapat menghitung solusi, tetapi tidak dapat mengkonstruksi salah P(x) dan H(x).
Saat verifikator memilih titik tantangan s, parameter acak lain λ dipilih untuk menghasilkan hubungan linear tambahan antara s dan λ. Pemverifikasi mengirimkan s dan λ setelah enkripsi homomorfik ke pembukti. Prover mengirimkan buktinya kembali, dan verifikator perlu memverifikasi hubungan antara parameter acak λ dan s sebagai tambahan untuk memverifikasi apakah buktinya benar.
**Bertujuan pada masalah bahwa pemverifikasi dapat memecahkan input rahasia, kita dapat memperkenalkan ZK. ** Melihat seluruh bukti, kita dapat menemukan bahwa selama proses verifikasi, pembukti hanya mengirimkan nilai polinomial yang dihitung ke pemverifikasi, dan pemverifikasi dapat menyimpulkan koefisien polinomial melalui nilai, yang merupakan input rahasia dari pepatah. Untuk mencegah pemverifikasi mundur, kita dapat memilih dua angka acak lagi dan menambahkan satu set nilai saat menurunkan polinomial A, B, dan C dari R1CS, sehingga polinomial yang dipulihkan satu urutan lebih banyak dari polinomial asli , sehingga verifikasi Pembaca tidak dapat memperoleh informasi polinomial asli dari polinomial terenkripsi untuk mewujudkan ZK.
Setelah pengoptimalan, kami menemukan bahwa sistem bukti masih membutuhkan interaksi antara pemverifikasi dan pembukti.Bagaimana kita dapat mencapai non-interaksi?
Terapkan non-interaktif
**Untuk mencapai non-interaksi, SNARK memperkenalkan pengaturan tepercaya (Pengaturan). **
Dengan kata lain, sebelum dimulainya pembuktian, hak verifikator untuk memilih poin tantangan acak diserahkan kepada pihak ketiga yang terpercaya.Setelah pihak ketiga memilih parameter acak λ, ia menempatkan λ terenkripsi di sirkuit R1CS. Dalam hal ini cara, CRS (Common Reference String, string referensi publik) dihasilkan. Verifikator dapat memperoleh Sv-nya sendiri dari CRS, dan verifikator dapat memperoleh Sp-nya sendiri dari CRS.
Perlu dicatat bahwa λ perlu dihancurkan setelah menghasilkan Sv dan Sp. Jika λ bocor, mungkin digunakan untuk memalsukan transaksi melalui verifikasi palsu.
Alur Kerja zk-SNARK
Setelah memahami proses konstruksi SNARK, berdasarkan rangkaian aritmatika yang dapat menghasilkan bukti, proses pembuktian zk-SNARK adalah sebagai berikut:
Pengaturan:(sirkuit C, λ)= (Sv, Sp)
Melalui sirkuit C dan parameter acak λ, dihasilkan parameter acak Sv dan Sp yang digunakan oleh pembukti dan pemverifikasi berikutnya.
Buktikan(Sp,x,w) = Π
Prover menghitung bukti Π melalui parameter acak Sp, input publik x, dan input rahasia w.
Verifikasi(Sv,x,Π) == (∃ w st C(x,w))
Pemverifikasi memverifikasi apakah C(x,w)=0 ada melalui parameter acak Sv, input publik x, dan bukti Π. Pada saat yang sama, verifikasi apakah pembuktian dihitung dengan rangkaian C atau tidak.
Pada titik ini, kami telah menyelesaikan penjelasan dari keseluruhan zk-SNARK Mari kita lihat kasus aplikasi yang sebenarnya.
Kasus: Ambil zk Rollup dari Scroll sebagai contoh
Peran sistem pembuktian adalah untuk memungkinkan pembukti meyakinkan pemverifikasi untuk mempercayai satu hal;
Untuk sistem pembuktian zk adalah untuk membuat verifikator percaya bahwa Bukti Nol Pengetahuan (zero knowledge proof) yang dihitung oleh algoritma zk adalah benar.
Kami menggunakan Scroll zk Rollup sebagai contoh untuk mengilustrasikan pengoperasian sistem bukti zk.
Rollup mengacu pada perhitungan off-chain dan verifikasi on-chain. Untuk zk Rollup, setelah transaksi dieksekusi off-chain, pembukti perlu membuat sertifikat zk untuk root negara baru yang dihasilkan setelah transaksi dieksekusi, dan kemudian meneruskan sertifikat ke kontrak L1 Rollup untuk verifikasi on-chain.
Perlu dicatat bahwa ada dua jenis blok di zk Rollup:
L1 Rollup block: blok yang dikirimkan ke Ethereum
Blok L2: blok yang terdiri dari transaksi yang diajukan oleh pengguna di L2
Berikut ini adalah alur kerja Scroll zk Rollup:
Pengguna memulai transaksi di L2, Sequencer mengambil transaksi, mengeksekusi transaksi off-chain dan menghasilkan blok L2 dan root status baru; pada saat yang sama, mengirimkan data transaksi dan root status baru ke kontrak Rollup pada Ethereum (mengirimkan data transaksi adalah untuk ketersediaan data);
Saat blok L2 dihasilkan, Koordinator akan menerima jalur eksekusi blok dari Sequencer, dan kemudian menetapkan jalur tersebut secara acak ke Roller mana pun;
Roller mengubah jalur eksekusi yang diterima menjadi sirkuit, dan menghasilkan sertifikat validitas untuk setiap sirkuit, lalu mengirimkan sertifikat kembali ke Koordinator;
Setiap kali k L2 blok dihasilkan, Koordinator akan mengirimkan tugas agregasi ke Roller lain untuk mengumpulkan bukti dari k blok menjadi satu bukti gabungan;
Koordinator mengirimkan satu bukti agregasi ke kontrak Rollup, dan kontrak Rollup memverifikasi bukti agregasi dalam kombinasi dengan akar status dan data transaksi yang dikirimkan sebelumnya. Jika verifikasi lolos, blok yang sesuai dianggap diselesaikan pada Scroll.
Seperti dapat dilihat dari proses di atas, Roller adalah pembukti dalam sistem, dan kontrak Rollup adalah pemverifikasi. Roller menghasilkan bukti zk untuk transaksi yang dieksekusi secara off-chain; kontrak Rollup memverifikasi bukti tersebut, dan jika verifikasi lolos, kontrak Rollup akan langsung mengadopsi root status yang dikirimkan sebagai root status barunya.
Lihat Asli
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
Konstruksi dan kasing zk-SNARK
TL;DR
Masalah yang akan Dibuktikan-Aritmetika Sirkuit-R1CS-Polynomials
Karena karakteristik polinomial, waktu verifikasi dipersingkat secara efektif, dan kesederhanaan tercapai.
Sederhananya, dalam proses menurunkan polinomial, dua bilangan acak lagi dipilih, sehingga polinomial yang diturunkan dapat mencegah verifikator mendapatkan koefisien dari polinomial asli, yaitu input rahasia dari pembukti, sehingga sebagai mewujudkan ZK.
Sebelum pembuktian dimulai, pihak ketiga diperkenalkan, yaitu pengaturan tepercaya, yang menetapkan tugas asli pemverifikasi untuk memilih nomor acak ke pengaturan tepercaya, untuk mewujudkan non-interaksi antara pemverifikasi dan pembukti.
Teknologi ZK telah menarik banyak perhatian di bidang Web3 dalam dua tahun terakhir. Mulai dari Rollup, semakin banyak proyek di jalur berbeda yang mencoba menggunakan teknologi ZK. Diantaranya, SNARK dan STARK adalah dua istilah yang paling sering didengar.Untuk lebih memahami penerapan teknologi ZK di tahap selanjutnya, **artikel ini akan menyederhanakan logika pembuktian SNARK dari perspektif non-teknis, dan kemudian menggunakan * * Scroll's zk Rollup ** digunakan sebagai contoh untuk mengilustrasikan pengoperasian sistem bukti zk. **
Tujuan dari artikel ini adalah untuk menjelaskan logika dasar, yang mudah dibaca. Ini akan mencoba untuk menghindari penggunaan terminologi, dan tidak akan masuk ke detail seperti transformasi matematis. Mohon maafkan saya atas segala kekurangan.
Pada Januari 2012, Alessandro Chiesa, seorang profesor di University of California, Berkeley, ikut menulis makalah tentang SNARK dan mengusulkan istilah zk-SNARK.
zk-SNARK, nama lengkap Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge, adalah sistem pembuktian menggunakan teknologi ZK. **Perlu dicatat bahwa SNARK adalah nama kelas skema, dan ada banyak metode kombinasi berbeda yang dapat mengimplementasikan SNARK. **
Yang perlu dipecahkan oleh zk-SNARK adalah "masalah verifikasi kalkulasi", yaitu apakah pemverifikasi dapat secara efisien memverifikasi hasil kalkulasi tanpa mengetahui privasi pembukti.
Berikut ini akan menggunakan proses konstruksi zk-SNARK yang disederhanakan untuk mengilustrasikan bagaimana sistem menggabungkan pengetahuan nol untuk mencapai verifikasi yang efisien. **
Konstruksi Zk-SNARK
Ubah soal yang akan dibuktikan menjadi polinomial
Sederhananya, ide SNARK adalah mengubah bukti apakah pernyataan itu benar atau tidak menjadi bukti apakah persamaan polinomial itu benar atau tidak.
Seluruh proses konversi: masalah yang harus diverifikasi ➡ rangkaian aritmatika ➡ R1CS ➡ polinomial ➡ konversi antar polinomial
Pertanyaan untuk diverifikasi➡Rangkaian aritmatika
Untuk membuktikan benar tidaknya suatu soal melalui perhitungan, soal yang akan dibuktikan terlebih dahulu harus diubah menjadi soal perhitungan, dan setiap perhitungan dapat digambarkan sebagai rangkaian aritmatika.
Sirkuit aritmatika biasanya terdiri dari konstanta, "gerbang penjumlahan", dan "gerbang perkalian".Melalui superposisi gerbang, kita dapat membuat polinomial kompleks.
Polinomial yang dibangun oleh rangkaian aritmatika pada gambar di atas adalah: (Inp1+Inp2)*(-1) = Keluaran
Masalah pada kenyataannya sangat rumit untuk diubah menjadi rangkaian aritmatika, kita dapat dengan mudah memahaminya sebagai: memasukkan beberapa konten, konten diubah oleh sirkuit, dan akhirnya menghasilkan hasil. Sekarang:
Berdasarkan konsep rangkaian aritmatika, kami membuat rangkaian aritmatika untuk membangkitkan bukti, yaitu:
Rangkaian berisi dua set masukan, masukan publik x dan masukan rahasia w. Masukan publik x berarti bahwa isi adalah nilai tetap dari masalah yang akan dibuktikan, yang diketahui baik oleh pemverifikasi maupun pembukti, dan masukan rahasia w berarti bahwa isi hanya diketahui oleh pembukti.
Rangkaian aritmetika yang kita bangun adalah C( x, w ) = 0, yaitu masukan x dan w melalui rangkaian, dan hasil keluaran akhirnya adalah 0. Ketika pembukti dan pemverifikasi mengetahui bahwa keluaran rangkaian adalah 0 dan masukan publik adalah x, pembukti perlu membuktikan bahwa ia mengetahui masukan rahasia w.
Rangkaian aritmatika ➡R1CS
Kita akhirnya membutuhkan polinomial, tetapi rangkaian aritmatika tidak dapat langsung diubah menjadi polinomial, dan diperlukan R1CS sebagai perantara antara keduanya, sehingga rangkaian aritmatika diubah menjadi R1CS terlebih dahulu.
R1CS, nama lengkap Kendala Peringkat-1 (sistem kendala orde pertama), adalah bahasa untuk mendeskripsikan sirkuit, yang pada dasarnya adalah persamaan matriks-vektor. Secara khusus, R1CS adalah urutan tiga vektor (a,b,c), dan solusi untuk R1CS adalah vektor s, di mana s harus memenuhi persamaan:
Diantaranya, mewakili operasi produk dalam.
Konversi matematika khusus di sini dapat ditemukan di Vatalik: Program Aritmatika Kuadrat: dari Nol ke Pahlawan
Kita hanya perlu mengetahui bahwa peran **R1CS adalah membatasi deskripsi setiap gerbang dalam rangkaian aritmatika, sehingga vektor di antara setiap gerbang memenuhi hubungan di atas. **
R1CS➡Polinomial
Setelah mendapatkan media R1CS, kita dapat mengubahnya menjadi polinomial ekuivalen.
Konversi setara antara matriks dan polinomial dapat dilakukan seperti yang ditunjukkan pada gambar berikut:
polinomial
ubah menjadi matriks
Sesuai dengan sifat transformasi ekuivalen di atas, untuk matriks yang memenuhi R1CS, kita dapat menggunakan metode interpolasi Lagrange untuk mengembalikan setiap koefisien polinomial.Berdasarkan hubungan ini, kita dapat menurunkan matriks R1CS sebagai hubungan polinomial, yaitu:
Catatan: A, B, C masing-masing mewakili polinomial
Polinomial sesuai dengan batasan matriks R1CS yang sesuai dengan masalah yang ingin kita buktikan Melalui konversi di atas, kita dapat mengetahui bahwa polinomial memenuhi hubungan di atas, yang berarti bahwa matriks R1CS kita benar, sehingga menunjukkan bahwa pembuktinya adalah di sirkuit aritmatika.Input rahasia untuk juga benar.
Hingga saat ini, masalah kita disederhanakan menjadi: pemverifikasi secara acak memilih angka x, dan meminta pemberi sertifikat untuk membuktikan bahwa A(x) * B(x)=C(x) benar. berarti input rahasia pemberi sertifikat benar.
Konversi antar polinomial
Dalam rangkaian aritmatika kompleks, terdapat puluhan ribu gerbang, dan kita perlu memverifikasi apakah setiap gerbang memenuhi batasan R1CS. Dengan kata lain, kita perlu memverifikasi persamaan A(x) * B(x)=C(x) beberapa kali, tetapi efisiensi verifikasi terpisah satu per satu terlalu rendah. kendala gerbang pada satu waktu?seks?
Untuk kenyamanan pemahaman, kami memperkenalkan P(x), misalkan P(x) = A(x) * B(x) – C(x)
Kita tahu bahwa polinomial apa pun dapat didekomposisi menjadi polinomial linier asalkan memiliki solusi. Jadi kita membagi P(x) menjadi F(x) dan H(x), yaitu:
Maka F(x) bersifat publik, artinya ada H(x) = P(x)/F(x), sehingga polinomial yang ingin kita verifikasi akhirnya berubah menjadi:
A(x) * B(x) – C(x): Berisi koefisien polinomial, yang hanya diketahui oleh pembukti, yaitu input rahasia.
F(x) : Polinomial publik yang diketahui oleh pemverifikasi dan pembukti, yaitu input publik.
H(x): Pembukti mengetahuinya melalui perhitungan, tetapi pemverifikasi tidak dapat diketahui.
**Masalah terakhir yang akan dibuktikan adalah: persamaan polinomial A(x) * B(x) – C(x) = F(x) * H(x), berlaku untuk semua x. **
Sekarang hanya perlu memverifikasi polinomial satu kali untuk memverifikasi bahwa semua kendala memenuhi hubungan matriks.
**Di sini kita telah menyelesaikan transformasi soal untuk dibuktikan menjadi polinomial yang hanya perlu diverifikasi sekali, menyadari kesederhanaan sistem. **
Namun kesederhanaan implementasi ini adalah untuk mempersingkat waktu verifikasi verifikator, lalu bagaimana dengan ukuran buktinya?
**Sederhananya, dalam protokol bukti, struktur pohon Merkle digunakan, yang secara efektif mengurangi ukuran bukti. **
Setelah seluruh proses konversi selesai, dua masalah akan muncul secara alami:
Karena polinomial memungkinkan kesederhanaan pembuktian. Masalah pembuktian tanpa pengetahuan adalah untuk memverifikasi bahwa perhitungan memenuhi banyak kendala, dan polinomial dapat memverifikasi banyak kendala pada satu titik. Dengan kata lain, pemverifikasi harus memverifikasi n kali untuk mengonfirmasi masalah, tetapi sekarang hanya perlu memverifikasi sekali untuk mengonfirmasi kebenaran bukti dengan probabilitas tinggi.
Hal ini ditentukan oleh karakteristik polinomial, yaitu hasil perhitungan polinomial pada setiap titik dapat dianggap sebagai representasi dari identitas uniknya. Untuk dua polinomial, mereka hanya akan berpotongan pada jumlah titik yang terbatas.
Untuk dua polinomial berderajat d di atas: A(x) * B(x) – C(x) dan F(x) * H(x), jika tidak sama, keduanya hanya akan paling banyak titik d Berpotongan, yaitu solusi pada titik d adalah sama.
Setelah menyelesaikan konversi polinomial, kita akan memasuki tahap pembuktian polinomial.
Buktikan polinomial berlaku
Demi ilustrasi, kami menggunakan polinomial P(x) = F(x) * H(x).
Sekarang, masalah yang ingin dibuktikan oleh pembukti adalah: pada semua x, P(x) = F(x) *H(x).
Proses verifikasi polinomial di atas oleh pembukti dan pemverifikasi adalah sebagai berikut:
Namun jika kita pikirkan baik-baik, kita akan menemukan bahwa ada beberapa masalah dalam proses di atas:
Untuk mengatasi masalah di atas, kami melakukan optimasi berikut:
Setelah pengoptimalan, kami menemukan bahwa sistem bukti masih membutuhkan interaksi antara pemverifikasi dan pembukti.Bagaimana kita dapat mencapai non-interaksi?
Terapkan non-interaktif
**Untuk mencapai non-interaksi, SNARK memperkenalkan pengaturan tepercaya (Pengaturan). **
Dengan kata lain, sebelum dimulainya pembuktian, hak verifikator untuk memilih poin tantangan acak diserahkan kepada pihak ketiga yang terpercaya.Setelah pihak ketiga memilih parameter acak λ, ia menempatkan λ terenkripsi di sirkuit R1CS. Dalam hal ini cara, CRS (Common Reference String, string referensi publik) dihasilkan. Verifikator dapat memperoleh Sv-nya sendiri dari CRS, dan verifikator dapat memperoleh Sp-nya sendiri dari CRS.
Perlu dicatat bahwa λ perlu dihancurkan setelah menghasilkan Sv dan Sp. Jika λ bocor, mungkin digunakan untuk memalsukan transaksi melalui verifikasi palsu.
Alur Kerja zk-SNARK
Setelah memahami proses konstruksi SNARK, berdasarkan rangkaian aritmatika yang dapat menghasilkan bukti, proses pembuktian zk-SNARK adalah sebagai berikut:
Melalui sirkuit C dan parameter acak λ, dihasilkan parameter acak Sv dan Sp yang digunakan oleh pembukti dan pemverifikasi berikutnya.
Prover menghitung bukti Π melalui parameter acak Sp, input publik x, dan input rahasia w.
Pemverifikasi memverifikasi apakah C(x,w)=0 ada melalui parameter acak Sv, input publik x, dan bukti Π. Pada saat yang sama, verifikasi apakah pembuktian dihitung dengan rangkaian C atau tidak.
Pada titik ini, kami telah menyelesaikan penjelasan dari keseluruhan zk-SNARK Mari kita lihat kasus aplikasi yang sebenarnya.
Kasus: Ambil zk Rollup dari Scroll sebagai contoh
Peran sistem pembuktian adalah untuk memungkinkan pembukti meyakinkan pemverifikasi untuk mempercayai satu hal;
Untuk sistem pembuktian zk adalah untuk membuat verifikator percaya bahwa Bukti Nol Pengetahuan (zero knowledge proof) yang dihitung oleh algoritma zk adalah benar.
Kami menggunakan Scroll zk Rollup sebagai contoh untuk mengilustrasikan pengoperasian sistem bukti zk.
Rollup mengacu pada perhitungan off-chain dan verifikasi on-chain. Untuk zk Rollup, setelah transaksi dieksekusi off-chain, pembukti perlu membuat sertifikat zk untuk root negara baru yang dihasilkan setelah transaksi dieksekusi, dan kemudian meneruskan sertifikat ke kontrak L1 Rollup untuk verifikasi on-chain.
Perlu dicatat bahwa ada dua jenis blok di zk Rollup:
Berikut ini adalah alur kerja Scroll zk Rollup:
Seperti dapat dilihat dari proses di atas, Roller adalah pembukti dalam sistem, dan kontrak Rollup adalah pemverifikasi. Roller menghasilkan bukti zk untuk transaksi yang dieksekusi secara off-chain; kontrak Rollup memverifikasi bukti tersebut, dan jika verifikasi lolos, kontrak Rollup akan langsung mengadopsi root status yang dikirimkan sebagai root status barunya.