In the previous examples, Peggy was able to prove things to Victor through a series of interactions. For ZKPs to be practical, interactions between the prover and the verifier should be minimal. Fortunately, a technique called SNARK allows for non-interactive zero knowledge proofs.
SNARKs have the following properties (from whence they derive their name):
- Succinct: the sizes of the messages are small compared to the length of the actual proof.
- Non-interactive: other than some setup, the prover sends only one message to the verifier.
- ARguments: this is really an argument that something is correct, not a proof as we understand it mathematically. Specifically, the prover theoretically could prove false statements given enough computational power. So, SNARKs are “computationally sound” rather than “perfectly sound”.
- of Knowledge: the prover knows the fact in question.
You’ll typically see “zk” (for zero-knowledge) tacked on the front to indicate that during this process, the verifier learns nothing other than the facts being proved.
The mathematics underlying zkSNARKs involves homomorphic computation over high-degree polynomials. But we can understand how zkSNARKs work without knowing the underlying mathematics that ensure they’re sound. If you’d like more details of the mathematics, I recommend Christian Reitwiessner’s zkSNARKs in a Nutshell
As a simple example, suppose Victor is given a
H of some value. Peggy wants to prove that she knows the value
s such that
sha265(s) == H without revealing
s to Victor. We can define a function
C that captures the relationship:
C(x, w) = ( sha256(w) == x )
C(H, s) == true, while other values for
w will return false.
Computing a zkSNARK requires three functions
G is the key generator that takes a secret parameter called
lambda and the function
C and generates two public keys, the proving key
pk and the verification key
vk. They need only be generated once for a given function
C. The parameter
lambda must be destroyed after this step since it is not needed again and anyone who has it can generate fake proofs.
The prover function
P takes as input the proving key
pk, a public input
x, and a private (secret) witness
w. The result of
P(pk,x,w) is a proof,
prf, that the prover knows a value for
w that satisfies
The verifier function
V(vk, x, prf) which is true if the proof
prf is correct and false otherwise.
Returning to Peggy and Victor, Victor chooses a function
C representing what he wants Peggy to prove, creates a random number
lambda, and runs
G to generate the proving and verification keys:
(pk, vk) = G(C, lambda)
Peggy must not learn the value of
lambda. Victor shares
vk with Peggy.
Peggy wants to prove she knows the value
s that satisfies
x = H. She runs the proving function
P using these values as inputs:
prf = P(pk, H, s)
Peggy presents the proof
prf to Victor who runs the verification function:
V(vk, H, prf)
If the result is true, then the Victor can be assured that Peggy knows the value
C does not need to be limited to a
sha256 hash as we did in this example. Within limits of the underlying mathematics,
C can be quite complicated and involve any number of values that Victor would like Peggy to prove, all at one time.