How to make zero-knowledge proofs non-interactive?
With
earlier zero-knowledge verification systems there was one big problem.
For it to work, the prover and the verifier had to be online at the same
time. In other words, the process was “interactive”. This made the
entire system inefficient and almost impossible to scale up. The
verifiers couldn’t possibly be online at the same time as provers all
the time? There needed to be a system to make this more efficient.
In
1986, Fiat and Shamir invented the Fiat-Shamir heuristic and
successfully changed the interactive zero-knowledge proof to
non-interactive zero knowledge proof. This helped the entire protocol
work without any interaction. The procedure behind it is very simple.
So,
to give you an example, this is how zero knowledge proofs used to work
before Fiat and Shamir. Let’s prove this using simple discrete
logarithms.
- Anna wants to prove to Carl that she knows a value x such that y = g^x to a base g.
- Anna picks a random value v from a set of values Z, and computes t = g^v and sends t to Carl.
- Carl picks a random value c from the set Z and sends it to Anna.
- Anna computes r = v-c*x and returns r to Carl.
- Carl checks if t= g^r * y^c holds or not ( since r= v-c*x, y= g^x and by simple substitution, g^(v-c*x)* g ^ c*x = g^v = t).
- Carl doesn’t know the value of x, by merely checking if t = g^r * y^c he can verify that Anna does indeed know the value of x.
Now
while the above interaction is zero-knowledge, the problem with this is
that Anna and Carl need to be online and exchanging values for it to
work.
How can Anna prove to Carl that she has knowledge of something without Carl being online? She can do so by using a simple cryptographic hash function, as Fiat and Shamir theorized.
Let’s look how the example above would work in a non-interactive way:
- Anna wants to prove to Carl that she knows a value x such that y = g^x to a base g.
- Anna picks a random value v from a set of values Z, and computes t = g^v.
- Anna computes c = H(g,y,t) where H() is a hash function.
- Anna computes r = v – c*x.
- Carl or anyone can then check if t = g^r * y^c.
So, as you can see, zero knowledge proofs were made non interactive. And this was what laid the foundations for Zk-Snarks.
The above content is taken from this link https://blockgeeks.com/guides/zcash/