Unleash the non-determinism of constraints to improve zero-knowledge proof performance

The non-determinism inherent in constraints systems at first appears like an unusual, somewhat weird feature for those who start working in the zero knowledge field. But as we will show, this non-determinism can also be leveraged to reduce the size and complexity of such constraints systems, thus improving the performance of zero-knowledge proofs.

We have already written about how isekai converts source code into arithmetic circuits, but there is one thing we did not talk much about, although it plays an essential role inside isekai. It is the constraints system that is generated from the arithmetic circuit and that constitutes the input of the different proof systems.

The constraints system are bi-linear equations that represent the execution of a program. Each instruction of a source code is encoded into one or several equations, so they are like an encoded version of the program listing. The values of the equation variables can be seen as the trace of the program execution. If two constraints systems are mathematically equivalent but one has less constraints, the zero-knowledge proofs based on the smaller system will be typically more efficient.

At the beginning, isekai was using libsnark to generate these constraints but we now use our own implementation because we need to generate constraints for other fields. Working at the constraints level can be quite powerful and I will explain in this post some tricks that we used.

Constraints are sensitive
The first thing we noticed when we wrote our own constraints generator is that the resulting system was smaller in size and performing a little bit better that libsnark’s output. It turns out that the reason was simply in the way the boolean constraints were expressed:

x(x-1)=0 <=> x=x²

While being strictly equivalent, isekai’s result (on the right) is a bit more compact and generates (slightly) smaller and faster proofs!

Since bit decomposition includes a linear constraint that can be simplified, we were tempted to go further by removing it and generating an equivalent system with one constraint less, every time there is a bit decomposition. You should know that bit decomposition appears a lot in an arithmetic circuit, because a computer operates modulo 32 bits while the constraints typically live in a 256 bit world. So we constantly need to check for 32 bits overflow and this is done with a 32 bit decomposition. However, the resulting system, while effectively having quite less constraints than libsnark output was this time bigger in size and generating slower proofs!? The reason is that the resulting constraints, although less of them, are more complex.

Non-determinism
The constraints system allows us to take advantage of non-determinism. A simple example is with field division. To compute 1/b in a prime p field, one can take bᵖ⁻² using Fermat’s little theorem. Such formulation would require lots of bi-linear equations e.g doing bₙ=bₙ₋₁*bₙ₋₁until we reach p-2 but instead we can use only one simple bi-linear constraint (if b is not null): a*b=1.

The same trick can be used for integer division a/b; instead of implementing the Euclidean algorithm and converting it to a constraint system, we can simply use the constraint a-r=b*q (together with the additional constraints enforcing r<b).

Memory Access

Non-determinism can also be used for dynamic memory access. You should know that memory access is best implemented using techniques from TinyRAM paper. What I will explain is much less efficient but at the same time much simpler and easy to understand so consider it is for educational purposes only.

To illustrate dynamic memory access, let’s assume we have an array a of size n and we need to access a[b]. Both b and a are variables of the system (i.e they are not constant values). The naive way to implement a[b] is by trying all possibilities;

if (b==0)
    return a[0] 
else if b(==1)
    return a[1]
else
…
else if (b==n-1) 
    return a[n-1]

Such formulation can be easily encoded into a constraint system that will generate 3n constraints (think of one for the ‘if, one for the ‘else’ and one for the ‘return’).

One way to improve this is by using a new gate that I call arithmetic split. It takes an input b and generate n outputs bᵢ which are all 0 except for the one where i is equal to b. The trick is that such gate can be implemented with n+2 constraints;

• n constraints saying that bᵢ are booleans (0 or 1)
• one constraint expressing that the bᵢ are all null except one (∑bᵢ = 1)
• one stating that the non-null element correspond to b (∑bᵢ*i=b).

Then a[b] is simply the sum of a[i]*bᵢ, which requires n additional constraints.

Using arithmetic-split gate for array look-up

It can be easily proved that the previous system while having two more constraints is equivalent to:

Here we only gained two constraints. A better optimization is to use binary-search techniques. Binary search usually does not work well with constraint systems as we need to track both branches, so effectively doubling the halving…

However here the point is that an array of size two can be accessed by only one constraint, so one constraint can halve an array in two arrays, giving in total 1 + 2 + 4 + …+ 2ᵏ = 2ᵏ⁺¹ constraints where k is the bit length of n. That means that instead of 2n constraints with the arithmetic split gate, we can achieve something between n and 2n, depending on how close n is to a power of 2.

When the array a is a constant array, the previous technique generates n constraints. However we can take advantage of the array being of constant values to reduce the cost even more, by using polynomials.

Evaluating polynomials
A basic observation is that monomials can be trivially computed from their previous monomial with one constraint: xᵏ = x.xᵏ⁻¹ which means a polynomial can be computed by at most n — 1 constraints where n is the polynomial’s degree.

The idea then is to lower the degree of the polynomial by doing Euclidean division. With the constraint P — R = B ∗ Q, we can compute polynomial P using lower degree polynomials R, B and Q. If we keep repeating this process with the results of Euclidean division, we can constantly reduce the overall degree of the resulting polynomials. We observe here there is a race condition on the number of constraints, increasing with the number of divisions and polynomials, and decreasing with the degree of the polynomials. It turns out we can win this race, the minimum of constraints being obtained when the resulting degree is close to √n, giving approximately 2√n constraints.

Going back to our initial problem of doing an array look-up for a constant array a of size n, it can be done in O(√n) by using the polynomial of degree n-1 such that P(i) = a[i] for all i = 0…n-1

The above examples are obviously not exhaustive. There is significant scope for further optimisation of constraints systems, and non-determinism is one of the principal tools available for this.