barretenberg icon indicating copy to clipboard operation
barretenberg copied to clipboard

Trace sorting: Avoid use of q_arith in aux gate selector configuration

Open ledwards2225 opened this issue 11 months ago • 0 comments

Various subrelations in the Auxiliary relation are triggered by combinations of (non-gate) selectors, e.g. q_m, q_2. The RAM_CONSISTENCY_CHECK subrelation is triggered via q_arith which is a gate selector. This means that we sometimes have simultaneously q_aux == q_arith == 1. This was done to avoid raising the degree of the relation (which would have had more serious ramifications for Plonk due to the zero-check approach).

This simultaneous selector issue is an obstacle for allowing each block to only track a single selector, and certainly for representing selectors as ranges instead of polynomials. One solution is to simply replace the use of q_arith with q_m * q_4 (for example). This raises the degree but may be a worthwhile tradeoff.

Note: The choice of q_arith is arbitrary; the arithmetic relation is trivially satisfied for the RAM_CONSISTENCY_CHECK since the wire scaling selectors q_1, q_2 etc are all zero. In other words, using q_m * q_4 instead does not result in the loss of any constraint.

ledwards2225 avatar Mar 18 '24 18:03 ledwards2225