Possible optimization in slice_adder_column

For computation of multi-variable length queries in circuits/src/keccak/multivar.rs, a significant part of the logic involves computation of the slice-adder matrix $S_k$. This matrix has $L_k$ rows and ${\sum }_i{L}_i$ columns. The values of $L_i$ are constants (known during circuit generation). There are also circuit variables $0\le {\ell }_i\le L_i$. The matrix $S_k$ is now defined as follows:

To make an example, let us consider the case where $L_0=2,L_1=3,L_2=4$ and we are considering $S_1$. Then, $o_1$ will satisfy $0\le o_1\le 2$. Should we have $o_1=0$ and ${\ell }_1=3$, then the matrix would look as follows:

If we had ${\ell }_1<3$, then only the first ${\ell }_1$ entries with $1$ in the above matrix (counting them from the top) would contain $1$, the rest would contain $0$ instead.

If instead we have $o_1=2$ and ${\ell }_1=3$, then the matrix would look as follows:

In general, the following matrix shows which entries could be either $0$ or $1$, depending on what the values of the ${\ell }_i$ are, marked by $?$.

Note that various entries are always zero. These come in three types:

1. Columns to the right

2. A triangle at the bottom left

3. A triangle at the top right (but left of the already mentioned columns)

In general, the entries of these three classes can be described as follows:

1. $j\ge {\sum }_{i=0}^k{L}_i$

2. $j-i<0$

3. $j-i>{\sum }_{i=0}^{k-1}{L}_i$ but not $j\ge {\sum }_{i=0}^k{L}_i$

Note that the following inequalities always hold:

Thus, $0\le o_k\le {\sum }_{i=0}^{k-1}{L}_i$. We can now show that the three types of entries above must always be zero:

1. As $0\le i<L_k$, the inequality $j\ge {\sum }_{i=0}^k{L}_i$ implies $j-i>{\sum }_{i=0}^{k-1}{L}_i=o_k$.

2. As $o_k\ge 0$, the inequality $j-i<0$ directly implies $j-i\ne o_k$.

3. If $j-i>{\sum }_{i=0}^{k-1}{L}_i$, then by definition $j-i>o_k$.

Instead of using constraints to calculate the matrix entries from their definition, it is more efficient to use the constant $0$ where the entry must be zero.

This optimization is done in the code for the first two types of entries that are always zero.

For the first type, this is handled by prepare_preimage and add_slice_at_offset as follows: prepare_preimage passes ${\sum }_{i=0}^k{L}_i$, as max_nonzero_position to add_slice_at_offset, and then add_slice_at_offset never calculates columns from max_nonzero_position forward.

For the second type, this is handled in slice_adder_column. This does not require any additional data; the entries with $i>j$ can directly be filled with the constant zero.

The optimization not yet implemented is the third type. This could be done as follows.

The prepare_preimage could, in addition to ${\sum }_{i=0}^k{L}_i$, also pass ${\sum }_{i=0}^{k-1}{L}_i$ to add_slice_at_offset, which then passes this value further to slice_adder_column, perhaps as an additional argument offset_max. Then those entries for which j > i + offset_max could be set to the constant zero rather than constraining their calculation from the definition.

The amount of constraints saved by this optimization would be similar to the constraints saved by the second optimization.