ZK Proof
I am going to do a really quick primer on zero knowledge proofs because they are a lot of fun. Remember those teachers which said you would never need to remember math? Buckle up. Its not hard, but it does require some out of the box thinking and some basic algebra. People make a lot of crypto look really confusing, and it is. But, its also really not that hard when you dive into it. Its a bunch of really simple/trivial concepts put together to form something really complex. I wrote this because I was trying to figure out how zk proofs worked, and I could not find a good example. If you are lucky, you got to witness (pun intended) me do this entire thing on a whiteboard without notes.
Let’s start by proving that we know a solution to x**3 + x + 5 = 35. This is obviously true when x=3, but let’s prove we know the answer.
Step 1 - Circuit
Start by drawing out a little circuit.
| x | | x |
\ /
| * |
|
| W1 | | x |
\ /
| * |
|
| W2 | | x |
\ /
| + |
|
| W3 | | 5 |
\ /
| + |
|
| O |Step 2 - Encode wires
Now we can take that circuit and we can pretty easily represent it as a system of equations. The system of equations is most easily represented by a matrix. The ordering of the columns doesnt technically matter, but lets start with the ordering of the specific wires. We are going to say matrix A * matrix B = matrix C. Easy enough.
For the first wire, we know that x * x equals wire 1. So, we will set all of the columns to 0 except for x in both matrix A and B. Then they will equal wire 1 in matrix C.
c,x,o,1,2,3 * c,x,o,1,2,3 = c,x,o,1,2,3
---------------------------------------
0 1 0 0 0 0 * 0 1 0 0 0 0 = 0 0 0 1 0 0 (w1 = x*x)Lets go ahead and fill that in for the other wires
c,x,o,1,2,3 * c,x,o,1,2,3 = c,x,o,1,2,3
---------------------------------------
0 1 0 0 0 0 * 0 1 0 0 0 0 = 0 0 0 1 0 0 (w1 = x*x)
0 1 0 0 0 0 * 0 0 0 1 0 0 = 0 0 0 0 1 0 (w2 = x*w1)
1 0 0 0 0 0 * 0 1 0 0 1 0 = 0 0 0 0 0 1 (w3 = 1*(x+w2))
1 0 0 0 0 0 * 5 0 0 0 0 1 = 0 0 1 0 0 0 (o = 1*(5+w3))We really want a special type of matrix to make the math work out. We can go into details, but trust me here. Lets do something as easy as 11 = 1. We need a 1 in the c column on the C matrix. And we also need a 1 in the x column of the C matrix, so 1x = x.
c,x,o,1,2,3 * c,x,o,1,2,3 = c,x,o,1,2,3
---------------------------------------
1 0 0 0 0 0 * 1 0 0 0 0 0 = 1 0 0 0 0 0 (1 = 1*1)
1 0 0 0 0 0 * 0 x 0 0 0 0 = 0 1 0 0 0 0 (x = 1*x)
Okay, now lets combine those rows together. And we are going to reshuffle things a little bit. You will notice that C becomes an identity matrix Z (1s on the diagonal)
c,x,o,1,2,3 * c,x,o,1,2,3 = c,x,o,1,2,3
---------------------------------------
1 0 0 0 0 0 * 1 0 0 0 0 0 = 1 0 0 0 0 0 (1 = 1*1)
1 0 0 0 0 0 * 0 1 0 0 0 0 = 0 1 0 0 0 0 (x = 1*x)
1 0 0 0 0 0 * 5 0 0 0 0 1 = 0 0 1 0 0 0 (o = 1*(5+w3))
0 1 0 0 0 0 * 0 1 0 0 0 0 = 0 0 0 1 0 0 (w1 = x*x)
0 1 0 0 0 0 * 0 0 0 1 0 0 = 0 0 0 0 1 0 (w2 = x*w1)
1 0 0 0 0 0 * 0 1 0 0 1 0 = 0 0 0 0 0 1 (w3 = 1*(x+w2))Step 3 - Wire inputs
There we go! Now the input to solve this equation is just the value of the wires which solves the system of equations. Since we know x, we can go ahead and compute the values of each of the wires.
c,x,o, 1, 2,3
-------------
1 3 35 9 27 30 Step 4 - Sanity check
Remember, we setup AB=C. So, AZ * BZ = CZ. If you plug that into a system equation, you should see they match. We see that 11=1. And 13=3. And 135=35. And …
AZ - {1, 1, 1, 3, 3, 1}
BZ - {1, 3, 35, 3, 9, 30}
CZ - {1, 3, 35, 9, 27, 30}Step 5 - QAP
But, I thought you said this was zero knowledge. I see the value right there! Alright, that’s where this starts getting a little tricky.
Let’s convert A into a vector, or more appropriately a QAP (Quadratic Arithmatic Polynomial). We can do this using a langrange interpolation or something like an FFT. Recall that our A matrix is
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
0 1 0 0 0 0
0 1 0 0 0 0
1 0 0 0 0 0Taking the first column (A0), we have the values [1, 1, 1, 0, 0, 1]. So, we can do something like
A0 | B0 | C0
x:0 y:1 | x:0 y:1 | x:0 y:1
x:1 y:1 | x:1 y:0 | x:1 y:0
x:2 y:1 | x:2 y:5 | x:2 y:0
x:3 y:0 | x:3 y:0 | x:3 y:0
x:4 y:0 | x:4 y:0 | x:4 y:0
x:5 y:1 | x:5 y:0 | x:5 y:0That generates a pretty nasty polynomial, but now we have something like
A0 = 1 - (25 x)/12 + (95 x^2)/24 - (19 x^3)/8 + (13 x^4)/24 - x^5/24.
B0 = 1 - (1637 x)/60 + (1115 x^2)/24 - (607 x^3)/24 + (133 x^4)/24 - (17 x^5)/40
C0 = 1 - (137 x)/60 + (15 x^2)/8 - (17 x^3)/24 + x^4/8 - x^5/120
Now we can simply ask people to solve for a value of X. We know that if we do this for the values within the range, then the system of equations is appropriately solved. But, we could even ask for something out of bounds, something like solve this when x=7. If you tell me, -34. Then I know that you know the equation. Which means that you know the column values. Either way, if you answer enough “challenges”, then I can be confident that you do in fact know everything about the circuit. And, the only way for you to know the intermediate values of the circuit is for you to know the input x, which means you must know the answer! It’s interesting, because I can setup this entire thing without necessarily knowing the answer myself.
How does this work in practice? Hey, Craig tell me the value of A0 at x=0, and x=1 and … and tell me the value of A1 at x=0, and x=1 and … all the way up through B6 or whatever. But, realistically, you probably dont need me to tell you every single datapoint. You can pick a handful and be reasonably confident Im not making things up if I get them right. Funny enough, I never have to tell you that the answer is 3 for you to know that I know the answer. Or, depending upon the setup, for me to prove that I know the answer without actually revealing the answer (wouldnt want anyone cheating/copying).
Step 6 - Other fun things
There you have it! You just designed a very simple zero knowledge proof. There are a lot of other things we can do.
- Depending on how you setup C, its not an identity matrix - but you could easily convert it into an identity matrix Z. C’AB. Or, just rename C’A as A. And now, you have AB=Z.
- We can make A a single polynomial. We did A0 using the values x0..x5. But, we could make A1 simply x6..x11 rather than its own polynomial.
- We can down sample. That would be a really, really big polynomial. Even our tiny circuit would have something like 36 interpolations. Perhaps too big or computationally expensive. Perhaps lets use every other data point.
- We can use modular math. For circuits, the numbers are normally pretty small, but sometimes they can get large. Its common to use a large prime number as your modulo or sometimes something like 255 (to keep in a single byte). So, every number would be %p; where p is some number. This can help reduce size, and therefore decrease the cost of the zk proof. It can also help make it harder to “crack” the zk proof.
- We can use elliptic curve math. Rather than y being real numbers, they could correspond to primes.
Step 7 - The future
ZK proofs are a rapidly advancing technology. There are a couple of different setups to make these work. Some require some trust, some dont. Some require magic numbers, some dont. This was a setup using a r1cs, but there is extra stuff which needs built on top to run these zk proofs on a blockchain.
One style of zk proofs which is getting a lot of attention are plonks. My example zk proof was using what is referred to as a rank 1 constraint system. Relatively easy to reason about, pretty straight forward math, and not too computationally expensive. But, its alternative plonk trades off being relatively easy to reason about for a lot of computational benefits.
It sets up a system QlA + QrB + QoC + QmAB + Qc = 0. Where Q are constants. A is left, B is right, C is constant. Its functionally similar to our circuit above, but it needs to introduce some fancy constraints (Like A1==B1). There is some math magic to make it happen, maybe a later post.
Other
One thing to note is that we normally don’t actually just evaluate polynomials. We normally use a Kate commitment. Rather than evaluate P(x) = c, we can instead prove that (P(x) - a)/(x-z) is not a fraction.
Let’s take a relatively simple example. I want to prove that given P = x**2, that P(2) = 4.
(P(x)-4)/(x-2)
(x**2-4)/(x-2)
=
x+2So, we get Q = x + 2. I know that (x-2)*(x+2) = x**2-4, which is what we are trying to prove. Neat. Now, normally you will use generator points from some prior trusted setup so that I cannot pick any random points to prove. But, still, neat. We are essentially encrypting the evaluation of the polynomial.