Why and How zk-SNARK Works 6: Verifiable Computation Protocol

Maksym
Maksym
Apr 19, 2019 · 8 min read

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

Image for post
Image for post
Image for post
Image for post

Note: using symbol ∏ allows for a concise way to express product of multiple elements, e.g.:

Image for post
Image for post

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

  • 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:

Image for post
Image for post

It is now not possible to use variable polynomials from other operands since following α-s are not known to the prover:

Image for post
Image for post

Variable Consistency Across Operands

Image for post
Image for post

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.,

Image for post
Image for post

and shift it by some other random value β, i.e.,

Image for post
Image for post

This shifted polynomials are provided to the prover to assign values of the variables alongside with variable polynomials:

Image for post
Image for post

And the ​ β is encrypted and added to the verification key gᵝ . Now, if the values of all vᵢ were the same, i.e.,

Image for post
Image for post

the equation shall hold:

Image for post
Image for post

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

Image for post
Image for post

such that at least two of them are non-equal but the equation holds, rendering the check ineffective:

Image for post
Image for post

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:

Image for post
Image for post
Image for post
Image for post

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:

Image for post
Image for post

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

Image for post
Image for post

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.,

Image for post
Image for post

Non-malleability of Variable and Variable Consistency Polynomials

Let us exemplify remark 4.1 with the following two operations:

Image for post
Image for post

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

Image for post
Image for post

he can satisfy both the correct operand polynomials and variable values consistency checks:

Image for post
Image for post

Malleability of Variable Consistency Polynomials

Moreover the availability of

Image for post
Image for post

allows to use different values of same variable in different operands. For example, if we have an operation:

Image for post
Image for post

Which can be represented by the variable polynomials:

Image for post
Image for post

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:

Image for post
Image for post
Image for post
Image for post

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:

Image for post
Image for post

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.,

Image for post
Image for post

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 γ:

Image for post
Image for post

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

Image for post
Image for post

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

Image for post
Image for post

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

Image for post
Image for post

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

Image for post
Image for post

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].

Continue reading part 7

References

[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.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store