Efficient Rollup Batch Posting Strategy on Base Layer / Akaki Mamageishvili

Transcript

foreign [Music] welcome to my presentation and I want to thank organizers for organizing this excellent event so this is a joint project together with Edward Felton who is a co-founder and chief scientist at of chain labs and I joined them last year as a research scientist so if you are not familiar with of chain labs this is a company that built arbit room roll up chain and contributes to its development at the moment

so now what are Roll-Ups this is probably the shortest introduction in the Roll-Ups so the purpose of Roll-Ups is to scale the base layer and in our case it's ethereum but in principle it can be some other layer one blockchain and he does by moving the execution phase of of the chain but it they inherit security of the base layer by posting the transaction relevant data which is called call data to this base layer and here in case of optimistic Roll-Ups as arbitrary transaction relevant data is just

transactions compressed but you can imagine some other technologies that can pull some other specification of the data and then second part where the roll up technology comes in is some roller specific mechanism that checks that execution was done correctly okay so now here we are solving a problem of posting call data at the right time and as you saw in the previous presentation I think there was a slide where ethereum based fee Rises very quickly and very high but it doesn't

last forever it lasts for a few hours maybe at most and these periods the Roll-Ups or sequencer of the roll up or whoever posts the transaction relevant data called Data want to avoid posting because the price is high but on the other hand it also they also want to avoid delaying the posting too much okay and one instance is that uh there was a time where basically raised 100 times and it lasted several hours and the automatic mechanism of the sequencer

didn't post the data and then arbitrine developers had to manually post the data okay so now how do we model this optimization problem so we assume that in round I so round corresponds to every time that's a new batch is created we count how many batches do we have currently queued and we also look at the current base fee price okay and then we need to make a decision based on these two numbers do we want to so how many uh patches do we want to post okay so this is our

strategy s that is a function of the price that we see now and how many batches do we have at the moment okay so intuitively you can guess that s should be weakly increasing in the QI so more patches we have in the queue more we want to post and it should be also weekly decreasing in price higher The Price Less we want to post and this just helps the optimization in that it decreases the search space of optimal strategies Okay so next is how the cost is modeled so first part of the cost is

exactly how much we pay if we post ni many batches and batches have the same size approximately that was the case at least with arbit room that creates almost equal size batches then the first part of the cost is a direct cost of hosting and second part of the cost is delay cost and here we take quadratic function of how many are remaining for the future how many batches do we want to post in the future but you can take some other function we thought that quadratic is easier to analyze and it has some nice analytical properties and also because

we wanted it to be faster than linear function so there's this normalizing factor C it should also capture some preferences so here I want to make a comment for example if the rollup has a technology that delays the finality then you you should not withhold a batch more than this time for sure otherwise there is a security issue and in case of arbitrum that the delay time is quite large it's one week so it's fine to assume some quadratic function and anyway the coefficients that we are plugging in it makes too expensive to delay so we are never

reaching one week period okay so further justification of delay costs first is psychological when the user see that batches are not posted they think that maybe sequencer is broken and that creates maybe some kind of panic another is L2 users so roll up users they may have preferences about how fast they want their transactions to be posted on the base layer and the third part which is not very relevant at the moment because the sequencer acting the interest of the roll up is that pricing of the transaction and

compensating the ethereum so the compensating the sequencer for posting on the ethereum on the base layer and further the there is a delay harder the mechanism to compensate becomes so let's uh further justification of the delay cost okay so now what is the optimization problem in the next round we are subtracting how many batches we posted but one new batch arrives so that's how rounds are actually defined and we assume that in the next round the price of the gas fee is a random

variable that depends on the current price and at the moment we assume that this is independent of what Roloff does or what is our strategy but I would say this is not completely true at the moment if for example there is some huge roll up it can also move this price up if it posts too many or down if it doesn't post anything and in the future if roll ups become even bigger than this may not hold but at the moment let's say it's a reasonable assumption hey what is the objective value we want to optimize discounted costs so we sum up

costs over the infinite Horizon and we discount the future so one unit of cost we incur today is Delta in the next round and Delta Square in the next next so we care slightly less about the future and more about the present and this also makes the expression converge so initially we take that we don't have any patches so we start from fresh and there is some price of the base fee but results are independent of this initialization actually okay so now what do we think about the gas fee so first we assumed that it's

uniformly distributed on this interval of seven over eight times the price and eight nine over eight the price and these constants are coming from base fee mechanism CIP 1559 so if there is a maximum demand achieved then the base fee is increasing by 12.5 percent this is one over eight if the demand was Zero then it decreases with the same amount and we we were assuming let's say in the next round demand will be uniform at random and that's what happens with

the price and then if for example arbitrum posts or yes any other roll-up posts every five blocks then we need to take a convolution of five uniform random variables and this is quite a good approximation form for normal distribution but then we looked at the data and it doesn't look very uniformly at random uniform at random and there is a big outlier we see that in about 16 17 percent of the cases full blocks blocks were created

and that is happening because of the priorities and how EIP 1559 works and there is some small Spike also some small outlier at zero blocks and this is also happening because of the CIP 1559 and there is another paper that we later found out that shows that sometimes if there is a big Miner it prefers and things that this Miner will propose to also not minor but no proposal proposal proposes two blocks in a row it prefers to keep one block empty so that basically goes down and then make next block full because then

it can collect more priority fees so whatever this is the what data shows and we we have to work with this but if you look at one minute relative change now it looks kind of normal there is small Spike at 1.8 which means that five times in a row there was a full block but otherwise it looks quite normal with some yeah some bias on the left but that is also explainable and yeah actually I skipped this part here that the product of these two numbers T1 and T2 is less

than one so this is again coming from the eip1559 transaction fee mechanism but anyway as you see here uniform so the normal distribution is a good approximation of what is happening to the price when roll up comes next time to post a batch okay this side already talked about so related literature is actually inventory policy problem where so there is some manufacturer produces

something in our case manufacturer is roll up and produces blocks and it wants to either sell depending on the price and demand in our case these are cost of posting so that's the first difference but in principle is they are dual problems and second difference is that manufacturer has linear costs or at least that's what we found is in the literature and that is associated with maintenance costs but in our case we think that it's not linear because of the nature it's not just maintenance because we don't keep it in the warehouse but yeah users have some requirements that their transactions are on the base layer or we have some

deadline that we need to post so to solve this problem we applied the Q learning so it's dynamic programming so we need to calculate two matrices so first Matrix is the Q from the Q learning I suppose it has parameters State St that tells what is the price and also how many in the queue we have the batches and the a t is a action so in each state we need to know what is the best action or what will be the value of the Q

table if action 80 is taken and then we need to calculate the optimal action and that is denoted by o vector and we have this value update iteration with 1 minus Alpha let's say probability we keep the original value of the table and with Alpha we take cost that is incurred in this state plus Delta times because Delta refers to the Future expected cost but taking into account that when we go in the future we will take optimal actions

okay so this is where this is what is mean a means so we are taking the action that minimizes the cost so we assume that in the future we will optimally distribute or poster batches okay so this is a very clean iterative formula and yeah so I already explained what is City that's the cost that is incurred by taking this action 80 and to find this action a that is minimizing the cost in the future we take all Vector element because we know that o is

optimal and then we calculate all or resign values of O once we iterate and update values of Q new Matrix and initialization can be done in arbitrary way but we just took one of the initializations which means that at every moment we post all the batches okay this initialization but you can pause zero batches and it doesn't really matter it converges very quickly and with the same speed okay now the complexities and the how much we could try how large values of uh

price and the the size of the queue so we discretize the price space of course we couldn't calculate on the continue and yeah so we assume that we cannot hold more than some upper bound on Q batches and then the space complexity is the size of this large Matrix is p q square and this is not a bottleneck then we need to also assume something about the support of the random variable that defines the next round price and if we assume that this is also linear in the price and in case of

let's say in uniform case it's not exactly linear but in case of normal distribution it's linear then time complexity is P Square Q squared this is already quite slow for large values of p and Q but there is also the convergence the ah parameter I so we want we we will not calculate the precise values of the Matrix but we need to converge to something and this parameter depends on the learning Factor so higher the learning Factor so it's not actually exactly monotonic but what it really

depends on is Delta so higher the Delta slower it is so if we take Delta closer to 1 which means that we care about the future cost almost as almost the same as today's cost then it becomes very slow okay so now what are the insights that we obtain first is that there is a threshold price below which all batches are posted so if the price is low enough just post all the batches and this is actually quite intuitive but if the price is high enough then it depends now we want to keep some size so there is another threshold that depends on the price

about which we post everything and Below which we don't post anything okay so there are this two thresholds here and then we compare this algorithm that we calculated the optimal algorithm to the old algorithm of arbitrum and compare their performance so in the new algorithm the q-learn algorithm we have two parameters so first we need to define the large threshold TP and then depending on the price we need to Define decide how how fast so how large is the other threshold

that depends on the price in the original algorithm were three parameters so there was an acceptable price under which it post the batch and each batch is associated with these three parameters then there is some exponent and third there is update time so what happens if the price is not below acceptable price then it waits for this update time which in that case was two hours and then it multiplies the acceptable price by exponent and that exponent was two so it was waiting for two hours and if

the price was still not good enough then it was doubling the price so there is also trivial algorithm that we looked at and this is just post all batches immediately and has good property that there are no delay costs but of course sometimes then you post very very high cost and you don't wait for the price to drop and also it has many minimum load on the system when you do this L1 cost calculation okay so there is another algorithm that also completely ignores the delay cost and just waits for the price to drop below some threshold but there will look

at the data and saw that if for example you take threshold cost 100 then you need sometimes to wait 1394. blocks and this is unacceptable and 360 it was 14 000 crazy so that is completely unacceptable okay so now we compare these two algorithms that we have and see that the old algorithm actually does better job when it comes to publishing costs so the observable cost but the new algorithm doesn't make it too bad so the publishing cost slightly increases but delay cost is dropped very much and if you look at the maximum delay it's

much lower so for example for parameter 60 and 2 maximum delay is only 40 to uh minutes while in case of let's say the original algorithm it would be 193 that's like more than three hours so there is a lot of future research to be done in this Direction first we don't have a theoretical proof of optimality of our insights or why do we need to have these thresholds and I think it's a possible to do fairly easy but yeah I'm not an expert in the optimization field or that kind

of optimization second is yeah so I mentioned that it can be that price changes depending on the strategy and now we assume that it's independent so that is also an interesting problem to look at and then the same approach doesn't apply so there was also mentioning of the CIP 4844 by Mario I think so this is new Initiative for the batch posting or the roll up data posting called the data posting which creates a new market and one main thing that all these what we did now becomes irrelevant because this data will become

almost free but this is not the case and I I think in size that we obtain in this research will be useful in the future when this proposal will be deployed and the last question is assume so so far as far as I know only only arbit room uses this strategy and other chains are doing so I don't know exactly what they're doing but most of them are not doing this strategy and it would be interesting to observe if this strategy is an equilibrium strategy so if everyone else does this is this equilibrium or do the separate chains prefer to deviate from this

please thank you for your attention [Music] thank you very much I think yes the microphone is working we have about five minutes for any questions that has been super technical and super interesting I don't have any questions because I don't follow everything but maybe Wolfgang in the middle of the room has a question or someone else yes sir right in the middle do we have a microphone for that gentleman right here in the middle or you can shout absolutely hello and there is a threshold uh below

which you take everything is is that right so there is threshold below which you post all patches and above which there is another threshold depending on the price you want to post more or less and what do you do in between the two thresholds also there is no in between so let's say we post threshold 60. so under 60 WE Post everything about 60 let's say if it's very close to 60 WE Post almost everything but let's say keep one so from 60 to 64 so there is some functional form we keep one batch but if it's higher and higher we keep more and

more so for like let's say 200 we would keep 10 batches but the rest we will post oh so it's not that you keep everything in the queue is that yeah keep some amount depending uh how large it is and larger it is more we keep okay and do you know or have you thought about what happens if you include some randomization in the keeping process so instead of keeping it linearly or quadratically as it increases maybe there is some randomization so I found one result that shows that deterministic strategy of this type is optimal so it doesn't specify what is the strategy what it says the sum strategy like this which specifies for

each price so this is from inventory policy literature so that specifies for the price or the demand in that case and the quantity uh posting or selling fixed amount deterministically is optimal so you don't want to randomize or do some weird things and okay that's that's great and um is this already um productive is this how arbitrary sequencer Works yes yeah so we deployed it uh last year in November and it already went through the spikes a few times but there is not enough data to make some conclusions yet but at some point

we will track the data and observe what it is does what it is actually doing in the production thank you very much thank you thank you for the question we have one minute and 10 seconds until the next session time for one more question anybody anybody Wolfgang you're taking notes no if not then we thank you very much for the presentation super and you can just join us on the side here we're going to move on to the next section but before that thank you very much [Applause] foreign