Snark: Zero Knowledge Proofs

Interactive Zero Knowledge Proof

Alice wants to convince Bob that she executed f(a,b) correctly. Alice tells Bob that given the inputs 1,2 f() outputs 3. Bob wishes to verify so he gives Alice inputs 2 & 3, f() outputs 5. Bob and Alice go back and forth, until Bob is satisfied that Alice proved f(a,b) executed correctly. This is an interactive zero knowledge proof.

Non Interactive Zero Knowledge Proof

Alice precompiles f(a,b) for a multitude of inputs, Alice provides all inputs and outputs to Bob, Bob can verify that given all the inputs and outputs f(a,b) executed correctly. This is a non-interactive zero knowledge proof.

SNARKs

These proofs require trusted setup. They are 188 bytes no matter what they are proving. This trusted setup allows Alice to prove f(a,b) with a single 188 byte proof.

STARKs

Does not require a trusted setup. Logarithmic in size. Fast verification. Currently highly experimental.

Bulletproofs

Do not require a trusted setup. Are logarithmic in size of the complexity of that function.

Summary

STARKS find their value in any proof that requires fixed size and fixed verification time with a trusted setup. Ideal for state transitions and fixed block sizes.

Bulletproofs allow for linear verifiable non trusted setup proofs. Ideal for smart contracts. The complexity of the smart contract could increase the proof complexity to the point where it is no longer verifiable on-chain.