Consensus Protocol

Mysticeti introduces the concept of a proposer slot as a tuple (validator, round), which can either be empty or contain the validator’s proposal for the respective round. Unlike Bullshark, which has a proposer slot every two rounds resulting in high latencies, Mysticeti addresses this by introducing multiple proposer slots with three states: to-commit, to-skip, and undecided for each round. The default state of proposer slots is undecided.

The end goal of Mysticeti is to mark all proposer slots as either to-commit or to-skip by detecting specific DAG patterns:

• Skip Pattern: The skip pattern is identified if for all proposals, we observe 2f+1 subsequent blocks that do not support it. The skip pattern, illustrated by Figure 2 (left), where at least 2𝑓 + 1 blocks at round 𝑟 + 1 do not support a block (𝐴, 𝑟, ℎ).

• Certificate Pattern: The certificate pattern, illustrated by Figure 2 (right), where at least 2𝑓 +1 blocks at round 𝑟 +1 support a block 𝐵 ≡ (𝐴, 𝑟, ℎ). We then say that 𝐵 is certified. Any subsequent block (illustrated at 𝑟 + 2) that constrains in its history such a pattern is called a certificate for the block 𝐵.