A new “consensus”: The Tangle Multiverse [Part 3]

The full article was originally published by Hans Moog on Medium. Read the full article here.

In the last part we talked about the ledger state, which is used to track and manage conflicts by booking conflicting spends into different git-like branches. The nodes then use virtual voting to decide which one of these branches becomes part of the ledger state.

Before starting to talk about the new voting scheme (finally), I want to take a last detour and talk about some fundamentals around voting based consensus mechanisms because it will help us to judge the proposed solution.

Every consensus requires some form of voting

Nodes in distributed systems see events in a different order. This is due to the fact, that it takes some time for messages to propagate in the network.

According to Einstein’s special theory of relativity, it is impossible to say in an absolute sense that two distinct events occur at the same time if those events are separated in space.

This fact is called the relativity of simultaneity. Since there is no absolute truth regarding the order of events, the only way to anyway agree on some order is to let the nodes vote. Even protocols that do not market themselves as voting based consensus protocols usually still use a form of voting.

In bitcoin for example, the miners who are issuing new blocks, essentially vote on the preferred chain by attaching their newly mined blocks to the chain that (from their perspective) appears to be the longest one. The chain that received the most votes (blocks) is considered to be the correct chain. Since the mining rewards are part of the blocks, miners are incentivized to always mine on the longest chain.

Other consensus mechanisms take a more democratic approach and do not choose a single leader who then get’s to cast his vote but instead try to consider the opinions of a group of nodes.

Voting is “expensive”

Most voting protocols do not scale very well with the amount of consensus nodes – the message overhead is simply getting too big.

This is the reason why protocols like EOS limit the amount of block producers to a very small group. Increasing the amount of block producers would destroy their performance. They essentially trade decentralization for performance.

FPC and CA make different trade-offs and instead of reaching deterministic consensus, they reach probabilistic consensus by asking only a random subset of other nodes. This allows us to vote more efficiently than classical consensus protocols but even here the voting at some point gets problematic.

Example: Imagine that we use FPC, the majority of the mana is held by 50 nodes and we have 10,000 nodes in the network. At 1000 conflicting TPS, these top 50 nodes would have to answer 10 million vote requests per second. This is the reason why we currently consider to make the top mana holders proactively gossip their opinions (i.e. in form of a transaction). This way they would only have to send a single message instead of responding to 10 million requests every second.

In my opinion, this “gossiping of opinions” is however just another form of putting the votes on the tangle and therefore a predecessor of the virtual voting solution that I am proposing.

Note: This is of course an extreme example because 1000 conflicting transactions per second is most probably not the amount of conflicts we would see on an every day basis — but it shows that even probabilistic voting protocols have their limits.

Virtual voting

Virtual voting is a term originally coined by Hashgraph and describes a mechanism where nodes include their opinions in the events that they are anyway sending. This way, there is no additional message overhead for the actual voting, since the events already contain the opinions of the participants in the network.

Even though Hashgraph introduced this term, they are in no way the first ones that used such a voting mechanism. In fact even bitcoin uses a form of virtual voting because the blocks contain the transactions and the vote (the attachment location of the block). Bitcoin consequently does not require an additional voting layer to reach consensus.

To further optimize the voting process, virtual voting based protocols usually depend on the ability to “inherit” votes in their data structure (i.e. in bitcoin every new block votes and vouches for the whole chain of blocks that came before it).

Conclusion

The quest for the holy grail of consensus is therefore essentially a quest for the most efficient voting mechanism.

Virtual voting seems to be very close to the optimal message overhead but so far we haven’t seen a virtual voting protocol, that does not require us to either select a leader first (i.e. block chain) or agree on a fixed size committee (i.e. Hashgraph).

Especially when taking sharding into account, it would be extremely beneficial to not have to agree on a fixed amount of validators upfront.

IOTA for example aims to build a sharding solution that allows every node to individually decide which data and how much of it it wants to process. Every node therefore has a very individual perception of which nodes are the “validators” (high mana nodes) and the protocol needs to “converge” independently of the size of the observed slice of the tangle.

The full article was originally published by Hans Moog on Medium, where people are continuing the conversation by highlighting and responding to this story. Read the full article here.

You might also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. AcceptRead More