IOTA Tangle Graph from http://www.tangleblog.com
Welcome
Hello blockchainer! Today’s topic is an enhanced mutation of blockchain — The Tangle of IOTA.
This post serves as a very beginner-level overview of the crypto with 9th largest market cap , IOTA. All the graphs and contents are fully credit to IOTA’s white paper.
Update:
A speech with topic of IOTA Tangle and Cryptographic Vulnerabilities, delivered by two friends of mine (Alan Yip and Martin Shin) and me, is ready on Youtube: IOTA Tangle and Cryptographic Vulnerabilities
Why IOTA?
Due to the rapid growth of IoT (Internet of Things), the demand for micropayment inevitably lifted off. As you might recall, Bitcoin was devised toward the goal of solving the needs of micropayment, but it turned out to be infeasible in two reasons:
- Heavy fee: As the amount of payment reduces, the relative fee rate rises.
- Separation of roles: Bitcoin requires two types of users: transaction verifier (miners) and transaction issuers (normal users). Lacking the homogeneity among roles, the chance of conflicts remains high, wasting everyone’s resources to solve the conflicts.
Whereas, IOTA Tangle puts forward a better solution.
It replaces Blockchain with a DAG (directed acyclic graph), called Tangle. Figure 1 shows a typical DAG.
Figure 1: Directed Acyclic Graph (from http://ericsink.com/)
What’s Tangle?
Tangle is made of sites and nodes:
- Sites: Transactions represented on the graph.
- Nodes: Issuers of transactions.
Sites are a part of the Tangle graph, containing one or some transactions that relate together. Nodes are the users of IOTA who are eligible to issue transactions.
Key Rule: A newly issued transaction is obligated to approve TWO old transactions. Yes, two.
The responsibility of approving the new transactions belongs to everyone, specifically, the transaction issuers. It removes the special role of miners and brings equality back to all users. NO MORE MINERs!
Relationship between transactions
There are two ways that transaction A can be approved by transaction B. One way is that transaction A is directly approved by transaction B.
Figure 2: Direct Approval of Transaction
Second way allows some transactions (e.g. X, Y) to be placed in between, linking up the indirect relationship of A and B as followed:
Figure 3: Indirect Approval of Transaction
Who started up Tangle?
Genesis transaction is the first transaction in Tangle:
- It is directly/indirectly approved by all other transactions.
- It sends tokens from “an address containing all tokens” to other “founder addresses”.
How to choose transactions to approve?
In the early stage, there is NO such rule for choosing transactions to approve. Nodes are assumed to follow some reference rules since they are usually local devices that belong to the same regions.
What is Tip?
Tip is a newly issued transaction that has not received any approval. An algorithm called tip selection algorithm is used to solve conflicts. It runs many times to check which transaction, of the two conflict transactions, is more likely to be approved by a selected tip.
Tangle is Asynchronous
Tangle can tolerate conflicting transactions that popped up asynchronously. It believes that any incorrect transaction would be automatically orphaned, or erased, as Tangle keeps on growing.
Propagation incentive for nodes
A node will be dropped by its neighbor, when it shows laziness toward propagating transactions. The incentive keeps all nodes working, though they don’t issue transactions that frequent.
Terms that matter
All the following terms are defined as essential attributes of a transaction. Let’s call it transaction A.
Weight (Own weight): The weight of transaction A is proportional to the effort put in by its issuer, which can be assumed to be 3^n.
Cumulative weight: Transaction A’s own weight + the sum of own weights of all the followed transactions that directly/indirectly approve transaction A. (E.g. In figure 4, transaction D has own weight as 1, and cumulative weight as 6 = D’s own weight + A’s own weight + B’ own weight + C’s own weight = 1 + 1 + 3 + 1.)
Figure 4: Weights (from IOTA white paper). Own weights at right-bottom. Cumulative weights at left-top, as bold.
Score: Transaction A’s own weight + the sum of own weights of all previous transactions approved by transaction A. (E.g. In figure 5, transaction A has score as 9 = A’s own weight + B’s own weight + D’s own weight + F’s own weight + G’s own weight = 1 + 3 + 1 + 3 + 1.)
Figure 5: Score (from IOTA white paper). Score at left-top, in the circle.
Height: The length of the longest oriented path to the genesis.
Depth: The length of the longest reverse-oriented path to certain tips.
For instance, in figure 5, the height of D is 3 (D → F → G → genesis), and the depth of D is 2 (D ← B ← A).
What is Cutset?
Let’s assume the average time of issuing a transaction is time H.
Cutset is a group of tips alive at timespan between time t and time t + time H, with the following definition:
- Any path from a new transaction to genesis MUST go through the cutset.
- The smaller the size, the higher the chance that a new transaction can be approved. In the other word, a new transaction has fewer competitors.
- It used as a checkpoint for DAG pruning and other actions taken to control the growth of Tangle.
Strategy of choosing transaction
- Random: Not good, for it does not encourage approving tips.
- Random among the top section (section near tips): Good. Tips have a much higher probability to be selected and approved.
Low load and high load
The load of Tangle determines its efficiency, feasibility, and security.
Low load:
- A small number of tips, usually 1 or 2.
- A weak inflow of transactions.
- Happened when: low network latency and great computational power.
High load:
- A large number of tips. Depends on the strategy of choosing transaction.
- A strong inflow of transaction.
- Happened when: high network latency and low computational power, forcing several new transactions to turn to approve the same tips.
- Disadvantage: Some transactions might need to wait for a long while before being approved.
Figure 6: Low Load and High Load (from IOTA white paper).
Problem of High Load
In high load, an unapproved transaction can be missed out, and no longer have the chance to be approved.
- Great solution (white paper v1.2): The owner of transaction can reattach or rebroadcast the transaction, knowing that the tokens will not be sent until the transaction is approved. Any duplicate copies via reattach/rebroadcast will be discarded later. [source 2.6]
- Great solution (white paper v0.6): The owner of transaction issues a new empty transaction referencing the missed transaction, so as to help it get approved.
- OK solution: Pick some random tips and approve the top ones, leaving a better chance that the missed transaction might be approved soon.
How fast the Tangle grow?
The speed of growth of the cumulative weight of a given transaction can be examined in two different load contexts:
- Low load: Grow at constant speed.
- High load: Grow with increasing speed during adaptation period, and return to a constant speed after the period. For the reason that all new transactions will be guaranteed to indirectly approve this transaction. Shown in figure 7.
Figure 7: Growth speed of cumulative weight for a transaction in high load environment (From IOTA white paper).
Attacks and Countermeasures
Stay tuned! This section is to be discussed in the next post soon. :)
Conclusion
From the white paper, it can be seen that IOTA Tangle deviates from blockchain and creates its own way of selecting and approving transactions. There is no more miners, and no more blocks. As a DAG implementation, lots of interesting statistics can be computed by nodes to have more insights of its neighbors and the network itself.
Aside from the benefits and drawbacks of IOTA, there are far more to be discussed about the potential threats that might overthrow the rosy prospect, and the possible countermeasures that could save it from ruins. Nevertheless, the invention of IOTA still proves its worth.
To delve into the details and mathematics, IOTA white paper is here to help!
Thanks!!
Thanks for your time! Please leave some applauses if you like the post. ;p
Feel free to correct me if I got anything wrong. Leave your comments~