Non-Interactive ZKP
Introduction
Previously, we’ve looked at Interactive ZKP, and in the last article, we saw the flaws of Interactive ZKP, including scalability issues and limited transferability. Today, we’ll look at non-Interactive ZKP which solves these issues.
Non-Interactive ZKP
Until 1986, when Fiat and Shamir invented the Fiat-Shamir heuristic, the Zero-Knowledge Proof verifi]cation system used to be interactive. They changed Interactive ZKP system to non-Interactive ZKP.
Fiat-Shamir heuristic is a technique that involves creating a digital signature from an Interactive zkp, this will make fact-checking public without revealing the underlying information, i.e., the witness (data) can be proven publicly without the prover being online all the time like Interactive ZKP.
Example of Non-Interactive ZKP with discrete algorithm
This is similar to the example used in the previous article on Interactive ZKP but there’s a difference. We’ll see it as we proceed.
1. Slytherin wants to prove to Gryffindor that she knows the value of "Witness." Such that y= g^ "witness," where g is the base and w is the exponent
2. Slytherin picks a random value "x" from a set of values "Z" and computes "t" = "g^x".
3. Slytherin computes c = H(g, y, t) where H() is hash function
In the previous article on Interactive ZKP we could see an interaction between the prover and the verifier in step 3. Now, the Fiat–Shamir heuristic allows us to replace the interactive step 3 with a non-Interactive random oracle access. In practice, hash function is used.
4. Slytherin computes d = v – c*"Witness"
5. Slytherin or anyone (public) can verify if t = g^d * y^c.
The security of the scheme is weakened if the hash value used does not depend on the (public) value of y as a malicious prover can then select a random value x so that the product c*"witness" is known.
Advantages
Scalable—doesn’t need the prover and verifier to be online at all times.
Transferable: If the prover generates a proof once, it’s made public for different verifiers to see the proof, which doesn’t require the prover to generate proof again for different verifiers.
Applications
Blockchain: Thanks to this technology, transactions in public chains can be verified even if the participants are anonymous.
zk-SNARK, zk-Stark, and Bullet Proof utilize this tech.
Conclusion
The introduction of Non-Interactive ZKP has contributed to the advancement of Zero-Knowledge Technology; we can see its impact in zk algorithms such as zk-Stark, zk-Snark, etc.
Sources- https://en.m.wikipedia.org/wiki/Fiat–Shamir_heuristic
https://en.m.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof
https://www.geeksforgeeks.org/non-interactive-zero-knowledge-proof/?ref=rp