# Zk-SNARKs: under the hood (series)

by
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
categories
Building Great Products  Company Culture  Consumer Tech  Cryptocurrency  Entrepreneurship  Productivity  Sales  Tracking Business Performance  