Fraud Proof Protocols: BoLD, Dave, and other alternatives

1

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 106 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 240 blocks, whereas we only need 226. 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 226, 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
3 Likes
2

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.