Solving the problems that can only be solved by consensus in distributed systems is something I love. They’re fascinating problems, exist at high scale and are beautiful to watch in action. (Well, at least to me. But I am a twisted boy, so tastes and colors)
The Apollo project has a two consensus mechanisms. The Fireflies View uses consensus to maintain a virtually synchronous view on the membership set, across all members. This is an agreement across the entire population as to what members constitute the population. This sounds silly, but simply that bit of an agreement – i.e. who am us anyway? – is a powerful piece of context that can be cleverly leveraged to produce some rather interesting results.
The other consensus mechanism is in the Ethereal subsystem. The base functionality is an asynchronous, byzantine fault tolerant, causal consensus mechanism. Ethereal is based on Aleph and provides the basis for producing distributed ledgers of transactions in the CHOAM module. CHOAM builds on Ethereal to provide the traditional replicated state machine driven by transactions. These transactions are generic and represent commands for the replicated state machine. CHOAM is built upon by the SQL State Machine module to produce a full featured distributed SQL database.
It’s important to note that the consensus mechanism of Ethereal builds upon the View membership consensus of the Fireflies module. This dependency is not a simple dependency on an abstract membership service. Rather, the upper layer consensus mechanisms depend upon knowing the precise membership of the group. CHOAM uses the membership to build up the membership Contexts, which have an internal connection structure that produces byzantine fault tolerant member subsets, and these subsets are leveraged by CHOAM to elect random committees to perform consensus.
BFT Contexts
Something we can do with shared knowledge of the membership is construct graphs of these members. If we use deterministic rules to do so, then all members can construct the same graph from the same membership using the same rules independently – i.e. without any communication/coordination. In particular, we can construct special kinds of graphs that form random rings of the members and these graphs allow us to do some pretty amazing things (these graphs are known as expander graphs). An example of this is shown in the diagram below from the Fireflies paper (which you should read as it is most awesome).
In this diagram, we have members { A … G }. These members have a unique identity (ID) and this id can be hashed to map the id to a consistent hash ring, composed of hashes from 0 to the MAX hash value (0 -> 256 bits in Apollo by default). Members are mapped to this ring at the position determined by the SHASH.
The purpose of the SHASH is to “randomly” distribute the members around the ring. Note that this SHASH is based on the ring identity (ID). In this example, the SHASH is simply some hash function over the concatenation of the ring.id and the member.id. In Apollo, it’s slightly different but we use the exact same idea to randomize the ordering of members on a given ring.
One important thing about using a ring structure is that each member on the ring has a predecessor and a successor. We take the convention of the counterclockwise member as the predecessor and the clockwise as the successor. Because the structure is a ring, all members are defined to have a predecessor and a successor – in the single member case, that is the member, itself.
The reason for the SHASH being a function of both the member id and the ring id is that we construct multiple rings for a context. The precise way this is constructed is rather involved (as all magic inevitably is), but the interesting thing is that this construction results in a set of rings that form an expander graph of very low diameter – from simulations, a diameter of approximately 2.
The diameter of a graph is the measure of how many hops – or edges – are required to go from random member A to random member B. This is an amazing property of these ring graphs when we consider that on any given ring a member has only 2 neighbors.
In this diagram all of the members are present on each of the 3 rings although the ordering of the members is different for each ring. This is caused by using a different SHASH function for each ring – e.g. one that concatenates the ring id with the member id.
In addition to dense connectivity between the members, these rings are constructed in such a fashion as to produce byzantine fault tolerant subsets via the ring structure that we can leverage elsewhere – as seen in previous posts. This is why these Fireflies View Contexts are considered foundational to Apollo and show up throughout the rest of the architecture.
Byzantine Fault Tolerant Subsets
These BFT subsets are formed using these rings in the membership Contexts. In the example below, we have 5 members, {A … E} and 3 rings. Again we note that all members are present on all 3 rings, but appear in different orderings.
The way these rings are constructed ensures (with high probability) that selecting successors of a provided hash digest forms a byzantine fault tolerant member subset. In this example the cardinality of the set is 3 and the members of the selected set are the nodes {A, D, E}. These nodes form the byzantine fault tolerant set for the chosen hash location – whether that hash be a member ID or some other hash value (such as a view ID or block hash). In this example, the BFT subset can tolerate one byzantine member.
But let’s be clear. All the above – the rings, the BFT sets, all that – is only possible because we have consensus on the set of members and all the members agree this same set of members. Without consensus on membership, we can’t easily get the same magical properties outlined above.
In Apollo, Views change membership in a quantum fashion- that is, the membership changes in interval step functions; not a continuously changing value at arbitrary times. These Views represent a consensus on the membership, they are stable, and change in discrete time steps – every member of a view shares the same view. This is in contrast to other membership services like Zookeeper and others, where membership changes happen at any time in continuous fashion, and there is no concept of a stable, consensus “view” of members.
As discussed previously, we can use the HexBloom authenticated data structure to create a very compact cryptographic representation of the membership group – the view – similar in function to a Merkle Tree. We can construct the HexBloom of a View’s membership using the Identifiers of the members as the hash ID used to calculate the HexBloom, and thus the compact hash is the same size as the IDs (32 bytes). And this compact hash of the HexBloom of a View can be used as the Identity – ID – of a View’s Context. The compact hash acting much like the root hash of a Merkle Tree.
The encoding of the View’s members in the HexBloom creates a strong binding between the membership set and the compact digest – hash – of that HexBloom. This is a property akin to the strong binding previously discussed between KERI (Stereotomy) Identifiers and the Key Pairs they represent. Signing a compact hash is signing the precise membership of a View.
Ethereal, CHOAM and SQL State Machines
Ethereal represents another kind of consensus in Apollo. This consensus mechanism builds upon the stable membership group to implement a form of asynchronous, causal consensus. The Ethereal implementation in Apollo is based on the most excellent paper Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes. This is an asynchronous Byzantine Fault Tolerant consensus mechanism that produces blocks of unit data using an Atomic Broadcast. These blocks of data can represent transactions, key data, whatever – it’s a general service for producing continuous blocks of data in consensus and processing across the group.
Ethereal is used by the CHOAM module in Apollo to provide generic State Machine Replication. CHOAM produces command blocks containing batches of Transactions that are processed by all members of the combine – the reliable broadcast group that defines the CHOAM. CHOAM, in turn, is leveraged by the Apollo SQL State Machine to produce… well… a fully functional distributed SQL database.
I know that I’m glossing over quite a lot wrt these systems. Ethereal, CHOAM and the SQL State Machine are complex, elegant systems. But for the most part, the implementation details of these systems are irrelevant in so much as the capabilities match the claims (🤞). For the purposes of this post, the point is that Ethereal provides a consensus solution that ultimately results in a simple to use replicated SQL database.
And we have to note again that all of the machinery just described rests upon the foundation of the humble Fireflies Context. The Ethereal consensus mechanism requires knowing the membership set completely and that all members agree on the membership of this set. And what that means, in essence is that we already have consensus – from the very beginning – on the membership set!
Before we even begin the Ethereal Atomic Broadcast protocol, before the Genesis block of a CHOAM group is produced. The means and mechanisms for adding and removing members of a consensus protocol is actually a pretty involved thing and non trivial to accomplish.
This is why, in CHOAM, there is an entire View Change Protocol (in the form of a Finite State Machine) that handles this membership change logic. As is common throughout Apollo, the Context abstraction is coupled to the CHOAM using the underlying Fireflies View membership overlay. It’s the view change protocol implementation that allows CHOAM to securely adapt to an evolving group membership.
Which is pretty cool, if I do say so myself.
Nesting and Scaling BFT
This is a long post and I’ve really yet to even dive into detail on these consensus systems. What I’d like to stress, however, is the motif of Byzantine Fault Tolerance. I keep repeating this theme because it really is a binding kind of pattern throughout the Apollo architecture. The notion of BFT comes up in signing thresholds, consensus – anywhere we need distributed agreement, either expressed or implied.
Recalling the discussion above on the Fireflies View, the Context and the BFT ring construction, another reason why the underlying Context foundation is important is one of scalability. Consensus mechanisms can be expensive and different kinds of consensus mechanisms have different costs. Heck, different kinds of consensus have different uses, too.
And so the BFT subset we can leverage, based on the Context’s rings becomes a powerful scaling and load balancing mechanism in Apollo. The number of members in this subset is far smaller than the number of total members in the group. This means that we can use this subset as a BFT membership that can perform consensus work, ultimately recorded through signatures.
As you can see from above, we can construct a byzantine fault tolerant set of rings from membership cardinalities of 1,000,000 members and still only require less than 42 rings. This even holds when using ludicrous probabilities for any member being byzantine (e.g. 20% chance of any member being byzantine means you do not have control over your systems and have far bigger problems).
This means that our BFT subsets – based on the rings of our Context and k in the graph above – result in a dramatic reduction in the number of things required – communication channels, messages, signatures, agreements, commitments, etc. Apollo systems don’t need BFT agreement across 1,000,000 members (which is clearly insane). Rather, Apollo systems can cleverly create BFT subsets of far, far less members of these large groups having them do the consensus for them. And this trick can only be performed because all the members are working with the same membership View.
That’s because this magical construction of BFT subsets still relies on an underlying consensus: the membership set itself. The View. Which brings us back to the consensus Views of Fireflies. Ultimately, the entire construction of Apollo – and the applications and services built on that – rest upon the foundation of the Fireflies membership Contexts and the stable, quantum View changes provided in the Apollo Fireflies implementation.
Which turns out to be a very good thing. By relentlessly reusing these abstractions – the Context, the Rings – we don’t have to keep rewriting the same solution. We can reuse this BFT subset motif to provide the Gorgoneion Identity Bootstrap service as well as provide the foundation for the replicated SQL database we use for the Access Control Oracle in Sky. We can craft compact proofs and maintain ideal state using these BFT subsets to maintain high trust signature chains that ultimately establish identity.
This relentless, recursive application of the BFT motif, over and over and over in Apollo that kind of makes it tough, and hard to kill.
Well, that’s what it says on the label anyway. In future posts I really want to dive into detail on these subsystems, rather than just gloss over them as one has to when portraying the higher level picture of how they integrate with each other to perform more complex actions.
The important points from this post, though, are that Apollo really reuses the heck out of a Byzantine Fault Tolerant subset pattern. The foundation for the pattern rests in the underlying membership set consensus maintained by the Apollo Fireflies View implementation. The membership Views change in a discrete quantum fashion and provide a stable foundation to create expander graphs of the membership set that allow us to construct these BFT groups. Using these groups we can build even more sophisticated versions of consensus and even implement protocols to manage these underlying membership view changes. Ultimately, a full featured, replicated SQL database is provided by Apollo using these underlying consensus services.
Leave a Reply