Zero knowledger proof non-interactive

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/