Zero Knowledge Proof: SNARK
Table of Contents
In this post, I will try to describe my knowledge about SNARK. By the time I’m writing this post, ZK Hack Discord is running ZK Whiteboard Study Group and they are discussing about SNARK, so maybe I’m lucky :D
Resources
ZK Whiteboard Sessions - Module One: What is a SNARK? by Dan Boneh
zk-SNARKs: A Gentle Introduction by Anca Nitulescu
Detail
What is a SNARK ?
In the class of non-interactive proofs, a particularly interesting concept for proving integrity of results for large computations is that of SNARK, i.e., succinct non-interactive argument of knowledge. By this term, we denote a proof system which is:
Succinct: the size of the proof is very small compared to the size of the statement or the witness, i.e., the size of the computation itself.
Non-interactive: it does not require rounds of interaction between the prover and the verifier.
Argument: we consider it secure only for provers that have bounded computational resources, which means that provers with enough computational power can convince the verifier of a wrong statement.
Knowledge-sound: it is not possible for the prover to construct a proof without knowing a certain so-called witness for the statement; formally, for any prover able to produce a valid proof, there is an extractor capable of extracting a witness (”the knowledge”) for the statement.
Examples:
I know an such that
I know such that
SNARK systems can be further equipped with a zero-knowledge property that enables the proof to be done without revealing anything about the intermediate steps (the witness). We will call these schemes zk-SNARKs.
zk-SNARK is really fit with blockchain, so we have lots of applications
Mathematical Background
Arithmetic Circuits
Let is a finite field with , then we can define Arithmetic Circuits as:
A directed acyclic graph (DAG) where internal nodes are labeled or , with input and .
An -variate polynomial with an evaluation recipe
A map , with = number of gate
Argument Systems
A preprocessing argument system is made up by three algorithms: Setting Algorithm, Prove Algorithm and Verify Algorithm (S, P, V):
public parameter for prover and verifier
proof
accept or reject
An argument system requires:
Complete:
Soundness: If accepts, then “knows” such that , and if doesn’t know , then
Zero Knowledge:(Optional) reveal nothing about
SNARK: Succinct Non-interactive ARgument of Knowledge
A succinct preprocessing argument system is made up by three algorithms: Setting Algorithm, Prove Algorithm and Verify Algorithm (S, P, V):
public parameter for prover and verifier
short proof ;
accept or reject, fast to verify;