SNARK Design, Part II, with Justin Thaler | a16z crypto research talks

Transcript

um all right morning everyone welcome to today's a16z um crypto research seminar uh justin thaler from georgetown is back he's gonna be giving part two of his snarks tutorial we'll see if there's a part three later or not but for now let's let's hear part two thanks tim yes so um i'm going to start today by recapping the first uh talk in case um anyone is joining um for the first time today um and then i will kind of continue or complete the overview of rola projects so last time i sort of described the idea of a roll-up what roll-ups are trying to accomplish but today i'll actually kind of dive

deeper into the details of what specific projects are doing and if there's time i will then tell you a little bit about how these snarks actually work in sort of more detail than i described last time um and that's where we'll see if i might or might not have have time for that um okay so here's the abbreviated recap kind of 90 minutes into four um so let me remind you what is a snark um so the approver claims to know some witness satisfying some property and just as a concrete example this could be you know the the prover and verifier might have agreed on some cryptographic hash function and some output y of that hash function and the prover claim to know a pre-image w

um of that uh hash function output um so the the trivial proof that the prover knows w would be to just send w to the verifier who can just directly check that w satisfies the claim property in this case by evaluating the hash function on w and confirming it spits out y and basically a a snark is is just any way for the prover to prove to the verifier that it knows w um with costs better than that of the trivial proof system so so sync means that the proof is shorter than actually sending w explicitly to the verifier and ideally the proof will be faster to check um than the verifiers runtime in the trivial proof system and in that case we'll call the snark work saving for the verifier in general snarks are

designed in a two-step process so there's a front end and a back end and ideally the front end will take some computer program written in a high-level language which takes as input the witness and sort of checks that the witness satisfies the claimed property and the front-end will transform that computer program into an equivalent representation typically something like a circuit satisfiability instance um because things like circuits are kind of easier for the snark proof machinery to be applied to than you know directly to some high-level computer program um and then the snark for circuit satisfiability um or you know so people are like to use variants of that in practice or generalizations that's called the back end of the system

um so you know last last time i described a like sort of the standard paradigm for designing snarks it's a three-step process um so first you design a protocol called a polynomial iop um and i said last time what that is and if i if i if we get to the part of the talk where this is relevant again today i'll of course remind you um the second step is to design a cryptographic primitive called a polynomial commitment scheme and if you put these two together you get a succinct interactive argument and then you can just pull the interaction out to get a static proof a non-interactive proof by applying something called the fiat mirror transformation okay so um with sort of that background

on snarks out of the way um here's like the one slide that tells you how how a roll-up works so the idea is that sort of without a roll-up um today blockchains are sort of storing the entire state of the world on the l1 so on layer one that means on the blockchain so that means like all of the blockchain nodes kind of have to know like everyone's account balances or something like that um that that's what i mean by the state of the world it's like all the data that lives on the blockchain um and and the rollup seeks to avoid that by storing only a commitment to that data on the l1 a cryptographic commitment um so think of this as just like one cryptographic hash value which

somehow you know is uh binds everyone in the world to the underlying data but the commitment itself is tiny it's just like 256 bits or something like that um and the idea of the rollup is that you know it's going to process a big batch of transactions and figure out what is the new state of the world um you know by applying those trans that batch of transactions to the current state of the world right um and then computer commitment to that new state and post that new that new commitment on the l1 on the blockchain okay and the problem with that is we don't want to just trust that the rollup service does all that computation

correctly so we don't want to just trust that the roll up sort of correctly applied all the transactions to the old state of the world and then correctly computed the you know a commitment to the new state of the world so uh the roll-ups will pair uh the new commitment with a snark proof that the new commitment is correct right so that means like the rollup's going to prove that it knows a bunch of transactions such that you know all the transactions are valid meaning you know they come with a digital signature and you know none of them involve somebody spending more money than they have in their account things like that and the roll-up will prove that you know when you apply those transactions to the old state of the world underlying the old commitment it leads to a new state of the world underlying the new

commitment and i just want to remind everyone um sort of read that i had a discussion last time about how you measure the performance of these roll-ups um and sort of there there are two things you might care about uh latency and throughput um latency is determined by two things so this is this is the delay between one a transaction post to the the roll-up service which we call layer two um and when a proof capturing that transaction posts to l1 um which is when we consider the transaction to be finalized so the two contributors to latency are the time to compute the proof right because we kind of have to wait around for that proof to be there before we can post it to l1 obviously and also we have to wait around for

enough transactions to hit the l2 that the rollup is kind of ready to um treat them as a batch and roll them all up by computing the relevant proof for them and you know the commitment that corresponds to the state following their processing and all of that um so yeah so the main reason you want like lower down on batch size is just so that the amortized cost per transaction is low enough for yes um so exactly so if you have yeah this is all about saving gas on the l1 um of course there are gas costs there um because you know blockchain nodes have to do work for every transaction and store

state for every transaction um so you me you make people pay for that um because otherwise you know people are just going to try to get as much transaction data as they can on the chain and the nodes will all fall over um yeah so this is all about saving gas um that's why you want the batch sizes to be big um and there are sort of i guess you could say there might be economies of scale to bigger batches so it's it's not just that more batches are getting kind of cryptographically compressed into a single commitment and proof but it's also that um you know the the proofs involve um like if if multiple transactions in a

batch refer to the same account um you kind of get multiple reads to the same piece of data so you only the approver is only having to deal with authentication information for that piece of data sort of once doesn't have to pay every time and often um we're going to talk about data availability again in a minute um but uh you know a lot of roll ups are storing um the the data underlying the commitments on chain and you sort of only have to store um sort of the the latest account balance um on chain in principle right so if in a single batch you know like 18 different

transactions hit the same account you can kind of net them all and only pay to store the the final result on chain you don't have to store 18 different values so there are kind of multiple ways that big batches help save the cost of a roll-up i don't know if this is like interesting or not but i noticed that your defined latency is like the moment that you hit l1 you assume that are you are you basically abstracting like that l1 is kind of perfect and instantly final in this case like i wonder if there's interactions between the fact that posting to l1 for some types of blockchains doesn't really guarantee that the thing's finalized is like that

yeah so i mean i guess the simplest um thing is um to wait long enough you know if it's proof of work chain wait for enough more transactions i guess that also applies to proof of stake that is just considered final on on l1 and that's what i mean by post to l1 but there are other subtleties i'm not we we're i'm about to raise when we talk about data availability which is i was seeing that some of these roll-ups have ways to revert state um if bad things happen well okay i don't know details about if the you know they've just they've at

least discussed um the possibility of reverting state um even after proofs might have posted to l1 um so you might have to be very careful about what you consider five finality um if if something like that might happen uh but yeah at sort of the crudest level at least um people sort of consider the the roll up to the transactions be finalized when uh when a proof that kind of incorporates that transaction gets hit cell one whatever whatever that means yeah and basically it's confirmed yeah confirmed on l1 yeah yeah i guess if um if it's possible that l1 might sort of you know drop the block that has the the

proof in it then um there's no sort of global record that um of the proof anymore i guess the question we should come back to later is every role suffer from this problem equally or some like more tolerant of pre-order yeah yeah we should yeah we should discuss and think about that i would it doesn't seem particularly specific to any roll-up design just the whole notion of of a roll-up posting a proof capturing a basic transaction seems to be key but definitely you know their plans to sort of deal with possible attacks um definitely factor into finality and i'll discuss possible attacks

momentarily okay so yeah so people obviously care about um latency um yeah this also means by the way if like you know one of if your transaction that's in a batch is a withdrawal transaction i think you don't actually get your money back on chain um until a proof capturing that withdrawal transaction uh hits the chain so um in that situation even if the roll-up service provider or you know some intermediary um you know you're an end user and there's some service that's using the roll-up provider even if they're willing to kind of grant their users finality before uh the proof hits the chain

um if you're trying to withdraw from the roll-up i think you just cannot actually you know like get those funds um kind of um liquid in your wallet until until that the proof capturing the withdrawal hits hits the chain so yeah you can um as with optimistic roll-ups i think people can kind of step in and potentially uh you know provide liquidity before finality um kind of take on risk if you will um so that end users don't have to but i i don't know yeah but if you're trying to do like a direct withdrawal from a rollup i think this this latency is really going to matter because i think it's usually like two

transactions right because you need a withdrawal transaction within the roll-up and then you like submit your own trend like that comes from the roll-up server and then you submit your own thing to actually move yeah to like pull the funds from like the roll-ups yeah smart contract of the roll up to your wallet yeah i think that's how it works okay so that's latency um and then the other measure of performance is is throughput so this is the number of l2 transactions that can be processed by the roll-up in a given amount of time and we had a fairly lengthy discussion last time about how due to something called pipelining this actually has nothing to do with latency

um in principle um so maybe i'll summarize that in a sentence here just um as a reminder or for for those who might who weren't here last time so the idea is like imagine it takes a a year to compute a proof okay but the proofs are really small so once you have a proof in hand you can get it on l1 really quickly and sort of in in steady state you can do this thing where you're actually getting um a proof onto l1 um like if it only takes a minute to upload a proof to l1 once the proof is in hand you can actually get a proof one to l1 once per minute in steady state it's just those proofs are kind of capturing year old data so you think of like as soon as you have a batch of transactions

kind of ready to be proved you hand it off to the approver you kind of think of putting it in a pipeline that takes a year to get through the pipeline right but after that initial like year is done then like every minute you're kind of throwing a new batch of transactions off to the prover and a proof is coming out the other end of the pipeline and you can throw that proof up onto l1 and this just happens every minute new batch goes to the approver a new proof comes out of the pipeline you throw it up on l1 so in principle this has nothing to do with latency but of course in practice people won't tolerate like one year latency so yeah like to maximize throughput you kind of want your batch size to just be as big as it can possibly be because

that's gets the most kind of savings or compression of the transactions um since these snarks have succinct proofs that uh grow sublim sublinearly with you know the statement being proved but there's there's limits uh put in place by latency demands but also some of these snarks like the approvers will just kind of fall over when the statements get too big so there's lots of things that sort of can limit um uh throughput in practice um but yeah i sort of flagged this last time because a lot of the the roll-up projects will discuss performance in terms of throughput like transactions per second and um if you if you sort of don't know that that's what they're talking about

latency you might think like transactions per second is referring to like uh the speed of the approver you know like kind of the the end-to-end pipeline which would be really latency and that's not what they're talking about um and that makes sense because throughput is ultimately what determines blockchain scalability in terms of just like how many transactions the blockchain as a whole can process in a given amount of time um but it's just yeah you have to know what people are talking about um if you don't have the context it can be very confusing um okay so i guess i will mention this is the last thing i talked about last time a bunch of rollups today are doing recursive proof aggregation um or composition

um and this uh i guess covering this also clarifies the pipelining thing so the idea is um they want to sort of work on on smaller blocks than they otherwise would um and uh but they can work on the small blocks in parallel um so the idea is you process like a small block compute the new commitment and send um the batch the little small batch off to the prover to start chewing on the proof but as soon as you know this commitment you can kind of start processing the next small block um and and send the next um that that small block off to the approver to compute the next proof and you you can do that before the first proof is finished so you can

sort of do everything in parallel and then you're this is effectively reducing your batch size so now you have one proof for each small batch but you don't want to post all of those proofs to l1 because your gas cost savings will be poor so what you'll do is you'll sort of recursively apply the snark to aggregate all of these proofs into one small proof the idea is you'll use the snark for the prover to prove that it knows the proofs pi 1 pi 2 up to pi t that would have caused each of which would have caused the verifier to accept okay so you need to take the snark verifier um for the small batches like

represented as a circuit or something um you know t times once for each batch and then the prover gets applied to that circuit to prove that it knows these t proofs that would have convinced the verifier to accept okay does that make sense so the witness of the top level yeah and it's the pie eyes and and i guess also the ci is because the the on-chain verifier for you know the non-community if you were posting these on chains also needs to know the commitment to verify the proof and then at the bottom level um it's sort of

so subblock two you're kind of the point is to verify the computation assuming some given initial state at the beginning of sub and then that the correctness of that will be verified in the first of the sub blocks right um exactly exactly so um this proof is ultimately going to refer to this commitment um because if you if you imagined you weren't doing this recursion you were just posting these proofs online like the orange chain verifier would have needed to know this commitment to check like the statement being proved involves this commitment so that's why you you do have to know c1 before you can start um you know dealing with sub block two or

at least proving subblock two um working on computing pi two um and the reason to do this is um kind of twofold so so the provers in in like most marks can be parallelized but it can be a bit hairy because many of them require the prover to do a giant fft and that can be paralyzed but there are certain limitations on it um so this is unlocking more and sort of uh trivial parallelism because like almost trivially like as soon as you know c1 you can just start in parallel working on computing c2 and pi 2.

um and the other thing is i had mentioned when these when these snarks get applied to really really big statements the prover can often just fall over some of them are very space intensive for the approver so this is ensuring that some of the nastiness um uh of the prover like you don't want run into um because it's uh it's only getting applied to smaller statements um but then you're you're still getting sort of the gas savings as if it was applied to a big statement since you're aggregating the proofs rather than posting each proof on onto l1 okay um so i wanted to review that because um many so so like like zk sync one of the royal

projects has been doing this for a long time um actually as i mentioned last time it's it's uh they originally were doing it because they were working with a structured reference string that was too small to handle very big statements but then other roll ups that use different snarks are just now sort of launching this kind of recursively composed situation so i will be discussing some of that later and then yeah the last thing i wanted to discuss before kind of going to new material is um data availability um so because on um on the l1 we might only be storing commitments to the underlying data that used to live on the blockchain

um you have this issue of well where is the that data going to live now that used to you know the data underlying the commitment and the reason uh we needed to live somewhere and be made available to people is i guess twofold so one is like the roll-up provider might just disappear one day or be compromised and someone else might want to step in and take over um or if someone might be like getting censored like the roll-up provider is refusing to include their transactions in the in the batches and then they have to like force withdrawal of their funds and i think you can't do that if you don't know um the state underlying um the the commitment um so yeah it is important to uh have the data

be available and if it's not just living on chain then how is it going to be available and sort of there are two different approaches um out there uh one is to kind of store it on chain anyway but it can sort of be semi-unchained in a much cheaper way so in ethereum there's something called call data and that's where um the you know this data that sort of used to be like uh subject to the kind of full consensus mechanism of ethereum and stored by like all the nodes um now can live in in sort of this cheaper call data that's not stored by by all of the the nodes verifying the blockchain um and then uh there are approaches that will kind of keep the the data off the l1 um and use economic incentives to try to get other parties to make it

available um so i wanted to just have a slightly longer discussion about data availability um yeah sure so um you're thinking about your examples about why you want this call data i mean i think fundamentally what you need is just uh the ability to reconstruct the full state of the virtual machine right one way you can do that is re-execution of all the transactions right so i would say like you know having a list of all transactions is sort of sufficient for state reconstruction it's not obvious it's necessary right there's other way you can communicate it right is that right is it right that we only care about the transactions in as much as we care about state reconstruction that's correct yeah so um i mean

basically like to to withdraw your funds um from like um assuming that the roll-up has provided like a fourth force withdrawal mechanism which i think they're all doing otherwise people would maybe wouldn't use them because they'd be worried their funds would get censored and then they can't get them out um i think what you would need to know is like your own account balance which maybe you can just track yourself but then you also need to know the authentication information to prove that it's consistent with the latest commitment that's on chain and that sort of involves like aggregated information potentially from all account balances in the whole world so you definitely don't need to know like the whole list of transactions that led to the latest state of the world but

you do need to know if not the full state of the world like enough to get that authentication information which in general in the worst case cases like the full state of the world basically yeah yeah so these proofs that are getting stored on chain um they well so there's the commitment and then there's a proof that the commitment like was computed by applying valid transactions to the state of the world underneath the old commitment um so so this this data that i'm talking about making avail available sort of has has nothing to do with the proof so it gives a commitment to the new

state and they send you a way to update the state that's supposed to state is stored on chain can you update it with the commitment and prove that yeah so this is going to get into so let me jump to the discussion when you say you do you mean like you're not the roll-up provider but you're someone who knows the state of the world can you now like update can you function as a role provider so that is the perfect segue to this little conversation i wanted to have which is should entities other than the roll-up service be able to submit proofs to advance the state of the system okay um does anyone have any thoughts on that so joe's giving a thumbs down do you know the old state and the

commitment no what if the roller provider themselves update the proof that we every time they added you you update the state every time they add a new one like on chain yeah so the commitment to it and then they can also change the state and then prove that it is consistent with different yeah so that's basically what they're doing now um if they are keeping um the state of the world on chain and call data that is what they're doing so with every time they um update the commitment they also include you know they have a bunch of call data that they include too and they pay the gas feeds to get that stored you know in the on-chain call data people call this like semi-on-chain i don't know because only full nodes are

storing it or something um so that's what they are doing now but there's more and more services that either have or are soon planning to roll out off-chain data storage and then they might no longer do that yeah i mean if you just like trust the roll-up service in every way you can um you can obviously just trust them to solve data availability themselves but the whole point of being worried about data being available is you know what if the roll-up service gets compromised what if they're trying to censor you um and you have to force withdrawal from them um yeah but if the other cases the service goes offline

or something yeah yeah but then the final state is on the actual blockchain right if a commitment to the stage on the blockchain and if you're if they're using like the sort of call data based data availability solution then also the underlying data is on chain and at least living in the full nodes or whatever um but again you know there's this big push um to not do that because so the the bene the gas savings of roll-ups is sort of bounded and what what i read is bounded by about 100 x or so um if you're sort of going this call data route um and maybe some of the upcoming eips if they get approved sharding making

call data expire after a year things like that maybe that i don't know if that moves the 100x up a little bit but uh when people people will talk about you know like 20 000 x improvements and i think you really need data off chain if you hope to do that um even even with if they incorporate all the eips that are being proposed um and again that refers to throughput um okay so does that joe did you want to well i the philosophically correct answer is that anyone should be able to submit a

proof um it's like the proof is self-validating but it seems like it opens things up to a lot more potential attacks and yeah risks so it's not like it's not obvious that it's actually the right trademark yeah so um i think uh i don't think there is a right answer but i guess just to clarify i guess if you if you did want only the roll-up service to be able to submit proofs you could do it just by requiring them to sign the proofs right the smart contract says i look for a digital signature of the corresponding to the roll-up services public key or something um so if if the answer is that um only the roll-up server should be able to post proofs i guess the concerns then are

like centralization and censorship right like the government maybe someone could go to the roll-up service and say do not process transactions from this public key their evil their an evil party don't do it um and then i guess that party should hopefully be able to force a withdrawal but they can't um use the service anyway and so if the world is run by a handful of roll-up services um you know maybe i don't know maybe that party has to pay crazy gas fees that only providers that have taken over the world can pay or you know because they can't use a roll-up service who knows so i guess those are the concerns um you know how how can you say that the blockchain is decentralized if uh you know the roll-up services

are centralized and are running the world i mean there's also like a there's kind of a disaster scenario if you make them sign every update that they lose that key yeah no progress again forever but you could probably hedge against that by saying like if the if the roll-up server doesn't submit an update for xbox then like all of a sudden yeah yeah there seems a really big design space here um so but if if the answer is is yes and anyone can submit a proof or if the service gets compromised i did want to discuss the following data availability attack because actually this hadn't occurred to me until i was making the slides for today um so

i i guess these things are nice to raise and and and then i found discussion online the roll-up services are thinking about exactly this kind of attack and what to do um so uh a party whether the person who sort of now has taken over the roll-up service or you know the person anyone out there who's allowed to function as the approver um can honestly generate a proof that processes some legitimate transactions but then they just don't tell anyone in the world what the transactions are or they put out fake transactions that don't actually like correspond to the proof if you're not careful and aren't not checking for that they could try that um and the point now is that you know the the system has been sort of updated on chain

um like there's a commitment now to an updated state of the world but no one but the attacker knows the new state of the world so like the whole roll-up is bricks no one else can advance the state of the world um because to do so you know you have to you know know a bunch of authentication information and you know even like a single transaction is going to affect uh authentication information for the whole state of the like any any piece of data um yeah does that make sense it seems like there's a lot of different get ripped it would be ways as far as i know it never happened it'll be interesting to see in the next like year or something if the first role observer actually like somehow manages

to get itself stuck yeah yeah on the slide there's right and obviously i'm just uh raising this as something that everyone has to think about and i'm sure the services are um i'm gonna tell you a solution um to prevent this attack even if anyone in the world can update the proof um but this is not necessarily the solution that the services are are using it i i actually don't know in detail what they're doing um so so here it is um so if the data is being stored on chain the state of the world is in this call data you can demand that the verifier so like the smart contract that runs the snark verifier um demands all state changes as

call data so it will take as part of its input like the the latest uh state of the world written to the call data okay and it will then have to sort of um uh treat treat that as what's called public input to like the the circuit that it's applying a snark to um right because uh you know as i described how rollups work previously uh you know the approver is going to prove that it like knows a bunch of transactions and you know the the new state of the world that kind of follows by processing those transactions you know applying them to the old state of the world

um and then show that like the new state of the world kind of underlies the the new commitment that it's posting to the chain um and in that situation the new state of the world is part of the witness that is never that the prover knows but is never revealed to the verifier so what i'm saying is you have to get that part of the witness out of the witness and directly into the verifiers hands so you could think of it as still part of the witness but it's like getting sent explicitly to the verifier but it has to come directly from from the orange chain storage now right because the verifier is trying to basically trying to confirm that like the new state of the world is actually one chain so it's available to everyone um and so done naively this is extremely

expensive um because the way that many of these snarks work um any public input like that's fed to the snark verifier like each little piece of data that's part of that public input you have to do cryptographic operations the verifier has to do cryptographic operations so this is like substantially increasing the size of the public input to the snark verifier causing the snark verifier to do a whole bunch of crypto operations therefore greatly increasing the gas costs of running like the roll-up verifier on chain but there's fortunately a technical trick you can do to alleviate this called the hash trick so this is cryptography's hash trick not like machine learning's hash trick so what

you do is um rather than um having the whole call data be public input to the verifier public input means like both the verifier and the approver know it um you only make a hash of of the of the call data available to the verifier and the verifier is just going to check directly and this is really important outside of the snark proving machinery that this this claimed hash actually is the hash of some call data so outside of the proof machinery the verifier is going to take a bunch of call data compute its hash you know like sha 3 of call data and confirm it equals like this public input being fed to the snark verifier right i'm distinguishing here between

like the smart contract verifier and the snark verifier um which is probably confusing but basically um the snark verifier is um has to do a whole bunch of crypto operations for any any any public input that's kind of getting fed through the proof machinery and here we're making sure that only only the hash is getting fed through the proof machinery whereas the smart contract that is doing the roll-up verification is sort of free to also do other checks that don't involve the snark at all okay so it looks like this is not coming across totally well but maybe the some you know a a hint of of um what's going on here is is coming across

yeah just to make sure i understand the only advantage of this over like why do we even need roll ups is because you store these things semi-unchained if it was not called data but just on chain then there's no advantage to roll up here right why do you do all the roll-ups to save putting it on chains so now you're doing it so so that's um i think there'd still be an advantage though because you don't have to put all the signatures on chain right you just need to know like a also like the what needs to be available on chain at

any time is kind of the latest state of the world you don't need to know the whole history of transactions that led to that so i don't know that people are doing this now but you could sort of forget transactions on chain and just at all times only have the node storing like kind of the latest state of the world i i i'm not saying that this is an easy thing to engineer that anyone's doing this i'm just saying in principle wait but this in this solution you need all state changes stored in the code you in the call data what you need is the current state of the current data underlying the current commitment um so you could you could forget everything else um and i don't judge you want to

say hold on i mean you don't you can't represent that as like the full state of the world and call data in each block right that would be like way too big it's only the changes right yeah yeah well so okay so well i guess what if i'm understanding what you're saying correctly um you're saying that um what what something that people actually i guess do do now is they're storing um only sort of deltas like differences between each state update um and uh so so they are remembering kind of the whole history then um in a sense but like any kind of they can net out multiple transactions within each each

batch within each state update right so if like in a single batch there's a thousand transactions that all you know um 500 of them increased an account balance 500 of them decrease in account balance they can also be net out and you don't need to know the individual ones which is i guess related to what i was saying um basically if you put every trend like effectively you have to put every transaction like a summary of every transaction in the call data but you save on i guess netting because you can net transactions and then you save on all the witnesses like the transaction witnesses signatures which don't have to go on a chain much usually the signature is bigger

than the effect of the transaction and you're also saving like the time of all of the blockchain nodes verifying every signature so it's your you get to both you know cut out the storage of the signatures and the time to check that they're correct their abilities something like that okay yeah so that's the savings if you're keeping stuff on on semi on chain um but with off-chain storage which is like really where the giant gas savings will come in if people sort of are comfortable with this here's something else you could do so you could have some like just other distributed systems using um you know bft

techniques to achieve consensus or something and that other system can like threshold sign the hash value um that's supposed to be the hash of the new state of the world um basically attesting that you know the that they are storing um this the state of the world so the idea is like if enough people have said okay i'm going to try to make this data available your you know the l1 is going to say okay well you know i guess i'm convinced that this data is going to be made available because enough of you have said that you downloaded it that you know someone someone should be making it available um

so this is basically reducing kind it's a reduction from the liveness of the roll-up from like date availability for the roll-up to sort of liveness of the bft system you know that has now sort of attested with some kind of majority or two-thirds or something that that bft system is going to make this data available so it's just kind of placing the trust in the in the bft system instead of um you know in the in the costlier solution that was keeping the data sort of semi-unchained um and and i just as a reminder like um the the nice thing about cryptographic commitments is that nobody can like fuss with the data and change it so like you only need really one party to be able to

broadcast to the world what the what the data is that they're supposed to be making available they don't need to um there's no way that someone can maliciously like change that data because they wouldn't be able to authenticate it uh with respect to the commitment that is stored um on l1 yeah to say like i don't think you need a bft system for this i think it's much simpler because you only need one party to keep the data and they don't really need to reach consensus because if you believe like the l1 achieves eft for achieving consensus then they can all just check that they're scoring they can check if yeah so i guess the the concern would be

um that it'd be expensive if you know you got a million people saying i have the data i have the data i have the data and you sort of have to figure out which one is telling the truth like you can check but you have to potentially you know check a whole bunch of people if there's malicious parties out there and that's just expensive i guess you don't you don't think that's something people are concerned about um [Music] i mean i guess you could sort of do it through some like smart contract where people claim to have the data and don't then they yeah they yeah yeah i don't know yeah it seems though like you could have some simpler like kind of just

uh like you have x nodes and they all say they have the data and as long as it's honest then you're kind of okay right yeah so um at any rate like yeah basically if enough people say they're going to make the data available you only have to trust one of them so it's probably fine and you know basically if 50 people said make it available one one of them is going to i guess the eft wouldn't actually even help with the attack that you're talking about because if you have a vft system you can still have like malicious nodes that will lie about having the real data so you still have to check right like anybody who gives you the data you still have to check yeah i guess yeah i don't know how big the threshold here

would be for the threshold signature like if it's above a majority then you could just like yeah anyway um this is uh i just mostly wanted people to think about this data availability problem in more detail because i was just thinking about it almost for the first time as i was preparing this talk and realizing the subtleties and thought it was a useful conversation to have so i did it online in the talk um but yeah thanks so much joe for keeping me from saying anything to too dumb any any questions at this point i mean um i know what some of the

projects are planning um you know you have um like zk sync is planning something called zk porter they're gonna i believe they're launching a token and using basically proof of stake to try to incentivize people to make data available and also sort of be honest about it so people don't waste their time i guess checking it and it turns out not to be correct um it sounds like a second option potentially and it's just you just have this nice property that no one can with the data but you know there is i guess potentially a cost if people do want to try there's a cost to sort of root them out i guess i think starkware is already keeping

data off chain but i don't i don't know exactly how they are um dealing with these issues i don't know the details um there's a so yeah there's a large design space i mean people have plans at a minimum um if they haven't launched um and i guess it remains to be seen how some of these play out i suppose um yeah it can be hard to follow like where some of these projects are with their plans and you know they they've been openly discussing their plans for a while and so you find an old post and it's hard to figure out like well has it been implemented yet or not um yeah it's just um it's it's there's a lot of activity in the space it's hard it's hard to track

um you know what what was you know um plan you know very open discussions about plans and what's actually been been done um okay so i guess i'll we'll dive into um like what the roll-up projects are actually doing especially in terms of their snarks because that's what i'm an expert on um and there won't be too much discussion about data availability anymore okay so remember snarks kind of work in a two-step process you've got this front end and that sort of um spits out some kind of circuit satisfiability instance and then you apply a snark for circuit satisfiability instance so let me start with front ends okay so there are sort of two extremes

that are very prominent at least they're maybe not the only approaches but they're certainly i think the the most prominent ones being pursued so one extreme is kind of inhabited by starkware which has exposed a high-ish level language um one bullet point later called a limited assembly like language so it's it's it's higher than just writing down a circuit for sure but it's still a you know somewhat low-level language it's not like java or something anyway so a high-level language called cairo to programmers and they have an automatic you know compiler that turns cairo programs into circuits um so the language so the programmer has to be aware of

many snark specific issues and there are limitations to it um so for example like all arithmetic in cairo has done modulo or large prime and greater than unless that like integer inequality tests are not supported um and i believe the programmer has to actually so you know like leverage what's called non-deterministic advice which is kind of taking advantage of the ability that you're dealing with a circuit satisfiability instance and not a circuit evaluation instance so there are sort of ways to keep the circuit small by sort of adding extra elements to the witness called advice and i believe the programmer in cairo sort of has to explicitly

program that advice in many cases um i think i think that's true just looking through um their high level descriptions of cairo without actually using it myself yeah so the idea here is um you're sort of you're sort of pushing more responsibility to the programmers and giving them like limited expressivity um like i guess i guess you know programmers today write smart contracts in solidity and for a programmer ideal programmer experience you'd like them to not have to change that so that's the other extreme is just let programmers write in solidity um and there are a whole bunch of projects seeking to do this

and they sort of all use the term zk evm but means slightly different things by this and ultimately the the circuits that they're planning to use might differ i think some of them are okay so last time i mentioned so i'll say this again i believe the way uh ethereum smart contracts work is they're typically written in solidity and then they're compiled into what's called evm bytecode that's ethereum virtual machine um and then the smart contracts actually execute that byte code so i believe some of these projects are like literally kind of taking each bytecode instruction and coming up with an optimized sort of circuit that implements that bytecode instruction and so they're working sort

of directly with representing the byte code and others are kind of transpiling solidity into like other um lower level languages and then sort of turning those other so that they're not going through evm by code and then turning um those other lower level languages into circuits so just different sort of engineering approaches to go from solidity into the circuits that are equivalent to the solidity program um and as far as i know um these pro so i've heard the starcraft team like publicly you know like podcasts say like one reason they chose their approach was basically faster development time like they could like this just takes a a time a ton a ton of engineering to make this

reasonable um so they they went with like the kind of easier compilation problem where the language is sort of designed so that all programs in it are snark friendly and amenable to like kind of standard off-the-shelf techniques um so i believe as far as i can as i understand the zke evm projects have not yet launched full front and back ends on test net so like i think zk sync they launched a test net um back in february i i believe that it's generating and executing circuits but not generating the proofs for the circuits yet um in contrast so zk sync 1.0 which i'll talk more about in a bit only supports you know like token

transfers and nfts um so much more limited functionality than like general smart contracts but that has been live on mainnet um for a couple years already so zk sync 2.0 is what's going to um have this you know very exciting support for solidity where you know no one will have to know anything about snarks to use it um but it's just a it's a very difficult engineering problem um okay any questions about that yeah um does your crew know the like front-end circuit when they like tracking approved yeah they need to know the circuit like the verifier yeah so great question um the verifier needs to know the circuit too um because

it if it doesn't know the circuit like it doesn't know like what the approver is actually proving the statement about and i'll say more about this shortly um okay so uh something i want to point out is that there might be a tension here between achieving like performance of these roller projects and and security in the sense that um especially with uh like the zkevm projects because it's just a very difficult problem to turn like general solidity programs into circuits like solidity was not designed with like snark proving machinery in mind at all um so what many of them are doing is they're sort of using very intricate hand-coded gadgets which just really means like

optimize circuits for common subroutines or instructions okay so just just as an example to give you a sense of this zk sync 1.0 in the zk sync repo so this is like not even dealing with zkevm this is just like nfts and transfers and swaps they have like 5 000 lines of bellman in the zk sync repo so bellman is like a language is you're almost like hand coding a circuit like just writing down gate by gate the circuit almost was originally designed for zcash i think and now the whole community uses it um but then even outside the zk sync repo they have something called the franklin crypto gadget library and you know that has well over 5000 more lines of um of bellman in it

and something that's particularly complicated just for them is i think i mentioned that they're doing this composition of snarks and it's kind of nasty to represent a snark verifier as a circuit um exactly how you what complications come up depends on what snark you're using because the verification machinery is different um so they wound up with an annoying situation where ethereum today supports just one pairing friendly curve people have different names for it but bn256 is one of the names um and for technical reasons um this curve is like not friendly to recursion to like representing the snark verifier as a circuit so they wind up having to implement like really really really big

integer arithmetic in a finite field in a circuit and so one of their you know big um and so like achieving this when they did in 2020 um is like a huge engineering accomplishment uh but it's like it's complicated to make that um efficient like the circuit's really reasonably small so that's like five or seven thousand lines of bellman code like just in one repo to handle big integer arithmetic so just to be clear um you know i mean this is these efforts are some of the most innovative you know important engineering efforts in the space but um you know the the tagline of zk sync is rely on math not validators this is um sort of to differentiate from optimistic

roll-ups where you're hoping that like people will raise an alarm if they detect any fraud that's they call those validators but just to be clear like the math might include like 15 000 lines of hand-coded circuits and so you know if there is some bug in there you know the approver winds up proving a statement about a circuit that doesn't actually is not actually equivalent to the statements that you know we really want to be proven and you know maybe that um is a security vulnerability maybe it's just a bug um but you know people should be aware of that so i think um formal verification uh of of these circuits uh is an important direction like sort of in the long run um it's just uh you know that

such intricate hand coded circuits you know uh auditing you know we're going to audit that as as best we can obviously but um be it'd be much nicer to have some kind of automated formal guarantee of equivalence or something like that but it seems like a challenging verification problem now the i guess the the main project maybe that's not doing this sort of complicated hand coded circuit specifications is is this cairo compiler but that's also pushing more responsibility onto programmers so you know it's not clear that that's less bug prone it's just the bugs might be coming from the the programmers who aren't necessarily expert on snarks or something like that um

and so i do want to mention so there's there was a nice paper i i learned about recently um so their transformation from from cairo programs to circuits they formally verified it with some proof assistant you know but of course they haven't um i shouldn't say of course at least right now i don't believe there's machinery for the programmer to confirm that the cairo program they wrote matches what they intended it to to mean uh yeah so kind of might be a pick your poison situation uh just to be aware of okay one the last thing i want to say about front ends um so cairo picked a i was uh an interesting approach to generate their circuit i was

surprised to learn this actually recently um so they generate a universal circuit with a von neumann architecture so that means it actually takes as public input the cairo program to be run and like the circuit itself kind of compiles and runs the program on the witness so i think this was gets to your question um you know you don't want to have a so that the smart contract snark verifier needs to know the circuit that you're dealing with this is one way to deal with that and to have just one smart contract that supports all all circuits is to just have a universal circuit like this um but this is sort of well known to this approach to generally lead to

big big circuits and so it's analogous to like a cpu architecture in particular von neumann one that's kind of compiling the program as part of the computation versus an asic and asic is like an application specific circuit and there's sort of two main sources of overhead here one is the circuit winds up repeating like the entire transition function of a cpu for every step of the program and so it's like you know at each step of the program like only one of the possible cpu instructions gets executed but the whole transition function sort of has to have logic it doesn't know in advance what that instruction is going to be has to have logic kind of implementing all of them

and that's another reason i think um they probably tried to keep the the cairo language as limited as possible to keep that transition function as simple as possible so hopefully i'm giving some sense of what this means like and and asic if you somehow know in advance or something what what instruction is going to get executed at time step 50 you can just sort of have logic for that um instruction there but um if you're taking if you have a vibe in architecture you don't you don't know that because you have to be able to handle any any program um so the other issue is potentially like the program kind of has to get compiled inside the circuit so i you know i found the blog post starcraft was saying that um

you know basically the the second source of overhead is not not so big and my guess is that's probably because their programs they might be fairly simple but at a minimum they're probably applying them on a very large batch of transactions so like the work to compile the program might be minimal compared to the you know much longer work to sort of run the program on many many transactions but um it's that sort of doesn't address overhead one um because the circuits that they use they use something called they call it a or algebraic and media representation kind of have a cpu formalism built in right so whether they're sort of taking an asic approach or an advertise a cert a program specific approach or not they

still have the cpu formalism there um so yeah um i don't i you know i i can't say you know like oh i took a cairo program and i sort of implemented it with a totally different intermediate representation that takes an asic approach and you know like this was the difference in size but it's sort of well well known that um there are overheads to this particular approach in terms of the size of the circuits that come out i do want to mention that the cost of large circuits in these snarks is mostly borne by the approver right because verification you know tends to the cost grow very very slowly with circuit size um so as far as like gas costs this isn't such a concern

as far as latency improver cost maybe it is um anyway so this is this is just my general impression of the approach um and there there are other ways to achieve kind of one smart contract for all programs like the asic approaches is still consistent with you know not having a different smart contract to verify you know every different um you know uh smart contractor program people want to want to write um it's just uh there are various ways to kind of pre-process the circuit so that the verifier kind of just has to deal with what comes out of the pre-processing so the pre-processing might be fairly expensive

but it doesn't have to happen like on-chain uh essentially um yeah so that's i wanted yeah that's what i want to say about front ends and how people are taking quite different approaches to the to the problems i don't uh it's probably something that could be figured out although so every every instruction in the cairo language has to be converted to a circuit form yeah yeah but um i mean you know there's nothing specific to cairo about that like snarks just need circuits and i'm using circuit in a broad sense you know like um that starcraft itself might

think of this algebraic intermediate representation as like not a circuit but it you know um conceptually it is just a certain kind of um you know uh low level representation that's amenable to designing a snark for um but the specific way they're going about it is you know in in designing the programming language called cairo it effectively involves programming a very simple processor and they are taking that processor and representing it kind of as a something like an arithmetic circuit that operates over a finite field and then if if someone wants to run a cairo program for a million steps they're sort

of repeating that processor uh sorry that circuit implementation of the processor like a million times so that makes sense so it depends on the size of the program yeah yeah so you would say um here so the the circuit they finally generate is like here's the cairo program i guess as public input they roll down as one for each step i know i think um this might be more in the details for me to say definitively but no i think it's like literally like maybe like here's the the text of the program maybe transpiled in some way um and you know also you know uh the number of steps it needs

to be run for or something um and then there's going to be a bunch of advice inputs basically um plus the the non the witness itself that's um and then the circuit will basically you know using the advice help confirm that so the advice might actually be like a transcript like a step-by-step record of running the program for a million steps on the witness and the the circuit just checks that like at each step of this transcript like the transition function or the circuit representation of the transition function of the cairo program was like correctly applied that makes sense yeah yeah i mean and what yeah

exactly when ibc was so ivc is a certain kind of proof system that supports like applying some kind of simple function to an input and you know proving you did it correctly and then updating the proof to capture like another application of that function and then updating the proof to capture another it's just the function is the process yeah yeah but they're not going through ivc they're representing the function the many many many applications of the function as a big circuit and hitting the whole circuit with a monolithic snark until they start recursively composing snarks as i sort of had the little two level tree before and which starts to get closer and closer to ivc when you do recursive composition snarks [Music]

other things the second thing you said about pre-processing yeah uh yeah but so pl so zk sync uses planck and planck has um holography fancy term for this pre-processing baked into it so you know at least at a high level um that's that's what they're doing um so basically and it's it's easy especially for zk sync 1.0 i think because uh you know there's basically only you know like six programs that might be run and each is just like swap you know um nft or something um but like yeah for each of those there's a circuit the circuit is maybe hand coded and very complicated but it sort of gets

summarized so what what happens is um what this really means is there's certain polynomials that capture the wiring of the circuit that's used inside the snark and if i give a third talk you'll see them um and so uh you basically um the preprocessing winds up uh producing cryptographic sort of commitments to those polynomials so the verifier only needs to know the commitment to the polynomial you know so the these polynomials like encode the circuit wiring so the verifier only needs to know sort of commitments to the circuit instead of like a full description of the circuit which would be very complicated and um large potentially does that make sense and in that way you can write sort of one verifier that sort of takes as it has to be like a trusted input um the

commitment to the circuit um and then what you know operate does the same exact thing it's just um the yeah the circuit is kind of getting into the verification through the commitment to the circuit instead of a full description of it okay let's see a time 20 minutes so yeah this guy i'll get through um basically the roll ups and then you still won't know how snarks work in any detail and then tim lets me i can tell you some more detail next time okay so that's front end so let's talk about back ends and this is this is really what i know more about to be on but you know they're both really important for end-to-end costs so i need i need to talk about front ends um so just a very brief summary a high level of what various projects are doing

so stockwear's back end uses the fry polynomial commitment scheme combined with you know some constant round polynomial iop which i won't get into the details of at all and um so fry if you remember from last time it's the polynomial commitment scheme that's with the shortest proofs among plausibly post-quantum polynomial commitment schemes and the proof length is like log squared of the size of the polynomial being committed like times the security parameter so they're still big ish that you know we uh we could hope to do bet you know better in the future maybe um certainly compared to kcg polynomial commitments which is used

in planck and they're not post quantum and they require trusted setup so that's what zika sync is using is just plonk so that that is a constant round polynomial iop combined with um kcg polynomial commitments instead of fry it's a different polynomial iop underlying it too there's a project called polygon zero which is using plot but they want post quantum security and they also like fry for other technical reasons i think so they're just kind of swap out kzg with fry um so z cash is now swapped out on kcg with bulletproofs um none of the rollups will do that because bulletproof verifier is not work saving so the the proofs are short but the verifier has a long runtime so you

wouldn't want that to happen on chain so i thought i'd mention that as like an alternative but that's not nice designs choice for roll-ups um and kind of as i'll say a little more about soon um you know i think that the prover computation um in these snarks is going to increasingly be a problem i might i would speculate that for these zkevm projects just the circuits that come out might you know even after all the engineering be pretty big and it'll just you know the prover work to prove those circuits will just be um challenging uh this pure speculation but it's just you know compiling solidity into into circus just seems like a

challenging problem so i know several projects are focusing on hardware acceleration for the prover like i guess designing asics like the actual hardware asics to for for common operations done by these approvers um okay so now i'll get into some more details of like the performance of some of these projects um so i'll like my main example is going to be um starkware so they have um kind of two products if you will called starknet and starkx i'll say more in a second about them my goal is just to give a sense of like the current latency the current gas savings the current throughput um and the current security features of of the snarks you know that the that the most prominent projects are using now um so just some background on like what

are stark net and star decks so stark net is a public smart contract l2 so i guess you can write i think like smart contracts via cairo like arbitrary cairo programs and they can like interact with like any other smart contract deployed on starknet i think um and you know then they're posting you know validity proofs of batches of starknet transactions to ethereum um i think it's a pretty recent launch um it appears that there is only several hundred thousand dollars of total value locked in stark net right now um stark x in contrast is is permissioned and application specific and there's there's much more it's been running much longer there's much more

value sort of locked up in it right now um the main i guess client if you is dydx which is the centralized exchange although apparently there's leaving ethereum soon so i guess that will a stark rarest ethereum roll up so that'll change but anyway so they uh the main uh so so for what i'm gonna describe actually you can forget the uidx so there are several other starkx users um and that there turn out to be most relevant for the performance results i'm going to share with you and that's because um starkware actually has starknet sharing approver with these starkx applications um

and they call the shared trooper sharp shared prover um and the provers closed source but the verifier you know runs as a smart contract on ethereum so you can see the verifier it's the same software implementation it's the same actual like server that's running it is it are they actually all one big proof together yeah so as far as i know they are in one big proof together and the reason they can do this well the way it's architected so they can do this is because everything has to go through a cairo program and because um it's a universal they generate a universal circuit that can handle any cairo program they can just have i guess like one big circuit that i guess takes as input now like i

don't know four five different programs you know well i guess four programs and then the cairo programs for each of the i guess the start net um contracts that are being have transactions in there in the batch and then the whole batch is is proved at once and i i think the reason they're doing this now is just to get the volume up enough to get gas savings basically so you know there's there's just not that much volume on on starknet now so it might not be enough to actually get major gas savings but if they sort of uh combine batches with the higher

volume um starkx clients then you get enough to actually get get gas savings basically does that make sense um so yeah they um i you know when i i wasn't aware of the shared prover when i sort of started trying to figure out some performance numbers so i thought i would just be able like there was just a single starknight prover and you know starknet has a has a nice block explorer so i thought i'd be able to sort of just see everything going into the roll-up and just have sort of unequivocal um information on performance but because of the shared prover and you know the um

starkx is is not some like public blockchain the way starknet is um i i did email um the the starkware folks and they were very helpful in helping me understand the performance so um yeah here are my findings as far as latency goes so proofs appear to be taking eight hours to generate uh i don't know this for sure but uh so the the minimum delay between a transaction hitting starknet and any proof getting verified on l1 is definitely eight hours or more so and it can go up to like 16ish hours so what seems to be happening is they're collecting they're waiting eight hours for a batch to complete and then they're computing the proof

and i mean it's possible that they're computing the proof quickly and just not posting it until the next eight hour window is up but uh yeah there's no reason to do that so um and uh i didn't ask them directly how long is your prover taking but their answer was not inconsistent with with the proofs taking eight hours to generate so anyway what i can say with certainty is the latency for transactions is between 8 and 16 hours and 8 of the hours are just waiting around for the batch to fill but the rest is not waiting for the batch to fill okay as far as what it costs to verify a proof um it's costing on average about 0.468 so this is from publicly this is

just me looking at a block explorer for ethereum um proofs take about 38 ethereum transactions to verify um this is also consistent i mean i did this calculation myself but there's sort of a nice website that just displays daily fees that the roll-up services are paying on ethereum so this was this matched up to what they were reporting [Music] yeah yeah yeah uh no no i should i should do that so for zk yeah yeah so i'm guessing so i know plonk proofs are 510 000 gas um and my just my own estimates are that

uh by using fry the proofs and the parameter settings that they're using it's going to be about an order magnitude bigger but what the verifier does to check the proof is different it's a bunch of hash evaluations instead of a bunch of elliptic curve operations so i can't say that the gas costs you know are you know are exactly proportional to the proof size um yeah it's also like somewhat an artifact of what was pre-compiled [Music] yeah but you know starkware is using you know k-sac 2-5 whatever 256 which is

ethereum's like built-in hash so everyone obviously uses the primitives that ethereum makes nicest to use um yeah but obviously whatever gas cost ethereum set um is were somewhat arbitrary and not done with you know rollups in mind and then they just tap you know people just have to live with them so um okay so yeah like i said starkware was nice enough to send me um which i really appreciate like transaction counts from like a week of starkx clients uh because i they said there were apis um which i never figured out um but so anyway they made it simple for me so um yeah based on those counts there appear to be about 90 000 transactions in a

batch of which only a really small fraction or stark net transaction so that sort of might you know explains certainly stark net users uh being interested in sharing approver um and yeah sort of um you know like like tim said you know just talking about each proof verification isn't so helpful i should have looked at gas um but just you know sort of very unscientific estimate for um the sort of gas savings they're getting you know was about i i estimated about 100x and this matches something that they said in a blog post i don't know how old the blog post was so seems like i was getting the right ballpark um they something to point out is just

looking at gas costs um you know there's more costs uh that the roll-up provider is sort of paying that are hidden because they're running the prover which might be you know killing an amazon cluster or something right so i don't know what those are and then um for the starkx clients i i suspect and they sort of mentioned it in the blog post announcing cairo that uh well they were that was my interpretation of their language uh that an expert cairo programmer might have you know opted they have to write in cairo so that they can all share the same smart contract but you might have an expert cairo programmer you know for a starkex client and a stark net person is writing the chiro program themselves

so um you know they they talked about you know optimizations that uh were being done in the cairo program and that's probably i'm guessing coming from an expert programmer so those are sort of the caveats um about this 100x number um and they they claim and you know i certainly believe them uh you know a thousand x savings for dydx and twenty thousand x for certain like mass nft minting operations i don't know the latency of these applications though i think they mentioned for this 20000x i i think the the email said that these were like for six hundred thousand nft minting operations so that would be um a much bigger batch than what you know i think i was seeing 90 000 transactions in the sharp uh batch so 600 000 is

at least seven times more than that and it's specific to the nft minting anyway um so yeah you get big enough batches and you can see like really amazing guest savings for sure um and the question is just how big can you get those batches so you're seeing the verifiers that stick between multiple transactions yeah a very rough estimate is up like uh 7 million for that price right now so it makes sense you'd have to split it up yeah and that would also make sense as be you know i was just guesstimating the proofs or maybe order magnitude bigger than planck proofs and planck is 510 000 gas so they're sort of matching up but

yeah yeah so you know fortunately uh there were you know uh blog posts and you know stuff they provided to me in email and then and what the performance i was sort of guesstimating through extremely unscientific means is fortunately like matching up with them so um yeah like even though my methods are not great um there doesn't seem to be any kind of mystery or disagreement here or anything so let's talk about security so um so sharp claims it's running at snark at 80 bits of security so what i mean is the smart contract won't let it run at lower than 80 bits of security and i looked on chain i like what the

parameters are and it's running at 80 bits of security but one thing i sort of want to clarify here is it's actually running fry which is the polynomial commitment it's using at 48 bits of security and that's under what i consider pretty aggressive conjectures about its soundness so it's basically asserting a specific fairly simple attack is optimal um so the proved security like what what we can formally analyze of fry is at most 22 bits where so how are they going to 80 bits of security if they're claiming 48 bits from fry uh so they add a 32-bit proof-of-work puzzle that basically uh so what's kind of happening is for the prover in its own head to kind of attempt to find a convincing proof of

a false statement with probability 2 to the minus 48 it has to first solve a 32-bit proof of work puzzle okay so they call this grinding okay um what this means though is that sorry it's a little technical i guess you can just jump to like this bulletproof here so um with more or less two to the 64 hash evaluations um you can have a 2 to the minus 16 chance of finding a convincing proof of the false statement and if you up the number of hash evaluations to 2 to the 80 you can get that probability like quite close to 1.

so so that so this is like an attack that is there if even if the conjectures are true okay can you say something about the conjectures for 48 verses for 22 yeah so i mean shortly it's um you know we we just don't have uh there's a gap between like the attacks we know like what a cheating approver can with what probably convince the verifier to accept and um and with what obviously we can analyze um and there are there are certain technical lemmas that go into the analysis so one part of the conjecture is

that like this technical lemma which it so so all of this involves reed solomon codes um and the technical lemma is proved up to what's called the johnson bound which is some kind of list decoding radius for reed solomon codes and so that that turns out to be like one minus square root the rate of the code so one part of the conjecture is that like the same result would apply all the way up to you can get rid of the square root over that rate um and that conjecture alone is not enough um because the way they analyze like the combination of the frey security

analysis with the polynomial iop involves list decoding and so the johnson bound which is a list decoding bound comes in again so you then i guess need even more like a second part of the conjecture that says like not only can the technical lemma analyzing fry like go up past the list decoding down but you also have to conjecture there's like another way sort of around um needing list decoding or i don't know enough about listing coding maybe maybe i don't know if you could just conjecture that there there are better list decoding results out there i have no idea really um yeah but uh this listing coding ban is coming up in terms of um you know so the approver is claiming to like have sent like a a merkle hash you know that of like the leaves are

evaluations of some polynomial but the verifier doesn't actually know like is this a polynomial so the question is like uh how far away from a polynomial is the actual thing that's committed and that's where the johnson bound is coming in is that that's fine um that is so that is proved in a information theoretic statistical sense and the crypto is only coming in in terms of merkel hashing um with you know collision resistant hash function and then applying fiat shamir to cut out the interaction yeah so 22 bits refers to the statistical security of the interactive thing that then gets sort of merkel hashtag

okay um so here's my like really half-baked analysis though of these attacks so i think they might eventually make economic sense i mean they certainly don't today but um i looked up apparently you know several years ago you know two to the 64 shot one evaluations cost about a million dollars and in principle the way people think about these roll-ups is if you can produce a commencing proof of a false statement you can potentially steal everything in the roll-up i mean could you in practice i don't know you know people and can you actually spend all those funds probably not but you know the idea is that the the snarks are just going to

protect you completely and like all bets are off if if someone you know finds a convincing snark proof of a false statement so you know um you know the hash function they're using is not sha sha-1 it's it's some variant to sha-3 because that's what's built into ethereum i think that's only a factor of you know like three or something slower so you could you could imagine running this attack you know you pay a million dollars or something and you know if you succeed with probability of 2 to the minus 16 you get i don't know 100 everything in the l2 if they actually gain traction could be 100 billion right in principle i don't actually think you could spend that money um and the expected winnings are significant like you would come out

ahead in expectation just you know um not a great probability you're going to succeed but if you do you just you win so much money um and you know if if these roll-ups some of them might launch a token i mean starker hasn't announced plans for that but zk sync is going to for you know their off-chain incentives data availability um and in that setting you could definitely an attacker could make money without being able to spend stolen funds right you just like ruin the roll up the token is worthless if you shorted the token that's how you can make your money um and you know you could potentially short find other ways to short companies if they don't have a token so yeah i mean you know right right now um attack it you know

running like the sort of trivial attack on on this kind of snark doesn't doesn't make sense but like in in a successful in a world where rolex are highly successful it might yeah so i um in practice right now um i i think the answer is only only starkware because starknetprover is shared with starkx and i don't believe that the data underlying starkex is available publicly i that's my best understanding um but if stark net you know it's it's new it's it's every time i check on it the

total value locked in it is going up like you know that'll be a public blockchain all of its data should just be sort of publicly available um it i you know i didn't see anything in these you know kind of sharp verifier smart contract that required a digital signature from starkware if you look at their way of thinking and you know their plans and blog posts they described it's actually it wasn't clear to me you know they talked about well what if the roll-up provider gets you know so in the context of the data availability discussion we had before they were worried about the roll-up provider getting compromised which suggested to me that they were imagining

only the roll-up you know you only had to worry about the roll-up provider doing this data unavailability attack situation but if the smart contract if the data underlying the state of the world is public and the smart contract doesn't require a signature then anyone can submit proofs so i don't have a complete firm answer to your question okay so let's discuss um like why uh what you know why they would run at 80 bits of security so in a sentence it's it's to save gas so what they're doing um like they could increase the security without meaningfully affecting the prover time um it you know uh it would only slo you

know slow down the verifier that's running on chain so they're doing this to say guys okay so some takeaways here um so the existing post-quantum starks uh snarks they they all have bigger proofs than the shortest non-post quantum snarks and in particular those proofs grow the nearly with the security parameter so this is this is why starkware is sort of setting that security parameter aggressively and small um yeah and i'd say i think i already mentioned that my rough estimate is at the um parameter settings they're using the their proof should be about 10x bigger roughly eight to ten something like that um

so you know there's this notion that post quantum security is better future proof it's kind of part of the branding of um of the post-quantum rollups but you know if if you're if your classical security is substantially worse possibly to the point of making attacks make economic sense now is it really is it really better um you know especially while the l1 itself is using non-post quantum secure crypto and all this stuff so that's something you know to consider also you know while i don't know that the prover is taking eight hours to run for sure you know it sort of appears to be unless they're just sitting on the proofs so i think that the latency will continue to be a

concern moving forward as you know batches get bigger and people maybe start doing more than just doing swaps and minting nfts if that ever happens something to point out is snarks with slightly bigger proofs might be fine if the prover is significantly faster because then you can take the batch sizes to be bigger and like a bigger proof from a bigger batch might actually be better than a smaller proof from a smaller batch so um this is sort of where i'm hoping to make some headway with you know the composed snarks i was mentioned last last talk um okay and then i know i'm out of time so i have an ultra brief case study for zk sync and then like one wrap up slide and then that's it

okay so just to compare because ck sync is using planck it's not post quantum it's not transparent so just to compare performance they have a block explorer they actually post time stamps when the commitment to the new you know state of the world is posted um to the l1 and they post also post timestamps when the when the proof gets verified um so looking at their um black explorer uh the proofs typically capture several thousand transactions so much less by at least an order magnitude than these sharp you know stark net and starkex batches and the latency tends to be several hours but this is appears to mostly just

be waiting around for batches to fill because i wasn't able to get a sense on my own of how long the proofs take to compute but zksync documentation says it should be about 10 minutes so you know i don't have any verification of that but yeah this was just an example of like you know what you can see on the block explorer so all of these things have been committed but not to l1 but the proof hasn't been posted whereas all of these the you know it says verified here the proof has been posted and verified and would you say that relatively fast driven mostly by the limited set of operations it's very hard to know i mean in general i would expect um for a given circuit size you know the the

starkware approver should be fry bottlenecked for the prover time um but i would also suspect because they're using the cpu abstraction that their circuits are pretty big you know but this is just based on just high level they're doing this cpu abstraction here the circuits are highly hand optimized and the prover should more or less be kcg bottleneck but also has to maybe commit to more i don't know the comparison of how many polynomials are getting committed in each and that's also going to really affect the prover time because planck requires approver to commit to a large number of polynomials and yes darkwater is polynomial iop probably does too but i don't know the exact comparison so yeah there's a lot of components to these snarks so it you know to actually isolate bottleneck

costs you really have to sit down and look at the circuit look at the underlying polynomial iop look at what the polynomial commitment scheme is i think for a given polynomial like one polynomial of a given size how long does it take kg to commit to it how long does it take fry to commit to it um i think kcg should be a little faster so yeah because they only do one a payment operation that's all yeah yeah so i would guess the circuits are smaller the batch sizes are smaller by a lot um and this is getting a little more speculative but i would think that the

the prover for a given circuit size is also probably a little faster with plunk than with anything using fry and so they all sort of combine to you know give apparently about 10 minutes whereas versus possibly eight hours although again i can't say that with certainty should have just emailed them and said hello for taking instead um yeah is that helpful okay so just the last thought for today um you know the um i you know with the case studies and this discussion of security and you know latency and stuff i i hopefully made clear that i do think that these

front-end and back end like snark choices have major implications for performance and security of the rollups another thing i realized i was trying to just understand what these roll-ups are doing like there's there's a lot more that goes into them just designing the whole system and you know the community you know like i the i think like the block explorer for stark net was just contributed by a community member um you know these smart contracts from stark men are probably going to interact with each other so you know there's a lot of um success of the rollups are going to depend on a lot more than you know the thing that i know about but you know when when security is important and and latency and throughput are

important so um you know you you do you should understand the these details um that i tried to kind of cover today um but that is there's a lot more to um and so the more i look into these roll ups just the deeper sort of the rabbit hole goes of everything you have to consider as you design or build them i mean i will say that whole list is relevant for almost any project and so what's really cool here is that in addition like how well you can implement these core primitives through computer science and also really i agree yeah yeah so maybe for most projects it's everything but this and here's the core engineering challenges were

usually hard and interesting right yeah you know i mean aside from starkware which i guess much happens but they have like some closed source stuff yeah [Music] i think most of these other projects are open sourcing everything and so i guess like i wonder how much even if they develop like a really fast prover like it can sort of be adapted by anybody else right yeah i mean it's not it's not clear and then with hardware acceleration for the prover it's a whole another story because yeah so some of these projects like actively want to distribute the prover both for liveness reasons and i mean other reasons too i guess um

and so but if you're imagining running the prover on an asic because that's what it takes you need all these people out there to own these asics um i mean i guess i'm i'm wondering about like from a business perspective like what's the barrier for any of these it could be like portable for somebody else launching your own competing roll-up yeah that's actually like a yeah so potentially the hardware um yeah i don't know i mean you could

imagine a world i guess where you know um there's a centralized roll up with the best performance but no one else can use it and so but if if they start censoring you you can go to a less performing roll up just speculating i don't know um yeah but uh yeah and there is this difference in open sourcing stuff um i know zk sync 1.0 for example is all open source and i don't know if net eventually starkville eventually plans to open source some of these approvers but um they they they open source to prover for um like a toy computation like a hash chain verification apparently but you know um that doesn't support general cairo program so you

certainly can't use it to um you know prove stark net roll ups even if it wasn't shared with starkx so yeah i don't know what the plan is open source project that tries to optimize the pro register yeah a lot of the projects are um are open source you know polygon zero is is open source um yeah i do wish to having gone through this exercise of trying to figure out what a lot of these projects are doing i i wish there was more than just the source code because um it can be hard you know sometimes you have to go to the source code for some of them to know what's going on and that's not a fun process but

you know it's definitely appreciated that there's a ground truth to what they're doing because the implementation is there uh yeah okay so that's that's a good stopping point for today and uh maybe next time we'll actually see what these sparks are doing after three hours of listening you