zkSNARKS explained like you know some math and some coding

March 16, 2022

Stuff like “Alice makes a proof of a computation and with that proof alone, Bob is satisfied that the computation was done correctly without knowing anything about the inputs” is the ELI5 version of zkSNARKS (kinda) but doesn’t really satisfy the how.

To truly understand snarks you need to understand it’s a whole bunch of different concepts that come together to creating a zero-knowledge Succinct ARgument of Knowledge. Funnily enough, the “zero-knowledge” part is optional and not always implemented by zkRollups, it’s the “succinct” part that’s the real game changer. As in, verifying a proof takes less resources than running the computation yourself.

I am far from an authority on the subject! Don’t hesitate to contact me if you find something wrong here.

Here is my best attempt at summarizing the steps involved and the specific terms you’ll need to look up if you want to dive deeper:

  • Take a normal computation, inputs -> stuff -> outputs

  • Simplify the computation, unroll the loops, etc. until you have the same computation expressed in terms of small operations like adding and multiplying (Quadratic Arithmetic Program)

  • Setup a system of constraints (Rank 1 Constraint System) given the inputs and the ouputs and all the operations in between

  • Transform it into a polynomial equation (Lagrange interpolation mostly). You just transformed the problem into an equivalent but “simpler” one: If you can prove that the equation equals specific values at specific points, you have proved the result of the initial computation. And there’s a bunch of math already established about polynomial equations.

  • Use a polynomial commitment scheme so that you can prove the value of the equation at any random point given to you by a verifier, and it’s faster for the verifier to check the proof than actually evaluate the equation themselves. (For the KZG scheme, this part requires the infamous trusted setup that prevents the prover from forging fake proofs)

  • With enough random evaluations, the verifier is satisfied that the polynomial you gave them does match with the properties expected of a polynomial that does equal 0 at specific points. (Schwartz–Zippel lemma)

  • Make it non interactive with a Fiat–Shamir heuristic. Basically replace the random points given to you by the verifier with random points given to you by a reliable source of randomness, in most cases the sha256 hash of the whole problem, inputs, and polynomial is enough to be reasonably confident the prover didn’t fake the randomness and colluded to get points that make his fake proof look good

  • Add the zero-knowledge bit optionally by tweaking the trusted setup a bit and adding some kind of “fudging” factors that neither the prover nor verifier know, but the rest works the same way and the proof works the same