Introductin of ZKP

What is a Zero Knowledge Proofs?

Zero-knowledge proofs (ZKPs) allow me to prove that I know a fact without revealing the fact itself. For example:

  • I know the private key corresponding to an Ethereum account, but I won't disclose what that key is!
  • I know a number such that SHA256(x)=0xa4865c2cae9713e9bcea7810ae83b14d18cfc259926cac793bf0ac7752851e8c ,but I won't reveal x!

In Ethereum, all transactions are secured using digital signatures based on public-key cryptography. Each public account is linked to a secret private key, and you cannot send funds from an account unless you possess that private key. A signature attached to every transaction essentially acts as a zero-knowledge proof that you know the corresponding private key. Although ZKPs might seem new, digital signature schemes have existed for decades.

Three properties of ZK Protocols

  • [Zero Knowledge] The Prover's responses do not disclose the underlying information.
  • [Completeness] If the Prover knows the underlying information, they can always respond satisfactorily.
  • [Soundness] If the Prover doesn't know the underlying information, they'll eventually get caught.

What are zkSNARKs?

zkSNARKs are a modern cryptographic tool that enables the efficient generation of a zero-knowledge protocol for any problem or function. Their properties include:

  • zk: Hides inputs
  • Succinct: Generates short proofs that can be verified quickly
  • Noninteractive: doesn't require a back-and-forth communication
  • ARgument of Knowledge: provers you know the input

Overview of ZKP Generation

  1. Transform your problem (e.g., graph isomorphism, discrete logarithm) into a function whose inputs you wish to conceal.
  2. Convert that function into an equivalent set of "R1CS"(Rank-1 Constraint System, or other) equations:
    • This is essentially an arithmetic circuit composed of "+" and "*" operations on prime field elements.
    • Simplified, the equations take the form , or .
  3. Generate a ZKP for satisfiability of the R1CS.

Types of SNARKs

There are two main types of SNARKs:

  1. Short Proofs with Higher Proving Time ComplexityThese SNARKs offer compact proofs but have a prover time complexity of . Examples include Groth16 and Plonk-KZG.
  2. Longer Proofs with Faster Proving Times These SNARKs prioritize faster proving times, resulting in longer proofs. Examples include FRI-based proofs, also known as STARKs (e.g., Plonky2).