Suboptimal Instruction-Specific Constraints

[aszepieniec]

Upon skimming the result of cargo test print_number_and_degrees_of_transition_constraints_for_all_instructions -- --nocapture, 8 instructions stand out as having max degree 10 or 11. I am skeptical that these constraints must be so expensive. With the fancy technique that enabled pick and place, i.e., using an inner product with potentially shifted weight vectors, I am sure we can shrink these instructions' polynomials' degrees' maximum.

Instruction	#polys	max deg	Degrees
pop 1	16	10	[1, 1, 1, 1, 2, 2, 2, 2, 1, 5, 5, 10, 4, 1, 1, 1]
divine 1	16	10	[1, 1, 1, 1, 2, 2, 2, 2, 1, 5, 5, 10, 4, 1, 1, 1]
read_mem 1	30	10	[1, 1, 1, 1, 2, 2, 2, 2, 1, 5, 5, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 1, 1]
write_mem 1	30	10	[1, 1, 1, 1, 2, 2, 2, 2, 1, 5, 5, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 1, 1]
sponge_absorb	10	11	[1, 1, 1, 1, 1, 1, 11, 1, 1, 1]
sponge_squeeze	10	11	[1, 1, 1, 1, 1, 1, 11, 1, 1, 1]
read_io 1	16	10	[1, 1, 1, 1, 2, 2, 2, 2, 1, 5, 5, 10, 5, 4, 1, 1]
write_io 1	16	10	[1, 1, 1, 1, 2, 2, 2, 2, 1, 5, 5, 10, 5, 4, 1, 1]

[jan-ferdinand]

The degree-11 polynomial in sponge_absorb and sponge_squeeze comes from the permutation argument between the processor table and the op-stack table, which needs to account for 10 op-stack elements in a single instruction. I'm not aware of any technique to incorporate these factors using a polynomial of smaller degree.¹

Footnotes

1. I'm not counting generic degree-lowering techniques, which are already being applied, of course. 😌 ↩

[jan-ferdinand]

The degree-10 polynomials in all other instructions is also due to the permutation argument between the processor table and the op-stack table, altough the overall composition is a little different. Since all the instructions take an argument in range $1 \leqslant i \leqslant 5$, the concrete factor to absorb is being de-selected using the indicator polynomial, which is of degree 4. For argument $i$, the polynomial describing correct transition of the running product is of the form $\texttt{running\_product}' - \texttt{running\_product} \cdot \prod_{j=0}^{i}\texttt{factor}_i$ where $\texttt{factor}_i$ is of degree 1. For $i = 5$, this polynomial is of degree 6.

I don't know of a technique to reduce the degree of the the running-product part of the degree-10 polynomial. It might be possible to squeeze a degree or two out of the deselector polynomial, but I'd need to dig into it more. All in all, I'm not certain there are significant speedups to be had here.

[jan-ferdinand]

I'm closing this issue, as (to the best of my knowledge) the technique that enabled instructions pick and place is not applicable to reduce the degrees of the pointed-out high-degree polynomials, and because I'm not aware of any clever tricks to reduce the degrees.

[aszepieniec]

Summarizing a conversation @jan-ferdinand and I just had in the office:

• The high degree comes from modifying the op stack bus many times, once for each op stack pointer shift.
• The question is if the op stack table can't pre-pack and un-pack on the side of the op stack table, and then send packages over the bus so that the processor table does not have to spend a lot of constraints unpacking elements one by one.
• We came up with an intuition for a concept:
  • Extend the op stack table by two columns, a package-index, and a package-accumulator.
  • The package-index says where in the package to put (or take) the current element (from).
  • When the package-accumulator is done, it gets sent over the bus.
  • Two extra columns is almost certainly less extra columns than what we currently need to press the degree from 11 to 4.