zkSummit - Scalability First with STARK - Avihu Levy (StarkWare Industries)

Transcript

hi everyone my name is Ivo levy I'm head of product at stock where here's a picture of me few kilos less I have with me here today my colleague Michael ray observer who is also he's a co-founder and chief architect in stock where he's also one of the co-inventors of Starks stock we're include currently around 20 team members most of them R&D were based in Israel we plan to release our first product together with zero X is going to be at the centralized exchange scalability engine we have our alpha for this product coming in mid April on test net only theorem to this date we raised

40 million dollars in funding into equity rounds and very generous grant from the theorem foundation okay so back at 2017 when we started there were several projects dealing with zero knowledge proof they were all targeting privacy when when someone heard the term zkp of zero knowledge proof they always had in mind privacy and what we realized when we entered this place is that well Starks can solve privacy but they are great candidate the best candidate to solve scalability and I want to to say

this we have a very deep understanding of their alternatives we have in our co-founders we have people who convened several proof systems so we understand very well the alternatives start snarks included but we think that currently the best proof system to solve scalability is actually Starks now what makes Stark's and few other proof system fit to solve scalability so what one would expect is that if you have a computation and then you grow this computation by a factor of 10,000 then it's a very nice property if you get both the proof size

and their verify running time to stay to grow but not by much so this is the first two that you see here you would expect that the proof will grow exponentially smaller when compared to the computation and the same goes with a verifier complexity you also want that you will be able to prove very large statement right because this is how you're going to use that for scalability so that means that you want you prove it to be as close to linear as possible so that you will be able to handle with even large statements or large circuits and the less property that is of interest is that you want to be able to prove any kind of computation or any statement that you want don't want to be

limited to some specific primitives we have two more bonuses on top of that in Stark the first one as you probably know there is no toxic quake waste that means that there is no trusted set up now trusted set up they mentioned the earlier what's what people think of that it's not very good there is also a practical problem where you have to regenerate the trusted set up every time you have a new circuit now I know that there is in this new construction that deals with it and clay and plan to have a stresses set up per size of circuit but it has it on its own drawbacks and in stocks you have no trusted set up at

all the other nice bonus the to the other bonds that we've got is that we rely on Lin cryptography the first thing that comes from here is that Starks are actually post quantum secure but there is there are few more gains that we get from that for example when we came to implement our verifier smart contract on aetherium we didn't use any pre comp eyes because we are cryptography or the cryptography inside star is so simple that we would go away just with simple prime field operation and hash function and we need no elliptic curve cryptography and we need no number

theoretical cryptography nabatea cryptography so it was rather easy and not very expensive to generate this verifier in a comparable very short time I want to start by giving an overview of how a stark scalability engine looks like and then I will dive to a specific example so what's happen or Mele before this mechanism today is that users normally send transactions on chain directly to Dadaab contract the transaction normally includes something like I'm the user please authorize me and then I want to change the state from A to B and what a

smart contract will do what the DUP smart contract will do we will verify that the user is authorized you will verify that the state the previous state is indeed a and that the state after transition is B and that the state transition is valid in general so what we propose is a different mechanism where we introduce this new entity proven node and it works the following you have any option mechanism it couldn't be users it can be release on top of 0x and they generate transactions now instead of selling test transactions directly to the DUP contract they're going to send it first to the prover node the proven not going to collect

them and generate a batch of those transaction and and then is going to generate a single proof to testify for the validity of each and every transaction in the batch this single proof is going to be presented to the Unchained verify smart contract which if verifies that the proof is correct and then you can submit a miracle route of the new state to the smart contract of the job so instead of having number of operation which is linearly related to the number of transactions that goes on chain we now have a single no matter how many transactions are included in it and the single proof takes almost the same time to verify whether it's thousand transaction or ten

thousand transactions so this what gives the scalability when you go to the specific case of stock decks what you see here the Dex is can be every layer this ruler sent normally settlements to Dex contract can be 0 ex contract for example and those settlements are very expensive to verify on chain because they include several storage operation they include several signatures you have to send the signatures so in total one settlement will cost about 150 thousand gasps one performed on chain what you what one will do with the stock tax instead is that settlements will go to

the proven owed proven node will collect them to a batch and then for each and every settlement he will prove the necessary condition for this settlement to be valid so he will prove that users signatures both on the maker and takers side are valid he will prove that every side in the settlement had enough had sufficient balance before the settlement to whatever tokens they're mentioning the data that are mentioned there that he changed the state correctly for that he is using a miracle tree of the accounts so these are basically proof that if he has a batch of settlements for all the settlements ifs in valid

signatures from both make her integral and that the state transition is correct and state transition is represented by the state of the miracle tree that contained the account balances then we generate the single proof that that attest to this to this batch and send this to the verifier contract the verifier contract if the proof is valid going to present the Dex contract with a new miracle root that commits to the new state of the accounts in this exchange when you look on the most important parameter to look on in scalability system they wanted to the one that you

expect to find is that the amortized gas cost per transaction goes down to zero when the number of transaction in a batch grows so we can see nicely I will explain in a moment but we can see nicely did this property preserved in structs really nice what you see here is results from our verifier contract on e theorem it goes from 128 transaction in a batch to more than 8004 8006 in in a batch the cost per trade or per settlement is about 800 guards which is 200 times less than what you would get

if you will settle the trades only theorem directly a trade here just to explain what a trade means so a trade here is 256 patterson - more or less i'm mentioning that because i want to defer it from payments where the payment case is simpler especially because you have just one side pane to the other and not to signed exchange to such exchanging tokens and also you have you could have payment for a single token here you adding with many many tokens so the factor if you want to compare these two payments the factor is between 3 & 4 with a complexity what about the very

thick the total verification cost of the proof so what I what you what you just see is the amortized cost per transaction what you see here is that the total cost to verify the proof on chain was well below the block limit for any size of batch that presented here we have few challenges the first one is the one of data availability now it's a I'm sure that almost everyone who sits in this room they know the data availability is a problem for many layer

2 solutions on a serial the one approach that is possible is to put the data on chain these will solve the data availability program but it also introduced a linear cost on main chain we do have several other ideas that we are testing at the moment to introduce a cheaper construction that provides data availability as well the second challenge is the one of censorship so here there are few approach that we could go we can and we plan the future to add privacy on top of that so if the prover doesn't know what's the in what's the data in the transactions being

proven then he it's hard for him to censorship because he don't know based on what to censor the other way to go with it is to have the data being committed before and then have the prover forced to prove the data that was committed by user previously and of course there is the possibility that you that one goes with not just a single proofer but with a network of prove us and then apply some consensus mechanism on top of that we also plans further reduce both in stark proofer complexity of chain which you already saw that is able to enter 8000 transaction but I'm

sure this number will go even better and reducing the stock verifier cash cost on chain I want to finish with this slide so we now able to verify on chain 8000 trades in a block which is 20 times more than what we presented just six weeks ago in Stanford and this is also 200 times better scale than what the theorem is able to do today and we're just getting started thank you I'll be happy to answer

questions on this any questions hi Tony from brave so the question I have for you is we respect to your prover time did you make some tests on Adams G consumption on energy consumption yes I we will provide more concrete numbers later but those proofs which were all generated on Amazon AWS machines that everyone can access

without GPUs so I also have a question regarding the prover time you've said it's quasi linear but what are the hidden constants that you currently a sudden currently have okay great question so both in both Starks and snarks you have two main parts you have the FFT part which is done depends on Starks it's multiple fifties on size which is smaller than

the size of the circuit multiplied by some factor so there is the FFT part and then there is the linear part with a construct factor that in Starks is a miracle tree and in snark is the multi exponentiation so the FFT part although it's quasi linear in fact it has it has good constants to it especially for us where we are able to choose whatever field we want to work on so we can very well optimized the operations there you can choose a very convenient field and then work on top of it for example you don't have to choose field which is on the of the size of that relate to the

security parameter wicket relate so it it has to be 256 bits we can work with a smaller field and also we could choose fields were some specific operation there are cheaper because we are not bound to any elliptic curve cryptography and to specific curve the other part if you compare the linear part so we have a miracle tree which is linear number of hash operations and in snarks you have multi exponentiations where you can look at it as linear number of multiplication on the curve so there there is like a fact of I don't know exactly but if you compare Blake to multi PK to multiplication elliptic curve I think

there is a factor of 100 there I don't know the exact number of what's there today and snarks but I guess this is it so I hope the answer the question can you give a concrete example of a time like for this example of what would the proof generation time be for 8,000 trades in a block yeah I don't know all the numbers for this graph but I could say that for example the two are 2048 transaction we compute it in less than twenty minutes I think any other questions your rate of speed up is really

impressive how particular are those speed ups to a particular like decentralized exchange protocol or are they more general so we talked I guess that the question was on the gas per transaction over time compared to if the improving time is related to any particular design of a decentralized exchange or if it's generic to anyone okay so the proper time here the statement here so the statement here is relate to a certain number of its most of the work here is to prove chain of

pettersen hashes you could use this construction not just for the centralized exchange but for example for any payment system or to save any state update in general so the numbers here can be easily compared to others if you just remember that the what the leading factor here is the number of Patterson hashes and so for example if I take eight thousand so eight thousand is about two million Patterson Hodge you could compare it to other systems I don't think that other system currently get to these sizes at least the father I know also because if you look on snarks only theorem I think that the maximum

number of that currently can be reached because of the pre-compiled is something like 512 sahaj if I compare if I move to our ones here so it's pretty hard to compare the moment does it answer the question DK's narcs there is a limit on the size of the circuits that you can construct based on the underlying elliptic curve used in the brew system is there such a limit with the stark set up as well so like what is the largest size of a

circuit that you can currently process so that's a very good question I mentioned earlier that both snarks and Starks has FFT in them so they both if you want to compute F of T efficiently you need to have a multiplicative group of some high order of some prime most of it we just used to add amoment but could choose other now we don't have constraints when choosing the field so we don't have to if we want to find such a field we can just go and choose prime that have that feature we don't need to do anything else whether in snarks if you you start oppisite you want to find

a curve that has paired nice pairing properties and then you are looking from all the curves that you found what is the field what is the field that you can build on top of them that you will be most good convenient so in this to answer directly to your questions we could choose a field of any size that we want and we can play with the parameters as long as they give us large enough multiplicative group we could do that yeah sorry no actually here we used we didn't it's not even optimized to field sizes

yet right I think yeah yeah just a curious question about the gas cost because there you have something going from five million to up to thank six right now it's very hard to get these transactions on through main net so actually this is not true I myself ran several tests where I sent large much larger than like larger transaction than those on may net in several times of the day with several costs and they always

get included within less than a minute so in less than a thirty Seconds to be honest it starts getting problematic if you want to fill up every block in tension it's it will be this problem with any number that we presented here so this is why I feel convenient to say it because if you look on those numbers one second sorry if you look on those numbers the number that we put here for etherium are assuming that the blocks are full so if you want to compare apples to apples you have to assume that all blocks are full we are not planning to fulfill all blocks in fact we are going to keep our gas consumption of the entire network probably below five percent so it's not

going to affect the network just there's also a secondary problem of which is like Barry with roll-up talks about a lot is how do you fill up a block optimally right that's a general knapsack problem that you can't really solve and how you pick transactions to include in a block and you don't want to introduce that algorithm solving time in choosing a block because that delays the miners etc etc so it's a pretty complicated topic but it's not necessarily a problem of you know filling up box yeah as you guys have been working on optimizing and you get these speed ups

have you been pinning the security parameters in in your start construction are you still tweaking this as well so those numbers are wood pinned security parameter of 80 so 80 bits of security but we could go to an half to 100 or more depends on our decision and it won't affect much the numbers here wait time for one more question before we head off to coffee thanks for your talk coming back to the graph you had earlier I guess and verification your gas cos is

going to be some of it is going to be pushing the trades to the chain so paying for data and the rest going to be computation for verifying the proof do you have a breakdown on how much is paid on data and how much is paid on computation yeah give more detail explanation now so the number that you see here is the is a double cost to send the proof and to verify it on chain it doesn't include the data now currently we are not putting the data on chain but even if we would we would probably include the data on a separate block because if you already put a data on chain you don't need it to be mentioned together with the proof you could first put the data and then relate to this

data and you prove later for example to a hash of this data most that most of the cost here like the thing something like 80% of the cost that you see is related to sending the proof now I think that the theorem community now understand that actually the most expensive part in the theorem is in fact the storage for the smart contract and not the transmission of the network and so there is a plan to reduce transmission cost when compared to storage operation so that storage operation will be more expensive and

relate to transmission if this will be the case for for example by raising together with the same factor both the block as limit and the storage then what you would get for us because we are paying mainly for transmission and almost nothing for storage you'd get that stark proofs will become even cheaper with time on ethereal all right thank you