Nomadic Labs
Nomadic Labs

Emmy+: an improved consensus algorithm

Underlying the Tezos network is a consensus algorithm, which, for the ease of reference, we will call Emmy. Consensus ensures that participants agree on the same blockchain and on its state. The ideas behind Emmy are described in the white paper and the specifics to its implementation can be found in the documentation. We recall that Emmy is a PoS based consensus with a use of endorsements to speed-up confirmation times and reduce selfish baking. This was done by defining the chain fitness as the total number of endorsements (in addition to the chain length).

This post introduces Emmy+, an improvement of Emmy which still guards against selfish baking but also achieves greater efficiency and stability. Emmy+ will be included in our next protocol proposal.

The main difference is that, in Emmy+, the number of endorsements included in a block no longer influences the fitness, but the timing of a block: the fewer endorsements a block carries the longer it takes before it can be considered valid. More precisely, a block is valid only if its timestamp has a minimal delay with respect to the previous block’s timestamp, and this minimal delay depends not only on the block’s priority but also on the number of endorsement operations included in the block.

As for block fitness, in Emmy+, it increases by one unit with each level. In this way, Emmy+ simplifies the optimal baking strategy: the bakers used to have to choose whether to wait for more endorsements to include in their block, or to publish the block immediately, without waiting. The incentive for including more endorsements was to increase the fitness and win against unknown blocks. However, when a block was produced too late in the priority period, there was the risk that the block did not reach endorsers before the block of the next priority. In Emmy+, the baker does not need to take such a decision, because the baker cannot publish a block too early. This should lead to fewer missed blocks and endorsements and therefore faster convergence.

Another advantage of Emmy+ is that chains that have fewer endorsements, signalling a difficulty in reaching consensus, become slower. This brings the algoritm closer to classic BFT consensus algorithms which have deterministic finality.

Finally, the changes lead to a few other simplifications, like simpler endorsement reward policy and shorter times between blocks when blocks at higher priority are missing, as we explain in more detail below.

Main change in detail

In Emmy, the minimal delay for a block with respect to the block at the previous level is given by the following function:

  emmy_delay(p) = 60 + 75 * p

where p is the block’s priority and the values 60 and 75 are given by the time_between_blocks constant, set to [60; 75]. (In the code base, the definition of what we call emmy_delay is implemented by the function Baking.minimum_time; see src/proto_alpha/lib_protocol/baking.ml in the master branch).

In Emmy+, the new delay function depends not only on priority but also on the block’s endorsing power e, that is, the number of slots corresponding to the endorsements included in the block. This new delay function is defined as follows.

  emmy_plus_delay(p, e) =
    if e >= initial_endorsers then
      emmy_delay(p)
    else
      emmy_delay(p) + delay_per_missing_endorsement * (initial_endorsers - e)

where delay_per_missing_endorsement and initial_endorsers are two new constants.

The value of initial_endorsers (init_endo) is set to 18. Recall that the maximum endorsing power of a block is given by the endorsers_per_block constant, set to 32. The rationale behind choosing the value 18 will be explained in a technical blog post and is intended to minimize the ability of a malicious baker to steal slots.

As for delay_per_missing_endorsement, it denotes a time period (Period.t) and it is set to 5 seconds. Therefore, with each missing endorsement with respect to the initial required amount, 5 additional seconds need to pass before the baker can send its block.

In addition, the value of time_between_blocks is changed from [60; 75] to [60; 40]. Thus the time between blocks when the block at priority 0 is missing is shortened.

The new delay function can be visualized on the following graph: delay function for Emmy+

The graph depicts 5 functions: t = emmy_plus_delay(p, e) for 5 values of p. It can be read as follows: a block at priority p and with endorsing power e needs to have a timestamp at least t seconds bigger than the timestamp of the block at the previous level. For instance, a block at priority 0 with endorsement power 12, needs to have at least 60 + 5 * max(0, 18 - 12) = 90 seconds delay, while a block at priority 2 with endorsement power 24 needs to have at least 60 + 2 * 40 + 5 * max(0, 18 - 24) = 140 seconds delay.

Finally, we emphasize that, besides minimizing the timing between blocks, these constants are also chosen such that a baker cannot steal the baking slots of other bakers by withholding its endorsements (unless it controls significantly more than one third of the total stake). We will publish a more tehnical blog post with details of our analysis, which will also show how the constants were chosen. The constants might actually slightly change as we refine our analysis.

Changes to the reward system

The rewards for blocks and endorsements are now dependent on blocks’ priority: for priority 0, the same rewards as in Emmy apply, however, for larger priorities, the block rewards become smaller and endorsement rewards are computed differently.

Concretely, the baking reward becomes block_reward / (p+1) and the reward per endorsement becomes endorsement_reward / (p+1) where p is the baked block priority or the priority of the block which contains the endorsement, respectively. Note that in Emmy, for endorsements, p was the priority of the endorsed block, not of the block which includes the endorsement. The constants block_reward and endorsement_reward do not change, they are still set to 16 and 2 tezzies. Security deposits also do not change.

This change makes selfish baking attempts much less profitable: a baker with a slot at priority 1 who might attempt to steal the block at priority 0 by withholding his endorsements would be better off having his endorsements included in the block of priority 0.

Other changes

RPC additions

There are three additional RPC services:

  • POST chains/<chain>/blocks/<block>/endorsing_power returns the endorsement power (i.e number of slots) of a given endorsement operation.

  • GET chains/<chain>/blocks/<block>/required_endorsements?[block_delay=<int64>] takes a block delay which represents the delay of a block’s timestamp with respect to the minimum time to bake at the block’s priority (as returned by Baking.minimum_time or emmy_delay above). It returns the minimum number of endorsements that the block has to contain to be valid.

  • GET chains/<chain>/blocks/<block>/minimal_valid_time?[priority=<int>]&[endorsing_power=<int>] takes two arguments, a priority and an endorsing power, and it returns the minimum time at which the next block can be baked. This is the dual of the previous service. It corresponds to the emmy_plus_delay function given above.

Improvements to the baker

The --await_endorsements argument to the baker was removed, as it becomes unnecessary. Indeed, the baker is forced to wait for a minimal amount of endorsements, it does not have a choice any longer.

New field in endorsement operations

Now an endorsement operation also includes a slot field, whose value is the first slot of the endorser. This is done in order to determine the endorser more quickly. Previously, the endorser was determined by iterating through all slot owners and checking which public key matched the endorsement’s signature; which was not an efficient method.

Emmy+ in the next protocol proposal

Emmy+ will be part of the next proposal of a protocol amendement. The mentioned changes appear in this merge request.


Receive Updates

ATOM

Contacts