[COSCUP Lecture] Data Structure and Consensus Innovation of IOTA
I would like to thank the organizers for inviting me to share IOTA at the Taiwan Open source community conference (COSCUP2022) and for making IOTA appear in COSCUP for two consecutive years. The topic of my lecture, “A Leaderless DAG and reality-based UTXO Ledger”, is to discuss the academic research results of IOTA in a profound and simple way (Note 1), from the innovation of data structure to the innovation of consensus mechanism. I hope the audience can understand IOTA’s insistence on doing things right from the first principle. Even if the price is lying down for a long time, it does not affect my belief that IOTA technology is THE BEST DLT that can change the world. You can also read the ‘IOTA Taiwan Community Voice Record about the historical conflicts and technological innovations of the ultimate DLT(Chinese)’, ‘DLT and Physics: consensus, time, and data structure(English)’. I hope you can get something from the article/video(Note 2). As usual, please share your comments, forward the article, and even donate.
Note 1: I use the title of the two papers to build my lecture title(Tangle 2.0 Leaderless Nakamoto Consensus on the Heaviest DAG, Reality-based UTXO Ledger）
Note 2: The COSCUP video is still not online, so here I post an article based on the presentation and will update the Youtube link later
UTXO Ledger
This blog will follow the structure to explain the components of the lecture title “A Leaderless DAG and reality-based UTXO Ledger” and to lead people to understand the IOTA in all aspects. First, since we’re talking about Decentralized Ledger Technology(DLT), we have to have a ledger. There are two main types of Ledger: Account and UTXO. Account-based ledger is used to track how much money is in an address, as shown in the figure below on the left. UTXO-based ledger tracks the money in the transaction, like who spent it, and who can now spend it, as shown on the right. The advantage of an Account-based ledger is that it is easy to execute smart contracts, and all instruction can be executed and tracked in sequential form (e.g. Can track who holds the LP token, or can perform multiple actions through a single transaction), basically the public chains that can executes smart contracts (e.g. ETH) are using Account. (the high-speed public chain such as Solana is designed to enhance transaction parallelism to improve performance). The public chain using UTXO architecture includes BTC, ADA, etc. The advantage of UTXO-based ledger is smaller ledger size and allows for native parallel sending transactions (if I have 10 UTXOs to spend, I can send them to 10 addresses at the same time), and the UTXO is mode secure (it’s easy to check double spending and see which UTXO has been used twice which is not the case for Account ledger). The downside is that it’s not suitable for native smart contracts (if it’s like ADA, each eUTXO represents a smart contract that can only be called once per block, the performance is very pathetic).
IOTA originally used Account-based ledger as its Data Structure, but was reborn as UTXO-based ledger in a major upgrade in 2021(IOTA1.5). IOTA sees the inability to natively execute smart contracts as a necessary trade-off in order to become the most secure, high-speed, decentralized DLT: IOTA DAG L1 defines native assets, NFTs, transaction and becomes the Settlement Layer. Then IOTA puts the smart contracts and computing layers in L2(Assembly Network). And even if you can’t run Turing-complete smart contracts in IOTA L1, Time Locked Hash Contracts(TLHC) alone can be used in many interesting ways. For example, in addition to Atomic Swap or Lightning Network, “you can set the expiration Time after sending a transaction” to prevent the exchange from being burned to the wrong address is significant UX improvement.
DLT is about consensus
Next I’d like to talk to you about another aspect of the nature of DLT: building consensus. In addition to the existence of the ledger itself, DLT also requires the nodes to agree on the version of the ledger. After all, avoiding contradictions and achieving consistency is the core requirement of DLT. In the world of blockchain, this problem can be simplified into who “produce block” (POW or POS) : all events is define in the chain of block with global order. And if there is only one block producer in each block to write the ledger, then decide which version ledger to be true is equivalent to how to obtain a block producer for each block.
The longest-chain principle (Nakamoto Consensus), which is common in the blockchain world, is a way to let different nodes who want to be block producer to choose block producer in a permissionless and decentralized way. Each transaction in a blockchain involves both the sender and the receiver plus a global hash. When different nodes come out with blocks and think of themselves as block producer packaging different transactions, the blockchain becomes more like a “block tree” (a bunch of forks), with branches opening up multiple possibilities. After the generation of several blocks, the social consensus of the nodes is the longest-chain principle, which cut off other possibilities, and let the blocks form the blockchain (here will not discuss the possibility of the whole blockchain is under censorship).
Leaderless : solve Blockchain Trilemma with DAG
Blockchain builds consensus efficiently by having block producer(leader) in each block to write the ledger. But it also creates a lot of architectural problems. The leader model has the following problems to overcome: first, the communication complexity. Since only one node is creating the block at the same time, the nodes need to achieve synchronization. And the synchronization speed of the whole ledger is mainly limited by the common gossip model (Solana does have innovation to reduce the communication complexity via POH); then, there is also the waste of the node hardware, where (without sharding) only one node in each block acts as the block producer, representing other nodes in standby or only verifying transactions. Because most of the hardware resources in a blockchain network are not writing the ledger, the network is at most as fast as a single node. That is to say, the increase in the number of nodes cannot make the performance of blockchain network increase easily (the SUI blockchain does use DAG mem pool to create horizontal expansion); The last unavoidable problem of the leader model is fee. When users have no way to update the DLT ledger by themselves, they have to package transactions by giving economic incentives to the block producer. This bottleneck caused by packaging through the block producer node will make it difficult for users to use the blockchain without fee.
Simply put, blockchain generally creates a wealth of possibilities by requiring “global order events” and consensus through “block producer writes the ledger”. However, this architecture resulted in the famous blockchain impossible trilemma: “security, decentralization, performance” can not be achieved simultaneously. From the perspective of the previous analysis, if the blockchain goes through the Nakamoto Consensus and apply “global order events” to achieve security, then the performance of the entire network and decentralization level of the block producer will easily have a trade-off (of course, this is not the “impossible theorem”).
If we think about this problem from a higher level perspective, maybe the blockchain trilemma is just a limitation caused by the blockchain architecture itself. If we change the data structure and consensus, maybe the limitation would be easier to solve. IOTA DAG tries to start from first principles and proposes a paradigm shift of DLT’s quadrulemma : “global order events, security, decentralization, and performance” cannot be reached simultaneously. IOTA DAG pointed out that a good L1 can fully acquire the three properties of blockchain trilemma. This revolution is like we entering the real world of 3D Tetrahedron(below) from the shadow of 2D triangular plane(above). More poetic speaking, we can call the IOTA DAG is a departure from the shadow blockchain world of Plato’s cave. As long as the ledger sacrifice the requirement of ‘global order event’, the potential realization of ‘non-linear/asynchronous ledger’ with ‘leaderless consensus’ is released. And since the security can be achieved through ‘leaderless consensus’(thus no the above mentioned bottleneck), decentralization and performance are no longer mutual exclusion feature. On the contrary, decentralization and performance go hand in hand. As more people use IOTA DAG networks, IOTA DAG network gets more performance.
DAG : Reality-based Consensus
While DAG has the advantage of being able to process transactions in parallel, it is also more prone to ledger conflicts (and global order to solve the conflicts). In order to construct the consensus mechanism applicable to leaderless and asynchronous ledger, IOTA proposes the fourth accounting revolution: After evolving from a single entry bookkeeping , double-entry bookkeeping (with sender/receiver) to a blockchain (with sender/receiver and transaction jash), IOTA assigns each transaction in the ledger to have “sender/receiver, transaction Hash, and node ID (with its Mana)” to create a “reality-based consensus.”
Using the below graph as example, each IOTA transaction (the box) needs to point to the previous transaction, and UTXO must point from the cyan square to the green square. Based on the left-most UTXO DAG, we can find that there are many conflicting transactions. Then we can simplify the UTXO DAG into Conflict DAG in the middle diagram. And draw the Conflict Graph based on which UTXOs (green squares) are pointed to more than once (adjacent boxes in the Conflict Graph represent contradictions). It is important to note here that the upper and lower middle graphs without UTXO information cannot be deduced from each other. Then let’s define “branch” and “reality” : “branch” is made up of transactions without contradiction, so n transactions could produced to in principal exponential amount of “branch”. All the boxes right hand side are “branch”. And the “branch” contains as more as transactions possible without introducing contradiction trading is “reality”. The right hand side Branch DAG has eight “branch” and has four “reality” (“ reality “ is grey box).
The “reality-based consensus” can be illustrated by the following figure: Since each node will contain the corresponding node ID(and its Mana) that sent the transaction when exchanging the transaction message, each node can therefore eliminate the box of Conflict Graph and the “branch” of Confilct DAG based on the node ID. This weight calculation process can be carried out without voting between nodes. In the end, each node will obtain the Conflict Graph without contradiction and the “reality” with the highest weight. By adding a node ID (and Mana) to every transaction in the IOTA DAG network, IOTA has achieved an unprecedented consensus mechanism.
It should also be mentioned that “reality-based consensus” is not the whole IOTA consensus mechanism: Due to the existence of FLP theorem, the non-synchronous deterministic model theoretically cannot obtain ‘fault-tolerant consensus in finite time”. IOTA introduces a on-tangle random number in the protocol layer to create “indeterministic heartbeat”, so that nodes can express their opinions once in finite time to avoid the deadlock of the consensus mechanism.
To conclude this article, I quote Hans Moog’s passionate statement that IOTA’s innovations in data structure and consensus mechanism are not about racing against the crypto bull bear cycle to become the “next L1”, but about striving for perfection and achieving theoretical limit to become the “last L1”.
“The only reason why contemporary DLTs rely on a total order is because they are using a data structure that doesn’t understand conflicts.”- Hans Moog, The Trust Machine — Part3
