About this Book
Zero-knowledge cryptography is a fascinating area, where a party can prove a statement without revealing any extra information about it; proving that something is true without revealing what makes that “something” true.
Circom is a hardware description language (HDL) specifically designed for creating zero-knowledge proofs. It enables developers to create arithmetic circuits, which are then used to generate proofs that demonstrate a certain statement is true, without revealing any additional information about the inputs used to make that statement.
Circom has opened up new possibilities for creating privacy-preserving applications, such as digital identities, voting systems, and financial transactions, where proving the validity of a statement is necessary, but keeping the underlying data private is critical.
On the other hand, zero-knowledge proofs can serve as proofs of honest computation, without necessarily hiding the data underneath. This paves the way on new methods of off-loaded computation, most notable example being the zk-rollup ecosystem.
Organization
The book is organized as follows:
- Arithmetic starts with a quick look at finite fields, i.e. what the numbers in a circuit actually are, and then has several hello-world level Circom programs such as addition & multiplication, to get the reader started, followed by inversion & integer division. It is strongly recommended to understand how the programs here work.
- Bits describes methods related to bits, which are signals with value 0 or 1; you can think of them as booleans as well.
- Comparators describes comparators such as equality, less-than, greater-than-or-equal and such. It also describes some more specialized methods like alias-check and sign-check.
- Control-Flow describes how if-else works in the circuit world.
- Arrays describes array methods.
- Hashing describes circuit-friendly hashes, such as Poseidon and MiMC, and how to build commitments with them.
- Merkle Trees describes Merkle Trees and their usage in Circom circuits, from binary Merkle trees to sparse Merkle trees and Merkle mountain ranges.
- Common Pitfalls collects the mistakes that come up again and again in Circom circuits, and how to avoid them.
- Further Topics covers topics beyond writing circuits, such as alternative provers, large circuits and folding.
- Examples puts everything together in complete circuits, from simple ones like Fibonacci & Magic Squares, to puzzles like Sudoku & N-Queens, some well-known LeetCode problems, fixed-point arithmetic, a ZK puzzle from Axiom, and Tornado Cash.
Counting Constraints
Throughout the book, we measure the cost of a circuit by its number of non-linear constraints, as reported by the Circom compiler with full simplification:
circom circuit.circom --r1cs --O2
Only multiplications of signals create non-linear constraints. Additions and multiplications by constants only create linear constraints, which are free: with --O2 the compiler eliminates them entirely, by expressing some signals in terms of others. For example, the Fibonacci circuit only has additions, so it has no non-linear constraints at all!
Follow Along
You can clone the repository and examine the circuits yourself, we provide documentation within the code as well. We also provide tests via Circomkit that demonstrate each circuit described here. In the repository, you can run the command below to run all tests:
bun test
Alternatively, you can play around with the circuits without ever leaving your browser, just visit zkrepl.dev!
Resources
There are many resources about Circom & ZK out there, to list a few:
- Official Circom Docs by @iden3.
- Circomlib is a collection of common circuits, by @iden3.
- Circom Tutorial by RareSkills.
- zkJargon Decoder by @nico_mnbl.
- BattleZips by BattleZips
- 0xPARC Learning Group 1 by 0xPARC
- Circom & Noir by @doulos819
Arithmetic
Our starting point is arithmetics, for a good reason: in the world of arithmetic circuits, we are only allowed to do two things: addition and multiplication.
First, we take a quick look at finite fields, i.e. what the numbers in a circuit actually are. Then, we will look at adding and multiplying many numbers within a circuit, then we move on to more advanced operations such as multiplicative inverse and integer division.
Finite Fields
The values in a Circom circuit are not integers: every signal is an element of a finite field. Most of the time you will not notice the difference, but many of the bugs in Common Pitfalls come from forgetting it. So before writing any circuits, let us take a quick look at what these numbers are.
What Is a Field?
A field is a set of numbers where you can add, subtract, multiply, and divide by anything except zero, and the result always stays within the set. The usual rules apply, e.g. and . The rational numbers and the real numbers are fields, while the integers are not, as is not an integer.
A finite field has a finite number of elements. The one we use is made of the integers modulo a prime :
If you are interested in the formal definitions, which build up from groups to rings and then to fields, see Field and Finite field. They are not needed to write good Circom code, though.
Arithmetic Modulo
Every operation in the field is done modulo : we compute the result as usual, and then take the remainder after dividing by . Here are a few examples with the tiny prime :
| Operation | Result |
|---|---|
| , since | |
| , since | |
| , since |
Why must be a prime? Because only then does every non-zero element have an inverse, so that division always works. Modulo 6, for example, is always even, so it can never be 1, and does not exist.
By default, Circom uses the prime of the BN254 elliptic curve, which is the one used by Ethereum’s precompiles:
You can choose a different prime with the --prime option of the compiler, such as bls12381 or goldilocks. Throughout this book we use BN254.
There Are No Negative Numbers
In the field, is simply , which is the largest element. So a “negative” number is really a huge number, and there is no notion of an element being smaller or larger than another that is preserved by arithmetic: with , we have , but while .
This is why comparing two signals is not trivial in a circuit: we must decompose them into bits, and make sure that they are small enough. See Comparators for how it is done, and Common Pitfalls for what happens when it is forgotten.
To make things more confusing, Circom’s relational operators such as
<treat the elements larger than as negative numbers, so-1 < 0is true in Circom code! This only affects the code that computes values, e.g. withvarand<--; constraints can not compare at all. Seenbitsfor an example where this matters.
Division
Division in the field is multiplication with the inverse: , where is the element such that . Computing an inverse is expensive, so in a circuit we compute it outside of the constraints, and only check that , as described in Inversion.
Circom has two division operators, and it is important to not mix them up:
/is the division in the field, so1 / 2is , the element that gives 1 when multiplied by 2.\is the integer division, along with%for the remainder, so7 \ 2is 3. These are not field operations, so they can only be used to compute values, and must be checked with constraints, as described in Integer Division.
The Size of
The BN254 prime has 254 bits, so every element fits in 254 bits. However, not every 254-bit number is an element: is larger than . This has a few consequences that come up throughout the book:
- A number with up to 253 bits is always an element, so decomposing it into bits is safe. That is why
Num2Bits(n)requires . - A 254-bit decomposition may have two solutions for the same element, and , called aliases. They are ruled out with an alias check.
- Arithmetic wraps around at , so an equation such as only holds over the integers if the values are small enough, as in Integer Division.
Try It Yourself
You can see the field in action with log, which prints the values while computing a witness:
template Field() {
signal input in;
log("-1 =", -1);
log("1 / 2 =", 1 / 2);
log("7 \\ 2 =", 7 \ 2);
}
This prints:
-1 = 21888242871839275222246405745257275088548364400416034343698204186575808495616
1 / 2 = 10944121435919637611123202872628637544274182200208017171849102093287904247809
7 \ 2 = 3
Adding 1 to the first number gives you itself.
Multiplication
There may be several “Hello World!“s of Circom, and multiplying numbers is surely one of them: the Multiplier circuit computes the product of all elements in an array.
Multiplier
template Multiplier(n) {
assert(n > 1);
signal input in[n];
signal output out;
signal inner[n-1];
inner[0] <== in[0] * in[1];
for (var i = 0; i < n - 2; i++) {
inner[i+1] <== inner[i] * in[i+2];
}
out <== inner[n-2];
}
Since multiplying more than two signals at once is non-quadratic, we have to do this two at-a-time. Here is how multiplying 4 numbers looks like:
flowchart LR
in_1(("in[1]")) --> i0
in_0(("in[0]")) --> i0
in_2(("in[2]")) --> i1
in_3(("in[3]")) --> i2
i0["inner[0]"] --> i1
i1["inner[1]"] --> i2
i2["inner[2]"] --> out(("out"))
There is really not much more to talk about in this circuit. It is simply a great way to test out whether you can understand the Circom syntax, loops, template parameters and such.
If you really like having everything as “gates” you could write the circuit with a Multiplier gate:
template Mul() { signal input in[2]; signal output out; out <== in[0] * in[1]; }Then, within the
Multiplieryou can use theMulgate for each multiplication.
Soundness
Imagine that you would like to use the circuit above to prove that you know some factors for some number:
Would it be okay to use the circuit above as given, with out as the only public signal?
If you think about this for a while, you will realize that the circuit does not care if a factor is 1 or not! Meaning that one can provide the same proof just by providing an array [k, 1, ..., 1] since:
Even further, if is even one can do:
These are classified as soundness errors, as they allow creating of valid proofs without actually proving the intended statement.
The circuit author is responsible from checking these edge-cases, and writing the necessary constrains to prevent soundness errors.
Constraint Count
Each multiplication of two signals is one constraint, so Multiplier(n) has non-linear constraints, e.g. 9 for 10 numbers.
Addition
Adding an array of values and returning the sum is a common operation within circuits.
Adder
template Adder(n) {
signal input in[n];
signal output out;
var lc = 0;
for (var i = 0; i < n; i++) {
lc += in[i];
}
out <== lc;
}
No matter how large is, a sum operation is just a single linear constraint! Formally, for an array with sum the following is a valid rank-1 constraint:
The variable lc within the code stands for “linear combination” and its just a variable that stores the expression on the right hand-side in equation above:
lc = in[0] + in[1] + ... + in[n-1]
Constraint Count
Adder(n) has 0 non-linear constraints, no matter how large n is. Its only constraint is linear, and linear constraints are free: the compiler simply substitutes out with the sum wherever it is used.
Inversion
The (multiplicative) inverse of an element within a prime field is denoted as such that . An additive inverse of is shown as and it holds that . Inverting an element within the circuit is inefficient, so the inverse is computed off-circuit and a constraint is added to make sure their multiplications result in 1.
Inverse
template Inverse() {
signal input in;
signal output out;
assert(in != 0);
signal inv <-- in != 0 ? 1 / in : 0;
signal isZero <== 1 - (in * inv);
// if isZero, since in = 0 this holds
// otherwise, it holds due to in * 0 == 0
in * isZero === 0;
inv * isZero === 0;
out <== inv;
}
Zero does not have a multiplicative inverse though. The assert(in != 0) above only runs while computing the witness, and it does not add any constraint, so a malicious prover could still provide a witness with in = 0. So the circuit handles that case with constraints as well, very much like IsZero:
- If
inis not zero,in * isZero === 0forcesisZero = 0, which meansin * inv = 1, i.e.invis the inverse ofin. - If
inis zero, thenisZero = 1, andinv * isZero === 0forcesinv = 0.
So the circuit returns 0 for an input of 0, and it is up to the caller to make sure that this is acceptable, or that the input is non-zero.
There are two ways to find an inverse outside the circuit:
- Use Extended Euclidean Algorithm
- Use Fermat’s Little Theorem
Interested reader can check them out on the web!
Constraint Count
Inverse has 3 non-linear constraints: one for isZero, and one for each of the two checks.
Integer Division
Integer division returns the quotient of two numbers, rounded down, e.g. . This is different from the division in a prime field, where is the field element that gives 7 when multiplied by 2.
IntDiv
template IntDiv(n) {
// ensures that `quot * in[1] + rem` can not wrap around the field
assert(n <= 125);
signal input in[2];
signal output out;
// divisor must be non-zero
signal is_non_zero <== IsZero()(in[1]);
0 === is_non_zero;
// compute the quotient and remainder outside the circuit
var quot_hint = in[0] \ in[1];
var rem_hint = in[0] % in[1];
signal quot <-- quot_hint;
signal rem <-- rem_hint;
// quotient & remainder must be n-bit numbers, otherwise a dishonest prover can
// pick a "negative" remainder (a large field element) that still passes the
// `rem < in[1]` check, or a quotient that is a field division `in[0] / in[1]`
_ <== Num2Bits(n)(quot);
_ <== Num2Bits(n)(rem);
// constrain the division operation
// in[0] / in[1] is defined as the unique pair (q, r) s.t.
// in[0] = in[1] * q + r and 0 <= r < |in[1]|
in[0] === quot * in[1] + rem;
component remIsLess = LessThan(n);
remIsLess.in <== [rem, in[1]];
remIsLess.out === 1;
out <== quot;
}
Doing integer division within a circuit is more costly than what one might one expect! Consider two -bit numbers and . An integer division implies the following equation:
where is the quotient, and is the remainder such that . As an example, consider the division . We have:
giving us the quotient and remainder . Notice that if we allowed , we could have:
which would be wrong! This is why we constrain the remainder with LessThan, to ensure .
However, that check alone is not enough. Remember that we are working in a prime field, where a “negative” number such as is actually a very large number . Consider the following:
This is a quotient with a remainder , which is wrong since should give . Is ? It should not be in the field, as is a very large number there; however, LessThan(n) is only correct for -bit inputs! It computes , which is an -bit number with its ’th bit unset, so it says that . A dishonest prover could then claim that .
To prevent this, we range-check both the quotient and the remainder using Num2Bits(n):
- With , the remainder can not be “negative” anymore, and
LessThan(n)can safely check . - With , the quotient can not be a field element like , which would satisfy in the field for any .
Finally, we must make sure that can not wrap around the field, otherwise the equation would only hold “modulo ” instead of over the integers. As and are -bit numbers, and can be at most bits (otherwise LessThan fails), the result is less than . The assert(n <= 125) ensures that this is less than the prime of BN254, which is around .
With these checks, the circuit has a unique solution for given and : the quotient and remainder of the usual integer division.
Constraint Count
IntDiv(n) has non-linear constraints, e.g. 50 for 16-bit numbers. Almost all of them come from the bit decompositions: the two range checks of the quotient & the remainder, and the -bit decomposition within LessThan.
Bits
A bit value can only be 0 or 1. As such, they can be treated as booleans too, where 0 is false and 1 is true. It is often useful to convert a number to it’s binary representation, or simply assert that a number can fit into n-bits for some n that is known at compile time.
AssertBit
template AssertBit() {
signal input in;
in * (in - 1) === 0;
}
To assert that a given number is bit (i.e. 0 or 1) you only have to check that , as there are only two numbers whose square equals to itself: 0 and 1. This expression is equivalent to , which is how we’ve written in the circuit above.
Normally people assert that a signal is bit without the template above; instead, it is preferred to do this inline where it is needed. Well, nothing really stops you from using templates.
Num2Bits
template Num2Bits(n) {
assert(n < 254);
signal input in;
signal output out[n];
var lc = 0;
var bit_value = 1;
for (var i = 0; i < n; i++) {
out[i] <-- (in >> i) & 1;
AssertBit()(out[i]);
lc += out[i] * bit_value;
bit_value <<= 1;
}
lc === in;
}
Num2Bits is an often used circuit that decomposes a given number to n bits. In doing so, it will assert that the number is representable by that many bits too. The binary decomposition happens the way it is done in most languages: shift and get the last bit, within a loop.
The operation (in >> i) & 1 is non-quadratic, so we have to use <-- there to assign the result to out[i] signal. At this point, out[i] can be anything given by a malicious prover, we have to constrain it. At the very least, we can assert out[i] to be a bit.
The important constraint in this template is that out when converted back to decimal should equal our number in. We make that constraint using the lc variable, which really acts like a sum in programming. It is important to remember at this point that Circom is an HDL, instead of a programming language. So, if we were to treat lc like some variable that is storing the sum, it won’t really be the reality. Here instead lc is a linear-combination of the signals:
lc = out[0]*1 + out[1]*2 + out[2]*4 + ... + out[n-1]*2^(n-2)
Thankfully, this entire equality is a quadratic constraint and we can simply check if lc === in to ensure the bitwise representation is correct.
Exercise: How would you modify
Num2Bitsabove to obtain a template likeAssertBits(n)that ensures a number can be represented bynbits?
Bits2Num
template Bits2Num(n) {
assert(n < 254);
signal input in[n];
signal output out;
var lc = 0;
var bit_value = 1;
for (var i = 0; i < n; i++) {
AssertBit()(in[i]);
lc += in[i] * bit_value;
bit_value <<= 1;
}
out <== lc;
}
If we can convert from an n-bit number to its binary representation, surely we should be able to convert from the binary representation with n-bits to the number itself. We do that with Bits2Num. This operation is rather straightforward, we just need to compute:
We use bit_value to keep track of , and this entire sum expression is stored within the lc (linear combination). In the end, we constrain the output signal to be equal to this expression.
Note that for both
Num2BitsandBits2Num, the most-significant bit is the last element of the array, and least-significant bit is the first element of the array. To demonstrate, consider the 4-bit number 11, normally shown as in maths. However, in these circuits we store the array[1, 1, 0, 1], in the opposite order!
Function: nbits
function nbits(n) {
var ans = 0;
// shift `n` to the right until all of its bits are consumed
while (n != 0) {
n >>= 1;
ans++;
}
return ans;
}
We might want to find the minimum number of bits required to represent a known value; we use a function called nbits (as in Circomlib) for that. Here, our parameter n is known at compile time, perhaps a generic argument or some constant somewhere.
The idea of this function is to shift the number to the right one bit at a time, counting how many shifts it takes until nothing is left. For example, becomes , , and finally , so nbits(9) = 4.
You may think of a loop such as
while (2**ans - 1 < n)instead, but beware: Circom compares field elements as signed numbers, where values larger than are negative. For example,-1 < 0is true, even though-1is actually in the field. Shifts on the other hand work with the actual value, so with shiftsnbits(-1)correctly returns the number of bits of the largest field element, which is 254 for BN254.
Constraint Count
| Circuit | Constraints |
|---|---|
AssertBit | 1 |
Num2Bits(n) | |
Bits2Num(n) |
Every bit costs one constraint, to assert that it is a bit; the sum of the bits is a linear combination, which is free. The function nbits is computed at compile time, so it has no constraints at all.
Logic Gates
It is often required to do some logical operations like AND, OR, NOT and XOR within a circuit. For the circuits within this chapter, we can assume that the inputs are asserted to be bits, i.e. they are either 0 or 1.
AND
template AND() {
signal input in[2];
signal output out;
out <== in[0]*in[1];
}
The logic table of AND is as follows:
| 0 | 1 | |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
This can be achieved by simply multiplying the two inputs!
OR
template OR() {
signal input in[2];
signal output out;
out <== in[0] + in[1] - in[0]*in[1];
}
The logic table of OR is as follows:
| 0 | 1 | |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 1 |
We almost achieve the result by adding the two numbers, except that we get 2 when both are 1. Well, AND is only 1 when both numbers are 1, so we subtract it from the result to solve that issue.
What we have is equivalent to in[0] + in[1] - AND(in).
XOR
template XOR() {
signal input in[2];
signal output out;
out <== in[0] + in[1] - 2*in[0]*in[1];
}
The logic table of XOR is as follows:
| 0 | 1 | |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
We can use the same trick for OR, just once more, to make the 1 + 1 turn to a zero. What we have is equivalent to in[0] + in[1] - 2 * AND(in).
NOT
template NOT() {
signal input in;
signal output out;
out <== 1 - in;
}
A NOT gate maps 0 to 1, and 1 to 0. We can achieve this by simply subtracting the signal from 1. Since and .
NAND
template NAND() {
signal input in[2];
signal output out;
out <== 1 - (in[0]*in[1]);
}
NAND is equivalent to NOT(AND(in)), giving us the circuit above.
NOR
template NOR() {
signal input in[2];
signal output out;
out <== 1 - (in[0] + in[1] - in[0]*in[1]);
}
NOR is equivalent to NOT(OR(in)), giving us the circuit above.
Constraint Count
Each gate with two inputs multiplies them once, so AND, OR, XOR, NAND and NOR have 1 non-linear constraint each, while NOT is linear and has none.
Comparators
Comparators compare two numbers in an arithmetic circuit. At the most basic level, we are interested in comparing a number to zero. Then, we can derive an equality check by simply checking if the difference of inputs is equal to zero.
- is the
IsZerocircuit
We usually make use of LessThan circuit which does a < b check, and derive all other remaining comparisons from that. This should make sense, since assuming both a and b are integers we can say:
- is the
LessThancircuit
IsZero
template IsZero() {
signal input in;
signal output out;
signal inv <-- in != 0 ? 1 / in : 0;
out <== 1 - (in * inv);
in * out === 0;
}
Here, we check if the given number has a multiplicative inverse. The only number that does not have an inverse is 0. However, inverting a number is a non-quadratic constraint (hence the <-- instead of <==) so must assume that signal inv can be any arbitrary value from the perspective of an adversarial prover. To constrain inv, we can invert it again! Notice that:
We can’t really add a constraint like 1 === in * inv because it will simply fail when in is 0. That is why we make use of a ternary operator to simply set inv to be zero if in is zero. So, we may expect in * inv to equal 1 if indeed the number has an inverse, meaning that the number is non-zero. By subtracting this from 1, we essentially do a logical NOT operation on the result, so that if the in has an inverse out becomes 0.
Let’s examine what happens when an adversary inputs some random inv on both cases where in is zero and non-zero:
When in = 0 and inv = x all constraints are looking good:
out <== 1 - 0constraint is fine0 * out <== 0constraint is fine
When in != 0 and inv = x the constraint is indirectly implied:
out <== 1 - in * xin * (1 - in * x) <== 0
Here, out could be anything but for in * (1 - in * x) <== 0 to pass the only option is that 1 === in * x so x must indeed be the inverse of in.
IsEqual
template IsEqual() {
signal input in[2];
signal output out;
out <== IsZero()(in[1] - in[0]);
}
As we mentioned before, if a = b then a - b = 0, allowing us to re-use the IsZero circuit.
LessThan
template LessThan(n) {
assert(n <= 252);
signal input in[2];
signal output out;
// convert in[0] - in[1] + 2^n to bits
// if in[0] > in[1], 2^n'th bit should be set
// if in[0] < in[1], 2^n'th bit should be reset due to subtraction borrow
component toBits = Num2Bits(n+1);
toBits.in <== ((1 << n) + in[0]) - in[1];
out <== 1 - toBits.out[n];
_ <== toBits.out; // only the n'th bit is needed
}
There is something going on here as you might notice, why are we using Num2Bits and what is that 1 << n doing there? It will all make sense.
The trick of LessThan is to think of bitwise-subtraction. Think of subtracting two n-bit numbers, a - b. Now suppose that during this subtraction the n-bit is set to 1, which is what 1 << n does. Note that the most significant bit of an n-bit number is (n-1)’th bit, as we are speaking in zero-indexed terms.
If a is less than b, then during this subtraction a will have to borrow that n’th bit. Otherwise, it is large enough that b can be subtracted without needing to borrow. To see if a < b we can simply check if n’th bit is borrowed or not during a subtraction. Since n’th bit will be 0 if it is borrwed, we must do a logical NOT operation (simply subtract the result from 1) as we assign it to the output.
The role of assert(n <= 252) is to ensure we can safely set n’th bit to 1. That would be a problem if n were to be greater than 252, as that is where the order of scalar field of our curve (BN254 in this case) is cut-off.
LessThandoes not check that its inputs aren-bit numbers, and if they are not, the result may be silently wrong. For example,-1is a very large number in the field, yetLessThan(n)([-1, 0])returns 1 since is an -bit number with its ’th bit unset. So the caller must range-check the inputs, e.g. withNum2Bits(n), unless they are already known to be small enough. See integer division for an example where forgetting this breaks the circuit.
LessEqThan
template LessEqThan(n) {
signal input in[2];
signal output out;
out <== LessThan(n)([in[0], in[1]+1]);
}
This is because .
GreaterThan
template GreaterThan(n) {
signal input in[2];
signal output out;
out <== LessThan(n)([in[1], in[0]]);
}
This is because .
GreaterEqThan
template GreaterEqThan(n) {
signal input in[2];
signal output out;
out <== LessThan(n)([in[1], in[0]+1]);
}
This is because .
Constraint Count
| Circuit | Constraints |
|---|---|
IsZero | 2 |
IsEqual | 2 |
LessThan(n) | |
LessEqThan(n) | |
GreaterThan(n) | |
GreaterEqThan(n) |
The cost of LessThan is its -bit decomposition, and the others are just LessThan with different inputs.
Constant Comparisons
Circomlib comes with a more efficient method when we are comparing one signal with another constant. In this section, we will explain the constant-comparison method along with several of its usages.
These methods depend on the prime field used within the circuit, and therefore re-using these same circuits may cause bugs due to hard-coded values in other prime fields!
Note that these circuits take the bits of a number as input, but do not constrain them to be bits; the caller must ensure that, e.g. by obtaining them from Num2Bits.
CompConstant
template CompConstant(constant) {
signal input in[254];
signal output out;
// The input is compared with the constant pair-by-pair, i.e. as 127 base-4 digits.
// At pair i, we add:
// a_i = 2^i if the signal pair is LESS than the constant pair
// b_i = 2^128 - 2^i if the signal pair is GREATER than the constant pair
//
// Note that b_i is -2^i in 128-bit two's complement, so modulo 2^128 the sum is:
// (sum of 2^i over "less" pairs) - (sum of 2^i over "greater" pairs)
// The most-significant differing pair outweighs all lower ones combined
// (2^i > 2^(i-1) + ... + 1), so its sign is the sign of the sum, just like
// ordinary magnitude comparison.
var a = 1;
var b = (1 << (128)) - 1;
var sum = 0;
var bit_value = 1;
signal parts[127];
signal out_bits;
for (var i = 0; i < 127; i++) {
// Extract the i-th 2-bit digit of the constant (bit positions i*2 and i*2+1)
var constant_lsb = (constant >> (i*2)) & 1;
var constant_msb = (constant >> (i*2 + 1)) & 1;
// Extract the i-th 2-bit digit of the input signal
var in_lsb = in[i*2];
var in_msb = in[i*2 + 1];
// part_bit_a: 1 iff the signal's 2-bit digit >= the constant's 2-bit digit
// part_bit_b: 1 iff the signal's 2-bit digit > the constant's 2-bit digit
//
// These are computed using boolean arithmetic on the input bits.
// Note: x + y - x*y = OR(x, y), and x*y = AND(x, y).
var part_bit_a;
var part_bit_b;
/**/ if ((constant_msb == 0) && (constant_lsb == 0)) {
// constant pair = 0: signal >= 0 is always true; signal > 0 iff any bit set
part_bit_a = 1;
part_bit_b = in_msb + in_lsb - in_msb*in_lsb; // OR(msb, lsb)
}
else if ((constant_msb == 0) && (constant_lsb == 1)) {
// constant pair = 1: signal >= 1 iff any bit set; signal > 1 iff msb set
part_bit_a = in_msb + in_lsb - in_msb*in_lsb; // OR(msb, lsb)
part_bit_b = in_msb;
}
else if ((constant_msb == 1) && (constant_lsb == 0)) {
// constant pair = 2: signal >= 2 iff msb set; signal > 2 iff both bits set
part_bit_a = in_msb;
part_bit_b = in_msb*in_lsb; // AND(msb, lsb)
}
else if ((constant_msb == 1) && (constant_lsb == 1)) {
// constant pair = 3: signal >= 3 iff both set; signal > 3 is impossible
part_bit_a = in_msb*in_lsb; // AND(msb, lsb)
part_bit_b = 0;
}
else assert(0 != 0); // impossible case
// Combine into the weighted contribution for this pair:
// signal pair < constant pair → part_bit_a=0, part_bit_b=0 → +a (penalty)
// signal pair = constant pair → part_bit_a=1, part_bit_b=0 → 0 (neutral)
// signal pair > constant pair → part_bit_a=1, part_bit_b=1 → +b (reward)
parts[i] <== (a * (1 - part_bit_a)) + (b * part_bit_b);
// accumulate parts
sum += parts[i];
// Advance weights: a doubles, b shrinks by the same amount, preserving
// the invariant that higher pairs dominate all lower ones.
b -= bit_value;
a += bit_value;
bit_value <<= 1;
}
// Bit 127 is the sign bit of the sum in 128-bit two's complement:
// - If in > constant, the sum is "negative" modulo 2^128, so bit 127 is set.
// - If in <= constant, the sum is "non-negative" modulo 2^128, so bit 127 is clear.
// Bits above 127 are just the overflow of the 2^128 terms, and are ignored.
//
// 135 bits are needed because the maximum possible sum is:
// sum_max = Σ(i=0..126) b_i = Σ(i=0..126) (2^128 - 2^i)
// = 127·2^128 - (2^127 - 1)
// = 2^135 - 2^128 - 2^127 + 1
// which fits in 135 bits but not 134.
out_bits <== sum;
component num2bits = Num2Bits(135);
num2bits.in <== out_bits;
out <== num2bits.out[127];
// only bit 127 is needed, suppress "unused" warning with `_ <==`
_ <== num2bits.out;
}
CompConstant returns 1 if in > constant, where in is given as 254 bits and constant is known at compile time. This circuit comes from Circomlib, and it looks rather mysterious at first. Let us take it apart piece by piece.
Comparing Digit by Digit
Think of how you compare two numbers by hand: you look at their digits from the most significant one, and the first digit where they differ decides the result. For example, because of the second digit, no matter what the remaining digits are.
CompConstant does the same, but instead of decimal digits it uses pairs of bits, i.e. base-4 digits. The 254 bits of in make up 127 pairs, in[2i] being the least-significant bit (in_lsb) and in[2i+1] the most-significant bit (in_msb) of the ’th pair. The same is done for the constant, which is known at compile time, so its pairs are just numbers.
For each pair , we compare the digit of in (call it ) with the digit of the constant (call it ) using two bits:
part_bit_ais 1 ifpart_bit_bis 1 if
Since is a constant, we can write these with a simple expression for each of its four possible values, where :
| 0 | always | either bit is set, OR(in_msb, in_lsb) |
| 1 | either bit is set, OR(in_msb, in_lsb) | , in_msb |
| 2 | , in_msb | , AND(in_msb, in_lsb) |
| 3 | , AND(in_msb, in_lsb) | never |
These are exactly the four branches in the loop, using the logic gates OR(x, y) = x + y - xy and AND(x, y) = xy.
Weighting the Digits
Next, each pair contributes a part to a sum:
parts[i] <== (a * (1 - part_bit_a)) + (b * part_bit_b);
There are three cases here:
- : both bits are 0, so we add
a. - : only
part_bit_ais 1, so we add 0. - : both bits are 1, so we add
b.
What are a and b? They start at and , and at the end of each iteration a grows by bit_value and b shrinks by bit_value, which doubles every time. Following the loop, at pair we have:
Here is the idea behind these values. Suppose we could add for a pair where in is smaller, and for a pair where in is larger. The most significant differing pair, say at position , contributes , and all the pairs below it can contribute at most
So, just like comparing by hand, the most significant differing pair decides the sign of the sum: it is negative if and only if in > constant.
The problem is that there are no negative numbers in our circuits, only field elements. So instead of , CompConstant uses , which is how is represented in 128-bit two’s complement. That is , while is the positive term.
Reading the Sign
In 128-bit two’s complement, the sign is the bit 127: a number is negative if and only if its bit 127 is set. So at the end, we decompose the sum into bits with Num2Bits and return its bit 127.
The sum itself is not a 128-bit number though, since every “greater” pair adds a on top. If there are such pairs, the sum is:
The part only affects the bits from 128 and above, so the bits 0 to 127 are exactly the two’s complement form of the bracketed difference. In other words, we only read bit 127 and ignore the rest.
As an example, let the constant be , which is in base-4. Here is what happens for a few inputs:
in | base-4 | pair 1 | pair 0 | sum | bit 127 | out |
|---|---|---|---|---|---|---|
| 3 | less, | greater, | 0 | 0 | ||
| 5 | equal, | less, | 0 | 0 | ||
| 6 | equal, | equal, | 0 | 0 | ||
| 7 | equal, | greater, | 1 | 1 | ||
| 8 | greater, | less, | 1 | 1 |
Notice the first row: the lower pair is “greater”, so the sum goes beyond , but it is the higher pair that decides, and bit 127 correctly stays 0.
Why 135 Bits?
The largest possible sum is when all 127 pairs are “greater”:
So 135 bits are enough to decompose the sum, and we need all of them even though only bit 127 is used: with fewer bits, Num2Bits would fail for large sums. The _ <== num2bits.out line tells the compiler that the other bits are unused on purpose.
Why Pairs of Bits?
It may seem simpler to compare bit by bit, but then we would have 254 digits with weights up to , and we would need 254-bit two’s complement. The sum would be around , way larger than the order of the field (), so it would wrap around and the trick would break.
With pairs, there are only 127 digits, the sum stays below , and it never wraps around. Comparing a pair with a constant digit still takes a single multiplication (in_msb * in_lsb), so each part is one constraint. In total, CompConstant has 262 non-linear constraints: 127 for the parts, and 135 for the decomposition. Compare that with a LessThan(254), which is not even possible since LessThan requires n <= 252!
AliasCheck
template AliasCheck() {
signal input in[254];
component comparator = CompConstant(-1);
for (var i = 0; i < 254; i++) {
comparator.in[i] <== in[i];
}
comparator.out === 0;
}
Alias check simply asserts that a given 254-bit number is within the prime field of BN254. The role of -1 there is just a short-cut to obtain the largest number within the field, .
Why would we need this? 254 bits can represent numbers up to , which is larger than . So a field element may have two different 254-bit representations, and , which are called aliases. If a circuit uses Num2Bits(254) without an alias check, a dishonest prover can pick the bits of instead of . AliasCheck asserts that the bits represent a number , which rules out the alias.
Sign
template Sign() {
signal input in[254];
signal output out;
var half = 1 / 2;
component comparator = CompConstant(half - 1);
for (var i = 0; i < 254; i++) {
comparator.in[i] <== in[i];
}
out <== comparator.out;
}
In a prime field, a field element is defined to be positive if it is closer to 0 than it is to the order of the field. Sign checks for that property and returns 0 if the number is positive, otherwise 1 if the number is negative. Specifically, for order and a number the sign of is:
- positive when
- negative when
Here, 1 / 2 is a field division, i.e. the inverse of 2, which is . So half - 1 is , and CompConstant returns 1 exactly when the number is negative.
Constraint Count
| Circuit | Constraints |
|---|---|
CompConstant | 262 |
AliasCheck | 261 |
Sign | 262 |
Note that these take the bits of a number as input, so if you also need to decompose a number into bits with Num2Bits(254), that is another 254 constraints.
Range Checks
A range-check is a common utility, asserting that a number is in some range [MIN, MAX]. It is important to keep in mind that you can make use of bit-decompositions to check for range [0, 2^n), which would be done by simply checking if a number is representable with n-bits.
Other zkDSLs often use lookup tables for range checks, which can be much cheaper than bit decompositions. Circom compiles to R1CS, which has no lookup tables, so we use bit decompositions instead.
AssertInRange
template AssertInRange(MIN, MAX) {
assert(MIN < MAX);
signal input in;
var b = nbits(MAX);
// find `in - MIN`:
// if `in > MIN` this is a b-bit value
// otherwise, it will underflow due to negation,
// and may be larger than MAX
component lowerBound = AssertBits(b);
lowerBound.in <== in - MIN; // e.g. 1 - 1 = 0 (for 0 <= in)
// find `in + 2^b - MAX - 1`
// if `in < MAX` this will result in a value less than `2^b - 1`
// ensuring that it is a b-bit value, otherwise this will be a value
// larger than b-bits
component upperBound = AssertBits(b);
upperBound.in <== in + (2 ** b) - MAX - 1; // e.g. 9 + (15 - 9) = 15 (for in <= 15)
}
Above is one way of doing a generic range check. Our approach here is to check:
in - MINis a b-bit valuein + 2^b - 1 - MAXis a b-bit value
where b is the minimum number of bits required to represent MAX. The nbits function is described within the bits section.
If in < MIN, the operation in - MIN will underflow and we will have a huge number, definitely not be b-bit representable (assuming a not-so-large MAX). As an edge case, if in == MIN we get 0, which is definitely b-bits.
If in > MAX, the operation in + 2^b - 1 - MAX becomes larger than 2^b - 1, which is not b-bit representable. As an edge case, if in == MAX we get 2^b - 1, which is the largest b-bit number.
Constraint Count
AssertInRange(MIN, MAX) decomposes two numbers into bits, where is the number of bits of MAX, so it has non-linear constraints. For example, AssertInRange(1, 9) has 8, and AssertInRange(0, 1000) has 20.
Control Flow
In the world of arithmetic circuits, control flow is a bit different than what most developers are used to. In normal programming, only one of the branches are executed:
if (cond) {
foo(); // only if cond == true
} else {
bar(); // only if cond == false
}
That is not how things work in our circuits! Instead, both branches are executed but only one of them is “returned”.
To understand why, first remind yourself that we are ALWAYS working with integers in our circuits. Both foo() and bar() will return an integer, and cond is either 0 or 1. The trick is to combine these results with cond and NOT(cond) in a simple sum expression:
cond*foo() + NOT(cond)*bar();
Opening this up, we have:
cond*foo() + (1-cond)*bar();
In fact, we can use one multiplication instead of two, using the following form:
cond*(foo() - bar()) + bar();
IfElse
template IfElse() {
signal input cond;
signal input ifTrue;
signal input ifFalse;
signal output out;
out <== cond * (ifTrue - ifFalse) + ifFalse;
}
Following our description above, an if-else is defined by the given circuit. Remember that both ifTrue and ifFalse signals are computed, regardless of the condition, but only one of them is returned.
IfElse(andSwitchbelow) does not constraincondto be a bit. Ifcondis some other value, the output is a mix of both branches, which a dishonest prover can often exploit. The caller must ensure thatcondis a bit, e.g. withAssertBit, unless it is already the output of a bit-returning circuit such asIsEqual.
Conditional Constraints
In your application, there may be cases where ifTrue and ifFalse can’t be valid at the same time, due to some condition; ifTrue might constrain a signal to be 0 but ifFalse might constrain that same signal to something else.
In these cases, we may add an auxillary signal which can enable/disable a constraint check. As an example, imagine the following template that constraints a signal to be 5:
template IsFive() {
signal input in;
in - 5 === 0;
}
We can add an auxillary isEnabled signal that is either 0 or 1, and disable this circuit when isEnabled = 0 as follows:
template IsFive() {
signal input in;
signal input isEnabled;
isEnabled * (in - 5) === 0;
}
If isEnabled = 1 both circuits are equivalent, but if isEnabled = 0 this circuit will always have 0 === 0 regardless of the in signal.
Circomlib has a circuit that makes use of this trick, see
ForceEqualIfEnabled.
Switch
template Switch() {
signal input cond;
signal input in[2];
signal output out[2];
out[0] <== cond * (in[1] - in[0]) + in[0];
out[1] <== cond * (in[0] - in[1]) + in[1];
}
It is often useful to switch the places of two signals based on a condition, which can be achieved with two IfElse lines together.
You can do this with a single multiplication too!
template Switch() { signal input cond; signal input in[2]; signal output out[2]; signal aux <== (in[1] - in[0]) * cond; out[0] <== aux + in[0]; out[1] <== -aux + in[1]; }
Constraint Count
Both IfElse and Switch have a single non-linear constraint, the multiplication with cond.
Multiplexing
Multiplexing is a technique to select one of many signals based on a control signal. It is often used to switch between different signals or to select a signal based on a condition.
Mux1
template Mux1() {
signal input in[2];
signal input sel;
signal output out;
out <== (in[1] - in[0]) * sel + in[0];
}
Mux1 is actually the same circuit as IfElse we defined in this section. Its just that the naming is a bit different, such that it is generalizable to higher multiplexers.
in[0]isifFalsein[1]isifTrueseliscondoutisout
The main idea here is that in has number of values equal to the number of bits of sel, and out = in[sel].
Mux2
template Mux2() {
signal input in[4];
signal input sel[2];
signal output out;
// due to multiplication we need an auxiliary signal
signal sel_0_sel_1 <== sel[1] * sel[0];
signal a11 <== (in[3] - in[2] - in[1] + in[0]) * sel_0_sel_1;
signal a10 <== (in[2] - in[0]) * sel[1];
signal a01 <== (in[1] - in[0]) * sel[0];
signal a00 <== in[0];
out <== (a11 + a10 + a01 + a00);
}
Mux2 is a 2-bit multiplexer, which means it can select one of four inputs based on two control signals. The arithmetic above may look weird, but its actually simple to derive. Just think of the sel cases in order (note that the bits are in little-endian):
sel = [0, 0]: You needin[0]here, and sinceselmultiplications will be 0, you needin[0]added by default.sel = [1, 0]: You needin[1], butin[0]was added already as a constant so you needin[1] - in[0]in total.sel = [0, 1]: Similar to the previous case, you needin[2], butin[0]was added already as a constant so you needin[2] - in[0]in total.sel = [1, 1]: You needin[3], but now we have all things from the previous cases added together, which is a total:in[0] + (in[1] - in[0]) + (in[2] - in[0]). We need to addin[3]and get rid of evertyhing else here, which gives usin[3] - in[2] - in[1] + in[0].
You can actually construct a
Mux2using threeMux1circuits.template Mux2() { signal input in[4]; signal input sel[2]; signal output out; signal inA <== Mux1()([in[0], in[1]], sel[0]); signal inB <== Mux1()([in[2], in[3]], sel[0]); out <== Mux1()([inA, inB], sel[1]); }In fact, this has 3 non-linear constraints while the previous implementation has 4 non-linear constraints!
Larger Multiplexers
There are larger multiplexing circuits, e.g. Mux3, Mux4, etc. but we will not cover them here. You can construct them with a similar approach as we did for Mux2, i.e. by using smaller multiplexers and combining them.
Constraint Count
Mux1 has 1 non-linear constraint, the multiplication with sel, and Mux2 has 4: one for sel[1] * sel[0], and three for the multiplications with the selectors.
Arrays
Circom arrays are a different kind of beast. The main reason is that in Circom, array operations must be known at compile-time. What do we mean by this:
- Array sizes are fixed, e.g. you can’t define an array based on the user input after compiling the circuit.
- Array indexing should be known at compile time, e.g. you can’t ask a user for index
iand returnarr[i]like you normally do.
Before we get to the problematic unknown-at-compile-time stuff, let’s quickly recap the known-at-compile-time array operations:
// an array with N elements
signal arr[N];
// a multi-dimensional array of size N * M
signal arr[N][M];
// read element at index i for known i
foo <== arr[i];
// write to element at index j for known j
arr[j] <== bar;
So now, what if we want to read or write to an index unknown at compile time?
ArrayRead
template ArrayRead(n) {
signal input in[n];
signal input index;
signal output out;
signal intermediate[n];
for (var i = 0; i < n; i++) {
var isIndex = IsEqual()([index, i]);
intermediate[i] <== isIndex * in[i];
}
out <== Adder(n)(intermediate);
}
To read an unknown index, we could instead read ALL signals (which is an operation known-at-compile-time) and then return a linear combination of them, with each value multiplied with an equality-check with our index.
arr_i =
A[0] * (i == 0)
+ A[1] * (i == 1)
+ ...
+ A[n-1] * (i == n-1)
This way, our array accesses are known at compile-time but we are still able to get the value at index i, albeit at the cost of some constraints.
arr_i =
A[0] * 0
+ A[1] * 0
+ ...
+ A[i] * 1
+ ...
+ A[n-1] * 0
= A[i]
In the paper xJsnark, this method is referred to as “Linear Scan”.
If
indexis not within , all of the equality checks are 0, andArrayReadsimply returns 0 instead of failing. If the index comes from the prover, you should range-check it yourself; see Two Sum for an example where forgetting this breaks the circuit.
ArrayWrite
template ArrayWrite(n) {
signal input in[n];
signal input index;
signal input value;
signal output out[n];
for (var i = 0; i < n; i++) {
var isIndex = IsEqual()([index, i]);
out[i] <== IfElse()(isIndex, value, in[i]);
}
}
Writing to an unknown-index works in a similar way to reading one. The idea is to simply copy the input signal array to an output array, but only at the index i we will use our new value instead of the existing one at in[i].
We have defined the
IfElsetemplate under the Control Flow section.
Constraint Count
Both ArrayRead(n) and ArrayWrite(n) compare the index with every position of the array, using an IsEqual (2 constraints) and a multiplication (1 constraint) for each, so they have non-linear constraints, e.g. 30 for an array of 10 elements.
Distinct
We may often require to check if an array has non-repeating values, also known as unique values or distinct values. A common example of this would be for a Sudoku circuit, e.g. you would like to assert that all values in a row are in range [1, 9] and that the row has distinct values.
AssertDistinct
template AssertDistinct(n) {
signal input in[n];
var acc = 0;
for (var i = 0; i < n-1; i++){
for (var j = i+1; j < n; j++){
var eq = IsEqual()([in[i], in[j]]);
acc += 1 - eq;
}
}
acc === n * (n - 1) / 2;
}
To assert that an array has distinct values, we can loop over the values and check each unique pair to be non-equal using the IsEqual template. For example, in an array of 4 elements this corresponds to the following checks:
IsEqual()([in[0], in[1]]) === 0
IsEqual()([in[0], in[2]]) === 0
IsEqual()([in[0], in[3]]) === 0
IsEqual()([in[1], in[2]]) === 0
IsEqual()([in[1], in[3]]) === 0
IsEqual()([in[2], in[3]]) === 0
We could have a constraint on each iteration, but instead we can sum all the results and see if all were zero in one constraint, as done with the acc variable above.
IsDistinct
template IsDistinct(n) {
signal input in[n];
signal output out;
var acc = 0;
for (var i = 0; i < n-1; i++){
for (var j = i+1; j < n; j++){
var eq = IsEqual()([in[i], in[j]]);
acc += eq;
}
}
// note that technically it is possible for `acc` to overflow
// and wrap back to 0, however, that is unlikely to happen given
// how large the prime-field is and we would need that many components
// to be able to overflow
signal outs <== acc;
out <== IsZero()(outs);
}
If you would like to return a bit-signal based on whether an array has all distinct values or not, you can slightly modify the AssertDistinct template to obtain that functionality. Instead of asserting each IsZero check, we accumulate them and then return whether that final sum is equal to zero or not.
Note that technically it is possible for
accto overflow and wrap back to 0, however, that is unlikely to happen given how large the prime-field is and we would need that many components to be able to overflow using 1+1+…+1 only.
Constraint Count
Both circuits compare every pair of elements with an IsEqual, so AssertDistinct(n) has non-linear constraints, e.g. 90 for 10 elements, and IsDistinct(n) has two more for its final IsZero. This quadratic cost is worth keeping in mind for large arrays.
Sorted
If we need an array to be sorted, we could sort the array out-of-circuit and pass in the sorted array, finally asserting that it is sorted indeed. To do this, we can simply check that consecutive elements are ordered, that is for all .
IsSorted
template IsSorted(n, b) {
signal input in[n];
signal output out;
// range check
for (var i = 0; i < n; i++) {
_ <== Num2Bits(b)(in[i]);
}
// accumulator for in[i-1] <= in[i] checks
var acc = 0;
for (var i = 1; i < n; i++) {
var isLessThan = LessEqThan(b)([in[i-1], in[i]]);
acc += isLessThan;
}
// sorted only if all `n - 1` pairs are ordered
out <== IsEqual()([acc, n - 1]);
}
Since the correctness of LessEqThan(b) is guaranteed only for inputs of at most b bits, we also add a range check using Num2Bits(b), which internally asserts that the input fits within b bits.
Each LessEqThan returns 1 for an ordered pair, so acc counts the ordered pairs. There are pairs, and the array is sorted only if all of them are ordered, so we return whether acc equals .
Be careful to not check whether
accis non-zero instead: that only tells that some pair is ordered, and an array like[0, 1, 2, 4, 3]would be considered sorted!
AssertSorted
template AssertSorted(n, b) {
signal input in[n];
// range check
for (var i = 0; i < n; i++) {
_ <== Num2Bits(b)(in[i]);
}
// accumulator for in[i-1] <= in[i] checks
var acc = 0;
for (var i = 1; i < n; i++) {
var isLessThan = LessEqThan(b)([in[i-1], in[i]]);
acc += isLessThan;
}
acc === n - 1;
}
If you would like to assert that the array is sorted instead of returning 0 or 1, you can simply constrain acc === n-1 at the end, instead of comparing it with IsEqual.
Constraint Count
Both circuits range-check each element with Num2Bits(b), and compare each consecutive pair with LessEqThan(b), for a total of non-linear constraints; IsSorted has two more for its final IsEqual. For 10 elements of 16 bits, AssertSorted has 313 constraints and IsSorted has 315.
Hashing
Hash functions are everywhere in zero-knowledge applications: commitments, Merkle trees, nullifiers, signatures, and so on. However, not all hash functions are equally good for circuits.
Traditional hash functions such as SHA-256 and Keccak are designed for CPUs: they work on bits and bytes, using operations like XOR, rotations and additions modulo . In a circuit, every one of these bit operations costs constraints, as we must first decompose values into bits. In contrast, field additions and multiplications by constants are free, and multiplications of two signals cost one constraint each.
So, there are hash functions designed specifically for circuits, called arithmetization-oriented or ZK-friendly hash functions. They work natively with field elements, using only a small number of multiplications. Here is how they compare, in terms of non-linear constraints:
| Hash function | Input | Constraints |
|---|---|---|
SHA-256 (Sha256(512) from Circomlib) | 512 bits (64 bytes) | 59281 |
MiMC (MiMCSponge(2, 220, 1)) | 2 field elements | 1320 |
MiMC (MultiMiMC7(2, 91)) | 2 field elements | 728 |
Poseidon (Poseidon(2)) | 2 field elements | 240 |
Note that two field elements hold about 508 bits, so Poseidon hashes about the same amount of data as SHA-256 above, with about 250 times fewer constraints! This is why Poseidon is the go-to hash function in Circom today.
Commitments
One of the most common uses of hash functions is a commitment scheme. In a commitment scheme, Alice can commit to a value to obtain a commitment . At some point later, Bob would like for Alice to reveal the committed value behind , and show that indeed Alice was the one that had committed in the first place.
A rough informal sketch of this interaction can be shown as:
sequenceDiagram actor A as Alice actor B as Bob note over A: [x] := Commit(x) A ->> B: [x] note over A, B: sometime later B ->> A: show me! A ->> B: x note over B: im convinced.
A cryptographic commitment scheme has two notable properties:
- Hiding: A commitment should reveal nothing about the underlying .
- Binding: A commitment , should only be revealed to , i.e. for some we shouldn’t be able to compute a commitment .
A hash function gives us a simple commitment scheme: where is a random number, also known as the blinding factor.
- It is binding, because opening the commitment to another would require finding a collision of .
- It is hiding, because does not reveal its inputs, and the random prevents anyone from simply trying all possible values of . Without , a commitment to a vote like would be trivial to “decrypt” by comparing it with and !
In a circuit, we can prove that we know the opening of a commitment without revealing it. The commitment is public, while and are private:
template Commitment() {
signal input x; // the committed value, private
signal input r; // a random blinding factor, private
signal input commitment; // public
signal hash <== PoseidonHash(2)([x, r]);
hash === commitment;
}
Of course, a circuit like this is more interesting when it also proves something about , e.g. that is within some range, without revealing itself.
A Merkle tree is another commitment scheme built from a hash function, which commits to a whole list of values at once.
Poseidon
Poseidon is a hash function designed by Grassi, Khovratovich, Rechberger, Roy and Schofnegger specifically for zero-knowledge proof systems. It works natively over the field of the circuit, and it is the most commonly used hash function in Circom.
Circomlib’s Poseidon is a heavily optimized implementation, which can be hard to read. The circuit below is a plain implementation of the same hash, written as described in the paper. It uses the same constants as Circomlib, and our tests confirm that it gives the same output as Circomlib’s Poseidon (via poseidon-lite) for 1, 2, 3, 5 and 16 inputs.
PoseidonHash
template SBox() {
signal input in;
signal output out;
signal in2 <== in * in;
signal in4 <== in2 * in2;
out <== in4 * in;
}
template PoseidonHash(n) {
assert(1 <= n && n <= 16);
signal input in[n];
signal output out;
// the state has one more element than the inputs, called the "capacity"
var t = n + 1;
// number of full rounds and partial rounds, from the Poseidon paper
var R_F = 8;
var N_ROUNDS_P[16] = [56, 57, 56, 60, 60, 63, 64, 63, 60, 66, 60, 65, 70, 60, 64, 68];
var R_P = N_ROUNDS_P[t - 2];
var C[t * (R_F + R_P)] = POSEIDON_C(t);
var M[t][t] = POSEIDON_M(t);
// the initial state is `[0, in[0], ..., in[n-1]]`
var state[t];
state[0] = 0;
for (var i = 0; i < n; i++) {
state[i + 1] = in[i];
}
for (var r = 0; r < R_F + R_P; r++) {
// 1. add round constants
for (var i = 0; i < t; i++) {
state[i] += C[r * t + i];
}
// 2. apply the S-box: to all elements in a full round, and only to the
// first element in a partial round; the full rounds are the first and
// last `R_F / 2` rounds, and the partial rounds are in between
var isFull = (r < R_F / 2) || (r >= R_F / 2 + R_P);
for (var i = 0; i < t; i++) {
if (i == 0 || isFull) {
state[i] = SBox()(state[i]);
}
}
// 3. mix the state by multiplying it with the MDS matrix
var mixed[t];
for (var i = 0; i < t; i++) {
mixed[i] = 0;
for (var j = 0; j < t; j++) {
mixed[i] += M[i][j] * state[j];
}
}
state = mixed;
}
out <== state[0];
}
The Permutation
At the heart of Poseidon is a permutation over a state of field elements. To hash inputs, we use a state of elements: the inputs, and one extra element called the capacity, which starts as 0. The state is then scrambled through many rounds, and the first element of the final state is the hash.
This is the sponge construction: inputs are “absorbed” into the state, the permutation is applied, and the output is “squeezed” from the state. Circomlib uses a single permutation, so it can hash at most 16 inputs at once.
Each round consists of three steps:
- Add round constants: a different constant is added to each element of the state, so that the rounds are not all the same.
- S-box: each element is raised to the power of 5, i.e. . This is the only non-linear step.
- Mix: the state is multiplied with a MDS matrix, so that every element affects every other element in the next round.
The constants and the matrices are generated once by a script from the authors, and Circomlib has them in poseidon_constants_old.circom, which we include here.
Why ?
The S-box must be a permutation of the field, otherwise two different states could map to the same one. The map is a permutation exactly when . For BN254, is divisible by 3, so does not work, and is the smallest exponent that does. It costs 3 constraints, as seen in SBox:
Full & Partial Rounds
Here is the clever part of Poseidon. The S-box is the only expensive step, so Poseidon uses two kinds of rounds:
- Full rounds apply the S-box to all elements. There are of them: 4 at the beginning and 4 at the end. They protect against statistical attacks, such as differential and linear cryptanalysis.
- Partial rounds apply the S-box to only the first element. There are of them in the middle, between 56 and 70 depending on . They are cheap, yet they still increase the algebraic degree of the permutation, which protects against algebraic attacks.
The number of partial rounds for each is in the N_ROUNDS_P table, as computed by the authors’ script. With this design, the number of S-boxes is instead of .
Constraint Count
The round constants and the MDS matrix are all known at compile time, so adding them and multiplying with them are linear operations, and they cost no non-linear constraints at all. Only the S-boxes cost constraints, 3 each:
For 2 inputs, that is and , so . In fact, the compiler finds 240 non-linear constraints with --O2, because in the very first round the capacity element is a constant ( plus a round constant), so its S-box is computed at compile time.
| Inputs | S-boxes | Constraints (--O2) | ||
|---|---|---|---|---|
| 1 | 2 | 56 | 72 | 213 |
| 2 | 3 | 57 | 81 | 240 |
| 16 | 17 | 68 | 204 | 609 |
Circomlib’s Optimized Version
Circomlib’s Poseidon computes the very same hash, and has the very same number of non-linear constraints. So what is optimized? Look again at the partial rounds: only one element goes through the S-box, while the other elements just go through the linear layers. The Poseidon paper describes how to take advantage of this:
- The round constants of the partial rounds can be moved through the linear layers, so that only the first element needs a constant in each partial round. The rest are merged into the constants of the other rounds.
- The MDS matrix in the partial rounds can be replaced by one dense matrix (
Pin Circomlib) followed by a sparse matrix for each partial round (Sin Circomlib), applied by theMixStemplate. A sparse matrix only multiplies the first element with each of the others, so it has about entries instead of .
In R1CS, these linear operations end up inside the non-linear constraints as linear combinations, so fewer terms make the R1CS smaller. For example, with --O2 and 2 inputs, Circomlib’s Poseidon has an R1CS file of about 114KB, while our plain implementation has about 247KB, with the same 240 constraints.
Circomlib also has
PoseidonEx(nInputs, nOuts), which lets you set the initial value of the capacity element and returns more than one element of the final state.Poseidon(nInputs)is simplyPoseidonEx(nInputs, 1)with an initial state of 0.
MiMC
MiMC by Albrecht, Grassi, Rechberger, Roy and Tiessen is one of the first hash functions designed for circuits, and it is remarkably simple. Its name stands for “Minimal Multiplicative Complexity”, as it aims to use as few multiplications as possible. It was used by early zero-knowledge applications such as Tornado Cash, and while Poseidon is preferred today, MiMC is a great way to see how such a hash function works.
Circomlib has two variants of MiMC, and we explain both of them here, using Circomlib’s own code. Our tests check these circuits against a short TypeScript implementation of the formulas below, which reads the round constants from Circomlib’s sources.
MiMC7
template MiMC7(nrounds) {
signal input x_in;
signal input k;
signal output out;
var c[91] = [
0,
20888961410941983456478427210666206549300505294776164667214940546594746570981,
// ... 89 more constants
];
var t;
signal t2[nrounds];
signal t4[nrounds];
signal t6[nrounds];
signal t7[nrounds-1];
for (var i=0; i<nrounds; i++) {
t = (i==0) ? k+x_in : k + t7[i-1] + c[i];
t2[i] <== t*t;
t4[i] <== t2[i]*t2[i];
t6[i] <== t4[i]*t2[i];
if (i<nrounds-1) {
t7[i] <== t6[i]*t;
} else {
out <== t6[i]*t + k;
}
}
}
MiMC7 is a block cipher: it encrypts a field element x_in with a key k. Each round adds the key and a round constant to the state, and raises the result to the power of 7:
After 91 rounds, the key is added one more time to get the output. The first round constant is 0, which is why the first round is just k + x_in.
Why and 91 Rounds?
Just like the S-box of Poseidon, must be a permutation of the field so that encryption can be reversed, and that requires . For BN254, this holds for 7 (and 5), but not for 3.
The number of rounds comes from a simple argument: after rounds, the output is a polynomial of degree in the input. If the degree is small, an attacker could recover the polynomial by interpolation. So we want , which gives:
Cost
Computing takes 4 multiplications: , , and . That is 4 constraints per round, so MiMC7(91) has constraints.
MultiMiMC7
template MultiMiMC7(nInputs, nRounds) {
signal input in[nInputs];
signal input k;
signal output out;
signal r[nInputs +1];
component mims[nInputs];
r[0] <== k;
for (var i=0; i<nInputs; i++) {
mims[i] = MiMC7(nRounds);
mims[i].x_in <== in[i];
mims[i].k <== r[i];
r[i+1] <== r[i] + in[i] + mims[i].out;
}
out <== r[nInputs];
}
A block cipher is not a hash function yet. MultiMiMC7 turns it into one using the Miyaguchi–Preneel construction: each input is encrypted with the current state as the key, and the result is added to both the state and the input:
The final is the hash. This costs one MiMC7 per input, i.e. 364 constraints per input.
MiMCSponge
template MiMCFeistel(nrounds) {
signal input xL_in;
signal input xR_in;
signal input k;
signal output xL_out;
signal output xR_out;
// doesn't contain the first and last round constants, which are always zero
var c_partial[218] = [
// 218 constants
];
var t;
signal t2[nrounds];
signal t4[nrounds];
signal xL[nrounds-1];
signal xR[nrounds-1];
var c;
for (var i=0; i<nrounds; i++) {
if ((i == 0) || (i == nrounds - 1)) {
c = 0;
} else {
c = c_partial[i - 1];
}
t = (i==0) ? k+xL_in : k + xL[i-1] + c;
t2[i] <== t*t;
t4[i] <== t2[i]*t2[i];
if (i<nrounds-1) {
var aux = (i==0) ? xR_in : xR[i-1] ;
xL[i] <== aux + t4[i]*t;
xR[i] <== (i==0) ? xL_in : xL[i-1];
} else {
xR_out <== xR[i-1] + t4[i]*t;
xL_out <== xL[i-1];
}
}
}
The other variant uses a Feistel network with a state of two elements, and . In each round, the left element goes through , the result is added to the right element, and the two are swapped:
In the last round, the elements are not swapped. Since each round only changes one of the two elements, a Feistel network needs twice as many rounds: . The first and last round constants are 0, which is why Circomlib only stores the other 218.
Each round costs 3 constraints, for , and , so MiMCFeistel(220) has 660 constraints.
template MiMCSponge(nInputs, nRounds, nOutputs) {
signal input ins[nInputs];
signal input k;
signal output outs[nOutputs];
var i;
// S = R||C
component S[nInputs + nOutputs - 1];
for (i = 0; i < nInputs; i++) {
S[i] = MiMCFeistel(nRounds);
S[i].k <== k;
if (i == 0) {
S[i].xL_in <== ins[0];
S[i].xR_in <== 0;
} else {
S[i].xL_in <== S[i-1].xL_out + ins[i];
S[i].xR_in <== S[i-1].xR_out;
}
}
outs[0] <== S[nInputs - 1].xL_out;
for (i = 0; i < nOutputs - 1; i++) {
S[nInputs + i] = MiMCFeistel(nRounds);
S[nInputs + i].k <== k;
S[nInputs + i].xL_in <== S[nInputs + i - 1].xL_out;
S[nInputs + i].xR_in <== S[nInputs + i - 1].xR_out;
outs[i + 1] <== S[nInputs + i].xL_out;
}
}
With a state of two elements, we can build a sponge: is the rate where the inputs are absorbed and the outputs are squeezed, and is the capacity that is never touched directly.
- Absorb: for each input, add it to and apply the permutation.
- Squeeze: the first output is . For each additional output, apply the permutation again and output .
So MiMCSponge(2, 220, 1), which hashes two elements into one (e.g. two children of a Merkle tree node, as in Tornado Cash) has constraints.
MiMC vs. Poseidon
| Hash | Inputs | Constraints |
|---|---|---|
MultiMiMC7(2, 91) | 2 | 728 |
MiMCSponge(2, 220, 1) | 2 | 1320 |
Poseidon(2) | 2 | 240 |
MiMC applies its S-box to a single element in every round, so it needs many rounds and its cost grows with each input. Poseidon processes all inputs at once in a single permutation, and with its partial rounds it needs only 81 S-boxes for 2 inputs. That is why Poseidon has replaced MiMC in most new applications.
Merkle Trees
If you have been in the world of crypto for a while, it is highly likely that you have heard the term Merkle Tree, also known as Merkle Hash Tree.
Definition
A Merkle Tree is a hash-based data structure, and can serve as a cryptographic commitment scheme.
You can commit to a set of values using a Merkle Tree, such as:
- Evaluations of a function
- Coefficients of a polynomial
- Files in your database
Here is an example, where we commit to a vector using a Merkle Tree:
graph BT subgraph Merkle Tree h1["h1 (Merkle Root)"] h2 --> h1; h3 --> h1 h4 --> h2; h5 --> h2 h6 --> h3; h7 --> h3 h8 --> h4; h9 --> h4 h10 --> h5; h11 --> h5 h12 --> h6; h13 --> h6 h14 --> h7; h15 --> h7 end m -- hash --> h8 y -- hash --> h9 v -- hash --> h10 e -- hash --> h11 c -- hash --> h12 t -- hash --> h13 o -- hash --> h14 r -- hash --> h15
In a Merkle Tree, every node is made up of the hash of its children. In this example binary tree, that would be:
- and so on.
The leaf nodes are the hashes of elements of the committed set of data. The final hash at the root of the tree is called the Merkle Root.
Merkle Trees are often implemented as binary trees, but the concept works for -ary trees as well, where each node has children.
Merkle Proof
At some point, we may be asked to show that indeed some element of the comitted data exists at some position. For our example above, a verifier could ask “is there really a at position 6?”.
A naive method here would be give the entire comitted set of data, and let them prove the Merkle Root; however, we can do much better than that! With Merkle Trees, we can answer such queries in a much more efficient way, and without revealing any other data than the one we are asked to reveal.
The trick is to provide the hashes needed to compute all the way from the requested element up to the Merkle Root. In total, we only need to provide one hash per level (in the case of a binary-tree Merkle Tree) and the verifier can compute the root!
For instance, to show that we have at position 6, we need to provide the hashes that are used to compute the parent nodes.
- is computed by verifier.
- requires to be provided.
- requires to be provided.
- requires to be provided.
- is our commitment, which the verifier knows already.
The proof is visualized below for the same tree, where the values known & computed by the verifier are colored green and the values provided by the prover are colored blue:
graph BT classDef g fill:#afa classDef b fill:#aaf subgraph Merkle Tree h1["h1 (Merkle Root)"]:::g h2:::b --> h1 h3:::g --> h1 h4[fa:fa-eye-slash] --> h2 h5[fa:fa-eye-slash] --> h2 h6:::g --> h3 h7:::b --> h3 h8[fa:fa-eye-slash] --> h4 h9[fa:fa-eye-slash] --> h4 h10[fa:fa-eye-slash] --> h5 h11[fa:fa-eye-slash] --> h5 h12:::b --> h6 h13:::g --> h6 h14[fa:fa-eye-slash] --> h7 h15[fa:fa-eye-slash] --> h7 end t:::g -- hash --> h13
You see, we only needed to provide 3 hashes here, although our data had 8 elements! In fact, if you have elements you only need to provide elements to the verifier, this is so much more efficient than the naive method of sending all the data to the verifier.
A Merkle Root can serve as a cryptographic commitment to a set of data.
- It is hiding because you can’t find the preimage of an hash efficiently. However, just like a hash commitment, if the values are easy to guess you should hash each of them with a random blinding factor.
- It is binding because assuming otherwise would require you to find a hash-collision efficiently, which is known to be intractable.
To reveal that some value is part of the comitted set of data at a specific point, you only need to reveal the path from that node to the root, along with the value itself, as described above.
Types of Merkle Trees
There are several types of Merkle Trees, each with its own use cases:
- Binary Merkle Tree
- Incremental Merkle Tree
- Sparse Merkle Tree
- Complete Binary Merkle Tree
- Merkle Mountain Range
Further Reading
- The original paper is “A Digital Signature Based on a Conventional Encryption Function” by Ralph Merkle.
- “Providing Authentication and Integrity in Outsourced Databases using Merkle Hash Tree’s” by Mykletun, Narasimha, Tsudik is another paper that is slightly easier to read.
- RareSkills Merkle Tree second-preimage attack blog post.
Binary Merkle Tree
A Binary Merkle Tree is the most common kind of Merkle Tree: every node has two children, and the tree is dense, i.e. it has exactly leaves for a tree of depth , all of them filled. The tree of the vector [m, y, v, e, c, t, o, r] in the introduction is a Binary Merkle Tree of depth 3.
We have two circuits for it: one computes the root of the whole tree, and the other verifies a Merkle proof for a single leaf. Both use Circomlib’s Poseidon as the hash function.
BinaryMerkleTree
template BinaryMerkleTree(n) {
assert(n > 0);
var NUM_LEAVES = 1 << n;
var NUM_NODES = (1 << (n+1)) - 1;
signal input leafs[NUM_LEAVES];
signal output root;
signal nodes[NUM_NODES];
// compute hashes of leaves
for (var i = 0; i < NUM_LEAVES; i++) {
nodes[(NUM_NODES - 1) - i] <== Poseidon(1)([leafs[(NUM_LEAVES - 1) - i]]);
}
// build the tree from the leaves to the root in reverse
for (var i = NUM_NODES - NUM_LEAVES - 1; i >= 0; i--) {
nodes[i] <== Poseidon(2)([nodes[2*i + 1], nodes[2*i + 2]]);
}
root <== nodes[0];
}
This circuit takes all leaves, and computes the Merkle root. The nodes are stored in a single array nodes of size , in the same layout as a binary heap:
- the root is
nodes[0], - the children of
nodes[i]arenodes[2i + 1]andnodes[2i + 2], - the leaves are the last elements.
So we first hash each leaf into the last positions, and then fill in the rest of the array backwards, from the last internal node all the way to the root:
graph BT n0["nodes[0] (root)"] n1["nodes[1]"] --> n0 n2["nodes[2]"] --> n0 n3["nodes[3] = H(leafs[0])"] --> n1 n4["nodes[4] = H(leafs[1])"] --> n1 n5["nodes[5] = H(leafs[2])"] --> n2 n6["nodes[6] = H(leafs[3])"] --> n2
Hashing Leaves & Nodes Differently
Notice that leaves are hashed with Poseidon(1) while internal nodes are hashed with Poseidon(2). This is not just because a leaf is a single value: it also makes sure that a leaf can never be confused with an internal node.
Suppose we hashed the leaves and the nodes the same way, e.g. by not hashing the leaves at all. Then an internal node could be presented as a “leaf” with value , and its “proof” would just be the rest of the path above it. Someone could then prove that is in the tree, although was never one of the committed values. This is known as the second-preimage attack on Merkle trees.
Poseidon(1) and Poseidon(2) use a different state size, and therefore different constants, so they behave like two unrelated hash functions. To pass off an internal node as a leaf hash, one would have to find an such that Poseidon(1)(x) = h, which is infeasible.
BinaryMerkleProof
template BinaryMerkleProof(n) {
assert(n > 0);
signal input in;
signal input siblings[n];
signal input indices[n];
signal output root;
// the path from the leaf to the root
signal path[n+1];
// the last element in the path is the leaf hash
path[n] <== Poseidon(1)([in]);
// compute the "audit path" w.r.t indices
signal children[n][2];
for (var i = n; i != 0; i--) {
// index 0: sibling is on the right
// index 1: sibling is on the left
//
// the index MUST be a bit, otherwise `Switch` returns a mix of the
// path and the sibling, which can be crafted to forge a proof
AssertBit()(indices[i-1]);
children[i-1] <== Switch()(indices[i-1], [path[i], siblings[i-1]]);
path[i-1] <== Poseidon(2)(children[i-1]);
}
// the last element in the path is the root hash
root <== path[0];
}
Most of the time we do not want to give the whole tree to the circuit, but only prove that some value is in it. As described in the introduction, a Merkle proof consists of one sibling per level, and we compute the root by hashing our way up from the leaf.
At each level, we must know whether our node is the left or the right child, so that we hash the two children in the right order. This is given by indices: 0 if the sibling is on the right, and 1 if the sibling is on the left. The Switch template then puts the two children in the correct order:
indices[i] = 0gives[path, sibling],indices[i] = 1gives[sibling, path].
The circuit outputs the computed root, and it is up to the caller to compare it against a known (e.g. public) root.
The Indices Must Be Bits
Switch does not check that its condition is a bit, and if it is not, the result is a mix of the two inputs:
A dishonest prover can choose the sibling and so that these are any two values that add up to path + sibling. In particular, at the top level, it can make them equal to the actual two children of the root, which gives the correct root for a leaf that is not in the tree! That is why we assert that each index is a bit with AssertBit, and our tests include such a forged proof to make sure that it is rejected.
Indices from the Leaf Index
The indices are simply the bits of the leaf’s position, from the most significant bit to the least significant one. For example, in a tree of depth 2, the leaf at position is the left child of the right child of the root:
- at the top level, our node is on the right, so the sibling is on the left:
indices[0] = 1 - at the bottom level, our node is on the left, so the sibling is on the right:
indices[1] = 0
So instead of indices, one could take the position of the leaf as an input and decompose it with Num2Bits, which would also constrain the indices to be bits.
Constraint Count
Each hash costs a few hundred constraints, so the hashes dominate the cost. With Poseidon(1) having 213 and Poseidon(2) having 240 constraints:
BinaryMerkleTree(n)hashes leaves and internal nodes, e.g. 1572 constraints for 4 leaves.BinaryMerkleProof(n)hashes one leaf and nodes, plus oneSwitchand oneAssertBitper level: constraints. A tree of depth 20 has more than a million leaves, yet a proof for it takes only 5053 constraints.
See Also
Incremental Merkle Tree
An Incremental Merkle Tree is a Binary Merkle Tree of a fixed depth that starts out empty, and is filled with leaves one by one, from left to right. It is the data structure behind applications like Tornado Cash, where each deposit adds a commitment to the tree, and Semaphore, where each member of a group is a leaf. A user can then prove that their leaf is in the tree, without revealing which one it is.
Here we use zk-kit, a library by PSE that Semaphore is built on: its BinaryMerkleRoot circuit for membership proofs, and its IMT TypeScript implementation to build the trees in our tests.
Empty Subtrees
An empty leaf has some fixed value, which we call ZERO. Semaphore uses 0, while Tornado Cash uses keccak256("tornado") modulo , which is unlikely to ever be an actual leaf.
Since every empty leaf has the same value, every empty subtree of the same height has the same root as well. These are called the zeroes of the tree:
So the root of a completely empty tree of depth is simply , and we never have to store the empty part of the tree.
Inserting a Leaf
Leaves are always inserted at the next free position. This makes insertion very cheap: to insert a leaf at position , we walk up from the leaf to the root, and at each level:
- if our node is a left child, its sibling on the right is still empty, so the sibling is the zero of that level,
- if our node is a right child, its sibling on the left is a subtree that is already full, and will never change again.
So we only need to remember the last full left subtree of each level, which Tornado Cash calls filledSubtrees. An insertion then takes only hashes and storage, no matter how many leaves the tree has. That is why such trees are popular in smart contracts.
Membership Proofs
template BinaryMerkleRoot(MAX_DEPTH) {
signal input leaf, depth, index, siblings[MAX_DEPTH];
signal output out;
signal nodes[MAX_DEPTH + 1];
nodes[0] <== leaf;
signal roots[MAX_DEPTH];
var root = 0;
signal indices[MAX_DEPTH] <== Num2Bits(MAX_DEPTH)(index);
for (var i = 0; i < MAX_DEPTH; i++) {
var isDepth = IsEqual()([depth, i]);
roots[i] <== isDepth * nodes[i];
root += roots[i];
var c[2][2] = [ [nodes[i], siblings[i]], [siblings[i], nodes[i]] ];
var childNodes[2] = MultiMux1(2)(c, indices[i]);
nodes[i + 1] <== Poseidon(2)(childNodes);
}
var isDepth = IsEqual()([depth, MAX_DEPTH]);
out <== root + isDepth * nodes[MAX_DEPTH];
}
A membership proof works just like in a Binary Merkle Tree, but zk-kit’s circuit differs from ours in a few ways:
- The position of the leaf is given as a number
index, and decomposed into bits withNum2Bits. This also guarantees that the indices are bits, which is important. - The siblings are given from the bottom to the top, i.e.
siblings[0]is the sibling of the leaf. - Instead of
Switch, it uses Circomlib’sMultiMux1to order the two children. - The depth of the tree is an input, and it can be anything up to
MAX_DEPTH. At each level, the node is selected as the root if that level is the depth. This is useful for the LeanIMT of Semaphore v4, whose depth grows as leaves are added. - The leaves are not hashed before going into the tree. In these applications, the leaves are already hashes, e.g. commitments.
Since the leaves are not hashed and the depth is an input, the verifier must make sure that the depth is the actual depth of the tree. Otherwise, a prover could pick a smaller depth and present an internal node as a “leaf”, which is the second-preimage attack we have seen before. Semaphore, for example, checks the depth in its smart contract.
Insertion Proofs
template IncrementalMerkleTreeInsert(DEPTH, ZERO) {
signal input oldRoot;
signal input leaf;
signal input index;
signal input siblings[DEPTH];
signal output newRoot;
// the position must be empty in the old tree
signal emptyRoot <== BinaryMerkleRoot(DEPTH)(ZERO, DEPTH, index, siblings);
emptyRoot === oldRoot;
// the same path with the new leaf gives the new root
newRoot <== BinaryMerkleRoot(DEPTH)(leaf, DEPTH, index, siblings);
}
Insertion is usually done outside of a circuit, e.g. by a smart contract. However, sometimes we want to prove that an insertion was done correctly, e.g. when many insertions are batched together off-chain, and only a single proof is verified on-chain.
The trick is to notice that inserting a leaf does not change its siblings: the siblings are all in other parts of the tree. So the same path proves two things:
- With the
ZEROleaf, the path givesoldRoot. This proves that the position was empty before the insertion. - With the new
leaf, the same path givesnewRoot, which is the root after the insertion.
The circuit uses two BinaryMerkleRoots for this, with DEPTH as the depth. It does not check that index is the next free position, which is up to the caller, e.g. by making index a public input that is compared with the number of leaves. Also note that inserting ZERO itself would leave the tree unchanged, so ZERO should never be a real leaf.
Our tests use zk-kit’s IMT to fill a tree of depth 4 from empty to full, proving every insertion along the way, and check that inserting into a position that is already filled, using a wrong old root, or using an index outside of the tree all fail.
Constraint Count
Almost all of the cost comes from the Poseidon hashes, one per level. For a tree of depth 20, i.e. about a million leaves:
| Circuit | Constraints |
|---|---|
BinaryMerkleRoot(20) | 4923 |
IncrementalMerkleTreeInsert(20, 0) | 9720 |
The insertion proof costs about twice as much as a membership proof, since it computes two roots.
See Also
- PSE zk-kit: Incremental Merkle Tree
- PSE zk-kit: Lean Incremental Merkle Tree
- HerodotusDev’s Accumulators IMT
- RareSkills Tornado Cash Line-by-Line
Sparse Merkle Tree
A Sparse Merkle Tree is a Merkle tree that commits to a key-value map. Instead of placing the leaves one after the other, the position of each leaf is given by its key: the bits of the key tell us which way to go at each level, starting from the root. With 254-bit keys, the tree has possible positions, and almost all of them are empty, hence the name “sparse”.
Since the position of a key is fixed, a Sparse Merkle Tree supports two kinds of proofs:
- Inclusion proof: a key is in the tree with some value, just like a membership proof.
- Exclusion proof: a key is not in the tree, by showing that its position is empty or occupied by another key. This is not possible with the other Merkle trees, where a leaf could be anywhere.
This makes them great for things like revocation lists, nullifier sets, or the state of a rollup. Circomlib has circuits for Sparse Merkle Trees, designed by Iden3 (see the paper), and circomlibjs has a matching TypeScript implementation which we use in our tests.
Compressing the Tree
A tree of depth 254 would require 254 hashes for every proof, which is way too many. So Circomlib compresses the tree: a subtree that contains only one leaf is replaced by that leaf. In other words, a leaf is placed at the highest level where it is alone, instead of at the very bottom.
As an example, consider a tree with the keys 1 and 3. The bits of the keys are read starting from the least significant one, and 0 means left while 1 means right:
- Both keys have the lowest bit set ( and ), so both go to the right of the root, and the left of the root is empty.
- Their second bit differs, so at the next level 1 goes to the left and 3 goes to the right, and now each of them is alone.
graph BT root["root"] e["0 (empty)"] --> root n["H(L1, L3)"] --> root l1["L1 = leaf of key 1"] --> n l3["L3 = leaf of key 3"] --> n
So the root is , using just two levels. With random keys, the leaves are at a depth of about on average. A tree with a single key is just that leaf, and an empty tree has the root 0.
Leaves
A leaf contains both the key and the value: , using Poseidon(3). Including the key is important, since a leaf can now be at any level, and its position alone does not tell us its full key. The extra 1 separates leaves from internal nodes, which are hashed with Poseidon(2).
SMTVerifier
The circuit for both kinds of proofs is SMTVerifier(nLevels), where nLevels is the maximum depth of a leaf. It has the following inputs:
root: the root of the tree.siblings: the siblings from the root down to the leaf, padded with zeros up tonLevels.key&value: the key, and its value for an inclusion proof.fnc: 0 for an inclusion proof, 1 for an exclusion proof.oldKey,oldValue&isOld0: for an exclusion proof, either the position ofkeyis empty (isOld0 = 1), or it holds the leaf of another keyoldKeywith valueoldValue.enabled: if 0, the circuit does not check anything. This is useful when the proof is optional, e.g. within a batch.
Using our example tree:
| Proof | siblings | Notes |
|---|---|---|
| key 1 is in the tree | fnc = 0 | |
| key 2 is not in the tree | goes to the left of the root, which is empty: isOld0 = 1 | |
| key 5 is not in the tree | goes right, then left, where it finds key 1: oldKey = 1 |
Levels & States
How does the circuit know where the leaf is? Since the siblings are padded with zeros, the leaf is right below the last non-zero sibling. The SMTLevIns template finds this level, and requires the very last sibling to be zero, so that the tree is never deeper than nLevels.
Then, each level is in one of the following states, given by a small state machine (SMTVerifierSM):
top: above the leaf, where we hash the child with the sibling,inew: the level of the leaf, for an inclusion proof, i.e. the leaf ,iold: the level of the leaf, for an exclusion proof with another key, i.e. the leaf ,i0: the level of the leaf, for an exclusion proof with an empty position, i.e. 0,na: below the leaf, where there is nothing to compute.
Each level then computes its node based on its state:
template SMTVerifierLevel() {
signal input st_top;
signal input st_i0;
signal input st_iold;
signal input st_inew;
signal input st_na;
signal output root;
signal input sibling;
signal input old1leaf;
signal input new1leaf;
signal input lrbit;
signal input child;
signal aux[2];
component proofHash = SMTHash2();
component switcher = Switcher();
switcher.L <== child;
switcher.R <== sibling;
switcher.sel <== lrbit;
proofHash.L <== switcher.outL;
proofHash.R <== switcher.outR;
aux[0] <== proofHash.out * st_top;
aux[1] <== old1leaf*st_iold;
root <== aux[0] + aux[1] + new1leaf*st_inew;
}
Since exactly one of the state signals is 1, the result is either the hash of the child and the sibling (ordered by the key bit lrbit, using a Switcher), the old leaf, the new leaf, or 0 (for i0 and na). The node of the top level is then compared with root.
Checking the Keys
There are two more important checks in SMTVerifier:
- The keys are decomposed into bits with
Num2Bits_strict, which also performs an alias check. Otherwise, a key and the key plus would have different bits, and thus different positions in the tree. - For an exclusion proof with another key,
oldKeymust be different fromkey. Otherwise, one could “prove” that a key is not in the tree by using its own leaf as the “other” leaf, which our tests check as well.
SMTProcessor
Circomlib also has SMTProcessor(nLevels), which proves that a change to the tree turns oldRoot into newRoot, similar to the insertion proof of an Incremental Merkle Tree. The operation is given by two bits fnc:
fnc | Operation |
|---|---|
[0, 0] | nothing |
[1, 0] | insert |
[0, 1] | update |
[1, 1] | delete |
It works with the same siblings for the old and the new tree. An insertion is a bit tricky though: if the position of the new key holds another leaf, that leaf must be pushed down until the two keys go different ways, which adds new levels to the tree. Our tests use circomlibjs to insert, update and delete keys, and check that SMTProcessor computes the same new roots.
Constraint Count
| Circuit | Constraints |
|---|---|
SMTVerifier(10) | 4063 |
SMTVerifier(20) | 6573 |
SMTProcessor(20) | 11535 |
Each level costs about 251 constraints, most of which is the Poseidon(2) hash. On top of that, there is a fixed cost of about 1550 constraints for the two leaf hashes and the two 254-bit key decompositions with alias checks.
See Also
- Tochicool’s SMT
- Efficient Sparse Merkle Trees by Rasmus Dahlberg, Tobias Pulls, and Roel Peeters.
- Iden3 (authors of Circom) has a nice publication on Merkle Trees: Sparse Merkle Trees by Jordi Baylina and Marta Belles.
Complete Binary Merkle Tree
A Binary Merkle Tree must have exactly leaves. If we have, say, 5 values to commit to, we must pad them with 3 more to reach 8, which wastes space and hashes. A Complete Binary Merkle Tree solves this: it works with any number of leaves , using exactly nodes. It is used by Nervos CKB, for example.
The idea is to fill the tree level by level, just like a binary heap. The nodes are stored in an array where the root is at position 0, the children of the node at position are at and , and the leaves are the last nodes. Here is the tree with 5 leaves:
graph BT n0["0 (root)"] n1["1"] --> n0 n2["2"] --> n0 n3["3"] --> n1 n4["4 = H(leaf 0)"] --> n1 n5["5 = H(leaf 1)"] --> n2 n6["6 = H(leaf 2)"] --> n2 n7["7 = H(leaf 3)"] --> n3 n8["8 = H(leaf 4)"] --> n3
Notice that the leaves are on the last two levels: leaves 0, 1 and 2 are at depth 2, while leaves 3 and 4 are at depth 3. This is the same layout as our BinaryMerkleTree, which is simply the special case , where all leaves are at the same depth.
CompleteBinaryMerkleTree
template CompleteBinaryMerkleTree(N) {
assert(N > 0);
signal input leafs[N];
signal output root;
// nodes are stored as in a binary heap: the root is at 0,
// the children of node `i` are `2i + 1` and `2i + 2`, and the leaves are the last `N` nodes
signal nodes[2 * N - 1];
for (var i = 0; i < N; i++) {
nodes[N - 1 + i] <== Poseidon(1)([leafs[i]]);
}
for (var i = N - 2; i >= 0; i--) {
nodes[i] <== Poseidon(2)([nodes[2 * i + 1], nodes[2 * i + 2]]);
}
root <== nodes[0];
}
Computing the root is exactly as in BinaryMerkleTree, only with leaves: hash the leaves into the last positions, then fill in the internal nodes backwards from position down to the root. Our tests check that CompleteBinaryMerkleTree(4) gives the same root as BinaryMerkleTree(2).
CompleteBinaryMerkleProof
function cbmtDepth(N) {
var depth = 0;
while ((1 << (depth + 1)) <= 2 * N - 1) {
depth++;
}
return depth;
}
template CompleteBinaryMerkleProof(N) {
assert(N > 1);
var D = cbmtDepth(N);
signal input leaf;
signal input index;
signal input siblings[D];
signal output root;
// the index must be within the leaves; `N <= 2^D`, so both fit in `D + 1` bits
_ <== Num2Bits(D + 1)(index);
signal isValid <== LessThan(D + 1)([index, N]);
isValid === 1;
// position of the leaf in the tree, counting from 1 at the root, level by level;
// the leaf is at the deepest level `D` if its position is at least `2^D`, otherwise at `D - 1`
var position = N + index;
signal isShallow <== LessThan(D + 1)([position, 1 << D]);
var depth = D - isShallow;
// the index of the leaf within its level, whose bits give the path from the leaf to the root
var levelIndex = position - (1 << D) + isShallow * (1 << (D - 1));
signal leafHash <== Poseidon(1)([leaf]);
root <== BinaryMerkleRoot(D)(leafHash, depth, levelIndex, siblings);
}
A proof for a leaf is again its siblings from the leaf up to the root, but now the leaves can be at two different depths, so the number of siblings depends on the leaf. We use zk-kit’s BinaryMerkleRoot for this, which supports a variable depth up to a maximum: the maximum is the deepest level , and the siblings of a shallower leaf are padded with a 0.
The interesting part is to find the depth and the path of a leaf from its index, and it turns out that this is mostly linear. Number the nodes from 1 instead of 0, i.e. the root is 1, and the children of are and . In this numbering:
- The leaf with index is at position .
- A node at depth has a position in range . So the leaf is at the deepest level if , and at level otherwise. A single
LessThanfinds out which one. - The bits of describe the path from the root: after the leading 1, each bit is 0 for a left child and 1 for a right child. So , the index of the node within its level, has exactly the bits of the path, which is what
BinaryMerkleRoottakes as itsindex.
For example, with , leaf 4 is at position , which is , so it is at depth 3. Its index within the level is : from the root it goes left, left, then right, which is node 8 in the 0-based numbering of the figure above.
Since the depth is computed from the index instead of being given by the prover, the prover can not present an internal node as a leaf by choosing a smaller depth. We also make sure that the index is less than , otherwise an index like would point to some other node of the tree.
Constraint Count
| Circuit | Constraints |
|---|---|
CompleteBinaryMerkleTree(5) | 2025 |
CompleteBinaryMerkleProof(5) | 967 |
CompleteBinaryMerkleProof(1000000) | 5200 |
A proof for a million leaves has a depth of 20, and it costs about the same as a proof in a Binary Merkle Tree of depth 20, but without having to pad the leaves to .
See Also
- Nervos Network’s CBMT implementation: https://github.com/nervosnetwork/merkle-tree
Merkle Mountain Range
A Merkle Mountain Range (MMR) is an append-only commitment to a list of values that can grow forever. Unlike an Incremental Merkle Tree, it has no fixed depth and no empty leaves. Instead, it is a list of perfect binary Merkle trees, called mountains, of decreasing heights. MMRs are used for append-only logs, such as committing to all block headers of a blockchain, e.g. by HerodotusDev for storage proofs.
Here we use HerodotusDev’s accumulators library in our tests, with its Poseidon hasher which is the same as Circomlib’s, and our circuit computes the very same root.
Mountains
When a value is appended, it becomes a new mountain of height 0. Then, as long as the last two mountains have the same height, they are merged into one mountain that is one level higher, by hashing their peaks together. This is just like incrementing a binary counter, where a carry merges two mountains!
In fact, the mountains of an MMR with leaves correspond exactly to the bits of : there is a mountain of height if and only if the bit of is set. For example, with leaves there are three mountains, with 8, 2 and 1 leaves:
graph BT subgraph "height 3: leaves 0-7" p0["peak 0"] a1[" "] --> p0 a2[" "] --> p0 b1[" "] --> a1 b2[" "] --> a1 b3[" "] --> a2 b4[" "] --> a2 l0["0"] --> b1 l1["1"] --> b1 l2["2"] --> b2 l3["3"] --> b2 l4["4"] --> b3 l5["5"] --> b3 l6["6"] --> b4 l7["7"] --> b4 end subgraph "height 1: leaves 8-9" p1["peak 1"] l8["8"] --> p1 l9["9"] --> p1 end subgraph "height 0: leaf 10" p2["peak 2 = 10"] end
The total number of nodes, which HerodotusDev calls the elements count, is , where is the number of set bits in , i.e. the number of peaks. For our example that is .
The Root
The peaks are combined into a single hash by bagging them from right to left:
and the root of the MMR also commits to the elements count:
With a single peak, the bag is just that peak. Note that a leaf is used as is, without hashing, just as in HerodotusDev’s implementation.
MerkleMountainRangeProof
template MerkleMountainRangeProof(B) {
assert(B > 1);
signal input leaf;
signal input index;
signal input leafCount;
signal input siblings[B - 1];
signal input peaks[B];
signal output root;
// each set bit of `leafCount` is a mountain, with a height equal to the position of that bit
signal n[B] <== Num2Bits(B)(leafCount);
signal i[B] <== Num2Bits(B)(index);
// the mountain of the leaf is at the highest bit where `leafCount` and `index` differ, and
// `leafCount` must have a 1 there while `index` has a 0, which also means `index < leafCount`
signal both[B];
signal noneAbove[B + 1];
signal isMountain[B];
noneAbove[B] <== 1;
for (var h = B - 1; h >= 0; h--) {
both[h] <== n[h] * i[h];
isMountain[h] <== (n[h] - both[h]) * noneAbove[h + 1];
noneAbove[h] <== noneAbove[h + 1] * (1 - (n[h] + i[h] - 2 * both[h]));
}
var mountains = 0;
for (var h = 0; h < B; h++) {
mountains += isMountain[h];
}
mountains === 1;
// height of the mountain, index of the leaf within the mountain (the lower bits of `index`),
// and index of the peak of the mountain (the number of higher mountains)
signal offsets[B];
signal peakIndices[B];
var height = 0;
var offset = 0;
var peakIndex = 0;
for (var h = 0; h < B; h++) {
var lower = 0;
for (var k = 0; k < h; k++) {
lower += i[k] * (1 << k);
}
var higher = 0;
for (var k = h + 1; k < B; k++) {
higher += n[k];
}
height += h * isMountain[h];
offsets[h] <== isMountain[h] * lower;
offset += offsets[h];
peakIndices[h] <== isMountain[h] * higher;
peakIndex += peakIndices[h];
}
// the root of the mountain must be its peak
signal peak <== BinaryMerkleRoot(B - 1)(leaf, height, offset, siblings);
signal selectedPeaks[B];
var selected = 0;
for (var j = 0; j < B; j++) {
var isPeak = IsEqual()([peakIndex, j]);
selectedPeaks[j] <== isPeak * peaks[j];
selected += selectedPeaks[j];
}
selected === peak;
// bag the peaks from right to left: `bag = H(peaks[0], H(peaks[1], ... H(peaks[k-2], peaks[k-1])))`
var numPeaks = 0;
for (var h = 0; h < B; h++) {
numPeaks += n[h];
}
signal isLast[B];
signal lastParts[B];
signal hashes[B - 1];
signal bags[B];
var isInner = 0; // 1 if there is a peak to the right of `j`
for (var j = B - 1; j >= 0; j--) {
isLast[j] <== IsEqual()([numPeaks, j + 1]);
lastParts[j] <== isLast[j] * peaks[j];
if (j == B - 1) {
bags[j] <== lastParts[j];
} else {
hashes[j] <== Poseidon(2)([peaks[j], bags[j + 1]]);
bags[j] <== lastParts[j] + isInner * hashes[j];
}
isInner += isLast[j];
}
// the root commits to the number of elements (all nodes) as well
var elementsCount = 2 * leafCount - numPeaks;
root <== Poseidon(2)([elementsCount, bags[0]]);
}
To prove that a leaf is in the MMR, we prove that it is in its mountain (a regular Merkle proof up to the peak), and that the root of the MMR is computed from all the peaks. The parameter B is the number of bits of the leaf count, so the circuit works for any MMR with less than leaves.
Finding the Mountain
Which mountain is the leaf with index in? The mountains split the leaves into consecutive ranges according to the bits of , from the highest bit to the lowest. So the leaf is in the mountain of height , where is the highest bit where and differ. Since , at that bit has a 1 and has a 0.
In our example with , the leaf first differs from at bit 1, so it is in the mountain of height 1. Then:
- its index within the mountain is given by the lower bits of , i.e. : it is the right leaf of that mountain,
- its peak is the second one, as there is one set bit of above bit 1, i.e. one higher mountain.
In the circuit, noneAbove[h] tracks whether and are equal on all bits above , and isMountain[h] is 1 only at the highest differing bit, if has a 1 there. We require exactly one isMountain to be 1, which also proves that : if , the highest differing bit (if any) would have a 1 in instead.
With isMountain as a selector, the height, the index within the mountain, and the index of the peak are all computed with one multiplication per bit. Then zk-kit’s BinaryMerkleRoot computes the peak from the leaf, with the height of the mountain as its depth, and we compare it with the selected peak from peaks.
Bagging the Peaks
The number of peaks is the number of set bits of , so it is not known at compile time. We compute the bag for every possible number of peaks, from right to left: bags[j] is the peak itself if it is the last one, the hash of the peak with bags[j + 1] if there are more peaks to its right, and 0 if it is not a peak at all. The isLast signals mark the last peak, and summing them from the right gives isInner, which tells whether there is a peak to the right.
Finally, the root is the hash of the elements count and bags[0].
Testing
Our tests build MMRs of different sizes with HerodotusDev’s library, and check the proof of every leaf against the library’s root (and the library’s own proof verification). They also check that an index outside of the leaves, a wrong leaf, and swapped peaks are rejected, and that the root changes with the leaf count.
Constraint Count
| Circuit | Constraints |
|---|---|
MerkleMountainRangeProof(5) | 2252 |
MerkleMountainRangeProof(20) | 9752 |
With B = 20, the MMR can have up to a million leaves. About half of the cost is the proof within the mountain, and the other half is bagging: since the number of peaks is not known at compile time, the circuit always computes B - 1 hashes for it. If the verifier already knows the peaks, e.g. because they are public inputs, bagging could be done outside of the circuit, and only the peak of the leaf would need to be checked.
See Also
- HerodotusDev’s Accumulators MMR
- Grin’s MMR documentation, which explains MMRs in more detail.
Common Pitfalls
A circuit can compute the right answer for every honest input, and still be broken: what matters is what a dishonest prover can get away with. Most bugs in Circom circuits are under-constrained circuits, where some signal is not fully determined by the constraints, so a prover can pick a value of their liking and still create a valid proof.
The pitfalls below come up again and again throughout this book. Each of them links to the chapter where it appears.
Hints Are Not Constraints
The <-- operator assigns a value to a signal without adding any constraint, and so does an assert on a signal: they only run while computing the witness. A dishonest prover does not have to run them at all, and can put any value into such a signal.
So every signal assigned with <-- must be fully pinned down by === constraints afterwards.
- Integer Division computes the quotient and the remainder with
<--, and checking onlyin[0] === quot * in[1] + remandrem < in[1]is not enough: a “negative” remainder still passes, unless both the quotient and the remainder are range-checked. - Inversion has an
assert(in != 0), which does not prevent a witness within = 0, so the circuit must handle that case with constraints.
Booleans Must Be Constrained to Be Bits
Many circuits assume that some signal is a bit, e.g. the condition of IfElse & Switch, the selectors of a multiplexer, or the inputs of the logic gates. If it is not constrained to be 0 or 1, the output becomes a mix of both options.
In a Binary Merkle Tree, an index that is not a bit lets a prover choose the two children of a node freely, and prove that a leaf is in the tree although it is not! Use AssertBit, or obtain the bits from Num2Bits.
Comparisons Need Range Checks
LessThan(n) is only correct when both inputs are n-bit numbers, and it does not check this itself. For larger inputs, it silently returns a wrong result: e.g. it says that , where is actually the largest field element.
So always range-check the inputs of a comparison, unless they are already known to be small. Forgetting this broke Integer Division, and would break the indices of Two Sum.
There Are No Negative Numbers
Every signal is a field element modulo a prime , so is , and arithmetic wraps around at . This is easy to forget:
- A “negative” value passes a check like
x < yif the inputs are not range-checked. - An equation like
a === q * b + rholds modulo ; it only holds over the integers if the values are small enough to not wrap around, which is why Integer Division limits its number of bits. - At compile time, Circom compares field elements as signed numbers, so
-1 < 0is true there; seenbits.
Bit Decompositions Can Have Aliases
A field element of BN254 fits in 254 bits, but 254 bits can represent numbers larger than . So some values have two different 254-bit representations, and . If a circuit decomposes a value into 254 bits, it must also check that the bits represent a number less than , using an alias check. The Sparse Merkle Tree does this for its keys, otherwise a key could take two different paths in the tree.
Out-of-Bounds Accesses Do Not Fail
ArrayRead returns 0 for an index outside of the array, instead of failing. If the index comes from the prover, it must be range-checked; otherwise reading a 0 may be enough to cheat, as in Two Sum.
Check the Inputs, Not Just the Computation
A circuit proves a statement about its inputs, and the inputs are chosen by the prover. If the statement only makes sense for “valid” inputs, the circuit must check that they are valid:
- A Magic Square circuit that only checks the sums accepts a grid of all 5s.
- The famous formula of Missing Number returns a meaningless answer for repeated or out-of-range numbers.
- Sudoku needs both the range checks and the distinctness checks, as neither is enough on its own.
Bind Every Public Input
A public input that does not appear in any constraint may not be bound to the proof, so the same proof could be valid for another value of it. Tornado Cash squares its recipient for this reason, so that nobody can copy a proof from the mempool and change the recipient to themselves.
Hash Different Things Differently
When the same hash function is used for different kinds of data, a value of one kind may be passed off as another. In a Merkle tree, an internal node could be presented as a leaf, which is the second-preimage attack. Hash leaves and nodes differently, and if the depth of a tree is an input, make sure that it is the actual depth, as in the Incremental Merkle Tree.
Test the Failures
Tests that only check valid inputs can not find any of the bugs above. For every circuit, also test that invalid inputs are rejected: out-of-range values, non-bits, wrong orders, and so on. With Circomkit, expectFail checks that an input is rejected, and editWitness & expectConstraintFail let you hand-craft the witness of a dishonest prover, including the values assigned with <--. For example, the test of Integer Division forges a witness with a wrong quotient, and checks that the constraints reject it.
Logic errors are worth testing for as well: IsSorted once returned 1 if any pair was ordered, and a test with a fully reversed array could not notice it, while a test with a single pair out of order could.
Further Topics
The world of Circom is vast, and here we take a look at some topics beyond writing circuits.
Alternative Provers
SnarkJS is not the only option to prove Circom circuits, you can check out some alternative provers in other languages as well:
- Go-Rapidsnark is a collection of Go packages by Iden3, that allow you to compute witnesses, generate, or verify Circom proofs.
- Ark-Circom has Arkworks bindings to Circom’s R1CS for proof & witness generation.
- Lambdaworks has Circom adapters for Groth16.
However, these are not as capable as SnarkJS, e.g. they only support Groth16 protocol.
Large Circuits
If you have very large circuits (e.g. >20M constraints) you will have some practical problems, most notably the limited memory of your machine. There is a great HackMD post that describes what the best practices are for large circuits, see here.
Folding
Folding is when a “well-structured” circuit with many iterations is folded into a single “iteration” from which a proof is generated that proves all iterations are correct. See more at awesome-folding.
-
A recent work from PSE called Sonobe paves the way to fold Circom circuits.
-
Nova-Scotia is a middleware to compile Circom circuits for the Nova prover.
Just Logging
If you would like to experiment with some circuit code quickly, zkRepl is usually the best option. In any case, if you still want to play locally you can simply write logs in your code and compile your circuit with:
circom ./your-circuit.circom --verbose
This will not emit any build artifacts, it will only print logs.
Simple
These examples put the basic building blocks together into complete circuits:
- Fibonacci computes a Fibonacci number, a “Hello World” of Circom.
- Magic Square proves knowledge of a magic square, with range & distinctness checks.
- Missing Number solves a LeetCode problem, and shows why the input must be checked.
Fibonacci
Calculating n’th Fibonacci number is yet another “Hello World!” of Circom. We simply constrain the starting numbers (given as input in) and assert the recurrence relation
Fibonacci
template Fibonacci(n) {
assert(n >= 2);
signal input in[2];
signal output out;
signal fib[n+1];
fib[0] <== in[0];
fib[1] <== in[1];
for (var i = 2; i <= n; i++) {
fib[i] <== fib[i-2] + fib[i-1];
}
out <== fib[n];
}
Here is how computing the 4’th Fibonacci number looks like:
flowchart LR
in_1(("in[1]")) --> f1["fib[1]"]
in_0(("in[0]")) --> f0["fib[0]"]
f1 --> f2
f0 --> f2["fib[2]"]
f2 --> f3
f1 --> f3["fib[3]"]
f3 --> f4
f2 --> f4["fib[4]"]
f4 --> out(("out"))
You can also implement Fibonacci recursively in Circom!
template FibonacciRecursive(n) { signal input in[2]; signal output out; if (n <= 1) { out <== in[n]; } else { var prev = FibonacciRecursive(n-1)(in); var prevprev = FibonacciRecursive(n-2)(in); out <== prev + prevprev; } }However, this is the “stupid” recursive way where we are not memoizing: every call creates two more components, so the number of components grows exponentially with
n, just like the Fibonacci numbers themselves. That makes the circuit much larger and much slower to compile.
Constraint Count
Fibonacci(n) has 0 non-linear constraints! Every step is an addition, i.e. a linear constraint, which is free. So no matter how large n is, this circuit costs nothing to prove, which is a nice reminder that only multiplications of signals have a cost.
Magic Square
A magic square is an n-by-n grid of numbers where every row, every column and both diagonals add up to the same number, called the magic sum. A normal magic square additionally uses each of the numbers 1, 2, ..., n^2 exactly once. Here is the classic 3-by-3 one, with magic sum 15:
4 9 2
3 5 7
8 1 6
MagicSquare
template MagicSquare(n) {
signal input in[n][n];
// the magic sum of a normal magic square
var sum = n * (n*n + 1) \ 2;
// ensure all values are in range [1, n^2] and distinct,
// so that each of 1, 2, ..., n^2 is used exactly once
signal flat[n*n];
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
AssertInRange(1, n*n)(in[i][j]);
flat[i*n + j] <== in[i][j];
}
}
AssertDistinct(n*n)(flat);
// sum diagonals
var diags[2];
for (var d = 0; d < n; d++) {
diags[0] += in[d][d]; // top-left -> bottom-right
diags[1] += in[n-1-d][d]; // bottom-left -> top-right
}
sum === diags[0];
sum === diags[1];
// sum rows
var rowsums[n];
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
rowsums[i] += in[i][j];
}
sum === rowsums[i];
}
// sum columns
var colsums[n];
for (var j = 0; j < n; j++) {
for (var i = 0; i < n; i++) {
colsums[j] += in[i][j];
}
sum === colsums[j];
}
}
With this circuit you can prove that you know a normal n-by-n magic square without revealing it. The square in is the only input, and it is private.
The Magic Sum
The magic sum is not an input, because for a normal magic square it is fixed by n. The numbers 1, ..., n^2 add up to , and they are split evenly over n rows, so each row (and likewise each column and diagonal) must add up to
e.g. 15 for and 34 for . Since this is known at compile time, we compute it as a var. We use \, which is integer division in Circom, rather than /, which is division in the field. The two agree here because is always even, but \ makes the intent clear.
Summing with Variables
Notice that we never create a signal for the intermediate sums. diags, rowsums and colsums are all vars, so each of them simply builds up a linear expression over the input signals. When we finally write
sum === rowsums[i];
Circom emits a single constraint in[i][0] + in[i][1] + ... + in[i][n-1] = sum, with sum being a constant. There is no need to store each partial sum in its own signal. All we need is one constraint per line:
nconstraints for the rows,nconstraints for the columns,2constraints for the diagonals,
for a total of 2n + 2 constraints. These are all linear constraints though, so they are free: the compiler eliminates them by expressing some of the signals in terms of the others. The sums cost 0 non-linear constraints!
Using Each Number Once
The sums alone are not enough. Without any checks on the values, the circuit would happily accept squares that are not very magical at all, such as:
5 5 5 6 0 9
5 5 5 8 5 2
5 5 5 1 10 4
Every line adds up to 15 in both of them, but the first one repeats 5, and the second one uses 0 and 10. On top of that, every value is a field element, so a prover could also fill the grid with “negative” numbers (very large field elements) that happen to add up correctly.
To rule these out, we reuse two templates from earlier chapters, range checks and distinct values:
signal flat[n*n];
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
AssertInRange(1, n*n)(in[i][j]);
flat[i*n + j] <== in[i][j];
}
}
AssertDistinct(n*n)(flat);
Every value is now in [1, n^2], and there are n^2 distinct values, so the grid must contain each of 1, ..., n^2 exactly once. We flatten the square into flat because AssertDistinct expects a one-dimensional array.
Both checks are needed. With only the range check, the all-5s square is still accepted. With only the distinctness check, the second square above is still accepted.
So all of the cost of this circuit comes from these checks, as the sums are free.
Constraint Count
| Square | Constraints |
|---|---|
| 3-by-3 | 144 |
| 4-by-4 | 400 |
For the 3-by-3 square, 72 constraints are for the range checks (8 per cell), and 72 for AssertDistinct, which compares every pair of the 9 cells. The sums, as we have seen, are free.
The same pattern of “check the sums, the ranges and the distinctness” shows up again, at a larger scale, in the Sudoku example.
Missing Number
This is LeetCode 268: given an array nums of n distinct numbers in the range , find the only number in that range that is missing from the array. For example, for nums = [3, 0, 1] the answer is 2.
MissingNumber
template MissingNumber(n) {
signal input nums[n];
signal output out;
// without these checks, `out` would be meaningless for an invalid `nums`
for (var i = 0; i < n; i++) {
AssertInRange(0, n)(nums[i]);
}
AssertDistinct(n)(nums);
// the missing number is the sum of 0, 1, ..., n minus the sum of `nums`
var sum = 0;
for (var i = 0; i < n; i++) {
sum += nums[i];
}
out <== n * (n + 1) \ 2 - sum;
}
The Famous Trick
The well-known solution is a one-liner. The numbers add up to , and exactly one of them is missing from nums, so:
This is even better in a circuit than on a CPU: it is only additions and a constant, so it costs zero non-linear constraints!
template MissingNumber(n) {
signal input nums[n];
signal output out;
var sum = 0;
for (var i = 0; i < n; i++) {
sum += nums[i];
}
out <== n * (n + 1) \ 2 - sum;
}
We use
\, which is integer division in Circom, instead of/, which is division in the field. The two agree here because is always even.
The Catch
On LeetCode, the input is guaranteed to be valid. In a circuit, nothing is guaranteed: whoever creates the proof also picks the input. The circuit above returns some number for any array, valid or not. For example, with we have , and:
nums = [0, 0, 4]gives 2, but4is out of range and0is repeated.nums = [1, 4, 1]gives 0, which is not even missing from a valid point of view.
A proof that “the missing number is 2” would be meaningless here. So, just like the magic square, we must check the input as well:
- every number is in range , using
AssertInRange, - all numbers are distinct, using
AssertDistinct.
With these, nums is exactly with one number removed, and the formula gives the right answer.
Constraint Count
The formula is free, but the checks are not. AssertDistinct compares every pair of numbers, so the cost grows quadratically:
n | non-linear constraints |
|---|---|
| 9 | 144 |
| 100 | 11300 |
For , 9900 of these come from AssertDistinct and 1400 from the range checks. The famous trick that makes this problem “easy” is not where the work is: in a circuit, most of the cost goes into making sure that the input actually satisfies the assumptions of the problem.
Intermediate
These examples are mostly puzzles where the circuit verifies a solution, instead of finding it:
- Sudoku is the classic zero-knowledge example.
- Two Sum verifies the answer to the famous LeetCode problem.
- N-Queens verifies a placement of queens on a chessboard.
- Fixed-Point Arithmetic computes with fractions, as needed for zkML.
Sudoku
Sudoku is the classic example of a zero-knowledge proof: you want to convince someone that you have solved a puzzle, without showing them the solution.
Sudoku
template Sudoku(n_sqrt) {
var n = n_sqrt * n_sqrt; // board size is a perfect square
signal input solution[n][n]; // solution is a 2D array of numbers
signal input puzzle[n][n]; // puzzle is the same, but a zero indicates a blank
// ensure that solution & puzzle agrees
for (var row_i = 0; row_i < n; row_i++) {
for (var col_i = 0; col_i < n; col_i++) {
// puzzle is either empty (0), or the same as solution
puzzle[row_i][col_i] * (puzzle[row_i][col_i] - solution[row_i][col_i]) === 0;
}
}
// ensure all values in the solution are in range
for (var row_i = 0; row_i < n; row_i++) {
for (var col_i = 0; col_i < n; col_i++) {
AssertInRange(1, n)(solution[row_i][col_i]);
}
}
// ensure all values in a row are distinct
component distinctRows[n];
for (var row_i = 0; row_i < n; row_i++) {
for (var col_i = 0; col_i < n; col_i++) {
if (row_i == 0) {
distinctRows[col_i] = AssertDistinct(n);
}
distinctRows[col_i].in[row_i] <== solution[row_i][col_i];
}
}
// ensure all values in a column are distinct
component distinctCols[n];
for (var col_i = 0; col_i < n; col_i++) {
for (var row_i = 0; row_i < n; row_i++) {
if (col_i == 0) {
distinctCols[row_i] = AssertDistinct(n);
}
distinctCols[row_i].in[col_i] <== solution[row_i][col_i];
}
}
// ensure that all values in squares are distinct
component distinctSquares[n];
var s_i = 0;
for (var sr_i = 0; sr_i < n_sqrt; sr_i++) {
for (var sc_i = 0; sc_i < n_sqrt; sc_i++) {
// square index
distinctSquares[s_i] = AssertDistinct(n);
// (r, c) now marks the start of this square
var r = sr_i * n_sqrt;
var c = sc_i * n_sqrt;
var i = 0;
for (var row_i = r; row_i < r + n_sqrt; row_i++) {
for (var col_i = c; col_i < c + n_sqrt; col_i++) {
distinctSquares[s_i].in[i] <== solution[row_i][col_i];
i++;
}
}
s_i++;
}
}
}
The board is n-by-n, where n is a perfect square (4, 9, 16, …), and it is split into n boxes of size n_sqrt-by-n_sqrt. That is why the template takes n_sqrt as its parameter rather than n itself: Sudoku(3) is the usual 9-by-9 board with 3-by-3 boxes, and Sudoku(2) is a small 4-by-4 board with 2-by-2 boxes.
The circuit has two inputs:
puzzleis the board as it was given to you, with0for the blank cells. This is public, so that the verifier knows which puzzle you have solved.solutionis your filled board. This is private, and it never leaves the prover.
{
"file": "examples/intermediate/sudoku",
"template": "Sudoku",
"params": [3],
"pubs": ["puzzle"]
}
A solution is valid when all of the following hold:
- it agrees with the puzzle on every given cell,
- every value is in
[1, n], - every row has distinct values,
- every column has distinct values,
- every box has distinct values.
The circuit checks these rules one by one.
Agreeing with the Puzzle
puzzle[row_i][col_i] * (puzzle[row_i][col_i] - solution[row_i][col_i]) === 0;
For every cell, we want: “either the puzzle cell is blank, or it equals the solution cell”. A product is zero when either of its factors is zero, so a single multiplication encodes this “or”:
- If
puzzle[row_i][col_i] = 0, the left factor is zero and the constraint holds no matter what the solution has there. - Otherwise the right factor must be zero, i.e.
puzzle[row_i][col_i] = solution[row_i][col_i].
That is one constraint per cell.
Values in Range
AssertInRange(1, n)(solution[row_i][col_i]);
Each value of the solution is checked to be within [1, n] using the range check from earlier. Note that the lower bound matters just as much as the upper bound: without it, a prover could leave a cell as 0, or use a huge field element that wraps around.
For n = 9, we have MAX = 9, which needs 4 bits, so each range check is two 4-bit decompositions, i.e. 8 constraints.
Distinct Rows, Columns and Boxes
Every row, column and box is a group of n cells, and each group must contain distinct values. For this we use AssertDistinct, which checks every pair of cells in a group to be non-equal.
Rows and columns are straightforward: distinctRows[col_i] collects column col_i, and distinctCols[row_i] collects row row_i.
The names are swapped compared to what is collected, i.e.
distinctRowscollects the columns anddistinctColscollects the rows. It makes no difference for correctness: between the two of them every row and every column is checked.
Boxes need a bit more indexing. We walk over the boxes with (sr_i, sc_i), compute the top-left corner of the current box as (r, c) = (sr_i * n_sqrt, sc_i * n_sqrt), and then feed the n_sqrt * n_sqrt = n cells of that box into distinctSquares[s_i] one after the other. For a 4-by-4 board, the boxes are:
+-----+-----+
| 0 0 | 1 1 |
| 0 0 | 1 1 |
+-----+-----+
| 2 2 | 3 3 |
| 2 2 | 3 3 |
+-----+-----+
Why This Is Enough
Together, the range check and the distinctness checks pin down each group completely. A row has n cells, every cell is in [1, n], and no two cells are equal. There is only one way to fit n distinct values into n possible numbers, so every row is exactly a permutation of 1, 2, ..., n. The same holds for every column and every box, which is precisely the rule of Sudoku.
Neither check is enough on its own. Without the range check, a row such as 10 20 30 ... would be distinct. Without the distinctness check, a row of all 5s would be in range.
Constraint Count
There are 3n groups to check for distinctness, and each AssertDistinct(n) compares n(n-1)/2 pairs. This quadratic term is what dominates the circuit:
| Board | Constraints |
|---|---|
| 4-by-4 | 256 |
| 9-by-9 | 2673 |
For the 9-by-9 board, these break down as:
- 81 constraints for agreeing with the puzzle (one per cell),
- 648 constraints for the range checks (8 per cell),
- 1944 constraints for the distinctness checks (27 groups, 72 each).
Testing
The interesting tests are the ones that should fail. For each rule, we take a correct solution, break that single rule, and expect the witness calculation to fail:
- copy a value within a row, a column or a box,
- put a
0or ann + 1into a cell, - give a puzzle whose clue disagrees with the solution.
One gotcha: when making these “bad” inputs, make sure you copy the board instead of editing it in place. A spread such as { ...INPUT } only copies the top level, so badInput.solution[0][0] = ... would also change INPUT.solution. Every later test would then start from an already broken board, and could pass for the wrong reason.
const withCell = (i: number, j: number, value: number) => {
const solution = INPUT.solution.map((row) => [...row]);
solution[i][j] = value;
return { ...INPUT, solution };
};
it("should NOT accept non-distinct rows", async () => {
await circuit.expectFail(withCell(0, 0, INPUT.solution[0][1]));
});
Two Sum
This is LeetCode 1, perhaps the most famous coding interview question: given an array nums and a target, find two different indices i and j such that nums[i] + nums[j] = target. For example, for nums = [2, 7, 11, 15] and target = 9, the answer is i = 0, j = 1.
TwoSum
template TwoSum(n) {
signal input nums[n];
signal input target;
signal input i;
signal input j;
// indices must be within the array, as `ArrayRead` returns 0 otherwise
AssertInRange(0, n - 1)(i);
AssertInRange(0, n - 1)(j);
// indices must be different; we require `i < j` so that each pair is given in one order only
signal isLess <== LessThan(nbits(n - 1))([i, j]);
isLess === 1;
// the numbers at these indices must sum up to the target
signal a <== ArrayRead(n)(nums, i);
signal b <== ArrayRead(n)(nums, j);
a + b === target;
}
Verify, Don’t Search
The brute-force solution tries all pairs, which takes time. The famous solution uses a hashmap to find the pair in time:
function twoSum(nums: number[], target: number): [number, number] {
const seen = new Map<number, number>();
for (let j = 0; j < nums.length; j++) {
const i = seen.get(target - nums[j]);
if (i !== undefined) {
return [i, j];
}
seen.set(nums[j], j);
}
throw new Error("no solution");
}
Neither of these is a good fit for a circuit. Trying all pairs would cost constraints, and there are no hashmaps in a circuit.
Instead, we do not search at all! The prover runs the hashmap solution outside of the circuit, and gives the indices i and j as inputs. The circuit only verifies that they are a solution, which is much simpler:
signal a <== ArrayRead(n)(nums, i);
signal b <== ArrayRead(n)(nums, j);
a + b === target;
This is a recurring idea in zero-knowledge circuits: finding an answer may be hard, but checking it is often easy, and the circuit only needs to do the latter. We have seen this before with integer division, where the quotient is computed outside the circuit and only checked inside.
Checking the Indices
Since the indices come from the prover, the circuit must make sure that they are valid.
Different Indices
The two indices must be different, otherwise nums = [2, 7, 11, 15] with target = 4 would be “solved” by using the 2 twice. We require i < j, which also makes the order of the answer unique:
signal isLess <== LessThan(nbits(n - 1))([i, j]);
isLess === 1;
Indices Within the Array
This one is easy to miss. Recall that ArrayRead returns 0 if the index is not within the array. So without a range check, the prover could use an index that is out of bounds to read a 0:
nums = [2, 7, 11, 15]withtarget = 2is “solved” byi = 0, j = 4, since2 + 0 = 2.- The same works with a “negative” index such as
i = -1, which is a very large number in the field.
Both of these pass the checks above if we forget the range checks! Note that LessThan can not help us here, as it is only correct for inputs that are already range-checked. So we assert that both indices are in range using AssertInRange:
AssertInRange(0, n - 1)(i);
AssertInRange(0, n - 1)(j);
After that, LessThan is safe to use as well.
Constraint Count
Most of the cost comes from the two ArrayReads, each of which compares the index with every position of the array. So the circuit is :
n | non-linear constraints |
|---|---|
| 4 | 34 |
| 100 | 635 |
For , the two ArrayReads take 600 of these, and the range checks & LessThan take the rest.
Note that the numbers are field elements, so
nums[i] + nums[j] === targetis an equation modulo the prime . Since is huge, for “normal” numbers like those on LeetCode (even negative ones) this is the same as the usual equation over integers.
N-Queens
This is LeetCode 51: place n queens on an n-by-n chessboard so that no two queens attack each other. A queen attacks along its row, its column, and both of its diagonals. Here is a solution for :
. Q . .
. . . Q
Q . . .
. . Q .
NQueens
template NQueens(n) {
signal input queens[n];
// each queen is within the board
for (var r = 0; r < n; r++) {
AssertInRange(0, n - 1)(queens[r]);
}
// there is one queen per row by definition of `queens`,
// and there must be one queen per column as well
AssertDistinct(n)(queens);
// no two queens on the same diagonal, i.e. `r + c` is distinct,
// and on the same anti-diagonal, i.e. `r - c` is distinct
var diagonals[n];
var antiDiagonals[n];
for (var r = 0; r < n; r++) {
diagonals[r] = r + queens[r];
antiDiagonals[r] = r - queens[r];
}
AssertDistinct(n)(diagonals);
AssertDistinct(n)(antiDiagonals);
}
On LeetCode, you would find all solutions with backtracking. In a circuit, just like Sudoku, we instead verify a given solution: the prover finds a placement outside the circuit, and the circuit checks that it is valid.
Representing the Board
We could take the whole board as an n-by-n array of 0s and 1s, but there is a much better representation. Since there must be exactly one queen in each row, we can describe a placement by the column of the queen in each row:
The solution above is queens = [1, 3, 0, 2]. With this representation, “one queen per row” holds by definition, and we do not have to check it at all. Choosing a good representation of the input is often the cheapest optimization there is!
The Checks
What is left is to check that each queen is on the board, and that no two queens share a column or a diagonal:
- On the board: each
queens[r]is in range , usingAssertInRange. - Columns: all
queens[r]are distinct, usingAssertDistinct. - Diagonals: two squares and are on the same diagonal when , and on the same anti-diagonal when . So all
r - queens[r]must be distinct, and so must allr + queens[r].
Note that r - queens[r] may be negative, which is a very large number in the field. That is not a problem here, since AssertDistinct only checks for equality, and two field elements are equal exactly when the integers they come from are equal (for numbers this small).
Testing
Besides testing a few valid and invalid placements, we can test the circuit against all possible placements for a small board. For , every placement with distinct columns is a permutation of , and there are of them. The 6-queens puzzle has exactly 4 solutions, so the circuit must accept exactly 4 of these 720 permutations, which it does.
Constraint Count
There are three AssertDistinct checks of n values each, which compare every pair, and n range checks. For the classic 8-queens puzzle, the circuit has 216 non-linear constraints: 168 for the distinctness checks, and 48 for the range checks.
Fixed-Point Arithmetic
Circuits only know field elements, but many real computations need fractions: prices, interest rates, or the weights of a machine learning model. Floating-point numbers are far too complex for a circuit, so we use fixed-point numbers instead, which are simply integers with an implied scale. This is how zkML libraries such as circomlib-ml represent the numbers of a neural network.
Representation
A fixed-point number with fractional bits is stored as the integer . With :
| Number | Stored as |
|---|---|
| , rounded | |
Negative numbers are just negative field elements, i.e. , as described in Finite Fields. We call a number -bit if its stored integer is in . Our circuits are written for any and , and the tests use .
We use a power of two as the scale, so that rescaling is just dropping bits. A power of ten such as (as used by circomlib-ml, and by Ethereum tokens) works as well, but it needs an integer division instead.
Addition Is Free
The sum of two fixed-point numbers is the sum of their integers, as . So addition, subtraction, and multiplication by an integer constant are free, just like with integers.
Multiplication Needs Rescaling
The product of two fixed-point numbers has the wrong scale:
So after multiplying, we must divide by , i.e. drop the lowest bits. In a field, there is no “drop the bits” operation, so we decompose the number into bits and add back only the ones we keep.
Rounding Signed Numbers
Decomposing into bits only works for non-negative numbers, as a negative number is a huge field element. So we first shift the number by , which maps the signed range to , drop the bits, and then undo the shift:
template FixedPointRescale(M, F) {
assert(F < M && M < 254);
signal input in;
signal output out;
// shift to a non-negative number, which also asserts that `in` has `M` bits
signal bits[M] <== Num2Bits(M)(in + 2 ** (M - 1));
// drop the lowest `F` bits
var shifted = 0;
for (var i = F; i < M; i++) {
shifted += bits[i] * 2 ** (i - F);
}
// undo the shift, which is a multiple of `2^F`
out <== shifted - 2 ** (M - 1 - F);
}
Since the shift is a multiple of , undoing it after dropping bits gives exactly , i.e. the result is rounded down, also for negative numbers: becomes , not .
The bit decomposition has another job as well: it checks that the input actually has bits. Without it, a number such as would wrap around after the shift, and give a wrong result.
Multiplication
template AssertSigned(N) {
signal input in;
// shifting by `2^(N-1)` maps [-2^(N-1), 2^(N-1)) to [0, 2^N)
AssertBits(N)(in + 2 ** (N - 1));
}
template FixedPointMul(N, F) {
signal input in[2];
signal output out;
AssertSigned(N)(in[0]);
AssertSigned(N)(in[1]);
// the product has `2F` fractional bits; it is at most `2^(2N-2)`, which is
// the square of the smallest number `-2^(N-1)`, so it fits in `2N` bits
signal product <== in[0] * in[1];
out <== FixedPointRescale(2 * N, F)(product);
}
We range-check the inputs, so that we know the size of their product. An -bit number is at least , so the product is at most .
Careful here: itself is not a -bit signed number, which goes up to ! The square of the smallest number is the single product that does not fit, so we rescale with bits. The tests multiply the extreme values to catch exactly this kind of off-by-one.
Note that the output is not range-checked: the product of two -bit numbers may need more than bits, e.g. does not fit in , whose largest number is just under . If the output is used in another multiplication, that multiplication checks its range anyway.
Dot Product
Most of the arithmetic in a neural network is in dot products, . Rescaling costs constraints, which is much more than the multiplication itself, so we do not rescale each product. Instead, we add up the products with fractional bits, which is free, and rescale only once at the end:
template FixedPointDot(n, N, F) {
signal input a[n];
signal input b[n];
signal output out;
// sum the products with `2F` fractional bits, without rescaling them one by one
signal products[n];
var sum = 0;
for (var i = 0; i < n; i++) {
AssertSigned(N)(a[i]);
AssertSigned(N)(b[i]);
products[i] <== a[i] * b[i];
sum += products[i];
}
// each product is at most `2^(2N-2)`, so their sum is less than `2^(2N-2+nbits(n))`
out <== FixedPointRescale(2 * N + nbits(n), F)(sum);
}
The sum of products is larger than a single one, so we need more bits, which is about nbits(n). As a bonus, rescaling once also rounds once, so the result is more accurate.
Beyond Dot Products
With these, you can build a whole neural network layer: a matrix-vector product is dot products, and adding a bias is free. The activation functions are harder:
- ReLU is , which needs the sign of . In
FixedPointRescale, the sign is the top bit of the shifted number, so it is almost free to get! - Sigmoid and other smooth functions have no exact form, so they are replaced with a polynomial approximation, which only needs multiplications and additions.
Constraint Count
| Circuit | non-linear constraints |
|---|---|
FixedPointMul(32, 16) | 129 |
FixedPointDot(4, 32, 16) | 327 |
FixedPointDot(100, 32, 16) | 6571 |
FixedPointMul(N, F) has constraints for range-checking the inputs, 1 for the product, and for rescaling, so . FixedPointDot(n, N, F) has for the range checks & products, and nbits(n) for a single rescale. Rescaling each product separately would add constraints per product, about 6400 more for .
See Also
- Integer Division, for rescaling with a scale that is not a power of two.
- circomlib-ml, which implements the layers of a neural network in Circom.
Advanced
These examples are larger circuits, focusing on optimization and real-world applications:
- Filtering Tuples solves a ZK puzzle from Axiom, moving elements of an array with a logarithmic shifter.
- Tornado Cash is a private mixer, built from commitments, nullifiers and Merkle trees.
Filtering Tuples
This example is a solution to a ZK puzzle from the Axiom Open Source Program:
Write a circuit that takes a fixed-length array
inof 100 tuples and an arbitrary valuematch, and outputs:
num_match, the number of tuples whose first entry ismatchout, an array of 100 tuples where the firstnum_matchentries are the matching tuples, and the rest are 0-paddedThe goal is to minimize the number of non-linear constraints.
For example, if match = 5 and the input is [[6, 8], [5, 5], [7, 6], [5, 4], ...], the output starts with [[5, 5], [5, 4], ...], keeping the matching tuples in their original order. Our solution is generic over the number of tuples n, and the challenge is Filter(100).
Filter
template Filter(n) {
signal input in[n][2];
signal input match;
signal output num_match;
signal output out[n][2];
// number of bits needed for a shift, which is at most n-1
var B = nbits(n - 1);
// find the matching tuples
signal isMatch[n];
for (var i = 0; i < n; i++) {
isMatch[i] <== IsEqual()([in[i][0], match]);
}
// `val[j]` and `bits[j]` hold the second entry & shift bits of the tuple in slot `j`;
// non-matching tuples are zeroed out, so moving them around has no effect
var val[n];
var bits[n][B];
signal values[n];
signal shifts[n];
component shiftBits[n-1]; // the first tuple never moves
var count = 0;
for (var i = 0; i < n; i++) {
// the shift is the number of non-matching tuples before this one
values[i] <== isMatch[i] * in[i][1];
shifts[i] <== isMatch[i] * (i - count);
count += isMatch[i];
val[i] = values[i];
// a tuple can not move further left than the first slot, so the shift
// of the i'th tuple is at most `i`, and fits in `nbits(i)` bits
var b_i = nbits(i);
if (i > 0) {
shiftBits[i-1] = Num2Bits(b_i);
shiftBits[i-1].in <== shifts[i];
}
for (var k = 0; k < B; k++) {
bits[i][k] = k < b_i ? shiftBits[i-1].out[k] : 0;
}
}
num_match <== count;
// at stage `b`, a tuple whose shift has bit `b` set moves left by `2^b`;
// it carries its value along with the remaining bits `b+1, b+2, ...` of its shift
//
// as above, the remaining shift of a tuple in slot `j` is at most `j`, so its
// bit `k` can only be set if `j >= 2^k`; we skip the products that are always 0
signal movedVal[B][n];
signal movedBits[B][n][B];
for (var b = 0; b < B; b++) {
var d = 1 << b;
// what leaves each slot, i.e. the tuple if it moves and 0 otherwise
for (var j = 0; j < n; j++) {
if (j >= d) {
movedVal[b][j] <== bits[j][b] * val[j];
} else {
// can not move further left, its shift is guaranteed to be smaller than `d`
movedVal[b][j] <== 0;
}
for (var k = 0; k < B; k++) {
if (k > b && j >= (1 << k)) {
movedBits[b][j][k] <== bits[j][b] * bits[j][k];
} else {
movedBits[b][j][k] <== 0;
}
}
}
// each slot keeps what has not left, and receives what leaves from `d` slots to the right
for (var j = 0; j < n; j++) {
val[j] = val[j] - movedVal[b][j];
if (j + d < n) {
val[j] += movedVal[b][j + d];
}
for (var k = b + 1; k < B; k++) {
bits[j][k] = bits[j][k] - movedBits[b][j][k];
if (j + d < n) {
bits[j][k] += movedBits[b][j + d][k];
}
}
}
}
// the first entry of a matching tuple is `match` itself, so we only need to know
// which slots are filled, i.e. the first `num_match` slots: `isFilled = [1, ..., 1, 0, ..., 0]`
signal isFilled[n];
for (var j = 0; j < n; j++) {
isFilled[j] <-- j < count ? 1 : 0;
}
// the first one is a bit, and each next one is either 0 or the same as the previous one,
// so all of them are bits and once a 0 is seen the rest are 0 as well
isFilled[0] * (isFilled[0] - 1) === 0;
for (var j = 1; j < n; j++) {
isFilled[j] * (isFilled[j - 1] - isFilled[j]) === 0;
}
var filled = 0;
for (var j = 0; j < n; j++) {
filled += isFilled[j];
}
filled === num_match;
for (var j = 0; j < n; j++) {
out[j][0] <== match * isFilled[j];
out[j][1] <== val[j];
}
}
With 100 tuples, this circuit has 3203 non-linear constraints. Let us see how we get there.
The Naive Approach
First, we find the matching tuples with IsEqual, and count them as we go:
A matching tuple i goes to the slot , i.e. the number of matching tuples before it. Since is just a sum, it costs nothing. Then, each output slot k can pick its tuple as:
This is correct, but every pair of i and k needs an IsEqual and a few multiplications. That is about pairs, and for 100 tuples it adds up to 25447 non-linear constraints. We can do much better.
The First Entries Are Free
Notice that we do not need to move the first entries at all: the first entry of a matching tuple is match itself! So out[k][0] is match for the first num_match slots, and 0 for the rest:
out[j][0] <== match * isFilled[j];
where isFilled = [1, ..., 1, 0, ..., 0] has exactly num_match ones. We let the prover provide isFilled, and constrain it as follows:
isFilled[0] * (isFilled[0] - 1) === 0;
for (var j = 1; j < n; j++) {
isFilled[j] * (isFilled[j - 1] - isFilled[j]) === 0;
}
The first constraint makes isFilled[0] a bit. The others say that each entry is either 0, or equal to the previous one. So all entries are bits, and once there is a 0 the rest are all 0. Finally, their sum must be num_match, which leaves only one possible isFilled. That is just one constraint per slot, plus one more for the multiplication with match.
Now, only the second entries must be moved around.
Moving Left with a Log-Shifter
Instead of thinking which tuple goes to each slot, let us think how far each tuple must move. A matching tuple i goes to slot , so it moves to the left by:
which is the number of non-matching tuples before it. Again, this is a sum, so it is free. We could move each tuple by in one step, but that is again an array access with a variable index. Instead, we break the shift into its bits:
and move the tuples in stages: at stage , a tuple moves to the left by if its bit is set. After all the stages, every tuple has moved by exactly . Since , we need only stages, which is 7 for 100 tuples.
As an example, let a be the match value, and x be something else:
| slot | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| input | x | x | x | x | ||||
| shift | 0 | 1 | 3 | 3 | ||||
| after stage 0 (by 1) | ||||||||
| after stage 1 (by 2) |
Here has shift so it moves only in stage 0, and have shift so they move in both stages. With 8 tuples there is also a stage 2 (by 4), but here no shift has that bit set, so nothing moves.
No Collisions
Can two tuples end up in the same slot at some stage? That would be a problem, as they would be added together. Luckily, the answer is no.
Consider two consecutive matching tuples . They go to consecutive slots, so , and since counts the non-matching tuples before each one, we also have . After the stages , each tuple has moved by the lower bits of its shift, i.e. by . So the distance between the two tuples is:
If and have the same higher bits, this is exactly 1. Otherwise, is larger by at least in the higher bits, and the distance is at least . Either way the distance is positive, so the tuples never collide, and they also keep their order.
For this to hold, the non-matching tuples must not get in the way. So we simply turn them into zeros, both their value and their shift, and then moving zeros around has no effect at all:
values[i] <== isMatch[i] * in[i][1];
shifts[i] <== isMatch[i] * (i - count);
A Stage
At stage with , each slot j keeps whatever does not leave it, and receives whatever leaves from the slot j + d:
Here is the neat part: the product moved[j] is used twice, once for leaving slot j and once for arriving at slot j - d. So a stage costs just one multiplication per slot for each value that is moved.
A tuple must also carry the remaining bits of its shift as it moves, as they are needed in the later stages. Those are moved in the same way, again with one multiplication each. The bits are computed once at the start using Num2Bits, and they move along with the tuple from then on.
Skipping the Zeros
A tuple can never move to the left of slot 0. So a tuple in slot j has at most j slots left to move, which tells us that some bits are always 0:
- The shift of tuple
iis at mosti, so it fits innbits(i)bits. The first tuple never moves at all. - During the stages, the bit of a tuple in slot
jcan only be set if .
We skip the multiplications for those, and constrain the corresponding signals to 0 instead, which is not a non-linear constraint.
Is It Sound?
Almost everything in this circuit is computed with <== from the inputs, so there is no room for a dishonest prover. The only values that come from the prover are:
- the inverses within
IsEqual, which are fixed by its constraints, - the bits within
Num2Bits, which are unique for a number that fits in the given bits, - the
isFilledmask, which is unique as described above.
So there is exactly one valid witness for each input, and since the shifting never causes a collision, that witness gives the correct output.
Constraint Count
Here is where the 3203 non-linear constraints of Filter(100) come from:
| What | Constraints |
|---|---|
IsEqual for each tuple | 200 |
| zeroing the values and shifts | 199 |
Num2Bits for the shifts | 573 |
| moving the values through the stages | 573 |
| moving the shift bits through the stages | 1458 |
the isFilled mask, and out[j][0] | 200 |
| Total | 3203 |
That is about 8 times fewer constraints than the naive approach. Notice that moving the shift bits is the most expensive part; this is the price we pay for not using any variable-index array accesses.
Tornado Cash
Tornado Cash is a mixer on Ethereum, and one of the best-known applications of zero-knowledge proofs. Users deposit a fixed amount of tokens, and later withdraw them to a different address. Anyone can see the deposits and the withdrawals, but nobody can tell which deposit a withdrawal belongs to. This example puts together many of the pieces from this book: commitments, incremental Merkle trees, and a new one, nullifiers.
How It Works
- Deposit: the user picks two random secrets, a
nullifierand asecret, and sends the tokens along with a commitment to the contract. The contract inserts into an incremental Merkle tree. The secrets are kept by the user, and the commitment hides them. - Withdraw: later, the user proves in zero-knowledge that they know the secrets of some commitment in the tree, without saying which one. Along with the proof, they reveal the nullifier hash . The contract checks the proof, checks that the nullifier hash was not seen before, records it, and sends the tokens to the recipient.
The anonymity comes from the Merkle proof: it shows that the commitment is one of the leaves, and the more deposits there are, the larger the crowd to hide in.
CommitmentHasher
template CommitmentHasher() {
signal input nullifier;
signal input secret;
signal output commitment;
signal output nullifierHash;
commitment <== Poseidon(2)([nullifier, secret]);
nullifierHash <== Poseidon(1)([nullifier]);
}
The original circuits use a Pedersen hash for the commitment and MiMCSponge for the Merkle tree. We use Poseidon for both, which is much cheaper; see Hashing for a comparison.
Withdraw
template Withdraw(DEPTH) {
signal input root;
signal input nullifierHash;
signal input recipient;
signal input relayer;
signal input fee;
signal input nullifier;
signal input secret;
signal input index;
signal input siblings[DEPTH];
// the nullifier hash must belong to the deposit
signal (commitment, computedNullifierHash) <== CommitmentHasher()(nullifier, secret);
computedNullifierHash === nullifierHash;
// the deposit must be in the tree
signal computedRoot <== BinaryMerkleRoot(DEPTH)(commitment, DEPTH, index, siblings);
computedRoot === root;
// these are not used in any constraint, so we add dummy constraints to bind
// them to the proof; otherwise, they could be changed without invalidating it
signal recipientSquare <== recipient * recipient;
signal relayerSquare <== relayer * relayer;
signal feeSquare <== fee * fee;
}
The tree is a binary Merkle tree with Poseidon, so we use zk-kit’s BinaryMerkleRoot as in the Incremental Merkle Tree chapter, and test it against zk-kit’s IMT in TypeScript.
Nullifiers
Without nullifiers, the same deposit could be withdrawn again and again: the proof only shows that a deposit exists, and since it does not reveal which one, the contract can not tell that it was already used.
The nullifier hash solves this. It is uniquely determined by the deposit, so withdrawing the same deposit twice reveals the same nullifier hash, and the contract rejects the second withdrawal. At the same time, it does not reveal which deposit it belongs to, since computing the commitment also requires the secret.
Why two secrets, and not just one? The commitment must not be computable from the nullifier hash, otherwise anyone could find the commitment in the tree, and link the withdrawal to its deposit. The secret is never revealed, so the commitment stays hidden, even after the nullifier hash is published.
Note that the nullifier hash depends only on the deposit, and not on its position in the tree. A prover might try to use a different index for the same deposit, but the Merkle proof fails for any position other than the real one, and even if a commitment was deposited twice, both would have the same nullifier hash and could be withdrawn only once.
Binding the Public Inputs
The recipient, relayer, and fee are not needed to prove anything, so why are they inputs at all? Because the proof is public: it is sent in a transaction, and anyone watching the mempool can copy it. If the recipient was not part of the proof, an attacker could replace it with their own address, and steal the withdrawal.
So the recipient is a public input of the proof, and changing it should make the proof invalid. But the circuit does not use it anywhere, so the original circuit adds dummy constraints with squares, to make sure that these inputs are bound to the proof:
signal recipientSquare <== recipient * recipient;
The original code is honest about it: “Most likely it is not required, but it’s better to stay on the safe side and it only takes 2 constraints”. Indeed, the Groth16 setup of snarkjs adds an extra constraint of the form x * 0 = 0 for every public input x, which binds it to the proof even if the circuit never uses it. So with snarkjs, the squares are only a defense in depth; but other proof systems and tools may not do this, so it is a good habit to make sure that every public input appears in a constraint.
The relayer and fee exist because the user’s new address has no ETH to pay for gas: a relayer sends the transaction on their behalf, and takes a fee from the withdrawn amount. Binding them prevents anyone from raising the fee.
Trusting the Circuit
This circuit has a famous history. In 2019, a bug was found in the MiMC implementation of circomlib that Tornado Cash used: a single = instead of <== left an output of the hash under-constrained, so a prover could choose a fake root and withdraw tokens that were never deposited. The Tornado Cash team found it, drained the vulnerable contract themselves, and moved the funds to a fixed one. It is a great reminder that one missing constraint is enough to break everything.
Constraint Count
| Circuit | non-linear constraints |
|---|---|
CommitmentHasher() | 453 |
Withdraw(20) | 5316 |
The commitment and the nullifier hash take 240 + 213 constraints for Poseidon(2) and Poseidon(1). The Merkle proof takes most of the rest, about 243 per level, which is a Poseidon(2) and a few constraints to put the children in order. The three squares add 3. With a depth of 20, the tree has room for about a million deposits.
See Also
- Tornado Cash circuits, the original implementation.
- Proof of Innocence by Chainway, which lets a Tornado Cash user prove that their withdrawal does not come from a list of deposits of their choosing, e.g. those of a hack, without revealing which deposit it does come from.
- Semaphore, which uses the same ideas (a Merkle tree of commitments and nullifiers) for anonymous signaling, e.g. voting.