# SHPLONK
*Thanks to Zac Williamson, Ariel Gabizon, Georgios Konstantopoulos, Ben Edgington and Tom Waite for various comments and suggestions.*
## Background
Those of you who have read the [PLONK](https://eprint.iacr.org/2019/953.pdf) paper will be aware that it involves a batched polynomial commitment scheme that extends the ["Kate" KZG10](https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf) scheme.
I'm writing this article for those of you who want to get to grips with [SHPLONK](https://eprint.iacr.org/2020/081.pdf) without sifting through wads of research papers.
### Why do we need PCSs?
**Polynomial Commitment Schemes** are a sort of mathematical scaffolding that allow cryptographers to load a large amount of information into a single elliptic curve point -- a single 'number'. This is very important on blockchains, especially ones where storing data is expensive (e.g. Ethereum).
If you did this in a really naïve way, for example just hashing all the data together e.g. $H(a_0| ... | a_d)$, you would be unable to test any arithmetic at all inside that 'mulsh' of information, and to prove you'd committed to it you would therefore have to reveal / transmit all those $a_i$ values.
Polynomial commitment schemes use polynomials almost like a vector space -- each 'dimension' is 'loaded' with one of the numbers in the 'trace' of computing a programme (by 'trace', we mean the sequence of all inputs, intermediary values and outputs computed/used in the course of running the algorithm concerned concerned).
More importantly, the *polynomial* bit is useful because it allows the 'uploaded' numbers to stay mathematically separated 'inside' that single committed number, and in such a way that mathematical relations can be tested there.
### Authors
The SHPLONK scheme was created by the following researchers:
- Dan Boneh, Professor of CS at [Stanford University](https://www.stanford.edu/)
- Justin Drake, Researcher at [Ethereum Foundation](https://www.ethereum.org/)
- Ben Fisch, PhD student at [Stanford University](https://www.stanford.edu/)
- Ariel Gabizon, Chief Scientist at [Aztec Protocol](https://www.aztecprotocol.com/)
### Prior Knowledge
This article assumes good familiarity with the theory of groups and a very basic understanding of how elliptic curves can be turned into additive groups. One also needs to understand the concept of a bilinear map -- in the context of elliptic curves, this is known as a 'pairing'.
For a quick-blast primer, look no further than this article:
[Exploring Elliptic Curve Pairings (Vitalik Buterin)](https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627)
## Part 1. Kate Refresher
The 2010 Kate scheme (properly called the Kate-Zaverucha-Goldberg scheme) allows a prover to create some data which binds them to an evaluation of a polynomial $f(X) = \sum_{i=0}^k a_i X^i$ in a provable fashion.
Creating that data is called a 'commitment'.
### Role of the Reference String
I referred earlier to PCSs as sort of 'mathematical scaffolding'.
What I was describing in particular is a list of precomputed elliptic-curve points known as a **Reference String** -- in the case of Kate, a list of successive powers of an unknown quantity $\alpha$, such as that generated in the recent AZTEC [Ignition Ceremony](https://www.aztecprotocol.com/ignition):
\begin{align*}
\langle g, g^\alpha, ... g^{\alpha^t} \rangle \in \mathbb{G}^{t+1}
\end{align*}
Where $\mathbb{G}$ is some elliptic curve group.
There is a big assumption we rely on that even if the whole world knows these elliptic curve points $g$, $g^\alpha$, ... $g^{\alpha^t}$ etc, one can't back out $\alpha$ - it's known as the **$t$-Strong Discrete Log Assumption**. It sounds hard, but it's basic to state: given this string of elliptic curve numbers, it's computationally infeasible to find $\alpha$.
That's quite eyebrow-raising if you've not seen it before. Actually, when $t$ gets very big (~$2^{40}$ for Aztec's chosen curve BN254) the SRS provides so much structural information that it does indeed start to corrode the curve's security.
Anyway, this Reference String provides us with little monomial blocks of the form $g^{\alpha^i}$, from $i=0$ (the generator point) right up to $i=d$, where $d$ is the degree of the biggest polynomials we want this Reference String to be used for.
:::spoiler On the Length of the Reference String
> **Length of Reference String:** These polynomials 'represent' the data to which we've committed (often, this data will be the trace of numbers created in performing a computation -- e.g. the execution of a smart contract -- that is, the inputs, the intermediate values, and the outputs). The more and more terms $g^{\alpha^i}$ we include in our Reference String on Day 1, the greater the complexity of computations this Reference String can support. For example, a Reference String just comprising $\langle g^{\alpha^0}, g^{\alpha^1}, g^{\alpha^2} \rangle$ can never help us 'store' more than three numbers - most computations will create many more numbers in the course of execution than 3! So when you set your number $d$, you need to be really sure it's big enough to support all conceivable computations.
:::
Along with polynomial coefficients, these little blocks can be used to create encrypted evaluations of a given polynomial $f(X):=\sum_{i=1}^n a_i.X^i$ in the obvious way, by just exponentiating those blocks by the coefficients of $f(X)$, and multiplying them all together:
\begin{align*}
g^{f(\alpha)} = g^{a_0 + a_1.\alpha + a_2.\alpha^2 + ... a_d.\alpha^d} = g^{a_0}.g^{a_1.\alpha}... g^{a_d.\alpha^d} = (g)^{a_0}.(g^{\alpha^1})^{a_1}...(g^{\alpha^d})^{a_d}
\end{align*}
And this is where **polynomial commitment scheme** begins -- the Prover has now created a 'commitment' to a polynomial. It has bound the prover to *this particular polynomial* (so they can't change their mind later on).
Using the Reference string, the Prover had enough building blocks to form $g^{f(\alpha)}$, so long as $deg(f) \leq t$, the maximum power $g^{\alpha^t}$ in the Reference String. And in doing so, their first stake is in the ground, and the tent can't be pitched anywhere else (pictorial analogy to follow shortly).
### A Mental Image
So often a good picture can be instructive.
The image I tend to have in mind for polynomial commitment schemes is pitching a tent. You start by putting in the central post, which roots the tent -- 'committing' at the unmanipulable, unknowable value $\alpha$.
To make a proof, you tie a number of guy ropes (different evaluation points) -- as many as are required to support the structure of the canopy (the zero knowledge proving scheme relying on this commitment scheme).
Some schemes may only require one such point (and the analogy is found to be a bit flimsy -- it would be an odd-looking tent!). Others may require two or more.
![Picturing Polynomial Commitment Schemes](https://i.imgur.com/eW5SxIt.png)
### 1. Commitment
>The prover starts by 'committing' to their chosen polynomial, by evaluating $f$ at a value they don't know and can't influence -- for this they use the Reference String
How do you commit to a value you don't know? Well, we can commit to the polynomial evaluated at this mystery number $\alpha$ whilst that number is inside the exponent of the point $g$. After all, we know the $i^{th}$ powers:
\begin{align*}
C = g^{f(\alpha)} = \prod (g^{\alpha^i})^{a_i}
\end{align*}
So this number is the value that $f$ takes at $\alpha$, but encrypted as an elliptic curve point.
### 2. Opening
>Prove that inscrutable $C$ value actually represents a polynomial in $\alpha$, the secret setup value
Sometime later after the Commitment was published, the Verifier says -- "now, prove your original commitment $C$ really was the encrypted valuation of some polynomial at $\alpha$".
In fact, says the Verifier, here's a point $\beta$ at which to make your proof (which is with almost certainty $\neq \alpha$).
The Prover does a quick calculation which P could only do if $C$ was really $g^{f(\alpha)}$:
\begin{align*}
\psi_\beta (\alpha) = \frac{f(\alpha) - f(\beta)}{\alpha - \beta}
\end{align*}
The observation of Kate here is the following -- given a polynomial $f(X)$, if one evaluates it at some other point $\beta$ then $f(X) - f(\beta)$ is divisible by $X-\beta$. This is obvious because $f(X)|_{X=\beta} - f(\beta) = 0$.
:::spoiler Another way to think about this
> You can also think of this as 'deleting the constant term' -- note that $f(X) - f(\beta) = \sum a_iX^i - a_i.\beta^i$. Now for $i=0$ this is just $a_0 - a_0 = 0$ and all the other terms are of the form $a_i (X^i - \beta^i)$. And $X - \beta$ is a factor of each of these. So the whole thing is divisible by $X-\beta$.
:::
Now, the Prover must provide the Verifier with the following information:
\begin{align*}
\langle \beta, f(\beta), g^{\psi_\beta(\alpha)} \rangle
\end{align*}
Now, if $f(\beta)$ isn't the claimed evaluation, we have a problem -- because then $g^{\psi_{\beta}(\alpha)}$ will contain negative monomial powers (because of that $\alpha - \beta$ term in the denominator). There are no negative powers in the reference string by definition! We'll discuss a bit further in the next section.
### 3. Verify
> The computation the Verifier (read: smart contract) must do to check the proof is correct -- more precisely, they must check the relationship between the original commitment $C$ and the quotient $g^{\psi_\beta (\alpha)}$.
It is then quite a simple matter for the Verifier to check that the following holds:
\begin{align*}
e(C, g) \stackrel{?}{=} e(g^{\psi_\beta(\alpha)}, g^\alpha. g^{-\beta}).e(g,g)^{f(\beta)}
\end{align*}
Hum. Why?
What we're trying to do is to work out whether the Prover successfully divided through the polynomial $(f(X) - f(c))$ by the linear term $(X-c)$ with no remainder -- and recall that comparing factors is exactly what pairings do.
Take another look -- the left hand side of the equation is:
\begin{align*}
e(C, g) = e(g^{f(\alpha)}, g) = e(g, g)^{f(\alpha)}
\end{align*}
Ok, so that's a constituent bit of the more complicated term $\psi_\beta (\alpha) = \frac{f(\alpha)-f(\beta)}{\alpha - \beta}$. And the right hand side is:
\begin{align*}
e(g^{\psi_\beta(\alpha)}, g^{\alpha - \beta}).e(g, g)^{f(\beta)} = e(g,g )^{\psi_\beta(\alpha).(\alpha - \beta)}.e(g, g)^{f(\beta)} = e(g,g )^{\frac{f(\alpha) - f(\beta)}{\alpha - \beta}.{(\alpha - \beta)}}.e(g, g)^{f(\beta)}
\end{align*}
-- which you can see reduces to $f(\alpha)$ in the exponent.
:::spoiler Something that may be gnawing at you
- I'm uncomfortable about this. I thought $\mathbb{G}$ was a prime cyclic group, i.e. we can think of the numbers in the exponent as elements of $\mathbb{Z}_r$, some prime $r$?
- Yes, that's right
- Well, $\mathbb{Z}_r$ is then a field -- multiplicative inverses everywhere
- That's also right
- So what exactly am I proving by dividing out by this $\alpha - \beta$ term? So long as they're not equal, no problem?
- Actually, without access to this linear-division argument, there's a huge problem. Remember $\alpha$ has only ever been served to you in encrypted form, as $g^\alpha$ etc. So you could only perform the division by knowing the polynomial result. Remember always that $\alpha$ is locked inside this unwieldy elliptic curve point, which means you can't divide nor multiply by $\alpha$ - only add.
:::
### 4. Breathe
Take stock -- what have we just done?
- The **Prover** committed to a polynomial using the Reference String (i.e. gluing together terms of the form $g^{\alpha^i}$, exponentiating by the polynomial $f$'s coefficients to make $g^{f(\alpha)}$)
- The **Verifier** said 'hang on, how do I know you've committed to any kind of polynomial'? Please evaluate this thing at a point of my choosing $\beta$, and come back to me and prove they both evaluate the same polynomial
- The **Prover** comes back with two items -- the evaluation $f(\beta)$ and an elliptic curve point evaluated at the difference between the evaluations $f(\alpha)$ and $f(\beta)$, divided out by the linear term $(\alpha - \beta)$
- The **Verifier** then uses a nice(ish) pairings equation to check this computation was done correctly inside the exponent of $g$
Notice one very important thing -- when the Verifier was running their checks, they had to use the first element from the Reference String $g^\alpha$. This means that not only is the Prover proving they can find this solution, but that it was created out of a degree 1 or larger polynomial in $\alpha$.
In other words, the Prover showed the 'polynomialness' of the thing which was originally committed to.
## Part 2. SHPLONK
SHPLONK is a polynomial scheme built to allow a single group element to be used to prove that not just one, but several polynomials $\{f_i(X) \in \mathbb{F}_{q}: i\in [k]\}$ have each been evaluated over a set of points $S_i \subset \mathbb{F_{q}}$ bespoke to each of those polynomials.
This is a heavy-duty generalisation because it allows each polynomial to have its own 'evaluation set', but there are certainly situations (such as in PLONK) where one wants to commit to some polynomials at (say) two points, whilst evaluating others at one point.
The important thing is -- we'd like our proof to consist of just one single elliptic curve group point, proving the evaluation of all those polynomials at all those evaluation points.
### Before Starting
#### 1. Symmetric $\rightarrow$ Asymmetric Pairings
We're now going to make our notation 'grown up', and move to asymmetric pairings (which is the recommended setting for Kate as well as SHPLONK). What does that mean?
Well a symmetric pairing is of the form:
\begin{align*}
e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T
\end{align*}
And an asymmetric pairing is of the form:
\begin{align*}
e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T
\end{align*}
Where $\mathbb{G}_1 \neq \mathbb{G}_2$, but both are elliptic curve groups (and often will be closely related to one another).
#### 2. Exponential $\rightarrow$ Additive Notation
We are also going to shift from exponential notation, where a point that is 5 times the point $g_1 \in \mathbb{G_1}$ (the generator point) is written $g_{1}^5$, to the more-intuitive **additive notation**, where that point is now written $[5]_1$. This notation was originally introduced by Jens Groth, creator of the famous Groth16 circuit.
Similarly, the generator $g_2 \in \mathbb{G_2}$ when multiplied by 3 is now written $[3]_2$, not $g_{2}^3$.
>Ariel Gabizon points out one redeeming feature of exponential notation -- it's much easier to visualise the notion that 5 is not necessarily known in $g_{1}^5$ vs in $[5]_1$ -- because 5 is sort of 'tucked away' upstairs.
>
> See what you think.
### Setting up SHPLONK
We have the following ingredients:
- There are k polynomials under investigation $\{f_i(X) \in \mathbb{F}_{q}: i\in [k]\}$
- There are k sets of evaluation points $\{ S_i \subset \mathbb{F}_q :i\in [k]\}$. So for each $i$, $f_i$ will be evaluated over the points in $S_i$ (often each $S_i$ is just a handful of one or several points)
- Whilst we're here, let's collect these 'points of interest' together and give them a name $T = \bigcup_{i=1}^k S_i$ -- again, this is typically a tiny subset of $\mathbb{F}_q$. Let's give them names too: $T = \{ t_1 , ... t_m \}$
- And again whilst we're here, let's form polynomials $\{r_i(X) \in \mathbb{F}_{ < | S_i | } [X]: i\in [k]\}$ by a very simple rule -- $f_i (s) = r_i (s)$ each $s \in S_i$. Note that generally $f_i$ will be enormous (potentially degree hundreds of thousands or more). Note also that $r_i$ will generally be degree 0, 1, 2, or some other low number (degree 0 if proving system needs $f_i$ tested at 1 point, degree 1 if 2 points, etc)
- And a final reminder our elliptic curve pairing is now assumed to be *asymmetric* -- that means that our pairing isn't a map on $\mathbb{G}_1 \times \mathbb{G}_1$, but instead on $\mathbb{G}_1 \times \mathbb{G}_2$. In this section we will refer to the chosen generator of each group as $[1]_1$ and $[1]_2$ respectively. In turn that means that where we'd previously have written $g^x$ we now write $[x]_1$ and $[x]_2$ respectively
- A Reference String $srs = gen(d, t)$
- $d$ is the maximum degree of polynomial this SRS can support and in general is $>>t$
- $t$ is the maximum number of evaluation points
:::spoiler What do we mean by 'evaluation points'
Remember, a PCS is a first step in a zero knowledge scheme. Suppose the scheme for which SHPLONK is being used has 3 polynomials to evaluate, and the first will be evaluated at 2 points, and the others at 1 point each. That means that in this use of SHPLONK, $t = 4$
:::
- The SRS is of the form:
\begin{align*}
\langle [1]_1, [\alpha]_1, [\alpha^2]_1, ... [\alpha^d]_1,[1]_2, [\alpha]_2, [\alpha^2]_2, ... [\alpha^t]_2, \rangle
\end{align*}
### General Intuition
We're going to try to somehow generalise the Kate commitment. Kate says 'commit to something you claim is a polynomial in $\alpha$'. Now we're going to test it at a point of the Verifier's choosing, and we do it by getting you to calculate the following:
\begin{align*}
D = [\frac{f(\alpha) - f(\beta)}{\alpha - \beta}]_1
\end{align*}
Whilst you're acclimatising to additive notation, here it is in the old exponential notation:
\begin{align*}
D = g_{1}^{\frac{f(\alpha) - f(\beta)}{\alpha - \beta}}
\end{align*}
Now suppose the Prover had picked $C$ in some other way, with $C = g^\beta$. To be able to construct this divided out value above, and picked some other number $\delta$ masquerading as a legitimate $f(\beta)$. They would then have to have taken the $g^{\beta - \delta}$ and found a way to take the $\alpha^{th}$ root of this quantity -- breaking either the assumption the didn't know $\alpha$, or else a version of the discrete logarithm problem.
### Commit
Each polynomial is committed to using the $\mathbb{G}_1$ bit of the trusted setup -- i.e. that first list of $d$ points. It's done just as we saw in the Kate scheme, except we need to produce $k$ of these things (one for each polynomial):
\begin{align*}
C_i = [f_i(\alpha)]_1 = \sum_{j \geq 0} a_i [\alpha^i]_1
\end{align*}
A reminder that this is just additive notation, and we would previously have written this in exponential notation as:
\begin{align*}
C_i = g_1^{f_i(\alpha)} = \prod_{j \geq 0} (g^{\alpha^i})^{a_i}
\end{align*}
These mean the same thing!
Ok, so this leaves us with a commitment $C_i$ for each polynomial -- i.e. each of our k polynomials has been 'evaluated' at $\alpha$:
\begin{align*}
Com = \langle C_1, ... C_k \rangle
\end{align*}
Now, Kate would say - each $C_i$, evaluate each polynomial at some other point $\beta_i$, and send the verifier that quotient polynomial.
Before we run the general scheme, you might want to take a quick look at SHPLONK in the particular case of one evaluation point $s_1$. This will help us compare its functionality to Kate.
If you're feeling brave and want to see it in one, crack straight on with 'Full SHPLONK'.
:::spoiler SHPLONK on 1 Polynomial
>
>
> We have a commitment to one polynomial $f_1(X)$ -- that is, $C_1 = [f(\alpha)]_1$. We computed this using the trusted setup $[1]_1, [\alpha]_1, [\alpha^2]_1, ... [\alpha^d]_1$.
>
> Now, SHPLONK doesn't say -- directly evaluate that polynomial at another point $s_1$ and then prove you can divide out by a linear term $X - s_1$. It expresses itself differently but with (in the 1 polynomial case) the same effect.
>
> Now just so we remember our terminology, SHPLONK writes the evaluation set of $f_1(X)$ as $S_1 = \{ s_1 \}$ (because in this case we're doing the simple Kate thing, just evaluating at one point away from the trusted setup point $\alpha$.
> >
> Instead it says something equivalent -- prove that when you deduct a polynomial $r_1(X)$ that evalutes to the same as $f_1(X)$ at $s_1$, the resultant polynomial is divisible by $X - s_1$ (i.e. the polynomial is zero at $s_1$):
>
> \begin{align*}
> r_1(X) = f_1(s_1)
> \end{align*}
>
> That is a **constant** polynomial, because we only need to force one value -- if we need to force at two values we'll need a linear polynomial.
>
> But look at the possibility this now opens up -- we can just add in evaluation points by allowing $r_1(X)$ to be degree 1 (i.e. matching $f_1$ at two points, not just 1). And then we can prove $f_1 - r_1$ is divisible by $(X - s_1)(X - s_2)$.
:::
### Full SHPLONK!
#### 1. Make the $r_i(X)$ polynomial (one for each $f_i(X)$)
Both Prover and Verifier can make these - no communication needed, because Prover has told the Verifier what values $f_i(X)$ takes at each $s \in S_i$.
::: spoiler
> #### Making the $r_i(X)$ polynomials from Lagrange Polynomials
> We can form these using Lagrange polynomials $L_{s, S_i}(X)$
> Lagrange polynomials are ugly-to-make, lovely-to-use little building blocks that are zero everywhere they need to be (i.e. across $S_i$) except at one particular point $s \in S_i$. $L_{s, S_i} (X)$ needs to be at most a degree $|S_i|-1$ polynomial. Note that outside $S_i$ (remember we're in a field called $\mathbb{F}_q$), god only knows what these things evaluate to -- we really don't care.
>
> Formally:
>
> $L_{s, S_i}(X) =
\begin{cases}
1 &\quad\text{: } X = s\\
0 &\quad\text{: } X \in S_i \setminus \{ s \}
\end{cases}$
> Then we just need to 'scale up' each one to be $f_i(s)$ at $s$ (rather than 1), and then add them all together:
>
> \begin{align*}
> r_i(X) = \sum_{s \in S_i} f_i(s).L_{s, S_i}(X)
> \end{align*}
>
> And we're done!
:::
#### 2. Bind all the polynomials $f_i(X)$ into one $F(X)$
We can do this pretty easily:
\begin{align*}
F(X) := \sum_{i=1}^k \gamma^{i-1}.f_i(X)
\end{align*}
Where we use some pseudorandom number $\gamma$ computed after, and based on, their commitments (e.g. a hash of their commitments). This means the prover cannot tune their commitments to work for a value of $\gamma$ they already know.
Note the similarity of the role of $\gamma$ here to $\alpha$ in the polynomial commitment. Not identical, because $\gamma$ is disposable and both sides can and will learn its value. But it's something that the Prover cannot control.
It is, in fact, just a concrete substitute for a variable.
#### 3. Prover makes the bound-together quotient polynomial
As in the one-evaluation case, we make $r_i(X)$ match $f_i(X)$ on each element $s \in S_i$. Then the proof will be to show we can divide out $f_i(X) - r_i(X)$ by the polynomial which is zero across $S_i$, written $Z_{S_i}(X)$. At the risk of stating the obvious, both prover and verifier can easily compute this:
\begin{align*}
Z_{S_i}(X) = \prod_{s \in S_i} (X - s)
\end{align*}
And so the prover needs to make that all-important zero polynomial:
\begin{align*}
h(X) = \sum_{i=1}^k \gamma^{i-1}.\frac{f_i(X) - r_i(X)}{Z_{S_i}(X)}
\end{align*}
Notice this is just the quotient polynomial $h_i(X)$ for each $f_i(X)$:
\begin{align*}
h_i(X) = \frac{f_i(X) - r_i(X)}{Z_{S_i}(X)}
\end{align*}
And then we staple them all together, with powers of $\gamma$, which can be generated from a hash of the accumulated data so far, to avoid anyone being able to game the relationships between the $h_i(X)$ polynomials.
The Prover can't get away with any funny business here, because they already committed to each $f_i(X)$ by evaluating at the unknown number $\alpha$ -- we call these $C_i$.
So now the Prover can just evaluate this polynomial at one point (that mystery unknown point $\alpha$) and they have effectively given an evaluation proof for all $f_i(X)$ over their respective evaluation sets $S_i$:
\begin{align*}
\text{Compute: } W := [h(\alpha)]_1
\end{align*}
Remember (and forgive me for repeatedly banging the drum) that this was formed by the Prover being able to compute $h(X)$'s coefficients, and using the little $[\alpha^i]_1$ points from the Reference String to evaluate the commitment.
#### 4. Verifier Checks the Division Happened Correctly
This is going to look really nasty, but it's very, very similar to Kate - just with $k$ polynomials in the product rather than $1$. The plan is straightforward -- we can check whether the Prover successfully divided out $f_i(X) - r_i(X)$ by $Z_{S_i}(X)$ to create $W_i$ by using a pairing, and just sliding the factor $Z_{S_i}(\alpha)$ between the two sides of the pairing.
Deep breath -- the Verifier computes, for each set $S_i \subset T$ (recall $T$ is just the union of all those $S_i$ set by definition):
\begin{align*}
Z_{T \setminus S_i}(X)
\end{align*}
And evaluates each of these at $\alpha$ over the second run of points in the Reference String (you can now see why we provided for $t = |T|$ of those $\mathbb{G}_2$ points in the setup):
\begin{align*}
[Z_{T \setminus S_i}(X)]_2
\end{align*}
checks that:
\begin{align*}
\prod_{i=1}^k e(\gamma^{i-1}.(C_i - [r_i(\alpha)]_1),[Z_{T \setminus S_i}(\alpha)]_2) \stackrel{?}{=} e(W, [Z_T(\alpha)]_2)
\end{align*}
Where $W:= \sum_{i=1}^k \gamma^{i-1}.W_i$
Let's break this down because it's a far too much to absorb in one gulp:
1. $(C_i - [r_i(\alpha)]_1)$ -- what is this quantity? Well, the $C_i$ bit is just the $f_i(X)$ that we know and love evaluated at mystery point $X = \alpha$ (we've been calling this the commitment $C_i$), but as an 'encrypted' elliptic curve point. Furthermore, $r_i(X)$ is deducted so the resultant polynomial is zero on $S_i$. Some comments here to convince you all these values are (and can be) known by the Verifier:
- We know the Prover already sent all those $C_i$ values at the beginning
- The Verifier picked the evaluation sets $S_i$, and $r_i(X)$ depends only on those plus the values $f_i(X)$ takes at those $X$ values -- again, the Prover sent those values $\{ f_i(s): s \in S_i \}$ to the Verifier
- A final observation - you might think, 'this whole exercise feels slightly futile or else slightly Zen -- what exactly am I achieving by building this monolithic $f_i(X)$ and then just nullifying it (sending it to zero) on some small set $S_i$ of interest by deducting $r_i(X)$?'. The point is this -- generally the degree of $f_i(X)$ will be very large (routinely $10^6$ or more). And you don't want to communicate all its terms due to reasons of succinctness (literally putting the 'S' in 'SNARK'!). By contrast, the degree of $r_i(X)$ is usually $1$ or $2$ and rarely more (depending on the crytography system relying on this commitment scheme).
2. Now, this quantity $(C_i - [r_i(\alpha)]_1)$ can only be divided out by $Z_{S_i}(\alpha)$ if the Prover actually knows the answer to $\frac{f_i(X) - r_i(X)}{Z_{S_i}(X)}$. Yes but why? Well, if we knew the number $\alpha$ in its 'naked' form, this would be no problem -- we simply find the inverse of $Z_{S_i}(\alpha)$ in $F_{q}$ and then 'exponentiate'. But we don't know $\alpha$. In other words, aside from correctly dividing the polynomials $\frac{f_i(X) - r_i(X)}{Z_{S_i}(X)}$ (i.e. proving $f_i(X)$ evaluates to the claimed values on the small handful of points $S_i$), we need to break the Discrete Log Problem -- but our Foundational Creed was that we can't do this.
3. Now, we need to actually prove this thing really was the quotient value. Well, we need to be able to multiply it to check it's equal to $f_i(\alpha) - r_i(\alpha)$. But we have none of those 'raw' numbers. And we can't compute $[f_i(\alpha) - r_i(\alpha) ]_1$ (the 'encrypted' form) from the two 'encrypted' numbers $W_i := [\frac{f_i(\alpha) - r_i(\alpha)}{Z_{S_i}(\alpha)} ]_1$ and $[Z_{S_i}(\alpha)]$. Hum -- why not? Well, how are you going to get those two 'inner' numbers to interact multiplicatively? The best you can do is add them. This is the [Diffie Hellman Problem](https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_problem) and is a sort of cousin ofthe Discrete Log Problem (you'd have to break discrete log to successfully compute $[ab]_1$ from $[a]_1$ and $[b]_1$). So the question remains, how to check this? **Solution:** our magical pairing operation comes to the rescue -- we can use the pairing to shift the unknown factor $Z_{S_i}(]\alpha)$ between the right-hand argument and the left-hand argument, and thus check:
\begin{align*}
e((C_i - [r_i(\alpha)]_1),[1]_2) \stackrel{?}{=} e(W_i, [Z_{S_i}(\alpha)]_2)
\end{align*}
4. Almost there. This equation looks a lot simpler than that huge equation above with a big product and the $\gamma^i$ term and a $Z_{T \setminus S_{i}}(\alpha)$. Actually we're a really small step away from getting to that big equation from here. The plan is to staple all the pairings together using those randomised $\gamma^i$ numbers. There's a good reason for doing this - after doing this stapling exercise, we will be able to collapse the right-hand side down to just one pairing, from $k$ stapled pairings. Pairings, remember, are expensive operatins.
- First, each $i$, we're going to turn the right-hand argument of the right-hand side into something that will look the same for each $i$. The smallest term divisible by each $Z_{S_i}(X)$ is $Z_{T}(X)$. Does that mess up the left-hand side? Of course, but we can solve that by just putting in $Z_{T \setminus S_{i}}(\alpha)$ (zeroing out all the evlaution points of the other polynomials) rather than just $1$. This gives:
\begin{align*}
e((C_i - [r_i(\alpha)]_1),[Z_{T \setminus S_i}(\alpha)]_2) \stackrel{?}{=} e(W_i, [Z_{T}(\alpha)]_2)
\end{align*}
- Good, that furthest right-hand term is now completely independent of which $i$ we have. So let's use our randomising factors $\gamma^i$ to staple all these pairings together:
\begin{align*}
\prod_{i=1}^k e((C_i - [r_i(\alpha)]_1),[Z_{T \setminus S_i}(\alpha)]_2)^{\gamma^{i-1}} \stackrel{?}{=} \prod_{i=1}^k e(W_i, [Z_{T}(\alpha)]_2)^{\gamma^{i-1}}
\end{align*}
- Now for that efficiency gain -- we can compute the quotient commitment for the stapled-together version of $W_i$ *before* doing the right-hand pairing -- taking the number of pairings down from $2k$ to $k+1$:
\begin{align*}
\prod_{i=1}^k e(\gamma^{i-1}.(C_i - [r_i(\alpha)]_1),[Z_{T \setminus S_i}(\alpha)]_2) \stackrel{?}{=} e(\sum_{i=1}^{k} \gamma^{i-1}.W_i, [Z_{T}(\alpha)]_2)^{\gamma^{i-1}}
\end{align*}
One last observation -- you can see why we needed the Reference String to take the form it did -- $d$ polynomials to support the degree of the biggest $f_i(X)$ we might conceivably commit to. And $t << d$ points for the maximum number of evaluation points we might need across all $k$ polynomials (i.e. $|S_1| + ... +|S_k|$).
## Part 3. Concluding Remarks
If you followed all that first time -- congratulations! It's not easy and one wouldn't expect to digest all this at the first time of asking. It's probably worth revisiting the [paper](https://eprint.iacr.org/2020/081.pdf) with (hopefully) a better intuition for the ideas behind SHPLONK.
### Join us
Are you an engineer and does this material excite you?
We are hiring engineers with a strong mathematical intuition -- if that's you, please get in touch with Arnaud Schenk at arnaud@aztecprotocol.com.