Proper notion of execution trace in the code #808
Assignees
Comments
ledwards2225
added a commit
to AztecProtocol/aztec-packages
that referenced
this issue
Feb 21, 2024
Introduces an `ExecutionTrace` class responsible for translating raw
circuit data into the "execution trace polynomials", which I define as
the wire, selector and permutation argument polynomials (sigma/id). This
work was previously split across several different methods in the
Composers/ProverInstance and much of the logic was duplicated between
Plonk and Honk. That core logic is now shared across Plonk/Honk for all
flavors. It is encapsulated into a single call of the form
`Trace::generate(circuit, proving_key);` which takes the raw circuit
data contained in `circuit` and populates the provided `proving_key`
with wire, selector and sigma/id polynomials.
The main work of the `ExecutionTrace` is to "sort" the relatively
un-ordered raw circuit data. For example, for GUH, the ordering of the
execution trace is (1) zero row, (2) goblin ecc op gates, (3) public
inputs, and (4) conventional gates. Each one of these can be described
as an `ExecutionTraceBlock` which is a {`wires`, `selectors`} pair. E.g.
the conventional gates block is just the existing {`builder.wires`,
`builder.selectors`}. The public inputs block has all of its selectors
equal to zero, the first two wires equal to `builder.public_inputs`, and
the remaining wires identically zero. And so on. Eventually, each gate
type will have its own `ExecutionTraceBlock`. (I've rephrased the goblin
ecc op gates as an ExecutionTraceBlock as an example). These blocks are
constructed by the builder and "sorting" is achieved in `ExecutionTrace`
by simply arranging the blocks as desired then constructing polynomials.
From here, achieving a sorted execution trace should amount to
introducing one `ExecutionTraceBlock` for each gate type in the
builders, populating the appropriate block in each gate construction
function (instead of piling everything into a single `wires`,
`selectors`), then arranging those blocks to define the execution trace
polynomials in `ExecutionTrace`.
Closes AztecProtocol/barretenberg#808
Closes AztecProtocol/barretenberg#859
---------
Co-authored-by: ludamad <[email protected]>
AztecBot
pushed a commit
that referenced
this issue
Feb 22, 2024
Introduces an `ExecutionTrace` class responsible for translating raw
circuit data into the "execution trace polynomials", which I define as
the wire, selector and permutation argument polynomials (sigma/id). This
work was previously split across several different methods in the
Composers/ProverInstance and much of the logic was duplicated between
Plonk and Honk. That core logic is now shared across Plonk/Honk for all
flavors. It is encapsulated into a single call of the form
`Trace::generate(circuit, proving_key);` which takes the raw circuit
data contained in `circuit` and populates the provided `proving_key`
with wire, selector and sigma/id polynomials.
The main work of the `ExecutionTrace` is to "sort" the relatively
un-ordered raw circuit data. For example, for GUH, the ordering of the
execution trace is (1) zero row, (2) goblin ecc op gates, (3) public
inputs, and (4) conventional gates. Each one of these can be described
as an `ExecutionTraceBlock` which is a {`wires`, `selectors`} pair. E.g.
the conventional gates block is just the existing {`builder.wires`,
`builder.selectors`}. The public inputs block has all of its selectors
equal to zero, the first two wires equal to `builder.public_inputs`, and
the remaining wires identically zero. And so on. Eventually, each gate
type will have its own `ExecutionTraceBlock`. (I've rephrased the goblin
ecc op gates as an ExecutionTraceBlock as an example). These blocks are
constructed by the builder and "sorting" is achieved in `ExecutionTrace`
by simply arranging the blocks as desired then constructing polynomials.
From here, achieving a sorted execution trace should amount to
introducing one `ExecutionTraceBlock` for each gate type in the
builders, populating the appropriate block in each gate construction
function (instead of piling everything into a single `wires`,
`selectors`), then arranging those blocks to define the execution trace
polynomials in `ExecutionTrace`.
Closes #808
Closes #859
---------
Co-authored-by: ludamad <[email protected]>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
We often talk about the "execution trace" in a colloquial sense but it has no agreed upon definition, much less a well defined notion in the code. Introducing an execution trace object in the code may bring a lot of value and readability. ACIR format already has something approaching this in its construction of a circuit from grouped constraints. Note: this could possibly be connected to another useful refactor: distinguishing between a circuit builder and the circuit data, the latter being only the stuff needed by a composer to do its job.
The text was updated successfully, but these errors were encountered: