Zero-Knowledge Proofs
Origins
The concept of Zero-Knowledge Proofs (ZKPs) was first invented by Shafi Goldwasser, Silvio Micali and Charles Rackoff in their seminal paper, The Knowledge Complexity of Interactive-Proof Systems in the 1980s.Despite being considered as a theoretical breakthrough, even the cryptography community labeled the scheme as impossible in practice when the idea was born. Thanks to many breakthroughs made in the recent years, especially the contribution made by many web3 projects like ZCash and Aztec, we have seen a Mooreβs Law style improvement on the performance of zero-knowledge proof systems.
What is a Zero-Knowledge Proof System?
A zero-knowledge proof system is a protocol by which someone (the prover) can prove the correctness of a statement to someone else (the verifier) without disclosing any additional information. It consists of the following elements and satisfies the following properties.
Elements of Zero-Knowledge Proof Systems
Statement: The statement whose truth we want to prove.
Public Input: The information available to both the prover and the verifier.
Witness: The information known only by the prover which is enough to prove the statement. The prover wants to keep this information secret from the verifier.
Proof: A piece of information derived by the prover from the statement, public input, and witness that can be verified against the statement and the public input to test the truth of the claim.
Properties of Zero-Knowledge Proof Systems
Generally, zero-knowledge proof systems must satisfy the following 3 crucial properties:
Completeness: An honest prover can convince the verifier about any statement he/she knows.
Soundness: A computationally bounded prover cannot forfeit a proof that can convince an honest verifier.
Zero-Knowledge: The proof doesnβt leak any information other than the truth of the statement itself.
Example
To better illustrate a ZKP system, let us run a simple example in the finite field πΉ7F7.
Statement: 22 is a square in πΉ7F7
Public input: π₯=2x=2.
Witness: π€=4w=4, since 42=242=2 in πΉ7F7.
The protocol consists of the following steps:
The prover chooses a random non-zero πβπΉ7aβF7 and sends π¦=π2y=a2 to the verifier.
The verifier chooses πβ{0,1}bβ{0,1} and sends it to the prover.
The prover sends the verifier the proof π=π€ππΟ=wba.
The verifier accepts the proof if π2=π₯ππ¦Ο2=xby.
Then they repeat the protocol above for different values of πa until the verifier is convinced.Let us check that the above protocol satisfies the desired properties:
Completeness: It is clear, since π2=π€2ππ2=π₯ππ¦Ο2=w2ba2=xby.
Soundness: A dishonest prover might try to trick the verifier by sending a π¦y in step 1 which is not a square. In that case the verifier would reject the proof in half the cases, when they choose π=0b=0. If π¦y is a square but π₯x is not, the verifier would reject the proof when π=1b=1. A dishonest prover has a 1/21/2 probability to trick the protocol on each iteration, so this probability can be made negligible by iterating enough times.
Zero-knowledge: If π=0b=0, the prover does not use π€w at any point in the proof, it cannot be leaked. If π=1b=1, the only place where the prover uses π€w is in π=π€πΟ=wa, from which the verifier cannot extract π€w without the knowledge of πa. As long as the prover does not repeat the above protocol with the same πa for different πb's, the protocol remains zero-knowledge.
Succint Non-Interactive Arguments of Knowledge (SNARKs)
A particularly important type of ZKP systems are SNARKs. They are zero-knowledge proof systems which satisfy the following extra properties:
Argument of knowledge: The prover wants to prove knowledge of the witness itself. In the example above, the statement would be "I know a square root of 22 in πΉ7F7". One can show the protocol above also proves this stronger statement, thus making it an argument of knowledge.
Succinctness: The proof size is constant or logarithmic compared with the circuit size (i.e. the amount of computations) of the statement. The protocol above is also succint, since the proof is just a number in πΉ7F7.
Non-Interactive: Proof generation and proof verification happen in two consecutive rounds: first the prover runs a function proveprove to generate a proof and then the verifier runs a function verifyverify to verify it. The protocol above is interactive, i.e., it does not satisfy this property because of the continuous communication between prover and verifier.
Setup
SNARKs need an extra element to be properly defined
Setup: A set of proving and verifying keys necessary to execute the proveprove and verifyverify functions, respectively.
In pairing-based proving systems such as Groth16, the setup consists of a set of elliptic curve points, generated from a randomly sampled seed, more commonly known as the toxic waste. Knowledge of this seed allow an attacker to fabricate valid ZKPs for false statements, so it is of paramount importance that the generation of the keys is safely executed, i.e., that nobody knows the toxic waste employed to generate them. This is usually done in a multi-party computation known as Trusted Setup.
The simple definition of a SNARK
Once all the elements are fixed, a SNARK is defined as a pair of functions
prove(Setup, Public Input, Witness) -> Proof: Generates a proof for the knowledge of the witness using the public input and witness.
verify(Setup, Public Input, Proof) -> bool: Verifies the proof against the public input.
Last updated