Penerapan dan Pengembangan Teknologi zk-SNARKs di Bidang Blockchain
Ringkasan
zk-SNARKs(ZKP) teknologi dianggap sebagai salah satu inovasi terpenting di bidang Blockchain, dan juga merupakan fokus utama investasi ventura. Artikel ini memberikan tinjauan menyeluruh tentang perkembangan ZKP selama hampir empat puluh tahun dan kemajuan penelitian terbaru.
Pertama-tama diperkenalkan konsep dasar dan latar belakang sejarah ZKP, dengan fokus pada analisis teknologi ZKP berbasis sirkuit, termasuk desain, aplikasi, dan optimasi model seperti zkSNARK, Ben-Sasson, Pinocchio, Bulletproofs, dan Ligero. Dalam aspek lingkungan komputasi, dibahas bagaimana ZKVM dan ZKEVM meningkatkan kapasitas pemrosesan transaksi, melindungi privasi, dan meningkatkan efisiensi verifikasi. Artikel ini juga memperkenalkan mekanisme kerja dan metode optimasi ZK Rollup sebagai solusi ekspansi Layer 2, serta kemajuan terbaru dalam akselerasi perangkat keras, solusi hibrid, dan ZK EVM khusus.
Akhirnya, artikel ini melihat konsep-konsep baru seperti ZKCoprocessor, ZKML, ZKThreads, ZK Sharding, dan ZK StateChannels, serta membahas potensi mereka dalam skalabilitas Blockchain, interoperabilitas, dan perlindungan privasi.
Dengan menganalisis teknologi dan tren perkembangan ini, artikel ini memberikan perspektif 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, Dasar Pengetahuan zk-SNARKs
Ringkasan
Contoh zk-SNARKs
Dua, zk-SNARKs non-interaktif
Latar Belakang
Pengenalan NIZK
Transformasi Fiat-Shamir
Jens Groth dan penelitiannya
Penelitian Lain
Tiga, zk-SNARKs berbasis sirkuit
Latar Belakang
Konsep dan Ciri Dasar Model Sirkuit
Desain dan aplikasi sirkuit dalam zk-SNARKs
Potensi Kekurangan dan Tantangan
Empat, model zk-SNARKs
Latar Belakang
Model algoritma umum
Skema berbasis PCP linier dan masalah logaritma diskrit
Rencana berbasis bukti orang biasa
Bukti yang dapat diverifikasi berdasarkan probabilitas ( PCP ) zk-SNARKs
Klasifikasi tahap pengaturan konstruk umum bukti CPC( berdasarkan )
Lima, Gambaran dan Perkembangan zk-SNARKs Virtual Machine
Latar Belakang
Klasifikasi ZKVM yang ada
Paradigma Frontend dan Backend
Kelebihan dan Kekurangan Paradigma ZKVM
Enam, Ringkasan dan Perkembangan zk-SNARKs Ethereum Virtual Machine
Latar Belakang
Cara kerja ZKEVM
Proses implementasi ZKEVM
Karakteristik ZKEVM
Tujuh, Gambaran Umum dan Perkembangan Solusi Jaringan Layer Dua zk-SNARKs
Latar Belakang
Mekanisme kerja ZK Rollup
Kekurangan dan Optimasi ZK Rollup
Delapan, arah pengembangan masa depan zk-SNARKs
Mempercepat perkembangan lingkungan komputasi
Usulan dan Pengembangan ZKML
Perkembangan teknologi ekspansi ZKP
Perkembangan interoperabilitas ZKP
Kesembilan, Kesimpulan
Pendahuluan
Dengan munculnya era Web3, aplikasi Blockchain (DApps) berkembang pesat, dengan aplikasi baru muncul setiap hari. Dalam beberapa tahun terakhir, platform Blockchain menampung aktivitas jutaan pengguna setiap hari, memproses miliaran transaksi. Data besar yang dihasilkan dari transaksi ini biasanya mencakup informasi pribadi sensitif, seperti identitas pengguna, jumlah transaksi, alamat akun, dan saldo. Karena keterbukaan dan transparansi Blockchain, data yang disimpan ini terbuka untuk semua orang, sehingga memunculkan berbagai masalah keamanan dan privasi.
Saat ini, ada beberapa teknologi kripto 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 khusus yang dapat menyembunyikan identitas penandatangan, sehingga melindungi keamanan alamat akun, tetapi tidak dapat melindungi saldo akun dan jumlah transaksi. Komputasi multi-pihak yang aman memungkinkan distribusi 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, teknologi ini tidak dapat digunakan untuk memverifikasi apakah penagih di lingkungan blockchain memiliki jumlah transaksi yang cukup tanpa mengungkapkan jumlah transaksi, alamat akun, dan saldo akun.
zk-SNARKs(ZKP) adalah solusi yang lebih komprehensif, protokol verifikasi ini memungkinkan untuk memverifikasi kebenaran proposisi tertentu tanpa mengungkapkan data perantara apa pun. Protokol ini tidak memerlukan infrastruktur kunci publik yang rumit, dan penerapan ulangnya 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 mana pun. Proses verifikasi mencakup pembuatan bukti yang berisi jumlah transaksi yang diklaim oleh prover, kemudian bukti tersebut disampaikan kepada verifier, verifier melakukan perhitungan yang telah ditentukan sebelumnya pada bukti tersebut, dan menghasilkan hasil perhitungan akhir untuk menentukan 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 memainkan peran kunci 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 keberhasilan implementasi teknologi buku besar terdistribusi. Ini juga merupakan jalur utama untuk aplikasi industri dan investasi risiko.
Oleh karena itu, banyak proyek jaringan berbasis ZKP muncul, seperti ZkSync, StarkNet, Mina, Filecoin, dan Aleo. Seiring dengan perkembangan proyek-proyek ini, inovasi algoritma terkait ZKP bermunculan, dilaporkan hampir setiap minggu ada algoritma baru yang diluncurkan. Selain itu, pengembangan perangkat keras terkait teknologi ZKP juga berkembang pesat, termasuk chip yang dioptimalkan khusus untuk ZKP. Misalnya, beberapa proyek telah menyelesaikan penggalangan dana secara 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 pendorong kunci untuk penerapan teknologi Blockchain yang lebih luas, terutama dalam meningkatkan perlindungan privasi dan kapasitas pemrosesan.
Oleh karena itu, kami memutuskan untuk secara sistematis mengatur pengetahuan terkait zk-SNARKs ( ZKP ), untuk lebih baik mendukung kami dalam membuat keputusan investasi di masa depan. Untuk itu, kami telah meninjau secara komprehensif makalah akademis inti yang terkait dengan ZKP ( dan mengurutkannya berdasarkan relevansi dan jumlah kutipan ); pada saat yang sama, kami juga menganalisis secara rinci informasi dan whitepaper dari proyek-proyek terkemuka di bidang ini ( berdasarkan skala pendanaan mereka ). Pengumpulan dan analisis data yang komprehensif ini memberikan dasar yang kuat untuk penulisan artikel ini.
I. Dasar Pengetahuan zk-SNARKs
1. Ringkasan
Pada tahun 1985, para ilmuwan Goldwasser, Micali, dan Rackoff pertama kali mengajukan konsep zk-SNARKs dalam makalah berjudul "The Knowledge Complexity of Interactive Proof-Systems". Makalah ini merupakan karya dasar dari zk-SNARKs dan mendefinisikan banyak konsep yang mempengaruhi penelitian akademis selanjutnya. Misalnya, definisi pengetahuan adalah "output yang tidak dapat dihitung", yaitu pengetahuan harus merupakan sebuah output, dan merupakan suatu perhitungan yang tidak dapat dihitung, yang berarti itu tidak dapat berupa fungsi sederhana, tetapi harus berupa fungsi yang kompleks. Perhitungan yang tidak dapat dihitung biasanya dapat dipahami sebagai masalah NP, yaitu masalah yang solusi kebenarannya dapat diverifikasi dalam waktu polinomial, di mana waktu polinomial berarti waktu operasi algoritma dapat dinyatakan dengan fungsi polinomial dari ukuran input. Ini adalah standar penting dalam ilmu komputer untuk mengukur efisiensi dan kelayakan algoritma. Karena proses penyelesaian masalah NP yang kompleks, maka dianggap sebagai perhitungan yang tidak dapat dihitung; tetapi proses verifikasinya relatif sederhana, sehingga sangat cocok digunakan untuk verifikasi zk-SNARKs.
Salah satu contoh klasik dari masalah NP adalah masalah perjalanan salesman, di mana kita harus menemukan jalur terpendek untuk mengunjungi serangkaian kota dan kembali ke titik awal. Meskipun menemukan jalur terpendek mungkin sulit, memverifikasi apakah jalur yang diberikan adalah yang terpendek relatif mudah. Karena memverifikasi total jarak dari jalur tertentu dapat dilakukan dalam waktu polinomial.
Goldwasser dan kawan-kawan dalam makalah mereka memperkenalkan konsep "kompleksitas pengetahuan" untuk mengukur jumlah pengetahuan yang dibocorkan oleh pembuktian kepada pemeriksa dalam sistem pembuktian interaktif. Mereka juga mengusulkan sistem pembuktian interaktif (Interactive Proof Systems, IPS), di mana pembuktian (Prover) dan pemeriksa (Verifier) membuktikan kebenaran suatu pernyataan melalui interaksi berulang.
Secara keseluruhan, definisi zk-SNARKs yang dirangkum oleh Goldwasser dan rekan-rekan adalah suatu jenis bukti interaktif khusus, di mana verifier tidak akan memperoleh informasi tambahan selain dari kebenaran pernyataan selama proses verifikasi; dan mengajukan tiga karakteristik dasar termasuk:
Keterlengkapan: Jika argumen itu benar, pembuktian yang jujur dapat meyakinkan validator yang jujur akan fakta ini;
Keandalan: Jika pembuktian tidak mengetahui isi pernyataan, ia hanya dapat menipu verifier 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.
( 2. contoh zk-SNARKs
Untuk memahami zk-SNARKs dan atributnya dengan lebih baik, berikut adalah contoh untuk memverifikasi apakah pembuktian memiliki informasi pribadi tertentu, yang dibagi menjadi tiga tahap: pengaturan, tantangan, dan respons.
Langkah pertama: atur )Setup(
Pada langkah ini, tujuan pembuktian adalah untuk membuat sebuah bukti yang menunjukkan bahwa dia tahu angka rahasia s, tetapi tidak langsung menampilkan s. Misalkan angka rahasia s;
Pilih dua bilangan prima besar p dan q, hitung produk mereka n. Misalkan bilangan prima p dan q, hitung n yang diperoleh;
Hitung v=s^2 mod n, di sini, v sebagai bagian dari bukti dikirim kepada verifier, tetapi itu tidak cukup untuk memungkinkan verifier atau pengamat mana pun menyimpulkan s;
Pilih secara acak sebuah bilangan bulat r, hitung x=r^2 mod n dan kirimkan kepada verifier. Nilai x ini digunakan untuk proses verifikasi selanjutnya, tetapi juga tidak mengungkapkan s. Misalkan bilangan bulat acak r, hitung x yang diperoleh.
Langkah kedua: Tantangan )Challenge###
Validator secara acak memilih sebuah bit a( yang bisa berupa 0 atau 1), kemudian mengirimkannya kepada prover. "Tantangan" ini menentukan langkah yang perlu diambil oleh prover selanjutnya.
Langkah ketiga: Respon (Response)
Berdasarkan nilai a yang dikeluarkan oleh validator, penjamin memberikan respons:
Jika a=0, penjamin mengirim g=r( di mana r adalah angka acak yang dia pilih sebelumnya ).
Jika a=1, pembuktian menghitung g=rs mod n dan mengirimkannya. Misalkan bit acak a yang dikirim oleh verifier, berdasarkan nilai a, pembuktian menghitung g;
Terakhir, validator memverifikasi apakah g^2 mod n sama dengan xa^v mod n berdasarkan g yang diterima. Jika persamaan tersebut benar, validator menerima bukti ini. Ketika a=0, validator menghitung g^2 mod n, sisi kanan memverifikasi xa^v mod n=x; ketika a=1, validator menghitung g^2 mod n, sisi kanan memverifikasi xa^v mod n=xv.
Di sini, kita melihat g^2 mod n=xa^v mod n yang dihitung oleh validator menunjukkan bahwa pembuktian berhasil melewati proses verifikasi, tanpa mengungkapkan angka rahasia s. Di sini, karena a hanya bisa mengambil 0 atau 1, hanya ada dua kemungkinan, probabilitas pembuktian untuk berhasil melewati verifikasi berdasarkan keberuntungan adalah 1/2( ketika a mengambil 0 adalah ). Namun, validator kemudian menantang pembuktian k kali, pembuktian terus mengganti angka terkait, menyerahkan kepada validator, dan selalu berhasil melewati proses verifikasi, sehingga probabilitas pembuktian untuk berhasil melewati verifikasi berdasarkan keberuntungan adalah (1/2)^k( yang mendekati 0), kesimpulan bahwa pembuktian benar-benar mengetahui angka rahasia s mendapatkan pembuktian. Contoh ini membuktikan integritas, keandalan, dan sifat nol pengetahuan sistem bukti nol.
Dua, zk-SNARKs Non-interaktif
( 1. Latar Belakang
zk-SNARKs)ZKP( dalam konsep tradisional biasanya berupa bentuk protokol interaktif dan online; misalnya, protokol Sigma biasanya memerlukan tiga hingga lima putaran interaksi untuk menyelesaikan autentikasi. Namun, dalam skenario seperti transaksi instan atau pemungutan suara, sering kali tidak ada kesempatan untuk melakukan interaksi multi-putaran, terutama dalam aplikasi teknologi Blockchain, fungsi verifikasi offline menjadi sangat penting.
) 2. NIZK yang diusulkan
Pada tahun 1988, Blum, Feldman, dan Micali pertama kali mengajukan konsep bukti nol-pengetahuan non-interaktif ###NIZK(, membuktikan kemungkinan bahwa tanpa interaksi berulang, penunjuk )Prover### dan verifier (Verifier) masih dapat menyelesaikan proses otentikasi. Terobosan ini membuatnya demikian
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.
Analisis menyeluruh tentang teknologi zk-SNARKs dalam aplikasi Blockchain dan prospek masa depannya
Penerapan dan Pengembangan Teknologi zk-SNARKs di Bidang Blockchain
Ringkasan
zk-SNARKs(ZKP) teknologi dianggap sebagai salah satu inovasi terpenting di bidang Blockchain, dan juga merupakan fokus utama investasi ventura. Artikel ini memberikan tinjauan menyeluruh tentang perkembangan ZKP selama hampir empat puluh tahun dan kemajuan penelitian terbaru.
Pertama-tama diperkenalkan konsep dasar dan latar belakang sejarah ZKP, dengan fokus pada analisis teknologi ZKP berbasis sirkuit, termasuk desain, aplikasi, dan optimasi model seperti zkSNARK, Ben-Sasson, Pinocchio, Bulletproofs, dan Ligero. Dalam aspek lingkungan komputasi, dibahas bagaimana ZKVM dan ZKEVM meningkatkan kapasitas pemrosesan transaksi, melindungi privasi, dan meningkatkan efisiensi verifikasi. Artikel ini juga memperkenalkan mekanisme kerja dan metode optimasi ZK Rollup sebagai solusi ekspansi Layer 2, serta kemajuan terbaru dalam akselerasi perangkat keras, solusi hibrid, dan ZK EVM khusus.
Akhirnya, artikel ini melihat konsep-konsep baru seperti ZKCoprocessor, ZKML, ZKThreads, ZK Sharding, dan ZK StateChannels, serta membahas potensi mereka dalam skalabilitas Blockchain, interoperabilitas, dan perlindungan privasi.
Dengan menganalisis teknologi dan tren perkembangan ini, artikel ini memberikan perspektif 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, Dasar Pengetahuan zk-SNARKs
Dua, zk-SNARKs non-interaktif
Tiga, zk-SNARKs berbasis sirkuit
Empat, model zk-SNARKs
Lima, Gambaran dan Perkembangan zk-SNARKs Virtual Machine
Enam, Ringkasan dan Perkembangan zk-SNARKs Ethereum Virtual Machine
Tujuh, Gambaran Umum dan Perkembangan Solusi Jaringan Layer Dua zk-SNARKs
Delapan, arah pengembangan masa depan zk-SNARKs
Kesembilan, Kesimpulan
Pendahuluan
Dengan munculnya era Web3, aplikasi Blockchain (DApps) berkembang pesat, dengan aplikasi baru muncul setiap hari. Dalam beberapa tahun terakhir, platform Blockchain menampung aktivitas jutaan pengguna setiap hari, memproses miliaran transaksi. Data besar yang dihasilkan dari transaksi ini biasanya mencakup informasi pribadi sensitif, seperti identitas pengguna, jumlah transaksi, alamat akun, dan saldo. Karena keterbukaan dan transparansi Blockchain, data yang disimpan ini terbuka untuk semua orang, sehingga memunculkan berbagai masalah keamanan dan privasi.
Saat ini, ada beberapa teknologi kripto 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 khusus yang dapat menyembunyikan identitas penandatangan, sehingga melindungi keamanan alamat akun, tetapi tidak dapat melindungi saldo akun dan jumlah transaksi. Komputasi multi-pihak yang aman memungkinkan distribusi 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, teknologi ini tidak dapat digunakan untuk memverifikasi apakah penagih di lingkungan blockchain memiliki jumlah transaksi yang cukup tanpa mengungkapkan jumlah transaksi, alamat akun, dan saldo akun.
zk-SNARKs(ZKP) adalah solusi yang lebih komprehensif, protokol verifikasi ini memungkinkan untuk memverifikasi kebenaran proposisi tertentu tanpa mengungkapkan data perantara apa pun. Protokol ini tidak memerlukan infrastruktur kunci publik yang rumit, dan penerapan ulangnya 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 mana pun. Proses verifikasi mencakup pembuatan bukti yang berisi jumlah transaksi yang diklaim oleh prover, kemudian bukti tersebut disampaikan kepada verifier, verifier melakukan perhitungan yang telah ditentukan sebelumnya pada bukti tersebut, dan menghasilkan hasil perhitungan akhir untuk menentukan 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 memainkan peran kunci 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 keberhasilan implementasi teknologi buku besar terdistribusi. Ini juga merupakan jalur utama untuk aplikasi industri dan investasi risiko.
Oleh karena itu, banyak proyek jaringan berbasis ZKP muncul, seperti ZkSync, StarkNet, Mina, Filecoin, dan Aleo. Seiring dengan perkembangan proyek-proyek ini, inovasi algoritma terkait ZKP bermunculan, dilaporkan hampir setiap minggu ada algoritma baru yang diluncurkan. Selain itu, pengembangan perangkat keras terkait teknologi ZKP juga berkembang pesat, termasuk chip yang dioptimalkan khusus untuk ZKP. Misalnya, beberapa proyek telah menyelesaikan penggalangan dana secara 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 pendorong kunci untuk penerapan teknologi Blockchain yang lebih luas, terutama dalam meningkatkan perlindungan privasi dan kapasitas pemrosesan.
Oleh karena itu, kami memutuskan untuk secara sistematis mengatur pengetahuan terkait zk-SNARKs ( ZKP ), untuk lebih baik mendukung kami dalam membuat keputusan investasi di masa depan. Untuk itu, kami telah meninjau secara komprehensif makalah akademis inti yang terkait dengan ZKP ( dan mengurutkannya berdasarkan relevansi dan jumlah kutipan ); pada saat yang sama, kami juga menganalisis secara rinci informasi dan whitepaper dari proyek-proyek terkemuka di bidang ini ( berdasarkan skala pendanaan mereka ). Pengumpulan dan analisis data yang komprehensif ini memberikan dasar yang kuat untuk penulisan artikel ini.
I. Dasar Pengetahuan zk-SNARKs
1. Ringkasan
Pada tahun 1985, para ilmuwan Goldwasser, Micali, dan Rackoff pertama kali mengajukan konsep zk-SNARKs dalam makalah berjudul "The Knowledge Complexity of Interactive Proof-Systems". Makalah ini merupakan karya dasar dari zk-SNARKs dan mendefinisikan banyak konsep yang mempengaruhi penelitian akademis selanjutnya. Misalnya, definisi pengetahuan adalah "output yang tidak dapat dihitung", yaitu pengetahuan harus merupakan sebuah output, dan merupakan suatu perhitungan yang tidak dapat dihitung, yang berarti itu tidak dapat berupa fungsi sederhana, tetapi harus berupa fungsi yang kompleks. Perhitungan yang tidak dapat dihitung biasanya dapat dipahami sebagai masalah NP, yaitu masalah yang solusi kebenarannya dapat diverifikasi dalam waktu polinomial, di mana waktu polinomial berarti waktu operasi algoritma dapat dinyatakan dengan fungsi polinomial dari ukuran input. Ini adalah standar penting dalam ilmu komputer untuk mengukur efisiensi dan kelayakan algoritma. Karena proses penyelesaian masalah NP yang kompleks, maka dianggap sebagai perhitungan yang tidak dapat dihitung; tetapi proses verifikasinya relatif sederhana, sehingga sangat cocok digunakan untuk verifikasi zk-SNARKs.
Salah satu contoh klasik dari masalah NP adalah masalah perjalanan salesman, di mana kita harus menemukan jalur terpendek untuk mengunjungi serangkaian kota dan kembali ke titik awal. Meskipun menemukan jalur terpendek mungkin sulit, memverifikasi apakah jalur yang diberikan adalah yang terpendek relatif mudah. Karena memverifikasi total jarak dari jalur tertentu dapat dilakukan dalam waktu polinomial.
Goldwasser dan kawan-kawan dalam makalah mereka memperkenalkan konsep "kompleksitas pengetahuan" untuk mengukur jumlah pengetahuan yang dibocorkan oleh pembuktian kepada pemeriksa dalam sistem pembuktian interaktif. Mereka juga mengusulkan sistem pembuktian interaktif (Interactive Proof Systems, IPS), di mana pembuktian (Prover) dan pemeriksa (Verifier) membuktikan kebenaran suatu pernyataan melalui interaksi berulang.
Secara keseluruhan, definisi zk-SNARKs yang dirangkum oleh Goldwasser dan rekan-rekan adalah suatu jenis bukti interaktif khusus, di mana verifier tidak akan memperoleh informasi tambahan selain dari kebenaran pernyataan selama proses verifikasi; dan mengajukan tiga karakteristik dasar termasuk:
Keterlengkapan: Jika argumen itu benar, pembuktian yang jujur dapat meyakinkan validator yang jujur akan fakta ini;
Keandalan: Jika pembuktian tidak mengetahui isi pernyataan, ia hanya dapat menipu verifier 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.
( 2. contoh zk-SNARKs
Untuk memahami zk-SNARKs dan atributnya dengan lebih baik, berikut adalah contoh untuk memverifikasi apakah pembuktian memiliki informasi pribadi tertentu, yang dibagi menjadi tiga tahap: pengaturan, tantangan, dan respons.
Langkah pertama: atur )Setup(
Pada langkah ini, tujuan pembuktian adalah untuk membuat sebuah bukti yang menunjukkan bahwa dia tahu angka rahasia s, tetapi tidak langsung menampilkan s. Misalkan angka rahasia s;
Pilih dua bilangan prima besar p dan q, hitung produk mereka n. Misalkan bilangan prima p dan q, hitung n yang diperoleh;
Hitung v=s^2 mod n, di sini, v sebagai bagian dari bukti dikirim kepada verifier, tetapi itu tidak cukup untuk memungkinkan verifier atau pengamat mana pun menyimpulkan s;
Pilih secara acak sebuah bilangan bulat r, hitung x=r^2 mod n dan kirimkan kepada verifier. Nilai x ini digunakan untuk proses verifikasi selanjutnya, tetapi juga tidak mengungkapkan s. Misalkan bilangan bulat acak r, hitung x yang diperoleh.
Langkah kedua: Tantangan )Challenge###
Validator secara acak memilih sebuah bit a( yang bisa berupa 0 atau 1), kemudian mengirimkannya kepada prover. "Tantangan" ini menentukan langkah yang perlu diambil oleh prover selanjutnya.
Langkah ketiga: Respon (Response)
Berdasarkan nilai a yang dikeluarkan oleh validator, penjamin memberikan respons:
Jika a=0, penjamin mengirim g=r( di mana r adalah angka acak yang dia pilih sebelumnya ).
Jika a=1, pembuktian menghitung g=rs mod n dan mengirimkannya. Misalkan bit acak a yang dikirim oleh verifier, berdasarkan nilai a, pembuktian menghitung g;
Terakhir, validator memverifikasi apakah g^2 mod n sama dengan xa^v mod n berdasarkan g yang diterima. Jika persamaan tersebut benar, validator menerima bukti ini. Ketika a=0, validator menghitung g^2 mod n, sisi kanan memverifikasi xa^v mod n=x; ketika a=1, validator menghitung g^2 mod n, sisi kanan memverifikasi xa^v mod n=xv.
Di sini, kita melihat g^2 mod n=xa^v mod n yang dihitung oleh validator menunjukkan bahwa pembuktian berhasil melewati proses verifikasi, tanpa mengungkapkan angka rahasia s. Di sini, karena a hanya bisa mengambil 0 atau 1, hanya ada dua kemungkinan, probabilitas pembuktian untuk berhasil melewati verifikasi berdasarkan keberuntungan adalah 1/2( ketika a mengambil 0 adalah ). Namun, validator kemudian menantang pembuktian k kali, pembuktian terus mengganti angka terkait, menyerahkan kepada validator, dan selalu berhasil melewati proses verifikasi, sehingga probabilitas pembuktian untuk berhasil melewati verifikasi berdasarkan keberuntungan adalah (1/2)^k( yang mendekati 0), kesimpulan bahwa pembuktian benar-benar mengetahui angka rahasia s mendapatkan pembuktian. Contoh ini membuktikan integritas, keandalan, dan sifat nol pengetahuan sistem bukti nol.
Dua, zk-SNARKs Non-interaktif
( 1. Latar Belakang
zk-SNARKs)ZKP( dalam konsep tradisional biasanya berupa bentuk protokol interaktif dan online; misalnya, protokol Sigma biasanya memerlukan tiga hingga lima putaran interaksi untuk menyelesaikan autentikasi. Namun, dalam skenario seperti transaksi instan atau pemungutan suara, sering kali tidak ada kesempatan untuk melakukan interaksi multi-putaran, terutama dalam aplikasi teknologi Blockchain, fungsi verifikasi offline menjadi sangat penting.
) 2. NIZK yang diusulkan
Pada tahun 1988, Blum, Feldman, dan Micali pertama kali mengajukan konsep bukti nol-pengetahuan non-interaktif ###NIZK(, membuktikan kemungkinan bahwa tanpa interaksi berulang, penunjuk )Prover### dan verifier (Verifier) masih dapat menyelesaikan proses otentikasi. Terobosan ini membuatnya demikian