🛤️Arithmetic Circuits
Let's delve into why we need to represent our problem as an arithmetic circuit and what role the arithmetic circuit serves in the broader context of zk-SNARKs.
What is an Arithmetic Circuit?
An arithmetic circuit is a mathematical representation of a computation using basic operations like addition, multiplication, and subtraction. It consists of gates (which perform these operations) and wires (which carry values between gates).
Why Convert the Computation to an Arithmetic Circuit?
Structured Representation: Arithmetic circuits provide a structured way to represent our computation. Every problem or computation can be broken down into a series of smaller operations, which can be clearly and methodically represented using gates and wires in an arithmetic circuit.
Consistency and Completeness:
By translating the computation into an arithmetic circuit, we ensure it has a consistent and complete structure, making it easier to apply subsequent cryptographic protocols.
Universality:
One of the strengths of representing computations as arithmetic circuits is that virtually any computation can be translated into this format, making the process of zero-knowledge proofing universal. If you can represent a computation as an arithmetic circuit, you can produce a zk-SNARK for it.
From Circuits to Polynomial Equations:
The subsequent phases in the zk-SNARK generation process (like R1CS and QAP) operate on polynomial equations. Arithmetic circuits provide an intermediate step to translate our original problem into these polynomial equations.
In the context of our isZero() problem
The act of calculating
Arithmetic circuits are an abstract representation of computations using basic arithmetic operations. Each operation is represented as a "gate", and the inputs and outputs of these gates are connected through "wires". The IsZero() function can be transformed into such a circuit by mapping each arithmetic operation into a corresponding gate.
For the function:
We're focused on this computation:
Let's break this down into gates:
1. Multiplication Gate for -1 * in
Gate 0 takes the in signal (with is the input signal and represented by wire 1 (w1)) and multiplies it by -1 to produce an intermediate result:
out = -1 * in * inv + 1;
Which is equivalent to
out = -1 * w1 * inv + 1;
Which is equivalent to:
out = w2 * inv + 1;
Which gives us the gate:
Gate 0: w1 • (-1) = w2
Where w2 is the output of the gate:
2. Multiplication Gate for the result of step 1 multiplied by inv
Gate 1 takes the output of Gate 0 (from wire w2) and multiplies it with inv which is represented via wire w3) to produce another intermediate result:
out = w2 * inv + 1;
Which is equivalent to:
out = w2 *w3 + 1;
Which is equivalent to:
out = w4 + 1;
Which gives us the gate:
gate 1: w2 • w3 = w4
Where w4 is the output of this gate
3. Addition Gate to add 1 to the result of step 2
Gate 2 takes the output from Gate 1 (from wire w4) and adds 1:
out = w4 + 1;
Is equivalent to
out = w5
Which gives us the gate:
gate 2: w4 + 1 = w5
4. Verification Gate for the constraint in * out === 0
The constraint requires that the product of the input (in) and the output (out) is 0.
constraint: in * out === 0;
Remember that
In = w1
And
Out = w5
So the constraint: in * out === 0;
Is equivalent to
w1 * w5 === 0
Which gives us the gate:
gate 3: w1 • w5 = w6 ( === 0 )
Where the value in w6 should be 0 for the constraint to be satisfied.
Why use Gates?
Gates provide a standardized way to represent computations. By representing a function like IsZero() in terms of gates, we can then further convert it into more mathematical forms like R1CS that are required for zk-SNARK protocols. The benefit of doing so is that these protocols have specific requirements about the structure and form of the computations they can verify. By using gates and subsequent mathematical representations, we ensure that the function is compatible with the requirements of the zk-SNARK protocol.
Conclusion:
To achieve the zero-knowledge property, we need to ensure that our proof protocol doesn't leak information. zk-SNARKs, through their mathematical and cryptographic construction, achieve this, but they require the computation to be represented in a specific structured format, which is where the arithmetic circuit comes in. By breaking down the computation into its smallest components, we ensure that our zk-SNARK proof will be both zero-knowledge and sound.
Last updated
