ZK8: Ethical identity, ring VRFs, and zero-knowledge continuations - Jeff Burdges - Web3 Foundation

Transcript

foreign so today I'm going to be telling you about uh amongst other things I'm going to be telling you about this construction called uh ring vrf and this trick called a ZK continuation which I came up with at some point um to make ring vrfs fast very very fast okay so VR okay so we'll we'll say what a vrf is in a second so to start out we have um people here probably generally know what a ring signature is um so of course historically they were a little bit more you know some people like zcash tend not to use the term but

in a certain sense zcash is a ring signature where you have this fancy commitment which is the entire blockchain um and you know so there's actually a quite a variety of ring signatures and to some extent a huge amount of the stuff that's going on at this conference is talking about different types of ring signatures um okay um now uh vrfs are um basically their signatures where you prove the evaluation of some pseudorandom function that is tied to the the key the secret key of the signer makes sense this is the construction of them if you look at it so if if I were

to delete this line three this would just be a snore signature um if it's just check in line three if I delete it I just have a snore signature um all it's really doing is it's proving that there's a that this um output point which um is actually not the output that this pre-output point I've called out is um that it's it's also a multiple of the secret key times whatever I've hashed to the Curve um and okay fair enough so and then this this last thing on the last line this last hash is the prf part so you think about this out is keying the prf okay so what's a ring vrf it's simply a ring signature that also proves the

evaluation of pseudor random function so it's a ring signature that's also a vrf that's it um all right so to be able to build one I need to enter slightly tweak this EC vrf very minely all I've changed is is to add this T times K here I've added this extra T into the proof and I've added this multiple here but what this lets me do is now instead of my public key simply being the secret key times some generator now my public key is simply a Peterson commitment to the secret key very simple actually all right now uh now I need to get a little bit more complex I need to actually open up

cross 16 to be able to do something uh well okay so first of all now we're going to explain so this piece that I've just told you this Peterson vrf I'm going to use that as the second half of what we're calling zika a ZK continuation and but for the first half the part that actually gets continued I need to grow 16. so there's okay think about it this way what is the fastest uh what is the fastest snark was one you don't prove at all it's one that you've proven in the past and you're just going to reuse okay so this is cross 16. um this is ground 16. it

um we have so the things the the the Greek letters are toxic waste um the uh the a b and c or the proof and the x is the public inputs but sort of after they've already been bundled into a curve point so there are some pieces of the verifier key and you multiply them by the different public inputs and you add them up and that becomes X all right uh so that could look like this we could have a the secret key times some generator G named as in the previous slide actually won't be a generator here it could be but it won't it won't necessarily be in graph 16 but whatever that doesn't matter and then we

have this K and so there that right there is my com PK from the Peterson vrf already now if I did literally this and if the K was in the gross 16 then it would be shitty because now I have processed the secret key in the graph 16 which I don't ever want to do I've also um uh and I've also got to prove this Graphics reprove this gross 16 every time I use it so we're not going to do that instead what we're going to do is we're going to take this K we're going to Mark in The Trusted setup we're going to multiply it by some toxic waste elements and we'll get this K Delta guy which can now be introduced into C so this procedure here if you remove the 2K got the 2K terms this is the

re-randomization procedure for graph 16 and now the new these new K terms means that I can re-randomize the thing and also re-randomize the public input and if this costs me what force so it cost me to get two yeah four G1 scalar multiplications and two G2 scalar multiplications for the B line so extremely cheap um so I get to reuse my cross 16 and what I've the point of all of this is so that I've re-randomized the ABC with the typical re-randomization procedure for raw 16 and and and this adding this K lets me re-randomize the public input as well

and okay so now I what I need to be able to use this is I need for the the parts of the public input that uh the so the dot dot dots may be the verifier the actual verifier we'll see but for this com PK I need a proof of knowledge of that but I already had that the the Peterson vrf gives me that so this is it I have this cross 16 and the Peterson vrf and I have a um this gives me a ring vrf that is extremely cheap in fact the marginal cost of proving is totally 8g1 scalar multiplications plus two G tubes together multiplications so this is irtf you know ietf crypto

fast this thing is blazingly fast not like the this is not like other stuff that you've seen at this conference these this thing is fast um and uh okay so this is like this is okay so this x is describing the uh the X from sort of the previous slide but of course this BK is not really in the gross 16. I've just added it externally uh so the actual gross 16 would look something like this I have to I have to represent the BLS 12 377 point on the jub jub curve so I have to split the key up because the job curve is a bit smaller uh and I can do this this job arithmetic cheaply inside the snark and then I have to prove that this is in the

ring commitment fine um so this is pretty cool now there's one shitty thing here which is that I'm still processing the secret key inside the snark and now I don't have to reprove the snark very often but I still do have to reprove the snark every time the ring changes so which could depending you know it could be non-trivial uh so I can get rid of that too if I change my gross 16 to um just simply translate from this job representation to to the BLS 12377 representation and then prove the job job representation is another way like for example I could use caulk or caulk Plus or I could also have like

this girl 16 could just prove that the thing is that the secret key represents a public key in a block and then I could use Caulker plus to prove that blocks are you know exist so now this is a little bit heavier than the one on the previous slide but now I only ever need to prove this gross 16 once ever and so I only ever actually use my secret key integral 16 once and and the thing can be extremely efficient all right um so as I said this is sort of uh this is sort of I you know IET ietf crypto fast um and what can we do with it okay so um how can an identity be safe to use online well the answer is that it

shouldn't say anything about you so there's there's the wr3c and the Irma credential people or whatever are pushing this stuff about having like attribute crate-based credentials that talk tell that will selectively leak about you the problem is most of that stuff will get misused um so what we really want is identity system that doesn't leak anything about you it just like gives you a unique identity that's unlinkable from your identity in any other context so how do we do this um we okay so we make a ring that consists of people with as much as we can insure it one key per person and here's what your browser does it says validates the TRS the TLs cert of a site

including the CT the transparency logs and then it sends the vrf signature with message equal site name there's your identity on the site there's only one of you there they want to ban you they can ban you it's done on the subject of banning you know if you want to do weird you can do weird things where identity changes each month or you put like multiple identities like of multiple months in there and now this gives the ability to sort of a person sort of disappear for a month and then come back fresh there's all kinds of weird things you can do with ring verifs um now I'm going to tell so a caveat I said so these are blazingly fastering signatures um they're not actually that great for

long-term money because I I need this the to prove to prove ring membership I'm proving like I would be proving the existence of a utxo but I don't generally use a utxo more than once so this while it's super great for identity type things and other stuff it's not great for really long-term money turns out it's really awesome for ephemeral money so okay uh people may be aware that we have a climate change problem the world's going to plus 4C and 100 years there's no way we'll still have a billion people on this planet um you know most people are going to die um there's no way we can ever get to Mars and other places unless we figure out how to burn less use less Etc Okay so

and we see this now so a lot of the rationing we have is from other fuck-ups but like though the cooking oil shortage or the mustard shortage in France is because of climate change we're already feeling it so what do governments do in this kind of situation well they ration stuff so what you can do with the ring vrf is they're very good for rationing you can you could have an EU ration card or something with these things and you know if you're buying mustard and there's no mustard then it then the machine asks you to tap your ration card and it asks sort of mustard in the week and some counter based on how much mustard you're allowed to buy in a week and now what we do is we handle this exactly like exactly like other

blockchain money or like Chum chummy is more like a show me an ecash we just look for all these nullifiers and where we just save the nullifiers but now we only have to save them for about a week we don't have to save them forever like we do in something like zcash um or whatever the time thing is now us being blockchain people this is awesome for us if there was an e-ration card we could use the hell out of it to get like you know you have a pay-to-play game on chain and you just you and you just you you get so many free plays per day or whatever um so we can actually use this thing in a lot of ways uh to like rate limit

stuff that happens on chain and anyway in general this is a rate limiting thing I want the climate change Direction with the slide but any kind of rate limiting application is very nice um okay now specifically in the climate change case there's something else really cool here so um if you think about certificates which would be the other kind of way you would construct this kind of thing um certificates um are commonly a bit uh in that like the cas were issuing fraudulent certificates which is why we need the certificate transparency system uh in the covet yeah there were all these

fraudulent coveted certificates issued by different countries Etc it just leaks the keys leak the somebody that at their issues fraudulent certificates whatever the ring in the ring signature helps us fix this because it's just a database and it can be audited um now it also brings some problems depending on how we want to build it it's non-trivial you know like we could that's a lot of complexity I don't want to discuss in the talk feel free to talk to me afterwards but it's you know but basically the ring actually solves us a lot of problems without having to build something like certificate transparency on top okay last thing I want to tell you about is a protocol that would be you what we're using this for at the web3 foundation and polka dot so this is a

beautiful sassafras tree um many of you in this room have a affinity for this plant even though you've never heard of it um the um but it's uh anyway um the oops Yeah so so it's just a acronym and it's a it's basically if you've heard of these things he's like damn bunny has a paper on secret single leader elections it's how you have a block production protocol that produces like one block every six seconds with only one block producer and the block producer is anonymous before they make the block that's the goal and so it's a absolute so fixed time block production with uh with the block production being anonymous so

um what we're going to do is we're just going to have a schedule of block production and the schedule is going to be given by ring vrf outputs and we're going to just people are going to anonymously announce these ring vrf or block producers are going to anonymously announce good ring verif outputs and then we're going to sort them and this is a bit like so vrf Protocols are commonly like card games and this is a bit like Playing Cards Against Humanity you sort of you put your card down and then there's this anonymity system of shuffling the cards and then all the cards are flipped over and the fact that it's on the table is the proof that it was your that it was one of the proper cards and here we need to use the ring vrf for that

and okay so advantages of sassafras so the other competitor for uh uh a secret single leader election is this kind of on-chain Shuffle thing proposed by Dan bonnet which various ways optimizing it um it gives you better anonymity than sassafras because sassafras's anonymity is really the network layer anonymity which is weaker it's like you use Tor or use some other kind of network thing um or mixnet whatever or one hop Mix net is what we'll actually use so it's weaker anonymity but the thing is we can we actually know what we want is in tour you don't know what you want the anonymity for so it has to be really really strong and it's not but so you're sad but here we know exactly what we want the anonymity for it's to get good

on chain Randomness and and some other certain specific properties like difficulty and censorship and whatever so we can we can analyze it and um so we get randomness of about the quality of prowess which is not the best but it's pretty good actually um and it's vastly more efficient than bonus Shuffle stuff and another cool thing so um is so block producers know exactly when their slot is coming in in advance which is either an advantage or disadvantage but in our context it tends to be an advantage and they can even prove that they have their no when their slot is coming which is very cool and if we slightly if we add a little

bit extra into the ring vera for use it in funky ways then we can have essentially a tour-like circuit to each upcoming block to each upcoming slot to the block producer in that slot which means that users can just send their transaction directly to a block producer this is a bit like what Solana does it's a bit like why Solana Falls over all the time but but it uh if you say I'll have a mempool as a fault back it's fine and what it means is that most of the time you can avoid the mempool which saves actually if you're using your crypto right it saves uh so on the crypto side it saves like 60 or something um or more if you're using snarks certain snarks and on other things it

will save you know 50 because these transactions have to float around through the mempool or something now and something like polka dot context it's less than that because we don't have that many nodes in the power chains but uh whatever um one of the other things it does is it gives you better defenses against minor extractable value and front running if you use it in the right way isn't combined with other things it's just one tool in the box but uh last comment um generally These bespoke Chains like Cosmos or or polka dot or your polka dot parachains or whatever generally chains that only do one thing aren't going to have as much anywhere near as much of an Mev problem in the first place because they can find all these funky ad hoc

solutions that are you know very simple and sassafras plays generally plays nicer with that kind of thing um so anyway yeah smart contracts are shitty [Applause] you want to take questions or yeah people have questions sure um cool does anybody have any questions for Jeff yeah cool sorry where can we read more about this uh hopefully we'll have a paper on ePrint within a month

um there's a repo actually the paper one version of the paper is just in our ring vrf web w3f slash ring ring vrf so GitHub w3f slash ring ring vrf uh it will give you a version of things um the the code that's there is really outdated we've built about three versions of this thing at this point and we're and I'm working on sort of a fourth version that it is really this thing uh Sergey in the back has another version because while I say we're going to use this version on polka dot maybe we won't because um because we since we only have a thousand validators maybe this thing is slightly Overkill and we can do something anyway that has to just be

tried because there's actually many different ring vrfs you could build um if you're if you're interested in it and well like I said we built several but for small Rings it's different what you do would be different than this other questions from anybody Okay cool so we've finished up about 10 minutes earlier we've got one more talk today uh Dimitri covertovic you're not going to want to miss it all about hashing and ZK so uh feel free to take a break fill up your coffee fill up your water and come back here um four o'clock sharp