Reducing the number and sizes of batch_muls in Verifiers paired with Shplemini

[iakovenkos]

This issue concerns the method verify_proof() in ultra_recursive_verifier and the group operations performed there. Although these considerations could be useful for zeromorph, the main focus is on the Gemini+Shplonk multilinear PCS. See the reference point for Shplemini verifier.

There are 2 easy optimizations that could visibly reduce the number of gates in the recursive verifier circuits and decrease the number of group operations performed by the native verifier.

Optimization 1. Perform all group ops at the aggregation stage.

Currently,

• ShplonkVerifier performs 1 batch_mul in verify_gemini. It is of size NUM_ALL_ENTITIES + log_circuit_size + 1.
• PCS reduce_verify performs 1 batch_mul of size $3$ involving the result of the previous step
• agg_obj.aggregate performs 2 group ops, one of them involves the result of step 2.

Optimization:

All group ops are performed at the aggregation stage. Then we get

• 1 batch_mul of size NUM_ALL_ENTITIES + log_circuit_size + 1 + 1
• 1 group op (to aggregate $P_1$)

Numbers: $- 2 \times$ batch_mul calls results in 100 000 saved gates.

Optimization 2. Stop using extra group operations for "commitments" to shifted polynomials

Currently, commitments to shifted polynomials are a convenient abstraction, but they actually coincide with commitments to prover polynomials that are "shiftable"

Optimization:

Reorganize all_entities and the interface of our multilinear PCS such that:

• when claimed evaluations are formed it is of shape
  (evals of non-shiftable, evals of shiftable, evals of shifts of shiftable)
• Multilinear PCS accepts the vector of commitments that are sorted as follows
  (commitments to non-shiftable, commitments to shiftable)
  and the number of shiftable polynomials.

When we have this, ShplonkVerifier, would just add the scalars corresponding to the opening claims of shiftable polynomials and the scalars corresponding to the opening claims of their shifts. The scalar corresponding to the $i$th polynomial that is shiftable would then look as follows
$- \left( \frac{1}{z - r} + \nu \times \frac{1}{z + r} \right) \times \rho^i - \left( \frac{1}{r} \times \left( \frac{1}{z - r} - \nu \times \frac{1}{z + r} \right) \right) \times \rho^{i+k} $.

Numbers:

• Ultra Flavor has $9$ shiftable polynomials, therefore, the number of gates will drop by $\sim 45 000$.
• Mega Flavor has $24$ shiftable polynomials, the number of gates will drop by $\sim 120 000$.