Tensegrity

So how do we keep the cluster “identity” while we’re evolving the membership dynamically? This is an existential problem that comes down to what I’ll refer to as View Evolution, for kicks.

By “cluster identity” I abuse a concept to signify the unbroken chain of trust in a cooperating cluster such as Gorgoneion and maintaining this chain throughout the lifetime of the cluster, even as new members enter the group and other members leave it. Even when – at some point – the membership set has been completely replaced.

This trust is necessary to prove that actions the cluster took in the past – such as signing – are still correct even when none of the original signing members are still around. This becomes especially problematic as the cardinality of the membership changes as the number of rings in the fireflies Context of members in the Gorgoneion cluster changes in response – the cardinality of the BFT set can change at thresholds in membership. New members get inserted and old members leave changing the ordering of the members on any particular ring.

How do we maintain trust as the system evolves?

A Room With A View

View Evolution is the time series of ordered intervals represented by a stable membership population. These are discreet intervals of time, non zero in extent, where View V has a fixed membership set M. These Views are current only for the declared interval, with a stop and start instant. The membership M is constant during this interval and members neither join nor leave.

A new View is created when the underlying membership overlay (in Apollo, this is Fireflies) has members joining/leaving the current View. In Apollo Fireflies, the Views are discrete and are given unique IDs that are the compact hash of the HexBloom of the membership. This provides a unique digest for the view and can be used as the ID of that view.

The HexBloom is an authenticated data structure similar in function to a Merkle Tree with a number of very cool advantages, primarily that validation doesn’t depend on network latency and the structure is very fast both to build and validate. The HexBloom is composed of a hash digest (can be multiple, called the LinkedHashX) and a bloom filter. The digest is the XOR of all the other ID digests in the membership and the bloom filter is a low FPR bloom filter used for membership queries. It’s quite cool and as an authenticated data structure, it substitutes for a Merkle Tree and is far more useful to Apollo.

Using the HexBloom compact digest of a View gives us a unique membership function we can query using the bloom filter for membership. Note that we simply XOR the IDs of the members in any order to construct the LinkedHashX – and this works for member additions or deletes. This creates a history independent authenticated data structure, which makes it very easy to gossip and construct set memberships.

You can see this put to use in the Fireflies View maintenance where we use the HexBloom of the View the member is joining to filter out any gossiping of a non View member. This predicate is compact and extremely quick.

Proof Of Occupancy

Using the compact hash of the HexBloom, we get a digest that can uniquely identify the membership of a view. This gives us a solid foundation to prove statements about membership using that digest. In particular, what we need to prove in Gorgoneion attestation is that the group of signatures is the byzantine fault tolerant successor group, correctly calculated from the Context formed from this membership group for a particular View. Recall the diagram I’ve been using wrt rings, BFT and Fireflies:

This diagram demonstrates the process of creating the BFT subset from the rings of the context. In this example, we have five members: {A -> E} The context has three rings (ring count depends logarithmically on the membership cardinality) and every ring has every member mapped to the ring.

Notice that the members appear in different orders on each ring. That is because each ring has a different hash function that maps the member and this mixes up the member ordering – this is key to the construction. These rings are constructed in such a way that (with high probability) the resulting membership rings form a Byzantine Fault Tolerant subsets of the group membership. See the Fireflies thesis for way, way too much information on this topic.

Continuing with this example, say the View above with the 5 members has HexBloom compact digest Q, uniquely identifying the membership of that View. What we need to prove is that using Q, as the View ID the set {D, E, A} forms the BFT subset chosen for digest H. This proof would give us the required foundation to trust that the members {D, E, A} are the BFT authoritative validating signatures on hash H in View Q.

Gorgoneion uses these proofs as part of the validation of Key Events discussed in the previous post, establishing that these signatures were the correct signatures required at the time when the identifier was established.

Identity As Audit Trail

The above process is an audit trail of the view changes and the proof of the members that formed the BFT subset of a unique membership group. To maintain the chain of trust, when the View changes from View A to View B, we have a BFT member subset of View A sign the Hex Bloom of View B. This gives us a forward chain of trust from View to View by having the previous View “witness” or validate the next View.

This audit trail becomes the proof of the continuous BFT identity of the group as it changes membership. We can choose as the representative BFT subset of the group to be defined as the compact hash of the HexBloom of the View. We can use this digest in the same way in the example above to compute the successors of this digest on each ring, resulting in a BFT subset for that compact hash digest. We can use this subset as the “authoritative” BFT group for the View itself.

This gives us a deterministic way to select our BFT subset from the membership, knowing only the compact hash and the membership set. What we need is way to compactly prove that this set was indeed the authoritative BFT subset for a given hash, and prove such in the future, after the membership set has changed.

Super-efficient Aggregating History-independent PADs

Serendipitously, I recently came across a rather useful paper that I believe provides a significant part of the solution that Gorgoneion requires in Super-efficient Aggregating History-independent Persistent Authenticated Dictionaries. This paper describes a number of strategies we can use to construct proofs of precisely the kind that are required by Gorgoneion. These proofs are constant size with time (a very necessary property), using the accumulator strategy of section 4.4. I plan on using the HexBloom instead of the RSA accumulator, but it’s the same idea – just simpler and way more compact.

What was useful for me, from a conceptualization point of view, was the addition of the data structure the Gorgoneion cluster maintains for these historical proofs of BFT authority to work. The diagram below illustrates the Tuple Persistent Authenticated Dictionaries as an incredibly efficient way to keep track of the membership’s IDs in an evolving structure.

Basically it’s a way of encoding the intervals of digests distributed on a ring and serves as a better alternative to a Merkle Tree for the purposes of Gorgoneion. The data structure is composed of snapshots, representing members entering and leaving and the changes to the structure of the intervals as the group evolves – the trace of the evolution of the group membership.

We note that this data structure is history independent, meaning that it doesn’t depend on update order. This makes it really easy to gossip and distribute. As it already is an authenticated data structure, we can also securely gossip this data, ensuring wide spread diffusion of the membership View evolution via gossip between the members. This provides a quick, load balanced bootstrapping of the data structure and this can also be done securely and in a BFT fashion as well – naturally.

Thus the Gorgoneion cluster members gain another piece of distributed state that they’re maintaining – lol. This state forms the basis of proofs we can issue that prove the authoritative BFT membership of a given hash value. Using these proofs, we can prove that the members signing a Key Event are the authoritative members for that Key Event and do so at any time in the future for a correctly maintained group.

Which…. is pretty cool. I really hadn’t thought that would work out so well, but – at least for the moment – it appears to have done exactly that. We can leverage small, constant size proofs that leverage the HexBloom as BFT threshold signature sets to establish trust. The Gorgoneion cluster maintains a Persistent Authenticated Dictionary defining its membership views and the group maintains historical records required to prove these attestations in the future.

Not a small accomplishment. Still have to build it, of course. I think it should be straightforward, given the other gossip n’ replication work I’ve done so far. But we’ll see. Who knows what surprises lay in store for me when the code starts to execute?