Fraud Proof Protocols: BoLD, Dave, and other alternatives

[victorshoup]

Fraud Proof Protocols: BoLD, Dave, and other alternatives

By Victor Shoup

Introduction

BoLD [4] is a new fraud-proof protocol recently deployed on Arbitrum One. Different fraud-proof protocols make different tradeoffs, optimizing one feature, potentially at the expense of others. BoLD is optimized to minimize delay. Other protocols, such as Dave [1], are optimized to minimize prover costs. In this note, we explore these tradeoffs, making detailed comparisons between BoLD and Dave. We also explore other possible points in the fraud-proof design space.

The Dave blog post [2] mentions BoLD but only discusses multi-level BoLD, rather than single-level BoLD (1L-BoLD), which is not at all a fair comparison. Indeed, Dave inherently relies on ZK proofs to obtain “one-step” proofs at the block level, and there is no known multi-level extension of Dave that corresponds to multi-level BoLD, which does not rely on ZK proofs and instead utilizes “one-step” proofs at the instruction level.

The Dave paper [1] does compare Dave to 1L-BoLD (see Table 3 in that paper). Here, we present a cost analysis of BoLD based on assumptions more closely aligned with the assumptions used to analyze Dave (these assumptions are detailed in the comments section of [2]). Then, based on this analysis, we make a comparison between 1L-BoLD and Dave. We also explore variations and alternatives.

Summary

1. For 1L-BoLD, the cost of defending against an adversary with budget {T} is proportional to {\sqrt{T}}. For Dave, this cost is proportional to {\log(T)}.
2. Dave allows an adversary to add significant additional delay by posting just a single assertion and without actually censoring. In contrast, 1L-BoLD cannot be delayed by an adversary that does not censor, no matter how many assertions they post.
3. The suggested bond price in the Dave paper is much lower than that suggested for BoLD. However, as we argue, this price may be much too low to discourage an adversary from causing significant additional delay by making spurious assertions.
4. We also explore variations of 1L-BoLD. One such variation is essentially equivalent to a “single-round Dave” protocol, which has very similar properties to 1L-BoLD, but with much lower gas costs. In other variations, we look at hybrid protocols that more fully exploit the fact that we are already relying on ZK proof technology – using this technology more fully, but (unlike in a ZK rollup) only when there is an actual challenge (which keeps expenses low during normal operation). In fact, this hybrid ZK solution seems to be superior on most metrics than either 1L-BoLD or Dave. This solution has a small bond price and a small fixed cost to defend an assertion, and when there is no challenge, there are no additional costs other than that of simply posting an assertion.

1L-BoLD Cost Estimates

Assumptions:

1. 1 gas = 100 gwei = 10^-7 ETH
   1. same as in [2]
2. 1 bisection takes 500K gas
   1. Based on the current BoLD implementation
   2. The relatively high cost is due to the fact that every bisection writes to fresh storage, which is costly on L1
3. 1 ZK proof verification takes 300K gas
   1. Same as in [2]
4. Number of bisections in a challenge path: 26
   1. Based on the current BoLD implementation
   2. Note that Dave assumes 40 bisections per challenge; however, 26 is enough for the overall design goals of BoLD

So the cost (in gas) of one challenge path in BoLD is ~ 500K x 26 + 300K = 13.3 x 10⁶ gas. This translates to ~ 1.3 ETH.

Table 3 of Dave paper [1] calculates the cost (in bond size plus gas) to defend against an adversary with a certain resource budget. Of course, the defender is guaranteed to win and have all of its costs reimbursed, unless the adversary can exhaust the resources available to the defender. To carry out this calculation, we define:

• {T} = total adversary budget (could be TVL of chain)
• {B} = bond size
• {P} = path cost

We define C to be the cost to defend against an adversary with budget T. In the worst case, the adversary might create T/B challenges. Therefore:

C \le (T/B) \times P + B.

This is minimized when {(T/B) \times P = B}, or {B = \sqrt{T P}}.
So with {B} set to {\sqrt{T P}}, we have

C = 2 \times \sqrt{T P}.

This justifies the claim made above that to defend against an adversary with a budget of T, the honest defender needs a budget of size proportional to \sqrt{T}.

We can also define the Griefing ratio

\rho := T/C = 0.5 \times \sqrt{T/P}.

As in the Dave paper [1], we set {T} = 3M ETH.
Using {P} = 1.3 ETH, we set B := \sqrt{3M \times 1.3} ~ 2K ETH, which leads to {C} ~ 4K ETH and \rho ~ (3M)/(4K) ~ 0.75K.

Single round Dave

As noted above, bisection costs for BoLD are high since each bisection writes to fresh storage. It is fruitful to consider a variant of BoLD in which these different bisection paths are instead played as independent 1-1 matches. While some bisections near the root may be duplicated, this saves in gas overall because the storage costs are much lower. Indeed, this results in a very simple protocol that is essentially Dave with one round and an unbounded number of matches. We will refer to this as “single round Dave”.

According to the Dave blog post [2], one such 1-1 match takes 0.05 ETH for bisections plus 300K gas ~ 0.03 ETH for proof, so 0.08 ETH in total.
So we have P = 0.08 ETH. Again with T = 3M ETH, we set B := \sqrt{3M \times 0.08} ~ 0.5K ETH. Then we have

• C ~ 1K ETH
• \rho ~ 3K

Note: the estimate of 0.05 ETH for bisections in Dave is based on a sequence of 2⁴⁰ blocks, whereas we only need 2²⁶. So in actuality, it should be a bit less, namely, 0.04 ETH, but we will ignore that here.

Dynamic bond strategy

A dynamic bond strategy is given in the BoLD paper (Section 6.3 of [4]). While this does not decrease costs in the worst case, it does not require us to assume any particular value for the adversary’s budget – it scales automatically.

The idea is this: we have a base bond price equal to {P}, and the i-th assertion posted must post a bond of {i \times P}.

To analyze this strategy, suppose the adversary posts N assertions. We pessimistically assume the adversary arranges that the honest defender’s assertion is posted last. So the adversary pays bonds equal to ~ {N^2/2 \times P}, while the honest defender places a bond equal to ~ {N \times P}. If the adversary’ total budget is {T}, then he can post at most {N \sim \sqrt{2T/P}} assertions. To the honest defender’s total cost is {C \sim 2 N P = 2 \sqrt{ 2 T P}}. This is a small constant factor greater than the cost {\sqrt{T P}} calculated above, but we have the advantage that we do not need to know {T} in advance to set an appropriate bond price. Moreover, when there are no active challenges (which will almost always be the case), the posted bond will be very small, so the opportunity cost of keeping a very large bond posted is eliminated.

Note that we set the base bond price equal to {P}, which is the minimum possible to ensure we can reimburse honest gas costs using adversarial bonds. One can also easily verify that this is also the value that minimizes {C}.

A hybrid strategy

A useful observation is that if a defender has to fight off a large number of challenge assertions, it may well be cheaper to simply prove all the blocks of an assertion. In BoLD, an assertion is made once an hour with 4 blocks generated per second, for a total of < 15K blocks. (This is much smaller than 2²⁶, and the reason for using such a huge upper bound requires an examination of several details of BoLD that we will not get into here. Instead, we will simply use this 15K estimate.)

According to https://zkrollup.wtf/ethereum/g6.xlarge/reserved the average cost of proving an Ethereum block is 0.088 USD (as measured at the time of writing, April 2025). We also have

• L1 has a gas target of 15M per block (12 seconds)
• Arbitrum One has a gas target of 7M per second.

So, Arbitrum One has a gas target of 1.75M per block. Per Arbitrum One block, that’s 0.088 USD x 1.75/15 = ~ 0.01 USD, which means the cost of simply proving the entire assertion as a ZK proof is about 150 USD. Using an exchange rate of 1 ETH = 2K USD, this is 0.075 ETH. This is the proving cost of Ethereum blocks. Arbitrum actually uses an extension of EVM (Stylus) that allows for much greater computation per gas, so let’s multiply this cost by 10 to be on the safe side, obtaining a proving cost of 0.75 ETH per assertion.

Using this, we can bound C as follows. Let A be the cost of generating a ZK proof for the entire assertion plus the gas cost for verifying such a proof, so that:

A = 0.75 \mathrm{ETH} + 0.03 \mathrm{ETH} \le 0.8 \mathrm{ETH}.

It makes no sense to spend more than A on gas fees, as we can more cheaply just generate the proof for the entire assertion.

So we get

C \le 2 A + B \le 1.6 \mathrm{ETH} + B.

To force the defender to spend A on gas, the adversary must post N bonds so that N P \ge A, so N \times 0.08 \ge 0.8, or N \ge 10. (Here, we are using the P value taken from the above single-round Dave estimate.) So in other words, if the adversary makes N assertions, where we can take N=10, we stop playing the interactive game and just post a single ZK proof for the entire assertion. To ensure the defender can be reimbursed from confiscated bonds, we need B \ge P and N B \ge (N-1) P + A. Using our estimates, we can take B = 0.16 \textrm{ETH}. Therefore, C \le 2 A + B \le 1.6 \mathrm{ETH} + 0.16 \mathrm{ETH} \le 1.8 \mathrm{ETH}.

Note that the above cost, which is the maximum cost regardless of the number of challengers, is less than that of defending against just two adversarial challengers using the Dave protocol. For Dave, the cost of defeating a single challenger in a full complement of 21 matches is roughly 1 ETH (= 21 x 0.05 ETH), and so for two challengers, the defender will have to do this twice.

The above observations raise the obvious question: if we are going to use ZK proofs at all, why not just use them to prove all assertions all of the time (as in a ZK rollup). The answer is that it is a tradeoff between expenses and delay. On the one hand, if we use the interactive fraud proof, and there are no challenge assertions, the only expense (beyond that of just posting the assertion) is the opportunity cost of keeping a single bond of 0.16 ETH tied up on L1 which is negligible (this expense is 16 USD per year, based on 5% interest rate) but we have the 7 day delay. On the other hand, if we only use ZK proofs, then we have the ongoing expense of generating ZK proofs, which could be as high as 0.8 ETH per hour (so ~ 14M USD per year).

Another reason one might not wish to rely solely on ZK proofs to prove everything is that one may not trust that ZK proof technology provides both safety and liveness. Of course, if one does not trust this technology at all, then it may not seem reasonable to use it for single-level BoLD or Dave. However, even without complete trust, it can still be useful in this setting, if one uses some form of “security council” as a backstop to failures of liveness and/or safety. While such a “security council” solution can work in an interactive fraud proof, it is not really useful in a pure ZK-proof solution, as then one must take into account censorship attacks on the response of the security council, and then one is back to the same 7 day delay, and nothing is gained.

We can also significantly simplify the above hybrid interactive fraud proof protocol. We simply post an assertion, and if it is challenged, we post a ZK proof for the assertion. We still use timers and we still may use a security council backstop if we don’t fully trust the ZK proof technology. We would still have an inherent 7 day delay to protect against censorship attacks. For this solution, we must take B \ge A to ensure that we can reimburse for the cost of proving and posting the assertion, so B \ge 0.8 \mathrm{ETH} by the above estimates. So while simpler, the bond price for this protocol is higher (0.8 ETH vs 0.16 ETH, although this could change as ZK proving becomes cheaper).

Another tradeoff to consider is that any protocol that involves ZK proving entire assertions may be criticized for having a somewhat centralized nature. At the very least, such a protocol may require some amount of coordination among honest parties to carry out a rather large-scale distributed ZK proving computation. That said, the ZK proving can be fairly easily distributed among honest parties in a fairly trustless manner without too much coordination: different parties can generate proofs for different blocks, which can be verified by other honest parties and then “glued” together using standard recursion techniques (i.e., generating a proof that essentially says “I know proofs for a bunch of individual blocks”, which proves the entire assertion). The same type of criticism may also be directed towards single-level BoLD or one-round Dave, if the honest parties are required to generate many ZK proofs to defend against a large number of challengers.

Dave delay costs

The main drawback of Dave is that just by posting a small number of assertions, the adversary can add significant additional delay to the protocol, even if the adversary does not actively censor (which would likely be quite difficult and/or expensive to actually do).
For example, by posting just 8 assertions, the adversary can cause the protocol to run for 12 days – that’s 5 days more than the normal delay of 7 days. (Table 4 in the Dave paper indicates that such a delay can be achieved by posting 15 adversarial assertions. By direct calculation, we determined that this already happens with just 8 adversarial assertions.) Moreover, by posting just a single assertion, the adversary can cause an additional delay of 1.75 days (21 rounds at 10 hours per round, as per in Dave paper); moreover, if the adversary is able to actually censor for up to 7 days, then the additional delay becomes 10 days (the adversary can actually win in 20 of the 21 rounds by censoring, so there may be 40 rounds instead of 21).

By contrast, neither (single-level) BoLD nor any of the variations discussed above have this characteristic: if the adversary does not actually censor, there is no additional delay above the usual 7 day delay (except for the small amount of time needed to make the necessary protocol moves, which is on the order of a few hours); moreover, if the adversary is able to censor up to 7 days, then the additional delay is (approximately) 7 days.

The Dave paper, suggests that very small bonds can be used – they suggest 3 ETH. But if this is done, then the adversary can capriciously choose to significantly delay the protocol at quite low cost. For example, for just 3 ETH, the adversary can cause an extra delay of 1.75 days, without actually censoring. Any additional delay incurs opportunity cost and a degraded user experience for users that want to withdraw assets, and the bond should be priced high enough to discourage imposing this additional delay. A reasonable strategy is to ensure that the bond price is at least the value of this opportunity cost.

To be extremely conservative, consider a bank-run scenario. The Arbitrum One bridge (https://etherscan.io/address/0x8315177ab297ba92a06054ce80a67ed4dbd7ed3a) currently (as of April 2025) contains about 1M ETH. Assuming funds could earn 5% APY, the opportunity cost of delaying the withdrawal of 1M ETH for 1.75 days is ~ 0.2K ETH. This is quite a bit larger than the bond price of 3 ETH suggested in the Dave paper, which did not take such considerations into account at all. This is also significantly higher than the bond price of either of the hybrid protocols suggested above.

Acknowledgements

Thanks to Ben Berger and Ed Felten for their valuable discussions and ideas.

References

1. Dave paper https://arxiv.org/abs/2411.05463
2. Dave blog post: https://ethresear.ch/t/the-dave-fraud-proof-algorithm/21844
3. Cartesi paper: https://arxiv.org/abs/2212.12439
4. BoLD paper: https://arxiv.org/abs/2404.10491

[Suhyeon]

Thanks for your analysis. Your point about Dave’s vulnerability to delay attacks is very clear.

My question is about finding the right bond size. You use a “bank-run” scenario to show that a 3 ETH bond is insufficient, which makes sense for a worst-case analysis.

However, for a more typical scenario using an average daily withdrawal volume , could a moderately higher bond—say, larger than 3 ETH but still far less than the 0.2K ETH you calculated—be sufficient to deter these everyday griefing attacks?

It seems a key question is whether a practical bond price exists that can protect against average-case delays without becoming prohibitively expensive.

[victorshoup]

@Suhyeon Thanks for your comment and question. Please accept my sincere apologies for taking way too long to reply (I was distracted with traveling and then this just fell off my radar for a while…blah, blah, blah…lame excuse, I know!).

On the one hand, estimating the damage that can be done in a worst-case setting is obviously appealing. On the other hand, one can certainly consider the average-case setting as well.

Using dune.com, a colleague of mine estimated the average withdrawal rate from Arbitrum One over the last 7 days to be about 270 ETH/hour. Now, using a single bond, a. Dave attacker can cause additional delay of about 42 hours. Assuming an assertion is potsed once per hour, not only is the challenged assertion delayed 42 hours, but the next assertion is delayed 41 hours, the next 40 hours, and so on. So assuming 270 ETH is withdrawn in each assertion, the total additional delay cost is that of 270 x (1 + 2 + … 42) ~ 270 x 42^2/2 = 238K ETH hours. If we take that 5% annual interest rate and divide by the number of hours in a year, and multiply this by 238K ETH hours, we get 0.05/(365x24) x 476K ETH ~ 1.4 ETH.

This is even lower than the 3 ETH recommended in the Dave paper.

I do want to point out that in looking at recent withdrawals from Arbitrum One, we noticed that there are some very significant withdrawals that appear to be associated with binance (0xE69f81b825d7Dc31ee9becef4DbEab5cf30e3Abb). Indeed, over the last 90 days, there are a couple such withdrawals of 100K ETH, and more of somewhat smaller size. So let us say an adversary wanted to target one of those 100K ETH withdrawals. The cost of that delay would be 42 x 0.05/(365x24) x 100K ETH ~ 24 ETH.

So this is significantly higher than he 3 ETH recommended in the Dave paper, but significantly less than the 200 ETH I calculated in the “bank run scenario”.

One might argue that if users know that it is so cheap and easy to additionally delay large withdrawals, they might change their withdrawal strategy, so as not to withdraw such large amounts in a short time if they do not have to. Of course, expecting users to modify their behavior to mitigate against this attack vector seems a bit undesirable. There are other costs associated against additional delay, some of which may be quite hard to quantify, and for this reason, it seems reasonable to set the bind price significantly higher than 3 ETH to heavily discourage spurious assertions. But now, I admit, we are getting into murky territory…

[Suhyeon]

@victorshoup

Thanks for taking the time to circle back with such a detailed analysis, even if late.

I agree that the delay attack clearly threatens rollup stability. At the same time, because the attacker’s direct profit is limited, I am unsure how far we should push bond sizing and protocol design toward the absolute worst case. It seems we need a risk framework to quantify this trade-off, for example by weighing tail-risk delay costs (including liquidity stress and user trust erosion) against average-case costs and participation frictions from higher bonds.

This bisection game also seems to be a difficult topic in a different sense, and I think we need to work on transforming it into something more intuitive and simple. Another problem is…. it’s really not happening.

[hashcashier]

@victorshoup Wanted to bring Kailua to your attention. It’s a hybrid ZK dispute resolution protocol that’s been in development for almost a year now and is somewhat similar in its general design to your proposal from June, but with some more nuances to reduce the attack surface. Kailua is currently in use as the dispute protocol for BOB Mainnet.

Safety of funds in Kailua is guaranteed just by making a single honest assertion periodically, while the ZK proofs guarantee liveness of valid withdrawals. Moreover, Kailua requires only one constant-sized bond for one party to submit as many assertions as it needs.

Kailua is compatible with the Boundless decentralized proving marketplace, which alleviates also your centralization concerns. A proof for a large assertion can be broken down into smaller proofs (multiple small orders on Boundless) and then cheaply aggregated to prove the original assertion.