Zero Knowledge Proofs for Beginners

Let's start from absolute scratch. Consider the following polynomials:-

ax3 + bx2 + cx + d = y
ex2 = fy2 + gy3 + h

Here, a, b, c, d, e, f, g, h are constants. Say we are provided with a pair (x,y) and we want to verify whether (x,y) satisfies these equations. To verify, we can just substitute the provided value (x,y) in the equations and check that LHS = RHS for both equations.

Now, imagine that we have millions of equations and millions of variables to verify. How would we do that? We could just get some good hardware on the cloud and verify.

However, now imagine we want a smart contract to verify these millions of equations & variables. Since resources on a blockchain are limited, you might want to avoid performing these million checks on-chain. This is where zero-knowledge proofs come in.

ZK allows us to generate a "proof" that proves that a set of variables satisfy a set of equations. The awesome property about some particular implementations of these proofs is that it is small and fixed in size (Groth16), independent of the number of equations and variables it is proving. Anyone could take this proof and "verify" it. The computational resources to verify this proof are cheap and constant (~285K gas on Ethereum)

So, instead of performing expensive computations in a smart contract, one could just create a zk-proof for them, and provide it to the smart contract. The smart contract shall implement a proof verification algorithm, and if the proof checks, the smart contract can use the variables for further computation. It's like computational compression, in form of an active prover and a lazy verifier.

Another property of ZK is that you can hide inputs. This means I can prove that a certain set of variables satisfy the given equations, without revealing the entire set, or a subset of the input variables.

Finally, I want to mention that it is possible to represent most computations in the form of polynomials. Hence, ZK can be used to prove general computations.