An even more efficient version

To put things into perspective, our latest protocol version requires sharing 6 polynomials of degree at most $d=3$ (quotients are typically shorter), and the validator has to still do at most 3 multiplications per each one of the 3 equality checks. That is a communication cost of about $3\ast 6$ field elements and $3\ast 3$ field element multiplications. In general this would be ca. $d\ast 6$ field elements in communication and $3\ast d$ field multiplications for the $d$-th Fibonacci number (rounding this to the number of padded rows as discussed before). This does not seem quite useful given that only about $d$ additions would allows us to compute the $d$-th Fibonacci number directly!

But there is a goal behind our strategy. Our goal is to make both the communication and the verification constant ($O(1)$) for circuits with many gates! To achieve this we need a very useful primitive called a Polynomial Commitment Scheme. In particular, we are going to use the method called KZG. This method relies on pairings over elliptic curves and to keep this notebook as lean as possible, we are preparing a separate tutorial on this topic.

In the following we simply recap some fundamental properties of the needed ingredients while keeping our goal on sight.

What do we want to achieve? In a nutshell what we want to achieve is the following: We want to completely delegate computation of the circuit to the processor, and as before, also the interpolation of the column polynomial and the computation of the quotients. But the twist is, we will not ask for a full copy of a given polynomial $f(x)$, but just a very short and constant size piece of information that we call a commitment $c_f=\mathsf{\text{commitment}}(f(x))$. With this commitment, we can at a later stage challenge the validator to evaluate $f(\gamma )=\alpha$. We will be able to check on our whether indeed $f(\gamma )=\alpha$ by using $\gamma ,\alpha$ and the commitment $c_f$ using a function $\mathsf{\text{verify}}(\alpha ,\gamma ,c_f)$.

What this accomplishes:

• Instead of sharing a $d$-size vector for each polynomial over the network, we only share two elements: $c_f\in E$, where $E$ is an elliptic curve, and $\alpha \in {\mathbb{F}}_p$.
• A malicious or misbehaving processor $P$ cannot adapt to the interactive challenge $\gamma$ since it has already commited to a polynomial before seeing the challenge. This gives the validator confidence that the value was correctly computed.
• We can directly perform the constraint checks $f(\gamma )=Q(\gamma )\cdot Z(\gamma )$ in constant time, regardless of the number of gates in the circuit (that is, the polynomial $d$ of the interpolating polynomial). Certainly there are some upper bounds to the size of a circuit and we will come back to this later.

Given that by making this protocol more efficient we have to make it more resilient to misbehaving processors, we are going to call $P$ a prover and $V$ a verifier from now on.

Cryptographic Pairings

The first ingredient for our new protocol version will be a suitable elliptic curve pairing. We will give you some precomputed functions, but you may reconstruct them on your own.

We need a mapping:

$$e:{\mathbb{G}}_{\mathbb{1}}\times {\mathbb{G}}_{\mathbb{2}}\to {\mathbb{G}}_{\mathbb{t}}$$

for additive cyclic groups $({\mathbb{G}}_{\mathbb{1}},+)$ and $({\mathbb{G}}_{\mathbb{2}},+)$ and multiplicative $({\mathbb{G}}_{\mathbb{t}},\ast )$. Note that typically the first two groups are additive (since they are subgroups of an elliptic curve) and the destination group is multiplicative (usually defined over a field).

The mapping $e$ we are looking for is "bilinear", that means:

$$e(P+P^{\prime },Q)=e(P,Q)\ast e(P^{\prime },Q)$$$$e(P,Q+Q^{\prime })=e(P,Q)\ast e(P,Q^{\prime })$$

To construct secure pairings, it is important to chose the groups in a particular way which motivates choosing isomorphic but disjoint ${\mathbb{G}}_{\mathbb{1}},{\mathbb{G}}_{\mathbb{2}}$ which can be found as subgroups of an elliptic curve over a finite field extension $E({\mathbb{F}}_{q^k})$ and ${\mathbb{G}}_{\mathbb{t}}$ a subgroup of ${{\mathbb{F}}^{\mathbb{\ast }}}_{q^k}$. We are not going to explain this in more depth but if you are curious check Pairings for Beginners by Craig Costello.

import kzg
def e(P,Q):
    #Base field for BN254
    q = 21888242871839275222246405745257275088696311157297823662689037894645226208583
    #Number of points on BN254
    n = Integer(21888242871839275222246405745257275088548364400416034343698204186575808495617)
    k = 12
    t = 6*pow(4965661367192848881,2)+1
    return P.ate_pairing(Q, n, k, t,q)

P = kzg.P
Q = kzg.Q

show("P:",P)
show("Q:",Q)
show(e(P,Q))

Exercise 6

Check that the provided $e$ function is bilinear by randomly sampling an integer $s$ and multiplying over the additive subgroups:

$$e([s]\cdot P,Q)=e(P,[s]\cdot Q)=e(P,Q{)}^s$$

#Solve here!
s=Integer(randrange(1, p))