Block Packing: Reducing L1 Costs

Transcript

[Music] Y and we are already back with the next speaker I am really excited to welcome kinet on stage she is proving group manager at starkware and today she will be talking about applicative applicative recursion that's an upcoming Stark net feature which will deliver three big benefits I'm sure we will hear from her what these benefits are so um yeah you will get an engineers's insight into all of these upcoming features please welcome her on [Music] stage hello hi um so thank you for the

introduction my name is kin seal and I'm working uh in the engineering things in starware I'm leading the proving group and today I'm going to actually talk about block pecking so applicative raran was the previous name but we we've changed it lately because we think block pecking is more informative name so I'll be happy to hear after the talk if you think block pecking is indeed uh a good name H and block packing is a very cool feature that we are going to add uh to Stark net very soon um this is going to reduce L1 cost and do some a magic Magics that you will hear in this talk but first uh just make sure you all know stockar so we are a company uh

building validity rollups for a few years uh two main rollups we have is one is Stark X and the other one is Stark net both are validity rollups that H using Stark technology um and our uh uh a rollup is based on uh the Stark protocol which is implemented in sharp sharp is our shared prover system and it runs the stone prover stoneover is a prover we just released like more than a year ago and actually now we are working on a really cool the next gen prover which is Stover um but this is for another talk if you're interested you can reach out

to me or to any other of the starkware team members here and we can tell you about it h so starx and Stark net we have up to $1.3 trillion in community trading uh up to more than two billion dollars in tvl and from the beginning until now we have over 800 million transactions so that's kind of a lot of traffic there so now uh let's dive in into understanding what this block pecking feature is but before I would like to explain you about the new feature first I would like to walk you through step by step how the system looks now from the moment the transaction enter into the

system up until the state update on layer one so uh we have transaction entering to the the system and the first step is the sequencer so the sequencer takes the transaction and it forms the new potential blocks uh that are going to be the next blocks for Stark net and then before we update the state of the system with the new blocks we need to validate them right this is a validity rollup so we send the blocks to Sharp and sharp is the uh as I said before it's the shared prover it's the system that is in charge of proving a valid statement so let's do a few minutes of dive into what's happening in sharp um so we use sharp sharp to

promote a complex state it doesn't have to be necessarily Stark Stark net sharp is a shared po so it gets input from many uh different applications and systems but for now let's focus on the uh um on the interaction between Stark net and sharp so we have Stark net uh generating blocks and they send these blocks to Stark net backend to sorry to start to sharp back end um and the backend H creates the proofs for these blocks then the proof is being sent on chain to be verified on chain using the the solidity verifier if the proof is valid each of these blocks are going to

be registered uh in some special uh storage that is called fact registry so each block is going to have its own fact the fact is a unique identifier that um that identifi this block and the fact that the fact is written there signals that this block passed successfully both the prover and the verifier on chain and then starnet can do fact polling it can check that the fact is there and if the fact of the specific block is valid it can update its state on layer one and we do it block by block on layer one so each block has its own footprint of the fact written in layer one and we update the state block by Block in in layer one

in the stet side uh a slight more a slight uh an extra step in understand what's happening in sharp so maybe some of you know it we have a recursive flow so this is a little bit complex so bear with me we have blocks arriving to uh to Sharp you see the blocks you see the blocks to the left and first we generate a proof for each single block in it be a really small block or a big block but we generate a proof for a single block separately then we don't send these proofs on chain these proofs this wouldn't H give us the scale that we need because it can be a really small unit of uh computation so what we do we uh verify the proof using our chyo

verifier so Cairo is the language that our prover knows uh if you don't know Cairo please check it out this is a very cool language but anyway this verifier is not offchain is not written in solidity it's written in Cairo and it verifies the Stark proofs so now the Kyo verify verifies two proofs together and then we send this uh chiro program again to the prover to prove that the verification of the two proof of the two original blocks are valid so we get two to one we squash two to one and now we have a single poof for two different blocks and we can do it again again we

iterate this process and that's how we build the recursive tree of sharp so what you see here is the recursive tree the leaves are the original blocks but as I mentioned before sharp is a shared prover so the leaves can be uh not only of starnet blocks it can be of other um application it can be a different blockchain operating on top of sharp it can be uh starx for example but any uh logic unit can be uh plugging into the leaf and sharp eventually generate a single proof for all of them the last proof is the root proof and the root proof is sent eventually on chain to the

solidity verifier and this proof is actually a proof that the verification of the proofs of the verification of the proofs of the verification of the original proofs of the original leaves uh are okay so sharp uh uh sending the proof on chain and as I said before it's right a fact for each of the original Leaf to signals that this fact this uh leaves were proof and verified successfully on chain okay so uh zoom out again we had the transactions then it went to the sequencer in Stark net the sequencer forms the blocks then blocks go into Shar

we form this recursive Trin sharp and we sent the last proof the proof of the root on chain then for each of the leaves for each of the blocks we send we write fact on layer one to signals that these blocks are valid and now Stark net can update its state on layer one based on these facts so we check that the facts are there and then it promotes the state one by one for each block we also send the state diffs on layer one for data availability and we use the blobbing mechanism the new mechanism that we introduced lately in ethereum so we send a state if through there we use a single blob per a single block no matter if the block is full or

not we uh have a blob for each block so that's the end to end wait can I go back okay so that's the end to endend uh flow and now let's think of what we are paying for in this uh in this flow so I would like to focus on the uh block footprint uh what we the fixed per block cost on layer one in that flow so to the left you have the different operation we need to do for that flow and to the right uh for each unit we do it so we do a state update it cost 86k and this is done as I said before

per each block separately also uh for the blobbing mechanism we need the kzg precompilation it cost 50k and we do it per each block separately per each blob separately and but we have a blob per each block then we have the factor Distortion this identifier that we run on chain for each block this is 23k per each block and then there is something which is called memory page transaction which is the output of the block and again we pay 36k per each block so all in all we have almost 150k per block plus 50k per blob and this is done for each block

separately there is also the cost for sharing the proof but I didn't get into that one because what I want to focus on uh today is that we have here a linear cost for in the number of blocks and this is not very scalable right because we if we have more traffic we have more blobs we need to pay uh a linear cost in number of blocks so one of the motivation of the the new feature the block uh packing is to decouple this uh this connection between the uh the blocks and the fixed payment per block okay but if you are uh worried don't worry because we have a solution um but first uh I would like to

introduce you how we decrease the L1 cost in the current architecture without the new feature um so what we decided to do is to make the blocks bigger okay we used to operate uh to process around 10 million chyo steps per block but we gradually make it big uh bigger lately and now uh the blocks are size around 45 million chyo steps so this is more than four times more and this is good because now we have a better blob utilization right because uh The Blob are Fuller there are more State diffs and also the data for bigger blocks can overlap so it's also more efficient also we write less fact

and do less State update right because we do it for each block but now block are bigger so more transaction can fit into a single block but this uh uh but this uh solution has also uh many disadvantages uh because now all the the unit we process the blocks are bigger right it takes longer to run them longer to prove them we need bigger memory we need bigger machines and I think uh some uh really bad um not bad but something that we really didn't want uh is that now we have longer L2 finality right because on the same traffic we need to uh accumulate more transactions to uh

close a block so the frequency of the blocks went down and this is not a good uxix uh property of this uh Improvement and also probably some of you already noticed that we are still linear the number of blocks which is something that we want to avoid okay so I'm sure you can guess now that we have block pecking um so I would like to walk you through again the flow uh that we have uh uh in Stark net and sharp but now with the new feature of block of block pecking so we have transaction it's the same right transaction enter into the system and they go to the sequencer

and again they formed the block but now as the N the name indicates we did some kind of a packing so we treat the blocks in some sense a multiple set of blocks as a single block and we send them all together to Sharp so let's do another dive into sharp but now with the new feature of the block packing so what do you see to the right is the original tree of recursive tree that uh I've mentioned a few slides before so we have the leaves and we have proves and we create the verification and then Pro again and so on and so forth but now uh some of the leaves are not a single block but they are root of

what we called the block pecking tree so to the left you have the block pecking tree and you have the original block the set of block that were sent to sharp as a set and we generate for them exactly like before a proof and a verification and a proof of the verification and so on but eventually in the last um in the root in the last proof we squash the output of the blocks and the the root uh symbolize uh the entire tree so the root is like a block that uh is that represent the entire set of blocks and this is like the original Leaf of the uh sharp

tree so how does it help because now when we're writing when sharp sending the proof on chain we don't write a fact for each of the original block but we write a single fact for the leaf for the leaf of this uh tree to the left sorry for the root of the of the tree to the left and also the data is uh much more efficient because there are many um there are many St say diffs that some of them cancel each other and the uh the root there is um H is the most compressed H State diffs of all the original blocks so if we do a zoom out again we

have a transaction they're going to the sequencer the sequence uh the sequencer forms the starnet blocks but now the blocks are a set of blocks and not a single block separating I mean uh with respect to Stark net they are single blocks so the L2 frequency is uh doesn't we don't harm it but from the perspective of the prover it is a multi set of blocks and as you see here to the right sharp has now a the new uh the new um structure of the tree so it has the tree but it also have a sub sub tree which is the block pecking tree and now we send the proof of the root of this

entire tree but we also send uh a single fact for all the leaves of the sub tree we don't send uh four fact as before but one single fact for all of them what about State update so we save here as well because now as I said we treat them these blocks uh as a a set of blocks and we do a single state update for this all set of blocks Al also for the state diffs we use we are now have we can have a a a few blobs that uh we used in order to send the state diffs and to do the data availability solution uh on layer one

and we close the tree based on the blobbing uh how how uh much the blobs are full so now we can utilize The Blob much more and we can gain from that also uh a decrease in the cost So eventually we do a single State update we write single fact and the state diffs are much more efficient so uh this introduced a really high uh Improvement in uh efficiency and in scalability just um to sum up what we've said so let's go over the same uh operation that I mentioned before because we do the same operation but now let's see uh how it uh this new feature helps us so we have state update again

we pay the same we didn't Chade the state update itself the logic it's 86k but before that before the feature uh we paid it per block and now we paid it for the entire block pecking tree and this tree can be really big it's I mean here in the slides you see for a for blocks but it can have like many blocks um kyg compilation again we pay 50k per blob and the same we pay per blob but now Globs are going to be much Fuller and uh eventually it will be more efficient then fact registration the fact that we were used to write for each block we now write it for the entire

block pecking tree so again uh um we pay the same but we pay it on a much larger set of blocks and memory page again we have a single memory page for this entire block packing tree so we paid the 36k but for the entire block packing tree all in all the same uh amount of gas but we paid for much more blocks and this gives us um uh the scalability and the decoupling trade that we wanted so yeah I started by saying that we want to decouple the stet block frequency from L1 cost and this feature actually does it because now we have

this entire tree and this tree can be bigger and bigger and we don't pay like a fixed cost for each block separately but we pay for the entire tree again also blob utilization it's much better because there's a as I said we can uh close the tree based on the utilization of the blobs and also when you have many more blobs to blocks together State diffs are more efficient there are more chances to overlaps between the states uh of the BL between different uh diffs of the blocks and then we can uh utilize The Blob much better and then eventually it reduces L1 cost which is what we wanted and we can go back to small um to small blocks to Big Blocks I mean we decoupled the

frequency of the blocks from the cost and now we can play with the block size without uh uh harming the uh user experience with the L2 finality so we are happy okay thank you thank you so much um on the question on whether that is a good name I think that is a better name it is much easier to pronounce okay um do we have a question from the audience uh please raise your hand if if that is the case I can't see you otherwise does not look like it I mean you can also find Kinder at around sure

if you have any questions off the stage um thank you so much thank you [Music] why