This article describes in detail a Latest Message Driven (LMD) GHOST fork choice rule that is efficient to verify. Vitalik Buterin’s original post on this topic can be found here. Some background on the LMD GHOST rule is assumed, and can be found in this tutorial.

Motivation for Bitwise LMD GHOST

Latest Message Driven (LMD) fork choices are the go-to choice for creating Correct-By-Construction Casper fork choices that have provably nice properties. The gist of these LMD rules is that we only consider the information contained in each validator’s latest message that a block claims to know about. LMD GHOST is a natural choice in LMD fork choice rules, and we get some very nice properties from this combination.

However, there is a large computational cost to running LMD GHOST on the usual block tree. Bitwise LMD GHOST presents a viable solution to this problem, by reducing the complexity to O(V*log(h)), where V is the number of validators, and h is the depth of the block.

Structure of this article:

1. Efficiently running GHOST on a Binary Tree
2. Bitwise-Tree: Converting the usual block tree into a binary tree
3. LMD GHOST in the Bitwise-Tree (aka Bitwise LMD GHOST)

GHOST on a Binary Tree

Let us look at the specific case of executing GHOST on a binary tree of blocks. The GHOST rule would have to make a choice between at most 2 children, for any particular block. Although not very interesting on it’s own, this will enable us to efficiently verify whether a given block is valid under the GHOST rule.

Consider the binary block tree as illustrated. Let us verify the validity of block C3. First, we compute some additional data: agreeing[] and at[] arrays. agreeing[h] stores the number of votes consistent with block C3 upto height h in C3’s branch. at[h] stores the number of votes that support exactly the block at height h in C3’s branch. Note that agreeing[]is sorted in decreasing order.

Validity Check

Now we run the following steps (we’ll refer to this as the Validity Check):

• Binary search in agreeing[] for maximum height h where at least half of the validators agree. Verify that 2 * agreeing[h+1] ≥ (agreeing[h]-at[h])
• Repeat for maximum height where at least a quarter of the validators agree, and verify the inequality. Next, repeat for maximum height where at least 1/8 of the validators agree, and so on. Continue until you reach the head.

Note that the Validity Check will take O(log(h)) for each binary search, and O(log(h)) for the loop to reach the head, leading to total complexity O(log²(h)).

A closer look at the inequality: consider a block L with children M and N. The block whose validity is under question is N. Applying the GHOST rule on block L means that we choose the child whose subtree has better score. From the figure, we can see that:

• The support for N’s subtree is agreeing[h+1]
• The support for M’s subtree is the support for L’s subtree minus (the support for exactly L and the support for N’s subtree), which is agreeing[h]-at[h]-agreeing[h+1].

So, for N to be chosen in the GHOST execution, we need agreeing[h+1] ≥ agreeing[h]-at[h]-agreeing[h+1], i.e., 2 * agreeing[h+1] ≥ (agreeing[h]-at[h]).

Therefore, saying that N is the result of GHOST on the block tree is equivalent to saying that 2 * agreeing[h+1] ≥ (agreeing[h]-at[h]) for every height h in the branch of N. Note that the assumption that each block has a maximum of two children is a necessary condition for this statement.

Proof of Correctness

Now let us look at why the passing the Validity Check is necessary and sufficient for any block N to satisfy 2 * agreeing[h+1] ≥ (agreeing[h]-at[h]) for every height h it’s branch:

1. Necessary: Since 2 * agreeing[h+1] ≥ (agreeing[h]-at[h]) for all heights in the branch of N, it is satisfied at all heights that the Validity Check verifies this inequality.
2. Sufficient: Assume that the Validity Check passes, but for some height h in the block tree of N, 2 * agreeing[h+1] < (agreeing[h]-at[h]). Let x be the number of validators under consideration when the Validity Check crosses height h. Now, since the inequality is not satisfied here, h is obviously the maximum height where at least x/2 validators support the block at that height. But this implies that this height h would have been encountered as the maximum height where at least x/2 validators agree, and the inequality would have been checked, leading to a contradiction. Hence, a passed Validity Check implies that the inequality is satisfied for all heights h in the relevant branch.

Now that we have an efficient way of running GHOST on binary trees, let us come up with a way to first convert our usual block tree into a binary tree structure, and then look at how we can efficiently compute additional data such as agreeing[] and at[].

Bitwise-Tree

The bitwise-tree is a way to represent blocks from the usual block tree (where number of children are unbounded) in the form of a binary tree. We will maintain all the child-parent hierarchies, although they may not be expressed as an ancestor relation instead of a direct child-parent relation. Let us look at the construction (the figure describes it much better 😜):

1. For the root block B in the original block tree, add a corresponding block in the bitwise-tree and mark all the children of B in the original tree as the descendants of B in the virtual tree.
2. For every block V in the bitwise-tree, create “virtual” children blocks V0 and V1. Mark all descendants of V that have hash with prefix 0 as descendants of V0, and all descendants of V that have hash with prefix 1 as descendants of V1. If the hash of a certain block from the original block tree is reached, then replace that virtual block with the actual block. and repeat from step 1 assuming this block as the root.

GHOST in the Bitwise-Tree

The result of running GHOST on blocks in the bitwise-tree can be different from those on the original block tree. For example, the figure describes a situation where GHOST steps down differently (shown in red) in the two cases. However, this is not a major source of concern, since any attacks that would have orchestrated this difference could have exploited GHOST in the usual block tree by creating a block D with children C2 and C3.

Height in the Bitwise-Tree

The height of a block in the bitwise-tree is 256*original_height. Then, for any given validator and block B under consideration, the “virtual agreement height” (up to which the branch of the validator’s latest endorsed block agrees with the block’s branch) will be 256*actual_shared_height + number_of_common_bits, where:

• actual_shared_height is the actual shared height in the original block tree
• number_of_common_bits is the number of bits in the common prefix of the first different block in the branch of B and branch of the validator’s latest endorsed block.

Note that in order to run the Validity Check on some particular block in the bitwise-tree, we don’t actually need to construct the tree; we only need to compute agreeing[] and at[] mappings for each virtual height in the branch of the block. In the next section, we will see how to construct these mappings efficiently.

LMD GHOST in the Bitwise-Tree (aka Bitwise LMD GHOST)

Now that we know a way to run GHOST efficiently on binary trees, and have a way to represent our blocks in a binary tree, we want to run LMD GHOST on the blocks in our bitwise-tree (which we will call Bitwise LMD GHOST).

We will need the agreeing[] and at[] maps for blocks in the bitwise-tree. Let us look at the construction for these maps.

We introduce 2 additional maps in the state that each block must contain:

• For each validator, it’s last virtual agreement height. (the agrees_to[] map)
• For each validator, it’s last virtual at height. (the last_at[] map)

We will maintain a mapping of virtual height to number of validators having that height as last agreement height (let’s call this the last_agreeing[] map). After receiving a new block, we will just makes updates to last_agreeing[] from it’s previous block. The range of last_agreeing[] is going to be the depth of the block, say h.

We will be using a segment tree to store the last_agreeing[] map. Quick information about segment trees for an array of n elements:

• Answers queries about the sum (or some other range operation) over some range of the original array.
• Construction in O(h*log(h)), query in O(log(h)), update in O(log(h)).

Note that agreeing[x] = last_agreeing[x] + … + last_agreeing[h], i.e., agreeing[x] is a range sum query on the last_agreeing[] array. We won’t actually be storing a separate agreeing[] array.

Upon receiving a new block, for each validator with a new latest vote, we need to make 2 updates to last_agreeing[]: subtract that validator’s weight from it’s previous last agreement height, and add that validator’s weight to it’s new last agreement height. Assuming that there are V validators, and all of them might have new latest votes, this process will take O(V*log(h)).

Now we will construct at[]. For each validator v, check if last_at[v] is equal to it’s last virtual agreement height. If yes, then add the weight of the validator to at[last_at[v]]. This process will take O(V).

Modifications to the Validity Check

We are now in a position to run the Validity Check on blocks in the virtual tree, using the agreeing[] and at[] data that we computed. Each access of agreeing[] takes O(log(h)), and the binary search part requires O(log(h)) accesses, and there are O(log(h)) executions of the binary search by the time we reach the head. So the complexity of Validity Check becomes O(log³(h)).

However, we can use a clever trick to combine the agreeing[]accesses and the binary search process to take O(log(h)). Then, the complexity of the Validity Check returns to O(log²(h)).

Therefore, the overall complexity of verifying Bitwise LMD GHOST compliance on a block (i.e., computing the necessary data and running the Validity Check) is O(V*log(h))+O(log²(h)).