Optimizing challenge periods in rollup
Interactive rollup protocols, like our Arbitrum Rollup, speed up smart contract execution by having a validator assert what contracts will do, and allowing other validators to challenge or refute the assertion if they think it’s wrong. If a challenge interval passes without any challenge being made, the assertion is confirmed as true and the system moves ahead. In the common case, assertions will be correct, and challenges will be very rare, so a rollup chain can make progress faster and at lower cost than on-chain contracts ever could.
But how long should the challenge period be? As I’ll show in this post, there are factors that make us want a longer challenge period, and other factors that drive us toward a shorter challenge period. Below I’ll derive a formula for the optimal challenge period that minimizes the total cost of operation for a chain.
Advantages of a long challenge period
It’s well known that a longer challenge period is safer, because it makes censorship attacks on the chain more difficult. A bad actor might try an attack where they make a bogus assertion about what the chain might do, and then they censor any attempts to challenge that assertion, until the challenge period ends. The longer the challenge period, the less likely such as attack is to succeed.
A plausible model of this is that the probability of successful censorship over a challenge period of C block times falls off exponentially with C. If the total value of the rollup chain (that is, the maximum value an attacker could get by stealing everything on the chain) is V, then the expected value stolen by the attacker scales as V exp(-AC) for some constant A. To deter such an attack, we’ll require all asserters to deposit, say, 10 V exp(-AC), so the deposit lost in a failed attack is much bigger than the expected value of attacking.
This imposes a cost on honest asserters, because they have to lock up that much capital. If the chain protocol is efficiently designed and the chain is active, then in the common case there will be exactly one honest asserter who has that much deposited. The cost of that deposit, per unit time, is the deposit size times a nominal interest rate.
The longer the challenge time, the smaller this deposit can be — so longer deposit times reduce (this part of) the chain’s total cost of operation.
Advantages of a short challenge period
Users who want to withdraw funds from a chain prefer a shorter challenge period. If a user does a withdraw transaction on the rollup chain, their funds won’t appear on the main L1 chain until a challenge period has passed. From the user’s standpoint, those funds are locked up during the challenge period.
(The user might find a liquidity provider to advance the funds to them immediately on the L1 chain, in exchange for the provider receiving the user’s withdrawn funds later. But that just shifts the cost of locked-up funds to the provider, and the user will have to pay the provider a fee to compensate — so the user still pays the cost of lockup.)
We can model this cost by assuming that in an average block time, a fraction W of all funds in the chain is withdrawn. The total funds in withdrawal lockup at any time is then CWV (because WV are withdrawn per block, and C blocks’ worth of funds are in withdrawal lockup at any time), and this imposes a cost on the chain users of that amount times an interest rate.
Because this cost is proportional to the challenge time C, shorter deposit times reduce (this part of) the chain’s total cost of operation.
Finding the optimal challenge period
The optimal challenge period will be somewhere in the middle, where the sum of the two costs is minimized. Interestingly, both parts of the cost are locked-up funds, whose cost is the amount locked up multiplied by the assumed interest rate. So the optimal challenge period doesn’t depend on the interest rate — the minimum will be at the point where the total funds locked up, that is, the asserter’s locked-up deposit plus the users’ locked-up withdrawals, is minimized.
Let’s go to the equations. The total locked up funds at any time, on average, are 10 V exp(-AC) + CWV. Because V occurs in both terms, it won’t affect the minimum point. The minimum will be at whatever value of C minimizes 10 exp(-AC) + CW. We’ll find the optimum by the usual method of differentiating with respect to C, then setting the resulting derivative equal to zero and solving for C.
Cutting to the chase, the result is that the optimum happens when C = ln(10A/W) / A.
What does this mean in practice? Let’s plug in some plausible numbers, as shown in the graph above. We’ll set A so that an attacker’s chance of sustaining a censorship attack for one block time is 99% — which amounts to A = -ln(0.99) = 0.01. We’ll assume that 1% of the total value in the chain is withdrawn each day — so assuming 15-second block time, the fraction withdrawn per block time is about W = 0.000002. Plugging these into the formula, we get an optimal challenge delay of C = 1081 blocks. Assuming a 15-second block time, that about 4.5 hours.
How much does this cost? At any given time, a total of roughly 0.2% of the chain’s value will be locked up in one way or another. If the normal interest rate is 5%, the result is that total lockup costs impose a tax of 0.01% annually on the chain’s total value. For that low, low price, you get a chain that is faster, uses much less gas, and is much more scalable than an L1.
Interested in learning more about rollup? Check out my previous rollup tutorial, or learn more about how Arbitrum Rollup works. Or try out our code on testnet.
