Intuitive Stellar Consensus Protocol

Our previous post, “Why Quorums Matter and How Stellar Approaches Them”, focused heavily on quorum slices and the implications of quorum configurations. Recall,

A quorum slice is a subset of nodes on the network that a given node chooses to trust and depend on.

A set of nodes is a quorum if it is non-empty, and contains a slice for each member.

These definitions are quite abstract. In practice, when configuring a node, operators specify lists of nodes they trust. They also specify thresholds, or the minimum number of nodes in such lists that must agree. We call these lists quorum sets. For example, if an operator configures its quorum set to be {A, B, C} with a threshold of 2, then either {A, B}, {B, C} or {C, A} must agree before the node can proceed. {A, B}, {B, C} or {C, A} are all quorum slices.

We now introduce another concept crucial to SCP: blocking sets.

A blocking set is any set of nodes in a quorum set, without which it is impossible to reach consensus.

For instance, given a quorum set of 4 nodes with threshold 3 (meaning at least 3 out of 4 nodes must agree), any combination of 2 nodes forms a blocking set. Since any node from a quorum set can be in a blocking set, there may be many different blocking sets.

A consensus round is a procedure to agree on transactions to execute in a particular ledger. Statements are the smallest consensus round building block. In the context of Stellar, valid statements express different opinions of nodes regarding transactions to agree on for a given ledger . For example, “I vote for a set of transactions C to be considered for this ledger” is a valid statement. Similarly, “I applied a set of transactions C to this ledger” is also a valid statement.

A distributed system, such as the Stellar network, needs a consensus mechanism to agree on different statements. How do we ensure that a node does not act on a statement (for example, confirm a payment transaction) too early? More generally, when does a node know it is safe to confirm something? In the Stellar Consensus Protocol (SCP), agreement is achieved via federated voting.

In order to understand federated voting, we must first understand how a node reasons about the state of the network based on what it learns from its quorum set. Specifically, a node does not know what nodes outside of its quorum set decided, yet the network must agree on a single value. Before a statement is 100% agreed on by every honest node on the network, it has to go through three steps of federated voting: vote, accept, confirm. Given a statement A, a node might have four opinions on it:

1. I don’t know anything about A, and have no opinion.
2. I vote for A, it’s valid, but I don’t know if it’s safe to act on it yet.
3. I accept A, because enough nodes supported this statement, but I don’t know if it’s safe to act on it yet.
4. I confirm A, it is safe to act on it. Even if every node in my quorum has not confirmed A, they will not be able to confirm anything else but A.

In order to make transitions between the states above (vote, accept, confirm), federated voting prescribes the following rules:

Vote for A if it is consistent with my previous votes

Accept A if either:

• Every node in a quorum slice voted for or accepted A, OR
• My blocking set accepted A (even if I voted for something that contradicts A in the past, I forget about that vote, and proceed with “accept A”)

Confirm A if every node in a quorum slice accepted A

But why is federated voting really a three-step process? Couldn’t agreement be reached by simply accepting statements? The answer lies in one of the rules above: “My blocking set accepted A”. Without the confirm step, a node’s blocking set can convince the node to accept any arbitrary value. Accepting statements works only if all blocking sets are honest, but there’s no guarantee that they will be. With the confirm step, a node will only proceed to agree on a statement if every node in its quorum also accepted that statement, which yields optimal safety.

Each consensus round can be separated into two stages:

• Selecting candidate transaction sets that can be included in a ledger (nomination protocol)
• Ensuring that the network can unanimously confirm and apply nominated transaction sets (ballot protocol)

Intuitively, SCP acts like a funnel:

• A node starts with a possibility of agreeing on any value (in the context of Stellar, a value is a transaction set)
• Nominate statements aim to select an (ideally) small number N of candidate valid values.
• Prepare statements attempt to ensure a subset M (much smaller than N) of that finite set (i.e. any values that got confirmed nominated) can be committed.
• Commit statements either proceed to commit a confirmed prepared value, or commit what a node’s blocking set committed.

The nomination protocol helps scope the set of values to agree on, by performing federated voting on statements such as “Nominate transaction set C”. If the vote succeeds, the transaction set is added to the list of candidates to be used later in ballot protocol. There is an important invariant: as soon as a node confirms its first candidate, it stops voting to nominate any new transaction sets. It may still accept and confirm nominate statements that were introduced before, if, for example, it sees that the blocking set accepted some new value. This invariant guarantees that at some point all nodes will converge on a candidate set. Intuitively, if every node on the network stops introducing new values, but continues to confirm what other nodes confirmed, eventually everyone will end up with the same list of candidates.

Because it cannot tell whether other nodes have converged (no new values are being voted on) or some votes are still in-transit (haven’t been received), a node may start the ballot protocol as soon as it confirms a candidate. The input to the ballot protocol is called the composite value, and it is the biggest transaction set in the list of candidates confirmed through nomination.

Even after a node confirms its first candidate and starts the ballot protocol, nomination continues running in the background, so the node may confirm more candidates as it learns about accepted and confirmed nominations from other nodes on the network.

The ballot protocol attempts to safely commit the composite value, even if some nodes on the network become unavailable. It consists of two steps:

• “prepare”, which verifies that a node’s quorum slice has the right value and is willing to commit it
• “commit”, which ensures that a node’s quorum slice actually commits the value.

Ballot protocol incorporates federated voting on statements “Prepare transaction set C” and “Commit transaction set X”. It behaves optimistically, and tries to commit the composite value while nomination may still be running. In the best-case scenario, the rest of the network agrees with the proposed value. In the worst-case scenario, a node may get stuck trying to commit its composite value; it would then timeout and try again with a new composite value (updated by nomination) or switch its vote to what the blocking set accepted (abandoning its previous vote).