Crypto Gloss

Groth16: zk-SNARK Paling Efisien dengan Proof Tiga Elemen Grup

Penulis Groth, Jens
Tahun 2016
Proyek Akademis (UCL) — digunakan oleh Zcash, Tornado Cash, ZK-Rollup generasi pertama
Lisensi Creative Commons
Sumber Resmi eprint.iacr.org/2016/260
Disclaimer: Halaman ini merupakan ringkasan dan analisis edukatif dari whitepaper atau makalah teknis resmi. Konten ini disajikan untuk tujuan pendidikan semata dan bukan merupakan saran investasi atau keuangan. Selalu baca dokumen asli dan lakukan riset mandiri sebelum mengambil keputusan keuangan apa pun.

“On the Size of Pairing-Based Non-Interactive Arguments” adalah paper oleh Jens Groth (University College London), dipresentasikan di EUROCRYPT 2016. Paper ini memperkenalkan Groth16 — zk-SNARK yang paling efisien (proof terkecil, verifikasi tercepat) yang diketahui untuk pernyataan NP umum pada waktu publikasinya. Proof Groth16 hanya terdiri dari 3 elemen grup kurva eliptik (~200 byte untuk BLS12-381) dan dapat diverifikasi dalam satu persamaan pairing. Efisiensi ini menjadikan Groth16 pilihan produksi untuk Zcash Sapling, Tornado Cash, dan banyak ZK-Rollup generasi pertama.

Publikasi dan Konteks

Jens Groth telah mengerjakan proof non-interaktif selama bertahun-tahun sebelum 2016. Akademik SNARK berkembang melalui Groth-Sahai (2008), Quadratic Span Programs Gennaro et al. (2013), dan compiler Pinocchio (2013). Groth16 mencapai minimum yang dapat dibuktikan: 3 elemen grup adalah ukuran proof minimum untuk SNARK apa pun berdasarkan model keamanan yang sama. Dalam pengertian ini, Groth16 adalah optimal.

Cara Groth16 Bekerja

Langkah 1 — Sirkuit aritmetika ke R1CS:
Komputasi apapun (misalnya “saya tahu preimage hash SHA-256 ini”) dikompilasi ke Rank-1 Constraint System (R1CS): sekumpulan persamaan a · b = c atas bidang terbatas.

Langkah 2 — R1CS ke QAP:
R1CS diubah menjadi Quadratic Arithmetic Program (QAP) — representasi polynomial yang memungkinkan semua constraint dicek sekaligus menggunakan satu evaluasi polynomial.

Langkah 3 — Trusted Setup (CRS):
Trusted setup menghasilkan pasangan kunci (proving key, verification key) menggunakan nilai rahasia τ. Proving key berisi semua informasi yang dibutuhkan prover; verification key digunakan oleh verifier. τ harus dihancurkan setelah setup — ini adalah “toxic waste” Groth16.

Langkah 4 — Pembuatan Proof:
Prover menggunakan proving key untuk menghitung 3 elemen grup menggunakan sakelar acak dan witness (input privat). Waktu prover: O(N log N) di mana N adalah jumlah constraint.

Langkah 5 — Verifikasi:
Verifier hanya melakukan satu persamaan pairing dengan proof (3 elemen) dan verification key. Waktu verifikasi: konstan — tidak bergantung pada ukuran komputasi.

Trusted Setup: Risiko dan Mitigasi

Kelemahan utama Groth16: setiap sirkuit membutuhkan trusted setup baru. Jika τ bocor atau tidak dihancurkan, penyerang bisa memalsukan proof (mengklaim kepemilikan dana yang tidak dimiliki, dll.). Mitigasi:

  • Multi-party ceremony: Setup multi-pihak di mana setup aman selama satu peserta jujur
  • Zcash Powers of Tau: Upacara publik dengan ratusan peserta, masing-masing menambahkan randomness mereka
  • Tornado Cash: Upacara terpisah untuk sirkuit spesifik mereka

Penggunaan Produksi

  • Zcash Sapling (2018): Menggantikan Sprout (sistem proving Pinocchio) dengan Groth16 — waktu prover turun dari ~40 detik menjadi ~7 detik, penggunaan memori turun drastis
  • Tornado Cash: Sirkuit Groth16 untuk transaksi privat Ethereum
  • Loopring, zkSync Lite, StarkEx (awal): Proof SNARK untuk ZK-Rollup awal
  • FileCoin PoRep: Proof of Replication menggunakan Groth16

Keterbatasan

  • Trusted setup per-sirkuit — PLONK (2019) mengatasi ini dengan SRS universal
  • Prover lambat untuk sirkuit besar: mengharuskan FFT besar dan multi-exponentiation
  • Tidak bisa digunakan secara rekursif secara efisien (rekursi Groth16 membutuhkan pairing yang sangat mahal)

Warisan dan Dampak

Groth16 adalah sistem SNARK pertama yang cukup efisien untuk produksi nyata — membuktikan bahwa ZK proofs dapat berfungsi di skala blockchain. Pengaruhnya pada Zcash Sapling memengaruhi ekosistem privasi secara keseluruhan. Pekerjaan yang terinspirasi oleh dan mengatasi keterbatasan Groth16 menghasilkan PLONK, Halo2, Plonky2, dan Marlin — seluruh ekosistem SNARK modern.

Istilah Terkait

Referensi