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.
  • Investigate skipping: right now, the relations are quite chunky, and producing a skipping condition in, say, TranscriptRelation, leads to a system of linear equations that has no solutions.