ACIR Arithmetic Expressions: How do selectors work?

General
1

CONTEXT
Take this simple multiplication circuit. We can run nargo prove p --print-acir just to print the ACIR opcodes, which are shown here:

BLACKBOX::RANGE [(_1, num_bits: 32)] [ ]
BLACKBOX::RANGE [(_2, num_bits: 32)] [ ]
BLACKBOX::RANGE [(_3, num_bits: 32)] [ ]
EXPR [ (1, _1, _2) (-1, _4) 0 ]
DIR::QUOTIENT (out : _%EXPR [ (1, _4, _4) 0 ]%,  (_6, %EXPR [ 2³² ]%), _5)
BLACKBOX::RANGE [(_5, num_bits: 32)] [ ]
BLACKBOX::RANGE [(_6, num_bits: 96)] [ ]
EXPR [ (-1, _4, _4) (-1, _14) 0 ]
EXPR [ (1, _5) (2³², _6) (1, _14) 0 ]
EXPR [ (1, _5, _5) (-1, _7) 0 ]
DIR::QUOTIENT (out : _%EXPR [ (1, _7, _7) 0 ]%,  (_9, %EXPR [ 2³² ]%), _8)
BLACKBOX::RANGE [(_8, num_bits: 32)] [ ]
BLACKBOX::RANGE [(_9, num_bits: 96)] [ ]
EXPR [ (-1, _7, _7) (-1, _16) 0 ]
EXPR [ (1, _8) (2³², _9) (1, _16) 0 ]
EXPR [ (-1, _3) (1, _8) (-1, _10) 0 ]
DIR::INVERT (_10, out: _11) 
EXPR [ (1, _10, _11) (-1, _12) 0 ]
EXPR [ (1, _10, _12) (-1, _10) 0 ]
EXPR [ (1, _12) 0 ]

We are attempting to translate these expressions into a standard plonk gate. What is already clear:

  • The first element (q) in a tuple represents the selector, and the “_” prefixed values are witness indexes.
  • (q, _l, _r) represents a multiplicative term, and (q, _x) represents a linear combination

QUESTIONS

  1. When q = 1, this denotes a selector toggled on, right?
  2. Does q = -1 denote a selector toggled off, such that the selector should be witnessed as 0? If not, how is q = -1 interpreted?
  3. Infrequently, we see q = 2³². How is this value interpreted as a selector?
53 Likes
2

Answered by @kevaundray in Noir Discord:

I’ll start off with something simpler than what you wrote. Lets say I want to prove the following:

5x + 6y == 1

We would only need to use an Expression/Arithmetic gate for this since there are no range constraints, or black box functions above. The first thing we need to do is make one side of the equation equal to zero because this is what our expression terms implicitly do.

5x + 6y == 1

Is then the same as:

5x + 6y -1 == 0

Now we can express this in terms of an ACIR Expression gate. It would be:

EXPR [(5, _1), (6, _2) -1 ]

Whether this has a 1-1 correspondence with selectors in PLONK depends on your PLONK system(ie how it represents arithmetic equations). In general, I would say yes though.

Standard PLONK
For standard plonk, you have one equation: q_M w_L w_R + q_L w_L + q_R w_R + q_O w_O + q_C

The above would translate into:

q_M = 0 
q_L = 5
w_L = 1
q_R = 6
w_R = 2
q_O = 0
w_O = 0
q_C = -1

Turbo Plonk
For TurboPlonk and a lot of other more complex plonk arithmetisations, you will also have selectors which toggle parts of the equation/gates off. So in TurboPlonk there is a q_Arith selector which is always 1 or 0. When its 1 it means we are doing an arithmetic constraint, and when its zero, we are doing another constraint. This is sort of implied by the fact that we are processing an ACIR Expression and not explicitly stated in the ACIR opcodes. We would not be able to do that because the IR aims to be generic over different plonk configurations and R1CS

54 Likes