ZK7: Accountable light clients via BLS multisignature rollup - Alistair Stewart - Web3 Foundation

Transcript

[Music] hi i'm alistair uh let me know if i'm talking too quiet too loud if i start nostalgic just let me know please um although you can't see because it's completely illegible uh this is based uh i'm alistair stewart and this is based on joint work with with with oanna and with uh sergey who couldn't be here and i'm going to talk about um like clients sort of the problem of how to um

follow the contents of a blockchain efficiently now okay does this work yes it does um so specifically uh what is it like client so the way i'm gonna structure this talk i i'm gonna try and explain very briefly what what the uh what this solution does and then i'm going to um say how it does it sort of what what the snark is and only then am i going to explain why we did this and what it's at and why why it's this way compared to what everyone else does which i don't know if that will make sense but i hope so so

broadly speaking a light client it it is is uh something you'd be running on a resource controlling device and you're trying to follow this sort of decentralized consensus system and part of the problem is that um this and the system may have many consensus participants in case of sort of particularly thinking of proof-of-stake blockchains we have things like validators uh we might have a lot of them um sort of on polka dot we are aiming for a thousand but ethereum already has like 200 000 validators um and it's not obvious how i can get a

resource controlling device to understand what these guys have agreed on and the solution that i'm going to talk about is just um the problem of verifying that something was signed by many signers uh and i'll explain later exactly why this is the problem we need to solve um so we we can do multi-signatures this allows us to give or sort of aggregateable signatures like bls this allows us to give one signature from a lot of signers

but there is still an issue that this so this means instead of having a thousand signatures i can have one signature which is great um the issue with multi-signatures is of course that i still need to have the thousand public keys to verify them and that this set can change you know the set of guys who's who we are um interested in signing something can change frequently and if it does then these public keys are a lot of data by themselves now how do we solve this well the obvious solution is to use uh would be to use threshold

signatures maybe and there's certainly some you know every year there's interesting progress on this but it's still generally true that the the distributed key generation you need doesn't scale so well to uh thousands and millions of participants um and also it would actually be useful to know who who signed what but it would be nice to know who signed what and and not have um quite so much data from this public keys so what uh this solution does okay yeah i better sort of say how big

the problem is um and this is sort of yeah so we have these like two five six or three eight four bits public keys uh and if we have two five six bit public keys then we probably also have two five six big signatures for everybody so that doesn't actually save anything um we're looking at you know kilobytes and megabytes for every time we need to frequently every time we need to update this set unless we did something sensible um so what our solution works it does is this so basically the idea is that we're going to commit to a a long vector of public keys and we're going to we want to verify that a particular subset of these guys

signed something and we you know in indicate the subset by just giving a bit field you know bit vector of length then this size is still order of n but um like the public keys were 256 or 384 bricks so this this is 100 times less data you know at least than just giving the keys and this is you know a significant advantage and if you do this it's like it has the same advantages as you know just doing some sort of aggregateable signature scheme like bls by itself and that the scientists don't have to interact with

each other which is complicated when there's a lot of them and and indeed we know who signed what for which we kind of need probably need about a bit per uh per signer and so um how would we get such a straight scheme well sort of one of the obvious things to do we think to do was let's do something like bls everyone has their own bls public key and proofs of possession and we just need to compute an aggregate public key from this commitment or prove that you know that this uh this commitment to the vector and this

bit field give this aggregate public key and uh sort of the obvious solution would be let's use a snark for that so how would we do this with a snark well we could use something like like like plonk or whatever's popular right now um to do this with with plonk you probably want uh you know you probably want to use turbo pump you probably want to use a custom gate um so the kind of the operation that you're mostly trying to do here is uh you we have a load of you know elliptic curve points and we want to add a load of them if the bits are one um and this this means you know we define basically

a set of equations which give a conditional incomplete elliptic curve addition gate now in the uh in that i've seen code out there for a uh incomplete elliptic curve edition gate for turbo plunk and it looks very similar to this except without this b which is the bit that determines whether we add things or not um i'm kind of surprised that they didn't go a degree higher and put this bit in because when you're doing something like a multi-scale multiplication you normally want to condition on on bits so if we had such a such a gate uh how would we compute the problem

well there's this minor uh incompleteness issue um that if we want the simple formula that this is short wirecraft form and incompleted curved edition we have to make sure that we never add something to itself or it's opposite not least because we can't express zero and alpha coordinates um there's a really simple way of doing that for for bls which has a cofactor we just uh you know started with the base point outside the subgroup um and then if all the points we're adding are in the subgroup we never get uh

you know the the the accumulated sum is always outside the subgroup and so it never it's never equal to minus the thing we're adding or plus the thing we're adding and incompleteness is not a problem so how do we um so the circuit is super simple we just uh okay there should be a b here like imagine there's a b here uh a bi that i'm using to multiply these things and so yeah basically so the way like that the halo 2 guys are now talking about um how they do their circuits is is that they sort of think of that they're

talking of chips now we have sort of two-dimensional things so this is this is just a table where you imagine that uh each column stands for some polynomial commitment in lagrange basis and this is the value at some of each of these things at some power of roots of unity and so the uh the gate just you know takes some public key uh x and y coordinates this bit and uh the accumulated last accumulated value and adds and gives the next accumulated value and more or less the entirety of the circuit is we just repeat this end times um because

what we're doing is straightforward repeating the same thing end times we don't actually need a permutation argument if this is all we're doing so we didn't use planck we just did this and yeah so in the simple form this is just the circuit and it's sort of the simplest circuit you will see today i'm sure probably uh unless anyone knows anything's faster um and the advantage of a simple circuit is obviously the uh it's faster for the prover in the end yes you could drop this condition but

then you'd have um more variables bigger or a bigger degree with projected coordinates it's i doubt it's more efficient than this but you yeah i mean i mean just having extra variables would uh make it slower so yeah the inverse is kind of not a problem while you're you're while we're putting this in a constraint system it's just we multiply the other side by the inverse uh yeah the yes sure the the inversion is a problem for

computing um these things and they would be that would would would i just would be faster than projective coordinates but here we uh you know it's a snog we have non-determinism we just need uh to give a constraint and that has fewer uh variables if you do it in in affine coordinates and you just have a pair of points for each swing except for this incompleteness problem but you can uh though don't you have that in predictive coordinates too without unless you do something really complicated um and there's a there's a simple hack for that uh if you didn't have a um if you weren't dealing with the

subgroup there's also trivial things you could do to solve this like using feature mirror to find your point h or doing some hash to curve which would also work if uh if you have proof of possession for these public keys um yeah okay and here are the polynomial constraints sort of we have these four expressions and they have to divide x to the n minus one obviously this is incredibly complicated to put on a slide but uh it is simpler than plonk and other things right um i'm just trying to yeah emphasize that

this is uh we were going for uh something simplicity i mean as you know from as you all know particularly the guys who were like the last talk we're still in the era of hand optimizing all this stuff if you really care about prover time um and that's why we didn't use an off-the-shelf thing we did our own thing which admittedly took longer so there are sort of um two things here so one thing is is we did the trivial thing and uh which in this case is to avoid decommitting our commitment in the snark we use polynomial commitments so that the you know we don't have to do the de-commitment it's already in the right format

um this kind of made the proof a little bit more tricky because it breaks this sort of uh polynomial iop polynomial program abstraction that everyone is using a bit but it's not really too bad because this is actually what everyone has been doing with with circuit polynomials like you always if you have a polynomial commitment uh kind of in the input um which you trust for for the sonic marlin and this is not miles away from that it's it's we have we trust that someone committed to these public keys correctly um and the verifier doesn't you know compute that themselves so

um there is one thing that that's that's a bit slow if you do it this naive way uh when you have large numbers of public keys so you know your your polynomial uh your input is what the uh pub the the commitment to the public keys and uh this bit field now in the verification occasions um we have this polynomial b of x which is your sort of lagrange basis um commitment to this bit field and uh the verifier they have the bit field they can just evaluate this by uh so you know barry centric um evaluation for lagrange evaluation for

roots of unity um but doing that would would cost them order of enfield operations there are other things you can do so this is sort of like am i we're imagining that we consider each bit to be its own field element um another thing we could do was to split these bits into this bit vector into chunks and consider those to be field elements uh we'd have to add a few constraints so in particular we have this this pack scheme where uh we divide the input into uh sections of 128 bits or something that fits its power too that fits nicely into a field element and um then we kind of think of this as order

of n over lambda where lambda is your security parameter because your field size is 3 of lambda it ends up um being you know 100 times less field operations to do with this mid vector um at the cost of a few extra some constant number of extra group elements because we have to add real preparations because we have to add some more constraints or you could just give up on this bitfield entry and just count the number of wants and so your input would be the number of guys uh who were there and you could yeah you could add trivially some constraints to uh

to compute that from b of x uh but we are trying to uh put the bit field in for reasons i'll go into later and which polynomial commitment and which curves do you use so so we have an implementation on bw6761 bls 12377 which is the same thing that cello is using in their their plumo protocol but there's a whole load of other ways you could implement this the construction these guys used to produce this this 2 train is is generic like they pointed out there in an f research process that it would

completely work with bls 12 381 the only difficulty comes with with freer transforms and finding a multiplicative subgroup of the right size but like um because uh this this thing has a nice factor that the um that the uh you know the the base field is is nice and too attic for bls12381 the scalar field isn't too addict but the uh it is too addictive but the base field isn't and this is uh and the base field is the thing which our coordinates are in which we're doing addition over so that's um and then we have to use a different subgroup and more complicated fft but

it will work um for those of you using bls 12381 in your consensus um you could also use something other than kcg like non-pairing friendly outer curve we could probably get something smaller if you did some batching it would probably be faster if you want to verify loads of these and what's the embedding dimension what's that what's the embedding dimension of the curves so that that so so these guys came up with um okay and i'll try and remember if i can pronounce their names but no uh the guys that came up with with this curve gave a sort of generic construction for producing a curve uh

from a bls curve of about twice the size uh they wrote a couple of their paper which gave this and then another paper sort of generalizing it to vs12 and bls24 um so so basically you need a bigger curve in order to get the the base field of this curve inside it because we're doing operations on base field things well if you use pairings you have to get a bigger curve you can probably not do that if you didn't want to use bearings for the thing but we have to use pairings for bls uh which embedding of the curve so what's the height the minimum power

field finite field right so so what we what we're doing is we're considering um again always go with the simpler case we're considering the case when uh uh it's g1 for we we we're considering the case we put the public keys in g1 and so um the um it's in the base field that we have the coordinates uh not the g2 case which would definitely have a more complicated circuit okay so one yes what now admittedly there is a bit of a

trade-off in bls actually i think you can i i kind of speculate that it would be secure to put your keys in g1 and g2 and then you could have your uh you could have your hashtag g1 and the public keys in g1 for the verifier and that will get round uh the problem i think you might be seeing but um yeah the simplest thing was g1 if you want to be fast uh that was uh uh the trade-off we made so uh these are the are the

uh so we implemented it uh we've had this game for a while i'm going to give you the link at the end um and these are the sort of benchmarks we've got um the thing we were going for with all this this customization okay i've completely missed time this then um the thing we're going for with this this customization was to aim to have a a not only a decent verifier time but a fast proving time um and you see all these schemes uh under a second for a thousand validators you know like half a second and even if we go up to a million they're sort of five six minutes it's

which is kind of fast for what you can do with snarks on inputs that big so this is what we do how do we use it why is this the thing to do and how does this compare with what everyone else is so like clients as i said is a is software to um to let the resource contrain device um you know verify what's going on in the contents of the blockchain what resource came to contained by to interested in well you know a browser a phone or a blockchain so one of the the chief applications i'm thinking is for this is for bridges uh we have a light cloud on another blockchain and often it's it's just too expensive to put even a thousand public

keys on certainly on ethereum one uh uh so basically a blockchain is is more resource controlled than a browser on a phone um and this sort of affected our model a bit especially on how much security we want to have from this protocol um so we're looking at like you know uh we have like a that we're thinking of systems where you have a thousand to a million validators um we maybe believe statements assigned by two-thirds of them and the set changes like you know once a day or something which is quite a lot if you're dealing with an entire history of a blockchain and how like can we do this we can know

we can do this in constant size if this is all we're trying to do and dfinity mina have done it um both with huge overheads especially you know so dfinity does this this resharable threshold signature scheme so they keep the same key but it's complicated and they have to do this complicated thing every time they change the validator set and meena just put everything into a snark which is great because they're not just following consensus but validity but again they're a bit of in computation uh the direct comparable thing is cello's plumo thing which use the same curves we do to roll up dls signatures uh what's the difference between us and them well mainly it's the target the thing we're thinking of aiming at like we have they they have uh cello have like 100-ish validators we're

thinking of thousands to a million uh we're thinking of targeting a blockchain rather than a cell phone and that means that when it comes that you know the cell phone you have to sync from scratch many times you know almost every time you reach out maybe you have to sync it from scratch um but if we're doing something stateful on the blockchain we only need to increment it we only need to update it gradually uh as a result they aim to put like uh they underput like 140 something validated set up dates inside their snark and that meant that they had to do pairings inside snarks loads of hashes inside snarks and it just ends up being a lot slower than what we're doing uh we only do one evoke at a time which of course would be more data if you're thinking from the start

uh but on the other hand if you have a very large valid data set that the plumber approach already uses huge circuits you probably wouldn't be able to roll up many errors if you had that many validators uh their proving is very slow you know the hours to our seconds but that's because they do hashes and uh pairings in their circuit lots of hashes and the the bit that all that we do in our circuit is a very small part of what's in their circuit and this is fine for them because they only have 100 validators so we just catch up to something very recent and then we we give 100 or 200 validators public keys and we can just do this at a time whereas in our sort of model we don't ever want to give the validators the current set of public keys so we

have to do new proof for everything and it really helps to be able to you know do these proofs faster than the blockchain finalizes blocks so that's why we're aiming for sort of half a second with a thousand that even the like the the million validated figure i gave you the five to six minutes is faster than an ethereum to evoke so it's probably um fast enough um the other thing i want to say is that we don't actually um this all works under a two-thirds honesty assumption but generally we don't actually want to trust a validated at all we'd like to somehow assume they're rational we'd like to punish people who misbehave

and uh if we have this this bit field and we can tell who signed we can kind of do this uh so in particular we have this property called accountability which you know if you see the blockchain you see a like client proof of something false and if it's on a bridge it's public uh then you can work out uh you can you can give a proof to your blockchain and we can slash say a third of validators um and as we've seen recently bridge security is super important right i don't yeah we want to be as secure as possible um so yeah we have code uh there's a paper on its way that i will try and put a draft version of in this repository um takeaways this is kind of simple we can apply it to many existing proof of

stake protocols all they need to do is to use bls signatures or be adapted to use bls signatures and you know have the sort of thing most guys are doing i just want to say yeah if you want a snack crew that's fast for large insurances you have to optimize by hand try and make everything as simple as possible and uh we think accountability is super important okay [Applause] thanks uh we're actually out of time depending on if i get some thumbs up or thumbs down if we have time for questions anyone have a question so how many constraints will gain how many constraints how many

constraints or gates does it cost to have a pairing don't ask me we didn't do it uh so i think there's actually clever ways around to avoid having the pairing uh that i can think of that i will be going for if i really wanted to do a recursive version of this because i think it's going to be horrible thanks enjoy your break and then [Applause]