Simple Explanations of Arithmetic Circuits and Zero-Knowledge Proofs
This is the second (and most recent) post in a series of articles introducing zero-knowledge proofs to a broad audience. My last piece, A Simple Explanation Of Zero-Knowledge Proofs, is a good place to start if you are new to the topic.
In a zero-knowledge proof, a prover wants to convince a verifier that some public statement is true. However, the proof of this statement holds sensitive details that can’t be shared.
To get around exposing the sensitive data, the prover creates a new statement. This new statement must be chosen so that it’s truth implies the truth of the original statement. Furthermore, the proof of this new statement’s truth cannot reveal any of the secret data.
This idea is conveyed in the first article of this series, “A Simple Introduction to Zero-Knowledge Proofs”, where Peter proves to Veronica that he knows of of a specific type of path in a publically shared graph without exposing which vertices the path touches. He does this by creating a totally New Graph that contains the same type of path. He explicitly shows Veronica the path in the New Graph so that she can see that it exists. The fact that it exists in the New Graph implies that it also exists in the Old Graph.
In this article, I will bring the discussion a step closer to current applications of zero-knowledge proofs by discussing a protocol that deals with arithmetic circuits. Because of the simple arithmetic involved, such protocols lend themselves very well to financial and blockchain-related use cases.
For example, one person can prove to another that they have 3 different types of assets whose cumulative worth is $100,000 without exposing the amounts attributed to each individual asset. In this case, the public statement is that “I have three different assets whose cumulative worth is $100,000”. The private data that can’t be shared is the specific numerical worth associated with each asset.
In this article, I will describe one of the first ever zero-knowledge proof protocols involving arithmetic circuits. It is from the paper entitled, “Zero-Knowledge Proofs for Finite Field Arithmetic or: Can Zero-Knowledge be for Free”? by Ronald Cramer and Ivan Damgard from the year 1997. Like the protocol described in “A Simple Introduction To Zero-Knowledge Proofs”, this protocol is interactive and it is not succinct. But while it cannot be used in practice, its simplicity makes it a good protocol from which to build a deeper understanding. My discussion of this simpler protocol should help elucidate the concept of arithmetic circuits as well as help you build a stronger intuition for zero-knowledge proofs.
Arithmetic Circuits
Arithmetic circuits are a model for computing polynomials. Polynomials are sums of terms containing constants (such as 1,2,3), variables (such as x,y,z), and exponents of variables (such as x², y³). Here are a few examples of polynomials:
- 5x + 3y + 2
- 3x² + 7x + 19
- 5x + 7
Arithmetic circuits are similar to Boolean circuits. Like Boolean circuits, Arithmetic circuits have gates and wires. Most of the gates symbolize operations. In boolean circuits, the operations are logical operations such as AND, and OR. In Arithmetic circuits, the operations are arithmetic operations, such as addition and multiplication.
Wires carry data to be processed by the gates. In Boolean circuits, wires carry bits while in Arithmetic circuits they carry integers. Wires going into a gate contain the data to be processed by the gate. Wires directed out from a gate contain the result of the operation.
If a gate has no input wires, then it is considered an input gate. An input gate contains the data to be processed by the circuit, which can be either a variable or a number.
Arithmetic Circuit Satisfiability
In this zero-knowledge proof protocol, the prover wants to convince the verifier that he knows a solution to the arithmetic circuit.
A solution to an arithmetic circuit is an assignment of values to input gates that are consistent with the circuit’s structure. For example, if Peter assigns the value of 30 to the output wire, then any combination of (a,b,c) such that (a + b) * c = 30 is a valid solution to this circuit.
For example, (a=20,b=10,c=1) and (a=4,b=2,c=5) are both valid solutions to this circuit.
Commitments
Peter wants to prove to Veronica that he knows a solution to the equation, (a + b) * c = 30.
To do this, Peter will put all of the values (both private and public) associated with the circuit into perfectly hiding boxes. He will then prove to Veronica that the boxes contain (a,b,c and 30) such that (a+b)*c=30.
The “boxes” that Peter puts these values into are really called commitments. Commitments hide their inputs by using a function whose output is irreversible. Peter can commit to his values, send the commitments to Veronica, and be completely sure that she will not be able to uncover any of the original values. Sha256 is one example of a function that can be used in a commitment scheme.
To remove our need for technical detail, I will continue to refer to these commitments as boxes. In order for this analogy to make sense, we need to add some “magical operations” that act on these boxes. The first operation is “smashing”. When two boxes are smashed together, their insides are added together and put into a new box.
If Veronica smashes a blue box containing 4 with a green box containing 2, she gets a purple box containing 4+2 = 6. Even after smashing these boxes, Veronica still has no idea what is in the blue box, green box, or purple box. “Smashing” represents the fact that functions used by commitment schemes are additively homomorphic.
The second operation is called “pinning”. When an integer, x, is pinned to a box, the result is a box containing the original contents of the box multiplied by x.
In the above picture, the value, 2, is “pinned” to the box containing 3. The result is a new box containing the product of 2 and 3, which is 6. “Pinning” represents the fact that commitments are functions that preserve multiplication by a constant.
The Protocol
To reiterate, Peter wants to prove to Veronica that he knows a solution to the equation, (a + b) * c = 30.As described above, Peter puts all of the values into boxes and sends these boxes to Veronica. Now, Veronica has 4 boxes. She aligns these boxes with their positions on the circuit as shown below:
As depicted in the picture, Veronica is able to calculate a box containing the output to the addition gate on her own. All she has to do is to smash together the blue box with the green box. The result is the purple box. While she doesn’t know the contents of any of these three boxes, she can say with certainty that the blue box, green box, and purple box satisfy the addition gate.
Next, she needs a way to verify that the purple box, the red box, and the yellow box satisfy the multiplication gate. This is where the bulk of the computation happens. In fact, in all zero-knowledge proofs over arithmetic circuits, the resources associated with the computation of an addition gate are barely considered. This is because the “smashing” operation described above allows Veronica to know that three commitments satisfy an addition gate without the need for an interactive zero-knowledge proof protocol.
On the other hand, there is no analogous operation to “smashing” for multiplication. To prove that three commitments satisfy a multiplication gate, Peter and Veronica will have to engage in an interactive zero-knowledge proof protocol.
An Interactive Zero-Knowledge Proof for the Multiplication Gate
Peter’s goal is to convince Veronica that the inputs of the red box, purple box and yellow boxes satisfy the multiplication gate. In other words, he wants to prove that (contents of red box) * (contents of purple box) = (contents of yellow box).
In the introduction of the article, I mentioned that zero-knowledge proofs work by creating a new statement whose proof leaks no secret data and whose truth implies the truth of the original statement. Following this line of reasoning, Peter is going to create a new statement that can be transformed to the original statement through simple algebra. The benefit of this new statement is that Peter can prove it without leaking any of his secret data.
The original statement is that (contents of red box) * (contents of purple box) = (contents of yellow box). Like the original statement, the new statement will also be a statement of equality between two expressions and will take the form of LHS = RHS , where LHS and RHS are as follows (LHS stands for Left Hand Side and RHS stands for Right Hand Side):
LHS: (contents of red box) * (contents of purple box) * vRandomValue + (contents of red box)*pRandomValue
RHS: (contents of yellow box) * vRandomValue + (contents of red box)*pRandomValue
As you can see, LHS and RHS are almost identical except that RHS replaces (contents of red box) *(contents of purple box) with (contents of yellow box). Because of this, all the other terms cancel out, and the new statement, LHS = RHS reduces down to the old statement. Therefore, the truth of the new statement implies the truth of the old statement.
As you probably noticed, LHS and RHS have two values that didn’t appear in our arithmetic circuit; vRandomValue and pRandomValue. vRandomValue is a random value that Veronica generates to prevent Peter from cheating. pRandomValue is a value that Peter generates to keep his secrets hidden from Veronica.
All Peter has to do now is prove that LHS = RHS. As you will see, he will do this without leaking any of his secret data.
Peter Proves The New Statement
For this part, we need to introduce another magical property of our boxes — that a box’s color is directly associated with its value. This means that two boxes only have the same color if they contain the same value. This corresponds to the fact that commitment schemes must be binding — each output is associated with only one input.
In the first step of the protocol, Veronica generates a random value, vRandomValue, and sends it to Peter. Peter generates his own random value, pRandomValue, which he keeps secret from Veronica. Next, Peter computes a disguised version of (contents of purple box) as follows: (contents of purple box)*vRandomValue + pRandomValue.
As mentioned above, the purpose of vRandomValue is to prevent Peter from cheating. If it weren’t for vRandomValue, Peter could have cheated while initially creating the boxes by filling them with numbers that don’t satisfy the circuit, and then compensating for the difference with pRandomValue. Because of vRandomValue, the only way he could have cheated is if he had guessed the value of vRandomValue in advance. Since vRandomValue was chosen uniformly at random, it is very improbable that he could have guessed vRandomValue correctly.
pRandomValue, on the other hand, is used to hide (contents of purple box) from Veronica. If it weren’t for pRandomValue, Veronica could easily deduce what (contents of purple box) is from the term (contents of purple box) * vRandomValue because she already knows what vRandomValue is.
While pRandomValue must be kept secret from Veronica, it still needs to be incorporated into her calculation of the RHS box. To get around this, Peter pins pRandomValue to the red box and sends this new box to Veronica.
Veronica now has the following boxes:
And the following values:
Using these ingredients, Veronica can construct a box containing LHS and a box containing RHS. Once she constructs these two boxes she will check if they have the same color. If they do, then this implies that LHS = RHS, which implies that (contents of red box)*(contents of purple box) = (contents of yellow box), which is the goal of our protocol.
Constructing the box containing LHS: As a reminder, the LHS of the new statement is (contents of red box) * (contents of purple box) * vRandomValue + (contents of red box)*pRandomValue. If you look closely, you’ll see that this is actually just equal to (contents of red box) * (disguised version of contents of purple box). Therefore, she constructs the box containing LHS by pinning the (disguised version of contents of purple box) to the red box.
Constructing the box containing RHS: As a reminder, the RHS of the new statement is (contents of yellow box)*vRandomValue + (contents of red box)*pRandomValue. To construct this box, Veronica first pins vRandomValue to the yellow box. Then she smashes this with the new box Peter sent her, which contains (contents of red box) * (pRandomValue). The result is a box containing (contents of yellow box)*vRandomValue + (contents of red box)*pRandomValue, which is exactly the RHS of the new statement!
Veronica now has a box containing the LHS of the new statement and a box containing the RHS of the new statement. Since the the two boxes have the same color, Veronica is convinced that the new statement is true, and therefore that (contents of red box)*(contents of purple box) = (contents of yellow box). Since she is convinced, she accepts the proof. If the two boxes didn’t have the same color, she would reject the proof.
Proof that the Yellow Box contains 30
The original goal of this protocol is for Peter to prove to Veronica that he knows (a,b,c) such that (a + b) * c = 30. At this point in the protocol, Veronica knows that (contents of yellow box) = ((contents of blue box)+ (contents of green box)) * (contents of red box)). In other words, she knows that Peter has four values, (a,b,c,d), such that (a+b)*c = d. The only task remaining is for Peter to prove that the yellow box contains the value of 30.
To do this, Peter simply sends Veronica the key to the yellow box. Veronica opens the box. If she finds the value 30, Veronica accepts the proof. Otherwise, she rejects it.
Peter has now successfully proven to Veronica that he knows three values, a, b and c such that (a + b) * c = 30 without leaking any of his secret data.
Conclusion
Hopefully, you are less confused about zero-knowledge proofs over arithmetic circuits than you were when you started reading the article. If not — feel free to leave questions in the comments :) And if you enjoyed the article and want to see more like this, give it a clap or two.
