Zero Knowledge Proofs

• The proof-of-work in the classic Bitcoin blockchain is a key that when added to the hash of the block, yields a hash smaller than a specified amount (resulting in a hash with a certain number of leading 0 bits). However, this method requires the prover $P$ (miner) to provide the knowledge of an existing solution $w$ to the proof statement $x$ to the verifier $V$ (client).

• Zero-knowledge proofs are a family of proofs that attempt for the prover to prove to the verifier that they “could prove it if they wanted to”, where the proof $\pi$ is different from the secret information (called witness) $w$

• An interactive proof is zero-knowledge if what the verifier can computer after the interaction is the same as what they could have computed before

• https://en.wikipedia.org/wiki/Zero-knowledge_proof

• MOOC on ZKPs

zkSNARKs

• SNARK stands for “Succinct Non-interactive ARgument of Knowledge”

  • Argument of Knowledge: The prover, having the secret witness $w$, provides a proof which must prove the prover’s knowledge of $w$. In argument-system, the proof generated by $P$ has to convince the verifier $V$ that a arithmetic-circuit $C$, known by both $P$ and $V$, is satisfied for the inputs of the statement $x$ and the witness $w$
  • Non-interactive: Interactive proofs are able to use interactive communnication between the prover and verifier and often have the verifier accept the proof after being reasonably satisfied with the proofs. However, in contexts like a blockchain where often there is a single prover and multiple verifiers, this is not feasible and we need to rely on a single proof generated by the prover that can be verified in one-shot by any verifier, these are non-interactive proofs.
  • Succinct: For a non-interactive argument-of-knowledge to be succinct:
    • The proof $\pi$ must be “short”, have an at-most logarithmic complexity to the size of the circuit $|C|$
    • The time complexity to verify the proof must be at-most logarithmic to the size of the circuit $|C|$, and at-most linear to the size of the statement $|x|$

• A simple SNARK could involve $P$ sending the witness $w$ itself to $V$ (called the trivial argument system), but there are concerns related to this:

  • $w$ might be a secret that $P$ does not wish to reveal
  • $w$ might be too long, and the proof might no longer be succinct

• zkSNARK is a SNARK that has the added quality of being zero-knowledge, i.e., the proof received by $V$ does not reveal any information the witness $w$.

• Vitalik Buterin - Quadratic Arithmetic Programs: from Zero to Hero

• Lecture 10.3: What is a zk-SNARK?

• https://blog.jarrodwatts.com/how-zk-proofs-and-zkevms-work

• How zkVM/zkMIPS works. (by ZKM)