Bond Management

[ben-chain]

Bond Management for multi-round disputes

Background and Goals

One important goal for an optimistic dispute game is to provide incentive compatibility -- that is, the ability for an honest player to at least break even on gas while successfully challenging/securing the chain. This generally requires that the initial proposer posts a bond, which can be redeemed by the proposer if there are no challenges, or by a successful (honest) challenger. An additional, perhaps obvious, goal, is that the bond be finite and bounded to a reasonable size.

In the single-round context, this was fairly straightforward to implement -- because there is only one valid challenge for a given assertion, it's easy to require that the proposal is bonded, and that the challenger gets paid out. Here's where the OVM v1 did this.

Problem Statement

In a multi-round context, the problem is a little harder to solve. The core issue is that disputes no longer have a single "honest" outcome; depending on how the malicious proposer interacts/responds to a challenge, there may be multiple outcomes. This is especially true for dispute games in which the players do not commit to the full execution trace (i.e. post a merkle root of all execution steps) up front.

Assume that an initial (malicious) proposer has posted a finite bond which is enough to cover the gas of an initial challenge. While there is only one "correct" challenge that an honest party should post, there are infinitely many possible responses. What we need to do is make sure that only the person who made the "correct" challenge is paid out. Otherwise, an attacker could challenge their own malicious proposal many times and make it unprofitable for the honest challenger.

Intuitions for Solution

These are not very precisely stated, but I think we can safely make the following claims about a bond management system which solves the above goals. Consider an malicious proposer M who has made a malicious claim, and is adopting a strategy whereby they challenge themself via a puppet address P, in attempt to steal their own bond away from an honest challenger H.

1. Honest challengers must combat dishonest challengers

Imagine that M does not respond to either P or H for the remainder of the challenge period. It should be clear that the L1 contract has no way to decide who to give the bond to. Therefore, it must be the case that H should be able to play out the remainder of the game against the puppet to prove they are making the wrong challenge.

In the case where P challenges an earlier point in the execution than H, I think the strategy that H should follow is identical to what they would do if defending on behalf of M. If P challenges M at a later point, then this is not the case, and H needs a way to challenge M on an earlier point than what M and P are claiming to agree upon.

2. Interactions must each have a bond

Due to to 1. in combination with wanting a finite bond size, it must be the case that each interaction on-chain has a bond, as opposed to one big bond at the top. Otherwise, the attacker could simply create bond_size/interaction_gas_gost + 1 puppet challenges to make H lose money.

[tynes]

Is it possible to come up with an interface for this such that the implementation details can hide behind it and the existing contracts can interact with the interface and a mock implementation such that the implementation can be added in later?

There is currently no logic that restricts batch submission by msg.sender

https://github.com/ethereum-optimism/optimistic-specs/blob/main/specs/rollup-node.md#reading-l1-inputs

[norswap]

Some thoughts:

• The defender bond should cover more than the cost of the challenge. Submitting a wrong root has a lot of band consequences, it should really hurt to do it.
• A solution to "stealing your own bond" problem is to make the bond higher than the reward for the challenger. If the bond is large enough (which it should be), this is not a problem.
• The problem of diluting challengers with many sockpuppets is real.

Outline of a what I think a solution could look like:

1. Challengers assert an alternative output root.
2. Challengers are bonded — this bond must be big enough (with some margin/multiplier to account for varying gas cost, etc) to cover the cost of a whole fault proof for the defender. This prevents challengers from cheesing the defender. The defender can claim the bond if the challenge fails.
3. We must "de-duplicate" fault proofs to avoid sybill attacks. If multiple challenger attempt the same fault proof (same asserted output root), only the first to post each step in the binary search should get credit (must verify that these steps are the same, or they become different fault proofs). This ensures that the malicious sequencer can't dilute the reward with sockpuppets (though he can still "steal" the reward, which remember should be smaller than the bond, so still making a painful loss).
   • We could get fancier here and "front-load" the credit that the initial submitter gets, since he's taking a bigger risk to start the challenge and open himself to be slashed when nobody else has made the challenge yet.
   • Everything is MEV and this is too. In this case, the hard problem is the malicious sequencer might not challenge itself until someone else attempts too, in which case he can frontrun the challenge and have the honest challenger incur the cost of challenge step for which he will not credit... Using flashbots solves this, but I'm understanbly hesitant to rely on flashbots existing and operating as it currently does for security.
4. At the end of a challenge:
   • If it was successful through a final step, the reward (part of the bond) is split amongst credited challengers from step 3.
   • If it was successful through the defender not answering some challenges → this is the difficult scenario, see below.
   • If it fails, the bond of the challengers go to the defender. In this case, each challenger must be accounted separately, because they might have divergent execution. So their bond is forfeit when the final step is taken and they lose, or when their challenge expires.

Handling the defender timing out against many challenger (many of which might be sock puppets)

I think your insight is spot on:

Therefore, it must be the case that H should be able to play out the remainder of the game against the puppet to prove they are making the wrong challenge.

So honest actors should be able to challenge malicious challengers in the same way they challenge malicious defenders.

One possible way this works is that each challenge opens a 7 day window in which the challenge can itself be challenged. When a wrong sequencer output root times out, we have to wait for every challenger's window to expire, and then we distribute the reward amongst the challengers that haven't been challenged (normally these should all have asserted the same output).

Honest challengers are paid for these "recursive challenges" by their ability to recover the malicious challenger's bond. This process is identical to the top level one: the credit system still helps avoid sock puppets and if the malicious challenger stops responding, we again need to wait 7 days to challenge the challengers of the malicous challenge (lol).

One difficult thing here is what do we replace challenged output roots by? I guess we expect other sequencers to pick up the slack? We can't pick the output asserted by the challenger because (a) it might not have been subjected to a proper challenge itself and (b) it is not sufficiently bonded to install as the optimistically correct root. If a challenge succeeds via defender timeout then there isn't even a logical output root to pick in the first place.

More thoughts:

In the case where P challenges an earlier point in the execution than H, I think the strategy that H should follow is identical to what they would do if defending on behalf of M.

Agreed.

If P challenges M at a later point, then this is not the case, and H needs a way to challenge M on an earlier point than what M and P are claiming to agree upon.

Ah, that's a though one. I did not carefully think through the implications of a defender being challenged on multiple different output roots when writing the above.

I think the earliest successful challenge should take the bond though. Since the success of this challenge implies that P was dishonest not to challenge that in the first place. The problem is that the defender can hang on the honest challenge but speedrun the dishonest one. In this case we should enforce waiting on the resolution of all oldest challenges.

Due to to 1. in combination with wanting a finite bond size, it must be the case that each interaction on-chain has a bond, as opposed to one big bond at the top. Otherwise, the attacker could simply create bond_size/interaction_gas_gost + 1 puppet challenges to make H lose money.

I think the credit system above solves this by only rewarding the first challenger that pushes a proof forward in a given direction.

Alright... That's what I have. Is there any flaw in the above? The frontrunning flaw worries me slightly since it's a way to make it too costly for honest actors to challenge malicious challenges.