zk-SNARK: Argumen Singkat Non-Interaktif

zk-SNARK (Argumen Pengetahuan Non-interaktif Ringkas tanpa Pengetahuan) adalah bukti yang: (1) bersifat tanpa pengetahuan, (2) ringkas (bukti kecil, verifikasi cepat terlepas dari ukuran komputasi), (3) non-interaktif (satu untaian bukti).

Protokol Sigma cocok untuk pernyataan sederhana (pengetahuan tentang logaritma diskret). Untuk komputasi kompleks — "Saya menjalankan fungsi ini dengan benar pada masukan privat" — kita memerlukan sistem bukti serbaguna. SNARK membuktikan komputasi arbitrer dalam waktu verifikasi O(1).

Komputasi pertama-tama dinyatakan sebagai sirkuit aritmetika: graf asiklik berarah yang terdiri dari gerbang penjumlahan dan perkalian pada medan hingga. Contoh: membuktikan bahwa Anda mengetahui x sedemikian sehingga x^3 + x + 5 = 35 tanpa mengungkapkan x=3. Sirkuit tersebut memiliki sekitar 5 gerbang.

Sirkuit aritmetika dikonversi menjadi R1CS: sekumpulan kendala (A*z)*(B*z) = C*z, dengan z sebagai vektor semua nilai kabel. Setiap gerbang perkalian menjadi satu kendala. Pembukti harus menemukan z yang memenuhi semua kendala tanpa mengungkapkan kabel privat.

R1CS dikonversi menjadi QAP: polinom A(x), B(x), C(x) sehingga A(x)*B(x)-C(x) habis dibagi polinom target t(x) jika dan hanya jika semua kendala terpenuhi. Pembukti menunjukkan bahwa ia mengetahui hasil bagi polinom H(x) tanpa mengungkapkan saksi.

Groth16 (2016) adalah SNARK umum yang paling efisien. Setelah penyiapan tepercaya (pembuatan CRS), pembukti menghasilkan bukti yang terdiri dari 3 elemen grup (sekitar 192 byte untuk BLS12-381). Verifikasi: 3 operasi pemasangan. Bukti berukuran konstan, terlepas dari ukuran sirkuit.

Groth16 memerlukan penyiapan tepercaya untuk setiap sirkuit: ambil limbah beracun (rahasia acak), hitung Common Reference String, lalu hancurkan limbah beracun tersebut. Jika limbah itu masih ada, penyerang dapat memalsukan bukti. Upacara multipihak (Powers of Tau) mendistribusikan kepercayaan.

PLONK (2019) menggunakan penyiapan tepercaya universal: satu upacara berlaku untuk semua sirkuit hingga batas ukuran tertentu. Tidak diperlukan penyiapan khusus untuk setiap sirkuit. Imbalannya: bukti sedikit lebih besar daripada Groth16. Digunakan dalam implementasi zkEVM (Polygon Hermez, zkSync Era).

STARK (Argumen Pengetahuan Transparan yang Dapat Diskalakan) tidak memerlukan penyiapan tepercaya dan menggunakan fungsi hash (aman pascakuantum). Imbalannya: bukti lebih besar (puluhan KB dibandingkan 200 byte). Digunakan dalam StarkWare/StarkNet dan bahasa Cairo. SNARK lebih kecil; STARK tahan kuantum.

Groth16 menggunakan pemasangan bilinear: e: G1 × G2 → GT, dengan e(a*P, b*Q) = e(P,Q)^{ab}. Ini memungkinkan pemeriksaan identitas polinom dalam eksponen tanpa mengungkapkan nilai. Kurva BLS12-381 dioptimalkan untuk pemasangan Groth16 yang efisien.

Waktu pembuktian Groth16 untuk sirkuit dengan 10^6 gerbang: sekitar 10 detik pada CPU modern. Verifikasi: sekitar 1 ms. Asimetri ini disengaja: pembukti (yang melakukan komputasi berat) mengerjakan tugas; pemeriksa (simpul blockchain) hampir tidak melakukan pekerjaan.

zk-SNARK membuktikan komputasi arbitrer dalam bukti berukuran konstan. Alur pemrosesan: komputasi → sirkuit aritmetika → R1CS → QAP → bukti SNARK. Groth16 paling efisien (penyiapan tepercaya untuk setiap sirkuit); PLONK menggunakan penyiapan universal. Berikutnya: penerapan ZKP dalam blockchain.