Decouple publics from witness trace cell in Halo2

[qwang98]

After reviewing our Halo2 backend code, I noticed that we currently expose publics by copy-constraining trace cells in witness to public values in the single instance column using constrain_instance: https://github.com/powdr-labs/powdr/blob/main/backend/src/halo2/circuit_builder.rs#L483-L498.

To decouple publics from witness trace cell in Halo2, we would need to create witness columns (advice) in the Halo2 backend and:

1. Pass in public reference values to created advice columns via constraints in the form of advice_column.cur() - public_reference_value = 0
2. Copy constrain these advice columns to the instance column of publics.

I think @georgwiese mentioned that we additionally need to enforce that the witness column has the same value in all rows. I wonder if this is actually needed, since we can just pass in each public reference value to the first row of a created advice column? Another related question is why we needed a separate advice column for each public value? Is this because we don't know the degree of the circuit and therefore have to only put one value in each column?

Another thing I'm confused about is the "enforce_wrapping" constraint (https://github.com/powdr-labs/powdr/blob/main/backend/src/halo2/circuit_builder.rs#L267-L284). I wonder why this is needed?

[Schaeff]

I think @georgwiese mentioned that we additionally need to enforce that the witness column has the same value in all rows.

Isn't this already enforced by your advice_column.cur() - public_reference_value = 0 ?

Another thing I'm confused about is the "enforce_wrapping" constraint (https://github.com/powdr-labs/powdr/blob/main/backend/src/halo2/circuit_builder.rs#L267-L284). I wonder why this is needed?

On the lowest level, constraints are wrapping, which means that x' on the last row is x on the first row. However, in Halo2, the system uses the last few rows of the table to insert some blinding factors which are required for zero knowledge. Therefore, if our table has size N, we insert it inside a table of size 2 * N, where the second half is used for these blinding factors. However by doing that, we lose the wrapping behaviour, because x' on row N - 1 is not x on row 0, but x on row N. We re-introduce the wrapping behaviour using copy constraints, which is what enforce_wrapping does.

[georgwiese]

It's been a while, but my understanding of the Halo2 API is that there are special "instance columns" (which I think would be of a length equal to the number of publics and is a polynomial that's interpolated by the verifier) that has a cell for each public and can participate in copy constraints.

On the other hand, the Plonky3 API (which is what we want to adopt, see #1633) is that a public is just a scalar known at proof & verification time that can appear in any constraint.

To my knowledge, that's not supported in Halo2 (but please double-check!): Publics are always tied to specific instance column cells via copy constraints. Copy constraints only connect two cells, and which cells must be known at compile time.

To emulate this semantics in Halo2, one way would be to:

• Add one witness column per public (let's call it pub)
• Connect the first cell to the instance column via copy constraints
• Add a constraint like pub' = pub to make sure that the value is the same in all cells

This way, pub can be used in a constraint (it's just a column) and behaves like a scalar (it has the same value, no matter which row it is evaluated on).

Obviously, this is quite costly (commits to the value N times instead of once, adding a new column for each public), so if there is a better way, we should do this :) But it's also not prohibitive if we assume that the number of publics are fairly low compared to the number of columns we have anyways.

Pass in public reference values to created advice columns via constraints in the form of advice_column.cur() - public_reference_value = 0

I don't quite understand this. advice_column is what I called pub above, right? But what's public_reference_value? I needs to a variant of Halo2's Expression. The value is not known at compile time, so it can't be Constant. Challenge is kind of similar (it's a scalar different for each proof), but I think it would be tied to some hash. All the other terminals appear to be columns.

We re-introduce the wrapping behaviour using copy constraints

Actually, not anymore! I changed it to use rotations (which is cheaper) some time ago, see this code.