Plonky3 -> PIL Compiler

[georgwiese]

In order to explore adding features of Powdr to existing zkVMs, it would be nice to be able to compile other systems to powdr. A good starting point for this would be a compiler from Plonky3 to PIL. This has already been implemented as a prototype, but on a fork of SP1, requiring a significant amount of changes to the code base. We can probably do it cleaner. It also contains some SP1-specific stuff, and it would be great to only rely on the Plonky3 API, which is also used by other systems.

A first version of this should be able to take an instance of a type that implements Plonky3's Air, like their Keccak implementation, and output PIL, without any modifications to Plonky3 or the Air.

Roughly speaking:

• We can call AirBuilder::eval, passing it a special AirBuilder which simply records the constraints.
• From there, we can compile to PIL, similar to the prototype below.

One unsolved problem is how to get the column names, because I don't see how we would have access to those (in the example, the AIR builder does not know about the KeccakCols struct at all). The prototype solves this by implementing a prog macro, with which the column struct needs to be annotated, but maybe there is a less intrusive solution. Anyway, column names are not essential for the first version (they can be just called col1, col2, ...).

Existing Prototype & Pointers

A prototype exists on a fork of SP1 on this branch (full diff).

To test:

$ cd examples/fibonacci/script
$ cargo run -r

A few pointers:

• I hacked the export of SP1 to PIL into the get_chips_and_costs function here:
  • For each chip, we call eval using the SymbolicAirBuilder to extract the constraints.
  • This air builder is then passed to get_pil, along with human-readable names for columns, public values, and the chip. This computes the PIL string that is then written to a file.
• The pil-air-builder crate provides SymbolicAirBuilder and get_pil:
  • crates/pil-air-builder/src/symbolic_builder.rs implements SymbolicAirBuilder. It implements the main AirBuilder trait that Airs call to add constraints, but also some extensions that add public values, preprocessed (=fixed) columns and bus interactions.
    • Most of this code (and the other files in the crate) where copied and adjusted from the Plonky3 repository.
  • crates/pil-air-builder/src/lib.rs implements get_pil.
• The new colums and columns_core crate implement a prog macro to automatically extract fields (nested) structs representing columns in the constraint system. This is so that we can preserve the column names when exported, which is nice for debugging, but not essential for the functionality. We could also explore other ways, like manually providing the list of column names, or generating names automatically. Also, most of the other changes in the diff are just going around all chips and using these crates.