In this part of the blog post I want to finally talk about the new voting scheme that enables nodes to come to an agreement without exchanging additional votes or having to abandon transactions.
Overview of the status quo
Currently a transaction in IOTA can only mean one thing: It “approves” two referenced transactions, which means that it vouches for the full history of the transactions that it references up till the genesis. Since transactions can only express “total approval”, the only way to deal with “disapproval” is to abandon the “bad” parts of the tangle.
This is not very beneficial for a voting mechanism because the outcome of the voting is not clear upfront (as the word “voting” implies). We would consequently have to abandon parts of the tangle, if nodes would attach to transactions that are not immediately in line with the majority opinion. This increases the need for reattachments and allows an attacker to harm the network (by spamming conflicts), even if a double spend would ultimately not be successful.
In fact, this is even a huge game theoretical problem. Let me quote Alexander Skidanov, who has mentioned this problem when he analyzed Avalanche who also uses a DAG to inherit votes:
The transaction itself, is only considered approved if all the transactions in its Ancestry are approved. Thus, the transaction poster has a strong incentive to have as few transactions in the Ancestry as possible, in the extreme case only referencing the genesis. If they only reference the genesis, and don’t have any double posting, their transaction is guaranteed to be accepted, while if they reference someone else’s transaction, there’s a chance their transaction will get rejected because of the referenced transactions. The more transactions are in the ancestry, the higher is the chance of rejection. Thus, without some other incentives all reasonable actors will always only reference the genesis in their transactions, creating a very wide and very shallow graph.
If we want to make a decision about new transactions, we want people to attach to these undecided transactions and vote on their fate. But if voting on an undecided transaction lowers the chances of a transaction to be accepted, then there is no incentive to vote in the first place, which means that the whole protocol has a very strong incentive problem.
IOTA originally tried to solve this problem by making the tip selection use a “cumulative weight based random walk”, which means that honest nodes prefer to choose tips that are very far away from the genesis. Attaching somewhere that is not close to the tips would consequently lower a transactions chance to be picked up by others, which forced people to follow the protocol. This indeed solves the problem but it also has a few undesired side effects:
- Calculating the cumulative weight is expensive and doesn’t scale very well.
- Honest transactions have a chance to be left behind even though they are not even attaching to a conflicting transactions (i.e. because they were unlucky and didn’t gain enough weight).
- The random walk is gameable and opens up all kinds of attack vectors (like parasite chain attacks, blow ball attacks and so on).
Since the random walk is one of the biggest bottlenecks of IOTA and we would consequently like to get rid of it, we need to find a way for nodes to express their opinion without having to be worried about their transactions being abandoned later on.
The new voting scheme
To achieve this, we will change the way the tangle is read by introducing another ontology on top of the tangle, that will allow us to vote without having to abandon transactions.
1. Tracking opinions of transactions using realities
As explained in the earlier parts of this blog post, every transaction belongs to a particular reality. This reality is independent from its attachment location and only depends on the origin of the funds that the transaction is moving (“tangle inside the tangle”). Honest transactions that are not double spending and data transactions will always belong to the master reality. We call this reality the funds origin reality.
In addition, every transaction has a second reality that reflects its opinion. It is inherited from the parents and is calculated by aggregating the opinion realities of the referenced transactions with its own funds origin reality. This opinion reality represents the reality that a transaction is voting for. Since realities are organized in a hierarchical way, a transaction automatically also votes for all the parent realities that are ancestors of this opinion reality.
This sounds a little complicated but it essentially just describes the fact, that a transaction that “approves” a conflicting transaction will inherit the reality of this conflicting transactions as its opinion.
Let’s look at an example how the opinion gets inherited:
Note: The rules for aggregating realities has already been described in the second part of this blog post.
2. Polymorphic transactions
The previous example shows the equivalent of how the tangle works today, where transactions always inherit their parents perception of the ledger state (opinion). If the “CONFLICT” would be rejected and consequently abandoned, then all of its approvers would also have to be abandoned.
To work around this problem, we introduce an additional flag in the metadata of every transaction — the branch like switch — which allows us to change the meaning of the branch reference:
Partially Liked: The issuer of the transaction likes the funds origin reality but does not like the stated opinion — i.e. an honest transaction approving the “wrong” (from the point of view of the tx issuer) double spend. The opinion of the branch is accordingly not included when aggregating a transactions opinion.
Strongly Liked: The issuer of the transaction likes the opinion of the transaction (and consequently includes the opinion when aggregating its own opinion). Note, that the opinion automatically contains the funds origin.
Let’s look at the same example from before, but this time TX4, TX7 and TX8 are not agreeing with the perception that “CONFLICT” is the transaction that should become part of the ledger state and they set the branch like switch accordingly:
Note: We limit this switch to the branch, because we can not infer a lot of “knowledge” from a partial like and we want transactions to always make at least one statement about what they like (using their trunk). A partial like simply allows us to reference transactions that would otherwise have to be abandoned.
3. Local modifier based initial opinion
To determine the initial opinion of a node, we use a similar local modifier based rule as in our current coordicide solution: In case of conflicts, a node initially “likes” the reality of the transaction that it has seen first.
4. Tip Selection Algorithm
In the original white paper version of the tangle, the tip selection algorithm was a very crucial part of the consensus because it had to “count” the votes (find the heaviest sub tangle) before being able to hand out the tips for attachments. This counting of votes was an extremely heavy operation because it required us to do a random walk and therefore created a massive bottleneck for the scalability of the protocol.
In this new proposal, I want to decouple the tip selection and the consensus which allows us to build a much simpler and much more robust algorithm that can not be gamed by attacking the structure of the tangle.
The only purpose of the new tip selection algorithm is to allow nodes to efficiently vote and express their current opinion.
It works like this:
- We maintain two lists of tips: strongly liked and partially liked.
- We select the trunk uniformly at random from the list of strongly liked tips.
If the list of partially liked tips is empty:
- We choose the branch also from the list of strongly liked tips.
- We set the branch like switch to 1 — the transaction strongly likes both of the referenced transactions.
If the list of partially liked tips is not empty:
- We choose the branch from the list of partially liked tips.
- We set the branch like switch to 0— the transaction strongly likes the trunk and partially likes the branch.
As soon as a transaction becomes solid, we determine its funds origin and its opinion.
If we like the opinion of the transaction:
- We remove the referenced transactions from their corresponding tips list and add the new transactions to our list of strongly liked tips.
If we do not like the opinion of the transaction, but we like its funds origin:
- We add the new transaction to our list of partially liked tips.
This simple algorithm allows nodes to express their current opinion in a very efficient way without having to do any random walks.
5. The Future Liked Cone (FLC)
In our current perception of the tangle, we already have the concept of the future cone of a transaction, which describes all of the transactions that directly or indirectly reference a certain transaction.
Following this idea, we define the “Future Liked Cone” (FLC) to contain all of the transactions that directly or indirectly “like” a transaction.
A transaction directly or indirectly likes another transaction, if there exists a path towards the referenced transaction that consists either:
- solely out of “strongly liked” references or
- solely out of “strongly liked” references with a single “partially liked” reference at its end
To understand what this means, I want to show a short example how a double spend would look like using the mechanisms described so far. We start with a “healthy tangle” that doesn’t contain any conflicts (the different colors represent transactions from different nodes — this will be relevant later):
Now let’s assume that a double spend tx2 arrives, that is conflicting with an earlier transaction tx1. Lets furthermore assume, that an honest transaction attaches to tx2 (because it had a bad connection and saw the second transaction first). The nodes that prefer the first transaction are still able to reference the honest transaction, even tho it is behind the disliked double spend (by using the branch like switch — dashed line):
The FLC of both conflicting transactions looks like this:
The concept of the FLC will play an important role in the following building blocks.
6. Cumulative weight (based on mana)
Our last new concept before talking about the actual consensus rules is the mana based cumulative weight which will allow us to decide between conflicting realities.
In contrast to the white paper version we however don’t need the cumulative weight of every single transaction — we only need to calculate the cumulative weight of the reality as a whole (represented by its FLC).
To do that, we simply walk through its FLC and make a unique list of all the nodes that “support”” this FLC. The accumulated mana of the nodes in this list is the “cumulative weight” of this reality.
Note: In fact, we don’t even have to walk the tangle for this, since we can already maintain this unique list of nodes while transactions are being attached to this reality (on arrival / solidification). The opinion of transactions, tells us to which FLC they belong.
Let’s look at the earlier example and let’s compare the cumulative weight of the two FLCs (every node is represented by a different color):
7. Numbered transactions and changing opinions
So far we have defined, how nodes can cast votes (Tip Selection) and how we can count the votes (cumulative weight of the FLC), but to reach consensus, we need to allow nodes to change their opinion.
The basic idea is that later votes will replace earlier votes if they express a different opinion.
We therefore need to be able to tell which vote was the later one (preferably without doing an “expensive” random walk). An easy and straight forward way to do this is by making nodes include an ever increasing nonce as a transaction counter in their transactions. They start with a counter value of 0 and increase it whenever they issue a transaction.
Note: This per-node-transaction-counter is also beneficial for the rate control and spam protection.
Whenever we receive a transaction that likes a different reality of the same conflict set, we remove it from the unique list of “supporters” of the old reality and instead add it to the unique list of “supporters” of the new reality — this way the weight of realities can change (and in combination with the consensus rules tip to one majority opinion).
8. Consensus rule — the heaviest reality wins
Now we only need to define when and how a nodes changes its opinion (the actual consensus mechanism).
The consensus rule is very simple: The heaviest reality wins. If no reality is heavier than another reality, we decide based on sorting the hashes of the transactions that created the realities (and choosing the first one).
Let’s look at our previous example of a conflict in the tangle and see how nodes change their opinion:
The purple node (that initially favored tx2), now adjusted its opinion to follow the heavier reality and attached his new transaction accordingly. Since its later vote replaces the earlier one, it is now counted towards the accumulated mana of the other FLC.
Since every node follows the same behavior, the algorithm tips extremely fast. As soon as one reality is slightly favored, the whole network will instantly follow suit with its next transactions. Most of the times, the difference in mana of the issuing nodes of the conflicting transactions themselves might already be a big enough tie breaker for the tipping to start.
Even in situations where the tipping takes a bit longer, it only affects the consensus of the balance of this particular conflict since the transactions that attach to such a conflict are able to grow their own FLC independently.
9. Faster decisions — collaborative transaction issuing
To be able to make “fast” decisions and reach a fast finality, we need to have big mana holders constantly cast votes. Since forcing them to issue transactions would create a lot of unnecessary overhead for these nodes and the network, we need to find a different way for them to publish their opinion.
One of the ideas is a collaborative transaction issuing process, where nodes that want to issue a transaction first ask a big mana holder for their opinion and then include its answer in the transaction. This way every transaction has two voters (the issuer and a big mana holder) and we receive votes of enough mana relatively fast (more TPS means faster confirmations).
The mana of the the collaboratively issued transaction is shared among the issuing nodes (to create an incentive to answer these kind of requests). This way the big mana holders only need to answer a single request whenever they get chosen as the collaborator, instead of having to answer requests from multiple nodes for every single transaction.
The sharing of mana might in addition create a situation where mana is more evenly distributed in the network.
Summary
The presented voting mechanism works very similar to the original white paper version of the tangle. Instead of using Proof-of-Work to calculate the cumulative weight, we use the mana of the nodes that voted for a certain conflict.
The conflict that received the most votes (that has the heaviest FLC) wins, but instead of abandoning the rejected transactions, we keep them in the tangle through the partially liked references (which allows us to get rid of reattachments and therefore also of the game theoretic problems of a universal random tip selection) — see comparison of the two approaches:
The concept of realities might sounds a bit complex at first but it is essentially just an algorithmic optimization to calculate weights and track the opinions of transactions without having to do “expensive” random walks.
I will add another part to this blog post, where I will discuss attack vectors and analyze what an attacker could possibly do.
