The Stellar protocol: quorum slices and the quorum function

In this post, we explain how Stellar reaches network-wide consensus using quorum slices. We go over 2 key ideas, quorum slices and the quorum function, which are not cryptographic in nature but set-theoretic, using Python.

A key technical innovation of the Stellar protocol is the introduction of federated Byzantine agreements. These allow 4 cool things:

  1. To reach consensus fast and cheaply: within a few seconds and spending little energy
  2. To let anyone join the consensus process: no one has all the decision-making power
  3. To let everyone decide who to trust: if you want to be trusted, you better play clean
  4. To be safe: even if bad actors join the network, the network can still reach the "right" consensus

All of this rests on 2 key ideas: quorum slices and the quorum function. The good news is that these depend mostly on set theory!

A network of nodes

Quorum slices and the quorum function make no sense in isolation; they need context. This context is the network of nodes.

Let's say we have 3 people: Alice, Bob, and Charlie. They're trying to decide what movie to watch. They will be our network of nodes. Abstractly, we can stuff them all into a set called friends.

friends  = {'Alice', 'Bob', 'Charlie'}  # This is a set!
print(friends)

In mathematics, every set has associated to it another set, called its powerset. In Python, we can build powersets like this:

def powerset(s):
    """This function builds powersets. It takes a set `s` and returns the powerset of `s`.
    The powerset contains all subsets!"""

    n = len(s)  # Size of our set
    s = list(s)  # We turn our set into a list to allow indexing

    subsets = []  # Our powerset will actually be a Python list, for simplicity
    for i in range(2**n):  # We loop through each of the 2**n subsets of our set
        subset = {s[j] for j in range(n) if (i & (2**j))}
        subsets.append(subset)

    # We sort the powerset (actually a Python list) by length!
    # This is simply to aid visualization.
    return sorted(subsets, key=lambda x: len(x))


friends  = {'Alice', 'Bob', 'Charlie'}  # This is a set!
powerset_friends = powerset(friends)
print('set: ', friends)
print('powerset: ', powerset_friends)

You can run this snippet here:

Notice the set friends has 3 elements, and its powerset has 8 elements. This is no coincidence. In general, a set with n elements yields a powerset with 2**n elements. In Python, set() stands for the set containing no elements at all, called the empty set. The powerset of friends contains every possible combination of friends, including the "empty" combination!

A quorum slice: just a set of nodes... with a twist

Now that we have a set and and its powerset, we can start building quorum slices.

Each person in our example is a node. The set of all nodes is the network. A quorum slice is a subset of the network. A quorum slice doesn't make sense by itself; it needs to be associated to a node. So we'll be talking about "a quorum slice for Bob", or "a quorum slice for Alice".

Neglecting details, a quorum slice for Alice is just a set of nodes containing Alice.

Here's an example of a possible quorum slice for Alice:

  1. NODE: Alice
  2. POSSIBLE QUORUM SLICE FOR Alice: {Alice, Charlie}

Here's an example of an impossible quorum slice for Alice:

  1. NODE: Alice
  2. IMPOSSIBLE QUORUM SLICE FOR Alice: {Charlie, Bob}

It's impossible because it doesn't contain Alice!

Notice a quorum slice for Alice is just some element of the powerset. Of course, not every element of the upowerset needs to be a quorum slice for Alice. Also, some elements of the powerset can't be quorum slices for Alice.

And here comes the twist. If Alice wants some set of nodes to be her quorum slice, that set of nodes must satisfy an additional property: it must be trusted by Alice. Put another way: Alice must trust her quorum slice.

Trust is a very strong word: a set of nodes that Alice trusts can influence her decisions!

One of the key properties of federated Byzantine agreements is that every node decides which nodes it trusts. Or, to use our new language: every node chooses its quorum slice.

But that's not all. The last detail is: Alice isn't limited to a single quorum slice. She can choose as many quorum slices as she likes!

I like to refer to all of Alice's quorum slices as Alice's "happy family".

Question. What is the largest possible quorum slice for Alice?
Answer. {Bob, Charlie, Alice}.

Question. What is the smallest possible quorum slice for Alice?
Answer. {Alice}, meaning Alice trusts no one but herself.

Question. What are all the possible quorum slices for Alice?
Answer. There's 4 possible quorum slices:

  1. {Alice}
  2. {Bob, Alice}
  3. {Charlie, Alice}
  4. {Bob', Charlie, Alice}

Question. What is the largest possible "happy family" for Alice?
Answer. { {Alice}, {Bob, Alice}, {Charlie, Alice}, {Bob, Charlie, Alice} }, which is every quorum slice possible.

Question. What is the smallest possible "happy family" for Alice?
Answer. The smallest "happy family" for Alice has 1 quorum slice. There's 4 such "happy families":

  1. { {Alice} }
  2. { {Bob, Alice} }
  3. { {Charlie, Alice} }
  4. { {Bob', Charlie, Alice} }

The quorum function: each node has a family of quorum slices

Alice can choose as many quorum slices as she likes. So, Alice's "happy family" can have 1, 2, 3, or 4 members.

The quorum function says which particular family of quorum slices Alice chose. The quorum function doesn't work only on Alice, though, but on every node!

And that's all the quorum function is: the object that contains all the information about which particular "happy family" each node chose.

If we call the quorum function \( \textbf{Q} \), then we can refer to Alice's "happy family" as \( \textbf{Q}(\text{Alice}) \). More formally, \( \textbf{Q}(\text{Alice}) \) is the value of the quorum function evaluated at Alice.

Federated Byzantine agreement systems (FBAS)

A federated Byzantine agreement system (FBAS, for short) is simply a network of nodes together which a particular quorum function.

The SCP white paper puts it like this:

Definition (FBAS). A federated Byzantine agreement system, or FBAS, is a pair \( (\textbf{V}, \textbf{Q}) \) comprising a set of nodes \( \textbf{V} \) and a quorum function \( \textbf{Q} : \textbf{V} \longrightarrow 2^{2^\textbf{V}} \backslash \{\emptyset\} \) specifying one or more quorum slices for each node, where a node belongs to all of its own quorum slices.

In set-theoretic terms, the "happy family" is an element of the powerset of the powerset.

And now we're ready to define the quorum function. The quorum function is simply an assignment of nodes to quorum slices.

The quorum function says each node must have a family of trusted nodes.

Of course, since every node chooses its own quorum slices (its "happy family")

But that's not the whole story! Each node isn't limited to just one such family; it can choose as many as it wants!

Of course, a network of nodes can have many, many quorum functions. A particular quorum function simply corresponds to a particular assignment of quorum slices.

Can we watch the movie already?

Remember this whole nightmare started when the 3 friends decided to watch a movie.

We've still got a bit of ground to cover before we're ready for that. After going over quorums, federated voting, and the ballot process, we'll finally be ready. Stay tuned for part 3.