Implement codegen option for generic constraint evaluation format

[bobbinth]

The output of this codegen option should be a JSON file with the following structure:

{
    num_polys: integer,
    num_variables: integer,
    constants: [array of field elements in the Goldilocks field],
    expressions: [array of expression nodes],
    outputs: [array of node references],
}

In the above, node reference has the following structure:

{
  type: "POL | POL_NEXT | VAR | CONST | REF",
  index: integer,
}

Where:

• POL refers to the value in the column at the specified index in the current row.
• POL_NEXT refers to the value in the column at the specified index in the next row.
• VAR refers to a public input or a random value at the specified index.
• CONST refers to a constant at the specified index.
• REF refers to a previously defined expression at the specified index.

An expression has the following structure:

{
  op: "ADD | SUB | MUL",
  lhs: node_reference,
  rhs: node_reference, 
}

Where ADD, SUB, and MUL are the corresponding operations in the Goldilocks base field.

Code generation

To generate the code in the above format, we would need to do the following:

1. Merge main and auxiliary trace columns together into a single list of columns. For example, if we have 5 main trace columns and 2 aux trace columns, we should end up with with a list of either 9 or 11 columns, depending on the extension degree specified (i.e., 9 columns for quadratic extension and 11 columns for cubic extension). This also means that field extension degree should be an input parameter for this codegen option.
2. Flatten public inputs into a single array of values and merge it with random values array. This array will represent the variables array for the expressions.
3. Reduce all operations to the 3 supported operations in the base field. This also means that all operations over the extension field must be transformed into equivalent operations in the base field.

In addition to the above, we also need to add constraint merging logic to the constraint evaluation description. There should be only 3 entry points in the outputs section:

• One entry point to compute merged boundary constraints against the first step.
• One entry point to compute merged boundary constraints against the last step.
• One entry point to compute merged transition constraints.

The logic for merging transition constraints is described here and the logic for computing and merging boundary constraints is described here.

A few other things to consider:

• How to represent periodic columns? I am not yet sure if we can use constants or variables to represent them. We might have to introduce a new type of column in the top level.
• We might need to include a column which represents successive powers of the generator (i.e., $\omega^0, \omega^1, ..., \omega^{n-1}$). This might be implicit though.
• For merging columns, we will need to assume that extra randomness is provided by the verifier. These random values would be included in the variables section. We also may need to add degree adjust factors to the variables array as well.

Implementation approach

It would probably make senes to split implementation of this into several steps. The first step should probably not involve constraint merging and should have one output for each boundary and transition constraint. Only after this is working, we should implement constraint merging.

[grjte]

@bobbinth is EXP_REF correct here or should it just be REF?

[bobbinth]

Should be just REF. Updated!

[bobbinth]

Although, I wonder if just EXP (or EXPR) is better than REF. All of these are references (whether we are referencing a constant or a variable or a polynomial) - so, it might make sense to change REF to EXPR to make it clear that this is an expression reference.

[grjte]

I prefer EXPR over EXP if we're making the change, since EXP looks like exponent instead of expression, but I think I probably prefer REF (although it's a very mild preference).