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 paper will be aware that it involves a batched polynomial commitment scheme that extends the "Kate" KZG10 scheme.

I'm writing this article for those of you who want to get to grips with SHPLONK without sifting through long research papers.

Authors

The SHPLONK scheme was created by the following researchers:

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)
  • the basics of how the Kate Polynomial Commitment Scheme works Kate Commitments: A Primer 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

{fi(X)Fq:i[k]} have each been evaluated over a set of points
SiFq
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
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:

e:G×GGT

And an asymmetric pairing is of the form:

e:G1×G2GT

Where

G1G2, but both are elliptic curve groups (and often will be closely related to one another).

2. Exponential
Additive Notation

We are also going to shift from exponential notation, where a point that is 5 times the point

g1G1 (the generator point) is written
g15
, 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

g2G2 when multiplied by 3 is now written
[3]2
, not
g23
.

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

g15 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
    {fi(X)Fq:i[k]}
  • There are k sets of evaluation points
    {SiFq:i[k]}
    . So for each
    i
    ,
    fi
    will be evaluated over the points in
    Si
    (often each
    Si
    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=i=1kSi
    again, this is typically a tiny subset of
    Fq
    . Let's give them names too:
    T={t1,...tm}
  • And again whilst we're here, let's form polynomials
    {ri(X)F<|Si|[X]:i[k]}
    by a very simple rule
    fi(s)=ri(s)
    each
    sSi
    . Note that generally
    fi
    will be enormous (potentially degree hundreds of thousands or more). Note also that
    ri
    will generally be degree 0, 1, 2, or some other low number (degree 0 if proving system needs
    fi
    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
    G1×G1
    , but instead on
    G1×G2
    . 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
    gx
    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
      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:

[1]1,[α]1,[α2]1,...[αd]1,[1]2,[α]2,[α2]2,...[αt]2,

General Intuition

We're going to try to somehow generalise the Kate commitment. Kate says 'commit to something you claim is a polynomial in

α'. 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:

D=[f(α)f(β)αβ]1

Whilst you're acclimatising to additive notation, here it is in the old exponential notation:

D=g1f(α)f(β)αβ

Now suppose the Prover had picked

C in some other way, with
C=gβ
. To be able to construct this divided out value above, and picked some other number
δ
masquerading as a legitimate
f(β)
. They would then have to have taken the
gβδ
and found a way to take the
αth
root of this quantity breaking either the assumption the didn't know
α
, or else a version of the discrete logarithm problem.

Commit

Each polynomial is committed to using the

G1 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):

Ci=[fi(α)]1=j0ai[αi]1

A reminder that this is just additive notation, and we would previously have written this in exponential notation as:

Ci=g1fi(α)=j0(gαi)ai

These mean the same thing!

Ok, so this leaves us with a commitment

Ci for each polynomial i.e. each of our k polynomials has been 'evaluated' at
α
:

Com=C1,...Ck

Now, Kate would say - each

Ci, evaluate each polynomial at some other point
β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

s1. 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'.

SHPLONK on 1 Polynomial

We have a commitment to one polynomial

f1(X) that is,
C1=[f(α)]1
. We computed this using the trusted setup
[1]1,[α]1,[α2]1,...[αd]1
.

Now, SHPLONK doesn't say directly evaluate that polynomial at another point

s1 and then prove you can divide out by a linear term
Xs1
. 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

f1(X) as
S1={s1}
(because in this case we're doing the simple Kate thing, just evaluating at one point away from the trusted setup point
α
.

Instead it says something equivalent prove that when you deduct a polynomial

r1(X) that evalutes to the same as
f1(X)
at
s1
, the resultant polynomial is divisible by
Xs1
(i.e. the polynomial is zero at
s1
):

r1(X)=f1(s1)

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

r1(X) to be degree 1 (i.e. matching
f1
at two points, not just 1). And then we can prove
f1r1
is divisible by
(Xs1)(Xs2)
.

Full SHPLONK!

1. Make the
ri(X)
polynomial (one for each
fi(X)
)

Both Prover and Verifier can make these - no communication needed, because Prover has told the Verifier what values

fi(X) takes at each
sSi
.

Making the
ri(X)
polynomials from Lagrange Polynomials

We can form these using Lagrange polynomials

Ls,Si(X)
Lagrange polynomials are ugly-to-make, lovely-to-use little building blocks that are zero everywhere they need to be (i.e. across
Si
) except at one particular point
sSi
.
Ls,Si(X)
needs to be at most a degree
|Si|1
polynomial. Note that outside
Si
(remember we're in a field called
Fq
), god only knows what these things evaluate to we really don't care.

Formally:

Ls,Si(X)={1X=s0XSi{s}
Then we just need to 'scale up' each one to be
fi(s)
at
s
(rather than 1), and then add them all together:

ri(X)=sSifi(s).Ls,Si(X)

And we're done!

2. Bind all the polynomials
fi(X)
into one
F(X)

We can do this pretty easily:

F(X):=i=1kγi1.fi(X)

Where we use some pseudorandom number

γ 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
γ
they already know.

Note the similarity of the role of

γ here to
α
in the polynomial commitment. Not identical, because
γ
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

ri(X) match
fi(X)
on each element
sSi
. Then the proof will be to show we can divide out
fi(X)ri(X)
by the polynomial which is zero across
Si
, written
ZSi(X)
. At the risk of stating the obvious, both prover and verifier can easily compute this:

ZSi(X)=sSi(Xs)

And so the prover needs to make that all-important zero polynomial:

h(X)=i=1kγi1.fi(X)ri(X)ZSi(X)

Notice this is just the quotient polynomial

hi(X) for each
fi(X)
:

hi(X)=fi(X)ri(X)ZSi(X)

And then we staple them all together, with powers of

γ, which can be generated from a hash of the accumulated data so far, to avoid anyone being able to game the relationships between the
hi(X)
polynomials.

The Prover can't get away with any funny business here, because they already committed to each

fi(X) by evaluating at the unknown number
α
we call these
Ci
.

So now the Prover can just evaluate this polynomial at one point (that mystery unknown point

α) and they have effectively given an evaluation proof for all
fi(X)
over their respective evaluation sets
Si
:

Compute: W:=[h(α)]1

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
[α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
fi(X)ri(X)
by
ZSi(X)
to create
Wi
by using a pairing, and just sliding the factor
ZSi(α)
between the two sides of the pairing.

Deep breath the Verifier computes, for each set

SiT (recall
T
is just the union of all those
Si
set by definition):

ZTSi(X)

And evaluates each of these at

α over the second run of points in the Reference String (you can now see why we provided for
t=|T|
of those
G2
points in the setup):

[ZTSi(X)]2

checks that:

i=1ke(γi1.(Ci[ri(α)]1),[ZTSi(α)]2)=?e(W,[ZT(α)]2)

Where

W:=i=1kγi1.Wi

Let's break this down because it's a far too much to absorb in one gulp:

  1. (Ci[ri(α)]1) what is this quantity? Well, the
    Ci
    bit is just the
    fi(X)
    that we know and love evaluated at mystery point
    X=α
    (we've been calling this the commitment
    Ci
    ), but as an 'encrypted' elliptic curve point. Furthermore,
    ri(X)
    is deducted so the resultant polynomial is zero on
    Si
    . 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
      Ci
      values at the beginning
    • The Verifier picked the evaluation sets
      Si
      , and
      ri(X)
      depends only on those plus the values
      fi(X)
      takes at those
      X
      values again, the Prover sent those values
      {fi(s):sSi}
      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
      fi(X)
      and then just nullifying it (sending it to zero) on some small set
      Si
      of interest by deducting
      ri(X)
      ?'. The point is this generally the degree of
      fi(X)
      will be very large (routinely
      106
      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
      ri(X)
      is usually
      1
      or
      2
      and rarely more (depending on the crytography system relying on this commitment scheme).
  2. Now, this quantity

    (Ci[ri(α)]1) can only be divided out by
    ZSi(α)
    if the Prover actually knows the answer to
    fi(X)ri(X)ZSi(X)
    . Yes but why? Well, if we knew the number
    α
    in its 'naked' form, this would be no problem we simply find the inverse of
    ZSi(α)
    in
    Fq
    and then 'exponentiate'. But we don't know
    α
    . In other words, aside from correctly dividing the polynomials
    fi(X)ri(X)ZSi(X)
    (i.e. proving
    fi(X)
    evaluates to the claimed values on the small handful of points
    Si
    ), 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

    fi(α)ri(α). But we have none of those 'raw' numbers. And we can't compute
    [fi(α)ri(α)]1
    (the 'encrypted' form) from the two 'encrypted' numbers
    Wi:=[fi(α)ri(α)ZSi(α)]1
    and
    [ZSi(α)]
    . 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 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
    ZSi(]α)
    between the right-hand argument and the left-hand argument, and thus check:
    e((Ci[ri(α)]1),[1]2)=?e(Wi,[ZSi(α)]2)

  4. Almost there. This equation looks a lot simpler than that huge equation above with a big product and the

    γi term and a
    ZTSi(α)
    . 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
    γ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
      ZSi(X)
      is
      ZT(X)
      . Does that mess up the left-hand side? Of course, but we can solve that by just putting in
      ZTSi(α)
      (zeroing out all the evlaution points of the other polynomials) rather than just
      1
      . This gives:
      e((Ci[ri(α)]1),[ZTSi(α)]2)=?e(Wi,[ZT(α)]2)

    • Good, that furthest right-hand term is now completely independent of which

      i we have. So let's use our randomising factors
      γi
      to staple all these pairings together:
      i=1ke((Ci[ri(α)]1),[ZTSi(α)]2)γi1=?i=1ke(Wi,[ZT(α)]2)γi1

    • Now for that efficiency gain we can compute the quotient commitment for the stapled-together version of

      Wi before doing the right-hand pairing taking the number of pairings down from
      2k
      to
      k+1
      :
      i=1ke(γi1.(Ci[ri(α)]1),[ZTSi(α)]2)=?e(i=1kγi1.Wi,[ZT(α)]2)γi1

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
fi(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.
|S1|+...+|Sk|
).

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 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