The consensus algorithm#

This document provides a high-level description of Tenderbake, the Tezos proof-of-stake consensus algorithm.

History#

Before Tenderbake, there was Emmy*, a Nakamoto-style consensus consisting of a series of improvements of the one in the Tezos whitepaper.

Emmy*, like any Nakamoto-style consensus algorithm (such as Bitcoin or Ouroboros), offers probabilistic finality: forks of arbitrary length are possible but they collapse with a probability that increases rapidly with fork length.

Tenderbake instead, like any classic BFT-style consensus algorithm (such as PBFT or Tendermint), 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.

Overview#

The starting point for Tenderbake is Tendermint, the first classic-style algorithm for blockchains.

Tenderbake adapts Tendermint to the Tezos blockchain, but the adjustments required are substantive:

  • Tenderbake is tailored to match the Tezos architecture by using only communication primitives and network assumptions which Tezos supports.

  • 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 already uses them.

The design of Tenderbake and its rationale are described at length in the technical report and in a Nomadic Labs’s blog post. Here we only provide a user/developer perspective.

Tenderbake is executed for each new block level by a “committee” whose members are called validators, which are delegates selected at random based on their stake, in the same way as endorsers were selected in Emmy*. We let CONSENSUS_COMMITTEE_SIZE be the number of validator slots per level. Furthermore, we use CONSENSUS_THRESHOLD to denote two thirds of CONSENSUS_COMMITTEE_SIZE.

For each level, Tenderbake proceeds in rounds. Each round represents an attempt by the validators to agree on the content of the block for the current level, that is, on the sequence of non-consensus operations the block contains. We call this sequence the block’s payload.

Each round has an associated duration. Round durations are set to increase so that for any possible message delay, there is a round that is sufficiently long for all required messages to be exchanged. Round durations depend on protocol parameters MINIMAL_BLOCK_DELAY and DELAY_INCREMENT_PER_ROUND. These parameters specify round durations as follows:

\[\begin{split}round\_duration(0) &= minimal\_block\_delay \\ round\_duration(r+1) &= round\_duration(r) + delay\_increment\_per\_round \\ & = minimal\_block\_delay + (r + 1) * delay\_increment\_per\_round\end{split}\]

Round durations thus increase linearly with DELAY_INCREMENT_PER_ROUND.

Schematically, a round consists in the following steps:

  • a validator designated for that round injects a candidate block (representing a proposal) and consensus operations (representing votes) into the node to which it is attached, which then

  • diffuses those blocks and consensus operations to other nodes of the network, and thus

  • communicates them to the validators attached to those nodes, to carry out voting on which block to accept.

Unlike Emmy*, Tenderbake has two types of votes: before attesting a block b, a validator preattests b. Furthermore, to be able to attest, a validator must have observed a preattestation quorum, that is a set of preattestations from validators having at least CONSENSUS_THRESHOLD validator slots. Similarly, to be able to decide, a validator must have observed an attestation quorum, that is, a set of attestations from validators having at least CONSENSUS_THRESHOLD validator slots. The attestation quorum for a block b is included in a block b' on top of b, serving as a certification that b has been agreed upon. We also say that block b' confirms block b.

The validator’s whose turn is to inject a candidate block at a given round is called the proposer at that round. Proposers in Tenderbake are selected similarly to bakers in Emmy*: the proposer at round r is the validator who has the validator slot r. A proposer who has observed a preattestation quorum for a candidate block in a previous round, is required to propose a block with the same payload as the initial block. We talk about a re-proposal in this case.

Transaction and block finality#

A transaction is final as soon as the block including it has a confirmation (that is, a block on top of it). Indeed, as hinted above, a block contains the certification (that is, the attestation quorum) for the previous payload. Thanks to the attestation quorum, Tenderbake guarantees transaction finality after 1 confirmation.

It may be possible that different validators decide at different rounds, though on the same payload. The blocks at these different rounds differ precisely because they contain, in the header, as part of the block fitness, the round at which they were proposed. Among these “candidate” blocks, the block with the smallest round has the highest fitness and so it will be the one decided. Consequently, to agree on a block, that is, on both the payload and the header, Tenderbake needs one more confirmation, and thus guarantees block finality after 2 confirmations.

Time between blocks#

The time between blocks represents the difference between the timestamps of the blocks. The timestamp of a block is given by the beginning of the round at which the block has been agreed upon. Thus, the time between blocks depends on the round at which decisions are taken. For example, if the decision at the previous level was taken at round 4 and at the current level at round 2, then the current block’s delay relative to its predecessor, is \(round\_duration(4) + round\_duration(0) + round\_duration(1)\). The general case is as follows, say that the decision at the previous level is taken at round m and the decision at the current level is taken at round n, then the current block’s delay relative to its predecessor is \(round\_duration(m) + \sum_{i=0}^{n-1} round\_duration(i)\). We note that, under normal network conditions, and with active and compliant validators, decisions should be taken at round 0, meaning that the time between blocks would be \(round\_duration(0)\) seconds i.e., parameter MINIMAL_BLOCK_DELAY.

Validator selection#

Validator selection, that is, baking and attesting rights, are based on the baking power of a delegate. The baking power is a function of all tez owned by the delegate and its delegators, with staked tez weighted more than non-staked tez, and there are additional considerations such as overstaking and overdelegation; see the baking power formula.

The baking rights are determined CONSENSUS_RIGHTS_DELAY in advance, which is 2 cycles for the Quebec protocol. More precisely, at the end of cycle n and beginning of cycle n+1, the baking rights for cycle n+1+CONSENSUS_RIGHTS_DELAY=n+3 are randomly generated based on the current baking power of each delegate that meets the minimal power and own staked requirements.

Economic Incentives#

As Emmy*, Tenderbake rewards participation in consensus and punishes bad behavior. Notable changes however are as follows:

  • Fees and baking rewards go to the payload producer, the one who selected the transactions to be included in the block (and was the first to propose a block with that payload). In case of re-proposal, the payload producer might be different from the block proposer, the baker who injects the block.

  • Including extra attestations, that is, more than the minimal required to obtain a quorum, is rewarded with a bonus.

  • Attesting rewards are shared equally among all validators. Participation above a minimal threshold per cycle is however required.

  • Validators are rewarded instantaneously for baking blocks and including extra attestations, and not at the end of the cycle like in Emmy*.

  • At the end of a cycle c, the following actions happen:

    • the distribution of attesting rewards,

    • the selection of the consensus committee cycle c + CONSENSUS_RIGHTS_DELAY, based on the current active stake distribution.

Fees#

The fees associated to the transactions included in a block go to the payload producer. This is only natural given that this is the validator that selects the transactions to be included; see an in-depth blog post for further motivation.

The payload producer is usually the same delegate as the block proposer (that is, the one that signs and injects the block): that’s always true for blocks at round 0; however, in case of re-proposals this is not necessarily the case (see the algorithm description above).

Fees are allocated to the payload producer’s available balance immediately, that is, they are already reflected in the blockchain state obtained after applying the injected block.

Rewards#

There are three kinds of rewards: baking rewards, attesting rewards, and a bonus for including extra attestations.

The baking rewards are treated in the same way as fees: they go to the payload producer and are distributed immediately.

To encourage fairness and participation, the block proposer receives a bonus for the extra attestations it includes in the block. The bonus is proportional to the number of validator slots above the threshold of CONSENSUS_COMMITTEE_SIZE * 2 / 3 that the included attestations represent. The bonus is also distributed immediately.

The attesting rewards are distributed at the end of the cycle. Attesting rewards may be received even if not all of the validator’s attestations are included in the cycle’s blocks and is proportional to the validator’s active stake (in other words, to its expected number of validator slots, and not its actual number of slots). However, two conditions must be met:

  • the validator has revealed its nonces, and

  • the validator has been present during the cycle.

Not giving rewards in case of missing revelations is not new as it is adapted from Emmy*. The second condition is new. We say that a delegate is present during a cycle if the attesting power (that is, the number of validator slots at the corresponding level) of all the delegate’s attestations included during the cycle represents at least MINIMAL_PARTICIPATION_RATIO of the delegate’s expected number of validator slots for the current cycle (which is BLOCKS_PER_CYCLE * CONSENSUS_COMMITTEE_SIZE * active_stake / total_active_stake).

Regarding the concrete values for rewards, before Adaptive Issuance, we first fix the total reward per level, call it total_rewards, to 80 / blocks_per_minute tez. Assuming blocks_per_minute = 7.5, total_rewards is 10.67 tez. With Adaptive Issuance, this value changes dynamically over time but for the sake of example, we will assume that the reward value stays the same as above. We define:

  • BAKING_REWARD_FIXED_PORTION := baking_reward_ratio * total_rewards

  • bonus := (1 - baking_reward_ratio) * bonus_ratio * total_rewards is the max bonus

  • attesting_reward := (1 - baking_reward_ratio) * (1 - bonus_ratio) * total_rewards

where:

  • baking_reward_ratio to 1 / 4,

  • bonus_ratio to 1 / 3.

Thus, we obtain BAKING_REWARD_FIXED_PORTION = 2.67 tez, (maximum) bonus = 2.67 tez, and attesting_reward = 5.33 tez. The bonus per additional attestation slot is in turn bonus / (CONSENSUS_COMMITTEE_SIZE / 3) (because there are at most CONSENSUS_COMMITTEE_SIZE / 3 validator slots corresponding to the additional attestations included in a block). The rewards per attestation slot are attesting_reward / CONSENSUS_COMMITTEE_SIZE. Assuming CONSENSUS_COMMITTEE_SIZE = 7000, we obtain a bonus per slot of 2.67 / (7000 / 3) = 0.001143 tez and an attesting rewards per slot of 5.33 / 7000 = 0.000761 tez.

Let’s take an example. Say a block has round 1, is proposed by delegate B, and contains the payload from round 0 produced by delegate A. Also, B includes attestations with attesting power 5251. Then A receives the fees and 10 tez (the BAKING_REWARD_FIXED_PORTION) as a reward for producing the block’s payload. Concerning the bonus, given that CONSENSUS_COMMITTEE_SIZE = 7000, the minimum required validator slots is 4667, and there are 2333 = 7000 - 4667 additional validator slots. Therefore B receives the bonus (5251 - 4667) * 0.001143 = 0.667512 tez. (Note that B only included attestations corresponding to 584 = 5251 - 4667 additional validator slots, about a quarter of the maximum 2333 extra attestations it could have theoretically included.) Finally, consider some delegate C, whose active stake at some cycle is 1% of the total stake. Note that his expected number of validator slots for that cycle is 1/100 * BLOCKS_PER_CYCLE * CONSENSUS_COMMITTEE_SIZE = 1/100 * 10800 * 7000 = 756,000 slots. Assume also that the attesting power of C’s attestations included during that cycle has been 651,456 slots. Given that this number is bigger than the minimum required (756,000 * 2 / 3), it receives an attesting reward of 756,000 * 0.000761 = 575.316 tez for that cycle.

Slashing#

Like in Emmy*, not revealing nonces and double signing are punishable. If a validator does not reveal its nonces by the end of the cycle, it does not receive its attesting rewards. If a validator double signs, that is, it double bakes (which means signing different blocks at the same level and same round) or it double (pre)attests (which means voting on two different proposals at the same level and round), a part of the frozen deposit is slashed. The slashed amount for double baking is a fixed percentage of the frozen deposit PERCENTAGE_OF_FROZEN_DEPOSITS_SLASHED_PER_DOUBLE_BAKING. For double (pre)attestations, the formula is more complex, as it depends on the number of attestation slots that participated in the misbehavior; see Adaptive Slashing for more details. The payload producer that includes the misbehavior evidence is rewarded 1 / (GLOBAL_LIMIT_OF_STAKING_OVER_BAKING + 2) of the slashed amount; the rest of the slashed amount is burned.

If a delegate’s deposit is smaller than the slashed amount, the deposit is simply emptied.

The evidence for double signing at a given level can be collected by any accuser and included as an accusation operation in a block for a period of MAX_SLASHING_PERIOD.

As soon as a delegate is denounced for any double signing, it is immediately forbidden from both baking and attesting for at least 2 cycles.

The actual slashing and denunciation rewarding happen at the end of the last cycle of the slashing period of the misbehavior.

Note that selfish baking is not an issue in Tenderbake: say we are at round r and the validator which is proposer at round r+1 does not (pre)attest at round r in the hope that the block at round r is not agreed upon and its turn comes to propose at round r+1. Under the assumption that the correct validators have more than two thirds of the total stake, these correct validators have sufficient power for agreement to be reached, thus the lack of participation of a selfish baker does not have an impact.

Fitness#

The fitness is given by the tuple (version, level, locked_round, - predecessor_round - 1, round). The current version of the fitness is 2 (version 0 was used by Emmy, and version 1 by Emmy+ and Emmy*). The fitness encapsulates more information than in Emmy* because Tenderbake is more complex: recall that blocks at the last level only represent candidate blocks. In Emmy*, only the level mattered. But in Tenderbake, we need to, for instance, allow for new blocks at the same level to be accepted by nodes. Therefore the fitness also includes the block’s round (as the fifth component). Furthermore, we also allow to change the predecessor block when it has a smaller round. Therefore the fitness also includes the opposite of predecessor block’s round as the forth component (the predecessor is taken for technical reasons). Finally, to (partially) enforce the rule on re-proposals, the fitness also includes, as the third component, the round at which a preattestation quorum was observed by the baker, if any (this component can therefore be empty). By the way, preattestations are present in a block if and only if the locked round component is non-empty and if so, the locked round has to match the round of the included preattestations.

Next, we provide two examples of fitness values: 02::00001000::::ffffffff::00000000 and 02::00001000::00000000::fffffffe::00000001 (in the hexadecimal format that one may observe in the node’s logs). These two values have the following components:

  • the 1st component, 02, is the fitness version;

  • the 2nd component, 00001000, is the block’s level (level 4096);

  • the 3rd component is the block’s locked round: empty in the first case, 0 in the second;

  • the 4th component is the round of the predecessor block, here 0 in the first case and 1 in the second case;

  • the 5th component is the block’s round: 0 in the first case, 1 in the second case.

We recall (see Shell header) that the fitness is, from the shell’s perspective, a sequence of sequences of unsigned bytes and comparison is done first by the length of the sequence and then lexicographically (both for the outer sequence, and for each of the inner sequences). So the first fitness is smaller than the second one, because of the third component, the empty bitstring being smaller than any other bitstring.

Further External Resources#