Thanks to Zac Williamson, Ariel Gabizon, Georgios Konstantopoulos, Ben Edgington and Tom Waite for various comments and suggestions.
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.
The SHPLONK scheme was created by the following researchers:
This article assumes good familiarity with:
SHPLONK is a polynomial scheme built to allow a single group element to be used to prove that not just one, but several polynomials have each been evaluated over a set of points 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.
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:
And an asymmetric pairing is of the form:
Where , but both are elliptic curve groups (and often will be closely related to one another).
We are also going to shift from exponential notation, where a point that is 5 times the point (the generator point) is written , to the more-intuitive additive notation, where that point is now written . This notation was originally introduced by Jens Groth, creator of the famous Groth16 SNARK.
Similarly, the generator when multiplied by 3 is now written , not .
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 vs in – because 5 is sort of 'tucked away' upstairs.
See what you think.
We have the following ingredients:
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,
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:
Whilst you're acclimatising to additive notation, here it is in the old exponential notation:
Now suppose the Prover had picked in some other way, with . To be able to construct this divided out value above, and picked some other number masquerading as a legitimate . They would then have to have taken the and found a way to take the root of this quantity – breaking either the assumption the didn't know , or else a version of the discrete logarithm problem.
Each polynomial is committed to using the bit of the trusted setup – i.e. that first list of points. It's done just as we saw in the Kate scheme, except we need to produce of these things (one for each polynomial):
A reminder that this is just additive notation, and we would previously have written this in exponential notation as:
These mean the same thing!
Ok, so this leaves us with a commitment for each polynomial – i.e. each of our k polynomials has been 'evaluated' at :
Now, Kate would say - each , evaluate each polynomial at some other point , 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 . 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'.
We have a commitment to one polynomial – that is, . We computed this using the trusted setup .
Now, SHPLONK doesn't say – directly evaluate that polynomial at another point and then prove you can divide out by a linear term . 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 as (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 that evalutes to the same as at , the resultant polynomial is divisible by (i.e. the polynomial is zero at ):
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 to be degree 1 (i.e. matching at two points, not just 1). And then we can prove is divisible by .
Both Prover and Verifier can make these - no communication needed, because Prover has told the Verifier what values takes at each .
Making the polynomials from Lagrange Polynomials
We can form these using Lagrange polynomials
Lagrange polynomials are ugly-to-make, lovely-to-use little building blocks that are zero everywhere they need to be (i.e. across ) except at one particular point . needs to be at most a degree polynomial. Note that outside (remember we're in a field called ), god only knows what these things evaluate to – we really don't care.Formally:
Then we just need to 'scale up' each one to be at (rather than 1), and then add them all together:
And we're done!
We can do this pretty easily:
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.
As in the one-evaluation case, we make match on each element . Then the proof will be to show we can divide out by the polynomial which is zero across , written . At the risk of stating the obvious, both prover and verifier can easily compute this:
And so the prover needs to make that all-important zero polynomial:
Notice this is just the quotient polynomial for each :
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 polynomials.
The Prover can't get away with any funny business here, because they already committed to each by evaluating at the unknown number – we call these .
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 over their respective evaluation sets :
Remember (and forgive me for repeatedly banging the drum) that this was formed by the Prover being able to compute 's coefficients, and using the little points from the Reference String to evaluate the commitment.
This is going to look really nasty, but it's very, very similar to Kate - just with polynomials in the product rather than . The plan is straightforward – we can check whether the Prover successfully divided out by to create by using a pairing, and just sliding the factor between the two sides of the pairing.
Deep breath – the Verifier computes, for each set (recall is just the union of all those set by definition):
And evaluates each of these at over the second run of points in the Reference String (you can now see why we provided for of those points in the setup):
checks that:
Where
Let's break this down because it's a far too much to absorb in one gulp:
– what is this quantity? Well, the bit is just the that we know and love evaluated at mystery point (we've been calling this the commitment ), but as an 'encrypted' elliptic curve point. Furthermore, is deducted so the resultant polynomial is zero on . Some comments here to convince you all these values are (and can be) known by the Verifier:
Now, this quantity can only be divided out by if the Prover actually knows the answer to . Yes but why? Well, if we knew the number in its 'naked' form, this would be no problem – we simply find the inverse of in and then 'exponentiate'. But we don't know . In other words, aside from correctly dividing the polynomials (i.e. proving evaluates to the claimed values on the small handful of points ), we need to break the Discrete Log Problem – but our Foundational Creed was that we can't do this.
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 . But we have none of those 'raw' numbers. And we can't compute (the 'encrypted' form) from the two 'encrypted' numbers and . 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 from and ). 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 between the right-hand argument and the left-hand argument, and thus check:
Almost there. This equation looks a lot simpler than that huge equation above with a big product and the term and a . 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 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 stapled pairings. Pairings, remember, are expensive operations.
First, each , we're going to turn the right-hand argument of the right-hand side into something that will look the same for each . The smallest term divisible by each is . Does that mess up the left-hand side? Of course, but we can solve that by just putting in (zeroing out all the evlaution points of the other polynomials) rather than just . This gives:
Good, that furthest right-hand term is now completely independent of which we have. So let's use our randomising factors to staple all these pairings together:
Now for that efficiency gain – we can compute the quotient commitment for the stapled-together version of before doing the right-hand pairing – taking the number of pairings down from to :
One last observation – you can see why we needed the Reference String to take the form it did – polynomials to support the degree of the biggest we might conceivably commit to. And points for the maximum number of evaluation points we might need across all polynomials (i.e. ).
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.
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