BOLD's Building Blocks

History Commitments

The BOLD protocol, like other implementations of challenge protocols on optimistic rollups, needs a representation of the Layer 2 chain's history in order to function. This history, expressed as a series of blockchain states, is used to determine whether a claim about a future state is consistent with the agreed-upon history. Such a claim, where a party asserts that they know a history that results in a given state, is known as a history commitment.

Definitions

As mentioned above, a history is a chronological series of blockchain states, beginning with an agreed-upon initial state. Each of these states can be derived deterministically from their immediate predecessors in one step of execution (see “What is a Step?” below). The history is stored as a Merkle tree root hash to save space.

For example, a history of eight states can be represented as the series of states $\{S_0,S_1,...,S_7\}$, where $S_0$ is an initial state that is accepted by all parties.

When a history contains the state reached at the end of execution, it is known as a complete history and the final state is called the terminal state.

What is a Step?

When a BOLD protocol validator emulates the execution of some transactions in a batch, a virtual machine takes the initial state and repeatedly applies a state transition function until all transactions have been completed. Each of these applications of the state transition function is referred to as a step.

When an assertion about the final state is challenged, the dispute is narrowed down (using bisection) to a single step, which can be seen as an atomic portion of the history about which the claimant and challenger disagree. Each step must therefore be small enough to allow for easy verification.

It may be tempting to imagine each step as a single virtual machine instruction. However, such a solution is not practical, due to the extremely high cost of computing a new hash of the state with every single instruction.

Instead, the BOLD protocol uses what is known as a multi-level challenge, which uses several levels of granularity to describe different, “nested” steps, with every higher-level step consisting of many lower-level ones. This way, hashes only need to be recalculated with every higher-level step. When a challenge is narrowed down to one such step, however, the bisection process repeats with the lower-level steps contained within the higher-level step, until the instruction-level step in dispute is finally isolated.

The BOLD protocol uses three such levels of steps, which are:

• Block challenges: Each step represents one block on Arbitrum

• Big-step challenges: Each step consists of $2^{20}$ instructions

• One-step challenges: Each step represents one instruction

History as a Merkle Tree

We briefly touched on the fact that, on the BOLD protocol, history is represented as a Merkle root of the ordered list of states. The Merkle tree in this case is a hash of the history that allows for easy membership proofs.

Let's return to our example history, $\{S_0,S_1,...,S_7\}$. We can visualize the formation of the Merkle tree root $H_7$ as follows:

To calculate $H_7$, we hash every state $S_i$, then combine them in adjacent pairs and hash these to get four hashes, then do the same to get two, and finally repeat the process to obtain $H_7$.

This works great if our history's size is a power of two. What happens if this is not the case?

The Terminal State

It is not hard to imagine a complete history with a length that is not a convenient power of two, which would pose a problem to the Merkle tree representation mentioned above. In this case, the BOLD protocol can pad the history with copies of the terminal state to construct a conveniently sized Merkle tree of the history.

History Commitments

A history commitment is essentially an assertion that the history reaches a given state within a given amount of steps. It is represented as a pair $(n,M)$, where $n$ is the number of steps required to reach the claimed resulting state, and $M$ is the Merkle root of the history until that point. This claim may not actually be true, and it is the job of the protocol to decide between competing claims.

For example, a party could make an assertion that they know a history with 7 steps that results in a Merkle root of $H_7$. This assertion is represented by the history commitment $(7,H_7)$.

The reason that history commitments are so powerful has to do with the way Merkle trees work. If a Merkle tree is created using a good hashing algorithm, it will be collision-resistant. This means that it is computationally impossible to find two alternate histories that share the same Merkle root. Therefore, when a party publishes a history commitment on-chain, they commit to a single underlying history that cannot be repudiated.

Merkle trees also support easy proofs of membership. Even though the tree is represented by a single fixed-length hash, subtrees can be provided to prove that a particular state can be found in the history. Because the tree is collision resistant, such a membership proof is considered conclusive. This can be done without having to store the entire history on-chain.

In essence, the BOLD protocol's history commitments allow parties to make and verify claims about the results of some transaction execution, and provide a simple way to provide and store these claims without sacrificing the ability for the correct history to eventually be revealed.

Consistency Proofs

Before we can discuss how BOLD assertions are created, challenged, and verified in the form of edges, it is important to understand how a party can verify whether a given history is an initial portion, or prefix, of a longer history. This procedure, known as a proof of consistency, is a critical component of the bisection process.

How Merkle Proofs Work

Generally speaking, a Merkle proof is a way to verify that a given item $S$ is one of the items used to create some Merkle root $M$. A Merkle proof takes the form of a list of the hashes (known as subtrees) that are combined with the hash containing $S$ at each step, resulting ultimately in the root $M$.

To understand this better, let us return to our example seven-step history with the root hash $H_7$ and states $\{S_0,S_1,...,S_7\}$. A proof that $S_4$ is part of this history would have to include all the hashes highlighted in purple and green in the diagram below.

The Merkle proof is giving us the bare minimum information required to reconstruct the tree on our own. In our case, the calculation will proceed as follows:

1. Concatenate $S_4$ and $S_5$ and hash it.

2. Concatenate the result with the purple hash on the right of the diagram, and hash it.

3. Concatenate the purple hash on the left with the result and hash it.

4. Compare the result with $H_7$.

If the resulting hash is identical to $H_7$, then $S_4$ is considered to be a proven state in the history. This is because the possibility of finding the necessary hashes to combine with a non-member state $S_4^{\prime }$ to yield $H_7$ is so astronomically small as to be basically impossible.

Consistency Proofs

For the purposes of the BOLD protocol, a proof of membership is less important than a proof of consistency. Two history commitments are consistent if the shorter commitment's history is identical to the beginning portion (i.e. a prefix) of the longer commitment's history.

The process of proving two history commitments consistent is best illustrated with an example. Continuing with our seven-step example above, let's imagine that we wanted to prove that the history commitment $(4,H_4)$ represents a prefix of the history commitment $(7,H_7)$. We can break down proof this into two stages, which are:

1. Proving that $H_4$ can be formed from a given set of complete subtrees (i.e. with lengths corresponding to powers of two)

2. Proving that these subtrees can be combined to yield $H_7$

The first stage in this process is known as an expansion proof, and the second stage is referred to as the prefix proof.

Expansion Proofs

A proof of consistency begins with a party providing the root hashes of the smallest set of the history tree's complete subtrees, in addition to the prefix's history commitment. A complete subtree is a subset of the history with a length corresponding to a power of two. For example, in a consistency proof for the history commitments $(5,H_5)$ and $(7,H_7)$, we would be required to provide the root hashes $H_3$ and $n{H}_{4-5}$, complete subtrees with lengths 4 and 2 respectively. The division of the history $H_5$ into its complete subtrees is illustrated in the diagram below.

If the history commitment represents a complete tree, this step can be skipped.

The expansion proof proceeds by verifying that the subtrees can be combined to form the incomplete history tree. This process is known as expansion. Since this tree is incomplete, the smaller-height trees are combined with 0 and hashed at every step until they reach the height of a taller tree. Once the heights of two subtrees match, their root hashes can be concatenated and hashed as normal.

In our example of a consistency proof for $(5,H_5)$ and $(7,H_7)$, $H_{4-5}$ is combined and hashed with zeroes for one step before being able to be combined and hashed with the provided root hash $H_3$. If the result of this hash is the same as $H_5$, then the provided subtrees are valid for the history commitment $(5,H_5)$. See the diagram below for a visualization of the process.

Prefix Proofs

Once a history's complete subtrees are proven valid, we can proceed with proving that the smaller history is a prefix of the larger one. This process is illustrated with the diagram below:

The elements marked in green are the root hashes of the prefix's complete subtrees ($H_3$ and $H_{4-5}$), used in the expansion proof described above. To complete the prefix proof, we must also provide the elements marked in purple. These remaining complete subtrees, combined with the prefix's subtree hashes, can be used to reconstruct the root hash of the larger tree ($H_7$).

The properties of Merkle trees make it infeasible to create a proof that two distinct history commitments $(n_0,H_{n_0})$ and $(n_0,H_{n_0}^{\prime })$ are both consistent with a larger history commitment $(n_1,H_{n_1})$. This means that if a history commitment is consistent with another, the shorter commitment must be a prefix of the longer one.

BOLD Edges

In the BOLD protocol, an edge is a pair of history commitments, with the shorter commitment coming first in the pair and the longer one second. Edges can be understood as representations of portions of a history, and are considered the primary data structure used by the BOLD protocol.

Types of Edges

An edge is any pair of history commitments, $\left(\right(n_0,M_0),(n_1,M_1\left)\right)$, where $M_0$ is a prefix of $M_1$. The length of an edge is $n_1-n_0$. The first commitment is known as the start commitment, and the second one is known as the end commitment. A correct commitment is one where the final state is properly derived from the initial state via the state transition function.

In our seven-step example, an edge $\left(\right(4,H_4),(7,H_7\left)\right)$ has a length $3$. If both the start and end commitments are correct, then the edge represents a portion of the history containing the states $S_5,S_6,S_7$. Such an edge is known as a justified edge.

If, however, the start commitment is correct and the end commitment is not, then the edge is known as a deviating edge. By definition, a deviating edge must have an incorrectly-calculated transition somewhere within its range. For example, if we had a deviating edge $\left(\right(4,S_4),(7,S_7^{\prime }\left)\right)$, the start commitment's correctness indicates that the incorrect state transition must be in one of the states $S_5,S_6,S_7$.

In the case where the start commitment is incorrect, the edge is referred to as an irrelevant edge. As will become clear in the next quest, any history commitment with an irrelevant edge will necessarily have a deviating edge preceding it.

Conclusion

Edges form the fundamental building blocks of the BOLD protocol's challenge resolution process. In the next quest, we will see how different parties use edges to represent competing claims about the history, and use the challenge protocol to resolve that dispute. The properties of Merkle trees used in creating history commitments and their benefits for ensuring trustless collaboration to confirm the correct edge will also be discussed.