# Optimistic Sync: How many heads?

[`get_head`]: https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/fork-choice.md#get_head
[`filter_block_tree`]: https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/fork-choice.md#filter_block_tree

*Assumed prior reading: https://hackmd.io/Ic7VpkY3SkKGgYLg2p9pMg*

## Introducing the optimistic and verified trees

The *optimistic tree* is the block-tree of the beacon chain, assuming that any yet-to-be verified `ExecutionPayload` is valid.

The *verified tree* is the block-tree of the chain, assuming that any yet-to-be-verified `ExecutionPaylod` is invalid. (Another name for this might be the "pessimistic tree".)

About these two trees, we know:

- The verified tree is *always* a subset of the optimistic tree.
- If the optimistic head is present in the verified tree, the optimistic and verified heads are equal.

> Note: Neither the optimistic or verfied trees contain blocks with *invalid* payloads. As soon as an `ExecutionPayload` in the optimstic tree is found to be invalid, the containing block is pruned from the tree.

## The canonical heads

With these two trees, how does one determine the canonical heads of these trees? I.e., how does "fork choice" apply to these trees?

The most obvious head is the *optimistic head*. It is simply the result of running the [`get_head`][] function on the optimistic tree.

It follows that the *verified head* would be achieved in an equivalent way; run [`get_head`][] on the verified tree. However, there are some nuances when computing this head that are detailed next.

### Verified head nuances

The verified head becomes a more complicated when we consider how to handle votes from validators who have latest attestations in the *optimistic* tree (e.g., if their execution client is more synced than the local one). Such votes *may* or *may not* weigh into choosing the verified head. This leads to two variations of the verified head:

- The *strict verified head*: ignore any votes upon the optimistic tree.
- The *naive verified head*: allows votes on optimistic blocks to weigh upon their verified ancestors.

The word "naive" is used for the second definition, since a node using this head is trusting that other validators only attest to a block if its `ExecutionPayload` is valid.

### The tree-headed chain

There are now three different heads to be gleaned from the optimistic and verified tree:

* Optimistic head
* Strict verified head
* Naive verified head

About these heads, we know:

- If the optimistic head and strict verified head are equal, then so is the naive verified head.

### Considering implementation complexity

This isn't just an academic pursuit, we need optimistic sync for the merge and that's happening *soon*. So, let us consider implementation complexity.

Before we get started, lets just assume that a consensus client cannot handle the scenario where a finalized `ExecutionPayload` is invalid. If that happens, the client shuts down and social consensus is required. We will use this assumption through-out this entire document.

All the major consensus clients use the "proto-array" implementation of the beacon chain fork choice specification. So, this section will base itself in that implementation.

Finding the optimistic head in proto-array is simple, it requires very little modification. Once the ability to prune blocks with invalid `ExecutionPayloads` is implemented, it's just business-as-usual.

The strict verified head requires a little more thought. Intuitively, it might seem easy to modify a single proto-array instance to track the optimistic and strict verified heads, however things quickly get complex. Consider that the optimistic and verified trees may have arbitrarily different justified checkpoints; this means tracking two sets of balances and two sets of best/current justified checkpoints. It seems that two different proto-array instances are required for the optimistic and verified trees.

However, maintaining a verified tree which lags behind block import comes with its own practical difficulties. Once a block is verified by an execution client, the application must go and add all the parents which also became verified to proto-array (in reverse order). There's also all the attestations to the verified blocks to consider, they would need to be cached somewhere.

If we know anything at this point, it's that tracking the strict verified head is going to be *painful*. The naive verified head is slightly better, since we don't need to cache attestations. However, we still need to do retrospective application of blocks to ensure that only justified checkpoints from verified blocks are considered.

### Is there an easier way?

It's clear that tracking the optimistic head is easy, but either variant of the verified head is going to involve extensive changes.

Luckily, there is a *fourth* head that is easier to implement:

- The *verified ancestor head* (it could also be called the "verified optimistic ancestor head")

This head is simply the first ancestor (if any) of the optimistic head with a verified `ExecutionPayload`. For un-finalized (or recently finalized) heads, this means finding the verified ancestor head in proto-array means a simple, in-memory, reverse iteration from the optimistic head until the first block is found such that `is_verified(block.execution_payload)`. In the scenario where the verifed ancestor head is deeply finalized, a client may have to track it independently or default to some other value (e.g., the genesis/weak-subjectivity state).

The verified ancestor head differs from the naive verified head in the following ways:

- It uses the same set of balances as the optimistic head.
- It is not subject to the same [`filter_block_tree`][] conditions.

## Summary

It's clear that there are two heads that are easy to track within current consensus implementations:

- The *optimistic head*
- The *verified ancestor head*

And there are at least two other heads which need extensive changes to track:

- The *strict verified head*
- The *naive verified head*

With an aggressive merge timeline and low tolerance for bugs, it's desirable to figure out how to make consensus clients work with just the optimistic and VOA heads. To do this, we must enumerate the components which use the head and assess their safety under an optimistic or verified ancestor head. [Optimistic Sync: Which is the right head for the job?](/xsk9_feiQ3SIYz2yRa1z7Q) does just this.