6. STARKs in sharding with Eli Ben Sasson, Uri Kolodny, Avihu Levy (StarkWare), and Justin Drake

so happy who I think you're the one who's within starquest specializing on products which means looking at use cases specific to blockchains what would you say is like maybe one or two number one use cases of stocks to choose the number one okay this is oh maybe top few your favorites yeah sorry on Friday I presented three use cases and two of them were mainly for layer two and another one was related to clients and I didn't touch at all in layer one possible use cases I don't know to choose the that the best one of them to use but I do think that if you take the freedom to design your own layer 1 then Starks for scalability have a really good future and you can design you can think of more than one schemer Starks are using to create system which are no 10 to maybe few thousands times more scalability on top of the current solutions so I hope ok so it sounds like you're more interested in scalability then privacy which I guess is something I prefer and we also potentially more interested that the the base layer in terms of you know applications that I'm aware of on the shouting side one is making the fancy crypto that we have like the BLS the quantum secure because that is one of our n games in the design of a theorem but I guess another good one in terms of performance might be the idea of taking witnesses in the context of a stateless client and compressing those I guess I picked this two example maybe because the underlying crypto is is very easy as in the circuits that you have to work with relatively straightforward maybe primarily hash-based is that the type of scalability you are thinking of or the other type which is maybe related to state routes where you you have this full very complicated EVM a huge circuit so okay so to basically I think that when you when it comes to payment systems just payment system then it makes a lot of sense to even start with both stateless client and compressing the state at the same time so generate the proof of the state and have the status client and I would say even more if you okay the basic idea of stateless client is to say our block will be very compressed there will be just a state root in each book and the transactions themselves there will be much more compressed and why because now once we don't have signatures we can think of ways how to we basically stop to pay on space on the block and we stop to pay on storage and the only thing that we are paying now is transaction size and then we can think of ways to tweak this for example for example in which ways we represent our accounts and in which way we represent our value maybe we spread it for several types of value categories it's basic idea of sharding and in when you go to this direction you can probably get scale because because you remove the signatures and you remove the storage you can get scale of a node 10 to 20 s over on top of what idiom currently can do and the advantage that you will have in layer 1 over layer 2 here that you don't have to pay the COS cost for the proof so if you have it in early in the protocol then you pay just for the transactions or mainly for the transaction is is I given the example I clear enough or I think so I mean this example reminds me a little bit of the the CUDA project where it's specifically a payments blockchain and they use your knowledge proof to compress and provide scalability there yeah but I think that they chose to have the state on chain so at least the last lecture I've seen from them is that they store the whole lecture and and they still pay for the storage and I think you can get a little bit more efficient than that just going this path ok I mean because ok I didn't explain myself because when you keep the state on chain then every time that you transfer proof from state 1 to state 2 you have to give the Delta to other miners to update their state but if you don't store the state then you can just go on and use the transactions I think in terms of the data are you thinking of a model where every user is aware of his own balance but doesn't necessarily communicate all the deltas to the whole network to the home to all the miners it's kind of a more scalable in that fashion because everyone's in charge of their own little piece of data yeah so just moving on slightly I think one of the big downsides of Starks is like how do you produce them in the first place and how large they are and as I understand recently there's been a a grapefruit at least on the size of the stalks and is that something you'd like to talk about well first of all I'd like to say that among the proving systems that were aware of out there and we compared stark to all the teams that you know collaborated with us on this including snarks Leggero bulletproof know they we didn't get yet collaboration from them but all teams that basically ran on the same computers we start provers are ten times faster at least they're ten times faster than the second fastest proved er and this is because they have very lean cryptography and work over very simple fields and I think that so this all refers to the academic grade code which means that likely you know with our dedicated engineering team probably we'll see maybe you know more improvement in the prover running time with respect to the other technologies out there and again this is based on the underlying cryptography that is very lean for Starks as compared with other proof systems out there now regarding the argument size which is what the verifier sort of reads from the chain or elsewhere so indeed in the academic paper the length was around between like 200 and 500 kilobytes depending on the proof length and indeed we have brought this Terra our engineering and you know science team has brought this down currently we're looking at you know in the range of around 80 kilobytes for things that used to take 300 or 500 kilobytes previously and the improvements come from many different places and a better understanding of the soundness of the protocols and better engineering or various you know sub protocols in it I think we're not yet done a fee with the optimizations in terms of this argument length but I also like to point out that in terms of verification time even though the what the verifier reads is a little bit longer than in other systems the verification time is extremely fast even currently and the reason for that is that as opposed to a lot of the other constructions that use a heavy number theoretic constructions with you know elliptic curves or things like that basically what this start verifier does is you know sequentially like go through the proof computing a bunch of hashes and then a bunch of very simple operations like sores and small filled multiplications so that's where things are standing right now I'm always you know the scientist you have to always be optimistic I think we haven't seen the end of the improvements to this aspect but the prover time is already fastest by at least one order of magnitude compared against all the other technologies okay so it sounds like pruvit time really is one of your differentiators and that this will be accentuated possibly by several orders of magnitude with other engineering that will come out yes and there's also potentially hope as well for the proofs sizes to go down a little bit yes and from a verification standpoint it sounds like the basic operations are very simple and so you also have an advantage there yes indeed and I guess the biggest advantage in starks compared to the other technologies is the extreme scalability which means that a verifier even though he's seeing a computation for the very first time say described by a smart contract or by a computer program the time needed to verify a claim of computational integrity about that contract or computation is exponentially smaller than the time needed to execute that contract and this holds even for a contract seen for the very first time without any trusted set up any trust some shion's of any sort so that's I guess the biggest advantage in the Department of scalability which ties into what a viewer was mentioning that we believe you know scalability applications and solutions are probably going to be where Starks will you know shine really the most and be used the most excellent and yuria question for you so it sounds like you've identified the blockchain space as one area where you can do business so stock where is this company that you've set up with as I understand most of the people who have like the core knowledge and stocks from what I understand as well stock where has no intention to go the traditional route which is an ICO or to do things like consulting you have a different vision what is that yeah so we presented and back in a few weeks ago back in at consensus in New York and Ellie was on stage and he said there's no ICO and the volume of emails coming in asking them about participating that ICO increased tenfold so it seems like if you want to do a nice seal and the most efficient marketing is to say you're not doing nice so that said yes so our intention at this point is to see if we can commercialize this technology without having our own Park chain we were identifying a whole set of applications that are both layer one and layer two and and our hope is that we can be one of the first participants in this ecosystem in the sense of sort of a layer of college technology providers to block chains and it remains to be proven that sustainable businesses can be built that way I think that we've identified such a path I think in fact we we see several different avenues that building a sustainable business but I think that quite a few other players are concerned about that and I think that the ecosystems at large should-should should take that concern seriously in terms of how can new participants we regardless of the current ridiculous opportunity cost item I hope that window is closing in the sense of the ease of minting your own token and having your own ice he'll be even even once that speculative bubble goes away this opportunity cost right now I think sort of pulls a lot of people in that direction but even once that speculative bubble pops I think the industry should consider and think very hard about how to incentivize developers and outside parties to contribute knowledge to existing infrastructure and existing block chains I think that's a a fundamental question that seems to me very much open okay so you're experimenting with new models and one of your key aims is sustainability from a business perspective okay and from what I understood briefly reading one of your posts that could go in the direction with with partnerships with existing block chains where you don't build your own one but you partner with other ones or potentially going down the route of specialized hardware yes so that long term I think that custom hardware is one interesting direction providing services in the context of generating proofs I think is another interesting model with recurring revenues there the basic notion I think it was alluded to but I should just state this clearly the basic notion is that whatever off-tune computation one wants to conduct can be done off chain and call it AWS prices and the only thing that needs to be done on chain is this is a verification of a stark proof that for that computation which as Ellie said is it comes at an exponentially lower computational cost so we think that's sort of an appealing concept in the sense that it allows a lot of people to consider doing meaningful off-tune computations and feed that into a blockchain infrastructure okay great so and in the long term potentially does this vision to have specialized provers and I guess one of the nice things which enables that is that the previously they spent all this computational resources but at the end they produce a proof which is trustless and that's that's a very powerful trait of proof systems as this they say the proof is in the pudding so you don't need to go and interview the chef inspect that in the kitchen all you need to do is look at the proof and verify that that's indeed very powerful and and another point worth noting in this context is that to the extent the inputs to the prover are shielded then the prover has no no way of of in any way censoring the participants and in the computation that's also very important assurance I think to the general public ok great so the provers don't really have much visibility as to what they're proving and so the there is this sense of resistant that it's built into the system exactly ok great and so I guess this leaves the question how do we get from today to this end goal and from what I understand I think it'd be fair to say that maybe in the next year or two there's going to be a lot of building infrastructure and building ties with the community potentially releasing stuff open source making security audit to build trust as this is very new technology can you talk more about how you intend to engage with the community so yes and pretty much the roadmap that you describe meaning there's going to be certainly significant chunks of open source then we're gonna put out there some subject those of course to secure out it's an open discussion with the community around the IE the ideal cryptographic primitives that want to work with and in the process in parallel to this continue and explore layer 1 and layer 2 applications and we seem to be identifying a fair fair number of these sort of right now so so alone I think we're far from from being done and that's it I think there's a lot of sort of call it market development or about market education in terms of both understanding what people want to do but at the same time explain to them what it is that Starks can do for them and sort of get them to think about their problems with that capability in mind mm-hmm and in terms of kind of proving to the world that stocks can be used for scalability will it make sense as a strategy to focus on one single building block and making it very fast something like hash functions making them friendly to the Stark provers so that you know you can use this basic building block to build other things like signature education of course it would seem that that doing that efficiently would be of value to essentially every single application that we that we look at so that that seems to be a very productive move to make that the entire ecosystem move forward yeah and I'll just end with one technical question before opening out to the audience so yesterday we mentioned Mincey which is this hash function with a low multiplicative complexity eliyahu like do you see MMC as a like promising way forward it's one thing that we need to explore I'll just mention that you know the numbers that you get from Rhino constructions or not you know not you know we need to clock and optimize all these things but they they're also very you know friendly and there are other things like you know well okay there you're gonna lose quantum security but you know things that work over prime fields like Peterson and Schnoor and things like that are also as long as you're working we're the same feels also quite elegant so mimsy is definitely one candidate you know or our engineering and science teams are gonna look and basically clock and measure and give parameters for all of the different candidates hopefully also suggest a few new ones and then we'll we'll be like sort of a cost for different things and memc will be included definitely great because I guess it would be really to stock wise advantage and to the advantage of the whole ecosystem if we could somehow standardize around a hash function which everyone would use to build the protocols and then that would kind of make these protocols much more approachable to stop provers yes that's our hope okay questions I have the most obnoxious question possible but I'm just curious what is that like what do you expect as a timeline or kind of seeing Starks used everywhere because it definitely feels like one of those technologies that can be like a fundamental base for tons of other applications and systems so like well I mean you know we'd hope for them to be used tomorrow realistically you know as with all new technologies takes time so hopefully let's say within a year or you know to 18 months we'll start seeing some industry grade you know stuff that people can use I just want to mention the academic code is already available on lip stark on github under MIT license so those were you know fearless can already start using it there you know some examples there and interfaces there is sort of a tiny room like interface and you can build your own errors these are algebraic intermediate representations and you can start using the system already so but realistically I'd say you know one year to 18 months but it should maybe you know qualify this that making predictions about deploying systems as everyone here knows is a very risky business I'm gonna demonstrate my ignorance with this question but I'm gonna ask anyway because I'm so excited about this technology you guys talked about the size of proofs and how that's come down quite a bit recently is it also the case that computing proofs takes a lot of time a lot of resources and if so is is that under active research and how is that looking so computing proofs takes a lot of time start provers are the fastest provers out there already by a factor 10 over the second fastest and by many more factors over you know not the second-fastest and I urge you to look at the stark paper which is also available online there is a you know a bunch of figures there that show the running times in single and multi thread I just want to say from a ten thousand you know meter view provers are the heaviest part in all proof systems and they will likely remain that way in all proof systems specifically the stark prove er already currently is extremely lean to the point that it would require I think immense breakthroughs theoretical ones to improve on it theoretically not on the engineering so the engineering there's a huge room for improvement the orders of magnitude many of them but theoretically so without going into details to prove you take an execution trace you apply to it a single FFT which takes time T log T and after that you have a fully parallelizable computation that takes you six times you know some parameter that is linear in T arithmetic operation so we're a very simple field that's the Fri prover and basically then you apply hashes again fully parallelizable I think it's very unlikely that we will see significant asymptotic n't we're already looking at what's called strictly quasi linear running time o of T log T and we don't even know now we'll say something as a theoretical computer scientist we don't really know of any generic reduction from an NP language to let's say three set which is the simplest of you know and the most fundamental one of np-complete languages and the original you know NP completeness paper of of cook we don't know of any reduction from a generic language to 3sat that takes less than n log n time and work with with Stark's were already at the n log in upper bounds so I don't believe prove ur time asymptotic you know mathematical will go down anytime soon though I hope to be pleasantly surprised there's a lower bound of T you know and we're already have an upper bound of T log T and reducing that log T is gonna be very hard but you know building systems using good engineering can shave things off with several orders of magnitude and there were very optimistic we talked yesterday in the context of like finality and a blockchain certain types of applications do or don't make sense you know so for making a point of sale purchase maybe you have a ten second limit in the certain types of transactions we might need faster finality or slower finality is okay so based on what you just talked about are there certain types of applications which you think will or will not work well with Starks given the complexity and the amount of compute time required to compute the solver so I think that end-user and again I urge you to like download the stark lip stark and play with it z cache style you know shielded transactions already on the academic code probably if you if you match the numbers take very few seconds on a any standard laptop that will likely go down by you know an order of magnitude or two so I think it's completely reasonable that a smartphone can do a shielded transaction stark style in a second or less that's very reasonable the main power of Starks again is in the huge scale computations they're you know the prover is the bottleneck I think that there as well we will at some point see specifically tailored systems and possibly Hardware dedicated for it that will dramatically increase you know latent sorry decreased latency and make them these systems very attractive to everyday use I was just so there was a speaker earlier that was that showed a picture of this HPC cluster that that does what was it like more than a petaflop of or forgot how many and was just thinking wow if you know if we had a petal number of the kind of operations that we need you know you could probably compress the the proving of the validity of all of bitcoins blockchain to you know you could prove all of that or at least half a chain or something like that and then a smartphone could verify the validity of the utx so in fractions of a second so and I think we'll reach that point it's not there's no reason we shouldn't I feel like you've probably done of applications that are you know make a lot of sense so maybe we'll give some like it would be nice to have some basic intuition about like okay this is where a stark is useful versus this is not or something like that okay so you are not here on Friday yeah no it's okay I only mentioned few use cases there are many more so in terms of it here um you can think what I what I mentioned on Friday let's do it quick it's the privacy solution for shield transaction this is the most basic one that people already knows and familiar with I already explained a little bit about two approaches for scalability the first one is from the point of the transmission size and the other one which is more like can save much more is the computation perspective meaning that you can generate any proof of chain computation and have the contractors validate it I also mentioned compression of the chain in the meaning that clients doesn't have to validate state we're downloading all the clocks they can just validate a proof I can mention things also outside of the of the blockchain itself for instance you can validate that exchanges do hold enough assets in front of their liabilities for their users this is something that Starks specifically can be useful and good at because of the large scale of the processes sometimes need to generate and there are also some other simple use cases that still relevant for themes such as layer 1 solutions for instance replacing VLS signatures which star basse scheme that me we maybe talk about later today I want to give one more example we're sort of in the midst of conversations with the brave and what brave need to do is demonstrate to the general public once a month that tokens were fairly divided based on users usage and preferences etc now this is not something that would generally it will require a supercomputer but doing it on chain is prohibitively expensive from their perspective I think it's a very elegant test case of Starks because this is something needs to be done once a month right now they're sort of relying on band Brendon Ike's reputation so to speak you know in a real way and and in a positive way but he fully realizes that this needs to change and the trust needs to be established not because he's a trusted party but it needs to be established through the protocol so I think it's a very elegant case of a an opt-in computation not terribly frequent one which he wants to be able to provide that chain with a proof for on a monthly basis and looking forward beyond decentralized blockchains right I guess we all share the belief that at some point central trusted parties you know governments or various you know important players will start using blockchains for audit ability and accountability and things like that so you know if any one of these institutions a bank a big exchange not crypto starts putting say Merkel commitments of the daily state of the system onto a blockchain then with Starks you have basically unlimited capabilities for proving later on with zero knowledge if the need be and proving things to individual users that you know a month ago when we committed something you know your state your account your information your private rights were in the state so I hope I guess we all share this hope that you know we're going in that direction and that the decentralization accountability and irreversibility will someday be adopted by you know the various central trusted parties that anyways run the world right now apologies if this was discussed on Friday we still have a second I wasn't here on Friday and maybe this is a question for the etherium folks in the room but pragmatically speaking what do we need to add sort of support for starks to to aetherium release to verifying starks some of the obstacles quickly so first of all like a lot of the start constructions are done over binary finite fields and currently doing operations over binary finite fields inside of the EVM is totally not efficient so unless we want this to be kind of get it to easy if your m 2.0 starting exclusively with that though you would need a hard hard fork to add the pre-compiled is for like basically binary finite field operations though it could be done pretty generic like you basically need one thing that says multiply two numbers in some finite field will some bit that specifies what the what the binary field is and even if you don't do that you can like totally come up with stark silver prime fields as well though it has more efficiency issues the other one is that the size of a star keeps you agree writes to a few hundred a few hundred kilobytes and with aetherium is current tech yeah so limit of eight million the theoretic single block is kilobytes and that to in would the cost of stock verification and so unless you want to have a super some multiple and I've read that aetherium the watching like using using up eight million gas for a proof like yes a legitimately very expensive so you need to come up with possible like some kind of like application specific batching technique or whatever that would make that practical for the average user of a system one more thing I don't know that for example if you want at some point some point in the future to prove things on the state or the history of aetherium then you want all the opcodes or all the opcodes basically to be somehow start friendly because then you can translate them efficiently to constraints so this is one more thing that you can help start including so I think you you started off with a really great team and and you're hiring can you tell more about the team because I think you really do have a world-class team sure yes so we're we're hiring we think of these guys as bilingual in the sense that there are very strong engineers and very strong mathematicians the intersection of these sets is smaller than one would hope probably not in this room but out in the world and I think that's the main characteristic of our R&D team at the moment and the realization that in the foreseeable future we're going to run in parallel pushing on both the engineering front and the science front and that's something that were fully prepared to do indeed the blockchain front and some day in the hardware front