The Dave Fraud-Proof Algorithm — Triumphing over Sybils with a Laptop and a Small Collateral
(a.k.a. Fraud Proofs Are Not Broken)
The security of fraud proof systems hinges on two key properties: you should be able to become a validator (even if you’re broke), and you should be able to prevail over any number of dishonest validators (even if they’re a nation state). Together, these two properties allow an optimistic rollup to inherit the security of Ethereum. In addition, we require a third property: that disputes settle in a timely manner.
As it turns out, it is quite hard to design algorithms that adequately fulfills these three properties — allowing just anyone to participate opens the floodgates for an attacker to create as many Sybils as its resources allow.
Last year, in an ethresearch post, we showed that no algorithm at the time adequately satisfied all three properties. They were vulnerable either to resource exhaustion attacks or delay attacks, and mitigation strategies inevitably restricted participation. As a result, all implementations were destined to be suboptimal. This is particularly worrisome, given that over 90% of all value secured by rollups is poised to be protected by fraud proofs.
In November 2024, we published our novel research on this topic, introducing the Dave algorithm — a new fraud-proof algorithm that is resilient to Sybil attacks. We later presented our findings at Devcon SEA.
In this post, we provide a concise overview of the algorithm and its results. While Dave builds on established concepts in fraud proof protocols, it also introduces several novel techniques that address longstanding challenges, such as resource exhaustion attacks and delay attacks. We believe these advancements may represent a significant step forward in the field. At the same time, we are eager to engage with the community — especially those working on similar challenges — to refine these ideas further. Your insights and feedback will be invaluable as we continue to develop and enhance Dave.
Note that this post focuses on the theoretical properties of the Dave algorithm rather than its current development stages. We assume the reader is generally familiar with fraud proofs, and we have left the more technical details to the full paper. Interested readers are encouraged to read the paper for an in-depth analysis.
Resources
- Permissionless Refereed Tournaments (PRT) — our first algorithm, which introduces the computation hash (a.k.a history commitments), tournament brackets, and recursive disputes.
- Fraud Proofs Are Broken (but we can fix them) — our ethresearch post that started it all.
- Fraud Proof Wars by Luca Donno from L2Beat — an in-depth analysis of fraud proof approaches, algorithms, and trade-offs. There’s also his Devcon SEA 2024 talk of the same title.
- Dave: a decentralized, secure, and lively fraud-proof algorithm — our paper detailing the Dave algorithm.
- The Dave Fraud-Proof Algorithm: triumphing over Sybils with a laptop and a small collateral — our Devcon SEA 2024 talk on the Dave algorithm (here are the slides).
TL;DR
There are three properties we need from permissionless fraud proof protocols:
- security — an attacker must spend an impractical quantity of resources to defeat any single honest validator;
- decentralization — participation is unrestricted, either by imposing a permission list or demanding the deposit of expensive bonds;
- liveness — disputes settle in a timely manner.
Dave allows (but does not require) honest validators to cooperate trustlessly, playing collectively as one. We refer to this collective of honest players as the hero, and we call the attacker and its mob of perfectly coordinated Sybils the adversary. We’ll use the terms validator and player interchangeably.
Launching a Sybil attack in Dave is exponentially expensive for the adversary, relative to the resources the hero must allocate to prevail. In practice, this enables a singleton hero to triumph against nation-states — even with cheap bonds and no permission lists. The hero requires only a constant amount of hardware to participate in Dave, regardless of the number of Sybils, and the costs incurred are reimbursed after the dispute is resolved.
Crucially, settlement delay grows logarithmically on the number of Sybils, but with a key advantage over Permissionless Refereed Tournaments (PRT): the constant multiplying the logarithm is one order of magnitude smaller. As a result, Dave settles disputes within 2–5 challenge periods for any realistic number of Sybils.
Below, we compare Dave with three other fraud proof algorithms: OPFP from Optimism, BoLD from Arbitrum, PRT from Cartesi, and Dave (also from Cartesi). We consider a scenario where an attacker burns 1 million ether to launch a Sybil attack.
This comparison focuses on three key properties:
- Bonds: setting bonds too high undermines decentralization by excluding potential validators;
- Hero’s Expenses: excessive expenses compromise security — if the hero lacks sufficient funds to cover costs, the adversary will win and steal the total value secured (TVS);
- Delay: high delays harm liveness by slowing dispute resolution.
Note how Dave strikes a favorable balance between bonds, expenses, and delay relative to competing methods.
| Bond | Expenses* | Delay | |
|---|---|---|---|
| OPFP | 0.08 ETH  |
1,000,000 ETH  |
1 weeks |
| BoLD | 3,600 ETH  |
150,000 ETH |
1 weeks |
| PRT-1L | 1 ETH |
1 ETH |
20 weeks |
| Dave | 3 ETH |
7 ETH |
3 weeks |
* Expenses are reimbursed to honest parties after the dispute is over.
Although burning 1 million ether a very expensive attack, BoLD currently protects more than three times this amount (see L2BEAT) — it is conceivable, provided that it has an appreciable chance of succeeding.
Threat and resource model
The security of optimistic rollups depends on certain assumptions concerning the way blockchains operate. We assume that all transactions are processed correctly, eventually. However, we also assume that the adversary can subvert this process, to a limited extent, by:
- Censoring transactions: The adversary has the power to delay any set of transactions. The only limitation to this power is that the total amount of time during which it is exerted cannot exceed one week. This means the adversary may choose to use up all its budget in one go and delay any set of transactions for a week, or partition its budget in multiple spans of censorship.
- Reordering transactions: The adversary has the power to reorder incoming transactions on the blockchain, for example by front-running honest validators.
Interactive fraud-proof protocols require players to take turns when interacting with the blockchain. If no deadlines are set, the adversary could stall a dispute indefinitely. Conversely, the adversary could use its censorship budget to force the hero to miss a deadline. Fraud-proof algorithms must therefore take the censorship budget into account when setting the penalties incurred for missing any deadline.
It is quite a challenge to design lively protocols around a one-week censorship assumption. Pessimistically setting the deadline of every interaction to at least 1 week would ruin the liveness of any protocol. Protocols commonly use strategies like chess clocks to amortize this 1 week over many interactions. Dave introduces a novel technique that amortizes it over the entire dispute.
Players interact by making moves, which require spending resources (gas, compute, and/or bonds). The only hope an adversary has to defeat the hero is to exhaust its resources, preventing it from taking part in the dispute and compromising the security of the algorithm. Because of this, it is not sufficient to consider the hero as the total number of honest agents. The analysis must include the resources held by the hero as well. We need a more nuanced understanding of what “one honest validator” means.
For that, we take inspiration from Vitalik’s post. He describes trust as the use of any assumptions about the behavior of other people, classifying trust models as “the ability of the application to continue operating in an expected way without needing to rely on a specific actor to behave in a specific way”. When an algorithm allows N players to participate but requires M of them to be honest, he argues, M should be as small as possible (ideally 1) and N as large as possible.
(From Vitalik’s Trust Models)
This maps naturally to what we have described as security and decentralization. In the context of fraud proofs, decentralization demands an arbitrarily large value for N, and security demands — in addition — that M be 1. Algorithms that have these two properties (i.e., a single honest validator can enforce the correct result, and that validator can be anybody) inherit the security of the base layer. Through this lens, we define “one honest player” not as an individual agent, but rather as a unit of a total of N resources, M of which are spent to defend the correct behavior.
We assume the existence of at least one honest player.
The Computation Hash
Claims in Dave, like in PRT, are a computation hash: rather than committing only to the final state of a computation, validators now commit to the entire path of a computation. A computation hash is a Merkle tree where each leaf corresponds to an intermediary state in the execution history.
Now every bisection during the dispute must be accompanied by a valid proof that the segment is consistent with the original computation hash. This requirement prevents validators from lying during bisection; once committed, players can no longer lie during bisection. In particular, an adversary that posts the honest computation hash cannot single-handedly lose the game on purpose.
Unfortunately, building computation hashes that contain all state transitions is extraordinarily expensive if the state transition is a small VM step. In PRT, we proposed recursive disputes to mitigate this cost, but it introduces other problems. In Dave, we instead change the state transition from one VM step to several VM steps, and use a validity proof (i.e. a ZK proof) for the final one-step proof.
Dave
Dave, like PRT, employs a divide-and-conquer strategy that forces Sybils to eliminate one another, so that the hero never has to personally fight and defeat every single Sybil. To this end, we use a tournament-like matchmaking mechanism to pit competing claims against each other.
Our first attempt, PRT, used a simple bracket tournament that gives the hero an exponential advantage both in resource costs and incurred delays. Dave builds on this by introducing a repechage mechanic, not unlike a Swiss tournament. This mechanic, in addition to the exponential advantage, amortizes the one-week censorship assumption over the entire dispute.
Here is an informal overview of a dispute resolution under Dave:
- The hero submits the honest claim (a computation hash), and each Sybil submits a dishonest one. Claims are unique. All competing claims must be posted within 1 week. Rounds start as soon as there is more than one competing claim;
- At the start of a round, Dave partitions all surviving claims into small groups of size
G, following a specific matchmaking rule that we’ll describe later. One can think thatG = 2for most cases. Each group spawns one match for every pair of claims within. All matches of all groups in a round are concurrent, starting together and ending together. The round duration is fixed and is significantly shorter than 1 week; - A match concludes with one claim defeating the other, either by timeout or through a step action. The claim that wins all its
G - 1matches wins its group, and all the other claims lose; - Dave doesn’t eliminate claims outright. Instead, it keeps a tally of the number of times each claim has failed to win its group. When a claim has failed enough times to ensure censorship cannot be blamed, it is eliminated;
- If at least 1 week has elapsed, and if there is a single surviving claim, then this claim wins the dispute. Otherwise, repeat from item 2.
In the following sections, we’ll go into more details of each piece.
Match
A match progresses as follows: the blockchain guides the two competing claims through a binary search that progressively bisects the computation to pinpoint the earliest disputed state transition. Then, by verifying this single state transition (i.e., executing a step), the blockchain identifies the dishonest claim.
At each turn in a match, a validator defending a claim is expected to act with the goal of refuting its opponent. Ultimately, these actions — bisect and step — require submitting a transaction to the blockchain. There are different reasons for which a player might fail to submit bisect or step actions — Sybils may refuse to take actions, or honest participants may be censored. In these situations, we introduce a timeout mechanism that causes the unresponsive claim to forfeit the match.
Recall, however, that there’s a one-week censorship assumption. PRT uses a clock like the ones used in chess matches, which allows for amortizing the cost of censorship over all actions taken throughout a match. The idea is simple: give both claims an initial time budget of 1 week plus the needed time to take all moves (2 hour), and whenever one side is expected to act, keep its clock ticking. Once one of the claims exhausts their time budget, it forfeits the match by timeout. In this setup, it would be safe to eliminate losing claims, since everyone had enough time to have their say. However, considering the optimal delay strategy for the adversary, this makes disputes take (1 week + 2 hours) * log2 Sybils, which can still be too long.
Dave uses a similar idea. However, instead of a time budget of 1 week + 2 hours, it sets a much lower value of 8 hours (a grace period) plus the 2 hours to take all moves. (In the paper, we detail why 8 hours minimizes delays.)
Under this shorter budget, eliminating a claim immediately after a timeout would be unsafe, as it might be due to censorship. However, there’s an upper bound on how many matches a claim can lose due to censorship: 1 week / 8 hours, totalling a maximum of 21 lost matches. After 21 losses, it is safe to eliminate a claim, since the only possible explanation is a Sybil repeatedly running down its clock on purpose.
This mechanism is known as the hitpoint (HP) mechanic: every claim starts with 21 HP and loses one HP per timeout. The hero can never lose due to hitpoint loss, because the adversary can, through censorship, force at most 20 timeouts. After the adversary has fired all its shots and left the hero with 1 HP, the adversary will continue to lose its Sybils — mostly due to friendly fire, and ultimately at hands of the hero.
Matchmaking
The final piece of the algorithm is Dave’s matchmaking rule, which is at its heart. After each round, all surviving claims are repartitioned into new groups. Dave’s goal during matchmaking is to ensure that claims are pitted against opponents with similar HP, to the best extent possible.
The process is straightforward. Dave first sorts all claims by decreasing HP, and then consumes them in order, forming groups of G claims each. (Naturally, the last group may have fewer than G claims — and should a claim find itself alone in this last group, it is assumed to have won the group.) Without this matchmaking rule, Dave’s liveness would be worse than PRT’s.
Putting everything together, we show an example with four Sybils, and group size G = 2, showing how Sybils are grouped, demoted (i.e. lose hitpoints), and eventually eliminated.
Results
In the paper, we prove that the number of rounds grows logarithmically with the number of Sybils, plus a linear factor on the number of HP (i.e., O(HP + log Sybils)). To validate this theoretical result, we further created a program that exhaustively explores the adversary’s decision tree and identifies all maximum delay strategies.
Next, we analyze Dave with respect to liveness, security, and decentralization under a one-week censorship assumption and an eight-hour grace period (meaning 21 HP). While increasing the group size G can further improve liveness, it also raises the hero’s resource expenditures, which weakens security. Fortunately, a small group size of G = 4 adequately fulfills liveness. Therefore, the following discussion uses G = 4.
We show the settlement times in the table below, which indicates the total delay in days. We also propose a variant of our algorithm (described in Subsection 7.1 of the paper) that replaces the discrete HP mechanic with a continuous tally, to be studied in a future work. This variant could reduce the round duration by about half, thereby significantly improving liveness.
| N | Delay (standard) | Delay (continuous) |
|---|---|---|
| 2^{4} | 21.75 days | 12.08 days |
| 2^{8} | 27.00 days | 15.00 days |
| 2^{12} | 30.00 days | 16.67 days |
| 2^{16} | 33.00 days | 18.33 days |
| 2^{20} | 35.25 days | 19.58 days |
| 2^{24} | 38.25 days | 21.25 days |
| 2^{28} | 40.50 days | 22.50 days |
| 2^{32} | 42.75 days | 23.75 days |
This represents a significant improvement over PRT in terms of liveness. Next, we discuss why Dave’s security and decentralization are as strong as those of PRT.
Remember that decentralization demands that anyone is free (and can afford) to be the hero, and security requires that even a singleton hero can defeat an adversary backed by a nation-state.
The first threat to both security and decentralization comes from hardware requirements. In Dave, the peak transient computational power is independent of the number of Sybils — it remains constant. This means that, from a hardware perspective, Dave is secure (a Sybil attack cannot overwhelm the hero’s compute capacity) and decentralized (the minimum hardware remains affordable).
The next threat comes from gas expenditure and bond requirements. We proved that the number of rounds in Dave grows only logarithmically with the number of Sybils. This gives the hero an exponential resource advantage over the adversary, ensuring that even a lone validator can afford to engage in a dispute against a nation-state. As we showed in the TL;DR, a 1 million ether attack requires the hero to spend only 7 ETH. Dave is, as such, secure.
In practice, no realistic investment can drain a singleton hero’s funds — at worst, an adversary can only cause delays. This is in contrast with fully parallel algorithms like BoLD, where a well-funded or well-equipped adversary can win. We believe that a modest cost to liveness is preferable to a security vulnerability. This is perhaps the main reason we expect there will be no large-scale Sybil attacks in Dave: the adversary will never win, and delays grow logarithmically with the size of the investment that is ultimately lost.
This exponential advantage effectively decouples bond price from security, enabling bonds to be safely set low so anyone can act as the hero. Even a system with no bonds is secure. Ultimately, bonds in Dave serve as a mechanism to refund the winner for resources it spent in the defense of the honest claim, and perhaps as an added incentive for acting as the hero. Either way, a mispriced bond does not compromise security. By our best estimations, we suggest a bond of 3 ether. Thus, Dave maintains a high degree of decentralization.
Conclusion
We’ve shown a new fraud-proof algorithm that effectively balances decentralization, security, and liveness.
The barriers to entry, both in terms of bonds and in terms of hardware requirements, are constant and very low. This allows anyone to participate (decentralization). The quantity of resources necessary to mount an attack is exponential both on the delay it manages to cause and on the resources needed to overcome it. This makes it impractical to defeat the honest claim (security). Finally, a new strategy for amortizing censorship over the entire dispute enables punishing unresponsiveness without risking security or introducing large delays. In practice, no dispute will take longer than 2–5 weeks to complete (liveness).
Thus Dave triumphed over the Sybils with a laptop and a small collateral. Dave had no supercomputer on his hands.
(1 Samuel 17:50)
Afterword
The Dave algorithm has had the support of a remarkable group of people. I extend my deepest gratitude to:
- Augusto Teixeira and Diego Nehab, co-authors of the Dave paper.
- Pedro Argento, Stephen Chen and Guilherme Dantas, my co-conspirators in implementing the fraud proof system.
- Felipe Argento, Eduardo Barthel, João Garcia, and Milton Jonathan, for their insightful feedback and thorough review.
- Donnoh for his gracious involvement in reviewing our work.
I also extend my gratitude to Cartesi for funding the research and for providing the environment where the development could take place. We invite the reader to join us on our Discord, where we continuously engage in public research and debate these topics constantly.
