%load_ext autoreload
%autoreload 2

Groth16 in Klefki

Bilinear groups

We will work over bilinear groups \((p,\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_T,e,g,h)\) with the following properties:

• \(\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T\) are groups of prime order p

• The pairing \(e\): \(\mathbb{G}_1x\mathbb{G}_2 \rightarrow \mathbb{G}_T\) is a binlinear map

• \(g\) is a generator for \(\mathbb{G}_1\), \(h\) is a generator for \(\mathbb{G}_2\) and \(e(g, h)\) is a generator for \(\mathbb{G}_T\)

• There are efficient algorithms for computing group operations, evaluating the bilinearmap, deciding membership of the groups, deciding equality of group elements andsampling generators of the groups. We refer to these as the generic group operations.

from klefki.curves.barreto_naehrig.bn128 import BN128ScalarFP as FP, ECGBN128 as ECG
from klefki.algebra.utils import randfield

g = ECG.G1
h = ECG.G2

We write \([a]_1\) for \(g^a\), \([b]_2\) for \(h^b\), and \([c]_T\) for \(e(g, h)^c\). A vector of group elements will be represented as \([\mathbf{a}]_i\). We defined dot product as \([\mathbf{a}]_1 \circ [\mathbf{b}]_2 = [\mathbf{a}\circ \mathbf{b}]_T\)

NIZK

let \(R\) be a relation generator that given a security parameter \(λ\) in unary returns a polynomial time decidable binary relation \(R\). For pairs \((\phi, \omega) \in R\).

For pairs \((\phi, \omega) \ in R\), we call \(\phi\) the statement and \(\omega\) the witness. We defined \(R_{\lambda}\) to be the set of possible relations \(R \). The relation generator may also output someside information, an auxiliary input \(z\), which will be given to the adversary.

An efficient prover publicly verifiable non-interactive argument for \(R\) is a quadruple of probabilistic polynomial algorithms \((Setup,Prove,Vfy,Sim)\) such that

• \((\sigma,\tau) \leftarrow Setup(R)\): The setup produces a common reference stringσand a simulationtrapdoorτfor the relationR

• \(\pi \leftarrow Prov(R, \sigma, \phi, \omega)\):The prover algorithm takes as input a common reference string σ and \((φ,w)∈R\) and returns an argument π.

• \(0/1 \leftarrow Vfy(R, \sigma, \phi, \pi)\): The verification algorithm takes as input a common referencestring σ, a statement φ and an argumentπand returns 0 (reject) or 1 (accept).

• \(\pi \leftarrow Sim(R, \tau, \phi)\): The simulator takes as input a simulation trapdoor and statementφand returns an argument π.

QAP

Given \(n\) equations we pick arbitrary distinct \(r_1,\cdots,r_n \in \mathbb{F}\) and define

\[t(x) = \prod_{q=1}^n (x - r_q)\]

\[\sum_{i=0}^m a_i u_i(X) \circ \sum_{i=0}^m a_i v_i(X) = \sum_{i=0}^m a_i w_i(X) + h(X)t(X)\]

we will be working with quadratic arithmetic programsRthat have thefollowing description

\[R = (p, \mathbb{G}_1,\mathbb{G}_2, \mathbb{G}_T, e, g, h, l, \{u_i(X), v_i(X), w_i(X)\}_{i=0}^n, t(X))\]

with \(|p|=\lambda\). The realation defineds a field \(\mathbb{Z}_p\) and a language of statement \((a_i,\cdots, a_l) \in \mathbb{Z}_p^l\) and witness \((a_{l+1}, \cdots, a_m) \in \mathbb{Z}_p^{m-l}\) such that with \(a_0=1\)

from collections import namedtuple

RationalGenerator = namedtuple("RelationGenerator", ["F", "G1", "G2", "Gt", "e", "g", "h", "l", "U", "V", "W", "T"])

from klefki.zkp.r1cs import R1CS
from klefki.zkp.qap import QAP

@R1CS.r1cs(FP)
def f(x, k, c):
    y = x + c + k
    return y ** 3

qap = QAP(f.A, f.B, f.C)
U, V, W, T = qap.qap
a = f.witness(FP(89), FP(8), FP(8))

R = RationalGenerator(FP, ECG, ECG, ECG, ECG.e, ECG.G1, ECG.G2, 4, U, V, W, T)

\((\sigma,\tau) \leftarrow Setup(R)\):

Pick \(\alpha, \beta, \gamma, \delta, x \leftarrow \mathbb{Z}_P^*\), Define \(\tau = (\alpha, \beta, \gamma, \delta, x)\) and compute \(\sigma = ([\mathbf{\sigma_1}]_1, [\mathbf{\sigma_2}]_2\) where

\[\begin{split}(\mathbf{\sigma}_1, \mathbf{\sigma}_2) = \left( \left(\begin{split} \alpha, \beta, \delta, \{x^i\}_{i=0}^{n-1}, \left\{\frac{\beta u_i(x) + \alpha v_i (x) + w_i (x)}{\gamma} \right\}_{i=0}^l \\ \left\{ \frac{\beta u_i (x) + \alpha v_i(x) + w_i(x)}{\delta} \right\}_{i=l+1}^m, \left\{\frac{x^i t(x)}{\delta} \right \}_{i=0}^{n-2} \end{split}\right) , \left(\beta, \gamma, \delta, \{x^i\}^{n-1}_{i=0} \right) \right)\end{split}\]

from typing import Iterable, Tuple, Type
from operator import add
from functools import reduce

def setup(R, m) -> Tuple[Iterable, Tuple[R.G1, R.G2]]:
    tau = alpha, beta, delta, gamma, x = \
        randfield(R.F), randfield(R.F), randfield(R.F), randfield(R.F), randfield(R.F)
    n = R.U[0].degree
    sigma_1 = [alpha, beta, delta] + \
              [x ** i for i in range(0, n)] + \
              [(R.U[i](x) * beta + R.V[i](x) * alpha + R.W[i](x)) / gamma  for i in range(0, R.l)] + \
              [(R.U[i](x) * beta + R.V[i](x) * alpha + R.W[i](x)) / delta  for i in range(R.l, m)] + \
              [(x ** i * R.T(x)) / delta for i in range(0, n-1)]
    sigma_2 = [beta, gamma, delta] + \
              [x**i for i in (0, n)]

    sigma = ([R.g @ s for s in sigma_1], [R.h @ s for s in sigma_2])
    return tau, sigma

tau, sigma = setup(R, len(a))

\(\pi \leftarrow Prov(R, \tau, \sigma, a_1, \cdots, a_m)\)

Pick \(r, s \leftarrow \mathbb{Z}_p\) and compute \(\pi = ([A]_1, [C]_1, [B]_2\) where

\[A = \alpha + \sum_{i=0}^m a_i u_i(x) + r\delta\]

\[B = \beta + \sum_{i=0}^m a_i v_i(x) + s\delta\]

\[C = \frac{\sum_{i=l+1}^m a_i(\beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x)t(x)}{\delta} + As + Br - rs\delta\]

H = qap.H(a)

def prov(R, tau, sigma, a, r=None, s=None) -> Tuple[R.G1, R.G1, R.G2]:
    r = r or randfield(R.F)
    s = s or randfield(R.F)
    alpha, beta, delta, gamma, x = tau
    m = len(a)
    A = alpha + reduce(add, [a[i] * (R.U[i](x)) for i in range(0, m)]) + r * delta
    B = beta + reduce(add, [a[i] * (R.V[i](x)) for i in range(0, m)]) + s * delta
    C = (reduce(add,
                [a[i]*(beta * (R.U[i](x)) + alpha * (R.V[i](x)) + R.W[i](x)) for i in range(R.l, m)]) \
        + H(x) * R.T(x)) / delta \
        + (A * s + B * r - r * s * delta)
    return (R.g @ A, R.g @ C, R.h @ B)

pi = prov(R, tau, sigma, a, r, s)

\(0/1 \leftarrow Vfy(R, \tau, a_1, \cdots, a_l, \pi)\)

Parse \(\pi = ([A]_1, [C]_1, [B]_2 \in G_1^2 x G_2\). Accept the proof iff:

\[[A]_1 \circ [B]_2 = [\alpha]_1 \circ [\beta]_2 + \sum_{i=0}^l a_i \left[ \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} \right]_1 \circ [\gamma]_2 + [C]_1 \circ [\delta]_2\]

def vfy(R, tau, a, pi):
    alpha, beta, delta, gamma, x = tau
    A_1, C_1, B_2 = pi
    lhs = R.e(A_1, B_2)
    D = R.g @ (reduce(add, [
                a[i] * (beta * R.U[i](x) + alpha * R.V[i](x) + R.W[i](x))
                for i in range(0, R.l)]) / gamma)
    rhs = R.e(R.g @ alpha, R.h @ beta) * \
          R.e(D, R.h @ gamma) * \
          R.e(C_1, R.h @ delta)
    return lhs == rhs

vfy(R, tau, a, pi)

True

Explain

On \(Prov\) phase:

\begin{aligned} A &= \alpha + \sum_{i=0}^m a_i u_i(x) + r\delta \\ &= \alpha + A_{qap} + r\delta \end{aligned}

\begin{aligned} C &= \frac{\sum_{i=l+1}^m a_i(\beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x)t(x)}{\delta} + As + Br - rs\delta\\ &= \frac{1}{\delta} \sum_{i=l+1}^m \left(a_i(\beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x)t(x)\right) + As + Br - rs\delta \\ &=\frac{\beta}{\delta}\sum_{i=l+1}^m a_i u_i(x) + \frac{\alpha}{\delta} \sum_{i=l+1}^m a_i v_i(x) +\frac{1}{\delta} w(x)t(x)+ \frac{1}{\delta} \sum_{i=l+1}^m h(x)t(x) + As + Br - rs \delta \\ &=\frac{\beta}{\delta}A_{qap_{l+1, m}}+ \frac{\alpha}{\delta} B_{qap_{l+1, m}} + \frac{1}{\delta} H_{qap}T_{qap} + s\alpha + sA_{qap} + sr\delta + r\beta + B_{qap}(x) + rs\delta - rs \delta \\ &=\frac{\beta}{\delta}A_{qap_{l+1, m}}+ \frac{\alpha}{\delta} B_{qap_{l+1, m}} + \frac{1}{\delta} C_{qap_{l+1, m}} + \frac{1}{\delta} H_{qap}T_{qap} + s\alpha + r\beta + sA_{qap} + rB_{qap} + sr\delta \end{aligned}

A_1, C_1, B_2 = prov(R, tau, sigma, a, r, s)
alpha, beta, delta, gamma, x = tau

A_qap, B_qap, C_qap, T_qap, H_qap = qap.proof(x, a)
assert A_qap * B_qap == C_qap + T_qap * H_qap

A_qap_l2m, B_qap_l2m, C_qap_l2m, T_qap_l2m, H_qap_l2m = qap.proof(x, a, R.l, len(a))

A_qap_02l, B_qap_02l, C_qap_02l, T_qap_02l, H_qap_02l = qap.proof(x, a, 0, R.l)

assert A_qap_l2m + A_qap_02l == A_qap

assert A_1 == R.g @ (alpha + A_qap + r * delta)
assert B_2 == R.h @ (beta + B_qap + s * delta)
assert C_1 == R.g @ (beta / delta * A_qap_l2m + alpha/delta * B_qap_l2m + \
                     C_qap_l2m / delta + T_qap * H_qap / delta + \
                    s * alpha + r * beta + s * A_qap + r * B_qap + s * r * delta)

On Vry phase, for RHS

\begin{aligned} Rhs &= \underline{[\alpha]_1 \circ [\beta]_2}_{P1} + \underline{\sum_{i=0}^l a_i \left[ \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} \right]_1 \circ [\gamma]_2}_{P2} + \underline{[C]_1 \circ [\delta]_2}_{P3}\\\\\\ P1 & = [\alpha]_1[\beta]_2 = [\alpha \beta]_1[1]_2\\ P2 &= \sum_{i=0}^l a_i \left[ \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} \right]_1\\ &= \left[ \frac{\beta}{\gamma} A_{qap_{0,l}} + \frac{\alpha}{\gamma} B_{qap_{0,l}} + \frac{1}{\gamma}C_{qap{0,l}} \right]_1[\gamma]_2\\ &= [\beta A_{qap_{0,l}} + \alpha B_{qap_{0,l}} + C_{qap_{0, l}}]_1[1]_2\\\\\\ P3 &= [\frac{\beta}{\delta}A_{qap_{l+1, m}}+ \frac{\alpha}{\delta} B_{qap_{l+1, m}} + \frac{1}{\delta} C_{qap_{l+1, m}} + \frac{1}{\delta} H_{qap}T_{qap} + s\alpha + r\beta + sA_{qap} + rB_{qap} + sr\delta]_1[\delta]_2 \\ &= [\beta A_{qap_{l+1, m}}+\alpha B_{qap_{l+1, m}}+C_{qap_{l+1, m}}+H_{qap}T_{qap}+s\alpha\delta + r\beta\delta + s\delta A_{qap} + r\delta B_{qap} + sr\delta^2]_1[1]_2 \\ \end{aligned}

\begin{aligned} P1 + P2 + P3 &= [\alpha\beta + \beta A_{qap_{0,l}} + \alpha B_{qap_{0,l}} + C_{qap_{0, l}} + \beta A_{qap_{l+1, m}}+\alpha B_{qap_{l+1, m}}+C_{qap_{l+1, m}}+H_{qap}T_{qap}+s\alpha\delta + r\beta\delta + s\delta A_{qap} + r\delta B_{qap} + sr\delta^2]_1[1]_2\\ &= [\alpha\beta + \beta A_{qap} + \alpha B_{qap} + C_{qap} + H_{qap}T_{qap} + s\alpha\delta + r\beta\delta + s\delta A_{qap} + r\delta B_{qap} + sr\delta^2]_1 [1]_2 \end{aligned}

on LHS

\begin{aligned} Lhs &= [A]_1 \circ [B]_2 \\ &= [\alpha + A_{qap} + r\delta]_1 \circ [\beta + B_{qap} + s\delta]_2\\ &= [(\alpha + A_{qap} + r\delta)(\beta + B_{qap} + s\delta)]_1[1]_2 \end{aligned}

We knows that

\[A_{qap}B_{qap} = C_{qap} + H_{qap}C_{qap}\]

so

\begin{aligned} Rhs &= [\alpha\beta + \beta A_{qap} + \alpha B_{qap} + A_{qap}B_{qap} + s\delta A_{qap} + r\delta B_{qap} + s\alpha\delta + r\beta\delta + sr\delta^2]_1 [1]_2\\ &= [(\alpha + A_{qap} + r\delta)(\beta + B_{qap} + s\delta)]_1[1]_2 \end{aligned}

\[Lhs = Rhs\]