From Blocktree to Blockchain and Block Finalisation - Ethereum Yellow Paper Walkthrough (7/7)

Posted Jun 3, 2020

By Lucas Saldanha

11 min read

Welcome to the last post of the Ethereum Yellow Paper Walkthrough series! It took way longer than I expected when I started this almost two years ago, but here we are at the finish line.

In this final post, we’ll cover sections 10 and 11 of the Yellow Paper. We’ll look at how a tree of candidate blocks becomes a single canonical chain (section 10) and what block finalisation actually involves: validating ommers, paying rewards, the proof-of-work check and the difficulty adjustment (section 11).

If you missed any of the previous posts, here is the full series:

(DISCLAIMER: this post is based on the Byzantium version of the Yellow Paper)

From a tree of blocks to a single chain

One mental shortcut we’ve used throughout the series is to imagine Ethereum as a single chain of blocks, each linking back to its parent. The reality on the network is a bit messier than that. At any given time, miners around the world are working on different blocks at the same height. Some of these blocks will be accepted, others won’t, and the network needs a rule to converge on a single shared history.

That is what section 10 of the Yellow Paper is about. The data structure that lives across the network is a tree of valid blocks rooted at the genesis block. The protocol picks a single branch from that tree and calls it the canonical chain.

Block validity

Before a block can be part of the tree at all, it must be valid. The Yellow Paper lists the conditions a valid block has to satisfy:

The block header is well-formed (every field is the right type and within range).
The proof-of-work is valid (we’ll look at this in a moment).
The parent hash refers to a known parent in the tree.
The timestamp is strictly greater than the parent’s timestamp.
The gas used is no greater than the gas limit.
The gas limit is within bounds relative to the parent (the protocol allows the gas limit to drift by at most 1/1024 of the parent’s gas limit per block).
The transactions are valid (every transaction follows the intrinsic rules we discussed in post 4).
The state root, transaction root and receipts root in the header match the tries computed by replaying the transactions.
The ommer list is valid (we’ll talk about ommers in section 11).

If a block fails any one of these checks, it isn’t part of the tree.

Picking the canonical chain

So we have a tree of valid blocks. How do we pick one branch? The Yellow Paper is precise about it: the canonical chain is the path from the genesis to the head block of the branch with the greatest total difficulty.

Total difficulty is the sum of the difficulty field of every block from the genesis to that block. It is basically a proxy for the total amount of work that went into building that branch. Because mining a block is probabilistic and expensive, accumulating the most work is a strong signal that this is the branch the network has effectively voted for.

A few things follow from this rule:

Forks happen all the time. Two miners can find a valid block at the same height almost simultaneously. For a brief moment, both branches exist in the tree.
The network converges. Whichever branch is extended next ends up with higher total difficulty, and nodes that were on the other branch reorganise onto it.
Reorgs are part of life. A block that looked canonical can stop being canonical later if a heavier branch shows up. That is why wallets, exchanges and dapps wait for a few confirmations before considering a transaction final.

Ommers (or “uncles”)

Section 10 also introduces an idea that is fairly unique to Ethereum: ommer blocks (commonly called uncles). An ommer is a valid block whose parent is in the canonical chain, but which is not on the canonical chain itself. In other words, an ommer is a sibling of a canonical block.

In Bitcoin, sibling blocks (“stale blocks”) are just discarded. Ethereum took a different approach: a canonical block can include references to some recent ommers in its header, and both the canonical block’s miner and the ommer’s miner receive a (smaller) reward.

Why? Two reasons:

Small miners are at a disadvantage. In a network with non-zero latency, a small miner can produce a valid block that just gets out-raced by a better-connected miner’s block. Ommer rewards make sure that work isn’t entirely wasted, which helps reduce some of the centralising pressure on hash power.
More work counted, more security. Including ommers means the network counts more total work toward the canonical history.

The catch is that an ommer can only be referenced for a limited window (up to 6 blocks deep) and a block can include at most 2 ommers.

Block finalisation

Section 11 of the Yellow Paper defines the process the protocol follows to “finalise” a candidate block. In practice, this means computing the final state after the block and checking that everything adds up.

The Yellow Paper splits finalisation into four steps:

Validate the ommers.
Apply the transactions.
Apply the block reward (and ommer rewards).
Verify the state root and the proof-of-work.

Let’s go through each one.

Ommer validation

For each ommer included in the block:

The ommer must be a valid block header on its own (well-formed, valid PoW, etc.).
It must share an ancestor with the current block within the last 6 blocks.
It must not have been included as an ommer already in any of those 6 blocks.

These rules prevent a miner from reusing the same ommer to milk extra rewards, or from including arbitrary unrelated blocks.

Applying transactions

This is exactly the process we covered in posts 3 and 4. You take the transactions from the block body and apply them in order to the parent state, which gives you the intermediate state. Along the way you accumulate transaction receipts (which include the cumulative gas used, the logs and the bloom filter). At the end, the transactions trie and the receipts trie are computed, and their root hashes can be compared to transactionsRoot and receiptsRoot in the header.

The Yellow Paper writes this using the function $\Pi$ we first saw in post 1: applying a block to a state means applying each of its transactions in sequence.

Block reward and ommer rewards

After all transactions have been applied, the protocol pays out rewards:

The block reward is given to the beneficiary account named in the header. At the Byzantium fork, this was 3 ETH (the reward has changed across forks: it was originally 5 ETH and was later reduced again to 2 ETH at Constantinople).
Each ommer’s miner receives a reward that decreases the further back the ommer was relative to the current block, following:
\[\text{ommer reward} = \frac{(8 + U_n - B_n)}{8} \times R\]
where $U_n$ is the ommer’s block number, $B_n$ is the current block’s number, and $R$ is the block reward. Since the ommer is older than the current block, $U_n - B_n$ goes from $-1$ down to $-6$, so the numerator runs from $7$ down to $2$. The bigger the gap, the smaller the reward.
The current block’s miner gets an additional 1/32 of the block reward for each ommer included.

If the beneficiary or any ommer beneficiary is a non-existent account, the reward simply creates it (with the reward as its initial balance).

Verifying the state root and the proof-of-work

After applying all transactions and paying rewards, the protocol computes the root of the world state trie and compares it to the stateRoot field in the block header. If they don’t match, the block is invalid.

Last but not least, the protocol checks the proof-of-work, which is the main mechanism securing the chain.

The proof-of-work problem

The Yellow Paper specifies the proof-of-work problem using the Ethash algorithm. Ethash is what miners actually compute on their GPUs, and the Yellow Paper specifies it carefully because every client needs to compute the same answer.

In broad strokes, Ethash is built so that:

Verification is cheap. A node receiving a block can check the PoW quickly.
Mining is memory-hard. It is designed to make ASIC mining harder by requiring large amounts of memory (a “DAG” of several gigabytes, growing slowly with the chain).
Mining can’t be cached. Each attempt needs fresh data, so there is no shortcut for someone with a lot of hash power but limited memory bandwidth.

The PoW check itself comes down to two fields: the block header contains a nonce and a mixHash. The miner has tried billions of different nonces until they found one where the Ethash hash function output is below a target derived from the block’s difficulty. Other nodes recompute the same function and check it.

I won’t walk through the Ethash algorithm in detail. That could easily be its own post. The high level mental model is something like: “the miner searches for a nonce such that H(header_without_nonce, nonce) is below a threshold, and the threshold is tighter for higher-difficulty blocks”. For our purposes, that’s all we need.

Difficulty adjustment

The Yellow Paper also specifies how the difficulty of each new block is calculated, based on the parent’s difficulty, the time gap between the new block and its parent, and the “difficulty bomb”.

The intuition is simple:

If blocks are coming too fast (timestamp gap small), difficulty goes up.
If blocks are coming too slow (timestamp gap large), difficulty goes down.
The target average block time is around 13 to 15 seconds.

On top of this, there is the famous difficulty bomb, a term that grows exponentially with the block number. The idea is to slowly make mining harder and harder over time, eventually pushing the network towards proof-of-stake. The bomb has been delayed by network upgrades a few times already (most recently in the Muir Glacier fork at the start of this year) and will probably be delayed again before the planned move to PoS.

If you want to look at the formulas, equations 41 to 47 in section 11.3 of the Byzantium Yellow Paper define the full difficulty calculation.

The end of the series

That’s it! Across seven posts, we’ve gone from “Ethereum is a transaction-based state machine” to “here is how a block finalises and joins the canonical chain”. My hope is that even if you forget the specific equations, you walk away with a useful mental model of how the protocol fits together:

Ethereum is a state machine. Transactions change the state, and blocks group transactions.
The state is structured into tries (world state, account storage, transactions, receipts). The roots of these tries live in the block header.
Transactions cost gas. Gas exists so the network can charge for compute and prevent abuse.
Each transaction is validated and then applied. It either succeeds, fails or reverts, and the result is captured in a receipt.
Some transactions create contracts, others call into existing accounts. Both are formalised by the Yellow Paper as functions on the world state.
At the bottom of the stack sits the EVM, a deterministic stack machine that runs contract bytecode.
At the top, the network maintains a tree of valid blocks and picks the heaviest chain as canonical, while paying rewards to miners and ommer producers.

A lot has changed since I started this series, and a lot is still in flight. The move to proof-of-stake is on the roadmap, fee market changes like EIP-1559 are being debated, and honestly the Yellow Paper itself is starting to lag a bit behind the implementation. Even with all of that, the parts of the protocol we covered here are still the parts I find myself going back to when I am trying to understand a new EIP or read another client’s source code.

If you’ve followed along, thank you. Writing these has been one of my favourite ways of forcing myself to actually understand the protocol I work on for a living. If you spot anything inaccurate, anything that needs an update, or just have feedback, please leave a comment down below.

It’s been a long ride. Catch you in the next one!

References

Programming, Ethereum Yellow Paper

ethereum blockchain

This post is licensed under CC BY 4.0 by the author.