Consensus

The consensus protocol running on all Flare networks is Snowman++, introduced by Avalanche. This runs on both the P- and C-chains.

Snowman++ is a Byzantine fault tolerant (BFT) protocol, being part of the wider Snow family of probabilistic protocols, which includes:

• Slush: the foundational protocol in the Snow family. It operates in iterative rounds, during which each node samples a subset of the network and updates its local state according to the sampled majority. Nodes terminate simply once a predefined number of rounds has elapsed. Slush by itself is not Byzantine fault tolerant.

• Snowflake: an extension of Slush which introduces an additional threshold parameter for finalization. As a result, a node finalizes a state only after a specified number of consecutive queries consistently supports that same state. This refinement enhances Slush by improving its finalization properties.

• Snowball: augments Snowflake by incorporating local confidence counters. Each time a query reaffirms a particular state, the corresponding confidence counter for that state increments. This provides “memory” to the protocol, allowing nodes to accumulate additional certainty in their decisions over time.

• Snowman: while Avalanche originally relied on a directed acyclic graph (DAG) structure, Snowman is the linear-chain version of it. Within Snowman there are multiple Snowball instances running concurrently at various block heights, each awaiting finalization. Snowman's key advantage is its ability to leverage a single set of correspondences to drive several simultaneous Snowball processes, thereby enhancing the overall efficiency of the consensus mechanism.

• Snowman++: introduces a soft proposer mechanism, initially granting a single proposer the authority to create a block. Over time, additional validators become eligible to propose blocks, with each validator selected according to its stake. This design further refines Snowman’s block-production process by incorporating stake-weighted proposer selection.

Slush

Slush serves as the foundational protocol in the Snow family. In Slush, a node repeatedly samples the network and queries each selected peer regarding its current preferred state. The protocol is governed by two parameters:

• K: the number of nodes included in each sample.
• Alpha: the minimum threshold—constrained such that K/2 < Alpha < K + 1—required for a query to be considered successful. That is, at least Alpha nodes must support the same state.

When a query is deemed successful - i.e., it garners at least Alpha votes in favor of a particular state -- the node updates its own preference to match the majority state of the sample. The original formulation of Slush was defined for a binary decision scenario. The image below depicts such a binary decision example, where a user samples the network, queries the sampled participants, and updates its preferred state according to the majority. The example uses K=5 and Alpha=3 for the protocol parameters.

Slush does not incorporate inherent fault tolerance. This limitation is evident in its termination process, as the algorithm executes for a predetermined number of rounds rather than terminating based on reaching a consensus resilient against Byzantine faults.

The Slush algorithm is implemented as part of the go-flare client, within the snow/consensus/snowball package. The global parameters are defined as part of the genesis configuration.

Snowball

Snowflake and Snowball are enhancements to the original Slush protocol, introducing additional global and local parameters to govern when a node may finalize its decision.

• Beta: the required number of consecutive successful queries that support the same outcome before a node can finalize. In other words, a node is deemed to be finalized once it achieves the same decision in Beta consecutive successful rounds. This represents a significant improvement over Slush, which lacked any dynamic security mechanism within its fixed termination conditions.

• Confidence counter: Snowball adds to this logic an additional local confidence counter, confidence, which effectively further extends the protocol memory. This counter tracks the number of consecutive successful polls that have returned the current preference. A node will only update its local preference if the counter for a new state exceeds that of the current preference.

Tree structure

In the Go implementation from the snow/consensus/snowball package, the Snowflake and Snowball protocols share a common interface. For both protocols, decisions are made on the 32-byte binary form of the proposed blocks.

To effectively deal with more than two choices at a time, Snowball implements a Tree structure for all concurrent decisions. This implementation is specialized to handle multi-branch conflicts elegantly, by modeling them as a hierarchy, and thus optimizing the algorithm by allowing pruning.

More precisely, concurrent blocks at the same height are organized in a tree-like structure based on the first differing bit. As such, when adding a new block, the tree branches out through a binaryNode at the first differing bit, with the counting done from the most significant bit to the least significant bit. Here, bit indices are defined as:

[7 6 5 4 3 2 1 0] [15 14 13 12 11 10 9 8] ... [255 254 253 252 251 250 249 248]

An example of how concurrent blocks may be organized within the Tree structure is depicted below, where the first differing bit in a byte is also highlighted.

In the Tree implementation, each node in the tree structure holds a Preference and a confidence counter. Note that if the counter of a binaryNode increases following a successful poll, this propagates further up the tree towards the root node. binaryNodes can finalize only when the confidence counter reaches the globally defined Beta value, upon which they are replaced by unaryNodes, thus leading to branch trimming.

A key aspect of this implementation is that it avoids running polls for every single bit in the 32-byte representation at each block height. Next up we will see how Snowman optimizes the consensus algorithm further, by implementing a graph-like structure for blocks at different heights.

Snowman

While Snowball is used for deciding between concurrent blocks at the same block height, Snowman wraps this logic and extends it to a full linear blockchain. Snowman does enforce linearity, but non-finalized blocks can be temporarily organized into a DAG structure, which could simply be due to network delays for example. To convert this DAG structure to a linear graph, Snowman uses Kahn's topological ordering algorithm.

Naturally, for every block height, a set of block proposers is chosen in a deterministic fashion, as we discuss momentarily. This set is randomly determined using a seed based on the block height and on a characteristic that is chain-specific. Khan’s algorithm is used to organize blocks into a linear chain by enforcing the correct order of processing. More precisely, the algorithm enforces the parent-child relationships within the chain.

• Example: A validator might receive block B (at height N) before block A (at height N-1). Khan’s algorithm ensures that block B is processed only after block A is available and processed.

Khan's topological ordering algorithm ensures that:

• A block should not be added twice.
• A block that is being added should never have a child that was already added.

Go Implementation

The Snowman consensus is implemented through a Topological struct, which uses a graph for tracking the strongly preferred branch. Within this structure, topological order is done from leaves towards the genesis block.

For each round, validators report their currently preferred chain, rather than a single bit value, or a single block. Votes are then propagated transitively towards the genesis block, respecting parent-child relationships: a vote cast for a leaf implicitly supports its parent, provided that parent has not already been finalized. In the diagram below, blocks that have not been finalized are shown with dashed borders. A vote cast for block G is then propagated upward to blocks F and C.

Notably, a separate Snowball instance is running for every parent node within this structure. For example, at block C, the three concurrent child blocks are organized using the previously discussed Snowball Tree structure.

Consequently, the primary advantage of Snowman is its ability to leverage a single set of correspondences to drive multiple simultaneous instances of Snowball, thereby achieving efficiency and coherence across the consensus process.

Validator Sampling

A Snowman chain is initialized within the Manager interface of the chains package. This configures the global consensus parameters, as defined in the genesis files, as well as the type of sampling used by the validators.

The widely used sampling process in the consensus protocol is a weighted sampling without replacement, which is enforced in the snow/validators package. Here the weights are based on the validators' stake.

Snowman++

Snowman++ introduces a soft proposer mechanism, with a single proposer with the power to issue a block initially. The proposer selection is deterministic, based on the validator set and the chain height. Validators are selected using a weighted sampling without replacement, with the weight system based on stake.

At each block height, a fixed number of validators is selected, given by the protocol parameter maxWindows. Based on the position in the sampled set, the selected validators are then assigned a delay dictated by WindowDuration: the amount of time the validator must wait before being eligible to propose a block. These two parameters are part of the proposerVM, being configured as follows:

• maxWindows: currently set to 6.

• WindowDuration: currently set at 5 seconds.