4. Encrypting QAP

Encrypting QAP

We now have:

$$(U.a)(V.a) = (W.a) +h(x)t(x)$$

Irrespective of the fact that this is expressed in matrix form, its really an equality between polynomials - and said polynomials will be evaluated at some random point. If the equality holds upon evaluation, verification is cleared.

$$(29.5x^2 - 87.5x + 61)( -x^2 + 4x) = 84.5x^2 - 246.5x +171 + h(x)t(x)$$

Currently there are two problems we need to address:

1. The first problem with this is that its not zero-knowledge; we need to encrypt it via elliptic curve points

2. The second is that the prover could create a proof based on 3 arbitrary values such that a.b = c, with no relation to the original claim.

   1. Remember, the only thing the verifier does is check equality of the proof through some elliptic curve and mapping action.

   2. For a trivial proof of 1*1 = 1, the verifier’s computations would clear and reflect that the equality is correct and consistent.

In this section we will address the first problem of encryption. Elliptic curve generator points are used to obfuscate the witness values provided by the user.

Consider U.a

After substituting the witness values, the polynomial is evaluated at some random value, tau(τ).

• tau(τ) is generated during the trusted setup phase

• Now we could proceed to evaluate the polynomial at x = τ, to verify the equality

• However, this would not be very ZK of us. Therefore, instead of x = τ, we will use x = τ[G]

In the case of U.a, $x = τ[G]_{1}$

$$(U.a) = 29.5x^2 - 87.5x + 61 = 29.5[τ^2G_{1}] - 87.5[τG_{1}] + 61$$

• where G1 is the elliptic curve generator point of group 1.

In similar vein,

$$(V.a) = -x^2 + 4x = -[τ^2G_{2}] + 4[τG_{2}]$$

$$(W.a) = 84.5x^2 - 246.5x +171 = 84.5[τ^2G_{1}] - 246.5[τG_{1}] + 171$$

From this arrangement, is should be clear to the reader that

$$(U.a)(V.a) = (W.a) + h(x)t(x) \newline [A]_1 * [B]_2 = [C]_1 + h(x)t(x)$$

• where A,B and C are elliptic curve points of order 1, 2 and 1 respectively.

Therefore, we will need to transform h(x) and t(x) into elliptic curve points as well

• t(x) is evaluated within the trusted setup.

• h(x), however, is handled by the prover.

Evaluating t(x)

Since we need to do point addition with [C]/(W.a), we have to use G1.

$$t(x) = t(τG_1) = [(τ-1)(τ-2)(τ-3)]G_1 \newline also \space expressed \space as \newline t(τ) * G_1 = [T]_1$$

Essentially, we are just doing point (scalar) multiplication of the G1 point. (Or addition; all multiplication is addition if you are audacious enough).

Evaluating h(x)

h(x) is evaluated as such:

$$h(x)t(x) = h([T]_1) = h([t(τ) * G_1]) = [HT]_1$$

What this means is that h(x) is not independently evaluated on its own like t(x). Rather it is evaluated by requiring as input: $(τ^0[T_1], τ^1[T_1], τ^2[T_1], ...)$

Trusted setup: powers of tau

The trusted setup generates both a proving key and a verifier key. We will talk about the verifier key in a later section.

The proving key, which is generated at this stage comprises of the following powers of tau:

1. $(τ^0[G_1], τ^1[G_1], τ^2[G_1], ...)$ → for obtaining [A] and [C]

2. $(τ^0[G_2], τ^1[G_2], τ^2[G_2], ...)$ → for obtaining [B]

3. $(τ^0[T_1], τ^1[T_1], τ^2[T_1], ...)$ → for obtaining [HT]

The degree to which tau is raised is dictated by the polynomial which is in turn determined by the number of constraints.

Using the proving key and the witness values provided by the user, the prover will generate elliptic curve points: [A], [B], [C], [HT].

This generated proof is handed to the verifier, which simply checks for equality after raising the points to the G12 group via bilinear mapping.

Like so:

$$pairing([A]_1, [B]_2) \stackrel{?}{=} pairing([C]_1, [G]_2)$$

Note that here, [C] = [C] + [HT]; all of which are group 1 EC points.

---

• τ, Tau is not communicated to the prover

• Prover receives proving key, which are the powers of tau

• Tau is therefore obfuscated through ECC and the discrete log problem.

• Tau is toxic waste that must be disposed; cannot be revealed. If revealed will allow for creation of fake proofs.

---