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

Maksym
Maksym
Apr 25, 2019 · 8 min read

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

Image for post
Image for post

With the computation we are proving instead that:

Image for post
Image for post

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:

Image for post
Image for post

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

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

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

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

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

Image for post
Image for post

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:

Image for post
Image for post

We could set

Image for post
Image for post

which transforms into:

Image for post
Image for post

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:

Image for post
Image for post

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

Image for post
Image for post

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:

Image for post
Image for post

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

Image for post
Image for post

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

Image for post
Image for post

Which we can efficiently compute in the encrypted space:

Image for post
Image for post

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

Image for post
Image for post

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

Image for post
Image for post

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:

Image for post
Image for post

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

Image for post
Image for post

Conclusions

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

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.

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