Arrow icon
Ness Labs: Make the most of your mind
Learn more about Joggo

A Summary of

Zk-SNARKs: under the hood (series)

Vitalik Buterin
View original

We can use the Pinocchio protocol to allow a prover to prove that they know a solution for a particular quadratic arithmetic program (QAP) without revealing anything else about the actual solution.

  • Problem: The solution to a QAP is a set of polynomials which are often very large. It is difficult for provers to provide full solutions directly.
  • Solution: Provers can provide proof that they know the polynomial without revealing anything else.
  • Basic idea: Given points (P, Q) where Pk = Q, you can generate points (R, S) where Rk = S
    • R and S must be multiples of P and Q by a factor only you know
    • "Pairing check:" You do not need to know k to check that R = Sk when using elliptic curve pairings
  • Adapting this idea to linear combinations instead of elliptic curve points, provers can
    1. Provide a linear combination for each QAP solution in terms of unknown k values and points.
    2. Prove the linear combinations share unknown coefficients
    3. Prove linear combinations follow the QAP equation AB - C = HZ using a pairing check
  • To verify the solution is correct (and not just that the prover has one), use the Pinocchio verification algorithm
Related content
See all posts
Arrow icon