Why and How zk-SNARK Works 7: Constraints and Public Inputs

This is a series of articles. Part 6,​ ​ PDF version

Constraints

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

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:

Continue reading part 8

References