The State of STARK Tooling

Transcript

at maenette in the coming weeks we'll be launching as the scalability and settlement engine used by diversify which is a noncustodial trading you know decks over aetherium and we hope to be servicing other exchanges as well also expanding to the area of Nan fungible tokens and gaming and things like that we released no token we have a funding of 40 million dollars from two rounds of equity and a theorem Foundation grant so usually we talk about scalability about how we can process you know around ten thousand trades per se per second on

aetherium and as I said that will be servicing non fungible tokens but today that's not what I'm going to be talking about rather it's about how we can sort of access and work with the larger developer community and I'll be talking specifically about two projects into potential ways to integrate and work with code released by stark ware and in two very different contexts so I'll start with the first one which is going to be open source code that we already have committed to deliver and we'll be delivering in the summer and start looking to integrate with developers in the spring and this may interest folks both on layer 1 and layer 2 we're

looking for cool projects and you know working with cutting-edge efficient ZK Peas so let's talk a little bit about the open source code that we're going to be delivering so this is the start friendly hash project that we've took on ourselves about a year and a half ago and I just want to tell you a recount the history of how we arrived at it so in the summer of 2018 when we were a much younger and smaller company basically the very first project that we took on ourselves was we received a very sizable and generous grant from the etherium foundation and the nature of the grant was a sort of milestone dependent and it requested us to select

recommend the stark friendly hash and to implement it in C++ and the statement we need to prove is basically a proof of a hash chain that you took a long file and you produced its hash correctly and generate a proof for that so the specs for what we needed to do were quite daunting at the time we needed to be able to generate proof for a rate of more than 100 hashes per second and this has to be done on a quad-core machine with 16 gigabytes of RAM at the time this looked quite hard to achieve when we took this on ourselves the grant also states extra bonuses if we managed to hit higher

targets a rate of a thousand hashes per second on a quad-core and even one further extra bonus if we managed to reach ten thousand hashes per second and what we need to prove is basically that we inspected a hundred K long hash chain that corresponds to roughly three megabytes of data and the proof must be smaller than 200 kilobytes size and also it must be verifiable in ten milliseconds or less so this was what we were asked for a year and a half ago what happened is that we use all of this funding that we received in order to solicit a bunch of new constructions of stark friendly hashes because the list of existing hash functions wasn't quite

right for it to be proven so you know standard hash is like shahtoosh a3 Blake and others they were designed to optimize and minimize electrical consumption or the speed on on standard Hardware but they were not designed to minimize the time it takes to prove stuff over them so we understood that we need new constructions and sort of we again with his funding that we received from the etherion foundation we went ahead and funded a whole bunch of research and also other research came along and basically we are now the state where basically four new constructions have been suggested the first of them was broken that's the Jarvis pepper one it was the very first one and then we

have the hadees MMC which is stark had posted on already being deployed by various teams you know among them oh of one and loop ring vision rescue which is another a family of hashes and the GMC family so all of this happened over the course of the past two years and most of it was funded from this grant so this is what happened first the second thing that we did is we led this process of public scrutiny all of the constructions and this included several things first of all we understood that the algebraic crypt analysis of these ciphers is going to be extremely important and indeed the very first attacks on Jarvis and pepper were of this nature so we contracted the world

experts on this matter who actually sit in Paris professors Jean shells for gel and Ludovic Palais and we asked them to specifically target their algebraic crypt analytic tools on these constructions and we have received a report looking at all kinds of weaknesses and strengths of these different constructions we also started a challenge a public challenge that is currently running basically where if you break the hash you get the cache right there are smart contracts deployed on aetherium that you can now access and if you can find a pre-image for any one of these challenges that haven't been broken yet then you can get your ether automatically and a bunch of

the small security challenges have been broken the 45 bit ones the best of my knowledge none of the 80 bit ones have been broken and this of course helps us get more confidence as to the security of these new constructions the last thing that we did is convene a dedicated Committee of symmetric crypto analysts headed by Professor Encanto we'll also sits here in Paris so this committee took place here in Paris we attended it a bunch of folks from from Starke where there were representatives from the etherium foundation zak Williamson's and Don kite faced were there and of course 10 symmetric crypto analysts you know like the best experts in the world for this they looked at it and they

generated a report that is already publicly available you can write to us but we'll also soon post it on on our way site and basically what the this report says is that among the hashes it sort of feels least you know it feels less comfortable about GMC for all kinds of symmetric cryptanalysis reasons it feels slightly more confident but still there's some some some doubts or question marks around stark it and puts it on so it's not like there is an attack but there are some some things that make them feel a little bit uncomfortable and they felt most comfortable with vision and rescue that I should point out that in terms of their start friendliness actually vision and rescue are less friendly than GM's

and and posted on but they are you know currently it the best of our understanding a little bit deemed a little bit safer from the point of view of their security so what's going to come next is that during spring which is soon starting well first of all generate a final report with our recommendation and we'll also start a code audit process because you know you need this code to be audited by independent third parties at that point we'll also invite you know various developers who want to start building on this code to start accessing it and using it and working with us or independently on it and then a summer of twenty twenty that's when we

you know promised to finish this project and we will be releasing open source code for everyone to build on under some license that the etherion foundation will deem fit I think it will likely be something like around you know Apache or MIT but something very you know usable so now I so it seems likely as we're standing now appending you know further cryptanalytic you know scrutiny but it seems like we'll be recommending and implementing rescue as the start friendly hash and you know it's its detail this this construction is detailed in an academic paper by Abdullah Manali tamela show myself seaman Doogie and Alan Shapiro AK and

you can find it online so I just want to tell you how it looks like and why is it there sort of versed friendly so the state as you're generating the hash is comprised of 12 field elements each field element is around 60 two-bits large and the sort of way that you hash things is basically you operate in ten rounds and all of these rounds look the same so let's focus in a little bit on how a round looks like so you take your twelve field elements and you apply this transformation you first of all take each field element and you take its cube root the cube root is uniquely defined in this field there's exactly one value

that will give you the cube root modulo P to the P we're working with so you took cube roots of each one of these twelve field elements now you get twelve new field elements you multiply them by a fixed MDS matrix as you get twelve new field elements and you add a round constant to this thing so you add like a fixed vector that is sort of random looking and then you take these twelve field elements and you cube each one of them again so basically taking a cube root doing some sort of linear mix and then taking cubes again and you do this ten times this process so you take your output put it in the next row and fill it up so in terms of what we call an algebraic

execution trace you can see that for one invocation of the hash you get an algebraic execution trace that has sort of twelve rows in this case and ten columns or ten rounds in a total of 120 sealed elements for specifying this algebraic execution trace so now the next thing I want to tell you is that this is actually today the fastest proved er in the world for a hash chain so what is the statement we're discussing the statement is I know some file F such that Z which is the public input to the statement that everyone can see this Z equals the hash chain of F or a hash chain of a file is computed by I

mean you take your file and think of it as a sequence of words let's say each word is a 62 bit you know integer that we think of as a field that I'm in and what you do is you apply your hash sequentially to each one of these words one after the other okay actually a word is is not sixty-two bits it's actually more like 240 bits and the kind of proof that we're doing is as ek stark actually the code we're releasing does not have zero knowledge but that's one of the projects that you know we'll be soliciting is adding zero knowledge to it but it is a stark which means it is scalable the proving time is quasi linear the verifying time is exponentially smaller than the file size it is transparent so there's no trusted

set up and it is an argument of knowledge meaning that seeing a proof actually convinces you that the entity providing the proof knows the file not just that there exist some file that would give you this okay so I want in terms of scalability what we obtain is something that compresses a file that is roughly three megabytes long to a start proof it's gonna be less than 100 kilobytes long now why do we say it's the fastest prove are in the world so we we just had to update these slides because just yesterday loop ring announced a yet faster version of Lib snark err you know their version of a faster start prove er that actually manages to do around 160 hashes per core

which is beautiful for snarks or around 640 hashes the previous world record which I believe came from the coda project was 30 hashes per core so it went down up by a factor 5 and now is around 160 this is for the hash function posted on which is a somewhat snark friendly with you know security that is a you know there are some question marks around the security but it's definitely something that might be usable what we can do for Starks is if you take Peterson which is provably secure under assumptions of the discrete log we can run on something like this quad-core computer at a rate of 64 hashes per core

which is you know used to be twice faster than the fastest snark even for a snark friendly hash now it's a three times not as efficient but for rescue which is slightly less friendly than posted on but still friendly enough we will definitely release code that will be more than 600 hashes per core you know we we say more than because we're still finalizing the code it might be somewhat higher than that reaching a total of 2,400 hashes per second on a quad-core machine I'm reminding the the the the challenge asked us to go at least over a hundred hashes per second so we're sort of completely beyond that and actually even above the first sort

of bonus level of a thousand hashes per second okay and again this is the fastest prove are out there now if you ask yourselves why is this faster than what you can do under number theoretic instructions that also require a trusted set up like a snark the reason is I mean there's many reasons but let me just mention three important ones first of all because we don't rely on any number of theoretic assumptions we can use any field that we like so we actually go with fields that are supported by very fast hardware you know just commodity hardware it does them very efficiently so we're going for a field that has less than 64 bits so that multiplication is extremely fast and you know you could think of it as if

there's already an ASIC that is dedicated for doing this fast multiplication at one to two nanoseconds per multiplication second reason is that we get to choose which hash we're using in order to generate the commitments for various parts of our proof so the way our proof works is that you commit to you know stuff in the proof and then you need to reveal information based on queries so we can use the fastest hash out there we picked Blake - maybe if Blake three is gonna be faster someday this is another route for improvement and the last thing is that because we're working in a system that does not require bilinear pairings we can basically work with any degree of constrain so we can work with degree

constraints of degree three remember that the construction of rescue talks about cubing and cube roots and because of that we get roughly a factor two efficiency over what would have happened if we would have used something like r1 CS and bilinear pairings so these are some of the reasons why the is faster and and again it is the fastest prover in the world for these kinds of statements now when we release the code we'll also offer the users or developers this sort of trade-off that they can play with so there is a parameter call the rate of the code and you can play with it a little bit so if you go with a baseline of a rate of 1/4 you know that's sort of the baseline you'll get a proof that is somewhat

large around 80 kilobytes not 80 bits of security if you want the proof size to go down you could do that but then your proving time goes up a little bit so you can play this trade-off and same thing if you go down to a rate of 1 over 16 your proof size will go down even further but your proving time will go up a little bit and the same thing happens with you when you go to 120 bits of security so just to summarize the next steps are first of all in the summer we will be releasing open source code for this you could say that this is the first time that stark was releasing you know general open source code definitely for for provers I mean we did release things like the Stark 101 educational

code but this will be production grade audited code that for provers and verifiers it will go through auditing in the near you know in the next 3-4 months and sometime in the spring we're planning a workshop for developers who want early access to this code and want to build on it and start using it again this will be open source code at the end of the day and we just hope and believe this will be you know starting point for a lot of cool projects based on this so if this interests you then please you know apply to us today you can come up and talk to us or send an email all at the end of the talk I'll show you where to send your email to to sign up now the next thing I want to talk is a different set

of developer tools that we'll be releasing even sooner and that is the what we call you know not scalability but rather a snail ability so using crypto to warp time now already in 1996 there's a beautiful paper by Ron Rivest Adi Shamir and and Wagner they talked about using cryptography in their case it was RSA in order to create a delay in time to have something that is the analog of a sealed envelope that automatically opens up after a fixed amount of time and this is extremely useful for a lot of applications things like you know auctions you want the

sealed bid auction where people can put the envelope and it will definitely open up without any ability to retract your bid but no one knows what's in it till the time has elapsed you can use it for the deferred payments let's say you know you're renting an apartment so you want to have these payments that will open up once a month but you can't open them before and you can't backtrack on them and so on and so forth more recently the notion of a vdf of a verifiable delay function and by Bonaire boons but no and Ben fish has gained a lot of popularity it is extremely useful for proof of stake mechanisms and there are a lot of chains that want to become proof of stake or start off as proof of stake so

this is sort of the analog of a roulette wheel roulette wheel that is spinning and everyone knows that deterministically it will have a fixed output but no one knows in advance what this output will be so what I want to tell you about today is about code that we'll be releasing basically that gives you you know for the price of one stock you can get both applications you can have a mechanism or a smart contract that supports both delayed randomness as in the roulette wheel example and it also supports a time lock which gives you you know sealed bid auctions for a whole variety of things Vitalik was mentioning the Neva right the mining extractable value auctions

you could use it for auctions over all kinds of defy contracts and again we'll be releasing these things and if there are developers who want to start building on them or using them please talk to us so we can spec them and here I want to explain a little bit about what exactly is going on and how do we get one mechanism that gives you both things so a good analogy to have here is that of a good old jigsaw puzzle and there are three properties that are important to us a jigsaw puzzle right if you have it all sort of already made up correctly it's very easy to disassemble and scramble it up it's certainly much faster than going in the other direction of fixing it up and putting all the pieces in place so that takes more time

but once all place all pieces have been put in place correctly it's very easy to verify that that's the case and to see if you know it's the correct correct puzzle being built and there's only a unique way in which you can rebuild the puzzle so we'll do something that is like this but is cryptographically and we'll use this jigsaw puzzle to get to applications so you can still have this jigsaw puzzle you know example in mind and if you have a jigsaw puzzle functionality you can first of all get a verifiable delay function so this analog of a roulette something where the randomness is already deterministically baked in from the start but no one knows what it will end up being and how do you

get that so you take a blank square paper you sort of draw the contours of a jigsaw puzzle so it's completely white and blank and now you actually mess it up right and after you messed it up you take each one of these pieces and you write a random coin toss on them and then you throw it to the world and you say here's the randomness that I'll use right this will be you know the way I decide the the this you know who gets whatever it is or this is the randomness the way I'm gonna elect my leader so you wait and it takes a lot of time for this puzzle to be constructed once it is constructed everyone agrees that this is

a unique correct way for it to be constructed and now the randomness is revealed and no one knows much in advance what this randomness will be but you could take the same jigsaw puzzle and reverse things and get the other functionality which is a time lock puzzle so you take your large blank piece of paper and before messing it up you write your secret your secret right from left to right or whatever in some fixed way now you scramble it and throw it to the world so it will still take a lot of time for it to be unscrambled and put together and then once that is done right the whole world knows what was this secret that you locked in it at the

start of time but it's the same functionality that you can use to get both things so this is what we're going to be building and releasing so what we need is a function that has very quick disassembly but is slow to assemble so in mathematical terms you want to function such that F is very fastly computable but the inverse of F takes a lot of time to compute and what we'll do is you might wonder where does a-star come in here so it comes in because we'll use it to speed things up even more of the verification so we'll start with this thing that's in a time a symmetric encoding something that is fast in one direction but slow in the other and then we'll actually oops okay wrong button so then we'll actually

speed up the reification by applying a stark to the fast direction and this way save on on the verification cost so here's the function I mean there's the function that we will use for the time lock or for the you know for the fast direction it's a very simple function basically you repeat many times let's say 1 billion times the process of taking x cuban it and adding some number to it let's say 42 and you take mod p you repeat this a billion times it will take one second to compute this thing and that's the way you lock something

and if you want to unlock it you're gonna have to run the reverse computation which is easy to define but harder to compute because at each step you need to subtract 42 which is easy but then you need to take a cube root modulo P which will take you roughly log of P men multiplications so if you do the math if it takes you one second to lock something because let's say a billion steps took you that long unlocking it will take you two minutes and this is a very sequential computation we don't know of any efficient way to make it much faster and the analogy here is that you want your computation to be a little bit like you know having babies

so one pregnant woman will have a baby after nine months but we don't know of a way to take two pregnant women and you know get a baby a healthy baby in four and a half months so that's the kind of function that we're looking at here if you start with 30 seconds of a time lock it will take one hour to unlock and I just want to mention that locking you know for the purposes of sealed bid auctions is a very simple computation to do right you can write this code it's up there and then probably you can do that very efficiently even on your smartphone so the locking mechanism is very efficient and one way to verify that the solution is correct is just to go and redo the sort of naive computation of

the locking right going down the quick route but if you look at the gas cost for let's say 1 billion multiplications this will be roughly 1 billion gas on aetherium and that's far too expensive to contemplate so if you use a stark prover that proves to you the fast direction now the gas cost shrinks dramatically and it is practically in the code that we built only between one and two million gas and if you were to run a verifier for this it would be under 10 milliseconds to verify so not one second not 30 seconds but only about 10 milliseconds so here are some concrete measurements for the code that we wrote if you're looking for a delay

of one second sorry if you're looking at the delay time of 2 minutes we're locking something 4 it would take one second the proving time on our machines and these are big machines 72 cores so generating the start proof will take you roughly half a minute this half a minute doesn't need to start after you finished the delay it could start even before that so doesn't have to be lag time and the proof length is going to be 40 kilobytes and around one and a half million gasp to verify and similarly you can see that the things scale very very slowly so if you go to one hour of delay the amount of gas to verify is only one point eight million gasp so it's still very small

and you can also batch many statements of this form and still get essentially the same gas cost for verifying all of them in one shot now I just want to mention that there are potential speed ups for the delay right you can get it to be lower than whatever it is two minutes here so someone could spend roughly 1 million dollars spend nine months and get multiplication that is one order of magnitude faster okay you could also do use parallelization and sort of get a faster amortized delay by solving not one could cubic equation but sort of composing several steps two or three and finding one route for a higher

degree polynomial you can fight both of these things by changing the modulus by using more variables than one and by increasing the degree and if you combine all of these things together it will be harder it's not impossible to shorten the delay but it will be much much harder and much more expensive to significantly decrease the delay which is sufficient for our purposes so there are other alternatives to getting a vdf one of them is based on RSA that's the thing that is you know currently pursued by the vdf alliance also class groups is another thing that is being deployed on the Chea blockchain the advantage of Starke is first of all it is the only

system that is post quantum secure it has the smallest modulus size which means that the you know difference between the hardware that we'll be using in the fastest possible hardware out there will likely be small it's transparent no need for a trusted setup that's also shared with the class groups and like class groups it is available today we have the code written up the other biggest advantage is that you can use it for both things both as a time lock and a verifiable delay function so to give you some examples how you can use these things in actual applications because again we want to solicit teams to start using them or contemplating building on them so let's suppose you want to do a

sealed bid auction and let's work with a bidding phase of you know one minute and a time lock of one second and proof time of half a minute so basically you announce that the auction bidding phase is going to take one minute and your smart contracts or let's say roughly four blocks now if I'm gonna lock my bid it takes me one second to compute on my smartphone so I do that and now I post my bid to the it's in a sealed envelope I post it to the you know blockchain no one knows what its value is it will take one minute for it to be unlocked even by the fastest computer sorry it will take two minutes for it to be unlocked even by the fastest computer so by the time my bid has been unlocked already the the

bidding phases you know long since closed we have to wait till the very last bid comes in and then unlock that so it takes us three minutes right one minute for the auction phase two minutes for unlocking the very last bid and then on top of that with in at most another half minute you get the stark proof likely even before that and now you know the who you know what were the things you know sealed inside the envelopes and you can get one stark proof that attests to the correctness of all of the bids that have been placed so it's one gas cost of let's say 1 to 2 million gasps this supports the all of the bids that have been placed there and this can be

run as a service this can be integrated into you know your auction system and so on and so forth or into some dphi protocol here's another application that uses vdf for generating cards in a game in in a fair way so you want to generate your cards randomly but without the miner having the ability to control and give you better or worse cards so the way we're going to generate them is that a user comes in and purchases a loot box so no one knows what's in this loop box and now we'll the randomness from the blockchain header the latest blockchain header and will tell that user look this randomness together let's say with your user ID

will be you know thrown into a PDF and the output of that will determine the kind of crypto Kitty or you know gods Unchained card that you get or something like that so no one knows the randomness for a two minute duration so the miners can't really you know collude to give you better or worse cards and your randomness is deterministically tied to the randomness that you your cards are deterministically tied to what you threw in at the very start of time and no one can mess with it so there takes a half a minute for the start proof to appear and again you can batch and have one proof attesting to many different random misses if the need

to be and now you can open your loop box and be comfortable that you got your cards fairly so as we said there's a you know one mechanism think of one smart contract that will be running and you can apply it to both fair and earnest or to auctions and you know if this interests you so should come talk to us it's ready for deployment you get two different functionalities a delay and a time lock for for one stark and just summarizing again so in today's talk I've not spoken about stark exchange there are talks by diversify our partners in this that we'll be sharing a lot of exciting details on the

deployment of the scalability engine as part of the diversified trading platform we did talk today about two very different kinds of ways to interact with us as developers one is to you know work with the C++ code and add functionality to it for the stark friendly hashed it is the fastest start or zkp approver out there the other one is sort of thinking about how to use and integrate and build with the time-lock slash vdf there will be putting out there and please come talk to us here at the conference will be here throughout you can also follow us and you can reach out specifically by email if you want to vdf at starker co

or if you're interested in joining the workshop for the C++ code to a workshop at Starke or at co so thank you very much [Applause] okay so I'm told I have five minutes for Q&A there's someone there just thank you for your presentation it was really interesting I'm going to ask you a question about

PDFs in our network who actually really need the vdf so we looked and unfortunately very unfortunately we couldn't find any that we can use now because we can't really produce a six and without a six it's it's it's really you know they're not so many ASIC resistant idioms so I'm going to ask you actually very very generic questions ten years from now which direction you think vide F's will take will there be like a perfect basic resistant PDFs or there will be everyone will buy a six maybe this a six will be like included in there every every CPU and then another

question which is very practical since you have in your in Starks you have ability to do pretty much all kinds of things can you somehow use the K proofs or Starks Starks to create an ASIC resistant video okay so great questions about ASIC resistance I would like to argue that the vdf we just presented here is pretty ASIC resistant and let me explain why okay on the hardware that you buy today which runs that you know four to five gigahertz clock speed on whatever it is the latest 10 nanometer technology or 14 or whatever it is right you already have embedded within it a

pretty good ASIC for 64-bit multiplication right and it's one of the fastest thing that interests you know AMD and Intel because everyone needs a 64-bit multiplication right we can so the vdf I described here was written you know temporarily for a 256-bit modulus but we can easily build it for a 64-bit modulus and then if you think about it you know if you want to build a much faster ASIC for 64-bit multiplication it's not that you can't for sure you can but you are competing against you know you're competing essentially against Intel AMD whoever else is out there that have a very

strong interest in delivering everyone with a extremely fast you know very high grade low nanometer kind of technology so it's not impossible but it would be extremely costly and time consuming probably I'm guessing you know tens of millions of dollars to hundreds of millions of dollars to get the factor ten improvement if even physics allows you that so I would say that if you so the closer to you go to 64-bit modulus and if you go to let's say 128-bit modulus you're still the ability like the amount of dollars someone would have to put in and the time it would take to get a 10x improvement on the delay time I would say is extremely high

so to summarize I think that the stark construction that we base that we presented here and which is ready for deployment is very close to you know ASIC resistant as as much as anything can be and to answer the second question because of these reasons I believe that and I hope so but of course I'm speaking from a very particular position I hope that you know this will be the direction that all vdf stake because of the simplicity because of you know the well understanding of the basic problem that we're using as the video if this is not class groups where research is still

very preliminary this is about just you know taking routes in a finite field yeah so I think VD F's will in the long run look like this thank you okay so I'm told my time is out thank you very much [Applause]