Delay provision of degree ranges

[Schaeff]

Context

When generating a proof, the prover must have access to a commitment to the fixed columns in the size of the execution trace. These commitments are generated during a setup phase by providing static sizes. This requires the user to know how long the execution trace is going to be ahead of time.

In ASM, these sizes must currently be provided either in the declaration of the machines, or in the instantiation of submachines.
In PIL, they are defined in each namespace statement.

The issue with this is that we end up with a lot of code in the machines to deal with the sizes. This code could be made more ergonomic, but this issue describes another proposal.

Idea

The current flow is:

asm -> pil -> fixgen -> witgen -> setup -> prove

fixgen requires the static sizes which the trace is expected to have.

The idea is to delay fixgen as late as possible and split the flow into two stages

[ asm -> pil -> witgen ] -> [ fixgen -> setup -> prove ]
        run                        deploy(degrees)

This way, we only need to specify the degrees in the deploy phase. An idea for this would be something like a configuration file, similar to choosing an architecture to run a program on.

Impact

• We do not need to deal with runtime degrees inside the source code anymore. We may still want to introduce logic degree ranges, which make sure that lookup tables fit in the execution trace, or that counters do not overflow. In the edge case of a fixed sized machine which is common for fixed lookups, the runtime degree could be inferred from the logic degree.
• Witgen must be changed to work without materialised fixed columns. While it currently starts from the largest possible trace (based on the available fixed column sizes) and downsizes to the smallest value at the end of execution, it would probably need to instead start from 0 and extend as the trace grows. In order to avoid having to backtrack as fixed columns get updated to a larger size, the update would happen a few rows before a power of two is reached. Whether the columns would need to be materialised in memory or if computing the closed form is enough an open question.
• The format of the degrees to pass to the deployment phase and whether they could be pre-filled is an open question.

[chriseth]

For most purposes, it probably also suffices to have fixed columns not in column form but as an abstract pil expression. I think this is the interface we need:

• check if the fixed column is cyclic and return the period
• evaluate the fixed column at a certain row (if the value is not the same for all lengths of the fixed column, return an error)
• evaluate the fixed column at a certain row, given a certain column size