ECCVM prover optimizations

[iakovenkos]

• Commitment phase optimizations: ECCVM wires come from 3 different transcripts, and their sizes are generally bounded by the sizes of the corresponding transcripts. This could be used to reduce the commitment time.
• Sumcheck optimizations:
  • Several relations use the max upper bound on length instead of actual subrelations' lengths. E.g. TranscriptRelation, which has 25 subrelations. Now each subrelation length is set to 8, most of the subrelations are of lower degrees. Use shorter accumulators, re-use computed values, and so on.
  • Improve extend_edges logic: ideally, every entity is extended to the corresponding subrelation's length. This would save a lot of unnecessary ops. Although extend_edges is cheap on its own, if we are extending 100 entities to length 24 all the time, it translates into $24\times 100 \times$ circuit_size muls per sumcheck run. In the case of ECCVM it is more painful than in other flavors, because of the high degree in SetRelation (23), which is not needed in the most relations' subrelations. Measured this in a quck and dirty way on si/extend_edges_bench branch. Was able to shave 90ms off an CIVC bench. But was before Zac's skipping work
  • Investigate skipping: handled by @zac-williamson in feat: goblin Prover time is affected less by unused rows in circuit aztec-packages#14272
  • As a follow-up to Zac's work we can
  • • Commit to the witnesses in get_accumulators() using the fact that it's zero between num_transcript_rows and the last 4 rows
  • • z_perm can be computed more efficiently, as it stabilizes after the real circuit size, we're doing smth similar in Oink already. Additionally, can use commit_structured_with_nonzero_complement to reduce the commitment time
  • • Investigate log_derivative round optimizations. We shouldn't spend any time computing the derived witnesses at points that are skipped in the first round of Sumcheck.

[notnotraju]

This will be investigated once we decide on any other optimizations/restructuring to the ECCVM.