What Is a DAG?
Not to be confused with Australian slang, DAG stands for a “directed acyclic graph.” DAGs consist of:
- Nodes (that represent some object or data)
- Directed edges (arrows) that indicate some kind of relationship between nodes. The arrows in a DAG may not form a cycle (acyclic).
- A root node
- Leaf nodes with no children
Weighted directed acyclic graphs are DAGs with weights assigned to their vertices or edges. Below is an example of a weighted DAG with weights assigned to its vertices in red.
All directed acyclic graphs have at least one topological sorting. A topological sorting of a graph is a linear ordering of the graph’s vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
Several algorithms can determine the topological sorting of a DAG in linear time. These algorithms include Kahn’s algorithm and depth-first search. These algorithms for topological sorting have a linear running time, with big-O notation O(|V| + |E|) where V is the number of nodes and E is the number of edges. A topological ordering of a DAG can be used to compute the shortest path through a weighted DAG, also in linear time. The ability to determine the shortest path in a DAG algorithmically in linear time makes it an appealing graph choice, as the topological-sort shortest path outperforms Dijkstra’s algorithm. Dijkstra’s algorithm for finding the shortest path between nodes in a graph has a worst-case performance of O( |E | + |V | log |V |).
What Is the Tangle?
IOTA is using a DAG as a distributed ledger that its team calls the Tangle to store transactions.
The Tangle consists of:
- Transactions (nodes)
- Approvals / Confirmations (directed edges)
- Note: an indirect approval is when there is no edge between A and B but the path between A and B is greater than or equal to 2
- Genesis Transaction (root)
- Tips (leaf nodes)
Each transaction has a weight that is proportional to the amount of work the issuer (node) invested in it. Currently, the weights can only be values 3ⁿ where n is a positive integer that belongs to a finite interval of acceptable values. Each transaction also has a cumulative weight, which is its own weight plus the sum of the weights of all transactions by which it is approved either directly or indirectly.
Here we have a tangle or DAG in an early state. We can see the genesis transaction A and tip transactions I and G. Transaction D:
- Is approved directly by transactions F and H
- Is approved indirectly by transactions G and I
- Has a weight of 3
- Has a cumulative weight of 9 = 3 (Weight of D) + 3 (Weight of H) + 1 (Weight of I) + 1 (Weight of F) + 1 (Weight of G)
Below, a new transaction K with a weight of 3 is added to the tangle by approving tips I and G, and the cumulative weight (in green) of all other transactions increases by 3 (Weight of K). This notion of cumulative weight underlies the tip-selection algorithm that nodes use to select which transactions to approve in order to add their transactions to the tangle, as the cumulative weight is proportional to the transition probability of the tip.
It’s worth mentioning that at the beginning of the Tangle, a single network address had a balance that contained all 2,779,530,283,277,761 IOTA tokens, and the genesis transaction transferred these tokens to several “founder addresses.” The tokens were sold to investors in an ICO that ran from November 25 to December 21, 2015. There is no mechanism for token mining and no further IOTA tokens will be created.
Issuing a Transaction
In order to issue a transaction into the Tangle, a node has to select two transactions already in the Tangle to approve. These transactions may coincide. The node approves the two selected transactions by verifying their signatures and confirming that they are not conflicting with any of the transactions it approves either directly or indirectly. Then the node performs a cryptographic puzzle as proof of work. The issued transaction is not confirmed in the Tangle until other transactions have confirmed it through the same process. Transactions can be confirmed with either higher or lower certainty. What follows is a more detailed description of this process.
Step 1: Select two transactions to approve / confirm
In order to issue a transaction, the issuing node selects two other transactions in the Tangle. Ideally these two other transactions are as-yet-unconfirmed tips, selected using the Markov Chain Monte Carlo (MCMC) tip-selection algorithm.
The Markov Chain Monte Carlo algorithm is local, and works as follows:
- Consider all transactions in a subset of the Tangle with a cumulative weight between L and 2L (where L is large);
- Independently place N particles on N transactions in that interval (N is small—for example, 10);
- Let these particles perform discrete time random walks towards tips—meaning a transition from transaction x to transaction y is possible if and only if y approves x;
Let the two random walkers that reach the tip set first determine which two tips to approve. However, the algorithm will have to discard random walkers that reach tips too early as they may have landed on “lazy tips”—transactions that selected confirmed transactions to confirm rather than unconfirmed tips.
Let’s imagine that this is our tangle state:
The tangle above illustrates certain concepts:
- The green transactions (a–m) are considered fully confirmed, meaning their cumulative weight is high enough that they are confirmed with a high level of certainty, and it is highly likely that any newly added transaction will indirectly confirm these transactions.
- The blue transactions (n–u) are considered partially confirmed, meaning their cumulative weight is not high enough for them to be considered confirmed with a high level of certainty.
- The grey transactions (v–y) are newly added, unconfirmed transactions, also called tips.
- The orange transaction (z) is a lazy tip because it selected already confirmed transactions rather than tips to confirm. Perhaps the node that issued this transaction did not follow the MCMC tip-selection algorithm, or perhaps it experienced network delays. Either way, it is likely that other nodes using the MCMC tip-selection algorithm will discard this tip from consideration when selecting tips from the tangle to confirm, and will penalize this transaction tip for its laziness. This incentivizes nodes to confirm the latest tips, therefore contributing to the tangle by helping new transactions to become fully confirmed.
When issuing a transaction, a node can set a threshold for probability of approval, and can create a probability heuristic that shows how likely that tip is to be selected (and therefore approved) by other nodes using the tip-selection algorithm. If the tip’s probability heuristic is acceptable (i.e., greater than the desired threshold), the tip is selected.
Tip-selection strategies are the most important ingredient for IOTA because they prevent attack vectors. Also, since there is no known way of enforcing a tip-selection strategy, it is vital that the tip-selection algorithm incentivizes nodes to voluntarily choose the common strategy. IOTA is not able to force nodes to use a particular algorithm to select certain transactions for approval, but it is better if a large number of issuers (nodes) follow a reference rule (in this case, “Pick unconfirmed tips”). To see more diagrams of the Tangle as new transactions are added, take a look at unofficial IOTA blog Untangled’s helpful presentation.
The assumption is that since IOTA’s primary use case is the Internet of Things, its nodes will be specialized chips with preinstalled software. Furthermore, the tip-selection algorithm should incentivize use of the reference rule (by, for example, discarding tips reached too early). Take a look at Areas of Concern below for more discussion of the tip-selection algorithm.
Step 2: Verify the two selected transactions
The issuing node verifies each of the two selected transactions by:
- Confirming the selected transaction’s signature (IOTA uses Winternitz one-time signatures)
- Note: IOTA was using Curl, the first trinary hash function, but since Curl had security vulnerabilities (see Areas of Concern: History of Cryptographic Vulnerabilities), the IOTA team is using Kerl for now, which is Keccak-384 with conversion from 243 trits to 48 bytes (and vice versa) using two’s complement. IOTA is based on trinary instead of binary, and represent trytes as uppercase Latin letters and the number 9 (9A–Z). The IOTA team is also involved with the Jinn Ternary Processor.
- Confirming that the selected tip is not in conflict with any of the connected transactions (directly or indirectly approved)
- Solving a cryptographic puzzle similar to those in the Bitcoin blockchain. This is achieved by finding a nonce such that the hash of that nonce concatenated with some data from the approved transaction has a particular form. This is to prevent spamming.
- Note: “The algorithm for PoW in the IOTA implementation is structured such that the time to find a nonce is not much larger than the time needed for other tasks that are necessary to issue a transaction. The latter part is resistant against quantum computing and therefore give the Tangle much more protection against an adversary with a quantum computer when compared to the blockchain” (Popov, 26–27).
One important thing to note is that the IOTA network is asynchronous, meaning not all issuers (nodes) necessarily see the same set of transactions. The network can contain conflicting transactions, although conflicting transactions will not be selected by issuers (nodes) that are issuing new transactions, and will be orphaned into obscurity. See below for an example of double spending:
In the diagram above, a malicious user added two conflicting transactions (q and t) in different parts of the Tangle in an attempt to double spend. Subsequent nodes (such as r, v, w and y) might only have one of these conflicting transactions in their validation path, so they will approve these transactions. However, at some point, a node will try to issue a transaction (AA) that selects two tips (w, y) that show the conflict and it will consequently fail to confirm the selected tips.
Instead the node will reselect tips until it finds two non-conflicting tips. At some point, the tips of one branch of the Tangle will have higher cumulative weights than those of the other, and that branch’s tips will therefore be selected more frequently than the tips of the other branch. As more and more nodes approve tips from the favored branch, the tips from the other branch will become “old / lazy tips” and will no longer be selected. As a result, the double spend and subsequent transactions (t, y) will never become “fully confirmed.”
As you can see, as new transactions (1 through 7) were added to the Tangle, two branches formed as a result of the conflict caused by the double spend, but the top branch was more favored than the bottom branch. At some point, as the top branch gains in cumulative weight, legitimate nodes using the MCMC tip-selection algorithm will not select tip 7 to confirm. As a result, transactions t, y, 6 and 7 will never become fully confirmed.
The IOTA network incentivizes the propagation of transactions. Each issuer (node) maintains certain statistics, such as how many new transactions it has received from its neighbor. If a neighbor is lazy, it will be dropped. The IOTA team likes to highlight the fact that IOTA is ideal for trading (particular in an IoT environment), because there are no transaction fees, and the network ostensibly offers faster approval times than others. Furthermore, IOTA’s use of Winternitz one-time signatures makes the Tangle resistant to attacks involving a quantum computer.
The IOTA team have created several entities which are briefly mentioned in this section: namely, the IOTA Foundation, the IOTA Data Marketplace, and the IOTA Ecosystem. The IOTA Foundation was officially incorporated in Berlin on November 3, 2017, whereupon it became the first fully regulated, not-for-profit foundation in Germany to be capitalized with a cryptocurrency (IOTA tokens). The IOTA Data Marketplace represents a use case for IOTA that makes it possible to securely store, sell and access data streams. It is currently open for public testing and runs in real time on the IOTA test network. In February 2018, IOTA announced their plans for the IOTA Ecosystem. Due to launch in March, the Ecosystem will serve as a Foundation-led platform and community for developers, startups and hobbyists to share, learn, develop and collaborate on decentralized systems and distributed projects. The IOTA community subsequently donated 20 TI (tera-IOTA) to a fund intended to develop the Ecosystem.
Masked Authenticated Messaging
Last November, IOTA announced Masked Authenticated Messaging (MAM), a second-layer data communication protocol that is currently an experimental module and under peer review. MAM makes it possible to send and receive encrypted data streams over the Tangle. MAM uses a Merkle-tree-based signature, and is described in some depth by IOTA engineer Paul Handy here. For additional information, check out this IOTA Japanese Fan Site deep dive into MAM.
Areas of Concern
This portion of the document summarizes some of the areas of concern that exist within the IOTA community and broader blockchain community. It is up to readers to make their own determinations about the level of concern each topic warrants. Some of these issues are very contentious, while some may become less contentious as the IOTA team is able to publish and run more simulations.
The Controller and Milestones
The Tangle today has a special address called the Coordinator (or “coo,” as the IOTA team affectionately call it). It is controlled by the IOTA Foundation, and it issues transactions called milestones at specific intervals of time. If an existing transaction is approved directly or indirectly by the milestone transaction, then it is automatically treated as confirmed. Additionally, the code for the Coordinator is not open source, so it has not been “peer reviewed” by the community for vulnerabilities. The IOTA team state that they intend to open-source the Coordinator in the near future.
In October, the Coordinator was taken offline temporarily after an unplanned shutdown to protect users from an ongoing attack on the network. When the Coordinator was relaunched, some IOTA users found their token balance was zero and had to go through a claims process to recover their funds.
Opinion: Basically, this means that you should take the whole discussion above about cumulative weight, tip selection and gradual orphaning of conflicting branches with a grain of salt, because it has not been proven in the wild. Instead, the Coordinator’s milestone transaction determines whether a transaction is “fully” confirmed and prunes orphaned branches from the Tangle by issuing snapshots. The IOTA Foundation said it is only using the Coordinator until the network is strong enough to sustain a large-scale attack, but this arguably means that the Tangle is centralized at the moment, and can be (and has been) brought down if the Coordinator is brought down.
Ternary: Hardware Support and Beyond
Once it is mature enough, IOTA intends to return to its trinary hashing function, Curl, in order to make the Tangle resistant to quantum computing. This means that a ternary Curl Hasher (to support IOTA’s Curl) would have to become a standard component in CPUs deployed in IoT environments. Otherwise, IOTA would have to convert binary into ternary in software, which is inefficient and prevents IOTA from benefiting from existing security tools that are designed with binary in mind. Finally, ternary poses a barrier to entry for engineers who are more comfortable and confident working in binary.
Transactions in IOTA are each 10KB (while transactions in Bitcoin are on average 600B). The large size of these transactions raises questions about the technology’s suitability for IoT devices with limited storage.
Number of Tips
As previously mentioned, the success of the tip-selection algorithm determines the success of the Tangle. IOTA’s Markov Chain Monte Carlo (MCMC) tip-selection algorithm is supposed to incentivize issuers (nodes) to use the preferred algorithm, ensure that the majority of unconfirmed tips (transactions) are confirmed in a timely and fair manner and be resilient against attack vectors.
Because there is no way to force issuers (nodes) to use the recommended MCMC tip-selection algorithm, there is a concern that selfish issuers (nodes) might use a different, greedy tip-selection algorithm that could result in a narrow Tangle, as shown below. This narrow chain would render IOTA ineffective as a distributed ledger, since many sub-chains of transactions would be orphaned and left unconfirmed.
The IOTA Foundation ran some simulations with its MCMC tip-selection algorithm in the Tangle and presented the preliminary results in a paper on November 6, 2017. The IOTA white paper predicted that the total number of tips L(t) in the system at time t would fluctuate around a constant value and not escape to infinity. The white paper made a series of other predictions, all predicated on the assumption that issuers (nodes) would use a random tip-selection algorithm, rather than the MCMC tip-selection algorithm favored in the live IOTA system. The simulation of the Tangle using the MCMC tip-selection algorithm differs from the white paper’s predictions. Specifically, note that when α increases from 0.001 to 5, the number of tips goes from a widely fluctuating average to a linear function that grows significantly over time.
The IOTA team believes that the discrepancy is a result of differences between the continuous model described in the white paper and the discrete model used in the simulation. Team members plan to explore these differences in the future.
Opinion: A reasonable concern is that IOTA’s MCMC tip-selection algorithm, along with other, greedy tip-selection algorithms, may result in a narrow Tangle and that the number of tips, even in a perfect world with every issuer (node) using the MCMC tip-selection algorithm, will increase linearly over time, instead of hovering at an average.
Serguei Popov and the IOTA team address these concerns in two Medium posts (Part 1, Part 2) and an academic white paper. Popov maintains that the Tangle team proved the existence of a Nash equilibrium in the non-cooperative game where some issuers (nodes) choose a greedy tip-selection strategy to minimize their cost. They also proved that if the number of issuers (nodes) is large, all Nash equilibria are almost symmetric, meaning the costs of all issuers (nodes) are roughly the same. They then used this fact to assume that some fraction of the issuers (nodes) choose the same greedy strategy, because running IOTA simulations in which many issuers (nodes) use different strategies would be infeasible. This may leave a large leap of faith between the simulations and the real world, as it is completely likely that many issuers (nodes) will use many different greedy strategies, particularly in an IoT environment where the relative costs of different strategies might be different. The IOTA team’s preliminary simulations ran samples of approximately 50,000 transactions over the course of a couple of weeks on an Intel Xeon 12 core 3.20 Ghz processor, varying the arrival rate of new transactions (λ), the cost (similar to the average time needed for a transaction to be confirmed), the randomness (α) of the MCMC tip-selection algorithm, the network propagation delay ( h ), and the percentage of issuers (nodes) behaving selfishly (γ).
The IOTA team claims to have found that even when a large fraction of issuers (nodes) choose a greedy tip-selection strategy, they do not have much to gain by being selfish, and that non-selfish issuers (nodes) do not significantly lose efficiency by the presence of the greedy issuers (nodes).
However, they still have not been able to show that the IOTA Tangle can survive these greedy issuers (nodes) without becoming “narrow.” And they mentioned that the result does not hold for a higher α . Furthermore, they mentioned that these are averages, not distributions of the issuer’s (node’s) cost—meaning these lines could be hiding several very high-cost transactions if low-cost transactions evened them out. A network in which some transactions sometimes take a very long time to be confirmed, while at other times are confirmed very quickly, does not provide a reliable way for an individual to make transactions.
It’s worth mentioning that the IOTA team has been growing. Since January 2018, IOTA has opened a Tel Aviv office and the following people (or “mathemagicians,” as per IOTA) have joined the project:
- Darcy Gabriel Augusto Camargo Cunha, mathematician, Ph.D, supervisee of Serguei Popov (co-founder of IOTA)
- Koen Maris, CTO in the field of cyber security for Atos with a background in software engineering, ethical hacking and security solutions integration.
- Alon Gal, physicist, developer and entrepreneur; master’s in physics; previously worked as software engineer at Microsoft and founded Eureka (no longer active)
- Andreas Mikolajewski, professional software engineer since age 17, master‘s in computer science
- Johann Jungwirth, former chief digital officer of Volkswagen AG (joined the IOTA Foundation)
- Charlie Varley, master’s in computer science, created the Trinity Wallet for his thesis. The Trinity Wallet has now been absorbed by the IOTA Foundation
- Alisa Maas, background in the mobility sector, experienced product and marketing manager
- Matthew Darnell, IOTA community and distributed ledger technology veteran
- Mark Sulavka and his core team. Mr. Sulavka is the former chairman and CEO of the National Stock Exchange (original site no longer active). He brings with him Jeffrey Diedrich, Kenny Byrne, Egor Agafonov and Mark Kenna
With any luck, the IOTA team will be able to prove in the near future that its tip-selection algorithm will result in a non-narrow Tangle despite greedy issuers (nodes), thanks in part to these new team members.
History of Cryptographic Vulnerabilities and War of Words With MIT Digital Currency Initiative
In August 2017, the MIT Digital Currency Initiative took a look at the IOTA source code and found that the IOTA hash function Curl produced collisions when different inputs hash to the same output. The team developed an attack by means of which they were able to forge signatures on IOTA payments. The full vulnerability report can be read here and is explained in a blog post by Neha Narula, director of the Digital Currency Initiative at the MIT Media Lab. Since IOTA’s team was informed about the vulnerabilities of Curl, they have been using Kerl, which is Keccak-384 with conversion from 243 trits to 48 bytes (and vice versa) using two’s complement.
Joichi Ito, an MIT Technology Review board member and director of the MIT Media Lab, published a blog post expressing some concerns about IOTA after the MIT Technology Review published a positive article about it. First, Joichi felt that IOTA has given the perception at times that top-tier companies like Microsoft were partners in their marketplace, when in fact it was merely specific employees of said companies who had been involved in the IOTA marketplace. IOTA has addressed this concern, saying the misperception was created by and spread through the media, not IOTA’s official channels.
The IOTA team has a lot of issues with Neha Narula and the MIT Media Lab’s vulnerability report, specifically their interests and stakes in IOTA competitors. The best summaries of the IOTA team’s response to this issue are in a four-part post written on their blog and in several posts from IOTA co-founder Sergey Ivancheglo on (what may or may not be) his personal blog (which has now been taken down).
For more information:
This is a selection of additional resources that may be helpful or of interest to anyone who would like to dig deeper into IOTA and some of the topics discussed in this paper.
- https://nxtforum.org/proof-of-stake-algorithm/dag-a-generalized-blockchain/ (requires creating a free account to access)
IOTA Resources and References
Conversations Within the Community
Areas of Concern