Intuisi ZKP: Gua Ali Baba

Pembuktian Tanpa Pengetahuan (ZKP) memungkinkan pembukti meyakinkan pemeriksa bahwa ia mengetahui suatu rahasia (atau bahwa suatu pernyataan benar) tanpa mengungkapkan rahasia itu sendiri. Tiga sifatnya adalah Kelengkapan, Kebenaran, dan Tanpa Pengetahuan.

Jika pembukti mengetahui rahasia, ia selalu dapat meyakinkan pemeriksa. Pembukti jujur yang mengikuti protokol akan berhasil dengan probabilitas 1 (atau probabilitas yang sangat besar). Pemeriksa tidak akan menolak pembuktian yang valid.

Pembukti yang curang (yang tidak mengetahui rahasia) tidak dapat meyakinkan pemeriksa kecuali dengan probabilitas yang dapat diabaikan. Setiap ronde interaksi mengurangi probabilitas kecurangan—setelah k ronde: probabilitas keberhasilan pembukti curang paling banyak 2^{-k}.

Pemeriksa tidak mempelajari apa pun selain fakta bahwa pernyataan tersebut benar. Secara formal: terdapat simulator yang, tanpa mengetahui rahasia, menghasilkan transkrip yang tidak dapat dibedakan dari interaksi nyata antara pembukti dan pemeriksa. Pemeriksa memperoleh nol pengetahuan tambahan.

Sebuah gua memiliki lorong berbentuk cincin dengan pintu ajaib di tengah. Pembukti (Alice) mengaku mengetahui kata sandi. Pemeriksa (Bob) menunggu di luar. Alice masuk lalu memilih kiri atau kanan. Bob meneriakkan sisi tempat Alice harus keluar. Jika Alice mengetahui kata sandi, ia selalu keluar dari sisi yang benar. Probabilitas kecurangan per ronde: 1/2.

Setelah 20 ronde, pembukti curang berhasil dengan probabilitas 2^{-20} ≈ 1 banding sejuta. Alice (yang mengetahui kata sandi) berhasil setiap kali. Bob tidak pernah mempelajari kata sandinya—ia hanya melihat Alice keluar dari sisi yang diminta. Inilah pembuktian tanpa pengetahuan.

ZKP interaktif memerlukan komunikasi bolak-balik antara pembukti dan pemeriksa. ZKP Noninteraktif (NIZK) menggunakan transformasi Fiat-Shamir: mengganti tantangan acak pemeriksa dengan hash komitmen (hash = orakel acak). Hasilnya adalah satu rangkaian pembuktian yang dapat diverifikasi siapa pun.

ZKP merupakan Pembuktian Pengetahuan (PoK) jika strategi pembukti menyiratkan bahwa rahasia dapat diekstrak darinya. Ini lebih kuat daripada sekadar membuktikan bahwa suatu pernyataan benar. Tanda tangan ECDSA dan Schnorr adalah pembuktian pengetahuan noninteraktif atas kunci privat.

Autentikasi kata sandi tanpa mengirimkan kata sandi. Verifikasi usia tanpa mengungkapkan tanggal lahir. Pembuktian rentang (gaji Anda berada dalam suatu rentang) tanpa mengungkapkan gaji. Blockchain: membuktikan bahwa Anda mengetahui transaksi yang valid tanpa mengungkapkan transaksi tersebut.

Tanpa pengetahuan sempurna: keluaran simulator identik dengan transkrip nyata. ZK statistik: tidak dapat dibedakan kecuali dengan probabilitas yang dapat diabaikan. ZK komputasional: tidak dapat dibedakan oleh pemeriksa dengan waktu polinomial. Jaminan yang lebih lemah = bukti yang lebih efisien.

Gua tersebut adalah protokol tiga langkah: komitmen → tantangan → respons. Secara formal disebut protokol Sigma. Sebagian besar ZKP praktis (Schnorr, Pedersen, Fiat-Shamir) adalah protokol Sigma atau komposisinya. Namanya berasal dari bentuk Σ pada diagram alur pesan.

ZKP membuktikan pengetahuan tentang rahasia tanpa mengungkapkannya. Tiga sifat: kelengkapan, kekokohan, dan tanpa pengetahuan. Gua Ali Baba menggambarkan ZKP interaktif. Berikutnya: protokol Sigma dan identifikasi Schnorr.