A Beginner Friendly Intro to ZKPs. Part 1.
A first introduction to Zero-Knowledge Proofs
As we know from a previous blog post, Ethereum needs rollups to deliver at scale, and Zero-Knowledge (ZK) Rollups are a way forward. Let’s unpack (unroll?) that a bit.
A Zero-Knowledge Proof (ZKP) proves a certain mathematical statement is correct without revealing the statement itself. A simple example of a ZKP is a digital signature: you signing a message proves that you own the private key corresponding to the public key, without revealing the private key itself.
Consider a function f. Let f(x) = y. A ZKP for function f would prove that you possess the value x needed for y to be the output, without revealing x.
Consider a classic setup: A prover wants to prove to a verifier that they know some secret thing without revealing the secret. The verifier can ask the prover some questions or pose some challenges, and it verifies the information received from the prover.
ZKPs have 3 properties:
Zero-Knowledge: As explained above.
Completeness: As long as the prover possesses the underlying secret information, they can always provide a valid proof which can convince the verifier.
Soundness: If the prover does not possess the underlying secret information, they will eventually not be able to generate a valid proof. That is, after a few verifications, the prover will fail.
Some mathematical problems have had ZKPs around for a while: 3-coloring problem, Discrete Logarithms, and Graph Isomorphism, for example.
For every new problem, mathematicians would have to come up with a new ZKP, which is obviously not ideal. Ideally, we would like to have a way to generate ZKP for any arbitrary function f.
That’s where zkSNARKs come in. To break down the name:
zk: Zero-Knowledge, Meaning that it hides the input (in our example, it hides the input x)
S: Succinct. A proof that is created quickly (linear time) and verified even quicker (constant time)
N: Non-interactive. Meaning the verifier doesn’t need to ask anything from the prover
ARK: Argument of Knowledge. Meaning a proof that proves that you know the hidden input
zkSNARK is a cryptographic tool that takes in the code for function f and outputs a protocol for generating ZKPs for f.
ZKPs for arbitrary functions are incredibly useful in matters of scaling up while maintaining privacy, and we will explore this further in future editions of the newsletter.