This is a series of articles. Part 5, PDF version
We went through many important modifications of the knowledge of polynomial protocol to make it general-purpose, so let us see how it is defined now. Assuming agreed upon function f(*) the result of computation of which is the subject of the proof, with the number of operations d, the number of variables n and corresponding to them coefficients
Note: using symbol ∏ allows for a concise way to express product of multiple elements, e.g.:
The set of all the variable polynomials {lᵢ(x), rᵢ(x), oᵢ(x)} for i ∈ {1, …, n} and the target polynomial t(x) is called a quadratic arithmetic program (QAP, introduced in [Gen+12]).
While the protocol is sufficiently robust to allow a general computation verification, there are two security considerations that must be addressed.
Non-Interchangeability of Operands and Output
Because we use the same α for all operands of variable polynomials restriction check there is nothing that prevents prover from:
- using variable polynomials from other operands, e.g., L′(s) = o₁(s) + r₁(s) + r₁(s) + …
- swapping operand polynomials completely, e.g., O(s) with L(s) will result in operation O(s) × R(s) = L(s)
- re-using same operand polynomials e.g., L(s) × L(s) = O(s)
This interchangeability means that the prover can alter the execution and effectively prove some other computation. The obvious way to prevent such behavior is to use different α-s for the different operands, concretely we modify:
It is now not possible to use variable polynomials from other operands since following α-s are not known to the prover:
Variable Consistency Across Operands
For any variable vᵢ we have to assign its value to a variable polynomial for each corresponding operand, i.e.:
Because the validity of each of the operand polynomials is checked separately, no enforcement requires to use same variable values in the corresponding variable polynomials. This means that the value of variable v₁ in left operand can differ from variable v₁ in the right operand or the output.
We can enforce equality of a variable value across operands through already familiar approach of restricting a polynomial (as we did with variable polynomials). If we can create a “shifted checksum” variable polynomial across all operands, that would restrain prover such that he can assign only same value. A verifier can combine polynomials for each variable into one, e.g.,
and shift it by some other random value β, i.e.,
This shifted polynomials are provided to the prover to assign values of the variables alongside with variable polynomials:
And the β is encrypted and added to the verification key gᵝ . Now, if the values of all vᵢ were the same, i.e.,
the equation shall hold:
While this is a useful consistency check, due to the non-negligible probability that at least two of l(s), r(s), o(s) could either have same evaluation value or one polynomial is divisible by another etc., this would allow the prover to factor values
such that at least two of them are non-equal but the equation holds, rendering the check ineffective:
For example, let us consider a single operation, where it is the case that l(x) = r(x). We will denote evaluation of those two as w = l(s) = r(s) and the y = o(s). The equation then will look as:
Hence such consistency strategy is not effective. A way to mitigate this is to use different β for each operand, ensuring that operand’s variable polynomials will have unpredictable values. Following are the protocol modifications:
Same variable values tempering technique will fail in such construction because different β-s makes the same polynomials incompatible for manipulation. There is however a flaw similar to the one in remark 4.1, concretely because the terms
are publicly available an adversary can modify the zero-index coefficient of any of the variable polynomials since it does not rely on s, i.e.,
Non-malleability of Variable and Variable Consistency Polynomials
Malleability of Variable Polynomials
Let us exemplify remark 4.1 with the following two operations:
The expected result is b = a and c = 3a, with clear relationship c = 3b. This implies that the left operand’s variable polynomial has evaluations lₐ(1) = 1 and lₐ(2) = 3. Regardless of the form of lₐ(x), a prover can unproportionately assign the value of a, by providing modified polynomial lₐ′(x) = alₐ(x) + 1. Therefore evaluations will be lₐ′(1) = a + 1 and lₐ′(2) = 3a + 1, hence the results b = a + 1 and c = 3a + 1 where c ≠ 3b, effectively meaning that the value of a is different for different operations.
Because the prover has access to
he can satisfy both the correct operand polynomials and variable values consistency checks:
Malleability of Variable Consistency Polynomials
Moreover the availability of
allows to use different values of same variable in different operands. For example, if we have an operation:
Which can be represented by the variable polynomials:
While the expected output is b = a², we can set different values of a, for example a = 2 (left operand), a = 5 (right operand) as following:
Such ability sabotages the soundness of proof. It is clear that encrypted β-s should not be available to a prover.
Non-Malleability
One way to address malleability is to make encrypted β-s from verification key incompatible with encrypted Z(s) by multiplying them in encrypted space by a random secret γ (gamma) during setup stage:
Consecutively such masked encryptions does not allow feasibility to modify encrypted Z(s) in a meaningful way since Z(s) is not a multiple of γ, e.g.,
Because a prover does not know the γ the alteration will be random. The modification requires us to balance the variable values consistency check equation in the protocol multiplying Z(s) by γ:
It is important to note that we exclude the case when variable polynomials are of 0-degree (e.g., l₁(x) = 1x⁰), which otherwise would allow to expose encryptions of β in variable consistency polynomials of proving key
in case when any two of operands / output is zero, e.g., for l₁(x) = 1, r₁(s) = 0, o₁(s) = 0 this will result in
We could also similarly mask the α-s to address the malleability of variable polynomials. However it is not necessary since any modification of a variable polynomial needs to be reflected in variable consistency polynomials which are not possible to modify.
Optimization of Variable Values Consistency Check
The variable values consistency check is effective now, but it adds 4 expensive pairing operations and 4 new terms to the verification key. The Pinocchio protocol [Par+13] uses a clever selection of the generators g for each operand ingraining the “shifts”:
Such randomization of the generators further adds to the security making variable polynomials malleability, described in remark 4.1, ineffective because for intended change it must be a multiple of either
raw or encrypted versions of which are not available (assuming, as stated previously that we’re not dealing with 0-degree variable polynomials which could expose encrypted versions).
The optimization makes verification key two elements smaller and eliminates two pairing operations from the verification step.
Note: there are further protocol improvements in the Jens Groth’s 2016 paper [Gro16].
References
[Par+13] — Bryan Parno, Craig Gentry, Jon Howell, and Mariana Raykova. Pinocchio: Nearly Practical Verifiable Computation. Cryptology ePrint Archive, Report 2013/279. https://eprint.iacr.org/2013/279. 2013.
[Gen+12] — Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic Span Programs and Succinct NIZKs without PCPs. Cryptology ePrint Archive, Report 2012/215. https://eprint.iacr.org/2012/215. 2012.
[Gro16] — Jens Groth. On the Size of Pairing-based Non-interactive Arguments. Cryptology ePrint Archive, Report 2016/260. https://eprint.iacr.org/2016/260. 2016.
