Why and How zk-SNARK Works 8: Zero-Knowledge Computation

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

Zero-Knowledge Proof of Computation

Since the introduction of the general-purpose computation protocol (Proof of Operation section) we had to let go of the zero-knowledge property, to make the transition simpler. Until this point, we have constructed a verifiable computation protocol.

Previously to make a proof of polynomial zero-knowledge we have used the random δ-shift, which makes the proof indistinguishable from random (Zero-Knowldge section):

With the computation we are proving instead that:

While we could just adapt this approach to the multiple polynomials using same δ, i.e., supplying randomized values δL(s), δR(s), δ²O(s), δ²h(s), which would satisfy the valid operations check through pairings:

The issue is that having same δ hinders security, because we provide those values separately in the proof:

• one could easily identify if two different polynomial evaluations have same value, learning some knowledge, e.g.:

• potential insignificance of differences of values between L(s) and R(s) could allow factoring of those differences through brute-force, for example if L(s) = 5R(s), iterating check

for i ∈ {1…N} would reveal the 5× difference in just 5 steps. Same brute-force can be performed on encrypted addition operation, e.g.,

• other correlations between elements of the proof may be discovered, for example, if

then L(x) ⋅ R(x) = O(x), etc.

Note: the consistency check optimization makes such data mining harder but still allows to discover relationships, apart from the fact that verifier can choose ρₗ, ρᵣ in a particular way that can facilitate revealing of knowledge (as long as it is not a diversified setup).

Consequently, we need to have different randomness (δ-s) for each polynomial evaluation, e.g.:

To resolve inequality on the right side, we can only modify the proof’s value h(s), without alteration of the protocol which would be preferable. Delta (Δ) here represents the difference we need to apply to h(s) in order to counterbalance the randomness on the other side of the equation and ?⃝represents either multiplication or addition operation (which in turn accommodates division and subtraction). If we chose to apply Δ through multiplication (?⃝ = ×) this would mean that it is impossible to find Δ with overwhelming probability, because of randomization:

We could set

which transforms into:

However, as noted previously this hinders the zero-knowledge property, and even more importantly such construction will not accommodate the verifier’s input polynomials since they must be multiples of the corresponding δ-s, which would require an interaction.

We can try adding randomness to the evaluations:

However due to randomness it is non-divisible. Even if we address this by multiplying each δ with t(s)h(s), because we apply Δ through multiplication of h(s), and Δ will consist of encrypted evaluations (i.e., E(L(s)), etc.) it will not be possible to compute

without use of pairings (result of which is in another number space). Likewise computation is not possible through encrypted evaluation of Δh(x) using encrypted powers of s (from 1 to d), because the degree of h(x) and Δ is d, hence the degree of Δh(x) is up to 2d. Moreover, it is not possible to compute such randomized operand polynomial evaluation for the same reason:

Therefore we should try applying Δ through addition (?⃝ = +), since it is available for homomorphically encrypted values.

Every term in the numerator is a multiple of a δ, therefore we can make it divisible by multiplying each δ with t(s):

Which we can efficiently compute in the encrypted space:

This leads to passing of valid operations check while concealing the encrypted values.

The construction is statistically zero-knowledge due to addition of uniformly random multiples of δ˻, δᵣ, δ̥ (see theorem 13 of [Gen+12]).

Note: this approach is also consistent with the verifier’s operands, e.g.:

therefore the valid operations check holds but still only if the prover have used verifier’s values to construct the proof (i.e., Δ = δᵣ(Lₚ + Lᵥ ) + δ˻(Rₚ + Rᵥ ) + δ˻δᵣ t – δ ̥), see next section for more details.

To make the “variable polynomials restriction” and “variable values consistency” checks coherent with the zero-knowledge alterations, it is necessary to add the following parameters to the proving key:

It is quite curious that the original Pinocchio protocol [Par+13] was concerned primarily with the verifiable computation and less with the zero-knowledge property, which is a minor modification and comes almost for free.

zk-SNARK Protocol

Considering all the gradual improvements the final zero-knowledge succinct non-interactive arguments of knowledge, aka Pinocchio [Par+13], protocol is (the zero-knowledge components are optional and highlighted with a different color):

Conclusions

We ended up with an effective protocol which allows proving computation:

• succinctly — independently from the amount of computation the proof is of constant, small size
• non-interactively — as soon as the proof is computed it can be used to convince any number of verifiers without direct interaction with the prover
• with argumented knowledge — the statement is correct with non-negligible probability, i.e., fake proofs are infeasible to construct; moreover prover knows the corresponding values for the true statement (i.e. witness), e.g., if the statement is “B is a result of sha256(a)” then the prover knows some a such that B = sha256(a) which is useful since B could only be computed with the knowledge of a as well as it’s infeasible to compute a from B (assuming a have enough entropy)
• the statement is correct with non-negligible probability, i.e., fake proofs are infeasible to construct
• in zero-knowledge — it is “hard” to extract any knowledge from the proof, i.e., it is indistinguishable from random

It was possible to achieve primary due to unique properties of polynomials, modular arithmetic, homomorphic encryption, elliptic curve cryptography, cryptographic pairings and ingenuity of the inventors.

This protocol proves computation of a unique finite execution machine which in one operation can add together almost any number of variables but may only perform one multiplication. Therefore there is an opportunity to both optimize programs to leverage this specificity efficiently as well as use constructions which minimize the number of operations.

It is essential that verifier does not have to know any secret data in order to verify a proof so that properly constructed verification key can be published and used by anyone in a non-interactive manner. Which is contrary to the “designated verifier” schemes where the proof will convince only one party, therefore it is non-transferable. In zk-SNARK context, we can achieve this property if untrustworthy or a single party generates the keypair.

The field of zero-knowledge proof constructions is continuously evolving, introducing optimizations ([BCTV13, Gro16, GM17]), improvements such as updatable proving and verification keys ([Gro+18]), and new constructions (Bulletproofs [Bün+17], ZK-STARK [Ben+18], Sonic [Mal+19]).

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.

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

[BCTV13] — Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza. Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture. Cryptology ePrint Archive, Report 2013/879. https://eprint.iacr.org/2013/879. 2013.

[Gro10] — Jens Groth. “Short pairing-based non-interactive zero-knowledge arguments”. In: International Conference on the Theory and Application of Cryptology and Information Security. Springer. 2010, pp. 321–340.

[GM17] — Jens Groth, Mary Maller. Snarky Signatures: Minimal Signatures of Knowledge from Simulation-Extractable SNARKs. Cryptology ePrint Archive, Report 2017/540. https://eprint.iacr.org/2017/540. 2017.

[Gro+18] — Jens Groth, Markulf Kohlweiss, Mary Maller, Sarah Meiklejohn, and Ian Miers. Updatable and Universal Common Reference Strings with Applications to zk-SNARKs. Cryptology ePrint Archive, Report 2018/280. https://eprint.iacr.org/2018/280. 2018.

[Bün+17] — Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short Proofs for Confidential Transactions and More. Cryptology ePrint Archive, Report 2017/1066. https://eprint.iacr.org/2017/1066. 2017.

[Ben+18] — Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Report 2018/046. https://eprint.iacr.org/2018/046. 2018.

[Mal+19] — Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings. Cryptology ePrint Archive, Report 2019/099. https://eprint.iacr.org/2019/099. 2019.