Improve explanation of hierarchical selector polynomials in Plonk book

[markulf]

We can consider that q_arith is hierarchically at a higher level. q_l, q_r, q_c, q_m, q_o, q_4 could be considered wire selectors in arithmetic gates, and auxiliary values in other custom gates. On the other hand q_arith, q_logic, ... are gate selectors which determine which gate is activated at any point in the circuit.

The explanation should be expanded.

_Originally posted by @davidnevadoc in https://github.com/ZK-Garage/plonk/pull/107#discussion_r796522298_

[bhgomes]

After speaking with @LukePearson1 and @lopeetall, we think that q_arith should actually be removed entirely. The arithmetic gate just represents all the terms which have one of the six basic selectors (one for each wire, a multiplication selector and a constant selector).

Hierarchical selectors only make sense whenever the multiplying term has some subterm with no selector for example Kobi's MIMC gate:

q_1 * (c - (a + b + q_2)^7)

But there's an advantage to not having a hierarchy like this, because then we can more readily take advantage of other gates. This could have also been written:

q_1 * (a + b + q_2)^7

And the c term would come from the arithmetic gate. Depending on the circuit, one may prefer either of these two techniques but either way, filling a gate type with every possible selector (and a global one) don't make sense:

q_1 * (q_2 * c - q_3 * (a + b + q_4)^7)

since we could have composed this gate out of the ones above.

The main idea is to find the smallest polynomials so that when added together we get the gates we want rather than constructing entire gates as their own polynomial. This clashes a bit with the per-gate separation challenges but I think those should be removed too and we can consider all the gates combined as one large gate with many possible terms. This is in line with the common mental representation of the PLONK circuit as a large matrix with one column per wire + selector and one witness constraint per row.

[mathcrypto]

If we don't use selector polynomials like q_arith we won't be able to either activate or deactivate a specific gate as the idea behind using those selectors was to use the gates associated to them only when needed.

[markulf]

What are the per-gate separation challenges and what does it mean to remove them?

My suspicion is that there is potentially a trade-off between optimal performance and modularity. I.e. while it is unlikely that one would use a MiMC gates without arithemetic gates, for more complicated gates this is not necessarily the case.

I might lift the difficulty of this issue to D-high, but maybe the Plonk book can describe more than one approach and help us in finding the correct design that we implement.

[bhgomes]

If we don't use selector polynomials like q_arith we won't be able to either activate or deactivate a specific gate as the idea behind using those selectors was to use the gates associated to them only when needed.

The q_arith selector is redundant, but q_range and others are not. I'm not suggesting to remove all the global selectors just q_arith and I'm explaining why it's redundant.

[mathcrypto]

If we don't use selector polynomials like q_arith we won't be able to either activate or deactivate a specific gate as the idea behind using those selectors was to use the gates associated to them only when needed.

The q_arith selector is redundant, but q_range and others are not. I'm not suggesting to remove all the global selectors just q_arith and I'm explaining why it's redundant.

Yes for only q_arith it makes sense to remove it.

[davidnevadoc]

I think q_arith could be removed but we would need to do some adjustments. Since some gates (like FIxedBaseScalarMul) use the selectors q_l, q_r and q_c we would now need to make sure that the arithmetic constraint still holds in each round. Assigning the proper value to q_o would be enough. I think we should come up with a good way of making these adjustments, otherwise we are complicating the implementation of custom gates that want to reuse the selectors used in the arithmetic constraints.

[bhgomes]

I think q_arith could be removed but we would need to do some adjustments. Since some gates (like FIxedBaseScalarMul) use the selectors q_l, q_r and q_c we would now need to make sure that the arithmetic constraint still holds in each round. Assigning the proper value to q_o would be enough.

I think we should come up with a good way of making these adjustments, otherwise we are complicating the implementation of custom gates that want to reuse the selectors used in the arithmetic constraints.

Actually, I think this is a semantic issue with the fixed-based scalar mul gate, since it is just using q_l, q_r, and q_o as "free columns" instead of defining its own selectors. They should probably have their own selectors, or we find a systematic way for gates to "share columns" efficiently. But yes, you're right, this does break if we get rid of q_arith.

This also affects the logic gate which uses the constant selector.