SNARK - Proof Of Statement

• has to be fast and short Zero Knowledge - reveals nothing about subject of Statement.

Arithmetic Circuits - C

• DAG where
  • internal nodes are +, - or x
  • leaf nodes are 1, x1, x2 … xn
  • size of C = number of internal nodes(+, -, x)

Argument System

• Public Arithmetic Circuit C(x, w) → F
  • x is a tuple of n public statements
  • w is a tuple of m private witnesses
  • Two entities: Prover and Verifier
    • Prover convinces the Verifier that there exists some w for which C(x, w) = 0
    • May require Conversation

Preprocessing Argument Systems

• There is a preprocessing setup S : S(C) → public parameters (Sp, Sv)
• Prover : P(Sp, x, w) → proof π
• Verifier : V(Sv, x, π) → Accept / Reject
• Removes the need of a Conversation. Prover sends proof π to Verifier who can only Accept or Reject

Requirements

• Complete : If Prover is honest, then the verifier must Accept.
• Knowledge Sound : If Verifier Accepts, then Prover must know w such that, C(x,w) = 0.
• Zero Knowledge (Optional) : (C, Sp, Sv, x, π) reveal nothing about w

SNARK - a Succinct ARgument of Knowledge

• |π| = O(log(|C|), K)

• time(V) = O( |x|, log(|C|), K)