Fully support intermediate columns

[georgwiese]

Intermediate columns are just algebraic expressions, but they are not in-lined by the condenser. We've always had them, but usually access them via Analyzed::identities_with_inlined_intermediate_polynomials, so they actually end up being the same as an expression in PIL. I think we should stop doing that and eventually remove the function. There are 2 major use-cases:

Inlined expressions can be exponentially large

In cases where the same sub-expression is repeated many times, extracting that into an intermediate polynomial can reduce the size of the expression exponentially:

• See a simple pathological example in Support intermediate polynomials in p3 #1995
• A practical example is the fingerprint function, which repeats many intermediate result many times. In Improve fingerprint expression performance. #1985, we have significantly reduced the size of the resulting expression, but it is still exponentially large. With intermediate columns, we could have $O(n)$ intermediate polynomials.

All constraints need to be evaluated:

• By witness generation in every row of the trace (to solve for the witness)
• By the prover at every point of the quotient domain (e.g. twice the number of rows of the trace), to compute the quotient polynomial
• By the verifier at a random point

Hence, having an efficient algorithm to evaluate a polynomial constraint benefits all three steps.

Next steps:

• Repeat Support intermediate polynomials in p3 #1995 for other backends as well, so none of them uses identities_with_inlined_intermediate_polynomials.
• Handle intermediate polynomials in witgen. [WIP] Witgen: Handle intermediate polynomials #2007 is a prototype and seems to work well!
• Yield intermediate columns in PIL functions like fingerprint, which should dramatically reduce the verbosity of the generated expressions and enable efficient witgen, proving, and verification.

Intermediate polynomials can be turned into witness polynomials to reduce the constraint degree

A good example is Poseidon: Since it is an algebraic hash function, each output can be directly expressed as a very nested (and high-degree) algebraic expression of the inputs. The only reason we'd commit to any intermediate results would be to reduce the degree of the constraints.

Currently, we explicitly introduce witness columns to keep the degree low. That's not great for two reasons:

• The degree bound depends on the backend, and we want the Poseidon implementation to not depend on the backend.
• Even if we know the degree bound when writing the machine, we're likely not making optimal choices on which column to materialize, see this comment.

Next steps:

• Polynomials should be automatically broken to the maximum supported degree. #1971: When writing machines, we could always use intermediate columns and find a way to automatically turn them into witness columns as needed
• Implement a way to derive values for intermediate-turned-witness columns from the witness provided by witgen (so that witgen remains independent of the backend)