Proof-of-stake

Overview

The consensus algorithm in Tezos is based on the proof-of-stake mechanism. Proof-of-stake means that participants in the consensus algorithm are chosen in function of their stake (the amount of tokens a participant has). The same mechanism is used in the Tezos governance.

If one does not have enough stake to participate on its own or does not want to set up the needed infrastructure, (s)he can use delegation. Therefore, in Tezos, it is the delegates that may participate in consensus. However, at each level, not all delegates necessarily participate, and their participation weight may differ. The selection of the delegates’ participation rights at a level is done by running a PRNG (pseudo-random number generator). The PRNG’s seeds are obtained from random data that are regularly produced and stored on the blockchain. Thus, the procedure is deterministic in that delegates’ rights are uniquely determined from the seed; and it is random, in that its seed (and hence its results) cannot be predicted too much in advance.

Delegation

A delegate is any implicit account registered as such by emitting a delegate registration operation.

Any account (implicit or originated) can specify a delegate through a delegation operation. Any account can change or revoke its delegate at any time. However, the change only becomes effective after PRESERVED_CYCLES + 2 cycles. The value PRESERVED_CYCLES is a protocol constant.

A delegate participates in consensus and in governance with a weight proportional with their delegated stake, which includes the balances of all the accounts that delegate to it, and also the balance of the delegate itself. To participate in consensus or in governance, a delegate needs to have at least a minimal stake, which is given by the TOKENS_PER_ROLL protocol constant.

Delegates place security deposits that may be forfeited in case they do not follow (some particular rules of) the protocol. Security deposits are deduced from the delegates’ own balance.

Active and passive delegates

A delegate can be marked as either active or passive. A passive delegate cannot participate in the consensus algorithm.

A delegate is marked as active at its registration.

A delegate becomes passive at the end of cycle n when it has failed to participate in the consensus algorithm in the past PRESERVED_CYCLES + 1 cycles, that is, in cycles n, n-1, n-2, …, n - PRESERVED_CYCLES.

Delegates’ rights selection

Tezos being proof-of-stake, the delegates’ rights are selected at random based on their stake. In what follows we detail the selection mechanism used in Tezos.

Random seed

To each cycle is associated a random number called the seed. This seed is used within its cycle to generate pseudo-random values in the protocol, in particular for selecting delegates to participate in consensus.

The seed is the output of a simple multi-party randomness protocol (similar in spirit with the RANDAO protocol): at each cycle end, a new seed is computed as the hash of the previous seed and of nonces (for “number used only once”) provided by delegates during that cycle and stored on the chain. Nonces are supposed to be random. To ensure that participants do not adaptively chose their nonces and therefore that the seed is not easily biased, participants in the protocol use a ‘’commit and reveal’’ scheme: in the previous cycle, they first commit to nonces and they only reveal their committed nonces later, in the current cycle.

We make the assumption that at least one participant is honest, that is, it has indeed chosen a random value and this value was revealed. This is a necessary condition for the seed to be random. The randomness could however be biased as this protocol suffers from the following low-impact weakness: if a malicious participant can make sure she is the last revealer, then she can choose to reveal or not its committed value and can thus choose between two different predetermined seeds.

Concretely, the random seed for cycle n is a 256-bit long number computed at the very end of cycle n-1-PRESERVED_CYCLES from nonces to which delegates commit during cycle n-2-PRESERVED_CYCLES. Every BLOCKS_PER_COMMITMENT levels, the corresponding block contains a nonce commitment. More precisely, a block contains a commitment if and only if its cycle position modulo BLOCKS_PER_COMMITMENT is BLOCKS_PER_COMMITMENT - 1. The nonce is a 256-bit number generated by the block proposer and its commitment is included in the block header. The commitment is simply the hash of the nonce.

The committed nonce must be revealed by the original block proposer during cycle n-1-PRESERVED_CYCLES under penalty of forfeiting all of its expected endorsing rewards for that cycle. The associated security deposit is not affected.

A nonce revelation is an operation and multiple nonce revelations can thus be included in a block. A reward SEED_NONCE_REVELATION_TIP is given for including a revelation. Revelations are free operations which do not compete with transactions for block space. Up to MAX_ANON_OPS_PER_BLOCK revelations, wallet activations and denunciations can be contained in any given block.

The seed for cycle n is the bitstring obtained by iterating through the nonces revealed in cycle n-1 as follows: initially it is the seed of cycle n-1; at each iteration, the new bitstring is the hash of the concatenation of the previous bitstring with the iterated revealed nonce.

Stake snapshots

Before turning to the rights selection mechanism, we first introduce a new terminology, stake snapshot, to denote the stake distribution for a given block, as stored in the context. Stake snapshots are taken (and stored) every BLOCKS_PER_STAKE_SNAPSHOT levels. More precisely, a snapshot is taken at a level if and only if its cycle position modulo BLOCKS_PER_STAKE_SNAPSHOT is BLOCKS_PER_STAKE_SNAPSHOT - 1. Therefore, at the end of a cycle there are BLOCKS_PER_CYCLE / BLOCKS_PER_STAKE_SNAPSHOT stored snapshots.

At the end of cycle n-1-PRESERVED_CYCLES, the snapshot for cycle n is randomly selected from the snapshots stored in cycle n-1-PRESERVED_CYCLES. The selection is done through a very simple PRNG having as seed the random seed for cycle n.

Only the stake of active delegates with the minimal stake of TOKENS_PER_ROLL is snapshot.

Slot selection

Delegates’ rights to participate are determined using the alias method, more precisely using Vose’s algorithm (see also this more pedagogic description; the algorithm is the last one listed there). This algorithm samples from a discrete probability distribution, which is given by the stakes in a particular stake snapshot: the probability to sample a particular delegate is its stake in the snapshot over the total stake in that snapshot.

Concretely, the delegates’ rights at a given level are expressed in terms of the (quantity of) slots that the delegate owns at that level. This quantity represents the delegate’s weight in consensus. We note that, in the long run (that is, on average over many levels), the number of slots is proportional to its stake. The owner of a slot is obtained by sampling using the algorithm mentioned above. More precisely, given a level and a slot (which is just a non-negative integer), the mentioned algorithm is invoked to assign a delegate to the given slot. Its input is the probability distribution given by the stake snapshot for the cycle to which the level belongs. And whenever the algorithm needs to draw a random value, this is obtained using a simple procedure which has as its initial state: the level, the random seed for the cycle to which the level belongs, and the slot.

Protocol constants

Protocols are parameterized by several parameters called protocol constants, which may vary from one protocol to another or from one network to another (for instance, test networks move faster).

The list of protocol constants can be found in the API of the Constants module.

The values of protocol constants can be found using a specific RPC call, as shown in this example.

In particular, the protocol constants related to the proof-of-stake mechanism are detailed below.

Proof-of-stake parameters

Parameter name

Parameter value

BLOCKS_PER_CYCLE

8192 blocks

PRESERVED_CYCLES

5 cycles

BLOCKS_PER_COMMITMENT

64 blocks

MAX_ANON_OPS_PER_BLOCK

132 revelations

SEED_NONCE_REVELATION_TIP

1/8 ꜩ

TOKENS_PER_ROLL

6,000 ꜩ

BLOCKS_PER_STAKE_SNAPSHOT

512 blocks

Further External Resources

The original design of the proof-of-stake mechanism in Tezos can be found in the whitepaper.

Another presentation of the Tezos’ proof-of-stake mechanism can be found in the Tezos agora wiki entry.