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).

For the purpose of this example, we assume that the network may arbitrarily delay or drop messages that nodes send.

Consider the following quorum configuration, where both left and right sides are well connected; however, the dependency between the two sides is one-directional. In other words, the left side has nodes from the right side in its quorum slices, but not the other way around. In fact, the right side is a quorum itself inside of a bigger quorum, as shown by the dotted lines. This implies that A may not proceed without the agreement of the nodes on the right side. Moreover, A is a blocking set for the left side.

1. A consensus round begins with the node A introducing transaction set C by voting to “Nominate C.” In SCP, nodes broadcast their decisions on statements, such as vote, accept or commit, so node A also broadcasts its nomination vote.

2. Both sides receive node A’s broadcast message, and since it is valid, also vote to nominate C.

3. Since every node voted to nominate C, it is safe to proceed to accept nomination of C. Again, nodes broadcast their acceptance.

4. The connection quality may vary across nodes. In this example, imagine the network is pretty reliable on the left side, but is experiencing delays/outages on the right side. Because of these delays, the right side does not see acceptance of nomination of C. On the other hand, since the left side received the messages, and each node saw that a quorum slice accepted Nominate C (including node A, its blocking set), it proceeds to confirm the statement.

5. Recall, when a “nominate” statement is confirmed, its transaction set is added to the candidate set that SCP keeps track of. We denote such sets with curly braces. The node then selects the composite value, which is the largest transaction set in the candidate set. In this example, the left side adds C to its (currently empty) candidate set, creating {C}. It then selects C as the composite value (pretty straightforward since C is the only value in the candidate set), and starts the ballot protocol by beginning to vote on a statement to prepare C.

6. Recall, the right side and node A are experiencing outages, so messages “Accept Nominate C” are still in-transit. Without them, the right side cannot proceed to confirm the nomination of C. Meanwhile, there is a new transaction set D introduced by some nodes on the right side, and the vote to “Nominate D” is broadcast.

7. Node A receives a vote to nominate D, and since it is valid, and A has not confirmed anything yet (recall nomination of C got stuck due to network unreliability), it votes to nominate D as well. Because the left side has already confirmed nomination of C, it may not vote for any new values (only accept whatever their blocking set accepts), so it does not vote for D.

8. Since the right side voted to nominate D, they may accept D, and broadcast their messages. By now, the connectivity issues plaguing the right side have been fixed, so this time the network properly delivers those messages.

9. Since every node on the right side sees a quorum slice accept the nomination of D, they all proceed to confirm D. When new values are introduced, nodes include previous values they voted for or accepted in their messages. Node A previously accepted the nomination of C, so when the nodes on the right receive messages about D, they also learn about the acceptance of the nomination of C. The right side and A confirm C as well, and add it to the candidate set. At the end of this step, the candidate set for the right side is {C, D}.

10. The right side (including A) may now compute its composite value and start the ballot protocol. In this example, let’s assume that transaction set D is bigger than transaction set C. Since that’s the case, the candidate set {C, D} produces the composite value D , which the right side votes to prepare.

11. Votes to prepare D are broadcasted successfully, and as the right side voted for it, they accept “Prepare D” and broadcast it.

12. Recall that A is a blocking set for the left side — i.e., the left side may not proceed without the agreement of A. The left side gets the message that A accepted “Prepare D”, and accepts “Prepare D”, even though it voted for “Prepare C” earlier.

13. At this point, all nodes may confirm “Prepare D”, as prescribed by the federated voting rules.

14. Through another round of federated voting on the statement “Commit D”, the nodes on both sides agree that it is safe to act on D.

As soon as a node confirms “Commit D”, it is safe to act on D. Nodes write the transactions that make up D to the database, close the ledger, and start a new one. The process repeats over and over again every 5 seconds, ad infinitum.