Privacy via Zk Snarks

Using zk-SNARKs for Privacy on the Blockchain #

What is a zk-SNARK? #

  • SNARK: a succinct proof that a certain statement is true
    • e.g. statement: “I know an m such that $SHA256(m) = 0$
    • Note: SNARK means that the proof is short and fast to verify (if m is 1GB then using the message m as a proof is not a SNARK)
  • Blockchain applications:
    • Private Tx on a public blockchain: Tornadocash, Zcash, Ironfish, Aleo
    • Compliance: proving that private Tx are in compliance with banking laws; proving solvency in zero-knowledge
    • Bridging between blockchains: zkBridge

Review: arithmetic circuit #

  • Fix finite field $\mathrm{F} = {0, …, p-1}$ for some prime $p > 2$
  • Arithmetic circuit $C : \mathrm{F}^n \rightarrow \mathrm{F}$
    • Directed acyclic graph (DAG) where internal nodes labeled $+$, $-$, $\times$
    • Inputs labeled $1, x_1, \ldots, x_n$
    • Defines $n$-variate polynomial with an evaluation recipe
    • $|C|$: number of inner gates in $C$
  • Interesting arithmetic circuits
    • $C_\text{hash}(h, m)$: outputs 0 if $SHA256(m) = h$, and nonzero otherwise
    • $C_\text{hash}(h, m) = (h - SHA256(m))$, $|C_\text{hash}| \approx $ 20k gates
    • $C_\text{sig}(pk, m, \sigma)$: outputs 0 if $\sigma$ is a valid ECDSA signature on $m$ with respect to $pk$, hundreds of thousands of gates

NARK: Non-interactive ARgument of Knowledge #

  • Public arithmetic circuit: $C(x, w) \rightarrow F$
    • Where $x$ public statement in $F^n$, $w$ secret witness in $F^m$
  • Preprocessing (setup): $S(C) \rightarrow$ public parameters $(pp, vp)$ for prover, verifier
  • Prover: $P(pp, x, w) \rightarrow $ proof $\pi$
  • Verifier: $V(vp, x, \pi) \rightarrow $ accept or reject

NARK requirements #

  • Complete: if both $P$, $V$ honest, then $V$ should accept proof $\pi$
  • Adaptively knowledge sound: $V$ accepts a proof: $P$ “knows” $w$ such that $C(x, w) = 0$ (an extractor $E$ can extract a valid $w$ from $P$)
  • Optional: Zero knowledge: $(C, pp, vp, x, \pi)$ “reveal nothing” about $w$

SNARK: a succinct NARK #

Setup: similar, except

  • $P(pp, w, x)$ generates a short proof $\pi$ such that $|\pi| = O_{\lambda}(\log(|C|))$
  • $V(vp, \pi, x)$ is fast to verify such that $\text{time}(V) = O_{\lambda}(|x|, \log(|C|))$

For zero-knowledge, defining knowledge soundness and zero-knowledge: see CS255 notes

Types of preprocessing setup #

  • $r$ random bits
  • Trusted setup per circuit: $S(C; r)$ random $r$ must be kept secret from prover
    • Prover learns $r$: can provide false statements
    • Therefore: destroy machine after using this once
  • Trusted but universal (updatable) setup: secret $r$ is independent of $C$
  • Transparent setup: $S(C)$ does not use secret data (no trusted setup)

Recent progress on proof systems #

  • Groth (2016): proof size ~ 200 bytes, verifier time ~ 1.5ms, trusted per circuit setup
  • Plonk and Marlin (2019): proof size ~ 400 bytes, verifier time ~ 3ms, universal trusted setup
  • Bulletproofs (Bunz et al. (2017)): proof size ~ 1.5 kb (non-constant), verifier time ~ 3 sec, transparent setup
  • STARK (Ben-Sasson et al. (2018)): proof size ~ 100 kb (non-constant), verifier time ~ 10 ms, transparent setup, post-quantum enabled
  • And more!