Constraint System Counter

This repository provides a way of measuring the stats for R1CS. It is built with the use case of isogeny walks in mind, dealing with repeated blocks of constraints.

How to run

To run, make sure you have the Rust programming language installed and run

cargo run --release

Structure

The file constraint_system.rs contains the basics that all approaches to specify constraint systems share. These are expanded upon in the folder constraint_system. The approaches module contains the concrete approaches presented in the paper.

There are two ways of specifying constraint systems:

Symbolic approach

The basic approach only considers variables, without considering their coefficients. This has the potential disadvantage of overcounting the number of non-zero entries when coefficients cancel out.

Associated with this approach are two optimization methods:

• nnz_optimizer.rs will check for every variable whether it is more optimally represented as $(r, i)$ or as $(r, r + i)$. This has the potential to minimize the number of non-zero entries if the latter linear combination is used more often. The sum occurs naturally when converting constraints over Fp² to Fp.
• util/powers_of_variables.rs contains a utility to optimally compute powers of a certain variable. It will use squares when possible, and then it will set these coefficients so that they match coefficients already in linear combinations. This again saves non-zero entries.

Exact approach

There is an optimizing approach that automatically does variable substitution to minimize the number of non-zero entries. This enables automatically finding the sparsest representation of the constraint system.

• The exact approach exhaustively searches for the optimal variable representation. This always gives the best results. It will not change the constraint system though: for example, it might be more efficient to represent $ Y*Y=Y^2+Y$ as $(Y + 1)*Y=Y^2 + Y$, but this is outside of the scope of the optimizer. This approach can be used by calling optimize_exact.
• A disadvantage of the exact approach is that it scales very badly with the size of the constraint system. Whenever the system gets too large, the heuristic approach can be used instead by calling optimize_heuristic. This will usually produce the same results as the exact approach.

Analogous to the nnz_optimizer, there is the exact_coefficient_powers_of_variables optimizer as well. It will do the same thing: building powers of variables as efficiently as possible, attempting to use linear combinations that are already in use and can therefore be optimized away by one of the optimization approaches.

Optimizing the number of non-zero entries

To optimize the number of non-zero entries of a general R1CS $(A, B, C)$, one can put the constraint matrices under each other, $K$ = $\begin{pmatrix} A\B\C \end{pmatrix}$, and then try to find a full-rank matrix $T$ such that $KT$ is sparsest. This follows from the fact that

$$Ax \circ Bx = Cx \Leftrightarrow (AT)(T^{-1}x) \circ (BT)(T^{-1}x) = (CT)(T^{-1}x)$$

i.e. $T^{-1}x$ is a solution to the new system $(AT, BT, CT)$. The paper 'Sparsification of Rectangular Matrices' describes how such an optimal $T$ can be found.

In our case however, the constraint system is not shaped exactly as a regular R1CS. This is due to the fact that we specify only the constraints for one step, which we then duplicate for every step in the isogeny walk. We have three types of variables in the system:

• Curve variables, such as the $j$-invariants. These are used only for the curves themselves. Since they are used in two steps, once as the curve to move from and once as the curve to move towards, we can only use variables from the same curve to redefine these. I.e. $j_0 \leftarrow j_0 + j_0^2 + 1$ is valid, but $j_0 \leftarrow j_0 + f$ is not. We should also ensure that $j_0$ and $j_1$ are transformed in the same way; they represent the same set of variables.
• Step variables, such as the roots $f$. These are used only within this step, and therefore any change of variables within the constraint system of a single step is valid.
• 1: The constant appears only once in the constraint system. It may not be redefined, but used to redefine any variable.

To make things more confusing: redefining a variable means changing the columns of the other variables in the linear combination. The variable change $f \leftarrow f + j_0 + 1$ is valid, and means subtracting the column for $f$ from the columns for $j_0$ and $1$.

Suppose we sort the matrix $K$ by variables and rows. The resulting matrix then looks like

$$\tilde{K} = \begin{bmatrix} F & G & H & O_1 \\\ 0 & E & 0 & O_2 \end{bmatrix}.$$

Here, the first row of submatrices represents the step constraints, and the second row represents the curve constraints. The first column represents the step variables, the second the curve variables on the left hand side, the third the curve variables on the right hand side, and the last column has width 1 and represents the contributions of 1.

Using this definition for $\tilde{K}$, the transformation matrix looks like

$$T = \begin{bmatrix} A & B & C & Q \\\ 0 & D & 0 & R \\\ 0 & 0 & D & R \\\ 0 & 0 & 0 & 1 \end{bmatrix}.$$

Note that step constraints use any linear combination of variables, while curve constraints use only the variables from the same curve and 1. They are also transformed in the same way, with $D$ and $R$ appearing twice. 1 is not transformed.

For the heuristic approach, we try linear combinations of two columns within these rules and replace one of them with the sparsest linear combination. If a column becomes 0, this means that the variable is redundant.

For the exact approach, we use the exact algorithm of the abovementioned paper. We first transform the problem of finding $T$ to remove the restrictions on $T$ and then proceed in several steps. This has the additional advantage of reducing the size of the problem, which allows us to use this expensive approach for larger systems overall.

• First, note that for the transformed system, $F' = FA$. We can therefore first compute $A$ by optimizing the sparsity of $F'$.

• For the second step, we will focus on the curve constraints. Here, we want to find the solution $B$, $C$ and $D$ such that

  \begin{bmatrix}
  F' & G' & H' \\
  0 & E' & 0 \\
  \end{bmatrix} = \begin{bmatrix}
  F & G & H \\
  0 & E & 0 \\
  \end{bmatrix} \cdot
  \begin{bmatrix}
  A & B & C \\
  0 & D & 0 \\
  0 & 0 & D
  \end{bmatrix}
  

  is sparsest. Since we have already found $A$, and $D$ appears twice, we can instead search for a solution of the system

  \begin{bmatrix}
  F' & 0 & G' \\
  0 & F' & H' \\
  0 & 0 & E'
  \end{bmatrix}=
  \begin{bmatrix}
  F & 0 & G \\
  0 & F & H \\
  0 & 0 & E
  \end{bmatrix} \cdot
  \begin{bmatrix}
  A & 0 & B \\
  0 & A & C \\
  0 & 0 & D
  \end{bmatrix}.
  

  The advantage here is that we already have the first two column (of submatrices) of both $T$ and $K'$, and so we just have to find the column consisting of submatrices $G'$, $H'$ and $E'$. The number of non-zero entries of the new system will be larger since $F'$ appears twice, but since we only enhance the existing solution, the optimal solution of the transformed situation still corresponds to the optimal solution of the original system.

• In the last step, we need to find the column for 1. Here we need to be careful that curve variables are treated the same on both sides, i.e. that $R$ appears twice in matrix $K$. We again transform the system, this time into

  \begin{bmatrix}
  F' & G' + H' & O_1' \\
  0 & E' & O_2'
  \end{bmatrix} =
  \begin{bmatrix}
  F & G + H & O_1 \\
  0 & E & O_2
  \end{bmatrix} \cdot
  \begin{bmatrix}
  A & B + C & Q \\
  0 & D & R \\
  0 & 0 & 1
  \end{bmatrix}.
  

  Note that the solutions to this system are the same as for the original system. We only need to find $O_1'$, $O_2'$, $Q$ and $R$. We can therefore again use the exact algorithm, using the columns we have already found as a basis. We can then transform it back to the original system.