The Tech Behind IOTA — Part 2 (Consensus)
I’ve long thought of how to structure these tech series. It’s hard to choose a technical level of proficiency that everyone can follow, because everyone comes from a different background.
If you’re new, take a look at the first article of the series to get a general idea how the Tangle works and how it’s different from a blockchain. (here)
Going further, I will use some technical terms, but you should be able to follow without any problems.
The idea of the consensus algorithm is to structure the Tangle in such a way that every observer can come to a conclusion on what’s valid and what’s not, just by observing the Tangle. Once the Tangle is structured in such a way, nodes will calculate finality locally.
The consensus can be broken down like this:
-A node receives a transaction;
-It checks locally to see if it’s valid;
-If the node thinks the transaction is valid, it appends it to its copy of the Tangle and broadcasts it to its neighbors;
-It includes it in its tip selection algorithm (those are tips(transactions) that the node likes);
-If a node detects a conflict (2 transactions trying to spend the same funds), it reports it;
-If a conflict is reported, nodes vote to resolve the conflict;
-At this point, the node either still thinks the transaction is valid or it knows that it’s a double spend;
-All nodes do this;
-They continue issuing transactions referencing the ones from the tip selection algorithm (those are transactions that they like);
-If a transaction is voted as invalid by FPC (explained below), the tip selection algorithm won’t select it;
-The node calculates locally how many nodes have referenced the transaction;
-When it reaches a certain threshold, it confirms it as final and irreversible;
-This is done for all transactions.
The genius behind IOTA’s consensus in comparison to Nakamoto Consensus in blockchain is that in IOTA, nodes assume a transaction is valid and they only vote on conflicting transactions. In blockchain and Nakamoto Consensus all nodes essentially ask the leader what’s true and they verify the leader’s decision. In IOTA there are no leaders. All nodes issue transactions at the same time.
When nodes assume a transaction is valid, they only check locally and if it is valid, they append it to their copy of the Tangle and gossip it to their neighbors. Later, if they detect a double spend, then they engage in resolving the conflict. They use FPC (Fast Probabilistic Consensus) to come to an agreement. You can read the mathematical proofs (here)
I’ll try to explain how it works in plain language so that the majority can understand it.
When a conflict is reported, nodes have to come to an agreement on what is valid and what is not. They ask random nodes for their opinion and do that multiple times (multiple rounds of voting).
If a supermajority of nodes prefer one transaction, they all come to an agreement that it’s valid with high probability.
If no significant majority of nodes prefer a transaction, then the transaction will be invalid with high probability.
Nodes don’t ask all other nodes for their opinion, rather, only a random subset of nodes.
Nodes with more consensus mana have a bigger say in the network. They will be queried more frequently, so their opinion is more valuable than the opinion of low mana nodes.
High mana nodes will write their opinion in the Tangle and gossip it. They do this to reduce message overhead on their end. They know that nodes will ask for their opinion, so by doing this, they state it only once and make it available for everyone to see. Low mana nodes don’t do this, because only a small number of nodes will ask for their opinion, so it’s more efficient to answer those nodes directly than to gossip their opinion to all nodes that won’t even consider their opinion.
The voting stops individually for each node, when it hasn’t changed its opinion for N consecutive rounds.
This is a simple explanation of how FPC works.
Why can IOTA reach consensus asynchronously?
It’s the property of the data structure. Blockchain is a linear data structure and has a total ordering of transactions. It’s important which transaction came first. Nodes come to consensus not only on the validity of the transactions, but also on the order of those transactions. The Tangle is a nonlinear data structure and it doesn’t have total ordering. Nodes only reach consensus on the validity of transactions and don’t care which transaction was first and which was second within a time frame. I say within a time frame, because within that period of time the order is not known, but you can clearly say that one transaction happened today while another happened yesterday. A double spend attack is only possible within that period of time, when nodes don’t know which transaction came first. If an attacker tries a double spend, he’ll force nodes to vote. If he waits for the transaction to get confirmed and enough time has elapsed between his two transactions, in that case, nodes know that the second transaction came later and it will be rejected without voting. How do we define this time window, when order is not known? Essentially, it’s a multiple of the network delay (I think it’s 2 times the network delay). After that time, you know that all nodes received the transaction. If no conflict was reported, you know that an attacker attempting a double spend in the future came after and will be rejected.
Another important part of this consensus is the tip selection algorithm. Tips are recent transactions that are candidates for new transactions to attach to.
To keep it simple, nodes select tips at random that they like. They reference them in their transactions. When a node receives a transaction from its neighbor, it checks to see if it’s valid and if there is a conflict. If the node accepts the transaction, it checks who issued it and which transactions it references.
This is a key point.
Those references convey enough information to a node, so it knows the opinion of the issuing node. When it gathers enough opinions in this way, it calculates the finality of the transaction. The opinion is weighted by mana, so when a certain threshold is met, the transaction is final and irreversible.
It’s important to note that transactions are only considered tips for a limited time. If they don’t get referenced within that period, they’ll get orphaned and removed from the ledger state.
Conflicting transactions create multiple realities, but only one reality wins. It’s the reality that gets enough approval weight, while other realities are discarded. An efficient way to keep transactions that are attached to discarded realities is to use the “approval reset switch”. In that way, those transactions don’t have to be reattached to the winning (master) reality. I’ve made a video on this topic (here).
A naive approach to calculate the finality of a transaction would be to walk the Tangle and see how many unique nodes referenced it. Sum up their consensus mana and if it’s greater than a certain threshold, the transaction is final. However, this is an inefficient way to calculate approval weight. In IOTA, a concept called “markers” is used to calculate the approval weight efficiently. For those who want to dig into it in more details, check it out (here).
The beautiful thing about the Tangle and this consensus mechanism is that when a transaction is final, it’s irreversible and you can’t go back and revert it. In Nakamoto Consensus, you can. You can go back and produce new blocks, and once that chain becomes longer than the previous one, it wins and the other chain is discarded like it never happened. (In IOTA, conflicting realities get discarded too, however those transactions were never confirmed.)
Transactions that are honest will get confirmed within seconds, because nodes won’t vote on them. No conflict will be detected and they’ll accumulate approval weight quickly. Malicious actors, on the other hand, will have to wait longer for FPC to resolve the conflict, so the nodes agree how to format the Tangle.
For those of you wondering, can an attacker keep issuing conflicting transactions and keep nodes in a voting loop?
No. Every attacker has limited resources, as we all do. He can only try to attack the network with the limited TPS he’s entitled to, based on the mana he possesses. He can choose to waste his TPS by attempting a double spend (he needs 2+ transactions per attempt), or he can choose to do something more productive, like renting his unused TPS for a return. Either way, it’s his choice and the network will successfully mitigate any attempt.
I hope you’ve found this helpful and informative. These posts are available as they are, for free to anyone willing to read them. They resemble my view and understanding. They are not investment advice and for the official research and implementations, please reference IOTA’s official channels. For any questions, reach out to me on twitter (here) or join IOTA’s official Discord (here) where you can interact with the community and ask your questions and concerns.
Luka
