Delay Attacks on Rollups

Yeah, the collaterals and slashing solution is well known! It’s currently being employed by other optimistic solutions like Arbitrum, and it addresses many issues with making the algorithms of Canetti et al. and Feige at al. permissionless, related to Sybil attacks. However, described by Ed Felten here, it has issues of its own.

The collaterals and slashing solution is orthogonal to Cartesi’s solution. In fact, a protocol using Cartesi’s proposed algorithm should also include collaterals and slashing. Rather, Cartesi’s algorithm is a new fraud-proof primitive.

First, the paper starts with the “Refereed Games” primitive of Canetti et al., where two players can prove to a computationally limited referee that theirs is the correct result of a computation. Then, using this primitive, one can extend the protocol to allow a set of N players to fight over the result of a computation. This way, a single honest player in the set of N players can enforce the correct result of a computation.

However, this does not scale well over N; both the number of referee interactions and the computational effort spent by honest players grows linearly, and so does the overall dispute times. Adding collaterals and slashing is a way to disincentivize attackers. (And winning parties must at least recoup the resources they spent, otherwise a well-funded attacker may exhaust an honest player’s resources.) However, this introduces attacks that can delay liveness of roughly N challenge periods at a cost to the attacker of N collaterals.

Moreover, this has centralization concerns. The choice of collateral has to balance between restricting the number of people that can participate in disputes and how feasible delay attacks are. If it’s set to zero, then anyone can participate, but one could delay finality forever. If it’s set very high, very few would be able to participate, but delay attacks would be very expensive.

The preliminary Cartesi paper introduces the “Permissionless Refereed Tournaments” primitive, which addresses the limitations mentioned above. The main contributions are the concept of a computation commitment — a Merkle tree where the leaves are the intermediary Merkle hashes of the state of a computation — and sorting validators into tournament brackets.

With this primitive, rather than dispute effort growing linearly with the number of players, it grows logarithmically. An attacker that wants to delay finality by X, would have to spend exp(X) collaterals.

And this is just on delay attacks. There are other interesting features of Cartesi’s algorithm besides that.

1 Like