This came up in the Reth benchmarks. Without this our basic blocks
collection fails to see these extension branch instructions. These don't
come up in the ELF file because they're extensions.
With this PR, we don't allocate PlonK gates to compute the same
expression twice anymore, and instead just re-use the existing variable.
I also couldn't resist to refactor the code: Rather than adding yet
another `&mut ...` to `air_to_plonkish`, I introduced a
`CircuitBuilder`. I recommend reviewing this code with the "Hide
whitespace" setting, as most line changes are due to existing code being
indented differently.
Reduces the number of gates for Keccak from 21747 to 11466, as printed
by:
`RUST_LOG=powdr_openvm::powdr_extension::plonk=debug cargo test -r
keccak_plonk_small_prove_mock -- --nocapture`
Building on #2787, this PR adds an option to compile a precompile into a
PlonK circuit. It also adds tests, which are currently marked as
`should_fail`, because we don't implement bus interactions yet and
therefore have an imbalanced bus.
Example:
```
$ RUST_LOG=powdr_openvm::powdr_extension::plonk::chip=debug cargo test -r keccak_plonk_small_prove_mock -- --nocapture
...
Generating air proof input for PlonkChip PowdrAutoprecompile_0
Number of calls: 240
Plonk gates: 10124
Trace width: 8
Trace height: 4194304
...
LogUp multiset equality check failed.
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
test tests::keccak_plonk_small_prove_mock - should panic ... ok
```
This PR implements everything needed for the `PlonkChip` to actually
implement validating the algebraic constraints (no bus interactions
yet):
- I changed the implementation to assert zero, see comment below.
- Added a `build_circuit` function that takes a list of constraints,
rather than a single constraint.
- The chip now calls this function, passing the algebraic constraints.
- Some fixes in the PlonK witness generation, see comment below.
With this PR, none of this code is run yet, but #2788 does run it and
adds tests.
Builds on #2765 (already approved)
Implements a basic algorithm for PlonK witness generation.
Has a lot of TODOs and the code isn't actually run yet, but I'd suggest
to merge it already and iterate on that.
The general algorithm is:
- Call `Executor::generate_witness()` to get all the values of the
variables in the original constraint systems (= what would have been
trace cells in `PowdrChip`)
- For each call:
- For each gate:
- Set the selector columns (which are currently witness columns, should
eventually be preprocessed columns)
- Solve for temporary variables on the fly, assuming that there is at
most unknown when processing gates in order
- Set the witness columns (`a`, `b`, `c`), with their values either
coming from the result of `Executor::generate_witness()` or a temporary
variable.
Current plonk compiler transfer an air expression to plonk gate, but it
doesn't evaluate the expression.
for example:
`a * b * c = 0`
it will compile it to
```
a * b = temp0
temp0 * c = temp1
```
This PR set the last gate output, which is the output of the expression
(temp1 in the above example) to be zero
---------
Co-authored-by: Georg Wiese <georgwiese@gmail.com>
- Following the insight by @georgwiese that `eval` is actually not
called many times, this PR changes `PowdrAir` to store the AST nodes
based on `AlgebraicExpression` (as opposed to openvm
SymbolicExpression).
- During trace generation, we do work on each row of the table, which
currently includes some table lookups in the table of airs. Move as much
as possible out of the part which runs for each row, saving map lookups.
- Avoid collecting into a vector when processing bus interactions
Continuing #2733, this PR moves most of
`PowdrChip::generate_air_proof_input` into the `Executor`. As a result,
it is more encapsulated (all its fields are private now), and the
interface is such that we should be able to use it in the `PlonkChip` as
well: `Executor::generate_witness` returns a matrix of all variable
values, for each call to the APC. In the `PowdrChip`, this is the
witness directly; in the `PlonkChip`, we can compute the witness from
this matrix.
This PR *mostly* moves code. I would prefer to leave any bigger changes
to a different PR, so that it doesn't get too entangled.
Reduces the number of the `openvm` crate from 550 to 377.
(measured by `cargo tree --edges=normal -q | sed 's/.*── //' | cut -d' '
-f1 | sort -u | wc -l`.)
We no longer create the root proof and the last Halo2 proof that can be
verified on chain. These proofs tend to take a long time that is largely
independent of the statement being proven (and with which chips), so it
just adds a constant overhead.
To test, run this from the `cli-openvm`:
```
$ RUST_LOG=powdr_openvm=info cargo run -r prove $(pwd)/../openvm/guest-keccak --autoprecompiles 1 --pgo --input 10 --recursion
...
INFO ｉ [info]: Generating app proof...
INFO ｉ [info]: App proof took 1.378542917s
INFO ｉ [info]: Public values: [155, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
INFO ｉ [info]: App proof verification done.
INFO ｉ [info]: Generating aggregation proving key...
INFO ｉ [info]: Generating aggregation proof...
INFO ｉ [info]: Agg proof (inner recursion) took 22.166544083s
INFO ｉ [info]: All done.
```
The goal here is to make more explicit which powdr crates are needed for
powdr-openvm.
After this PR, next concrete steps are:
- Extract the elf stuff from powdr-riscv into another crate so that this
new crate can be used by powdr-openvm instead of powdr-riscv, since that
one has tons of other dependencies
- constraint-solver only depends on powdr-number which is great!
- powdr-autoprecompiles depends on a bunch of other powdr crates.
Ideally we'd eventually be able to remove from the dep list: ast,
parser, parser-util, pil-analyzer, pilopt
Extracts (one of the two...) `PowdrExecutor` into its own file. I just
moved the code (the only change is that I made the fields public for
now, to minimize code change).
I think the next steps should be:
- Make it do most of what `generate_air_proof_input` does as well
- Refactor (so the behavior is more encapsulated)
- Re-use it for witness generation of the PlonK chip
This bug was both a soundness bug and a performance bug, leading to
fewer columns being removed (although also too many bus interactions
being removed, see below).
This PR is an alternative to #2721, also fixing the regression of #2717.
It actually leads to benefits beyond that.
The idea is to only keep columns that are connected to *stateful* bus
interactions (i.e., memory and the execution bridge), because this is
the only way to affect the state of the VM. This is actually a special
case of the `remove_trivial_bus_interactions` step (trivial bus
interactions are connected to no columns, and therefore removed), so I
removed that (and simplified the `ConcreteBusInteractionHandler`).
[This](https://gist.github.com/georgwiese/56d768e86bbf6def28260ca92f0b5180)
is a diff of the generated PIL of the Keccak APC. I spot-checked a few
instances of removed columns and there were often columns that were
range-checked but otherwise un-constrained.
Based on commit 1dbe4db
- Split into two crates, lib and cli
- upgrade stwo, marked one stwo test `should_panic` @ShuangWu121
- various clippy and fmt fixes linked to the rust version update
- bring all rust versions to 2025-05-14. CI still installs other
versions for openvm which uses them internally. The stable rust version
we test on is bumped to 1.85
- remove `examples` and related tests, which test the powdr crate on the
previous version of powdr (since it uses another nightly). Happy to
discuss this if it's important @leonardoalt
