Skip to content

Instantly share code, notes, and snippets.

@mimoo
Last active June 17, 2022 00:18
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mimoo/a19e5b4c6e037691e7cb4264640c35e9 to your computer and use it in GitHub Desktop.
Save mimoo/a19e5b4c6e037691e7cb4264640c35e9 to your computer and use it in GitHub Desktop.
Zero-Knowledge Proofs FAQ

What's a ZK-SNARK?

A Zero-Knowledge Succinct Non-interactive adaptive ARgument of Knowledge is a term coined by Nir Bitansky† Ran Canetti‡ Alessandro Chiesa§ Eran Tromer in 2011 (From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again).

What are succint proofs?

the ZKProof reference documents different types of succintness:

  • Fully succinct: Proof length independent of statement size. O(1) crypto elements (fully)
  • Polylog succinct: Polylogarithmic number of crypto elements
  • Depth-succinct: Depends on depth of a verification circuit representing the statement.
  • Sqrt succinct: Proportional to square root of circuit size
  • Non succinct: Proof length is larger than circuit size.

What's the difference between a SNARG and a SNARK?

Why people omit the ZK part in SNARK and SNARG and other ZKPs?

Because proofs, in computer science, don't necessarily have to hide all inputs. For example you might want to prove that the result of a computation is correct (e.g. the 64th iteration of the Fibonacci series is 6557470319842) without hiding any of the input. If a prover wants to hide some of the inputs, the zero-knowledgeness part can often be added easily as an extra step in the proof.

What makes a ZK-STARK not a ZK-SNARK?

What are PCP, linear PCP, IOP, etc.?

What are IP and NIZK?

  • IP: interactive proof
  • NIZK: non-interactive zero knowledge proofs

interactive here means that messages are being sent back and forth between the prover and verifier, non-interactive means that the prover can create a proof that can be verified without any further interaction with them (like a signature).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment