ZKP & ZK-SNARKS
Ringkasan Singkat
- zk-SNARKs = Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge
- Teknologi ini memungkinkan satu pihak untuk membuktikan bahwa mereka mengetahui sesuatu tanpa mengungkapkan informasi itu sendiri
- Zcash menggunakan zk-SNARKs untuk membuktikan bahwa sebuah transaksi valid (jumlah yang benar, input yang belum terpakai) tanpa mengungkapkan pengirim, penerima, atau jumlahnya
- "Succinct" berarti proof tersebut sangat kecil dan cepat untuk diverifikasi bahkan untuk pernyataan yang kompleks
- Pool Orchard menggunakan Halo 2, sebuah sistem zk-SNARK yang tidak memerlukan trusted setup
Apa itu Proof?
Proof adalah dasar bagi semua matematika. Sebuah proof adalah sebuah klaim atau teorema yang sedang Anda coba buktikan & urutan derivasi yang dibuat untuk menyatakan bahwa teorema tersebut telah terbukti. misal, semua sudut dalam sebuah segitiga berjumlah 180° dapat diperiksa secara independen oleh siapa pun (verifier).
Proof
Prover ---> Membuat Klaim ---> Verifier Memilih ---> Terima/Tolak
(Baik prover maupun verifier adalah algoritma)
Dalam ilmu komputer, istilah untuk proof yang dapat diverifikasi secara efisien adalah proof NP. Proof singkat ini dapat diverifikasi dalam waktu polinomial. Ide besarnya adalah "Terdapat solusi untuk sebuah teorema & solusi tersebut diberikan kepada verifier untuk memeriksanya".
Dalam bahasa NP = dua kondisi harus terpenuhi:
Kelengkapan: Klaim yang benar akan diterima oleh verifier (memungkinkan prover yang jujur untuk mencapai verifikasi)
Keabsahan: Klaim palsu tidak akan memiliki proof (untuk semua strategi pembukti yang curang, mereka tidak akan mampu membuktikan kebenaran dari klaim yang salah).
Proof Interaktif & Probabilistik
Interaksi: Alih-alih hanya membaca proof tersebut, verifikator berinteraksi dengan pembukti secara bolak-balik melalui beberapa putaran pesan.
Randomness: Permintaan verifier kepada prover diacak dan prover harus dapat menjawab setiap permintaan dengan benar.
Dengan menggunakan interaksi dan keacakan secara bersama-sama, dimungkinkan untuk membuktikan suatu klaim kepada verifikator buta dalam Probabilistic Polynomial Time (PPT).
Dapatkah Interactive Proofs memverifikasi lebih banyak daripada proof NP secara efisien?
NP Proofs vs IP proofs:
| Pernyataan | NP | IP |
|---|
| NP | ya | ya |
| CO-NP | tidak | ya |
| #P | tidak | ya |
| PSPACE | tidak | ya |
NP - Terdapat solusi untuk sebuah pernyataan
CO-NP - Membuktikan tidak adanya solusi untuk sebuah pernyataan
#P - Untuk menghitung berapa banyak solusi yang ada dari sebuah pernyataan
PSPACE - Membuktikan sebuah alternasi dari pernyataan yang berbeda
Apa itu Zero-knowledge?
Apa yang dapat dihitung oleh seorang verifikator setelah sebuah interaksi adalah identik dengan apa yang dapat mereka buktikan sebelumnya. Interaksi selama beberapa putaran antara pembukti & verifikator tidak telah meningkatkan kekuatan komputasi dari verifikator tersebut.
Simulasi Paradigm
Eksperimen ini ada di seluruh kriptografi. Ini menghadirkan "Tampilan Nyata" & "Tampilan Simulasi".
Pandangan Nyata: Semua kemungkinan riwayat interaksi antara Prover & Verifier (P,V)
Tampilan Simulasi: Verifier mensimulasikan semua interaksi yang mungkin antara Prover & Verifier
Sebuah distinguisher berwaktu polinomial melakukan upaya untuk menentukan apakah mereka sedang melihat tampilan asli atau simulasi dan meminta sampel dari keduanya secara berulang-ulang.
Kedua pandangan tersebut dikatakan "secara komputasi tidak dapat dibedakan" jika untuk semua algoritma/strategi pembeda, bahkan setelah menerima jumlah sampel polinomial dari yang asli atau simulasi, probabilitasnya adalah >1/2.
Argumen Zero-knowledge of Knowledge
Sebuah protokol interaktif (P,V) adalah zero-knowledge jika terdapat sebuah simulator (algoritma) sedemikian rupa sehingga untuk setiap verifier dengan waktu polinomial probabilitas (ketika teorema tersebut benar), distribusi probabilitas yang menentukan perbedaan antara view asli dan simulasi tidak dapat dibedakan secara komputasi.
Protokol Interaktif sangat berguna ketika hanya ada satu verifikator. Sebuah contohnya adalah auditor pajak dalam aplikasi zero-knowledge 'proof of taxes'.
Apa itu SNARK?
Succinct Non-Interactive Argument of Knowledge
Definisi luas - Sebuah proof ringkas bahwa suatu pernyataan adalah benar. Proof tersebut harus singkat dan cepat untuk diverifikasi. Dalam SNARKs, sebuah pesan tunggal dikirim dari Prover ke Verifier. Verifier kemudian dapat memilih untuk menerima atau menolak.
contoh pernyataan: "Saya mengetahui sebuah pesan (m) sedemikian sehingga SHA256(m)=0"
Dalam sebuah zk-SNARK, proof tidak mengungkapkan apa pun tentang pesan (m).
Polinomial: Jumlah dari suku-suku yang mengandung konstanta (seperti 1,2,3), variabel (seperti x,y,z), dan eksponen dari variabel (seperti x², y³).
3x² + 8x + 17
Sirkuit Aritmetika: Sebuah model untuk menghitung polinomial. Secara lebih umum, ini dapat didefinisikan sebagai Directed Acyclic Graph di mana pada setiap node grafik dilakukan sebuah operasi aritmetika. Sirkuit ini terdiri dari gate penjumlahan, gate perkalian, dan beberapa gate konstanta. Dengan cara yang sama seperti sirkuit Boolean membawa bit dalam kabel, sirkuit Aritmetika membawa integer.
Dalam contoh ini, pembukti ingin meyakinkan verifikator bahwa ia mengetahui solusi untuk sirkuit aritmetika tersebut.
Commitments: Untuk melakukan ini, pembukti akan memasukkan semua nilai (privat dan publik) yang terkait dengan sirkuit ke dalam sebuah commitment. Commitment menyembunyikan inputnya dengan menggunakan fungsi yang outputnya tidak dapat dibalikkan.
Sha256 adalah salah satu contoh fungsi hashing yang dapat digunakan dalam skema komitmen.
Setelah pembukti melakukan komitmen terhadap nilai-nilai tersebut, komitmen dikirim ke verifikator (dengan keyakinan bahwa mereka tidak dapat mengungkap nilai asli apa pun). Pembukti kemudian dapat menunjukkan kepada verifikator pengetahuan tentang setiap nilai pada node di graf tersebut.
Transformasi Fiat-Shamir
Untuk membuat protokol menjadi non-interactive, pembukti menghasilkan keacakan (yang digunakan untuk tantangan tersembunyi) atas nama verifikator menggunakan fungsi hash kriptografi. Hal ini dikenal sebagai random oracle. Pembukti kemudian dapat mengirimkan satu pesan tunggal kepada verifikator yang setelah itu dapat memeriksa kebenarannya.
Untuk membentuk SNARK yang dapat digunakan untuk sirkuit umum, diperlukan dua elemen:
Skema komitmen fungsional: Memungkinkan seorang komiter untuk melakukan komitmen pada sebuah polinomial dengan string pendek yang dapat digunakan oleh verifier untuk mengonfirmasi klaim evaluasi dari polinomial yang dikomit tersebut.
Oracle interaktif polinomial: Verifier meminta prover (algoritma) untuk membuka semua commitment pada berbagai titik pilihan mereka menggunakan skema polynomial commitment & memeriksa apakah identitas tetap terpenuhi di antara mereka.
Persiapan
Prosedur pengaturan membantu verifikator dengan meringkas sirkuit & menghasilkan parameter publik.
Jenis pengaturan pra-pemrosesan:
Trusted Setup per sirkuit - Dijalankan satu kali per sirkuit. Bersifat spesifik untuk sebuah sirkuit & keacakan rahasia (Common Reference String) harus dijaga kerahasiaannya + dimusnahkan.
Pengaturan yang terkompromi dalam metode ini berarti pembuktian (prover) yang tidak jujur dapat membuktikan pernyataan yang salah.
Setup Terpercaya namun Universal - Hanya perlu menjalankan trusted setup satu kali dan setelah itu dapat melakukan pra-pemrosesan beberapa sirkuit secara deterministik.
Setup Transparan (Tanpa Trusted Setup) - Algoritma preprocessing tidak menggunakan keacakan rahasia sama sekali.
Jenis konstruksi SNARK proof:
Groth16: Memerlukan Trusted Setup tetapi memiliki proof yang sangat singkat yang dapat diverifikasi dengan cepat.
Sonic/Marlin/PLONK: Setup Terpercaya Secara Universal.
DARK/Halo/STARK: Tanpa Trusted Setup tetapi menghasilkan proof yang sedikit lebih panjang atau mungkin membutuhkan waktu lebih lama bagi prover untuk berjalan.
SNARKs sangat berguna ketika diperlukan banyak verifikator seperti blockchain seperti Zcash atau zk-Rollup seperti Aztec sehingga banyak node validasi tidak perlu berinteraksi selama beberapa ronde dengan setiap proof.
Bagaimana zk-SNARK diimplementasikan dalam Zcash?
Secara umum, zero-knowledge proofs adalah sebuah alat untuk menegakkan perilaku jujur dalam protokol tanpa mengungkapkan informasi apa pun.
Zcash adalah blockchain publik yang memfasilitasi transaksi privat. zk-SNARK digunakan untuk membuktikan bahwa sebuah transaksi privat valid dalam aturan konsensus jaringan tanpa mengungkapkan detail lain mengenai transaksi tersebut.
Video Penjelasan - Dalam kuliah ini Ariel Gabizon memberikan deskripsi tentang Zcash Note Commitment Tree, Blind Polynomial Evaluation & Homomorphically Hidden Challenges dan bagaimana semuanya diimplementasikan pada jaringan.
Baca buku Halo2 untuk informasi lebih lanjut.
Aplikasi Zero-Knowledge Lainnya
zk-SNARKs memberikan beberapa keuntungan dalam berbagai aplikasi yang berbeda. Mari kita lihat beberapa contohnya.
Skalabilitas: Hal ini dicapai melalui 'Outsourcing Computation'. Tidak ada kebutuhan mutlak akan zero-knowledge bagi sebuah rantai L1 untuk memverifikasi pekerjaan dari layanan off-chain. Transaksi tidak selalu bersifat privat pada zk-EVM.
Keuntungan dari layanan Rollup berbasis proof (zk-Rollup) adalah memproses batch yang berisi ratusan/ribuan transaksi & L1 mampu memverifikasi sebuah proof ringkas bahwa semua transaksi telah diproses dengan benar, meningkatkan throughput transaksi jaringan dengan faktor 100 atau 1000.
Interoperabilitas: Hal ini dicapai pada zk-Bridge dengan 'mengunci' aset di chain sumber dan membuktikan kepada chain tujuan bahwa aset tersebut telah dikunci (proof of consensus).
Kepatuhan: Proyek seperti Espresso mampu membuktikan bahwa sebuah transaksi privat telah patuh terhadap hukum perbankan setempat tanpa mengungkapkan detail dari transaksi tersebut.
Melawan Disinformasi: Di antara beberapa contoh di luar blockchain & cryptocurrency, penggunaan pembuatan proof pada gambar yang telah diproses oleh outlet berita & media untuk memungkinkan penonton memverifikasi sumber gambar dan semua operasi yang dilakukan padanya secara independen. https://medium.com/@boneh/using-zk-proofs-to-fight-disinformation-17e7d57fe52f
Pembelajaran Lebih Lanjut:
Bibliografi Zero-Knowledge - a16z Crypto
zkSNARK dengan Hanh Huynh Huu
Zcash: Halo 2 dan SNARKs tanpa Trusted Setups - Sean Bowe di Dystopia labs
Zero knowledge Proofs dengan Avi Wigderson - Numberphile
Zero-Knowledge Proofs Interaktif - Artikel Chainlink
Kuliah 1: Pengantar dan Sejarah ZKP - zklearning.org
Penjelasan Sederhana tentang Sirkuit Aritmetika - Medium
Skalabilitas itu Membosankan, Privasi Sudah Mati: ZK-Proofs, Apa Kegunaannya?
Halaman Terkait
