A look ahead to Tenderbake

We’re working on changing the Tezos consensus algorithm from the current Emmy⁺ algorithm, to a new algorithm called Tenderbake. We’d like to discuss this development, and explain why we’re considering it, and what advantages it will bring.

Tenderbake and Emmy⁺ belong to different algorithm families:

• Emmy⁺ is a Nakamoto style algorithm, whereas
• Tenderbake is a classical BFT-style algorithm.

So moving to Tenderbake would be a significant development on the Tezos network.

We made every effort to keep this blog post self-contained, but just in case, you might also find this glossary of the technical terms useful!

Why Tenderbake?

Tenderbake has quick, deterministic finality

From the point of view of the user, Tenderbake’s killer feature, relative to Emmy⁺, is that it offers deterministic finality: a block that has just been appended to the chain of some node is known to be final once it has two additional blocks on top of it, regardless of network latency.

Tenderbake is also fast, in the sense that it has a small (quick) time to finality: under typical good network conditions, and making a standard assumption of an attacker (“byzantine”) stake of at most 33% — meaning that at most 1/3 of the network is trying to undermine correct behaviour:

• in Tenderbake, one would expect to wait less than 1 minute for a block to be considered final, whereas
• in Emmy⁺, one would expect to wait at least 6 minutes.

How this estimate is made will become clearer below, when we introduce the notion of round duration.

We now expand on some of these claims:

Probabilistic finality (Nakamoto style)

Blockchains are decentralized, so consensus must likewise be decentralized. So suppose there exist blocks \(b\), \(b_1\), and \(b_2\) such that some participants on the blockchain’s network believe that \(b_1\) immediately follows \(b\), whereas others believe that \(b_2\) immediately follows \(b\): there is no central authority to enforce consensus on which participants are “right” and which are “wrong”, and we say the blockchain is forked, or in a forked state.

In Emmy⁺, like in all Nakamoto-style consensus algorithms, forks can have arbitrary length. However, forked states become exponentially unstable and tend to collapse down to a single branch (assuming decent bounds on network latency).

When a fork collapses to a single branch, we say that its blocks have reached finality. So, we say that Emmy⁺ has probabilistic finality because forks of arbitrary length are possible but they collapse with probability that increases suitably rapidly with fork length.

Deterministic finality (classical BFT-style)

In Tenderbake, forks are impossible. Or to put it slightly differently: forks collapse down to finality after just two blocks, always and regardless of network latency. This is deterministic finality. How this is achieved, is the topic of this post.

We need two blocks because:

1. The head of the blockchain is a candidate block to be agreed upon, and
2. its parent is a block whose non-consensus operations have been agreed, but the consensus operations might still change (on rare occasions).

Tenderbake is safe under asynchrony

From the point of view of a security analyst, Tenderbake has an advantage over Emmy⁺: no fork is possible, regardless of network delays, even during an asynchronous period.

Let’s explain. Our network model assumes partial synchrony, which splits time into two kinds of periods:

• During a synchronous period, there’s a global bound on the delivery delay for any network message.
  This is (hopefully) the usual state of affairs. Messages are delivered promptly (for a certain global value of “promptly”).
• During an asynchronous period, network performance may be degraded: but, every asynchronous period is finite.
  This is (hopefully) an exceptional state of affairs.

This is a realistic scenario because in the real world,

• networks work …
• … until they don’t, and then action is taken to fix the problem and service is restored in finite time.

So it is important for a consensus algorithm to

• function efficiently during synchrony, and just as important to
• (perhaps degrade but then) recover gracefully from asynchrony.

So back to our security analyst: Tenderbake guarantees that even if the network degrades during an asynchronous period, once synchrony is restored our blockchain will just pick up where it left off. Nakamoto-style consensus does not have this guarantee, and may emerge from an asynchronous period having developed long forks.

Nakamoto is “live”, classical BFT is “safe”.

As is so often the case in consensus, design boils down to making trade-offs: given that some asynchronous periods will eventually occur, do we prefer to be “live” or “safe” during them?

Nakamoto-style consensus algorithms favour being live: blocks are always produced, even in an asynchronous period. Classical BFT-style algorithms favour being safe: production of blocks pauses during an asynchronous period.

Our network model when designing Tenderbake assumes that any period of asynchrony is finite — we assume that somebody is going to rush to fix the broken cable, protect against the DoS attack, and/or bring the server back online. So it makes sense to be safe and (essentially) just wait for the network to come back online.

From Tendermint to Tenderbake: a journey

Tendermint

The starting point of our work was Tendermint, one of the first classical BFT-like blockchain algorithms.

Tenderbake is ‘just’ a version of Tendermint adapted for the Tezos blockchain, but the adjustments required are substantive, as we discuss below. In summary:

• Tenderbake is tailored to match the Tezos architecture by using only communication primitives and network assumptions which Tezos supports.
• In particular, Tenderbake makes weaker network assumptions than Tendermint, at the price of adding the extra assumption that participants have loosely synchronized clocks¹ — which is fine, because Tezos uses them.

The Tezos architecture

When we adapted Tendermint consensus to the Tezos architecture to arrive at Tenderbake, we had to account for the following structural features of Tezos:

1. Tezos’ self-amending feature means there is a separation between

   • the shell, which handles low-level communication, and
   • the economic protocol, which actually does the blockchain stuff and which can be updated by a Tezos amendment.

   The Tezos shell is for our purposes immutable, so our Tenderbake implementation has to fit into the more easily-updated economic protocol. In particular, we can use only communication primitives supported by the Tezos shell.

2. Furthermore, Tezos distinguishes between

   • a node, which is on the peer-to-peer network and whose job is to manage communication with other nodes and the validation and the storage of blocks, and
   • a baker, who produces blocks and communicates with just one node.

   We recall that bakers hold delegates’ keys and therefore for safety they are sandboxed — not directly exposed to the peer-to-peer network. So nodes manage communication and shield bakers from network attack, and bakers hold secrets and bake blocks into the blockchain. This arrangement affects what network assumptions we can make.

So, treating these points in turn:

1. Tendermint uses three types of consensus messages: proposals, prevotes, and precommits. We must map these to the following available shell communication primitives:

   • an operation; and
   • a block, which consists of
     • some block contents which is a list of operations, and
     • a block header which contains a hash of the block contents (for efficiency and as a checksum for data integrity).⁴

   We choose as follows:

   • Tenderbake maps Tendermint proposals to the native Tezos action of proposing Tezos blocks, and
   • Tenderbake maps Tendermint prevotes and precommits to Tezos operations.⁵

2. Bakers are semi-isolated from the network for their own safety, as discussed above, so Tenderbake must weaken the network assumptions of Tendermint³ because those assumptions are too strong to be guaranteed by the Tezos peer-to-peer layer.

   Tendermint assumes reliable broadcast: if a correct validator receives a message then all correct validators receive it. Notably, this requires that messages may be delayed, but messages may not be lost, during an asynchronous period.

   Tenderbake does not assume communication is reliable. Messages sent during an asynchronous period might never arrive. In fact, Tenderbake is designed to work without any additional assumption except partial synchrony. The technical jargon is: it assumes a best-effort broadcast primitive. Best-effort broadcast means that if a correct validator sends a message during a synchronous period, then all correct (non-byzantine) validators receive it. Best-effort broadcast is the broadcast primitive implicit in the definition of partial synchrony above.

The Tenderbake consensus algorithm in brief

Levels

Some terminology:

• The level of a block is the number of blocks since the genesis block, where the genesis block is at level 0.⁷
• The fundamental unit of identity in Tezos is a cryptographic key. A delegate is then a cryptographic key whose owner can participate in the consensus algorithm and in the governance process by virtue of registering (the public part of) their key on the chain, holding at least one roll (= 8,000 tez), and having been active recently.

Tenderbake is executed for each new block level by validators, which are delegates selected at random based on their stake,⁸ in the same way as endorsers are selected in Emmy⁺.

The validators’ task is to agree on which block to add next. In Tendermint, this process is

• started by each validator emitting a proposal message, which is just an abstract message in the algorithm proposing a block, and
• continued by validators voting on which proposal to accept, by a voting mechanism which we will describe in more details shortly; what matters for now is that voting takes place so voting messages must be communicated.

Tenderbake has to choose a concrete representation for this process. The natural way to propose a block is for a validator to use the native Tezos proposal mechanism to actually propose its preferred block as the next block to add to the next level in the Tezos blockchain. Validators can then vote on the proposed blocks by communicating their votes across the Tezos network as Tezos operations.⁹

So schematically, Tenderbake acts as follows:

1. a validator injects a candidate block (representing a proposal) and consensus operations (representing votes) into the node to which it is attached, which then
2. diffuses those blocks and consensus operations to other nodes of the network, and thus
3. communicates them to the validators attached to those nodes,
4. to carry out voting on which block to accept.

We now consider how the voting process works, in more detail.

Levels are composed of rounds

For each level, Tenderbake proceeds in rounds. Each round represents an attempt by the validators to agree on some block for the current level.

Each round has an associated duration. Round durations are set to increase so that for any possible message delay and/or asynchronous period (when the network may be slow or unreliable), there is a round that is longer.

Each round has three phases:

1. a block proposal phase;
2. a preendorsement voting phase, and
3. an endorsement voting phase.

In more detail:

1. In the block proposal phase, one of the validators is designated as the round’s proposer. The proposer’s task is to propose a candidate block (more on how this is chosen in a moment).
2. In the preendorsement phase, validators send a supporting vote (a preendorsement) on the candidate block’s contents. So, this is a vote in support of the non-consensus operations¹⁰ that it contains.
   Concretely, a preendorsement is a Tezos operation containing a tuple \((x,bc,r)\) with intended semantics
     “I, validator \(x\), hereby endorse block contents \(bc\) for round \(r\)“.
3. In the endorsement phase, provided validators have observed a quorum¹¹ of preendorsements for the block contents, validators send a confirmation vote (an endorsement) for the contents of the candidate block and for the preendorsement quorum.
   Concretely, an endorsement has the intended semantics
     “I, validator \(x\), hereby affirm to have observed a quorum of preendorsemeents for block contents \(bc\) at round \(r\)“.

First round vs. subsequent rounds

In the first round, the proposer is free to propose some block contents taken from its node’s mempool — this being a pool of pending operations that the node has accumulated, but which have not yet been baked into a block on the blockchain. In subsequent rounds, the proposer must propose the contents of the block candidate from the previous round, provided a quorum of preendorsements was observed for the block contents proposed in the previous round; otherwise, the proposer is free to choose from its node’s mempool, as for the first round.

If a validator observes an endorsement quorum at its current round for that round’s candidate block, then the validator considers that agreement has been reached on the block candidate’s contents for level \(\ell\),¹² and the validator can move to level \(\ell+1\). Each block candidate at level \(\ell+1\) will have to include the endorsement quorums of level \(\ell\), as a proof that agreement was indeed reached at level \(\ell\).¹³

If a validator does not observe an endorsement quorum at its current round for that round’s candidate block, then the validator considers that agreement has not been reached, and the validator loops back into a next round. This may be caused by:

• a byzantine proposer which does not make any proposal, or proposes two candidate blocks, or
• network delays: (pre)endorsements are sent but just don’t arrive in time, so that reaching a quorum times out.

A final round

Eventually there will be a round with

• a correct (non-byzantine) proposer who proposes precisely one candidate block as required, and
• the round is long enough so that any asynchronous periods have passed and network messages arrive in time, so that
• a quorum is observed and a candidate block for that round is agreed upon,¹⁵

and our loop terminates with consensus.¹⁴

How long does this all take?

Assuming good network conditions, validators will agree on a block after just one round, so that each level lasts one round. Also, finality is in two blocks, so that finality is achieved after two levels = two blocks.¹⁶ Thus, assuming good network conditions, the estimated time for block finality is one minute at most.

On first experiments on a private testnet for Tenderbake, the duration of the first round was set to 15s, so we confirmed that this one-minute estimate is experimentally accurate.

Why do we need (pre)endorsements?

Tenderbake has two voting phases: preendorsements and endorsements. Why vote twice?

These algorithms are genuinely subtle, and this particular design is typical of classical BFT-style consensus algorithms, going back for example to the seminal 1984 DLS (Dwork-Lynch-Stockmeyer) paper. We offer intuition as to why having two phases can be helpful, which — to be clear — is not intended as a definitive explanation:

Intuitively, having two phases helps to ensure agreement and progress even if the network gets partitioned or participants crash.

Suppose we had only one voting phase (so no preendorsements). Then either we allow validators to change their vote in later rounds, or we don’t:

• If we allow validators to change vote in later rounds…
  … then suppose only one validator \(v\) sees an endorsement quorum and decides on some block \(b\), but then it crashes. The other validators are not aware of \(v\)‘s decision, so they may later vote on a different block. Thus, the agreement property may be broken.
• If we don’t allow validators to change vote in later rounds…
  … then suppose the proposer for a round is Byzantine and it proposes two blocks \(b\) and \(b'\); then some validators vote on \(b\), and some vote on \(b'\), and neither \(b\) nor \(b'\) gathers a quorum of votes. Then there will be no agreement, because validators have to stick with the votes forever. Thus, the progress property is broken.

This is solved by using two voting phases. Indeed, with two voting phases, participants only endorse a block once they are confident that a preendorsement quorum already exists for it. This adds stability: a fragmented network might delay consensus, but it cannot enable a fragmented consensus.

To quote Pierre Chambart, answering the question “Why preendorsements?”:

Ça permet de mesurer si tu es dans la majorité, avant de prendre la décision de voter pour de vrai. (J’imagine la gueule d’une vraie élection si les gens ne voulaient voter que pour le vainqueur).

This allows you to know you’re voting with the majority, before casting your final vote. (Imagine what a real election would look like, if people only wanted to vote for the winner.)

The interested reader can also watch Ittai Abraham’s excellent tutorials:

• Byzantine fault tolerance, state machine replication and blockchains and
• The HotStuff approach to BFT (Hotstuff is a successor to Tendermint).

Where are we?

1. We proved on paper that Tenderbake is correct, in a sense made formal by Theorems 5 and 6 of that paper.
2. Then, we worked on a prototype to test our approach. This prototype took the form of a “demo” economic protocol, which includes just the consensus algorithm and a basic account system (but nothing more: e.g. no rolls, delegation, smart contracts).
3. We are now close to a fully-featured economic protocol (a modified version of Delphi using Tenderbake instead of Emmy+).
4. A private testnet is running a modified version of Delphi using Tenderbake instead of Emmy+. After fixing some observed issues, we plan to make this testnet public.

Conclusions

So that’s it! Tenderbake is classical BFT-like whereas Emmy⁺ is Nakamoto-like. Emmy⁺ has probabilistic finality making it more live but less safe, whereas Tenderbake has deterministic finality making it more safe but less live. Tenderbake also has noticeably quicker time to finality.

We’re testing it now: so watch this space.