Tenderbake's Baker as a State Machine

This post focuses on Tenderbake's baker and presents the automata underlying its implementation. This work results from a collaboration between Functori, Nomadic Labs, and Paris-Saclay University.

Introduction

We assume that the reader is familiar with practical Byzantine Fault Tolerant (PBFT) protocols and the Tezos blockchain. We recall below some of the most important notions to ease reading the rest of the post.

Nodes and blocks producers (called bakers) are currently implemented as separate binaries in the Tezos blockchain. Compared to Emmy's baker (the previous Tezos consensus protocol's baker), Tenderbake's baker is notoriously more elaborate. In particular, it is now responsible for the endorsing activity that allows finalizing blocks.

A brief digression on Tenderbake

Blockchain levels are made of rounds (starting from round 0), each of which comprises three successive (virtual) phases: a proposal phase where one of the bakers proposes a new block, followed by a preendorsement and then an endorsement voting phase. A quorum of votes must be observed on the proposed block at the end of each voting step. A baker considers that a quorum is reached for some proposal if it receives more than two-thirds of the bakers' votes. Remember that bakers' votes are weighted by their respective stakes.

In an ideal situation: when a consensus is reached for a proposal at some level (i.e., endorsement quorum is observed), each participant adds the proposed block locally to its blockchain, and a new instance of the algorithm is started for the next level.

This ideal situation may go wrong for many reasons in practice. For instance, messages (proposals or (pre-)endorsements) could be lost or delayed, and some bakers could be desynchronized or offline. Consequently, participants could only reach a consensus after some rounds in some situations.

A brief digression on Tezos architecture

Before digging into more details about the baker, let's introduce some high level (somehow simplistic) concepts about the Tezos node's architecture:

The Tezos blockchain is built on a peer-to-peer network in which peers, called nodes, are interconnected and communicate by message passing. Nodes implement the core algorithms and data structures of the blockchain. They are composed of:

• A Peer-to-peer (P2P) layer: runs a gossip protocol to communicate and exchange blockchains (complete or just head blocks) with other nodes;
• A distributed database (DDB): a data structure and a set of workers that are responsible for fetching data from and sending data to peers;
• Validators: a set of workers that use the rules of the economic protocol to check/validate blocks and operations;
• The Protocol: defines the rules to follow for consensus, transactions, and amendments parts. Ithaca 2 is an example of such a protocol, and Tenderbake defines the new rules of the consensus part;
• The Mempool: is a specific data structure for fetching, classifying, and propagating pending operations.

Nodes do not communicate plain messages directly, but only their hash values. When a node receives a hash, it checks if its value is already stored in its DDB. If not, the DDB is mandated to fetch the associated value from its neighborhood.

Plugging PBFT in the Tezos architecture

The Tezos blockchain has been designed to be agnostic to the consensus algorithm used to produce/validate blocks. Consequently, plugging a PBFT protocol like Tenderbake into Tezos' codebase is no piece of cake.

As sketched in the architecture below, bakers are not directly visible to the network. They only communicate through the nodes they are connected to (which we refer to as the node of the baker). Each baker communicates with its node via a Remote Procedure Call (RPC) mechanism. RPCs are used to get current heads and votes, inject proposals and (pre)endorsements, and fetch the operations to include in blocks. An internal loop is responsible for quorums monitoring and notifications.

This modular architecture raises several challenges in practice:

• First, while a baker is voting on a specific blockchain block, the Mempool can receive a new proposal and decide to change its head. In this case, resynchronization is required for the baker and the worker to vote or get a quorum on the current mempool's head;
• Second, since Tezos is designed to be consensus-agnostic, the rules of the Tenderbake algorithm are abstract, so it is crucial to make sure that the Mempool has access to all necessary information needed to choose the best blockchain at each time;
• Last, bakers combine timestamp information stored in the blocks and their current clock to know how long before a round timeout is triggered. Since each baker has its clock, this can lead to clock drift, to which the protocol must be resistant.

Tenderbake's baker automata

The role of a baker is to produce proposals and vote for the head blocks of the blockchain stored in its node's Mempool. For that:

• it gets the first two blocks of the blockchain from the node,
• it follows Tenderbake's rules to decide whether to vote (preendorse or endorse) on the current head.

A baker is also composed of a worker running in parallel, whose role consists in getting the votes from the Mempool (via RPCs) and checking for potential quorums.

The automaton below highlights the different states of the baker's worker loop:

• No proposal (or NP): the baker didn't receive a proposal for its current round yet;
• Collecting Preendorsements (or CP): the baker is collecting preendorsements for the proposal of the current round;
• Collecting Endorsements (or CE): the baker is collecting endorsements for the proposal of the current round.

To ease the presentation, we break down the role of the baker into two, as follows:

• Observer role: models the way the baker/worker's state evolves when receiving external events like timeouts, new proposals, new voting quorums, as is outlined by the transitions in the figure;
• Actor role: enunciates the conditions for which the baker
  • processes a new proposal and possibly accepts it to be for the current round,
  • possibly preendorses and endorses that proposal,
  • proposes a block with fresh content or with an already proposed payload.

The baker as an observer of the consensus

First, let's assume that a baker's binary runs without any baking tz key. In this case, the software will mainly act as an observer for received proposals and votes.

As said above, the baker keeps track of the two latest blocks of the blockchain because these two blocks may still change:

• The head block's content could completely change from one round to another as long as no consensus (endorsement quorum) is reached for it;
• The predecessor block got an endorsement quorum. But there might be other blocks at the same level which got endorsement quorums at different rounds. In this case, non-consensus operations are finalized: they cannot change anymore. However, the block's hash can still evolve, as consensus operations and the round might change.

Recall that bakers have a mechanism to determine their current rounds based on their clocks and on timestamps stored in the latest blocks of the blockchain. When a round's duration is over, the Timeout transitions (in red) allow bringing the automaton into the NP state.

Similarly, suppose a new proposal for the current baker's round is received from the node. The baker then starts collecting/counting preendorsements for it (green transitions). In particular, this means two things w.r.t. the baker's clock:

• The current design doesn't allow observing quorums for proposals that are in the past;
• Heads that might be in the future are not considered immediately.

Should a preendrosement quorum be observed, the automaton moves to the CE state (yellow transition) to monitor endorsement quorums (blue transition). As an improvement, we could also detect endorsement quorums while collecting preendorsements. Indeed, a baker might observe an endorsement quorum but no preendrosement quorum (which may not happen if preendorsements are lost).

The baker as an active actor in the consensus

Let's now assume that the baker's binary (tezos-baker-012-Psithaca binary for Ithaca 2 protocol) is run with a baking tz key that owns some rights. In this case, the software should observe the consensus and inject proposals or votes when opportunities arise. We will keep the presentation short and informal in this post. One can find more details in Formally Documenting Tenderbake paper. We assume the baker is at some level L and round R, denoted (L, R).

To operate correctly, the baker maintains some additional information about what has been observed/done so far, including the following:

• ELECTED = (block, eq) | null: when the baker observes a consensus for the first time at some level, the corresponding block and endorsement quorum eq are recorded;
• LOCKED = block | null: we keep track of the latest block for which the baker injected an endorsement (after observing a preendorsement quorum) at the current level if any;
• PQC = (pq, rnd, payload) | null: we remember the highest round rnd at which a preendorsement quorum pq was observed on a block. The payload part is the non-consensus operations of that block.

Proposing a block

When conditions are met, proposing a block is done as a post-action of the Timeout transition. That is:

• Case 1: the current round's duration is over. If the baker is the proposer of the next round of the same level, it can inject a block for (L, R+1). This block:
  • has a fresh payload if PQC = null (which implies that LOCKED = null);
  • reuses the payload in PQC, as sufficiently many participants preendorsed it (and probably endorsed it if they saw the preendorsement quorum). In this case, the re-proposed block should include the preendorsement quorum pq.
• Case 2: a proposal can be injected for the next level. Contrary to the observer mode, an active baker also keeps track of baking rights at level L+1, as soon as the ELECTED variable is set at level L. In this case, the baker maintains two timeouts to participate in consensus at level L and to timely inject a proposal at level L+1. Such a proposal is fresh and should contain the endorsement quorum and the hash of the elected proposal in ELECTED.

Processing a new proposal

A new proposal is supposed to have a better fitness than the previous one since fitness checks are done on the node. If the proposal's predecessor is different, the baker should also adapt its state and resynchronize its round. As said above, the proposals that seem to be in the future (w.r.t. baker's clock & state) and possibly reconsidered on time. Otherwise, the baker extracts some information from the block and continues updating its local variables accordingly:

• If the proposal's level is higher, it means that the baker is late. It should reset some parts of its state (including all variables listed above) and move to that level;
• If the proposal contains a preendorsement quorum, it means that the block is a re-proposal. So, the baker should likely update its PQC variable if the quorum in the proposal has a higher round.

Finally, proposals for the current baker's round are preendorsed if some additional conditions are met (see below). The worker also starts monitoring votes for it.

Preendorsing a proposal

The current baker preendorses a received proposal for (L, R) if:

• R is the current round of the baker (i.e., the proposal is neither outdated nor in the future);
• The baker didn't preendorse (a different block) at (L, R), and;
  • it never endorsed a block with a different payload at level L. Said otherwise: the variable LOCKED is either null or contains a block with the same payload as the current proposal, or
  • the received proposal has a preendorsement quorum whose round is greater than the LOCKED block's round.

Endorsing a proposal

The current baker endorses a received proposal for (L, R) if:

• R is the current round of the baker;
• The baker didn't endorse (a different block) at (L, R);
• The baker observed a preendorsement quorum for this proposal at (L, R).

Alongside endorsements injection, the LOCKED and PQC variables are updated accordingly.

Protection against double baking and voting

The baker's state is regularly saved to disk to be able to restart in a consistent and safe configuration in case of a crash. The watermarks mechanism, provided by hardware wallets or implemented with files on disk, also protects against double baking or voting risks.

Conclusion

This post gave a brief overview of the Tenderbake consensus protocol through its baker part. A more detailed and technical version of this work has been published at FMBC workshop as Formally Documenting Tenderbake. We refer the reader to this paper: Tenderbake -- A Solution to Dynamic Repeated Consensus for Blockchains and to this blog post: Tenderbake has been injected for more details about Tenderbake.