# The BOLD Protocol

# Delay Attacks
The BOLD protocol was conceived as a way to effectively minimize the damage caused by delay attacks. These attacks affect all optimistic rollups, and occur when malicious actors submit invalid challenges in an attempt to delay the confirmation of honest transactions on the Layer 1 blockchain.

## The Problem with Delay Attacks
At first glance, delay attacks do not appear to be as critical as some other types of attacks. After all, a delay attack does not completely prevent an honest transaction from being confirmed, only delaying it. Such an attack also does not attempt to change the results or order of the transactions themselves.

However, a delay attack can still inflict serious damage on an optimistic rollup protocol. Recall that optimistic protocols enable users to submit assertions about the outcome of a transaction, and others to submit challenges to that assertion, a dispute which would eventually be resolved in favor of the honest party.

With older protocols, attackers could submit as many challenges (including identical assertions) as they could pay for with gas fees. This would require honest parties to engage in an unknown amount of challenges, with no way of knowing how much time or gas it will take for their transaction to be confirmed.

Delay attackers are also able to arrange a situation where they deliberately lose challenges in the longest time possible, increasing the confirmation delay even longer. With such major delay and costs to confirm a transaction, an honest party may decide that promoting its honest assertion is not worth their while. If there are no other honest parties, or if all have withdrawn, it becomes possible for the attacker's incorrect assertion to prevail. Regardless, delay attacks increase costs and frustrations for rollup users and can do serious damage to a protocol's usability as compared to its competitors.

## Previous Arbitrum Solutions
Before the creation of the BOLD protocol, several incarnations of the Arbitrum challenge protocol attempted to minimize the damage caused by delay attacks, with some success. They also had some serious drawbacks, as we shall see.

### 2018 Arbitrum Protocol
The original Arbitrum challenge protocol allowed any party to submit a challenge to an assertion. The asserter would engage in one-vs-one resolution with every one of its challengers, bisecting the rival assertions to isolate the step in dispute. The defender of the assertion would then have to submit a one-step proof of their assertion for that step. If the asserter was able to defend themselves against every challenger, their assertion would be confirmed. If, however, even one of the challenges was successful, the assertion would be reverted.

Under this system, a delay attacker is able to submit as many incorrect assertions as they desire, so long as they have enough funds to do so. This can result in a situation where the attacker submits the same invalid assertion over and over again, draining the honest challenger's time and money.

### Production Arbitrum Protocol (2020)
The challenge protocol used commerically by Arbitrum is a little more resistant to delay attacks. In this iteration, rival assertions are conceptualized as different branches, forked from the same chain. The party that creates a new assertion branch submits a stake representing its support for that assertion. Challenger can then create rival "sibling" branches and add their stakes to them, and other parties can choose to add their stakes to any one of a group of sibling branches to show support for that assertion.

The resolution process proceeds with challenges being initiated between stakers on sibling branches. Whenever a staker loses a challenge, their stake is removed from whichever branch it may be on. After a certain period of time, any branch without stakers is removed together with its descendants and only the honest branch remains.

Unlike in the previous iteration of Arbitrum, rival branches can only be created within a set period of time after the creation of the oldest child. This ensures that an attacker cannot keep creating incorrect assertions indefinitely, a possibility under the old protocol. However, a delay attack can still be effective if organized in a slightly different way.

The worst case scenario delay attack would involve a collaboration between $N$ malicious actors. $N-1$ of these stake on the correct branch, together with the honest staker, and ones stakes on an incorrect branch. Then, under the worst-case assumption that the dishonest parties will always have priority in executing their challenges, the incorrectly-staked party will engage in $N-1$ challenges against their co-conspirators. These stakers will deliberately lose these challenges in the maximum time possible.

## One-vs-One Challenges
Both the 2018 and 2020 Arbitrum challenge protocols resolve competing claims with a system known as *one-vs-one challenges*. This means that a given party can only resolve one challenge with one rival party at any given time. The length of time required to confirm a correct assertion therefore depends on the amount of dishonest stakers or assertions involved in the delay attack. This makes it possible to delay the confirmation for an unbounded amount of time, making a delay attack extremely effective.

In the example above, $N-1$ challenge periods must pass before the honest party can finally eliminate the incorrect branch and confirm its assertion. This is the case even if the protocol were to ensure that each challenge would be finished in a bounded period of time, since only one challenge can be run at any given time. Thus, having a fixed upper bound for an assertion to be confirmed must involve the ability to run all the challenges simultaneously.

### Permissioned Validation
Because of this risk of delay attacks, Arbitrum has had to limit the pool of validators to a permissioned group trusted by the foundation. Assuming that these validators are honest and well-selected, the risk of delay attacks would be mitigated. However, this can only be seen as a temporary solution as it directly contradicts the permissionless and decentralized ethos central to the demand for blockchain technology. As a solution, Arbitrum has developed the BOLD protocol.

# The BOLD Protocol
The Bounded Liquidity Delay (a.k.a. BOLD) challenge protocol is Arbitrum's solution to the problem of delay attacks on optimistic rollups. It works by representing competing claims about execution as rival edges rather than competing challengers or stakes, narrowing down the point of contention with bisection, and finally executing a one-step proof to determine the honest edge. This procedure ensures that a correct edge will be confirmed (i.e. accepted as valid) within a set time limit, and allows for anyone to serve as a validator.

## All-vs-All Challenges
The BOLD challenge protocol opens up the possibility for what's known as *all-vs-all challenges*. Unlike previous versions of the Arbitrum challenge protocol, which require the execution of one challenge at a time, BOLD allows all challenges to be resolved simultaneously. These challenges are run between competing assertions, known as *rival edges*.

### Edges as Claims
A BOLD edge can be understood as a portion of a claim about the history. As mentioned before, an edge can be justified - that is, representing part of a correct history - or deviating, meaning that it starts off with a correct state and deviates somewhere in the middle.

The process of determining whether an edge is justified or deviating is a critical component of how the BOLD protocol works. The protocol does this by deciding between distinct edges that have the same start commitments and lengths. Since these edges must have different end commitments, they are considered *rival edges* and only one of them can be justified.

In the course of the protocol's validation process, rival edges begin as *level-zero edges*, which are edges that encompass a complete history. Every such edge is accompanied by a stake to disincentivize the submission of invalid challenges. If two or more parties submit the same history commitment as their claim, the level-zero edge of that commitment will have the combined stake of all those parties.

To isolate the point of disagreement between rival edges, it is necessary to split them until the dispute is narrowed down to an easily-verifiable single step. This process is known as *bisection*.

### Bisection
Bisection refers to the way that the BOLD protocol splits edges in half when evaluating rival assertions. Any unbisected rival edge with a length greater than one can be bisected, and bisection can be done by any party.

To do a bisection on an edge, a party provides a *midpoint history commitment*, which encompasses half of the history included in the edge. For example, if we have a level-zero edge $((0, H_0), (7, H_7))$, its midpoint history commitment will be $(3, H_3)$. The bisecting party must also provide a proof that their midpoint history commitment is consistent with the end commitment, which in our example is $(7, H_7)$. As we saw earlier, the properties of Merkle trees ensure that the bisecting party cannot create an incorrect midpoint history commitment with a proper proof.

This commitment can then be used to construct two *child edges* as the end commitment of the first edge and the start commitment of the second. Our example edge's children would therefore be $((0, H_0), (3, H_3))$ and $((3, H_3), (7, H_7))$, as shown in the diagram below.


Since the edges produced by a bisection are called children, the larger edge used to created them is known as the *parent edge*. Child edges are considered to be one level higher than their parent; in our case, the parent $((0, H_0), (7, H_7))$ is a level-zero edge, and its children would be called level-one edges.

The BOLD protocol uses bisection to narrow down the dispute between rival edges to a single step. Starting from the level-zero edge, parties repeatedly bisect the edge in contention and let the challengers select one of the two children to dispute. This edge will then be bisected and one of its children will again be selected to be challenged, and so on until an edge containing one step is reached.

### Trustless Collaboration with Consistency Proofs
In the 2020 Production version of Arbitrum, an honest staker cannot guarantee that other stakers on the honest branch would bisect that branch honestly to reach the step in dispute. This requires all parties on different branches to engage in one-vs-one challenges against each other, where only one challenge could be run at any given time. The challenges are run in sequence to ensure that, if one party successfully eliminates an invalid branch, the other parties do not waste gas challenging the staker on that branch.

For example, imagine that there are N stakers on an honest branch and 1 staker on a dishonest branch. An honest staker on the honest branch would engage in a challenge with the staker on the dishonest branch only if all the other stakers on the honest branch deliberately forfeited their challenges in a coordinated delay attack. If there are multiple honest stakers, however, only one staker has to engage in a challenge to eliminate the dishonest branch, saving the other honest stakers from having to run the challenge and waste gas. However, if challenges under this model were run as all-vs-all challenges, all honest parties would have to engage in the same challenge protocol to eliminate the invalid branch.

By contrast, the edge bisection process allows the BOLD protocol to execute many challenges simultaneously in the form of all-vs-all challenges. This is due to the fact that, because of how child edges can be proven to be consistent with the complete history, the repeated bisection process can be completed in a collaborative manner. The honest parties can thus split the costs required to confirm the correct edge, since every party can trust that the others created an honest bisection.

Since an honest party using the BOLD protocol can run challenges against all its rivals at the same, it is now possible to give a bounded time limit for the confirmation of the correct edge. Intuitively, this time limit must be related to the amount of time it takes to resolve the longest challenge the honest party engages in. It is also possible to allow for anybody to become a validator in a permissionless manner, since the risk of delay attacks by a malicious validator is significantly reduced.

## Edge Confirmation
An edge, which is essentially a claim about some execution history, is accepted as valid in a process called *confirmation*. As a result, its final state will be added to the Ethereum blockchain. At first, any party can create a level-zero edge, which represents a claim about the entire history of the transaction. Other parties can create rival level-zero edges to dispute that claim, or stake on an existing rival edge to indicate their support of that assertion. In the end, however, only one edge will be confirmed, and the others will be rejected.

An edge can be confirmed in one of three ways:

1. An edge with no rivals, known as a *presumptive edge*, can be confirmed after a certain period of time has passed.
2. An edge with rivals and children is considered confirmed when both of its children have been confirmed.
3. An edge of length one with rivals is confirmed via a one-step proof.

### Edge Timers
Every BOLD edge stores a timer that is used as part of the confirmation process, which is called the *presumptive timer*. The presumptive timer tracks the amount of time that an edge has been presumptive - that is, without rivals. This timer is used in turn to calculate the *path timer* of an edge, which is defined as the sum of the presumptive timer of the edge and the largest presumptive timer of one of its ancestors.

The path timer is not stored by the protocol, but can be calculated by getting an edge's list of ancestors. Once an edge's path timer reaches a value greater than a defined limit time $T$, the edge is considered to be confirmed. $T$ is referred to as the *challenge period*.

For example, let's imagine that a level-zero edge is created at time $0$. If no rivals were ever created, this edge's path timer would keep incrementing until it reached $T$ and the edge would be confirmed. Instead, a rival edge is created at time $2$. The first edge's path timer is therefore $2-0=2$, and the second's is $0$, since it came into existence as a rival edge.

Now suppose (for the sake of simplicity) that the first party bisects its edge into two, and no rival edges are created by the second party. In this case, the path timers of both children would be $2+t$, where $t$ is the amount of time passed since the bisection, and $2$ is the presumptive timer value of their only parent. Once this value reaches $2+t=T$, both child edges will be confirmed. As a result, their parent edge will also be confirmed, and the first party will be declared the winner of the challenge.

## Narrowing Down Challenges
In case a rival edge is created, it is necessary to bisect both rivals in a given pair to narrow down the range in dispute and possibly isolate the dispute to a single step. A subsequent child is only bisected further if that child itself has a rival. The edge that precedes the step in dispute will necessarily not have a rival, since its history is agreed upon by the challenging parties. An edge that is after the disputed step is also not subjected to bisection, as it is irrelevant. This process is best explained with an example, illustrated in the diagram below.


### Stage 1
Suppose that a dishonest party creates a deviating edge $((0, H_0), (7, H'_7))$ and an honest party creates a rival justifiable edge $((0, H_0), (7, H_7))$ within the required challenge period. Let's also suppose that the step in dispute between the two edges is the fourth step.

### Stage 2
To begin the challenge, the honest party bisects its edge to yield two edges: $((0, H_0), (3, H_3))$ and $((3, H_3), (7, H_7))$. In response, the dishonest party will bisect its edge as well, yielding $((0, H_0), (3, H_3))$ and $((3, H_3), (7, H'_7))$. Note that the first two child edges are identical for both parties. This is because the dispute only occurs on the fourth step, which is in the second child. In other words, the two parties agree that the earliest step in dispute is found between $H_3$ and $H_7$.

### Stage 3
In the second bisection, first the honest and then the dishonest party will dissect their second children to yield the justifiable edges $((3, H_3), (5, H_5))$ and $((5, H_5), (7, H_7))$, and the deviating and irrelevant edges $((3, H_3), (5, H'_5))$ and $((5, H'_5), (7, H'_7))$, respectively. In this case, the dispute takes place between the first edges, as they begin with the same history commitment and end with different ones. The irrelevant edge $((5, H'_5), (7, H'_7))$ can proceed without being challenged, as the presence of its deviating sibling will never allow their parent edge to be confirmed.

### Stage 4
Finally, the honest and dishonest parties will in turn bisect their first child edges to yield $((3, H_3), (4, H_4))$ and $((4, H_4), (5, H_5))$ for the honest party and $((3, H_3), (4, H'_4))$ and $((4, H'_4), (5, H'_5))$ for the dishonest party. At this stage, the first child edges of both parties can be put to the test with a one-step proof (see below).

In the case where there are more than two level-zero rival edges, this bisection process will be executed concurrently for every rival pair of edges.

## One-Step Proofs
Once a challenge is isolated to a dispute about a single step, the honest party's edge can be proven correct with a *one-step proof*. A one-step proof is, in theory, a proof that a single step of computation results in a particular state. The honest party will submit such a proof, whose correctness is easily and quickly validated via execution on Ethereum. The honest edge will thus be confirmed, and the dishonest one rejected.

In practice, it is impractical to define BOLD history commitments with steps corresponding to single steps of computation. Instead, BOLD uses a three-level system which was described in more detail in the previous quest. Whenever a higher-layer one-step edge is reached with bisection, the challenge process begins again with the rival higher-layer one-step edges represented as level-zero edges consisting of their expanded lower-layer steps.

This process works as follows: rival edges of with a length of one block each will have the challenge protocol proceed by creating rival edges with more granular steps of $2^{20}$ opcodes each. After bisecting to isolate the disputed step, the rival edges of length $2^{20}$ opcodes will once again be represented as rival edges with $2^{20}$ opcode steps each. Only once this final layer of edges is narrowed down to its disputed step can a proper one-step proof be provided and verified to effect confirmation.

## Bottom-Up Confirmation
Once the honest one-step edge is confirmed, the protocol will work on confirming or rejecting the parent edges until it reaches the level-zero edges. Recall that a parent edge is confirmed if both of its children have themselves been confirmed. This process ensures that only the correct level-zero edge ends up confirmed by the protocol.

The bottom-up confirmation for our previous example would proceed as shown in the following diagram, where every confirmed edge is highlighted in green. For this example, we proceed with the assumption that no other rival edges are created, and that the presumptive timers of all presumptive edges are left to tick. It is also assumed that the dishonest party will confirm its irrelevant edges in an attempt to confirm its incorrect level-zero edge.


### Stage 1
First, the correct one-step edge $((3, H_3), (4, H_4))$ is confirmed via a one-step proof, with its rival edge being rejected as a result. When the path timers for $((4, H_4), (5, H_5))$ and $((4, H'_4), (5, H'_5))$ exceed the challenge period, these edges become confirmed as well. Note that $((4, H'_4), (5, H'_5))$ is confirmed here despite being an irrelevant, and therefore incorrect, edge. This is not a problem for the protocol, as this edge's parent will always have a rejected deviating child. The confirmation of this irrelevant edge will therefore never cascade upwards as it would in the case of a justifiable edge.

### Stage 2
The protocol proceeds with the confirmation of the parent edge $((3, H_3), (5, H_5))$ due to the confirmation of both of its children. The edges $((5, H_5), (7, H_7))$ and $((5, H'_5), (7, H'_7))$ are confirmed by their timers, while the deviating edge $((3, H_3), (5, H'_5))$ is rejected because of its rejected child $((3, H_3), (4, H'_4))$.

### Stage 3
At this point, the edges $((0, H_0), (3, H_3))$ and $((3, H_3), (7, H_7))$ are confirmed due to their timer and confirmed children, respectively. The deviating edge $((3, H_3), (7, H'_7))$ is rejected.

### Stage 4
Finally, the procedure results in the confirmation of the honest party's edge $((0, H_0), (7, H_7))$ because of its confirmed children, and the rejection of the rival edge $((0, H_0), (7, H'_7))$.

### Rewards for the Honest Party
Now that the correct level-zero edge is finally confirmed, the honest party is refunded the stake it originally deposited to create the edge. The dishonest party, on the other hand, loses its stake, which is deposited into a public goods fund. The BOLD protocol also includes provisions to reimburse the honest party for the gas fees it spent in defending its assertion, the funds for which are taken from the public goods fund mentioned earlier.

# Conclusion
The BOLD protocol leverages the properties of Merkle history trees and their associated consistency proofs to enable honest parties to collaborate in confirming a justifiable edge. The procedure uses a combination of repeated bisections to find the single point of dispute, one-step proofs to resolve that dispute, and path timers to ensure that undisputed portions of the history are confirmed.

When at least one honest party follows this procedure, the BOLD protocol ensures that honest assertions will be confirmed on-chain and dishonest assertions will be rejected, while rewarding honest parties and penalizing dishonest ones. Importantly, the BOLD protocol ensures all this within a limited time bound and with support for any party to submit assertions and challenges.