aztec-packages icon indicating copy to clipboard operation
aztec-packages copied to clipboard

feat: goblin Prover time is affected less by unused rows in circuit

Open zac-williamson opened this issue 8 months ago • 0 comments

The ECCVM and Translator circuits previously did not have an ability to skip Prover computation for rows in the execution trace that were known to be empty.

This is a problem because in Aztec, the ECCVM circuit has a fixed (large) size of 2^17 rows and a typical transaction uses a small fraction of the execution trace. The same applies for the Translator circuit

This PR makes the following changes to uncouple ECCVM/Translator prover time from the total number of rows:

  • Added a new method skip_row to ECCVMFlavor and TranslatorFlavor, which is called during the sumcheck protocol.
  • skip_row is used by sumcheck_round to split the execution trace into contiguous blocks of active rows. Accumulations only happen over these rows, and multithreading is accurately split over the number of active rows (not the number of total rows)
  • compute_logderivative_inverse is now multithreaded
  • ECCVM algebra slightly modified to ensure that a row with no operations in it is fully zeroed-out across all columns

The latter point is useful because previously there were 3 columns in the ECCVM that were nonzero across the entire trace, contributing to commitment time. Additionally as a heuristic it is helpful to know that an empty row implies "do nothing"

As a consequence of these changes, an empty row in the ECCVM now sets the ECCVM accumulator to the point at infinity (previously the previous row's accumulator value was propagated in a no-op). This will be helpful in the future to enable us to concatenate multiple ECCVM operations that come from independent untrusted sources (i.e. concatenation should introduce a single-row gap between ECCVM opcode blocks that come from different sources)

When ./scripts/benchmark_client_ivc.sh was run - proving the ECCVM took:

ECCVM size Master Branch Time This Branch Time
2^16 2,639ms 1,829ms
2^17 4,357ms 2,383ms

Additionally this Pr solves issue #2217

zac-williamson avatar May 13 '25 16:05 zac-williamson