what does field STATE_WIDTH and CAN_ACCESS_NEXT_TRACE_STEP mean of PlonkConstraintSystemParams?

[DreamWuGit]

in latest better_better_cs module, PlonkConstraintSystemParams as follow:
pub trait PlonkConstraintSystemParams<E: Engine>: Sized + Copy + Clone + Send + Sync {
const STATE_WIDTH: usize;
const WITNESS_WIDTH: usize;
const HAS_WITNESS_POLYNOMIALS: bool;
const HAS_CUSTOM_GATES: bool;
const CAN_ACCESS_NEXT_TRACE_STEP: bool;
}

here what does field STATE_WIDTH and CAN_ACCESS_NEXT_TRACE_STEP mean?
and what is difference between STATE_WIDTH and WITNESS_WIDTH? looks confusing .
Can anybody explain ?

Thanks in advance !

[shamatar]

I should answer you tomorrow when back to the laptop with a normal keyboard :)

[shamatar]

Ok, so:

• STATE_WIDTH is a number of polynomials for which a copy-permutation check applies. In the original Plonk paper there are 3 of them, in our case there are usually 4 of them because it has marginal cost in a prover, but allows to have smaller circuits. To look at it another way - when you allocate values here you can use a term of "variable" that is unique in a circuit and always has provably the same value (much like in a Groth16)
• WITNESS_WIDTH is currently 0, but represents a number of additional polynomials that you can address through some gate (will give an example below). E.g in Halo2 those are called "advice" polynomials
• CAN_ACCESS_NEXT_TRACE_STEP - determines if any relation in the circuit (usually we call such relationships "gates") can access only current row of the trace or may be also next row of the trace. In the original Plonk paper gate has a form (up to coefficients) A * B + A + B + C + constant = 0, where capitals are state polynomials' names, and touches only a single row of the trace. In our work we use a modified version of the "main" gate as A * B + A + B + C + D + D_on_the_next_row + constant = 0 that allows to better chain long linear combinations (D_on_the_next_row is like a carry). If you would want you could introduce an additional gate (that we call "custom" gates) like A * WITNESS_0 = 1, that proves that A !=0, but an WITNESS_0 is not used for anything else, so it's placed in a WITNESS type polynomials

[DreamWuGit]

originally I understand witness as (A,B,C,D) columns values, STATE_WIDTH is equal to number of such columns, but in your comment, the "witness" meaning transformed, which is dedicated using for custom gate. the new STATE_WIDTH represents my old understanding witness.
So，in the modified version gate as A * B + A + B + C + D + D_on_the_next_row + constant = 0, the D_on_the_next_row represents single filed element .
i.e. there are two consecutive gates:
gate1: a1+b1 + c1 + D_on_the_next_row = 0
gate2: a2+ b2 + c2 =0
D_on_the_next_row can be any one of (a2,b2,c2) I think . therefore, the order of gate (row ) is important as original plonk paper describes, while halo2 mitigate this for offset reference in the whole table .

Correct me if wrong !

Thanks for discussion!

[shamatar]

Your understanding of witness is correct, it's just that I've used another naming.

"Witness" in my terms is not used anywhere yet, but it can be used e.g. to make custom affine transform + non-linearity gate for Poseidon hash like the following: A + B + C = W_0; W_0 ^4 = W_1; W_0 * W_1 = D. Effectively we get that D = (A + B + C)^5 and it's what we want, but used extra witness/advice columns (that are effectively discarded) for some extra bookkeeping and to have a degree of the constraints low (this example is quite artificial, but should give you a hint).

Halo2 uses other types of gates that allow one to access values in the previous and next rows as far as I remember, but with Plonk you can design many relationships using both relative or absolute row addressing.

Regarding D_on_next_row: you can do like this a1 + b1 + c1 + d1 + const - d2 = 0, -a2 + b2 + c2 + d2 = 0, effectively making a long linear combination into a2 (I've zeroed a coefficient for D_next in the row number 2)

[DreamWuGit]

more clear to your designing motivation, as D_next imported requires a new polynomial over D_next vectors in prove & verify procedure I think, D_next also reduce number of gates for the same arithmetic computation as well .

also, about HAS_CUSTOM_GATES flag, how to determine if there is an actual custom gate or how to make a custom gate underling in other words ?

[shamatar]

Yes, such gate requires an extra polynomial in setup (coefficients in front of D_next), but this is also not too large price because it's amortized by linearization

[DreamWuGit]

yeah, is there any custom gate example helping understanding "HAS_CUSTOM_GATES" flag, Thanks !

[shamatar]

Here is an example how to define a custom gate that does 5th degree non-linearity https://github.com/matter-labs/franklin-crypto/blob/770156e665d2d866f080e241876b358136ccc9f1/src/plonk/circuit/custom_rescue_gate.rs#L31

[DreamWuGit]

Got , will take a look!