Edit this page on GitHub (opens in a new tab)
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).
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 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'.
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 secara terpisah untuk setiap sirkuit. Common reference string (CRS) yang dihasilkan memuat parameter publik yang digunakan oleh pembukti dan verifikator. Material penyiapan perantara yang rahasia ("limbah beracun"), bukan CRS, yang harus dirahasiakan dan dimusnahkan. Penjelasan parameter publik milik ECC membedakan keduanya.
Jika materi pengaturan rahasia yang diperlukan disimpan atau dipulihkan, seorang prover yang tidak jujur mungkin dapat menghasilkan proof atas pernyataan palsu. Dalam upacara MPC, keamanan dapat bergantung pada setidaknya satu peserta yang mengikuti protokol dan menghancurkan kontribusi rahasianya.
Setup Tepercaya namun universal - Satu setup tepercaya menghasilkan parameter yang dapat digunakan untuk menurunkan kunci pembuktian dan verifikasi untuk beberapa sirkuit dalam batas ukuran yang didukung. Ini tetap mengandung asumsi penghancuran rahasia; universal bukan berarti transparan.
Setup transparan (tanpa trusted setup) - Parameter publik dapat dihasilkan tanpa trapdoor setup rahasia yang seseorang harus dipercaya untuk menghancurkannya. Hal ini tidak berarti bahwa pembuatan proof tidak menggunakan keacakan atau bahwa sistem tidak memiliki parameter publik. Buku Halo 2 memberikan contoh parameter grup publik.
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.
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.
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?