# SHPLONK

*Thanks to Zac Williamson, Ariel Gabizon, Georgios Konstantopoulos, Ben Edgington and Tom Waite for various comments and suggestions.*

## 1. 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 long research papers.

### 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 basic theory of elliptic curves, and pairings - if you need to digest that, I recommend [Exploring Elliptic Curve Pairings (Vitalik Buterin)](https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627)
- the basics of how the Kate Polynomial Commitment Scheme works -- [Kate Commitments: A Primer](https://hackmd.io/I9CvNQm-S-WQozt6ElNG_Q) tells you everything you need to know to understand SHPLONK. It was originally Section 1 of this article and I decided to give it its own page for reasons of brevity.

## 2. The SHPLONKsplainer

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

My article on Kate assumed the pairing operation was symmetric.

We are actually going to make our pairings 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 SNARK.

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 operations.
- 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|$).

## 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 me at tom [at] aztecprotocol [dot] com