Ethereum Foundation logo
  • home
  • blog
  • research
  • bounties ↗
  • team
  • events

Groth-Sahai Proofs Are Not That Scary

Mikhail Volkhov, Dimitris Kolonelos, Dmitry Khovratovich, Mary Maller | June 6, 2022

Header image

Groth-Sahai (GS) proofs are a zero-knowledge proving technique which can seem daunting to understand. This is because much of the literature attempts to generalise all possible things you can prove using GS techniques rather than because the proofs are overly complicated. In fact GS proofs are one of the simplest zero-knowledge constructions. For statements about group elements in pairing based groups, they are ideal because there is no heavy reduction to an NP constraint system, and this makes the prover very fast. Security wise they also rely on much more standard assumptions than SNARKs and thus are more likely to be secure.

In this post we will walk through an example Groth-Sahai proof and attempt to make the explanation accessible to a general cryptographic audience. Specifically we discuss how to prove that an ElGamal ciphertext contains 00 or 11. Our example includes the improvements by Escala and Groth. Prerequisites include knowledge about what a zero-knowledge argument is and what Type-III pairings are (but not how they are constructed).

And for those interested in experimenting with GS proofs in practice we have written a simple implementation in python -- check it out! It includes both the example we will be going through in this paper, and the more general proving framework that you can use to construct proofs for your language.

ElGamal in Pairing Product Equations

In order to prove that an ElGamal ciphertext contains 00 or 11 we must first arithmetise this statement into a form that is compatible with GS proofs. GS proofs take as input pairing-product equations; pairing product equations can be seen as the equivalent of arithmetic circuits in the sense that they arithmetise the relation that we are trying to prove. Thus in this section we show how to represent our statement using pairing product equations. In later sections we will show how to prove that these equations are satisfied under zero-knowledge.

Notation and Pairings

Recall the standard property of pairings: e(ga,h^b)=e(g,h^)ab e(g^a,\widehat{h}^b) = e(g,\widehat{h})^{ab} We denote the first source group by G1\mathbb{G}_1 and the second source group by G2\mathbb{G}_2. Elements from G2\mathbb{G}_2 are denoted with wide hat like E^\widehat{E}. We will write Θ=gθ\Theta = g^{\theta} and D^=h^d\widehat{D} = \widehat{h}^d trying, where it's possible, to use lowercase letters for exponents of the corresponding capital letter element.

Pairings allow us to define quadratic equations in the logarithms of the arguments, e.g.

e(X,h^)e(g,Y^)=1loggX+logh^Y^=0e(X,Y^)=e(X,Y^)loggXlogh^Y^=loggXlogh^Y^\begin{array}{ccc} e(X,\widehat{h})e(g,\widehat{Y})=1 & \Longleftrightarrow & \log_g X +\log_{\widehat{h}} \widehat{Y}=0 \\ e(X,\widehat{Y})=e(X',\widehat{Y}') & \Longleftrightarrow & \log_g X \cdot \log_{\widehat{h}} \widehat{Y} =\log_g X' \cdot \log_{\widehat{h}} \widehat{Y}' \end{array}

If you have not worked with pairings with multiple bases, see this explanation:

Collapsible: On Pairings with Multible Bases

As later we will employ multiple bases and not just g,h^g,\widehat{h}, pairing equations will also work "in parallel" for all pairs of bases from G1\mathbb{G}_1 and G2\mathbb{G}_2. Consider the following example. By bilinearity of the pairing e(g1ag2b,h^1ch^2d)=1e(g_1^a g_2^b, \widehat{h}_1^c \widehat{h}_2^d) = 1 is equivalent to: e(g1,h^1)ace(g1,h^2)ade(g2,h^1)bce(g2,h^2)bd=1e(g_1,\widehat{h}_1)^{ac} \cdot e(g_1,\widehat{h}_2)^{ad} \cdot e(g_2,\widehat{h}_1)^{bc} \cdot e(g_2,\widehat{h}_2)^{bd} = 1 In such a case we will always have ac=ad=bc=bd=0ac = ad = bc = bd = 0 when all gig_i and hih_i are chosen independently and uniformly at random.

Here is an example of how it works:

Pairings with Multiple Bases

ElGamal Verification in Pairing Equations

We first present our solution for arithmetising the statement "This ciphertext contains 00 or 11" directly and after explain the intuition for how we derived these equations. Let g1g_1 generate G1\mathbb{G}_1, and pk=g1sk\mathsf{pk} = g_1^\mathsf{sk}. Consider a (lifted) ElGamal ciphertext

CT=(CT1,CT2)=(g1r,Mpkr)(1)\mathsf{CT} = (\mathsf{CT}_1, \mathsf{CT}_2) = (g_1^r, M \cdot \mathsf{pk}^{r}) \tag{1}

Then M=g1mM = g_1^m is either (g1)0(g_1)^0 or (g1)1(g_1)^1 if and only if there exist witnesses W^1,W2,W^3\widehat{W}_1, W_2, \widehat{W}_3 such that

e(CT1,h^1)=e(g1,W^1)(E1)e(CT2,h^1)=e(pk,W^1)e(W2,h^1)(E2)e(W2,h^1)=e(g1,W^3)(E3)e(W2,W^3)=e(W2,h^1)(E4)\begin{array}{r c l r } e(\mathsf{CT}_1, \widehat{h}_1) & = & e(g_1 , \widehat{W}_1) & \hspace{1cm} (E_1)\\ e(\mathsf{CT}_2, \widehat{h}_1) & = & e(\mathsf{pk}, \widehat{W}_1) e(W_2, \widehat{h}_1) & (E_2)\\ e(W_2, \widehat{h}_1) & = & e(g_1, \widehat{W}_3) & (E_3)\\ e(W_2, \widehat{W}_3) & = & e(W_2, \widehat{h}_1) & (E_4) \end{array}

Note that the witness components (W^1,W2,W^3)(\widehat{W}_1, W_2, \widehat{W}_3) must be kept secret because they reveal information about the message MM.

Our purpose now is to explain how we arrived at the above set of pairing product equations and along the way to illustrate the design constraints that the GS proving system presents us with. Arithmetising statements is an art that Daira Hopwood is exceptionally skilled at (check out the Zcash spec, Appendix A, for many cool arithemetisation tricks). Alas, we are not Daira so please bear with us even if our solution is not optimal.

One characteristic feature of GS proofs is that all secret witness components must be group elements rather than field elements. So our secret that we want to keep hidden cannot be field elements 00 or 11 or rr, but must instead be group elements g10g_1^{0} or g11g_1^1 or g1rg_1^r. For our ciphertext to encrypt 00 or 11 we thus desire that m{(g1)0,(g1)1}m\in\{(g_1)^0,(g_1)^1\}. Turning to the equation (1) we have that this condition that is equivalent to

CT2pklogCT1{(g1)0,(g1)1}(2)\mathsf{CT}_2\cdot \mathsf{pk}^{-\log \mathsf{CT}_1} \in \{(g_1)^0,(g_1)^1\}\tag{2}

where logarithm is taken with base g1g_1. Denote W2=g1w2=CT2pklogCT1W_2 = g_1^{w_2} = \mathsf{CT}_2\cdot \mathsf{pk}^{-\log \mathsf{CT}_1} We wish to check that w22w2=0w_2^2-w_2 =0. Our one and only method of checking constraints is using pairing equations. We cannot pair W2W_2 with itself because we can only pair G1\mathbb{G}_1 elements with G2\mathbb{G}_2 elements. Thus we choose to "bridge" w2w_2 into G2\mathbb{G}_2 by introducing an additional group element W^3=h^1w^3\widehat{W}_3 = \widehat{h}_1^{\widehat{w}_3} such that

w2=w^3w2w^3w2=0\begin{array}{r c l} w_2 & = & \widehat{w}_3 \\ w_2 \widehat{w}_3 - w_2 & = & 0 \end{array}

where w2w_2 is a logarithm of some G1\mathbb{G}_1 element W2W_2 and w^3\widehat{w}_3 is a logarithm of some G2\mathbb{G}_2 element W^3\widehat{W}_3.

Bridge illustration

Then (2) is equivalent to

CT2pklogCT1=W2e(W2,h^1)=e(g1,W^3)e(W2,W^3)=e(W2,h^1)(3)\begin{array}{r c l} \mathsf{CT}_2\cdot \mathsf{pk}^{-\log \mathsf{CT}_1} & = & W_2 \tag{3}\\ e(W_2, \widehat{h}_1) & = & e(g_1, \widehat{W}_3) \\ e(W_2, \widehat{W}_3) & = & e(W_2, \widehat{h}_1) \end{array}

That first condition in (3) that CT2pklogCT1=W2\mathsf{CT}_2\cdot \mathsf{pk}^{-\log \mathsf{CT}_1} =W_2 currently does not look very much like a pairing product equation. We cannot use logarithms in PPEs, so we need an alternative method for arithmetising that logCT2logCT1logpk=w2\log \mathsf{CT}_2- \log \mathsf{CT}_1\cdot\log \mathsf{pk}=w_2 As CT1,CT2,pk\mathsf{CT}_1,\mathsf{CT}_2,\mathsf{pk} are all in G1\mathbb{G}_1, we make another bridge:

logg1CT1=w^1logCT2logpkw^1=w2\begin{array}{r c l} \log_{g_1} \mathsf{CT}_1 & = & \widehat{w}_1\\ \log \mathsf{CT}_2-\log \mathsf{pk}\cdot \widehat{w}_1 & = & w_2 \end{array}

In pairing equations this is equivalent to

e(CT1,h^1)=e(g1,W^1)e(CT2,h^1)=e(pk,W^1)e(W2,h^1)\begin{array}{r c l} e(\mathsf{CT}_1, \widehat{h}_1) & = & e(g_1 , \widehat{W}_1) \\ e(\mathsf{CT}_2, \widehat{h}_1) & = & e(\mathsf{pk}, \widehat{W}_1) e(W_2, \widehat{h}_1) \end{array}

Combining all our pairing equations together we arrive at our final pairing product equation for arithmetising that (CT1,CT2)(\mathsf{CT}_1, \mathsf{CT}_2) encrypts 00 or 11.

General Proof Structure

In this section we describe the GS setup, prover and the verifier used in representing the statement "This ciphertext encrypts 00 or 11".

Transparent Setup

We discuss how to run the GS setup. The setup does not depend on our pairing product equations at all and the same setup is used for proving any statement. It is only the prover and the verifier that depend on the pairing product equation explicitly.

NIZK proofs are constructed with a common reference string (CRS), that is used for both producing and verifying proofs. In GS proofs the CRS is constructed using public randomness and therefore they are said to have a trustless setup (this is a positive thing because we do not have to trust a third party or MPC that replaces it, like with many SNARKs). The GS CRS consists of eight independent elements --- four in each group.

g1,g2,g3,g4G1h^1,h^2,h^3,h^4G2crs=(g1g4,h^1h^4)\begin{array}{l} g_1, g_2, g_3, g_4 \gets \mathbb{G}_1 \\ \widehat{h}_1, \widehat{h}_2, \widehat{h}_3, \widehat{h}_4 \gets \mathbb{G}_2 \\ \mathsf{crs} = (g_1 \ldots g_4, \widehat{h}_1 \ldots \widehat{h}_4) \end{array}

In practice these elements are typically sampled as the output of a hash function, and the seed is published so that anyone can verify the setup procedure. It is permitted and encouraged to have fun (not too much fun) when choosing the seed and we sometimes like to use the opening lines of famous books.

We will reuse the generator g1g_1 for our ElGamal ciphertext which helps us to simplify the structure of prover and verifier.

Commitments to Witnesses

We now describe our GS prover. The prover aims to show the existence of a witness that satisfies the pairing product equations. The witness is secret and cannot be revealed directly. Thus instead the prover commits to the witness, and proves that the committed witness satisfies a related set of pairing product equations. We discuss the form of this commitment before we present the related set of equations.

The prover computes two elements using an algorithm that looks a lot like ElGamal encryption. To commit to WG1W \in \mathbb{G}_1 it chooses random field elements r,sr,s, sets C=g1rg2s, D=Wg3rg4sC = g_1^r g_2^s, \ D = W g_3^r g_4^s and returns (C,D)(C,D). We have expressed the commitment with respect to G1\mathbb{G}_1. To commit to elements in G2\mathbb{G}_2 we use the same method with respect to the generators (h^1h^4)(\widehat{h}_1\ldots \widehat{h}_4) instead of (g1g4)(g_1\ldots g_4).

Typically when we present this commitment scheme to cryptographers their immediate response is "why two generators?" or "why not use Pedersen commitments?". The answer to this question is highly nuanced and answering it here would disrupt the flow of this explanation. Thus we're not going to. But as a teaser, we will say that Groth and Sahai describe this commitment scheme as one that either satisfies hiding or binding depending on how the setup parameters are chosen.

Now, in our particular case of ElGamal encryption, we commit to our witness (W1^,W2,W3^)(\widehat{W_1}, W_2, \widehat{W_3}) once for all equations E1E4E_1-E_4:

(C^1,D^1)(h^1r1h^2s1, W^1h^3r1h^4s1)(C2,D2)(g1r2g2s2, W2g3r2g4s2)(C^3,D^3)(h^1r3h^2s3, W3^h^3r3h^4s3)\begin{array}{l} (\widehat{C}_1, \widehat{D}_1) \leftarrow (\widehat{h}_1^{r_1} \widehat{h}_2^{s_1}, \ \widehat{W}_1 \widehat{h}_3^{r_1} \widehat{h}_4^{s_1})\\ (C_2, D_2) \leftarrow (g_1^{r_2} g_2^{s_2}, \ W_2 g_3^{r_2} g_4^{s_2})\\ (\widehat{C}_3, \widehat{D}_3) \leftarrow (\widehat{h}_1^{r_3} \widehat{h}_2^{s_3}, \ \widehat{W_3} \widehat{h}_3^{r_3} \widehat{h}_4^{s_3}) \end{array}

The Prover and The Verifier

While the commitments (C^1,D^1,C2,D2,C^3,D^3)(\widehat{C}_1, \widehat{D}_1, C_2, D_2, \widehat{C}_3, \widehat{D}_3) are shared across all pairing product equations, each pairing equation requires a unique set of 88 proof elements and 44 verifier equations, so forms a "sub-proof". Here, mostly to stay concise, we show and later derive the proof system (prover and verifier) only for the second equation E2E_2. For the full system thus, prover must produce proofs for all four equations, and verifier must verify them all.

Recall that E2E_2 has the form

e(CT2,h^1)=e(pk,W^1)e(W2,h^1)(E2) e(\mathsf{CT}_2, \widehat{h}_1)= e(\mathsf{pk}, \widehat{W}_1) e(W_2, \widehat{h}_1) \tag{$E_2$}

The honest prover needs to construct the following eight elements, where α,β,γ,δ\alpha,\beta,\gamma,\delta are sampled randomly:

Θ1=pkr1g3αg4βΦ^1=h1r2h3αh4γΘ2=pks1g3γg4δΦ^2=h1s2h3βh4δΘ3=g1αg2βΦ^3=h1αh2γΘ4=g1γg2δΦ^4=h1βh2δ\begin{array}{l c l} \Theta_1 = \mathsf{pk}^{r_1} g_3^{\alpha} g_4^{\beta} & & \widehat{\Phi}_1 = h_1^{r_2} h_3^{-\alpha} h_4^{-\gamma}\\ \Theta_2 = \mathsf{pk}^{s_1} g_3^\gamma g_4^{\delta} & & \widehat{\Phi}_2 = h_1^{s_2} h_3^{-\beta} h_4^{-\delta}\\ \Theta_3 = g_1^\alpha g_2^{\beta} & & \widehat{\Phi}_3 = h_1^{-\alpha} h_2^{-\gamma}\\ \Theta_4 = g_1^\gamma g_2^{\delta} & & \widehat{\Phi}_4= h_1^{-\beta} h_2^{-\delta} \end{array}

And the four equations V1V4V_1 \ldots V_4 the verifier must check on the commitments and proof elements are as follows:

e(Θ1,h^3)e(Θ2,h^4)e(g3,Φ^1)e(g4,Φ^2)=e(D2/CT2,h^1)e(pk,D^1)(V1)e(Θ1,h^1)e(Θ2,h^2)e(g3,Φ^3)e(g4,Φ^4)=e(pk,C^1)(V2)e(Θ3,h^3)e(Θ4,h^4)e(g1,Φ^1)e(g2,Φ^2)=e(C2,h^1)(V3)e(Θ3,h^1)e(Θ4,h^2)e(g1,Φ^3)e(g2,Φ^4)=1(V4)\begin{array}{l l r} e(\Theta_1,\widehat{h}_3)e(\Theta_2,\widehat{h}_4)e(g_3,\widehat{\Phi}_1)e(g_4,\widehat{\Phi}_2) &= e(D_2 / \mathsf{CT}_2,\widehat{h}_1)e(\mathsf{pk},\widehat{D}_1) & \hspace{1cm} (V_1) \\ e(\Theta_1,\widehat{h}_1)e(\Theta_2,\widehat{h}_2)e(g_3,\widehat{\Phi}_3)e(g_4,\widehat{\Phi}_4) &= e(\mathsf{pk},\widehat{C}_1) & \hspace{1cm} (V_2) \\ e(\Theta_3,\widehat{h}_3)e(\Theta_4,\widehat{h}_4)e(g_1,\widehat{\Phi}_1)e(g_2,\widehat{\Phi}_2) &= e(C_2,\widehat{h}_1) & \hspace{1cm} (V_3) \\ e(\Theta_3,\widehat{h}_1) e(\Theta_4,\widehat{h}_2) e(g_1,\widehat{\Phi}_3)e(g_2,\widehat{\Phi}_4) & = 1 & \hspace{1cm} (V_4) \end{array}

The reader is encouraged to attempt deriving the same equations for E1,E3E_1,E_3 which are both easier than our case (we put our derivation for them at the end of the blog post). A more sadistical writer might also ask the reader to derive equations for E4E_4 as an exercise (possibly hinting that it is a simple), but after having attempted this exercise for ourselves we realised that E4E_4 is more involved due to its quadratic component. Thus at the end of this document we will actively discuss E4E_4.

The form of proof elements and equations is somewhat homogeneous: we always have 8 proof elements and 4 verification equation per pairing equation, and the LHS of verification equations is always the same. However, the number of pairings in verification equations depends on the particular form of the pairing equation (reflected in the RHS). The commitments, as mentioned before, are generated once for all pairing equations, which amounts to 2 elements per witness element.

The following illustration shows how it works on a large scale:

Groth-Sahai Diagram

Deriving Equations for E2E_2

The intention of this section is to provide an intuitive step-by-step explanation of how the proof elements and verification equations for the pairing product equation E2E_2 are derived. We describe our general strategy, but after that things are going to get more technical. To readers that don't fancy wading through pages of algebra, we recommend you stop reading after the general strategy is explained. To other readers who are more dedicated to understanding the magic behind GS proofs, we recommend you get comfortable with continously switching between additive and multiplicative notation because we do this a lot (we promise not in the same equation).

The General Strategy

We have a pairing product equation that the prover claims to hold for hidden witness variables. The prover cannot give the witness in the clear, this would violate zero-knowledge, but it still must tell the verifier something about its witness. The prover therefore generates a commitment which binds them to their witness without revealing any additional information.

Our general strategy now is to find an alternative set of pairing product equations that hold if and only if the contents of the commitments satisfy the original pairing product equation. Our strategy will proceed in two parts.

  • During our first part we search for intemediary proof elements that satisfy an intermediary set of pairing product equations if and only if the contents of the commitment satisfy the original pairing product equation. We treat soundness as if it holds unconditionally i.e. as if the only way for the prover to cancel out the randomness from the CRS is to multiply by zero. In the formal proof, we actually show that soundness does hold unconditionally provided the CRS is chosen carefully.
  • During our second part, we show how to randomise the intemediary proofs and pairing product equations in a way that fully hides the witness. This results in our final equations. Here we focus mostly on satisfying zero-knowledge but we must not break soundness in the process. In other words we try to ensure that a malicious verifier learns nothing from an honest prover, beyond the correctness of the ciphertext.

For arguing indistinguishability, one of the key properties we require is that the number of randomisers is equal to the number of proof elements minus the number of verifier equations. That way we can say e.g. that Element 1 is random, Element 2 is random, and Element 3 is the unique value satisfying Equation 1 given Elements 1 and 2. Thus our strategy is to add in additional randomisers to our proof elements and edit our verifier equations such that they still hold for the randomised proofs. To keep things sound we also have to add additional verifier equations to enforce that the prover doesn't abuse their newfound freedom. The other property we require is that there are no linear combinations between our randomisers such that they cancel out in undesirable ways. While deriving our equations for (E2E_2) we are merely going to optimistically hope that this holds, but formally check that it is the case later.

The Intemediary Pairing Product Equations for Commitments

For the first part of our strategy, we must find an intermediary set of pairing product equations demonstrating that the contents (W^1,W2)(\widehat{W}_1, W_2) of the commitments

(C^1,D^1)=(h^1r1h^2s1,W^1h^3r1h^4s1)(C2,D2)=(g1r2g2s2,W2g3r2g4s2)(\widehat{C}_1, \widehat{D}_1) = (\widehat{h}_1^{r_1} \widehat{h}_2^{s_1}, \widehat{W}_1 \widehat{h}_3^{r_1} \widehat{h}_4^{s_1}) \quad (C_2, D_2) = (g_1^{r_2} g_2^{s_2}, W_2 g_3^{r_2} g_4^{s_2})

satisfy the second equation

e(CT2,h^1)e(pk,W^11)e(W21,h^1)=1(E2) e(\mathsf{CT}_2, \widehat{h}_1) e(\mathsf{pk}, \widehat{W}_1^{-1}) e(W_2^{-1}, \widehat{h}_1) = 1 \tag{$E_2$}

For this explanation we find it helpful to work in logarithms, so here is some notation denoting the logarithms of generators in the CRS

g2=g1xh^2=h^1u^g3=g1yh^3=h^1v^g4=g1zh^4=h^1^\begin{array}{c c c } g_2 = g_1^x\qquad&&\widehat{h}_2 = \widehat{h}_1^{\widehat{u}}\\ g_3 = g_1^y\qquad&&\widehat{h}_3 =\widehat{h}_1^{\widehat{v}}\\ g_4 = g_1^z\qquad&&\widehat{h}_4 =\widehat{h}_1^{\widehat{\ell}} \end{array}

Then the logarithms of our commitments are given by

(c^1,d^1)=(r1+u^s1,w^1+r1v^+s1^) and (c2,d2)=(r2+xs2,w2+r2y+s2z)(\widehat{c}_1, \widehat{d}_1) = (r_1 +\widehat{u} s_1 , \widehat{w}_1+ r_1 \widehat{v}+ s_1 \widehat{\ell}) \text{ and } (c_2, d_2) = (r_2+xs_2,w_2+r_2 y+s_2 z)

If we now actually look at the logarithmic equation defined by (E2E_2) we get that

logg1CT2skw^1=w2(L2)\log_{g_1} \mathsf{CT}_2-\mathsf{sk}\cdot \widehat{w}_1=w_2 \tag{$L_2$}

where sk=logg1(pk)\mathsf{sk} = \log_{g_1}(\mathsf{pk}). Notice that r1,s1,s2,r2r_1,s_1, s_2, r_2 are known to the prover while x,y,z,u^,v^,^x,y,z,\widehat{u}, \widehat{v},\widehat{\ell} are not. We make no assumptions on whether sk\mathsf{sk} is known to the prover or not.

Our derivation strategy is, by introducing new variables, to obtain a set of equations equivalent to L2L_2 such that

  • The equations do not contain w^1,w2\widehat{w}_1,w_2;
  • The equations are bilinear, i.e. each term has at most one variable from each group.

Step 1: We first express w^1\widehat{w}_1 and w2w_2 in terms of the commitments (c^1,d^1,c2,d2)(\widehat{c}_1, \widehat{d}_1, c_2, d_2) and the randomness r^1\widehat{r}_1, s^1,r2,s2\widehat{s}_1, r_2, s_2. The commitment D^1\widehat{D}_1 should use the same randomness r^1\widehat{r}_1, s^1\widehat{s}_1 as the commitment C^1\widehat{C}_1. Therefore, we substitute r1=c^1u^s1r_1 = \widehat{c}_1 - \widehat{u} s_1 into the equation for w^1\widehat{w}_1 and obtain:

w^1=d^1(c^1u^s1)v^s1^\widehat{w}_1 = \widehat{d}_1 - (\widehat{c}_1 - \widehat{u} s_1 ) \widehat{v} - s_1 \widehat{\ell}

Similarly for the second commitment: w2=d2(c2xs2)ys2zw_2 = d_2 - (c_2 - x s_2) y - s_2 z

Step 2: Substituting into (L2)(L_2) we get

logCT2^sk(d^1(c^1u^s1)v^s1^ )=d2(c2xs2)ys2z\log{\widehat{\mathsf{CT}_2}} - \mathsf{sk} \cdot \Big( \widehat{d}_1 - (\widehat{c}_1 - \widehat{u} s_1 ) \widehat{v} - s_1 \widehat{\ell} \ \Big) = d_2 - (c_2 - x s_2) y - s_2 z

Step 3: The terms logCT^2,skd^1,d2\log{\widehat{\mathsf{CT}}_2}, \mathsf{sk} \cdot \widehat{d}_1, d_2 are already in the pairing equation form (degree at most two, at most two elements from different groups), so we leave them alone, moving to the RHS, and swapping sides of the equation:

skd^1logCT^2+d2=(c2xs2)y+s2z+sk(c^1u^s1)v^+sks1^\mathsf{sk} \cdot \widehat{d}_1 - \log{\widehat{\mathsf{CT}}_2} + d_2 = \big(c_2 - x s_2\big) y + s_2 z + \mathsf{sk} \cdot \big(\widehat{c}_1 - \widehat{u} s_1 \big) \widehat{v} + \mathsf{sk} \cdot s_1 \widehat{\ell}

Now, we want the RHS summands to be in the pairing-friendly form too. Currently they are not. For example, we cannot pair C2C_2 with g3=g1yg_3 = g_1^y because these are both in the same source group.

Step 4: To get the RHS into a pairing friendly form, we will introduce new elements. For each summand we introduce one proof element. For example, where yy is multiplied by (c2xs2)(c_2 - x s_2), we introduce ϕ^1=c2s2x\widehat{\phi}_1' = c_2 - s_2 x. This suggests creating four additional elements:

θ1=sk(c^1s1u^)(=skr1)θ2=sks1ϕ^1=c2s2x(=r2)ϕ^2=s2\begin{array}{ r c l l } \theta_1' & = & \mathsf{sk} \cdot (\widehat{c}_1 - s_1 \widehat{u}) & \quad (= \mathsf{sk} \cdot r_1) \\ \theta_2' & = & \mathsf{sk} \cdot s_1 & \\ \widehat{\phi}_1' & = & c_2 - s_2 x & \quad (= r_2)\\ \widehat{\phi}_2' & = & s_2 & \end{array}

The additional proof elements we introduced is somewhat arbitrary --- there are many (closely related if not equivalent) ways to construct GS verification equations. Now our first equation is in the following well-formed pairing-compatible form:

skd^1+d2logCT2=θ1v^+yϕ^1+θ2^+zϕ^2\mathsf{sk} \cdot \widehat{d}_1 + d_2 - \log{\mathsf{CT}_2} = \theta_1' \widehat{v} + y \widehat{\phi}_1' + \theta_2' \widehat{\ell} + z \widehat{\phi}_2'

Step 5: Our fifth and final step for determining the intemediary pairing equations is to enforce the previous four equations for Θ1,Θ2,Φ^1,Φ^2\Theta_1',\Theta_2',\widehat{\Phi}_1',\widehat{\Phi}_2'. We start by joining the first two (substituting the second into the first) and obtaining: θ1=skc^1θ2u^\theta_1' = \mathsf{sk} \cdot \widehat{c}_1 - \theta_2' \widehat{u} Similarly, by joining the third and the fourth equations, we get:

ϕ^1=c2ϕ^2x\widehat{\phi}_1' = c_2 - \widehat{\phi}_2' x

Resulting Intemediary Pairing Product Equation: Putting all 55 steps together, our intemediary pairing product equation challenges the prover to find

Θ1=pkr1, Θ2=pks1,Φ^1=h^1r2, Φ^2=h^1s2\Theta_1' = \mathsf{pk}^{r_1}, \ \Theta_2' = \mathsf{pk}^{s_1}, \widehat{\Phi}_1' = \widehat{h}_1^{r_2}, \ \widehat{\Phi}_2' = \widehat{h}_1^{s_2}

such that they satisfy

e(pk,D^1)e(D2CT21,h^1)=e(g3,Φ^1)e(g4,Φ^2)e(Θ1,h^3)e(Θ2,h^4)(V1)e(pk,C^1)=e(Θ1,h^1)e(Θ2,h^2)(V2)e(C2,h^1)=e(g1,Φ^1)e(g2,Φ^2)(V3)\begin{array}{ rl r} e(\mathsf{pk}, \widehat{D}_1) e(D_2 \mathsf{CT}_2^{-1}, \widehat{h}_1) & = e(g_3, \widehat{\Phi}_1)e(g_4, \widehat{\Phi}_2) e(\Theta_1, \widehat{h}_3) e(\Theta_2, \widehat{h}_4) & \hspace{1 cm } (V_1') \\ e(\mathsf{pk}, \widehat{C}_1) & = e(\Theta_1, \widehat{h}_1) e(\Theta_2, \widehat{h}_2) & (V_2') \\ e(C_2, \widehat{h}_1) & = e(g_1, \widehat{\Phi}_1) e(g_2, \widehat{\Phi}_2) & (V_3') \end{array}

(Proof elements in verification equations are without primes since they are considered to be formal variables.) Together these show that the commitments (C^1,D^1)(\widehat{C}_1, \widehat{D}_1) and (C2,D2)(C_2, D_2) contain witness elements W^1\widehat{W}_1 and W2W_2 such that the second pairing product equation (E2E_2) is satisfied.

We are now going to frustrate the reader by observing that the above process was rather circular. Indeed we cannot reveal Θ1,Θ2,Φ^1,Φ^2\Theta_1', \Theta_2', \widehat{\Phi}_1', \widehat{\Phi}_2' in the clear: they reveal too much information about the witness and violate zero-knowledge. For example observe that

e(D2,h^1)e(g31,Φ^1)e(g41,Φ^2)=e(g1m,h^1)e(D_2, \widehat{h}_1) e(g_3^{-1}, \widehat{\Phi}_1') e(g_4^{-1}, \widehat{\Phi}_2') = e(g_1^{m}, \widehat{h}_1)

for mm our secret message. The next step, however, will not be circular and we will show how to randomise these proof components in a manner that does not break zero-knowledge. That we have really gained is that Θ1,Θ2,Φ^1,Φ^2\Theta_1', \Theta_2', \widehat{\Phi}_1', \widehat{\Phi}_2' depend only on the original pairing product equations and the commitment randomness r1,s1,r2,s2r_1, s_1, r_2, s_2. In particular they do not depend on the witness W^1\widehat{W}_1, W2W_2.

A general property that is required (but not sufficient!) for zero knowledge is that number of randomisers \geq number of proof elements - number of verification equations. Here we have 44 commitment elements with 44 randomisers and then 44 proof elements with no additional randomisers. Given 33 verifier equations this leaves us 11 randomiser short.

Adding Zero-Knowledge: Getting Sufficient Randomisers

For the second part of our strategy, we must randomise our intermediary proofs (Θ1,Θ2,Φ^1,Φ^2)(\Theta_1', \Theta_2', \widehat{\Phi}_1', \widehat{\Phi}_2') and pairing product equations (V1),(V2),(V3)(V_1'), (V_2'), (V_3') to keep the witness hidden. We do this by adding blinding factors to Θ1,Θ2\Theta_1',\Theta_2' (order does not matter), and cancelling out the additional noise using other proof elements. Often the only way we can balance the randomised pairing equations is by adding additional proof elements. When we do this, we either add at least one new randomiser to the new proof element, or a new verifier equation which is a quadratic combinations of our other proof elements.

Step 1: We first introduce a randomiser to Θ1\Theta_1'. We must then edit our intemediary equations to adjust for the extra randomness. We set

θ1=θ1+yα\theta_1'' = \theta_1' + y \alpha

By substituting this into the RHS of (V1)(V_1')

ϕ^1y+ϕ^2z+θ1v^+θ2^\widehat{\phi}_1' y + \widehat{\phi}_2' z + \theta_1 \widehat{v} + \theta_2 \widehat{\ell}

we see that an additional term yαv^y \alpha \widehat{v} has been acquired. This is unwanted noise that we must cancel out. To cancel the extra terms we edit ϕ^1\widehat{\phi}_1' accordingly

ϕ^1=ϕ^1αv^\widehat{\phi}_1'' =\widehat{\phi}_1' - \alpha \widehat{v}

because this term is multiplied by yy. Now (Θ1,Θ2,Φ1,Φ2)(\Theta_1'', \Theta_2', \Phi_1'', \Phi_2') satisfy (V1)(V_1') and do not reveal the witness.

Step 2: We edit (V2)(V_2') so that our randomised proof elements can satisfy it. The RHS of (V2)(V_2') is given by

θ1+θ2u^\theta_1'' + \theta_2' \widehat{u}

and this has aquired the additional noise yαy \alpha. We cannot hope to cancel this noise out with Θ2\Theta_2 because of the u^\widehat{u} multiplier. For soundness, we also want to enforce that the noise added in Θ1\Theta_1'' is actually a multiple of yy and does not interfere with the witness. We thus introduce a new proof element that will be paired with yy blinded by an additional randomiser γ\gamma

ϕ^3=αγu^\widehat{\phi}_3 = - \alpha - \gamma \widehat{u}

And therefore, (V2)(V_2'') becomes

skc^1=θ1+θ2u^+yϕ^3(V2) \mathsf{sk} \cdot \widehat{c}_1 = \theta_1'' + \theta_2' \widehat{u} + y \widehat{\phi}_3 \tag{$V_2''$}

Now ϕ^3\widehat{\phi}_3 does not prevent (V2)(V_2') from being satisfied whenever (V2)(V_2'') is satisfied because yy is an unused basis. To make this equation balance we modify Θ2\Theta_2' and get

θ2=θ2+γy\theta_2'' = \theta_2' + \gamma y

and we see (V2)(V_2'') is still satisfied.

Step 3: We look back at (V1)(V_1') with respect to our randomised proof element Θ2\Theta_2''. By substituting this into the RHS of (V1)(V_1')

ϕ^1y+ϕ^2z+θ1v^+θ2^\widehat{\phi}_1'' y + \widehat{\phi}_2' z + \theta_1'' \widehat{v} + \theta_2'' \widehat{\ell}

we see that an additional term γy^\gamma y \widehat{\ell} has been acquired. This is unwanted noise that we must cancel out. To cancel the extra terms we edit ϕ^1\widehat{\phi}_1'' accordingly

ϕ^1=ϕ^1αv^γ^\widehat{\phi}_1 =\widehat{\phi}_1' - \alpha \widehat{v} - \gamma \widehat{\ell}

because this term is multiplied by yy. Now (Θ1,Θ2,Φ1,Φ2)(\Theta_{1}'', \Theta_2', \Phi_1, \Phi_2') satisfy (V1)(V_1') and do not reveal the witness.

Step 4: We edit (V3)(V_3') so that our randomised proof elements can satisfy it. The RHS of (V3)(V_3') is given by

ϕ^1+xϕ^2 \widehat{\phi}_1 + x \widehat{\phi}_2'

and this has aquired the additional noise αv^γl^-\alpha \widehat{v} - \gamma \widehat{l}. To cancel out the extra noise we introduce two new proof elements that will be paired with v^\widehat{v} and l^\widehat{l} respectively, and blind them with β\beta and δ\delta

θ3=α+xβθ4=γ+xδ\theta_3 = \alpha + x \beta \qquad \qquad \theta_4 = \gamma + x \delta

And therefore, (V3)(V_3') becomes

c^2=θ3v^+θ4^+ϕ^1+xϕ^2(V3) \widehat{c}_2 = \theta_3\widehat{v} + \theta_4 \widehat{\ell} + \widehat{\phi}_1 + x \widehat{\phi}_2' \tag{$V_3$}

Now Θ3,Θ4\Theta_3, \Theta_4 does not prevent (V3)(V_3') from being satisfied whenever (V3)(V_3) is satisfied because v^,^\widehat{v}, \widehat{\ell} is an unused basis. To make this equation balance we modify ϕ^2\widehat{\phi}_2:

ϕ^2=ϕ^2βv^δ^\widehat{\phi}_2 =\widehat{\phi}_2' - \beta \widehat{v} - \delta \widehat{\ell}

and we see (V3)(V_3) is still satisfied.

Step 5: We look back at (V1)(V_1') with respect to our randomised proof element ϕ^2\widehat{\phi}_2. By substituting this into the RHS of (V1)(V_1')

ϕ^1y+ϕ^2z+θ1v^+θ2^\widehat{\phi}_1 y + \widehat{\phi}_2 z + \theta_1'' \widehat{v} + \theta_2'' \widehat{\ell}

we see that an additional term βzv^δz^- \beta z \widehat{v} - \delta z \widehat{\ell} has been acquired. This is unwanted noise that we must cancel out. To cancel the extra terms we edit Θ1\Theta_1'' and Θ2\Theta_2'' accordingly

θ1=θ1+βz=θ1+αy+βzθ2=θ2+δz=θ2+γy+δz\begin{array}{c} \theta_1 = \theta_1'' + \beta z = \theta_1' + \alpha y + \beta z \\ \theta_2 = \theta_2'' + \delta z = \theta_2' + \gamma y + \delta z \\ \end{array}

Now (Θ1,Θ2,Φ1,Φ2)(\Theta_{1}, \Theta_2, \Phi_1, \Phi_2) satisfy (V1)(V_1') and do not reveal the witness.

Step 6: We edit (V2)(V_2'') so that our randomised proof elements can satisfy it. The RHS of (V2)(V_2'') is given by θ1+θ2u^+yϕ^3\theta_1 + \theta_2 \widehat{u} + y \widehat{\phi}_3 and this has aquired the additional noise βz+δzu^\beta z + \delta z \widehat{u}.

We shall need to add a proof element which is paired with zz to cancel the noise. We cannot balance any additional randomness that this new element introduces because Θ1\Theta_1 and Θ2\Theta_2 already both have zz components. Thus for our final proof element to not use up a randomiser we instead add a verification equation. See that

βz+δzu^=zx(θ3+θ4u^+ϕ^3)\beta z + \delta z \widehat{u} = \frac{z}{x} ( \theta_3 + \theta_4 \widehat{u} + \widehat{\phi}_3)

We thus introduce a new proof element

ϕ^4=βδu^\widehat{\phi}_4 = - \beta - \delta \widehat{u}

and a verification equation

0=θ3+θ4u^+ϕ^3+xϕ^4(V4) 0 = \theta_3 + \theta_4 \widehat{u} + \widehat{\phi}_3 + x \widehat{\phi}_4 \tag{$V_4$}

Now (V2)(V_2'') becomes

skc^1=θ1+θ2u^+yϕ^3+zϕ^4(V2) \mathsf{sk} \cdot \widehat{c}_1 = \theta_1 + \theta_2 \widehat{u} + y \widehat{\phi}_3 + z \widehat{\phi}_4 \tag{$V_2$}

We do not need to edit (V1)(V_1') or (V3)(V_3) because no proof elements have been edited.

Resulting Verifier Equations: Putting everything together, we have the following eight proof elements

Θ1=pkr1g3αg4βΦ^1=h1r2h3αh4γΘ2=pks1g3γg4δΦ^2=h1s2h3βh4δΘ3=g1αg2βΦ^3=h1αh2γΘ4=g1γg2δΦ^4=h1βh2δ\begin{array}{l l c l} & \Theta_1 = \mathsf{pk}^{r_1} g_3^{\alpha} g_4^{\beta} \quad && \widehat{\Phi}_1 = h_1^{r_2} h_3^{\alpha} h_4^{\gamma}\\ & \Theta_2 = \mathsf{pk}^{s_1} g_3^\gamma g_4^{\delta} && \widehat{\Phi}_2 = h_1^{s_2} h_3^{\beta} h_4^{\delta}\\ & \Theta_3 = g_1^\alpha g_2^{\beta} &&\widehat{\Phi}_3 = h_1^{-\alpha} h_2^{-\gamma}\\ & \Theta_4 = g_1^\gamma g_2^{\delta} &&\widehat{\Phi}_4= h_1^{-\beta} h_2^{-\delta} \end{array}

and 44 verification equations

e(pk,D^1)e(D2CT21,h^1)=e(g3,Φ^1)e(g4,Φ^2)e(Θ1,h^3)e(Θ2,h^4)(V1)e(pk,C^1)=e(Θ1,h^1)e(Θ2,h^2)e(g3,Φ^3)e(g4,Φ^4)(V2)e(C2,h^1)=e(Θ3,h^3)e(Θ4,h^4)e(g1,Φ^1)e(g2,Φ^2)(V3)1=e(Θ3,h^1)e(Θ4,h^2)e(g1,Φ^3)e(g2,Φ^4)(V4)\begin{array}{r c r} e(\mathsf{pk}, \widehat{D}_1) e(D_2 \cdot \mathsf{CT}_2^{-1}, \widehat{h}_1) & = e(g_3, \widehat{\Phi}_1)e(g_4, \widehat{\Phi}_2) e(\Theta_1, \widehat{h}_3) e(\Theta_2, \widehat{h}_4) & \hspace{1cm} (V_1) \\ e(\mathsf{pk}, \widehat{C}_1) & = e(\Theta_1, \widehat{h}_1) e(\Theta_2, \widehat{h}_2)e(g_3, \widehat{\Phi}_3) e(g_4, \widehat{\Phi}_4) & (V_2) \\ e(C_2, \widehat{h}_1) & = e(\Theta_3, \widehat{h}_3) e(\Theta_4, \widehat{h}_4) e(g_1, \widehat{\Phi}_1) e(g_2, \widehat{\Phi}_2) & (V_3) \\ 1 & = e(\Theta_3, \widehat{h}_1) e(\Theta_4, \widehat{h}_2) e(g_1, \widehat{\Phi}_3) e(g_2, \widehat{\Phi}_4) & (V_4) \end{array}