Aplikasi dan Pengembangan Teknologi zk-SNARKs di Bidang Blockchain
Ringkasan
Teknologi zero-knowledge proof (ZKP) secara luas dianggap sebagai salah satu inovasi terpenting di bidang blockchain. Artikel ini memberikan tinjauan sistematis terhadap literatur sejarah ZKP selama hampir empat puluh tahun dan penelitian terbaru.
Pertama-tama memperkenalkan konsep dasar ZKP dan latar belakang sejarahnya. Kemudian fokus menganalisis teknologi ZKP berbasis sirkuit, termasuk desain, aplikasi, dan metode optimasi model seperti zkSNARK, Ben-Sasson, Pinocchio, Bulletproofs, dan Ligero. Dalam bidang lingkungan komputasi, artikel ini memperkenalkan ZKVM dan ZKEVM, membahas bagaimana keduanya meningkatkan kemampuan pemrosesan transaksi, melindungi privasi, dan meningkatkan efisiensi verifikasi. Artikel ini juga memperkenalkan mekanisme kerja dan metode optimasi ZK Rollup sebagai solusi perluasan Layer 2, serta kemajuan terbaru dalam percepatan perangkat keras, solusi campuran, dan ZK EVM khusus.
Akhirnya, artikel ini mengulas konsep-konsep baru seperti ZKCoprocessor, ZKML, ZKThreads, ZK Sharding, dan ZK StateChannels, serta membahas potensi mereka dalam hal skalabilitas, interoperabilitas, dan perlindungan privasi di Blockchain.
Dengan menganalisis teknologi terbaru dan tren perkembangan ini, artikel ini memberikan perspektif yang komprehensif untuk memahami dan menerapkan teknologi ZKP, menunjukkan potensi besar dalam meningkatkan efisiensi dan keamanan sistem Blockchain, serta memberikan referensi penting untuk keputusan investasi di masa depan.
Daftar Isi
Pendahuluan
Satu, Pengetahuan Dasar zk-SNARKs
Ringkasan
Contoh zk-SNARKs
Dua, zk-SNARKs non-interaktif
Latar Belakang
Usulan NIZK
Transformasi Fiat-Shamir
Jens Groth dan penelitiannya
Penelitian Lain
Tiga, zk-SNARKs berbasis sirkuit
Latar belakang
Konsep dan Karakteristik Dasar Model Rangkaian
Desain dan Aplikasi Sirkuit dalam zk-SNARKs
Potensi Kekurangan dan Tantangan
Empat, zk-SNARKs model
Latar Belakang
Model algoritma umum
Skema berbasis PCP linier dan masalah logaritma diskrit
Skema berbasis bukti orang biasa
Pengetahuan nol berbasis bukti yang dapat diverifikasi secara probabilistik (PCP)
Klasifikasi tahap pengaturan berbasis CPC
Lima, Gambaran dan Perkembangan zk-SNARKs Virtual Machine
Latar Belakang
Klasifikasi ZKVM yang ada
Paradigma Frontend dan Backend
Kelebihan dan Kekurangan Paradigma ZKVM
Enam, Gambaran Umum dan Perkembangan zk-SNARKs di Ethereum Virtual Machine
Latar Belakang
Cara kerja ZKEVM
Proses implementasi ZKEVM
Ciri-ciri ZKEVM
Tujuh, Ringkasan dan Pengembangan Solusi Jaringan Lapisan Dua zk-SNARKs
Latar Belakang
Mekanisme kerja ZK Rollup
Kekurangan dan Optimasi ZK Rollup
Delapan, arah pengembangan masa depan zk-SNARKs
Mempercepat pengembangan lingkungan komputasi
Usulan dan perkembangan ZKML
Perkembangan teknologi skalabilitas ZKP
Perkembangan interoperabilitas ZKP
Kesembilan, kesimpulan
Referensi
Pendahuluan
Internet sedang memasuki era Web3, dan perkembangan aplikasi Blockchain berlangsung cepat. Dalam beberapa tahun terakhir, platform Blockchain menampung aktivitas jutaan pengguna setiap hari, memproses puluhan milyar transaksi. Data besar yang dihasilkan dari transaksi ini biasanya mencakup informasi pribadi sensitif seperti identitas pengguna, jumlah transaksi, alamat akun, dan saldo akun. Mengingat karakteristik keterbukaan dan transparansi Blockchain, data yang disimpan ini terbuka untuk semua orang, sehingga memicu berbagai masalah keamanan dan privasi.
Saat ini, ada beberapa teknologi kriptografi yang dapat mengatasi tantangan ini, termasuk enkripsi homomorfik, tanda tangan cincin, komputasi multi-pihak yang aman, dan zk-SNARKs. Enkripsi homomorfik memungkinkan operasi dilakukan tanpa mendekripsi ciphertext, membantu melindungi keamanan saldo akun dan jumlah transaksi, tetapi tidak dapat melindungi keamanan alamat akun. Tanda tangan cincin menyediakan bentuk tanda tangan digital yang khusus, mampu menyembunyikan identitas penandatangan, sehingga melindungi keamanan alamat akun, tetapi tidak dapat melindungi saldo akun dan jumlah transaksi. Komputasi multi-pihak yang aman memungkinkan pembagian tugas komputasi di antara beberapa peserta, tanpa peserta mana pun mengetahui data peserta lainnya, secara efektif melindungi keamanan saldo akun dan jumlah transaksi, tetapi juga tidak dapat melindungi keamanan alamat akun. Selain itu, enkripsi homomorfik, tanda tangan cincin, dan komputasi multi-pihak yang aman tidak dapat digunakan untuk memverifikasi apakah pembuktian memiliki jumlah transaksi yang cukup tanpa mengungkapkan jumlah transaksi, alamat akun, dan saldo akun.
zk-SNARKs adalah solusi yang lebih komprehensif, protokol verifikasi ini memungkinkan verifikasi kebenaran proposisi tertentu tanpa mengungkapkan data perantara apapun. Protokol ini tidak memerlukan infrastruktur kunci publik yang rumit, dan implementasi ulang tidak memberikan kesempatan bagi pengguna jahat untuk mendapatkan informasi berguna tambahan. Melalui ZKP, verifier dapat memverifikasi apakah prover memiliki jumlah transaksi yang cukup tanpa mengungkapkan data transaksi pribadi apapun. Proses verifikasi mencakup generasi bukti yang mencakup jumlah transaksi yang diklaim oleh prover, kemudian bukti tersebut disampaikan kepada verifier, verifier melakukan perhitungan yang telah ditentukan sebelumnya atas bukti tersebut, dan menghasilkan hasil perhitungan akhir, sehingga dapat meny得出 kesimpulan apakah menerima pernyataan prover. Jika pernyataan prover diterima, itu berarti mereka memiliki jumlah transaksi yang cukup. Proses verifikasi di atas dapat dicatat di Blockchain, tanpa adanya pemalsuan.
Fitur ZKP ini menjadikannya peran inti dalam transaksi Blockchain dan aplikasi cryptocurrency, terutama dalam perlindungan privasi dan perluasan jaringan, sehingga tidak hanya menjadi fokus penelitian akademis, tetapi juga secara luas dianggap sebagai salah satu inovasi teknologi terpenting sejak implementasi sukses teknologi buku besar terdistribusi. Selain itu, ini juga merupakan jalur utama untuk aplikasi industri dan investasi ventura.
Dengan demikian, banyak proyek jaringan berbasis ZKP muncul, seperti ZkSync, StarkNet, Mina, Filecoin, dan Aleo. Seiring dengan perkembangan proyek-proyek ini, inovasi algoritma terkait ZKP terus bermunculan, dilaporkan hampir setiap minggu ada algoritma baru yang diperkenalkan. Selain itu, pengembangan perangkat keras yang terkait dengan teknologi ZKP juga berkembang pesat, termasuk chip yang dioptimalkan khusus untuk ZKP. Misalnya, proyek seperti Ingonyama, Irreducible, dan Cysic telah menyelesaikan penggalangan dana besar-besaran, perkembangan ini tidak hanya menunjukkan kemajuan cepat teknologi ZKP, tetapi juga mencerminkan pergeseran dari perangkat keras umum menuju perangkat keras khusus seperti GPU, FPGA, dan ASIC.
Kemajuan ini menunjukkan bahwa teknologi zk-SNARKs bukan hanya merupakan terobosan penting di bidang kriptografi, tetapi juga merupakan kekuatan pendorong kunci untuk mewujudkan aplikasi teknologi Blockchain yang lebih luas.
Oleh karena itu, kami memutuskan untuk secara sistematis mengatur pengetahuan terkait zk-SNARKs, untuk lebih baik membantu kami dalam membuat keputusan investasi di masa depan. Untuk itu, kami telah meninjau secara komprehensif makalah akademis inti tentang ZKP; pada saat yang sama, kami juga menganalisis secara rinci informasi dan buku putih dari proyek-proyek terkemuka di bidang ini. Pengumpulan dan analisis data yang komprehensif ini memberikan dasar yang kokoh untuk penulisan artikel ini.
I. Pengetahuan Dasar tentang zk-SNARKs
1. Ringkasan
Pada tahun 1985, para akademisi Goldwasser, Micali, dan Rackoff pertama kali mengemukakan zk-SNARKs dan bukti interaktif dalam makalah "The Knowledge Complexity of Interactive Proof-Systems". Makalah ini adalah dasar dari zk-SNARKs, mendefinisikan banyak konsep yang mempengaruhi penelitian akademis selanjutnya. Misalnya, definisi pengetahuan adalah "output yang tidak dapat dihitung", yaitu pengetahuan harus merupakan output, dan merupakan perhitungan yang tidak dapat dilakukan, yang berarti ia tidak bisa berupa fungsi sederhana, melainkan harus merupakan fungsi yang kompleks. Perhitungan yang tidak dapat dilakukan biasanya dapat dipahami sebagai masalah NP, yaitu masalah yang solusi kebenarannya dapat diverifikasi dalam waktu polinomial, di mana waktu polinomial mengacu pada waktu eksekusi algoritme yang dapat dinyatakan dengan fungsi polinomial dari ukuran input. Ini adalah standar penting dalam ilmu komputer untuk mengukur efisiensi dan kelayakan algoritme. Karena proses penyelesaian masalah NP yang kompleks, maka dianggap sebagai perhitungan yang tidak dapat dilakukan; tetapi proses verifikasinya relatif sederhana, sehingga sangat cocok digunakan untuk verifikasi zk-SNARKs.
Salah satu contoh klasik dari masalah NP adalah masalah penjual keliling, di mana kita perlu menemukan jalur terpendek yang mengunjungi serangkaian kota dan kembali ke titik awal. Meskipun menemukan jalur terpendek mungkin sulit, memverifikasi apakah jalur tertentu adalah yang terpendek relatif mudah. Karena verifikasi total jarak dari jalur tertentu dapat diselesaikan dalam waktu polinomial.
Goldwasser dan rekan-rekannya memperkenalkan konsep "kompleksitas pengetahuan" dalam makalah mereka, untuk mengukur jumlah pengetahuan yang bocor dari pembuktian kepada verifier dalam sistem pembuktian interaktif. Mereka juga mengusulkan sistem pembuktian interaktif, di mana pembuktian dan verifier berinteraksi dalam beberapa putaran untuk membuktikan kebenaran suatu pernyataan.
Secara keseluruhan, definisi zk-SNARKs yang dirangkum oleh Goldwasser dan yang lainnya adalah jenis bukti interaktif khusus, di mana verifier tidak akan mendapatkan informasi tambahan selain kebenaran pernyataan selama proses verifikasi; dan diajukan tiga karakteristik dasar termasuk:
1.Kelengkapan: Jika argumen itu benar, pembuktian yang jujur dapat meyakinkan verifikator yang jujur tentang fakta ini;
2.Keandalan: Jika pembuktian tidak mengetahui isi pernyataan, ia hanya dapat menipu pemeriksa dengan probabilitas yang sangat kecil;
Sifat nol pengetahuan: Setelah proses pembuktian selesai, verifier hanya mendapatkan informasi "pembuktian memiliki pengetahuan ini", tanpa dapat memperoleh konten tambahan apa pun.
2.zk-SNARKs contoh
Untuk lebih memahami zk-SNARKs dan atributnya, berikut adalah contoh untuk memverifikasi apakah seorang pembuktian memiliki informasi pribadi tertentu, yang dibagi menjadi tiga tahap: persiapan, tantangan, dan respons.
Langkah pertama: Atur
Pada langkah ini, tujuan pembuktian adalah untuk membuat sebuah bukti bahwa dia mengetahui suatu angka rahasia s, tetapi tidak langsung menampilkan s. Tetapkan angka rahasia;
Pilih dua bilangan prima besar p dan q, hitung hasil kali mereka. Tentukan jumlah bilangan prima, hitung hasil yang didapat;
Perhitungan, di sini, v sebagai bagian dari bukti dikirim ke verifier, tetapi itu tidak cukup untuk memungkinkan verifier atau pengamat mana pun menyimpulkan s.
Pilih secara acak sebuah bilangan bulat r, hitung dan kirimkan kepada verifier. Nilai x ini digunakan dalam proses verifikasi selanjutnya, namun juga tidak mengekspos s. Misalkan bilangan bulat acak, hitungan yang diperoleh.
Langkah kedua: Tantangan
Validator secara acak memilih satu bit a( yang bisa berupa 0 atau 1), kemudian mengirimkannya kepada prover. "Tantangan" ini menentukan langkah-langkah yang perlu diambil oleh prover selanjutnya.
Langkah ketiga: Tanggapan
Berdasarkan nilai a yang dikeluarkan oleh validator, prover memberikan respons:
Jika, penjamin mengirim ( di sini r adalah angka yang dia pilih secara acak sebelumnya ).
Jika, penyetor menghitung dan mengirim. Misalkan bit acak yang dikirim oleh verifier, berdasarkan nilai a, penyetor menghitung;
Akhirnya, validator memverifikasi apakah g yang diterima sama. Jika persamaan terpenuhi, validator menerima bukti ini. Pada saat itu, validator menghitung verifikasi, verifikasi sisi kanan; Pada saat itu, validator menghitung verifikasi, verifikasi sisi kanan.
Di sini, kita melihat bahwa bukti yang dihitung oleh validator menunjukkan bahwa pembuktian berhasil melewati proses verifikasi, sambil tidak mengungkapkan angka rahasia s miliknya. Di sini, karena a hanya dapat mengambil 0 atau 1, hanya ada dua kemungkinan, probabilitas pembuktian untuk berhasil melewati verifikasi berdasarkan keberuntungan adalah ( ketika a mengambil 0 ). Namun, validator kemudian menantang pembuktian lagi, pembuktian terus-menerus mengganti angka terkait dan menyerahkannya kepada validator, dan selalu berhasil melewati proses verifikasi. Dengan cara ini, probabilitas pembuktian untuk berhasil melewati verifikasi berdasarkan keberuntungan mendekati 0(, dan kesimpulan bahwa pembuktian memang mengetahui angka rahasia s terbukti. Contoh ini membuktikan integritas, keandalan, dan sifat nol pengetahuan dari sistem zk-SNARKs.
Dua, zk-SNARKs non-interaktif
) 1. Latar Belakang
zk-SNARKs dalam konsep tradisional biasanya berupa bentuk protokol interaktif dan online; misalnya, protokol Sigma biasanya memerlukan tiga hingga lima putaran interaksi untuk menyelesaikan otentikasi. Namun, dalam skenario seperti transaksi instan atau pemungutan suara, sering kali tidak ada kesempatan untuk melakukan interaksi berulang kali, terutama dalam aplikasi teknologi Blockchain, fungsi verifikasi offline menjadi sangat penting.
2.Penawaran NIZK
Pada tahun 1988, Blum, Feldman, dan Micali pertama kali mengusulkan konsep zk-SNARKs, membuktikan bahwa tanpa interaksi multi-putaran, penjamin dan verifier masih dapat menyelesaikan proses otentikasi. Terobosan ini membuat transaksi instan, pemungutan suara, dan aplikasi Blockchain menjadi mungkin.
Mereka mengajukan bahwa zk-SNARKs non-interaktif dapat dibagi menjadi tiga tahap:
Pengaturan
Menghitung
Verifikasi
Mengatur fase menggunakan fungsi komputasi, mengubah parameter keamanan menjadi pengetahuan publik, biasanya dikodekan dalam string referensi bersama. Ini adalah cara untuk menghitung bukti dan memvalidasinya dengan parameter dan algoritma yang benar.
Fase perhitungan menggunakan fungsi perhitungan, kunci input dan bukti, dan menghasilkan hasil perhitungan serta bukti.
Pada tahap verifikasi, validitas bukti diverifikasi melalui kunci verifikasi.
Model string referensi publik yang mereka ajukan, yaitu berdasarkan semua peserta yang berbagi satu kata
Halaman ini mungkin berisi konten pihak ketiga, yang disediakan untuk tujuan informasi saja (bukan pernyataan/jaminan) dan tidak boleh dianggap sebagai dukungan terhadap pandangannya oleh Gate, atau sebagai nasihat keuangan atau profesional. Lihat Penafian untuk detailnya.
Teknologi zk-SNARKs merevolusi Blockchain: kemajuan menyeluruh dari Algoritme hingga perangkat keras
Aplikasi dan Pengembangan Teknologi zk-SNARKs di Bidang Blockchain
Ringkasan
Teknologi zero-knowledge proof (ZKP) secara luas dianggap sebagai salah satu inovasi terpenting di bidang blockchain. Artikel ini memberikan tinjauan sistematis terhadap literatur sejarah ZKP selama hampir empat puluh tahun dan penelitian terbaru.
Pertama-tama memperkenalkan konsep dasar ZKP dan latar belakang sejarahnya. Kemudian fokus menganalisis teknologi ZKP berbasis sirkuit, termasuk desain, aplikasi, dan metode optimasi model seperti zkSNARK, Ben-Sasson, Pinocchio, Bulletproofs, dan Ligero. Dalam bidang lingkungan komputasi, artikel ini memperkenalkan ZKVM dan ZKEVM, membahas bagaimana keduanya meningkatkan kemampuan pemrosesan transaksi, melindungi privasi, dan meningkatkan efisiensi verifikasi. Artikel ini juga memperkenalkan mekanisme kerja dan metode optimasi ZK Rollup sebagai solusi perluasan Layer 2, serta kemajuan terbaru dalam percepatan perangkat keras, solusi campuran, dan ZK EVM khusus.
Akhirnya, artikel ini mengulas konsep-konsep baru seperti ZKCoprocessor, ZKML, ZKThreads, ZK Sharding, dan ZK StateChannels, serta membahas potensi mereka dalam hal skalabilitas, interoperabilitas, dan perlindungan privasi di Blockchain.
Dengan menganalisis teknologi terbaru dan tren perkembangan ini, artikel ini memberikan perspektif yang komprehensif untuk memahami dan menerapkan teknologi ZKP, menunjukkan potensi besar dalam meningkatkan efisiensi dan keamanan sistem Blockchain, serta memberikan referensi penting untuk keputusan investasi di masa depan.
Daftar Isi
Pendahuluan
Satu, Pengetahuan Dasar zk-SNARKs
Dua, zk-SNARKs non-interaktif
Tiga, zk-SNARKs berbasis sirkuit
Empat, zk-SNARKs model
Lima, Gambaran dan Perkembangan zk-SNARKs Virtual Machine
Enam, Gambaran Umum dan Perkembangan zk-SNARKs di Ethereum Virtual Machine
Tujuh, Ringkasan dan Pengembangan Solusi Jaringan Lapisan Dua zk-SNARKs
Delapan, arah pengembangan masa depan zk-SNARKs
Kesembilan, kesimpulan
Referensi
Pendahuluan
Internet sedang memasuki era Web3, dan perkembangan aplikasi Blockchain berlangsung cepat. Dalam beberapa tahun terakhir, platform Blockchain menampung aktivitas jutaan pengguna setiap hari, memproses puluhan milyar transaksi. Data besar yang dihasilkan dari transaksi ini biasanya mencakup informasi pribadi sensitif seperti identitas pengguna, jumlah transaksi, alamat akun, dan saldo akun. Mengingat karakteristik keterbukaan dan transparansi Blockchain, data yang disimpan ini terbuka untuk semua orang, sehingga memicu berbagai masalah keamanan dan privasi.
Saat ini, ada beberapa teknologi kriptografi yang dapat mengatasi tantangan ini, termasuk enkripsi homomorfik, tanda tangan cincin, komputasi multi-pihak yang aman, dan zk-SNARKs. Enkripsi homomorfik memungkinkan operasi dilakukan tanpa mendekripsi ciphertext, membantu melindungi keamanan saldo akun dan jumlah transaksi, tetapi tidak dapat melindungi keamanan alamat akun. Tanda tangan cincin menyediakan bentuk tanda tangan digital yang khusus, mampu menyembunyikan identitas penandatangan, sehingga melindungi keamanan alamat akun, tetapi tidak dapat melindungi saldo akun dan jumlah transaksi. Komputasi multi-pihak yang aman memungkinkan pembagian tugas komputasi di antara beberapa peserta, tanpa peserta mana pun mengetahui data peserta lainnya, secara efektif melindungi keamanan saldo akun dan jumlah transaksi, tetapi juga tidak dapat melindungi keamanan alamat akun. Selain itu, enkripsi homomorfik, tanda tangan cincin, dan komputasi multi-pihak yang aman tidak dapat digunakan untuk memverifikasi apakah pembuktian memiliki jumlah transaksi yang cukup tanpa mengungkapkan jumlah transaksi, alamat akun, dan saldo akun.
zk-SNARKs adalah solusi yang lebih komprehensif, protokol verifikasi ini memungkinkan verifikasi kebenaran proposisi tertentu tanpa mengungkapkan data perantara apapun. Protokol ini tidak memerlukan infrastruktur kunci publik yang rumit, dan implementasi ulang tidak memberikan kesempatan bagi pengguna jahat untuk mendapatkan informasi berguna tambahan. Melalui ZKP, verifier dapat memverifikasi apakah prover memiliki jumlah transaksi yang cukup tanpa mengungkapkan data transaksi pribadi apapun. Proses verifikasi mencakup generasi bukti yang mencakup jumlah transaksi yang diklaim oleh prover, kemudian bukti tersebut disampaikan kepada verifier, verifier melakukan perhitungan yang telah ditentukan sebelumnya atas bukti tersebut, dan menghasilkan hasil perhitungan akhir, sehingga dapat meny得出 kesimpulan apakah menerima pernyataan prover. Jika pernyataan prover diterima, itu berarti mereka memiliki jumlah transaksi yang cukup. Proses verifikasi di atas dapat dicatat di Blockchain, tanpa adanya pemalsuan.
Fitur ZKP ini menjadikannya peran inti dalam transaksi Blockchain dan aplikasi cryptocurrency, terutama dalam perlindungan privasi dan perluasan jaringan, sehingga tidak hanya menjadi fokus penelitian akademis, tetapi juga secara luas dianggap sebagai salah satu inovasi teknologi terpenting sejak implementasi sukses teknologi buku besar terdistribusi. Selain itu, ini juga merupakan jalur utama untuk aplikasi industri dan investasi ventura.
Dengan demikian, banyak proyek jaringan berbasis ZKP muncul, seperti ZkSync, StarkNet, Mina, Filecoin, dan Aleo. Seiring dengan perkembangan proyek-proyek ini, inovasi algoritma terkait ZKP terus bermunculan, dilaporkan hampir setiap minggu ada algoritma baru yang diperkenalkan. Selain itu, pengembangan perangkat keras yang terkait dengan teknologi ZKP juga berkembang pesat, termasuk chip yang dioptimalkan khusus untuk ZKP. Misalnya, proyek seperti Ingonyama, Irreducible, dan Cysic telah menyelesaikan penggalangan dana besar-besaran, perkembangan ini tidak hanya menunjukkan kemajuan cepat teknologi ZKP, tetapi juga mencerminkan pergeseran dari perangkat keras umum menuju perangkat keras khusus seperti GPU, FPGA, dan ASIC.
Kemajuan ini menunjukkan bahwa teknologi zk-SNARKs bukan hanya merupakan terobosan penting di bidang kriptografi, tetapi juga merupakan kekuatan pendorong kunci untuk mewujudkan aplikasi teknologi Blockchain yang lebih luas.
Oleh karena itu, kami memutuskan untuk secara sistematis mengatur pengetahuan terkait zk-SNARKs, untuk lebih baik membantu kami dalam membuat keputusan investasi di masa depan. Untuk itu, kami telah meninjau secara komprehensif makalah akademis inti tentang ZKP; pada saat yang sama, kami juga menganalisis secara rinci informasi dan buku putih dari proyek-proyek terkemuka di bidang ini. Pengumpulan dan analisis data yang komprehensif ini memberikan dasar yang kokoh untuk penulisan artikel ini.
I. Pengetahuan Dasar tentang zk-SNARKs
1. Ringkasan
Pada tahun 1985, para akademisi Goldwasser, Micali, dan Rackoff pertama kali mengemukakan zk-SNARKs dan bukti interaktif dalam makalah "The Knowledge Complexity of Interactive Proof-Systems". Makalah ini adalah dasar dari zk-SNARKs, mendefinisikan banyak konsep yang mempengaruhi penelitian akademis selanjutnya. Misalnya, definisi pengetahuan adalah "output yang tidak dapat dihitung", yaitu pengetahuan harus merupakan output, dan merupakan perhitungan yang tidak dapat dilakukan, yang berarti ia tidak bisa berupa fungsi sederhana, melainkan harus merupakan fungsi yang kompleks. Perhitungan yang tidak dapat dilakukan biasanya dapat dipahami sebagai masalah NP, yaitu masalah yang solusi kebenarannya dapat diverifikasi dalam waktu polinomial, di mana waktu polinomial mengacu pada waktu eksekusi algoritme yang dapat dinyatakan dengan fungsi polinomial dari ukuran input. Ini adalah standar penting dalam ilmu komputer untuk mengukur efisiensi dan kelayakan algoritme. Karena proses penyelesaian masalah NP yang kompleks, maka dianggap sebagai perhitungan yang tidak dapat dilakukan; tetapi proses verifikasinya relatif sederhana, sehingga sangat cocok digunakan untuk verifikasi zk-SNARKs.
Salah satu contoh klasik dari masalah NP adalah masalah penjual keliling, di mana kita perlu menemukan jalur terpendek yang mengunjungi serangkaian kota dan kembali ke titik awal. Meskipun menemukan jalur terpendek mungkin sulit, memverifikasi apakah jalur tertentu adalah yang terpendek relatif mudah. Karena verifikasi total jarak dari jalur tertentu dapat diselesaikan dalam waktu polinomial.
Goldwasser dan rekan-rekannya memperkenalkan konsep "kompleksitas pengetahuan" dalam makalah mereka, untuk mengukur jumlah pengetahuan yang bocor dari pembuktian kepada verifier dalam sistem pembuktian interaktif. Mereka juga mengusulkan sistem pembuktian interaktif, di mana pembuktian dan verifier berinteraksi dalam beberapa putaran untuk membuktikan kebenaran suatu pernyataan.
Secara keseluruhan, definisi zk-SNARKs yang dirangkum oleh Goldwasser dan yang lainnya adalah jenis bukti interaktif khusus, di mana verifier tidak akan mendapatkan informasi tambahan selain kebenaran pernyataan selama proses verifikasi; dan diajukan tiga karakteristik dasar termasuk:
1.Kelengkapan: Jika argumen itu benar, pembuktian yang jujur dapat meyakinkan verifikator yang jujur tentang fakta ini;
2.Keandalan: Jika pembuktian tidak mengetahui isi pernyataan, ia hanya dapat menipu pemeriksa dengan probabilitas yang sangat kecil;
2.zk-SNARKs contoh
Untuk lebih memahami zk-SNARKs dan atributnya, berikut adalah contoh untuk memverifikasi apakah seorang pembuktian memiliki informasi pribadi tertentu, yang dibagi menjadi tiga tahap: persiapan, tantangan, dan respons.
Langkah pertama: Atur
Pada langkah ini, tujuan pembuktian adalah untuk membuat sebuah bukti bahwa dia mengetahui suatu angka rahasia s, tetapi tidak langsung menampilkan s. Tetapkan angka rahasia;
Pilih dua bilangan prima besar p dan q, hitung hasil kali mereka. Tentukan jumlah bilangan prima, hitung hasil yang didapat;
Perhitungan, di sini, v sebagai bagian dari bukti dikirim ke verifier, tetapi itu tidak cukup untuk memungkinkan verifier atau pengamat mana pun menyimpulkan s.
Pilih secara acak sebuah bilangan bulat r, hitung dan kirimkan kepada verifier. Nilai x ini digunakan dalam proses verifikasi selanjutnya, namun juga tidak mengekspos s. Misalkan bilangan bulat acak, hitungan yang diperoleh.
Langkah kedua: Tantangan
Validator secara acak memilih satu bit a( yang bisa berupa 0 atau 1), kemudian mengirimkannya kepada prover. "Tantangan" ini menentukan langkah-langkah yang perlu diambil oleh prover selanjutnya.
Langkah ketiga: Tanggapan
Berdasarkan nilai a yang dikeluarkan oleh validator, prover memberikan respons:
Jika, penjamin mengirim ( di sini r adalah angka yang dia pilih secara acak sebelumnya ).
Jika, penyetor menghitung dan mengirim. Misalkan bit acak yang dikirim oleh verifier, berdasarkan nilai a, penyetor menghitung;
Akhirnya, validator memverifikasi apakah g yang diterima sama. Jika persamaan terpenuhi, validator menerima bukti ini. Pada saat itu, validator menghitung verifikasi, verifikasi sisi kanan; Pada saat itu, validator menghitung verifikasi, verifikasi sisi kanan.
Di sini, kita melihat bahwa bukti yang dihitung oleh validator menunjukkan bahwa pembuktian berhasil melewati proses verifikasi, sambil tidak mengungkapkan angka rahasia s miliknya. Di sini, karena a hanya dapat mengambil 0 atau 1, hanya ada dua kemungkinan, probabilitas pembuktian untuk berhasil melewati verifikasi berdasarkan keberuntungan adalah ( ketika a mengambil 0 ). Namun, validator kemudian menantang pembuktian lagi, pembuktian terus-menerus mengganti angka terkait dan menyerahkannya kepada validator, dan selalu berhasil melewati proses verifikasi. Dengan cara ini, probabilitas pembuktian untuk berhasil melewati verifikasi berdasarkan keberuntungan mendekati 0(, dan kesimpulan bahwa pembuktian memang mengetahui angka rahasia s terbukti. Contoh ini membuktikan integritas, keandalan, dan sifat nol pengetahuan dari sistem zk-SNARKs.
Dua, zk-SNARKs non-interaktif
) 1. Latar Belakang
zk-SNARKs dalam konsep tradisional biasanya berupa bentuk protokol interaktif dan online; misalnya, protokol Sigma biasanya memerlukan tiga hingga lima putaran interaksi untuk menyelesaikan otentikasi. Namun, dalam skenario seperti transaksi instan atau pemungutan suara, sering kali tidak ada kesempatan untuk melakukan interaksi berulang kali, terutama dalam aplikasi teknologi Blockchain, fungsi verifikasi offline menjadi sangat penting.
2.Penawaran NIZK
Pada tahun 1988, Blum, Feldman, dan Micali pertama kali mengusulkan konsep zk-SNARKs, membuktikan bahwa tanpa interaksi multi-putaran, penjamin dan verifier masih dapat menyelesaikan proses otentikasi. Terobosan ini membuat transaksi instan, pemungutan suara, dan aplikasi Blockchain menjadi mungkin.
Mereka mengajukan bahwa zk-SNARKs non-interaktif dapat dibagi menjadi tiga tahap:
Mengatur fase menggunakan fungsi komputasi, mengubah parameter keamanan menjadi pengetahuan publik, biasanya dikodekan dalam string referensi bersama. Ini adalah cara untuk menghitung bukti dan memvalidasinya dengan parameter dan algoritma yang benar.
Fase perhitungan menggunakan fungsi perhitungan, kunci input dan bukti, dan menghasilkan hasil perhitungan serta bukti.
Pada tahap verifikasi, validitas bukti diverifikasi melalui kunci verifikasi.
Model string referensi publik yang mereka ajukan, yaitu berdasarkan semua peserta yang berbagi satu kata