This is a series of articles. Part 6, PDF version
Constraints
Our analysis has been primarily focusing on the notion of operation. However, the protocol is not actually “computing” but rather is checking that the output value is the correct result of an operation for the operand’s values. That is why it is called a constraint, i.e., a verifier is constraining a prover to provide valid values for the predefined “program” no matter what are they. A multitude of constraints is called a constraint system (in our case it is a rank 1 constraint system or R1CS).
Note: This implies that one way to find all correct solutions is to perform a brute-force of all possible combinations of values and select only ones that satisfy the constraints, or use more sophisticated techniques of constraint satisfaction [con18].
Therefore we can also use constraints to ensure other relationships. For example, if we want to make sure that the value of the variable a can only be 0 or 1 (i.e., binary), we can do it with the simple constraint:
We can also constrain a to only be 2:
A more complex example is ensuring that number a is a 4-bit number (also called nibble), in other words it is possible to represent a with 4 bits. We can also call it “ensuring number range” since a 4-bit number can represent 2⁴ combinations, therefore 16 numbers in the range from 0 to 15. In the decimal number system any number can be represented as a sum of powers of the base 10 (as the number of fingers on our hands) with corresponding coefficients, for example, 123 = 1 ⋅ 10² + 2 ⋅ 10¹ + 3 ⋅ 10⁰. Similarly a binary number can be represented as a sum of powers of base 2 with corresponding coefficients, for example, 1011 (binary) = 1 ⋅ 2³ + 0 ⋅ 2² + 1 ⋅ 2¹ + 1 ⋅ 2⁰ = 11 (decimal).
Therefore if a is a 4-bit number, then a = b₃ ⋅ 2³ + b₂ ⋅ 2² + b₁ ⋅ 2¹ + b₀ ⋅ 2⁰ for some boolean b₃, b₂, b₁, b₀. The constraint can be following:
and to ensure that b₃, b₂, b₁, b₀ can only be binary we need to add:
Quite sophisticated constraints can be applied this way, ensuring that the values used are complying with the rules. It is important to note that the above constraint 1 is not possible in the current operation’s construction:
Because the value 1 (and 2 from the previous constraint) has to be expressed through
where c can be ingrained into the proving key, but the v may have any value because the prover supplies it. While we can enforce the c ⋅ v_one to be 0 by setting c = 0, it is hard to find a constraint to enforce v_one to be 1 in the construction we are limited by. Therefore there should be a way for a verifier to set the value of v_one.
Public Inputs and One
The proofs would have limited usability if it were not possible to check them against the verifier’s inputs, e.g., knowing that the prover has multiplied two values without knowing what was the result and/or values. While it is possible to “hardwire” the values to check against (e.g., the result of multiplication must always be 12) in the proving key, this would require to generate separate pair of keys for each desired “verifier’s input.”
Therefore it would be universal if the verifier could specify some of the values (inputs or/and outputs) for the computation, including the v_one, instead of the prover.
First, let us consider the proof values
Because we are using the homomorphic encryption it is possible to augment these values, for example, we can add another encrypted polynomial evaluation
which means that the verifier could add other variable polynomials to the already provided ones. Therefore if we could exclude necessary variable polynomials from the ones available to the prover, the verifier would be able to set his values on those variables, while the computation check should still match.
It is easy to achieve since the verifier is already constraining the prover in the choice of polynomials he can use empolying the α-shift. Therefore those variable polynomials can be moved from the proving key to the verification key while eliminating its α-s and β checksum counterparts.
The necessary protocol update:
Note: following from the protocol properties (Single-Variable Operand Polynomials section) the value 1 represented by polynomials l₀(x),r₀(x),o₀(x) already have appropriate values at the corresponding operations and therefore needs no assignment.
Note: verifier will have to do extra work on the verification step, which is proportionate to the number of variables he assigns.
Effectively this is taking some variables from the prover into the hands of verifier while still preserving the balance of the equation. Therefore the valid operations check should still hold, but only if the prover has used the same values that the verifier used for his input.
The value of 1 is essential and allows to derive any number (from the chosen finite field) through multiplication by a constant term, for example, to multiply a by 123:
References
[con18] — Wikipedia contributors. Constraint satisfaction. Wikipedia, The Free Encyclopedia. 2018.
