Introduction

Introduction

Introduction and History of ZKP

Date: 2024-08-25 03:05:06

Reviewed:

Topic / Chapter: Introduction and History of ZKP

Notes

Introduction

Cornell Format

Date:

Reviewed:

Topic / Chapter:

Notes

Date:

Reviewed:

Topic / Chapter:

❓Questions

Notes

• Introduction to Modern SNARKs
  • SNARKs
    • SNARK: a succinct proof that a certain statement is true
      • i.e. “short” and “fast” to verify
      • e.g. solution itself: might not be short nor fast to verify
    • zk-SNARK: revealing nothing about $m$
    • potentially: a single reliable PC can monitor supercomputers’ operation
      • or: slow computer monitoring GPUs
      • slow computer: like layer-1s
  • Blockchain applications 1
    • outsourcing computation (not zk)
      • L1: quickly verifies work of off-chain service
    • e.g. scalability: proof-based rollups (zkRollup)
      • off-chain service processes a batch of Tx
      • L1 chain: verifies a succinct proof of correct processing
    • e.g. bridging blockchains: Po-Consensus (zkBridge)
      • enables transfer of assets from one chain to another
      • proving to target chain that asset was locked in source chain
  • Blockchain applications 2
    • (requiring zk)
    • private Tx on a public blockchain
      • zk proof that a private Tx is valid
    • compliance
      • proof that a private Tx is compliant w/ banking laws
      • proof that an exchange is solvent in zk
    • also: non-blockchain applications exist
      • e.g. fighting disinformation: C2PA
      • camera: w/ embedded secret key
        • and signs picture w/ location & timestamp
        • metadata: can be confirmed
      • problem: image post-processing
        • disable further C2PA verification
      • zk-SNARK solution
        • laptop: w/ (Photo, Ops)
        • $\pi$: proves that “I know a pair (Orig, Sig) s.t.”
          • Sig a valid C2PA signature on Orig
          • Photo is result of applying Ops to Orig
          • metadata(Photo)==metadata(Orig)
        • laptop verifies $\pi$ and shows metadata
        • size: ≤ 1 KB, takes ≤ 10 ms in browser
          • proof generation: takes a few minutes w/ sufficient HW
            • parallelizable
        • proof: must be not interactable
• What is SNARK
  • Arithmetic circuits
    • computation model: must be fixed to build SNARK
    • let $\mathbf{F}=\{0,\dots ,p-1\}$ for $p>2$
      • finite field
      • closed w/ addition & multiplication
    • arithmetic circuits
      • $C:F^n\to F$ (n input w/ 1 output)
      • directed acyclic graph, where
        • internal nodes: $+,-,\times$
        • inputs: $1,x_1,\dots ,x_n$
      • defines: n-variate polynomial w/ evaluation recipe
      • $|C|$: no. of gates in $C$
    • interesting cases
      • $C_{sha}(h,m)$: $(SHA256(m)==h)?0:1$
      • $C_{hSHA}(h,m)=(h-SHA256(m))$
        • $|C_{SHA}|\approx 20K$ gates (”small”)
      • $C_{sig}(pk,m,\sigma )$: output 0 if $\sigma$ a valid ECDSA sig of $m,pk$
    • structured vs. unstructured circuits

      • unstructured: w/ arbitrary wires

      • structured: build in layers, one circuit being repeated

        

        • layer: aka VM
  • NARK: Non-interactive ARgument of Knowledge
    • applied arithmetic circuit
      • $C(x,w)\to \mathbf{F}$
        • $x$: oublic statement in ${\mathbf{F}}^n$
        • $w$: secret witness in ${\mathbf{F}}^m$
      • preprocessing: $S(C)\to$ public params ($pp,vp$)
        • public param for prover / verifier
    • prover: $pp,x,w$
      • generate proof $\pi$ that $C(x,w)=0$
    • verifier: $vp,x$
    • preprocessing NARK: triple $(S,P,V)$
      • $S(C)$: description of circuit $C$
      • $P(pp,x,w)\to \pi$
      • $V(vp,x,\pi )$: accept / reject
      • all alg. and adversary: w/ access to random oracle
    • informal requirements
      • complete: $\forall x,w,:C(x,w)$⇒ $Pr[V(vp,x,P(pp,x,w))=1]=1$
        • i.e. always accept if valid
      • or: “knowledge sound”
        • if $V$ accepts ⇒ $P$ “knows” $w$ s.t. $C(x,w)=0$
        • and extractor $E$ can extract a valid $w$
      • optional: ZK: $(C,pp,vp,x,\pi )$ reveals “nothing new” about $w$
    • trivial NARK: $\pi =w$
  • SNARK
    • succinct preprocessing NARK
    • same for $S(C)$
    • $P(pp,x,w)$: short $\pi$
      • len($\pi$) = sublinear($|w|$)
    • $V(vp,x,\pi )$: fast to verify
      • time(V)= $O_{\lambda}(|x|$, sublinear($|C|$))
    • i.e. anything better than NARK: technically SNARK
    • however, strongly succinct NARK is:
      • len($\pi$) = $O_{\lambda}(\log |C|)$
      • time(V)= $O_{\lambda}(|x|,\log(|C|))$
        • i.e. no time to even read circuit $C$
        • thus: preprocessing needed
          • $vp$: summary of $C$
    • most SNARKs to be discussed: in constant time
    • trivial SNARK: not SNARK
      • long proof
      • $C(x,w)$ might be hard (and slow)
      • $w$: might be secret
  • Preprocessing (setup)

    • $S(C;r)\to (pp,vp)$

    • setup types

      • trusted setup per circuit
        • run fresh for each circuit
        • and $r$ must be kept secret
          • if $r$ is learned: false statements can be proven
          • generator: destroyed after task
      • trusted but universal (updatable) setup
        • secret $r$: independent of $C$
        • $S=(S_{init},S_{index})$
        • $S_{init}(\lambda ;r)\to gp$ (global param)
          • one-time setup, secret $r$
        • $S_{index}(gp,C)\to (pp,vp)$
          • deterministic
          • can be repeated
      • transparent setup
        • $S(C)$: doesn’t use secret data

    • significant progress

      	size of $\pi$	verifier time	setup	post-quantum
      Groth’16	$\approx$ 200 Bytes	$\approx$ 1.5 ms	trusted per circuit	no
      Plonk / Marlin	$\approx$ 400 Bytes	$\approx$ 3 ms	universal trusted setup	no
      Bulletproofs	$O_{\lambda }(\log \Vert C\Vert )$ $\approx$ 1.5 KB	$O_{\lambda }(\Vert C\Vert )$ $\approx$ 3 sec	transparent	no
      STARK	$O_{\lambda }({\log }^2\Vert C\Vert )$ $\approx$ 100 KB	$O_{\lambda }({\log }^2\Vert C\Vert )$$\approx$ 10 ms	transparent	yes

      • prover time: almost $O_{\lambda }(\Vert C\Vert )$
  • Knowledge
    • if $V$ accepts ⇒ $P$ knows $w$ s.t. $C(x,w)=0$
    • if $P$ knows $w$: we can “torture” $P$ to get $w$
    • formal knowledge
      • $(S,P,V)$ is knowledge sound for $C$ if
      • $\forall$ eff. adversary $A=(A_0,A_1)$ s.t.
      • $gp\leftarrow S_{init}()$, $(C,x,st)\leftarrow A_0(gp)$
      • $(pp,vp)\leftarrow S_{index}(C)$
      • $\pi \leftarrow A_1(pp,x,st)$
      • $Pr[V(vp,x,\pi )=1]>1/10^6$
        • i.e. non-negl
      • then $\exists$ eff. extractor $E$ s.t.
        • $gp\leftarrow S_{init}()$
        • $(C,x,st)\leftarrow A_0(gp)$
        • $w\leftarrow E(gp,C,x)$
        • $Pr[C(x,w)=0]>1/10^6-\epsilon$
    • i.e. if there is an efficient prover, then we can extract the knowledge
• Building an eff. SNARK
  • Building SNARK
    • general paradigm: two steps
      • a functional commitment scheme
        • cryptographic obj
      • a compatible interactive oracle proof (IOP)
        • info. theoretic obj
      • result: SNARK for general circuits
    • commitments scheme
      • made of commit & verify
      • must satisfy: binding & hiding property
    • standard commitment
      • $H:M\times R\to T$
      • $commit(m,r)$: com:=H(m,r)
      • $verify(m,com,r)$: accepts if com=H(m,r)
  • Functional commitment scheme
    • given a family of functions $F=\{f:X\to Y\}$
    • $co{m}_f\leftarrow commit(f,r)$
      • sent to verifier
    • verifier: sends $x\in X$
    • prover: sends $y\in Y$ and $\pi$
      • proving that $f(x)=y$ and $f\in F$
    • a functional commitment scheme for $F$
      • $setup(1^{\lambda })\to gp$: outputs public param
      • $commit(gp,f,r)\to co{m}_f$
        • binding & optional hiding (for zk-SNARK)
      • $eval(P,V)$
        • $P(gp,f,x,y,r)\to \pi$
        • $V(gp,co{m}_f,x,y,\pi )\to$ accept / reject
        • a SNARK for relation
          • $f(x)=y$, $f\in F$, and $commit(gp,f,r)=co{m}_f$
    • four important functional commitments
      • polynomial commitments
        • commit to a univariate $f(X)$ in $F_p^{\le d}[X]$
      • multilinear commitments
        • commit to multilinear $f$ in $F_p^{\le 1}[X_1,\dots ,X_k]$
        • e.g. $f(x_1,\dots ,x_k)=x_1{x}_3+x_1{x}_4{x}_5+x_7$
      • vector commitments (e.g. Merkle tree)
        • commit to $\overrightarrow{u}=(u_1\dots ,u_d)\in F_p^d$
        • open cells: $f_{\overrightarrow{u}}(i)=u_i$
          • prove that $i$th index is $u_i$
      • inner product commitments
        • aka inner product arguments (IPA)
        • commit to $\overrightarrow{u}\in F_p^d$
        • open an inner product $f_{\overrightarrow{u}}(\overrightarrow{v})=(\overrightarrow{u},\overrightarrow{v})$
  • Polynomial commitments
    • commit to a univariate $f(X)$ in $F_p^{\le d}[X]$
    • eval: for public $u,v\in F_p$, prover can convince
      • $f(u)=v$ and $\mathrm{deg}(f)\le d$
      • for verifier w/ $(d,co{m}_f,u,v)$
    • eval proof size & verifier time: $O_{\lambda }(\log d)$
    • few examples
      • w/ bilinear groups: KZG’10 (trusted setup), Dory’20
      • w/ hash functions only: based on FRI (long eval proofs)
      • w/ elliptic curves: Bulletproofs (short proof, but verifier time being $O(d)$)
      • w/ groups of unknown order: Dark’20 (slow)
      • KZG’10: most widely used
    • trivial commitment scheme: not a polynomial commitment
      • let $commit(f={\sum }_{i=0}^d{a}_i{X}^i,r)$
        • output $co{m}_f\leftarrow H((a_0,\dots ,a_d),r)$
      • eval: prover sends $\pi =((a_0,\dots ,a_d),r)$ to verifier
        • verifier accepts if $f(u)=v$ and $H((a_0,\dots ,a_d),r)=co{m}_f$
        • proof size & verification time: linear in $d$
  • Useful observation
    • for a non-zero $f\in F_p^{\le d}[X]$
      • for $r\stackrel{\$}{\leftarrow }{F}_p$: $Pr[f(r)=0]\le d/p$
        • aka SZDL lemma
        • also holds for multivariate polynomials
          • $d$: total degree of $f$
      • has at most $d$ roots in finite field
        • and $p$ possibilities for $r$
    • thus, suppose $p\approx 2^{256}$ and $d\le 2^{40}$
      • then $d/p$ is negligible
    • and if $f(r)=0$, $f=0$ for high probability
    • suppose $p\approx 2^{256}$ and $2\le 2^{40}$
      • let $f,g\in F_p^{\le d}[X]$
      • for $r\stackrel{\$}{\leftarrow }{F}_p$: if $f(r)=g(r)$
        • ⇒ $f=g$ w.h.p.
      • as $f(r)-g(r)=0$
        • ⇒ $f-g=0$ w.h.p.
      • $Pr[f(r)=0]\le d/p$
    • ⇒ simple equality test for two committed polynomials
  • Equality test protocol
    • interactive protocol
      • prover: $f,g\in F_p^{\le d}[X]$
      • verifier: gives $r\stackrel{\$}{\leftarrow }R$
      • prover: computes $y\leftarrow f(r)$, $y^{\prime }\leftarrow g(r)$
        • and attaches proof for
          • $y=f(r)$
          • $y^{\prime }=g(r)$
        • along w/ $y,y^{\prime }$
      • verifier: accepts if
        • valid proof
        • $y=y^{\prime }$
    • can be made non-interactive (Fiat-Shamir)
      • for all public-coin IP
      • prover: generates $r$ by its own w/ $H$
      • $P(pp,x=(co{m}_f,co{m}_g),w=(f,g))$
        • $r\leftarrow H(x)$
        • $y\leftarrow f(r)$, $y^{\prime }\leftarrow g(r)$
        • sends $y,y^{\prime },{\pi }_f,{\pi }_g$
      • $V(vp,x=(co{m}_f,co{m}_g))$
        • compute $r=H(x)$ itself as well
      • not a zk-SNARK as $f(r)$, $g(r)$ is revealed
  • F-IOP
    • goal: boost functional commitment
      • ⇒ SNARK for general circuits
    • let $C(x,w)$ be arith. circuit and $x\in F_p^n$
    • F-IOP: proof system that proves $\exists w:C(x,w)=0$ as follows
      • $setup(C)\to pp,vp$
        • $=(f_0,f_{-1},\dots f_{-s})$
        • oracles for functions in $F$
          • can be replaced into commitments
      • proof
        • prover: sends $f_1\in F$
          • verifier: sends $r_1\stackrel{\$}{\leftarrow }{F}_p$
        • prover: sends $f_2\in F$
          • verifier: sends $r_2\stackrel{\$}{\leftarrow }{F}_p$
        • … repeated t times
          • and verifier: runs ${\text{verify}}^{f_{-s},\dots f_t}(x,r_1,\dots ,r_{t-1})$
    • properties
      • complete: $\exists w:C(x,w)=0$ then $Pr[V=1]=1$
      • knowledge sound: unable to fake knowledge
  • Example poly-IOP
    • $C(X,W)=0$ ↔ $X\subseteq W\subseteq F_p$
    • prover
      • $f(Z):={\prod }_{w\in W}(Z-w)$
      • $g(Z):={\prod }_{x\in X}(Z-x)$
      • $q(Z):=f/g\in F_p^{\le d}[X]$
        • as $X\subseteq W$, $f/g$ is a polynomial
      • sends: $f,q$
    • verifier
      • $g(X):={\prod }_{x\in X}(Z-x)$
      • $r\stackrel{\$}{\leftarrow }{F}_p$ (public)
      1. query $w\leftarrow f(r)$
      2. query $q^{\prime }\leftarrow q(r)$
      3. compute $x\leftarrow g(r)$
      4. accept if $x\cdot q^{\prime }=w$
    • V accepts ⇒ $f=g\cdot q$ w.h.p. ⇒ $X\subseteq W$
      • kind of reversed logic
    • Extractor: $E(X,f,q,r)$
      • output $W$ by computing all roots of $f(Z)$
  • IOP Zoo
    • ⇒ SNARKs for general circuits
    • Poly-IOP (w/ Poly-Commit)
      • Sonic
      • Marlin
      • Plonk
    • Multilinear-IOP (w/ Multilinear-Commit)
      • Spartan
      • Clover
      • Hyperplonk
    • Vector-IOP (w/ Merkle)
      • STARK
      • Breakdown
      • Orion
    • ⇒ SNARK (non-interactive via Fiat-Shamir)
  • SNARKs in practice
    • programs: written in Domain-Specific Language
      • Circom, ZoKrates, Leo, Cairo, Noir..
    • compiles to SNARK friendly format
      • circuit, R1CS, …, EVM byte code
    • → SNARK backend prover (heavy computation)
      • outputs $\pi$

Introduction

Cornell Format

Date:

Reviewed:

Topic / Chapter:

Notes

Date: 2024년 7월 2일

Reviewed:

Topic / Chapter:

❓Questions

Notes

• Programming ZKP

  • Programming ZKP

    • converting idea into work
      • programmer: idea → high-level language
      • compiler: high-level language → R1CS
        • focus of today
      • setup: R1CS → param
      • prove: param → ZKP
      • verify: param * ZKP → {0,1}

  • ZKP basics

    • ZKPs for a predicate $\varphi$
      • prover knows $\varphi ,x,w$
      • verifier: knows $\varphi ,x$
      • proof $\pi$: shows $\varphi (x,w)$ holds
        • but not reveals $w$
      • what can be $\varphi$?
    • $\varphi$ in theory: any NP problem
      • e.g. $w$: factorization of $x$
      • e.g. $w$ secret key for public key $x$
      • etc.
    • $\varphi$ in practice: arithmetic circuit over input $x,w$

  • Arithmetic circuits (ACs)

    • domain: prime field
      • $p$: a large (~255 bit) prime
      • $Z_p$: integers $\mathrm{mod}p$
        • (modular) operations: $+,\times ,=$
    • approach 1: as a systems of field equations
      • e.g. $w_0\times w_0\times w_0=x$
        • $w_1\times w_1=x$
    • approach 2: as circuits

      • directed, acyclic graph

      • nodes: inputs, gates, constants

      • edges: wires / connections

      • (for the same eg)

        graph LR
          w_0[w_0] --> OPtimes_0([x])
          w_0[w_0] --> OPtimes_0([x])
          w_0[w_0] --> OPtimes_0([x])
          OPtimes_0([x]) --> OPeq_0([=])
          w_1[w_1] --> OPtimes_1([x])
          w_1[w_1] --> OPtimes_1([x])
          OPtimes_1([x]) --> OPeq_1([=])
          
          x[x] --> OPeq_0([=])
          x[x] --> OPeq_1([=])
          
        

  • Approach 3: Rank 1 Constraint Systems (R1CS)

    • R1CS: format for ZKP ACs
    • definition (linear combination)
      • $x$: field elements $x_1,\dots ,x_l$
      • $w$: $w_1,\dots ,w_{m-l-1}$
      • $\varphi$: $n$ equations of form
        • $\alpha \times \beta =\gamma$
        • $\alpha ,\beta ,\gamma$: affine combination of variables / constants
      • examples
        • $w_2\times (w_3-w_2-1)=x_1$
          • $\alpha =w_2$
          • $\beta =w_3-w_2-1$
          • $\gamma =x_1$
        • $w_2\times w_2=w_2$
        • ❌$w_2\times w_2\times w_2=x_1$
          • $w_2\times w_2=w_4$
          • $w_4\times w_2=x_1$
    • matrix definition
      • $x$: vector of $l$ field elements
      • $w$: vector of $m-l-1$ field elements
      • $\varphi$: matrices $A,B,C\in {\mathbf{Z}}_p^{n\times m}$
        • $z=(1||x||w)\in {\mathbf{Z}}_p^m$
        • holds when $Az\circ Bz=Cz$
          • i.e. element-wise product
      • each rows of $A,B,C$: coefficients for each R1CS
        • width: 1 more than no. of variables to include constants

  • Writing an AC as R1CS

    • example illustrated

      graph LR
        w_0[w_0] --> OPtimes_0([x])
        w_1[w_1] --> OPtimes_0([x])
        w_1[w_1] --> OPtimes_1([x])
        OPtimes_0([x]) --w_2--> OPplus_0([+])
        OPplus_0([+]) --w_3--> OPeq_0([=])
        
        x_0[x_0] --> OPplus_0([+])
        x_0[x_0] --> OPtimes_1([x])
        OPtimes_1([x]) --w_4--> OPeq_0([=])
      
        
      

    • procedure

      1. write intermediate $w$s
      2. write equations
         1. $w_0\times w_1=w_2$
         2. $w_3=w_2+x_0$
            1. $\beta =1$; $\gamma =w_2+x_0$
         3. $w_1\times x_0=w_4$
         4. $w_3=w_4$

    • now: how to convert high-level $\varphi$ to R1CS?

      • R1CS: like assembly
      • conversion from $\varphi \to$R1CS: w/ libraries, compilers, etc.

    • most zk products: built similarly

      • high-level code → compiler / library → R1CS → ZK proof system

    • example: Zcash

      • $\varphi$: definition of “spending money anonymously”
      • circuit: involves
        • Merkle tree
        • Pedersen hash
        • signatures
        • spend logic
        • etc.
      • written in Bellman library ⇒ R1CS
        • three tool types:
          • HDL
          • Library
          • PL + compiler
      • R1CS: fed into Groth16 (runs on user computer)

• Using an HDL

  • Circom basics

    • Circom: Hardware Description Language
      • ≠ programming languages

    	PL	HDL
    Objects	variables
    operations
    programs / func	wires
    gates
    circuit / sub-circ
    Actions	mutate variables
    call functions	connect wires
    create sub-circuits

    • HDLs for Digital Circuits
      • Verilog (dominate)
      • System Verilog
      • VHDL
      • Chisel
    • Circom: HDL for R1CS
      • wires: R1CS variables
      • gates: R1CS constraints
      • circuit: does 2 things
        • sets variable values
        • create R1CS constraints

  • Circom: base language

    • example code

      template Multiply() {
      	signal input x;
      	signal input y;
      	signal output z;
      	
      	z <-- x * y;
      	z === x * y;
      	
      }
      
      component main {public [x]} =
      	Multiply();
      

    • a template: is a (sub) circuit

    • a signal is a wire

      • input or output as property

    • <--: sets signal values

    • ===: creates constraints

      • must be rank-1
      • one side: linear; another: quadratic

    • <==: does both (shorthand)

    • specify that this template is the main

      • also which signals are public and which are not
      • input: implicitly private
      • output: implicitly public

  • Circom: metaprogramming language

    • example

      template RepeatedSquaring(n) {
      	signal input x;
      	signal output y;
      	
      	signal xs[n+1];
      	xs[0] <== x;
      	for (var i = 0; i < n; i++) {
      		xs[i+1] <== xs[i] * xs[i];
      	}
      	y <== xs[n];
      }
      
      component main {public [x]} = 
      	RepeatedSquaring(1000);
      

    • template arguments (fixed at compile time)

      • e.g. length for signal arrays

    • variables

      • mutable
      • not signals
      • evaluated at compile-time

    • loops

    • if statements

    • array accesses

  • Circom: witness computation & sub-circuits

    • guaranteeing non-zero

      template NonZero() {
      	signal input in;
      	signal inverse;
      	inverse <-- 1 / in; // not R1CS
      	1 === in * signal; // is R1CS
      }
      
      template Main() {
      	signal input a; signal input b;
      	component nz = NonZero();
      	nz.in <== a; // quits if a == 0
      	0 === a * b; // asking: is B zero?
      }
      

    • idea: to ask whether there exists multiplicative inverse

    • <--: more general than ===

    • components hold sub-circuits

      • access inputs / outputs w/ dot-notation

• Circom Tutorial

  • Implementing sudoku
    • $x$: puzzle
    • $w$: solution
    • $\varphi$: goal & rules
      • for simplification: forcing only no-duplicates-in-a-row rule
    • roadmap
      • implement notEqual (i.e. difference ≠ 0)
      • implement Distinct(n) from not Equal
      • implement Bits4 or in % 16 === in
      • implement OneToNice by computing
        • Bits4 on in-1
        • Bits4 on in+6
      • implement Sudoku by
        • check whether all numbers are in range
        • check whether solution matches the puzzle
        • check whether all numbers in the same row are distinct

• Using a Library

  • Library for R1CS

    • Circom key features
      • direct control over constraints
      • custom language
        • can be good / bad
    • alternative: library in a host language
      • Rust, OCaml, C++, Go…
    • key type: constraint system
      • maintains state about R1CS constraints & variable
        • i.e. value for variables & $A,B,C$
      • key operations
        • create variable
        • create linear combinations of variables
        • add constraint

  • Pseudo-rust example

    • variable creation
      • cs.add_var(p, v) -> id
      • cs: constraint system
      • p: visibility of variable
      • v: assigned value
      • id: variable handle
    • linear combination creation
      • cs.zero(): returns the empty LC
      • lc.add(c, id) -> lc'
      • id: variable (handle)
      • c: coefficient
      • lc' := lc + c * id
    • adding constraints
      • cs.constrain(lc_a, lc_b, lc_c)
      • adds constraint lc_a * lc_b = lc_c

  • Example code: Boolean AND

    #![allow(unused)]
    fn main() {
    fn and(cs: ConstraintSystem, a: Var, b: Var) -> Var {
    	let result = cs.new_witness_var(|| a.value() & b.value());
    	self.cs.enforce_constrant(
    		lc!() + a,
    		lc!() + b,
    		lc!() + result,
    	);
    	result
    }
    }

  • Leverage language abstractions

    • e.g. using structs, operator overloading, etc.

      #![allow(unused)]
      fn main() {
      struct Boolean {var: Var};
      
      // i.e. & overloading
      impl BitAnd for Boolean {
      	fn and(self: Boolean, other: Boolean) -> Boolean {
      		// same as before
      		Boolean {var: result}
      	}
      }
      }

    • example usage

      #![allow(unused)]
      fn main() {
      let a = Boolean::new_witness(|| true);
      let b = Boolean::new_witness(|| false);
      (a & b).enforce_equal(Boolean::FALSE);
      }

    • many different gadget libraries

      • libsnark: gadgetlib (C++)
      • arkworks: r1cs-srd + crypto-primitives (Rust)
      • Snarky (Ocaml)
      • Gnark (Go)

  • Witness computation

    • can perform arbitrary computations to generate witnesses
      • more freedom as it’s general-purposed language!

    #![allow(unused)]
    fn main() {
    let a = Boolean::new_witness(|| (4 == 5) & (x < y));
    let b = Boolean::new_witness(|| false);
    (a & b).enforce_equal(Boolean::FALSE);
    }

    • closure / lambda ||: executed only during proving

• Arkworks Tutorial (Rust)

• Using a Compiler

  • HDL & circuit libraries comparison

    • differences:
      • host language vs. custom language
    • similarities
      • explicit wire creation
      • explicit constraint creation
      • 👨‍🏫is it necessary?
        • No! by creating a new language, we can avoid it!

  • ZoKrates syntax

    #![allow(unused)]
    fn main() {
    type F = field;
    
    def main(public F x, private F[2] ys) {
    	field y0 = y[0];
    	field y1 = y[1];
    	assert(x = y0 * y1);
    }
    }

    • struct syntax for custom types

    • variables: contain values during execution / proving

    • can annotate privacy

    • “assert” creates constraints

    • main function exists

    • other language features

      • integer generics
      • arrays
      • variables
        • mutable
      • fixed-length loops
      • if expressions
      • array accesses

    • feature example

      #![allow(unused)]
      fn main() {
      def repeated_squaring<N>(field x) -> field {
      	field[N] mut xs;
      	xs[0] = x;
      	for u32 i in 0..N {
      		xs[i + 1] = xs[i] * xs[i];
      	}
      	return xs[N];
      }
      
      def main (public field x) -> field {
      	repeated_squaring::<1000>(x)
      }
      }

    • short: no way to compute witnesses

      • all witnesses: must be provided as input

        #![allow(unused)]
        fn main() {
        def main(private field a, public field b) {
        	assert(a * b == 1)
        }
        }

• ZoKrates Tutorial (~= Rust)

  • Compilation
    • compile: zokrates compile -i root.zok
    • setup: zokrates setup
    • witness computation: zokrates compute-witness -a 1 0 0 2 1 2 1 2
      • or: [[1,0], [0,2]] and [[1,2],[1,2]]
    • proof generation: zokrates generate-proof
    • verification: zokrates verify

• Overview of Prominent ZKP Toolchains

  • A quick tour

    • toolchain type

      • HDL: language for circuit synthesis description
      • library: library for describing circuit synthesis
      • PL + compiler: a language, compiled to a circuit

    • organized view

      language type	standalone?
      	no	yes
      circuit	library (Arkworks)	HDL (Circom)
      program		PR (ZoKrates)

    • pros and cons

      type	Circom	Arkworks	ZoKrates
      pros	clear constraints
      elegant syntax	clear constraints
      as expressive as Rust	easiest to learn
      elegant syntax
      cons	hard to learn
      limited abstraction (no types, etc.)	need to know Rust
      few optimizations	limited witness computation

    • other toolchains

      HDL	Library	PL + Compiler
      Circom	Arkworks (Rust)	ZoKrates
      	Gadgetlib (C++)	Noir
      	Bellman (Rust)	Leo
      	Snarky (OCaml)	Cairo
      	PLONKish (Rust)

    • timeline

      

    • shared compiler infrastructure?

      • source: (many PLs)
      • target: R1CS, Plonk, AIR
      • common techniques
        • Boolean
        • fixed-width ints
        • variables
        • mutation
        • structures
        • control flow
        • optimization
        • arrays
      • 👨‍🏫can we build a library to create a PL for ZKP with this common ground?
        • attempt: CirC

Introduction

Date:

Reviewed:

Topic / Chapter: SNARKs via Interactive Proofs

❓Questions

Notes

• Interactive Proofs
  • Motivation
    • computation-limited verifier
      • wants data analysis
    • verifier: holds data summary
      • queries to cloud provider w/ data
        • or: “challenges”
      • cloud provider: provides answer
    • interactive proofs (formally)
      • $P$ solves problem, tells $V$ the answer
        • then conversation goes
        • $P$’s goal: convince $V$ the answer is correct
      • requirements
        • completeness: an honest $P$ can convince $V$
        • (statistical) soundness: $V$ will catch $P$’s lie w.h.p.
        • if soundness holds only against “eff” provers: then it is argument not proof
  • Interactive proofs vs. arguments
    • soundness vs. knowledge soundness
      • $C(x,w)\to F$
      • soundness: $V$ accepts → $\exists w$ s.t. $C(x,w)=0$
      • knowledge soundness: $V$ accepts → $P$ “knows” $w$ s.t. $C(x,w)=0$
        • 👨‍🏫stronger!
    • standard soundness: meaningful even when knowledge soundness isn’t
      • as there is no “natural witness”
      • e.g. $P$ claims that output of $V$’s program on $x$ is 42
    • reverse: prover claims he knows secret key for a certain BTC wallet
      • or: preimage of hash that gives 0
      • many “witnesses” exist
    • public verifiability
      • only convincing the party that is choosing random challenges
        • others: can’t trust the proposed verifier
      • if interactive: each run only convinces one party
      • for public coin protocols: Fiat-Shamir is used
        • to make it non-interactive
• SNARKs from Interactive Proofs
  • SNARK example
    • procedure
      • $P$: commits cryptographically to $w$
      • reveals “just enough” info on commitment to allow $V$ to run checks
      • render non-interactive via Fiat-Shamir
• Review of Functional Commitments
  • Functional commitments
    • different types
      • polynomial commitments
        • to univariate $f(X)\in F_p^{\le d}[X]$
      • multilinear commitments
        • to multilinear $f\in F_p^{\le 1}[X_1,\dots X_k]$
      • vector commitments (e.g. Merkle trees)
        • to $\overrightarrow{u}=(u_1,\dots ,u_d)\in F_p^d$
        • open cells: $f_{\overrightarrow{u}}(i)=u_i$
  • Merkle trees: the commitment
    • uses: C.R. hash function
    • opening proof size: $O(\log n)$
    • example: univariate $f(X)\in F_7^{(\le d)}[X]$
      • $m_1=H(f(0),f(1))$
        • … $m_4=H(f(6),\ast )$
      • $h_1=H(m_1,m_2)$
      • $k_1=H(h_1,h_2)$
      • to prove value $f(4)$, must provide
        • $k_1$, $h_1$, $m_4$, $f(4),f(5)$
    • notation
      • $P$ Merkle-commits to all evaluations of $f$
      • upon request of $f(r)$, $P$ reveals all associated leaf along w/ opening info
      • two problems
        • no. of leaves: $|F|$
          • takes at least $|F|$ to compute commitment
          • want time proportional to degree bound $d$
        • $V$ does not know $f$ has at most degree $d$
• Interactive Proof Design: Technical Preliminaries
  • SZDL lemma
    • FACT: let $p\ne q$ be univariate polynomials of degree at most $d$
      • then $P{r}_{r\in F}[p(r)=q(r)]\le \frac{d}{|F|}$
      • $p(r)-q(r)$ has at most $d$ zeros
    • SZDL lemma: multivariate generalization
      • let $p\ne q$ be $l$-variate polynomials of total degree at most $d$
      • then $P{r}_{r\in F^l}[p(r)=q(r)]\le \frac{d}{|F|}$
      • using multivariate to lower the degree and make computation quicker
  • Low-degree and multilinear extensions
    • extension: given $f:\{0,1{\}}^l\to F$, a $l$-variate polynomial $g$ over $F$: extend $f$
      • if $\forall x\in \{0,1{\}}^{l}f(x)=g(x)$
    • multilinear extensions: any function $f:\{0,1{\}}^l\to F$ has unique multilinear extension (MLE) $\tilde{f}$
      • multilinear: polynomial has degree at most 1 in each var
      • e.g. $(1-x_1)(1-x_2)$, but not in $x_1^2{x}_2$
  • Example

    • let $f:\{0,1{\}}^2-F$ s.t.

      1	2
      8	10

    • $\tilde{f}:F^2\to F$ (multilinear extension)

      • $\tilde{f}(x_1,x_2)=(1-x_1)(1-x_2)+2(1-x_1)x_2+8x_1(1-x_2)+10x_1{x}_2$
        • actually: quite similar to SoP approach!

      1	2	3	4	5	6
      8	10	12	14	16	18
      15	18	21	24	27	30
      22	26	30	34	38	52
      29	34	39	44	49	56

      • True as:
        • $\tilde{f}(0,0)=1$
        • $\tilde{f}(0,1)=2$
        • $\tilde{f}(1,0)=8$
        • $\tilde{f}(1,1)=10$

    • non-multilinear extension

      • $f:g(x_1,x_2)=-x_1^2+x_1{x}_2+8x_1+x_2+1$

      1	2	3	4	5	6
      8	10	12	14	16	18
      13	16	19	22	25	28
      16	20	24	28	32	36
      17	22	27	32	37	42

      • True as:
        • $g(0,0)=1$
        • $g(0,1)=2$
        • $g(1,0)=8$
        • $g(1,1)=10$
  • Evaluating multilinear extensions quickly
    • fact: given as input $2^l$ evaluations of a function $f$
      • $\forall r\in {\mathbf{F}}^l\exists O(2^l)$-time algo to evaluate $\tilde{f}(r)$
      • i.e. by listing all its values with manually
    • sketch: using Lagrange interpolation
    • define ${\tilde{\delta }}_w(r)={\prod }_{i=1}^l(r_i{w}_i+(1-r_1)(1-w_i))$
      • i.e. multilinear Lagrange basis polynomial corresponding to $w$
      • or: PoS, but from analog values of $r$
        • ($w$ being digital)
    • fact: $f(r)={\sum }_{w\in \{0,1{\}}^l}f(w)\cdot {\delta }_w(r)$
    • $\forall w\in \{0,1{\}}^l$, ${\tilde{\delta }}_w(r)$ can be computed w/ $O(l)$ field operations
      • yields an $O(l{2}^l)$-time also
      • can reduce to $O(2^l)$ time via DP
• Sum-Check Protocol
  • Sum-check protocol

    • [LFKN90]

    • input: $V$ given oracle access to a $l$-variate polynomial $g$ over field $\mathbf{F}$

      • i.e. access to $g(i)$ where $i\in \mathbf{F}$

    • goal: compute the quantity

      • ${\sum }_{b_1\in \{0,1\}}{\sum }_{b_2\in \{0,1\}}\cdots {\sum }_{b_l\in \{0,1\}}g(b_1,\dots ,b_l)$
      • idea: outsource the computation to prover so that it takes $O(n)$ time instead of $O(2^n)$

    • 👟Start: $P$ sends claimed answer $C_1$

      • protocol checks that:
      • $C_1={\sum }_{b_1\in \{0,1\}}{\sum }_{b_2\in \{0,1\}}\cdots {\sum }_{b_l\in \{0,1\}}g(b_1,\dots ,b_l)$

    • 👟Round 1: $P$ sends univariate polynomial $s_1(X_1)$ claimed to equal

      $H_1(X_1):={\sum }_{b_2\in \{0,1\}}\cdots {\sum }_{b_l\in \{0,1\}}g(X_1,b_2\dots ,b_l)$

      • i.e. output if prover was honest

    • $V$ checks that $C_1=s_1(0)+s_1(1)$

      • or: ${\sum }_{b_1\in \{0,1\}}{s}_1(b_1)$

    • if check passes: safe to believe that $C_1$ is the correct answer

      • if $V$ believes $s_1=H_1$
      • i.e. check $s_1(r_1)=H_1(r_1)$ where $r_1\leftarrow R$
      • $V$ can compute $s_1(r_1)$ directly from $P$’s first message, not $H_1(r_1)$ though

    • 👟Round 2: ($P$ sends $s_2(X_2)$ and) $P$ recursively check that $s_1(r_1)=H_1(r_1)$

      • i.e. that $s_1(r_1)={\sum }_{b_2\in \{0,1\}}\cdots {\sum }_{b_l\in \{0,1\}}g(r_1,b_2,\dots ,b_l)$

    • 👟Round $l$: ($P$ sends $s_l(X_l)$ and) $P$ check that $H_l:=g(r_1,r_2\dots ,X_l)$

      • $V$: checks that $s_{l-1}(r_{l-1})=s_l(0)+s_l(1)$
      • by picking $s_l(r_l)=g(r_1,\dots r_l)$

    • general idea: checking $s_i$ only on first occurrence, trusting it there after

• Analysis of Sum-Check Protocol
  • Completeness
    • holds by design
    • if $P$ sends the prescribed messages: all tests will pass
  • Soundness
    • if some other message was sent: $V$ rejects w/ probability of at least $1-\frac{l\cdot d}{|\mathbf{F}|}$
    • e.g. $|\mathbf{F}|\approx 2^{128}$, $d=3$, $l=60$
      • then soundness error $\le 3\cdot 60/2^{128}=2^{-120}$
    • proof: by induction on no. of var $l$
      • base case: $l=1$; $P$ sends $s_1(X_1)$ claims to equal $g(X_1)$
        • $V$ picks $r_1$ at random, checks that $s_1(r_1)=g(r_1)$
        • if $s_1\ne g$, then $P{r}_{r_1\in \mathbf{F}}[s_1(r_1)=g(r_1)]\le \frac{d}{|\mathbf{F}|}$
      • inductive case $l>1$
        • recall: $P$’s first message $s_1(X_1)$ claimed to equal $H_1(X_1):={\sum }_{b_2\in \{0,1\}}\cdots {\sum }_{b_l\in \{0,1\}}g(X_1,b_2,\dots ,b_l)$
        • $V$ picks $r_1$ at random, (recursively) checks that $s_1(r_1)=H_1(r_1)$
        • if $s_1\ne H_1$, then $P{r}_{r_1\in \mathbf{F}}[s_1(r_1)=H(r_1)]\le \frac{d}{|\mathbf{F}|}$
        • if $s_1(r_1)\ne H(r_1)$, $P$ is left to prove a false claim in rec. call
          • applies sum-check to $l-1$ variate
          • by induction: $P$ convinces $V$ w/ probability at most $\frac{d(l-1)}{|\mathbf{F}|}$
    • summary: if $s_1\ne H_1$, $V$ accepts at most
      • $$\begin{gathered} P{r}_{r_1\in \mathbf{F}}[s_1(r_1)=H(r_1)] \\ =P{r}_{r_2,\dots r_l\in \mathbf{F}}[\text{V accepts}|s_1(r_1)\ne H(r_1)] \\ \le \frac{d}{|\mathbf{F}|}+\frac{d(l-1)}{|\mathbf{F}|}\le \frac{dl}{|\mathbf{F}|} \end{gathered}$$
  • Cost of the protocol
    • total communication: $O(dl)$ field elements
      • $P$ sends $l$ messages, each at univariate degree $d$
      • $V$ sends $l-1$ messages, each w/ 1 field element
    • $V$’s runtime: $O(dl+[\text{time(g)}])$
    • $P$’s runtime (at most)
      • $O(d\cdot 2^l\cdot [\text{time(g)}])$
• Sum-Check Protocol Application
  • Counting triangles
    • input: $A\in \{0,1{\}}^{n\times n}$
      • representing adjacency matrix of a graph
    • desired output: ${\sum }_{(i,j,k)\in [n{]}^3}{A}_{ij}{A}_{jk}{A}_{ik}$
    • fastest known algorithm: runs in matrix-multiplication time
      • i.e. ~= $n^{2.37}$ (super linear time)
    • IP: let verifier run in $O(n^2)$ time (minimum possible)
  • Protocol

    • protocol: view $A:\{0,1{\}}^{\log n}\times \{0,1{\}}^{\log n}\to F$

      

    • $\tilde{A}$: multilinear extension of $A$

    • define polynomial $g(X,Y,Z)=A(X,Y)A(Y,Z)\tilde{A}(X,Z)$

    • apply the sum-check protocol to compute

      • ${\sum }_{(a,b,c)\in \{0,1{\}}^{3\log n}}g(a,b,c)$
  • Costs
    • total communication: $O(\log n)$
    • $V$ runtime: $O(n^2)$
    • $P$ runtime: $O(n^3)$
    • $V$ runtime: dominated by evaluating
      • $g(r_1,r_2,r_3)=A(r_1,r_2)A(r_2,r_3)\tilde{A}(r_1,r_3)$
• SNARK for Circuit-Satisfiability

  • SNARK for circuit-satisfiability

    • $P,V$: agreed on circuit $C$ over $\mathbf{F}$ size $S$ and output $y$
      • $P$ claims to know $w$ s.t. $C(x,w)=y$
      • let $x$ be empty for simplicity
    • transcript $T$ for $C$: assignment of a value to every gate
      • is correct if it assigns gate values upon evaluating $C$ on a valid $w$

    

  • Transcript as a function

    • with domain $\{0,1{\}}^{\log S}$
    • assign each gate in $C$ a ($\log S$)-bit label and view $T$ as a function
      • mapping gate labels to $\mathbf{F}$

    

    • and final output: always $T(1,\dots ,1)$ (last gate to be computed)
• Polynomial IOP Underlying the SNARK

  • Polynomial IOP

    • $P$’s first message is a ($\log S$)-variate polynomial $h$ claimed to extend a correct transcript $T$
      • i.e. $h(x)=T(x)\forall x\in \{0,1{\}}^{\log s}$
    • $V$: needs to check this, but only able to learn few evaluation of $h$ (not $S$)

  • Intuition on $h$

    • $h$: distance-amplified encoding of $T$
    • domain of $T$: $\{0,1{\}}^{\log S}$
      • but domain of $h$: much larger (${\mathbf{F}}^{\log S}$)
      • 👨‍🏫small difference in $T$ → vast difference (almost all) in extension
        • due to distance-amplifying nature
        • by Schwartz-Zippel

    

  • Two-step plan

    • step 1: given any ($\log S$)-variate polynomial $h$, identify a related ($3\log S$)-variate polynomial $g_h$ s.t.
      • $h$ extends a correct transcript $T$ ↔ $g_h(a,b,c)=0\forall (a,b,c)\in \{0,1{\}}^{3\log S}$
        • or: “vanishing” over Boolean hypercube
        • i.e. if $h$ is not a correct transcript: $\exists a,b,c\text{ s.t. }{g}_h(a,b,c)\ne 0$
        • ~= abstraction of messy structure?
      • also: to evaluate $g_h(r)$ at any input: evaluating $h$ at 3 inputs are enough
    • step 2: design an IP to check
      • $g_h(a,b,c)=0\forall (a,b,c)\in \{0,1{\}}^{3\log S}$
      • in which $V$ only needs to evaluate $g_h(r)$ at one point $r$

  • Sketch

    • step 1 sketch: define $g_h(a,b,c)$ via:
      • $\widetilde{add}(a,b,c)\cdot (h(a)-(h(b)+h(c)))+\widetilde{mult}(a,b,c)\cdot (h(a)-(h(b)\cdot h(c)))$
      • $\widetilde{add}(a,b,c)$: gets 3 Boolean vectors in input
        • returns 1 iff $a$ is addition gate and 2 $n$ neighbors are $b,c$
        • else 0
      • $\widetilde{mult}(a,b,c)$: gets 3 Boolean vectors in input
        • returns 1 iff $a$ is multiplication gate and 2 $n$ neighbors are $b,c$
        • else 0
    • properties
      • $g_h(a,b,c)=h(a)-(h(b)+h(c))$
        • if $a$ is label computing sum of $b,c$
      • $g_h(a,b,c)=h(a)-(h(b)\cdot h(c))$
        • if $a$ is label computing multiplication of $b,c$
      • $g_h(a,b,c)=0$ otherwise
      • $g_h$ computation: can be outsourced to $P$ as it only depends on wiring structure, and thus being able to be committed
    • step 2: how to check $g_h(a,b,c)=0\forall (a,b,c)\in \{0,1{\}}^{3\log S}$
      • by evaluating $g_h$ at a single point?
    • if $g_h$ were a univariate polynomial $g_h(X)$
      • and we need to check that $g_h$ vanishes over some set $H\subseteq \mathbf{F}$, not $\{0,1{\}}^{3\log S}$
    • fact: $g_h(x)=0\forall x\in H$ ↔ $g_h$ is divisible by $Z_H(x):={\prod }_{a\in H}(x-a)$
      • $Z_H$: vanishing polynomial for $H$
      • 🧑‍🎓kind of trivial
    • polynomial IOP
      • $P$ sends a polynomial $q$ s.t. $g_h(X)=q(X)\cdot Z_H(X)$
      • $V$ checks this by picking a random $r\in \mathbf{F}$ and checking $g_h(r)=q(r)\cdot Z_H(r)$

  • Actual protocol

    • above: not works as $g_h$ is not univariate
    • computing (finding $q$) is expensive
      • in final SNARK: it would be applying poly-commit to additional polynomials
      • Marlin, PlonK, Groth16 does this, though
    • solution: use the sum-check protocol
      • handles multivariate polynomials
      • doesn’t require $P$ to send additional large polynomials
• Polynomial IOP for Circuit-Satisfiability
  • Recall sum-check
    • goal: compute the quantity (all sum)
    • proof length: roughly total degree of $g$
    • no. of round: $l$
    • $V$ time: ~= time to evaluate $g(r)$
      • not necessarily revealing info on $g$ as long as it knows $g(r)$ for random $r$
  • General idea
    • (works over integers, for ease of explanation)
      • $V$: checks ${\sum }_{a,b,c\in \{0,1{\}}^{\log S}}{g}_h(a,b,c{)}^2$
      • if all terms are 0: sum is 0
        • any non-zero term: cause it to change
    • at the end of protocol: $V$ evaluates $g_h(r_1,r_2,r_3)$
      • suffices to evaluate $h(r_1),h(r_2),h(r_3)$
        • 👨‍🏫in practice, this dominates the runtime
      • outside of these: $V$ runs in time $O(\log S)$
        • no. of variables
      • $P$ performs $O(S)$ field operations given $w$
        • even if there was no proof of correctness: same time