Trace sorting: Undo interleaved gate optimizations #873
Assignees
Milestone
Comments
AztecBot
pushed a commit
that referenced
this issue
Mar 20, 2024
This work results in an execution trace fully sorted by gate type.
Prior to this PR, all of the infrastructure was added to construct and
process a sorted execution trace. Each builder has a `blocks` object
which essentially holds a {`wires`, `selectors`} pair for each gate
type. Up until now, all gates were being added into `blocks.main`, which
is equivalent to what we've always done. This PR simply adds gates into
their appropriate specialized block, e.g. arithmetic gates are added
into `blocks.arithmetic` and auxiliary gates are added into
`blocks.aux`. After being processed in the `ExecutionTrace` class, this
results in an execution trace sorted by gate type.
Note: This PR adds dummy gates in several new locations to account for
the fact that some gates of a particular type were previously reading
into a subsequent gate of different type, which breaks once the gates
are sorted by type.
Note: This PR does not include any logic for taking advantage of the
sorted structure.
Closes #867 (gates
are sorted)
Closes #873 (no more
gate interleaving assumptions, except ones now identified in more
specific issues)
Closes #910 (gate
type summary via blocks.summarize())
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
There are several operations in the ultra builder that rely on interleaving gate types and/or simultaneous use of different gates which prevents a full sorting by type. Examples of simultaneous gate types include:
create_sort_constraint_with_edgeswhich results in a series ofsortgates for which the first and last are simultaneouslyarithmeticgatesRAM_CONSISTENCY_CHECKwhich is simultaneously anauxgate and anarithmeticgateExamples of assumed gate adjacency include:
create_final_sorted_RAM_gate) is an arithmetic gate. (Need to add a dummy for the "next row" read and separate the addition gate needed for a consistency check)The text was updated successfully, but these errors were encountered: