Investigate how goblin operations affect ECCVM row counts

[lucasxia01]

We don't really understand where all the ECCVM rows are coming from. We made changes like adding pairing points and doing extra checks in the folding verifier recently and had to bump the ECCVM size, but how many rows does each operation add? who knows

[maramihali]

From Zac:

• an add or eq_and_reset adds 1 gate
• an MSM with N full-width scalar multipliers and M scalar multipliers that are <= 128 bits: 32 + 64*[(2N + M)/4] gates, where [(2N + M)/4] is rounded up to the nearest integer

@zac-williamson does this change at all with your incoming optimisations to ECCVM?

[ledwards2225]

@iakovenkos If you do an accounting of our ecc ops, it would be nice to validate that the formula above is consistent with what we're seeing.

[iakovenkos]

ECCVM num rows for a single msm of size $N$: $33*\lceil N/4 \rceil + 31$ for $N$ short random scalars $33*\lceil N/2 \rceil + 33$ for $N$ ful sized random scalars assuming no points at infinity and scalars == 0 or constant 1.

[notnotraju]

Here is an approximate computation which also reproduces the above.

We have the following static variables.

• NUM_SCALAR_BITS (in our case, $128$)
• NUM_WNAF_DIGIT_BITS (in our case, $4$)
• NUM_WNAF_DIGITS_PER_SCALAR = NUM_SCALAR_BITS / NUM_WNAF_DIGIT_BITS (in our case, $32$)
• ADDITIONS_PER_ROW (in our case, $4$)

The Straus algorithm proceeds as follows. Suppose we have $m$ non-trivial short scalar multiplications. Imagine we organize them by writing the wNAF digits horizontally; then each row in this imagined table corresponds to a distinct scalar multiplication. There are then NUM_WNAF_DIGITS_PER_SCALAR + 1 columns: the expansion itself has lengthNUM_WNAF_DIGITS_PER_SCALAR, but to express even numbers we need an extra skew bit.

We chunk each column into $\lceil \frac{m}{\texttt{ADDITIONS-PER-ROW}}\rceil$ pieces of length ADDITIONS_PER_ROW; these chunks populate (part of) a single row of the MSM table in the ECCVM. When we finish a column that is not either the 1s column or the skew column in our imaginary table, we have a row corresponding to the NUM_WNAF_DIGIT_BITS doublings. (This numerology works especially conveniently because NUM_WNAF_DIGIT_BITS == ADDITIONS_PER_ROW; so our row either toggles 4 point-additions or 4 doublings.)

This estimates the number of rows generated by $m$ short non-zero scalar multiplications as:

$$(\texttt{NUM-WNAF-DIGITS-PER-SCALAR + 1})\lceil \frac{m}{\texttt{ADDITIONS-PER-ROW}}\rceil + \texttt{NUM-WNAF-DIGITS-PER-SCALAR} - 1.$$

Happily, after the edit, this is exactly Sergei's computation .

[iakovenkos]

added tests that are confirming the formulas here https://github.com/AztecProtocol/aztec-packages/pull/16262