Why and How zk-SNARK Works 3: Non-interactivity & Distributed Setup
This is a series of articles. Part 2, PDF version
Non-Interactivity
Till this point, we had an interactive zero-knowledge scheme. Why is that the case? Because the proof is only valid for the original verifier, nobody else (other verifiers) can trust the same proof since:
- the verifier could collude with the prover and disclose those secret parameters s,α which allows to fake the proof, as mentioned in remark 3.1
- the verifier can generate fake proofs himself for the same reason
- verifier have to store α and t(s) until all relevant proofs are verified, which allows an extra attack surface with possible leakage of secret parameters
Therefore a separate interaction with every verifier is required in order for a statement (knowledge of polynomial in this case) to be proven.
While interactive proof system has its use cases, for example when a prover wants to convince only a dedicated verifier (called designated verifier, more information in [JSI96]) such that the proof cannot be re-used to prove same statement to others, it is quite inefficient when one needs to convince many parties simultaneously (e.g., in distributed systems such as blockchain) or permanently. Prover would be required to stay online at all times and perform the same computation for every verifier.
Hence, we need the secret parameters to be reusable, public, trustworthy and infeasible to abuse.
Let us first consider how would we secure the secrets (t(s),α) after they are produced. We can encrypt them the same way verifier encrypts powers of s before sending to the prover. However as mentioned in the remark 3.2, the homomorphic encryption we use does not support the multiplication of two encrypted values, which is necessary for both verification checks to multiply encryptions of t(s) and h as well as p and α. This is where cryptographic pairings fit in.
Multiplication of Encrypted Values
Cryptographic pairings (bilinear map) is a mathematical construction, denoted as a function e(g*,g*), which given two encrypted inputs (e.g., gᵃ, gᵇ ) from one set of numbers allows to map them deterministically to their multiplied representation in a different output set of numbers, i.e., e(gᵃ, gᵇ ) = e(g, g)ᵃᵇ :
Because the source and output number sets (usually referred to as a group) are different the result of the pairing is not usable as an input for another pairing operation. We can look at the output set (also called “target set”) as being from a “different universe.” Therefore we cannot multiply the result by another encrypted value and suggested by the name itself we can only multiply two encrypted values at a time.
In some sense, it resembles a hash function, which maps all possible input values to an element in the set of possible output values and it is not trivially reversible.
Note: from first glance, such limitation must only impede a dependent functionality, ironically in the zk-SNARK case it is a paramount property on which security of the scheme holds, see remark 3.3.
A rudimentary (and technically incorrect) mathematical analogy for pairing function e(g*,g*) would be to state that there is a way to “swap” each input’s base and exponent, such that base g is modified in the process of transformation into exponent, e.g., gᵃ → aᵍ . Both “swapped” inputs are then multiplied together, such that raw a and b values get multiplied under the same exponent, e.g.:
Therefore because the base gets altered during the “swap” using the result (ab)ᵍ in another pairing (e.g., e((ab)ᵍ, gᵈ )) would not produce desired encrypted multiplication abd. The core properties of pairings can be expressed in the equations:
Technically the result of a pairing is an encrypted product of raw values under a different generator g of the target set, i.e., e(gᵃ, gᵇ ) = gᵃᵇ . Therefore it has properties of the homomorphic encryption, e.g., we can add the encrypted products of multiple pairings together:
Note: cryptographic pairing is leveraging elliptic curves to achieve these properties, therefore from now on notation gⁿ will represent a generator point on a curve added to itself n times instead of a multiplicative group generator which we have used in previous sections.
The survey [DBS04] provides a starting point for exploration of the cryptographic pairings.
Trusted Party Setup
Having cryptographic pairings, we are now ready to set up secure public and reusable parameters. Let us assume that we trust a single honest party to generate secrets s and α. As soon as α and all necessary powers of s with corresponding α-shifts are encrypted, the raw values must be deleted (for i in 0, 1, …, d):
These parameters are usually referred to as common reference string or CRS. After CRS is generated any prover and any verifier can use it in order to conduct non-interactive zero-knowledge proof protocol. While non-crucial, the optimized version of CRS will include encrypted evaluation of the target polynomial gᵗ ⁽ˢ⁾.
Moreover CRS is divided into two groups (for i in 0, 1, …, d):
Being able to multiply encrypted values the verifier can check the polynomials in the last step of the protocol:
Trusting One out of Many
While the trusted setup is efficient, it is not effective since multiple users of CRS will have to trust that one deleted α and s, since currently there is no way to prove that (proof of ignorance is an area of active research [DK18]). Hence it is necessary to minimize or eliminate that trust. Otherwise, a dishonest party would be able to produce fake proofs without being detected.
One way to achieve that is by generating a composite CRS by multiple parties employing mathematical tools introduced in previous sections, such that neither of those parties knows the secret. Here is an approach, let us consider three participants Alice, Bob and Carol with corresponding indices A, B and C, for i in 1, 2, …, d:
As the result of such protocol, we have composite sⁱ and α, where
and no participant learns secret parameters of other participants unless they are colluding. In fact, in order to learn s and α, one must collude with every other participant. Therefore even if one out of all is honest, it will be infeasible to produce fake proofs.
Note: this process can be repeated for as many participants as necessary.
The question one might have is how to verify that participant have been consistent with every value of CRS, because an adversary can sample multiple different s₁, s₂, … and α₁, α₂, …, and use those randomly for different powers of s (or provide random numbers as an augmented common reference string), rendering CRS invalid and unusable.
Luckily, because we can multiply encrypted values using pairings, we are able to perform consistency check, starting with the first parameter and ensuring that every next is derived from it. Every published CRS by participants can be checked as follows:
- We take power 1 of s as canonical value and check every other power for consistency with it:
- We now check if the α-shift of values in the previous step is correct:
where i ∈ {2, …, d} is a shortened form of “i is in 2, 3, …, d” and [d] is a shortened form of range 1, 2, …, d, which is the more convenient notation for the next sections.
Notice that while we verify that every participant is consistent with their secret parameters, the requirement to use previously published CRS is not enforced for every next party (Bob and Carol in our example). Hence if an adversary is the last in the chain he can ignore the previous CRS and construct valid parameters from scratch, as if he was the first in the chain, therefore being the only one who knows secret s and α.
We can address this by additionally requiring every participant except the first one to encrypt and publish his secret parameters, for example, Bob also publishes:
This allows to validate that Bob’s CRS is a proper multiple of Alice’s parameters, for i in 1, 2,…, d:
Similarly Carol will have to prove that her CRS is a proper multiple of Alice-Bob’s CRS.
This is a robust CRS setup scheme which does not rely entirely on any single party. In fact, it is sufficient if only one party is honest and deletes and never shares its secret parameters, even if all other parties have colluded. So the more there are unrelated participants in CRS setup (sometimes called ceremony [Wil16]) the faintest the possibility of fake proofs, the probability becomes negligible if competing parties are participating. The scheme allows involving other untrusted parties who are in doubt about the legibility of the setup because verification step ensures they are not sabotaging (which also includes usage of weak α and s) the final common reference string.
Succinct Non-Interactive Argument of Knowledge of Polynomial
We are now ready to consolidate the evolved zk-SNARKOP protocol. Being formal, for brevity, we will be using curly brackets to denote a set of elements populated by the subscript next to it, for example
denotes a set s¹, s², …, sᵈ . Having agreed upon target polynomial t(x) and degree d of the prover’s polynomial:
Remark 3.3 If it would be possible to reuse result of pairing for another multiplication such protocol would be completely insecure because the prover can assign
which would then pass the “polynomial restriction” check:
Conclusions
We came to the zero-knowledge succinct non-interactive arguments of knowledge protocol for the knowledge of a polynomial problem, which is a niche use-case. While one can claim that a prover can easily construct such polynomial p(x) just by multiplying t(x) by another bounded polynomial to make it pass the test, the construction is still useful.
Verifier knows that the prover has a valid polynomial but not which particular one. We could add additional proofs of other properties of the polynomial such as: divides by multiple polynomials, is a square of a polynomial. There could be a service which accepts, stores and rewards all the attested polynomials, or there is a need in an encrypted evaluation of unknown polynomials of a necessary form. However, having universal scheme would allow for a myriad of applications.
References
[JSI96] — Markus Jakobsson, Kazue Sako, and Russell Impagliazzo. “Designated verifier proofs and their applications”. In: International Conference on the Theory and Applications of Cryptographic Techniques. Springer. 1996, pp. 143–154.
[DBS04] — Ratna Dutta, Rana Barua, and Palash Sarkar. Pairing-Based Cryptographic Protocols: A Survey. Cryptology ePrint Archive, Report 2004/064. https://eprint.iacr.org/2004/064. 2004.
[DK18] — Apoorvaa Deshpande and Yael Kalai. Proofs of Ignorance and Applications to 2-Message Witness Hiding. Cryptology ePrint Archive, Report 2018/896. https://eprint.iacr.org/2018/896. 2018.
[Wil16] — Zooko Wilcox. The Design of the Ceremony. 2016. url: https://z.cash/blog/the-design-of-the-ceremony/ (visited on 2018–05–01).
