Perkembangan dan Aplikasi Teknologi zk-SNARKs: Tinjauan di Bidang Blockchain
Ringkasan
zk-SNARKs(ZKP) sebagai terobosan penting di bidang kriptografi, memainkan peran kunci dalam teknologi Blockchain. Artikel ini memberikan tinjauan sistematis tentang perkembangan ZKP selama hampir empat puluh tahun dan penelitian terbaru.
Pertama, diperkenalkan konsep dasar dan latar belakang sejarah ZKP. Selanjutnya, analisis fokus pada teknologi ZKP berbasis sirkuit, termasuk desain, aplikasi, dan metode optimasi model seperti zkSNARK, Ben-Sasson, Pinocchio, Bulletproofs, dan Ligero. Dalam hal lingkungan komputasi, artikel ini membahas bagaimana ZKVM dan ZKEVM dapat meningkatkan kemampuan pemrosesan transaksi, melindungi privasi, dan meningkatkan efisiensi verifikasi. Juga diperkenalkan mekanisme kerja dan metode optimasi dari zero-knowledge Rollup sebagai solusi ekstensi Layer 2, serta kemajuan terbaru dalam akselerasi perangkat keras, solusi campuran, dan ZK EVM khusus.
Akhirnya, konsep-konsep baru seperti ZKCoprocessor, ZKML, ZKThreads, ZK Sharding, dan ZK StateChannels dibahas, mengeksplorasi potensi mereka dalam hal skalabilitas Blockchain, interoperabilitas, dan perlindungan privasi.
Dengan menganalisis tren perkembangan teknologi ini, artikel ini menyediakan 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, Pengetahuan Dasar 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 Karakteristik Dasar Model Sirkuit
Desain dan aplikasi sirkuit dalam zk-SNARKs
Potensi Kekurangan dan Tantangan
Empat, model zk-SNARKs
Latar belakang
Model algoritma yang umum
Skema berbasis PCP linier dan masalah logaritma diskrit
Solusi berbasis bukti orang biasa
Pembuktian yang dapat diverifikasi berdasarkan probabilitas ( PCP ) zk-SNARKs
Klasifikasi berdasarkan tahap pengaturan konstruksi bukti umum CPC( )
Lima, Ringkasan 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 di Ethereum Virtual Machine
Latar Belakang
Cara Kerja ZKEVM
Proses implementasi ZKEVM
Ciri-ciri ZKEVM
Tujuh, Ringkasan dan Perkembangan Solusi Jaringan Layer Dua zk-SNARKs
Latar belakang
Mekanisme kerja ZK Rollup
Kekurangan dan Optimasi ZK Rollup
Delapan, arah perkembangan masa depan zk-SNARKs
Mempercepat pengembangan lingkungan komputasi
Pengenalan dan perkembangan ZKML
Perkembangan terkait teknologi ekspansi ZKP
Perkembangan interoperabilitas ZKP
Kesembilan, kesimpulan
Pendahuluan
Internet sedang memasuki era Web3, aplikasi Blockchain (DApps ) berkembang pesat. Dalam beberapa tahun terakhir, platform Blockchain setiap hari menampung jutaan aktivitas pengguna, memproses miliaran transaksi. Data besar yang dihasilkan dari transaksi ini biasanya mencakup informasi pribadi yang sensitif. 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. zk-SNARKs 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 kompleks, dan penerapan ulangnya tidak memberikan kesempatan bagi pengguna jahat untuk mendapatkan informasi berguna tambahan. Melalui ZKP, verifikator dapat memverifikasi apakah pembuktian memiliki jumlah transaksi yang cukup tanpa mengungkapkan data transaksi pribadi apa pun.
Fitur ZKP ini menjadikannya peran kunci dalam transaksi Blockchain dan aplikasi cryptocurrency, terutama dalam perlindungan privasi dan skalabilitas jaringan, sehingga tidak hanya menjadi fokus penelitian akademis, tetapi juga secara luas dianggap sebagai salah satu inovasi teknologi paling penting sejak penerapan sukses teknologi buku besar terdistribusi. Selain itu, ini juga menjadi jalur utama dalam aplikasi industri dan investasi risiko.
Oleh karena itu, banyak proyek jaringan berbasis ZKP bermunculan, seperti ZkSync, StarkNet, Mina, Filecoin, dan Aleo. Seiring dengan perkembangan proyek-proyek ini, inovasi algoritma tentang ZKP muncul tanpa henti, dilaporkan hampir setiap minggu ada algoritma baru yang diluncurkan. 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 dalam skala besar, perkembangan ini tidak hanya menunjukkan kemajuan cepat teknologi ZKP, tetapi juga mencerminkan pergeseran dari perangkat keras umum ke perangkat keras khusus seperti GPU, FPGA, dan ASIC.
Kemajuan ini menunjukkan bahwa teknologi zk-SNARKs tidak hanya merupakan terobosan penting di bidang kriptografi, tetapi juga merupakan pendorong kunci untuk mewujudkan aplikasi teknologi Blockchain yang lebih luas.
Oleh karena itu, kami memutuskan untuk secara sistematis menyusun pengetahuan terkait zk-SNARKs (ZKP) untuk lebih baik membantu kami dalam membuat keputusan investasi di masa depan. Untuk itu, kami telah meninjau secara komprehensif makalah akademis inti yang terkait dengan 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 kuat untuk penulisan artikel ini.
I. Dasar Pengetahuan zk-SNARKs
1. Ringkasan
Pada tahun 1985, para ilmuwan Goldwasser, Micali, dan Rackoff pertama kali mengajukan zk-SNARKs ( Zero-Knowledge Proof, ZKP ) dan Interactive Zero-Knowledge, IZK (. Makalah ini adalah karya dasar dari zk-SNARKs, yang mendefinisikan banyak konsep yang mempengaruhi penelitian akademis selanjutnya. Misalnya, definisi pengetahuan adalah "output yang tidak dapat dihitung", yaitu pengetahuan harus berupa output, dan merupakan perhitungan yang tidak dapat dilakukan, yang berarti ia tidak bisa berupa fungsi sederhana, tetapi harus berupa fungsi yang kompleks. Perhitungan yang tidak dapat dilakukan biasanya dapat dipahami sebagai masalah NP, yaitu masalah yang solusinya dapat diverifikasi kebenarannya dalam waktu polinomial, di mana waktu polinomial berarti waktu eksekusi 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 kompleks, maka dianggap sebagai perhitungan yang tidak dapat dilakukan; tetapi proses verifikasinya relatif sederhana, sehingga sangat cocok untuk digunakan dalam verifikasi zk-SNARKs.
Salah satu contoh klasik masalah NP adalah masalah perjalanan salesman, di mana harus menemukan jalur terpendek yang mengunjungi serangkaian kota dan kembali ke titik awal. Meskipun menemukan jalur terpendek mungkin sangat sulit, memverifikasi apakah jalur tertentu adalah yang terpendek relatif mudah. Karena verifikasi total jarak jalur tertentu dapat dilakukan dalam waktu polinomial.
Goldwasser et al. memperkenalkan konsep "kompleksitas pengetahuan" dalam makalah mereka, untuk mengukur jumlah pengetahuan yang bocor dari pembuktian kepada verifikator dalam sistem pembuktian interaktif. Mereka juga mengusulkan sistem pembuktian interaktif )Interactive Proof Systems, IPS(, di mana pembuktian )Prover( dan verifikator )Verifier( membuktikan kebenaran suatu pernyataan melalui interaksi berulang.
Secara keseluruhan, definisi zk-SNARKs yang dirangkum oleh Goldwasser dan kawan-kawan adalah suatu bukti interaktif khusus, di mana verifier tidak akan mendapatkan informasi tambahan selain nilai kebenaran dari pernyataan selama proses verifikasi; dan mereka mengusulkan tiga karakteristik dasar termasuk:
Keterlengkapan ) completeness (: Jika argumen tersebut benar, maka pembuktian yang jujur dapat meyakinkan verifier yang jujur tentang kebenaran ini;
Reliabilitas ) soundness (: Jika penyaji tidak mengetahui isi pernyataan, ia hanya dapat menipu verifier dengan probabilitas yang sangat kecil;
zk-SNARKs)zero-knowledge(: setelah proses pembuktian selesai, verifier hanya memperoleh informasi "pembuktian memiliki pengetahuan ini", tanpa mendapatkan konten tambahan.
) 2. contoh zk-SNARKs
Untuk memahami zk-SNARKs dan atributnya dengan lebih baik, berikut adalah contoh untuk memverifikasi apakah seorang 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 bukti yang menunjukkan bahwa dia tahu angka rahasia s, tetapi tidak menunjukkan s secara langsung. Misalkan angka rahasia s;
Pilih dua bilangan prima besar p dan q, hitung produk mereka n. Tentukan bilangan prima p dan q, hitung n yang diperoleh;
Hitung v=s^2 mod n, di sini, v sebagai bagian dari bukti dikirimkan kepada verifier, tetapi itu tidak cukup untuk membuat 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, hitungan yang diperoleh adalah x.
Langkah kedua: Tantangan )Challenge(
Validator secara acak memilih sebuah posisi a) yang bisa berupa 0 atau 1(, kemudian mengirimkannya kepada prover. "Tantangan" ini menentukan langkah-langkah selanjutnya yang perlu diambil oleh prover.
Langkah ketiga: respons )Response(
Berdasarkan nilai a yang dikeluarkan oleh validator, penjamin memberikan respons:
Jika a=0, penunjuk mengirim g=r) di mana r adalah angka acak yang dipilihnya sebelumnya (.
Jika a=1, pembuktian menghitung g=rs mod n dan mengirimkan. Misalkan bit acak a yang dikirim oleh verifier, berdasarkan nilai a, pembuktian menghitung g;
Akhirnya, validator memverifikasi apakah x sama dengan g^2 mod n berdasarkan g yang diterima. Jika kesetaraan terpenuhi, validator menerima bukti ini. Ketika a=0, validator menghitung x=g^2 mod n, memverifikasi sisi kanan g^2 mod n; ketika a=1, validator menghitung x=g^2/v mod n, memverifikasi )rs(^2/s^2 mod n.
Di sini, kita melihat x=g^2 mod n yang dihitung oleh validator menunjukkan bahwa pembuktian berhasil melewati proses verifikasi, sambil tidak mengungkapkan angka rahasia s. Di sini, karena a hanya dapat mengambil 0 atau 1, hanya ada dua kemungkinan, probabilitas pembuktian untuk berhasil melewati verifikasi bergantung pada keberuntungan 1/2) ketika a mengambil 0 yaitu (. Namun, validator kemudian menantang pembuktian k kali, pembuktian terus-menerus mengganti angka terkait, menyerahkannya kepada validator, dan selalu berhasil melewati proses verifikasi, sehingga probabilitas pembuktian untuk berhasil melewati verifikasi bergantung pada keberuntungan )1/2(^k) mendekati 0(, kesimpulan bahwa pembuktian memang mengetahui angka rahasia s terbukti. Contoh ini membuktikan integritas, keandalan, dan sifat tanpa pengetahuan dari sistem zk-SNARKs.
Dua, zk-SNARKs Non-Interaktif
) 1. Latar Belakang
zk-SNARKs###ZKP( dalam konsep tradisional biasanya merupakan bentuk protokol interaktif dan daring; 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 berulang, terutama dalam aplikasi teknologi Blockchain, di mana fungsi verifikasi offline menjadi sangat penting.
) 2. NIZK yang diusulkan
Pada tahun 1988, Blum, Feldman, dan Micali pertama kali mengemukakan konsep bukti nol pengetahuan non-interaktif ###NIZK(, yang membuktikan kemungkinan bahwa dalam situasi tanpa interaksi berulang, pembuktian )Prover( dan verifier )Verifier( masih dapat menyelesaikan proses otentikasi. Terobosan ini membuat transaksi instan, pemungutan suara, dan implementasi aplikasi Blockchain menjadi mungkin.
Mereka mengusulkan non-interaktif zk-SNARKs ) NIZK ( dapat dibagi menjadi tiga tahap:
Pengaturan
Menghitung
Verifikasi
Tentukan fase menggunakan fungsi komputasi, mengubah parameter keamanan menjadi pengetahuan publik ) yang dapat diakses oleh penjamin dan validator (, biasanya dikodekan dalam sebuah string referensi bersama ) CRS (. Ini adalah cara untuk menghitung bukti dan memverifikasi dengan parameter dan algoritma yang benar.
Tahap perhitungan menggunakan fungsi perhitungan, kunci input dan bukti, serta menghasilkan hasil perhitungan dan bukti.
Pada tahap verifikasi, validitas bukti diverifikasi melalui kunci verifikasi.
Model string referensi publik yang mereka usulkan )CRS(, yaitu berbasis pada semua peserta yang berbagi satu string untuk mencapai bukti nol interaktif non-interaktif untuk masalah NP. Operasi model ini bergantung pada pembuatan CRS yang tepercaya, semua peserta harus dapat mengakses string yang sama. Hanya ketika CRS dihasilkan dengan benar dan aman, skema yang dilaksanakan berdasarkan model ini dapat memastikan keamanan. Untuk banyak peserta, proses pembuatan CRS bisa sangat rumit dan memakan waktu, sehingga meskipun skema semacam ini biasanya mudah dioperasikan dan ukuran buktinya kecil, proses pengaturannya cukup menantang.
Kemudian, teknologi NIZK mengalami perkembangan pesat, muncul berbagai metode untuk mengubah bukti nol pengetahuan interaktif menjadi bukti non-interaktif. Metode-metode ini dalam konstruksi sistem
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.
13 Suka
Hadiah
13
7
Posting ulang
Bagikan
Komentar
0/400
LiquidityWitch
· 5jam yang lalu
penyulingan sihir zk... kolam gelap kebenaran matematis, di mana kriptografi kuno bertemu alkimia blockchain
Lihat AsliBalas0
SigmaBrain
· 08-11 01:18
Apakah zk akan menjadi solusi terbaik untuk L2?
Lihat AsliBalas0
NotSatoshi
· 08-11 01:16
Sudah beberapa tahun saya mendalami zk, tetapi masih belum memahami dengan baik.
Lihat AsliBalas0
WagmiWarrior
· 08-11 01:15
Lihat lagi ada yang membicarakan zk, lakukan penelitian dasar dengan baik sebelum membicarakannya.
Lihat AsliBalas0
UnluckyValidator
· 08-11 01:12
Ayam bayar belum cepat naik level
Lihat AsliBalas0
MetaLord420
· 08-11 01:11
Ini adalah pelindung zkrollup lagi...
Lihat AsliBalas0
BearMarketMonk
· 08-11 01:02
Tidak masalah apakah Anda hidup atau mati, zkp benar-benar harum
Analisis mendalam teknologi zk-SNARKs: Tinjauan komprehensif dari Algoritme hingga aplikasi
Perkembangan dan Aplikasi Teknologi zk-SNARKs: Tinjauan di Bidang Blockchain
Ringkasan
zk-SNARKs(ZKP) sebagai terobosan penting di bidang kriptografi, memainkan peran kunci dalam teknologi Blockchain. Artikel ini memberikan tinjauan sistematis tentang perkembangan ZKP selama hampir empat puluh tahun dan penelitian terbaru.
Pertama, diperkenalkan konsep dasar dan latar belakang sejarah ZKP. Selanjutnya, analisis fokus pada teknologi ZKP berbasis sirkuit, termasuk desain, aplikasi, dan metode optimasi model seperti zkSNARK, Ben-Sasson, Pinocchio, Bulletproofs, dan Ligero. Dalam hal lingkungan komputasi, artikel ini membahas bagaimana ZKVM dan ZKEVM dapat meningkatkan kemampuan pemrosesan transaksi, melindungi privasi, dan meningkatkan efisiensi verifikasi. Juga diperkenalkan mekanisme kerja dan metode optimasi dari zero-knowledge Rollup sebagai solusi ekstensi Layer 2, serta kemajuan terbaru dalam akselerasi perangkat keras, solusi campuran, dan ZK EVM khusus.
Akhirnya, konsep-konsep baru seperti ZKCoprocessor, ZKML, ZKThreads, ZK Sharding, dan ZK StateChannels dibahas, mengeksplorasi potensi mereka dalam hal skalabilitas Blockchain, interoperabilitas, dan perlindungan privasi.
Dengan menganalisis tren perkembangan teknologi ini, artikel ini menyediakan 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, Pengetahuan Dasar zk-SNARKs
Dua, zk-SNARKs non-interaktif
Tiga, zk-SNARKs berbasis sirkuit
Empat, model zk-SNARKs
Lima, Ringkasan dan Perkembangan zk-SNARKs Virtual Machine
Enam, Ringkasan dan Perkembangan zk-SNARKs di Ethereum Virtual Machine
Tujuh, Ringkasan dan Perkembangan Solusi Jaringan Layer Dua zk-SNARKs
Delapan, arah perkembangan masa depan zk-SNARKs
Kesembilan, kesimpulan
Pendahuluan
Internet sedang memasuki era Web3, aplikasi Blockchain (DApps ) berkembang pesat. Dalam beberapa tahun terakhir, platform Blockchain setiap hari menampung jutaan aktivitas pengguna, memproses miliaran transaksi. Data besar yang dihasilkan dari transaksi ini biasanya mencakup informasi pribadi yang sensitif. 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. zk-SNARKs 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 kompleks, dan penerapan ulangnya tidak memberikan kesempatan bagi pengguna jahat untuk mendapatkan informasi berguna tambahan. Melalui ZKP, verifikator dapat memverifikasi apakah pembuktian memiliki jumlah transaksi yang cukup tanpa mengungkapkan data transaksi pribadi apa pun.
Fitur ZKP ini menjadikannya peran kunci dalam transaksi Blockchain dan aplikasi cryptocurrency, terutama dalam perlindungan privasi dan skalabilitas jaringan, sehingga tidak hanya menjadi fokus penelitian akademis, tetapi juga secara luas dianggap sebagai salah satu inovasi teknologi paling penting sejak penerapan sukses teknologi buku besar terdistribusi. Selain itu, ini juga menjadi jalur utama dalam aplikasi industri dan investasi risiko.
Oleh karena itu, banyak proyek jaringan berbasis ZKP bermunculan, seperti ZkSync, StarkNet, Mina, Filecoin, dan Aleo. Seiring dengan perkembangan proyek-proyek ini, inovasi algoritma tentang ZKP muncul tanpa henti, dilaporkan hampir setiap minggu ada algoritma baru yang diluncurkan. 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 dalam skala besar, perkembangan ini tidak hanya menunjukkan kemajuan cepat teknologi ZKP, tetapi juga mencerminkan pergeseran dari perangkat keras umum ke perangkat keras khusus seperti GPU, FPGA, dan ASIC.
Kemajuan ini menunjukkan bahwa teknologi zk-SNARKs tidak hanya merupakan terobosan penting di bidang kriptografi, tetapi juga merupakan pendorong kunci untuk mewujudkan aplikasi teknologi Blockchain yang lebih luas.
Oleh karena itu, kami memutuskan untuk secara sistematis menyusun pengetahuan terkait zk-SNARKs (ZKP) untuk lebih baik membantu kami dalam membuat keputusan investasi di masa depan. Untuk itu, kami telah meninjau secara komprehensif makalah akademis inti yang terkait dengan 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 kuat untuk penulisan artikel ini.
I. Dasar Pengetahuan zk-SNARKs
1. Ringkasan
Pada tahun 1985, para ilmuwan Goldwasser, Micali, dan Rackoff pertama kali mengajukan zk-SNARKs ( Zero-Knowledge Proof, ZKP ) dan Interactive Zero-Knowledge, IZK (. Makalah ini adalah karya dasar dari zk-SNARKs, yang mendefinisikan banyak konsep yang mempengaruhi penelitian akademis selanjutnya. Misalnya, definisi pengetahuan adalah "output yang tidak dapat dihitung", yaitu pengetahuan harus berupa output, dan merupakan perhitungan yang tidak dapat dilakukan, yang berarti ia tidak bisa berupa fungsi sederhana, tetapi harus berupa fungsi yang kompleks. Perhitungan yang tidak dapat dilakukan biasanya dapat dipahami sebagai masalah NP, yaitu masalah yang solusinya dapat diverifikasi kebenarannya dalam waktu polinomial, di mana waktu polinomial berarti waktu eksekusi 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 kompleks, maka dianggap sebagai perhitungan yang tidak dapat dilakukan; tetapi proses verifikasinya relatif sederhana, sehingga sangat cocok untuk digunakan dalam verifikasi zk-SNARKs.
Salah satu contoh klasik masalah NP adalah masalah perjalanan salesman, di mana harus menemukan jalur terpendek yang mengunjungi serangkaian kota dan kembali ke titik awal. Meskipun menemukan jalur terpendek mungkin sangat sulit, memverifikasi apakah jalur tertentu adalah yang terpendek relatif mudah. Karena verifikasi total jarak jalur tertentu dapat dilakukan dalam waktu polinomial.
Goldwasser et al. memperkenalkan konsep "kompleksitas pengetahuan" dalam makalah mereka, untuk mengukur jumlah pengetahuan yang bocor dari pembuktian kepada verifikator dalam sistem pembuktian interaktif. Mereka juga mengusulkan sistem pembuktian interaktif )Interactive Proof Systems, IPS(, di mana pembuktian )Prover( dan verifikator )Verifier( membuktikan kebenaran suatu pernyataan melalui interaksi berulang.
Secara keseluruhan, definisi zk-SNARKs yang dirangkum oleh Goldwasser dan kawan-kawan adalah suatu bukti interaktif khusus, di mana verifier tidak akan mendapatkan informasi tambahan selain nilai kebenaran dari pernyataan selama proses verifikasi; dan mereka mengusulkan tiga karakteristik dasar termasuk:
Keterlengkapan ) completeness (: Jika argumen tersebut benar, maka pembuktian yang jujur dapat meyakinkan verifier yang jujur tentang kebenaran ini;
Reliabilitas ) soundness (: Jika penyaji tidak mengetahui isi pernyataan, ia hanya dapat menipu verifier dengan probabilitas yang sangat kecil;
zk-SNARKs)zero-knowledge(: setelah proses pembuktian selesai, verifier hanya memperoleh informasi "pembuktian memiliki pengetahuan ini", tanpa mendapatkan konten tambahan.
) 2. contoh zk-SNARKs
Untuk memahami zk-SNARKs dan atributnya dengan lebih baik, berikut adalah contoh untuk memverifikasi apakah seorang 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 bukti yang menunjukkan bahwa dia tahu angka rahasia s, tetapi tidak menunjukkan s secara langsung. Misalkan angka rahasia s;
Pilih dua bilangan prima besar p dan q, hitung produk mereka n. Tentukan bilangan prima p dan q, hitung n yang diperoleh;
Hitung v=s^2 mod n, di sini, v sebagai bagian dari bukti dikirimkan kepada verifier, tetapi itu tidak cukup untuk membuat 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, hitungan yang diperoleh adalah x.
Langkah kedua: Tantangan )Challenge(
Validator secara acak memilih sebuah posisi a) yang bisa berupa 0 atau 1(, kemudian mengirimkannya kepada prover. "Tantangan" ini menentukan langkah-langkah selanjutnya yang perlu diambil oleh prover.
Langkah ketiga: respons )Response(
Berdasarkan nilai a yang dikeluarkan oleh validator, penjamin memberikan respons:
Jika a=0, penunjuk mengirim g=r) di mana r adalah angka acak yang dipilihnya sebelumnya (.
Jika a=1, pembuktian menghitung g=rs mod n dan mengirimkan. Misalkan bit acak a yang dikirim oleh verifier, berdasarkan nilai a, pembuktian menghitung g;
Akhirnya, validator memverifikasi apakah x sama dengan g^2 mod n berdasarkan g yang diterima. Jika kesetaraan terpenuhi, validator menerima bukti ini. Ketika a=0, validator menghitung x=g^2 mod n, memverifikasi sisi kanan g^2 mod n; ketika a=1, validator menghitung x=g^2/v mod n, memverifikasi )rs(^2/s^2 mod n.
Di sini, kita melihat x=g^2 mod n yang dihitung oleh validator menunjukkan bahwa pembuktian berhasil melewati proses verifikasi, sambil tidak mengungkapkan angka rahasia s. Di sini, karena a hanya dapat mengambil 0 atau 1, hanya ada dua kemungkinan, probabilitas pembuktian untuk berhasil melewati verifikasi bergantung pada keberuntungan 1/2) ketika a mengambil 0 yaitu (. Namun, validator kemudian menantang pembuktian k kali, pembuktian terus-menerus mengganti angka terkait, menyerahkannya kepada validator, dan selalu berhasil melewati proses verifikasi, sehingga probabilitas pembuktian untuk berhasil melewati verifikasi bergantung pada keberuntungan )1/2(^k) mendekati 0(, kesimpulan bahwa pembuktian memang mengetahui angka rahasia s terbukti. Contoh ini membuktikan integritas, keandalan, dan sifat tanpa pengetahuan dari sistem zk-SNARKs.
Dua, zk-SNARKs Non-Interaktif
) 1. Latar Belakang
zk-SNARKs###ZKP( dalam konsep tradisional biasanya merupakan bentuk protokol interaktif dan daring; 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 berulang, terutama dalam aplikasi teknologi Blockchain, di mana fungsi verifikasi offline menjadi sangat penting.
) 2. NIZK yang diusulkan
Pada tahun 1988, Blum, Feldman, dan Micali pertama kali mengemukakan konsep bukti nol pengetahuan non-interaktif ###NIZK(, yang membuktikan kemungkinan bahwa dalam situasi tanpa interaksi berulang, pembuktian )Prover( dan verifier )Verifier( masih dapat menyelesaikan proses otentikasi. Terobosan ini membuat transaksi instan, pemungutan suara, dan implementasi aplikasi Blockchain menjadi mungkin.
Mereka mengusulkan non-interaktif zk-SNARKs ) NIZK ( dapat dibagi menjadi tiga tahap:
Tentukan fase menggunakan fungsi komputasi, mengubah parameter keamanan menjadi pengetahuan publik ) yang dapat diakses oleh penjamin dan validator (, biasanya dikodekan dalam sebuah string referensi bersama ) CRS (. Ini adalah cara untuk menghitung bukti dan memverifikasi dengan parameter dan algoritma yang benar.
Tahap perhitungan menggunakan fungsi perhitungan, kunci input dan bukti, serta menghasilkan hasil perhitungan dan bukti.
Pada tahap verifikasi, validitas bukti diverifikasi melalui kunci verifikasi.
Model string referensi publik yang mereka usulkan )CRS(, yaitu berbasis pada semua peserta yang berbagi satu string untuk mencapai bukti nol interaktif non-interaktif untuk masalah NP. Operasi model ini bergantung pada pembuatan CRS yang tepercaya, semua peserta harus dapat mengakses string yang sama. Hanya ketika CRS dihasilkan dengan benar dan aman, skema yang dilaksanakan berdasarkan model ini dapat memastikan keamanan. Untuk banyak peserta, proses pembuatan CRS bisa sangat rumit dan memakan waktu, sehingga meskipun skema semacam ini biasanya mudah dioperasikan dan ukuran buktinya kecil, proses pengaturannya cukup menantang.
Kemudian, teknologi NIZK mengalami perkembangan pesat, muncul berbagai metode untuk mengubah bukti nol pengetahuan interaktif menjadi bukti non-interaktif. Metode-metode ini dalam konstruksi sistem