Welcome back to our final dive into Consensus Post-Coordicide and what the IOTA world will look like when the Coordinator is no more.  So far, we’ve taken a look at a few “pillars” of research that are coming together slowly but surely.  Ultimately, the goal of the IOTA Project is to provide a decentralized tangle capable of surviving without the current Coordinator (which serves to ensure that malicious actors and their attacks cannot cripple the network or cause nodes to lose trust and leave altogether). 

Consensus Post-Coordicide

Needless to say, the process of removing the final link of centralization is not trivial and has been in the making for quite some time by now.  However, since the stakes are so high, the developers have really put their heads together to develop novel ideas to solve this problem. 

            While we discussed the IOTA transaction approval process in a previous post, it’s important to remember that this is how the network operates currently.  Given the new concepts that have to be integrated in order to complete the Coordicide, the novel method that we’ll cover in this post has to be different and able to function without the Coordinator in place.  Enough talk; let’s get to it!

Transaction Selection

            Remember the tip selection methodology we discovered in the post we linked to above?  It basically centered around a weighted random walk and functions adequately in the current environment.  However, as you might imagine, it’s not the best fit for the developers’ vision of the new tangle.  Let’s take a step back to find out why before looking at two proposed implementations that will be better suited for future utilization.

            Any time a transaction occurs on the network, the nearby nodes know about it almost immediately.  As you can imagine, the short distance between the neighboring nodes allows the information to pass quickly – but what about the nodes that might be quite distant from the original nodes?  There’s going to be a propagation delay before those nodes know anything about what’s happening on the “other side” of the tangle.  Because of this delay, a possibility exists that conflicting transactions can exist on the tangle – and that’s just fine.  The tangle is designed (as detailed in the original white paper) to take care of these conflicting transactions.  The only firm requirement:  the nodes need to come to consensus on which branch should remain.

Efficiency and Orphaned Transactions

            After several iterations of the tip selection algorithm, the network will eventually smooth things out.  All but one of the conflicting branches will be “dropped” from the network and one branch, agreed to by consensus, will remain on the tangle.  This works great, so what’s the problem?  There are two main issues here:  efficiency and dealing with orphaned transactions. 

First, the resolution of conflicts is iterative in nature (i.e., it has to happen over multiple cycles).  Because the tip selection algorithm has to be run over and over, the amount of time it takes to resolve conflicting transactions can be slow.  Yes, it works; but it also can be inefficient and, as the tangle continues to grow, may become unwieldy in the future. 

Second, the transactions that chose the orphaned branch (or maybe consider it the “wrong” branch) have to re-attach to the tangle.  Just because the branch they chose happened to be orphaned doesn’t necessitate that these transactions were anything but valid.  Now they are forced to go through the steps of attaching to the tangle all over again, wasting time and resources that could be devoted to raising goodput on the network (i.e., good throughput or actually getting meaningful tasks accomplished).

Shimmer Consensus Mechanism

            While the currently accepted consensus mechanism in IOTA is perfectly fine for the network now, the developers desire to deploy a more robust system that will not only become more efficient overall but also provide a solid defense against possible attacks.  The Shimmer consensus mechanism (which they also refer to as a “voting scheme” in the Coordicide white paper) is based on a natural phenomenon – the movement of bees.  Wait, bees?  Yep!  The process of “shimmering” by bees is a defense tactic against predators, but the motion of it all works perfectly to describe the way a consensus mechanism can function in IOTA. 

(Go take a look at this video – not only is it incredible, it’s also a great visual to understand the Shimmer we’ll be discussing). 

Figure 1:  An example of a shimmering process.  Image from IOTA.org.

            Essentially, the desire here is to start from a small cluster of neighboring nodes and spread a message throughout the tangle that eventually reaches everyone on the network (all the while providing for both security and correctness).  While it would be nice to know what every node thought about a transaction, it’s basically infeasible in the real world apart from the smallest of networks. 

Different Approach

Let’s take a different approach:  what if we let the small cluster of nodes close to the incipient transaction form an opinion about its validity and pass this information on to the rest of the tangle?  Consensus, then, could be formed as an emergent property of the network in an organic fashion.  This would occur over several iterations as neighboring nodes continued to ask each other’s opinions about the network.  Each respective node would adjust its opinion as the collection of neighbors across the tangle continued to communicate. 

Eventually (and hopefully) the network status would reach a point of stasis or convergence (based on that transaction; however in an active, sizable network it is reasonable to assume that activity will always be present and the network will never completely settle).

Binary Operations

            In the real world, it’s easy for someone to distinguish their opinion for something.  You might like sushi, for instance, but maybe it’s a “pretty good” in your estimation where something like steak would be an “awesome” rating instead and liver would be “no thanks”. 

We are fortunate to be able to express opinions in more than a “yes-or-no” sense.  Nevertheless, it takes a bit of intelligence to distinguish the differences here; computers don’t realize this kind of nuance usually.  They either see the pizza as “good” or “bad” (not that computers are very interested in pizza…).  On the tangle, the developers have chosen to experiment with algorithms that only output a “like” or “dislike” when it comes to transactions. 

While this might seem a bit elementary, imagine the propagation of this binary affinity across many thousands of other nodes at incredible speeds – it makes sense to keep the approval simple so that a very large number of nodes can approve or disapprove and reach consensus in a very short period of time.

Tip Selection

            With this in mind, let’s look at the basic approach the developers wish to take.  Nodes on the network will be tasked with providing a pro-active response to transaction approval as they take place.  If the node doesn’t find any conflicting transactions spent from the same address, the node will like it; otherwise, the node will dislike it.  While still accounting for the tip selection in use, the tangle will simply prune the future tips as they attempt to attach to the tangle (for those transactions that have been disliked). 

On a periodic basis, a voting scheme is applied to every transaction on the tangle.  The nodes all discuss with their neighbors whether or not they definitely like or dislike a transaction.  At this point, the developers have decided to keep things simple – if a transaction is liked, all of the transactions it has approved will be liked and vice versa.  Again, it’s important to keep in mind that the atomic elements should be kept simple so that the network can scale and still work nimbly.

First Probabilistic Consensus

            The IOTA developers are currently looking at two voting mechanisms for accomplishing the tasks of transaction approval and consensus.  The first is called Fast Probabilistic Consensus (FPC).  This mechanism is backed by rigorous mathematical proofs and has been shown to work quite effectively.  The downsides?  Nodes have to accept connections from non-neighboring nodes (potentially a security risk) and specific mathematical components of the consensus require implementing another layer of complexity. 

Cellular Automation Approach

The second voting mechanism is referred to as a cellular automation approach.  While this approach seems to be a bit faster and requires no connections among non-neighboring nodes, it is not backed by the same rigorous mathematical proofs as FPC and necessitates the incorporation of a more stringent autopeering solution.  Want to learn more about these options?  Check out the Coordicide white paper for a detailed explanation – it’s quite an intense read.

Untangling IOTA Series

            We really hope that you’ve enjoyed this series, Untangling IOTA, and this post, Consensus Post-Coordicide, as we have delved into the nuts and bolts of IOTA and taken a glimpse in to the next-generation network we hope to see soon.  There’s still so much more to learn and keep up-to-date with, so check out the official Coordicide site and IOTA’s blog (where much of this topic is discussed) for more.  New information is being released every day as the developers continue to push the boundaries of current distributed ledger technology.  We’ll see you soon, and until then, happy reading and enjoy the ride.

Cheers

The post Untangling IOTA Approval and Consensus Post-Coordicide – Series: Part 8 appeared first on San Francisco Tribe.