Simplified second-Spartan-sum-check (via simpler uniform R1CS product-vector MLE)

[arasuarun]

Making a note of a new optimization for Spartan applied to Jolt's R1CS recently suggested by Justin. It would involve simple changes to the A, B, C mle evaluations and the inner (second) sumcheck for the prover, and mle evaluation for the verifier.

Context: the three constraint matrices A, B, C are all in block-diagonal form as there are ~60 constraints and ~80 variables of z per RISC-V cycle. A boolean vector representing a row in this big matrix can be split into two components as $r = r_{small} \parallel r_{big}$ where $r_{small}$ denotes the constraint (from the small matrix) and $r_{big}$ denotes the step counter. A column can be split $y = y_{small} \parallel y_{big}$ where $y_{small}$ denotes the variable (from the small matrix) and $y_{big}$ is again the step counter. Currently, the uniformity of the R1CS is exploited as follows. Let $NC$ be the number of columns in the big matrix.

$(A * z)[r] = \sum\limits_{j_{small} \parallel j_{big} \in \{ 0,1 \} ^{\log(NC)}} A_{small}(r_{small}, j_{small}) * eq(r_{big}, j_{big}) * z(j)$,

and similarly for $(Bz)[r]$ and $(Cz)[r]$.

To prepare to apply sum-check to compute (a random linear combination of) the above three sums, the prover first evaluates the mles of A, B and C at all points of the form $(r, y)$ where $y$ ranges over $\{0, 1\} ^{\log(NC)}$, as: $A(r, y) = \sum\limits_{j} A_{small}(r_{small}, y_{small}) * eq(r_{big}, y_{big})$. Once these values are all computed, the prover is ready to call the second sumcheck through the function prove_spartan_quadratic.

It turns out there is an even simpler way to express $(A * z)$. There's no reason to sum over $j_{big}$ at all. We can simple write:

$(A * z)][r] = \sum\limits_{j_{small}} A_{small}(r_{small}, j_{small}) * z(j_{small} \parallel r_{big})$.

This means that the second sumcheck can just iterate over the variables in y_small which is a constant independent of the program length. And to run the second sum-check, the prover just needs to evaluate the mle of A, B, C at each point $y_{small} \parallel r_{big}$ as $A(r, y_{small} \parallel r_{big}) = \sum\limits_{j_{small}} A_{small}(r_{small}, y_{small})$.