S-Trilogy, Part Three: Direct Acyclic Graph, IOTA and Byteball

This space marks the final article in the S-trilogy – a series of articles focused on blockchain scalability. If you have missed the previous ones, we would highly recommend you to read them by clicking here, and here.

In the bitcoin blockchain, a block is created every 10 minutes and the size limit of a block is 1 MB. This limits the total number of transactions possible in a particular period of time. As we know from our previous articles in the S-series, Ethereum has better throughput than Bitcoin, but it is limited by the block gas limit. Many different projects such as Plasma, Raiden and Lightning Network are trying to solve this problem, as explained in the previous part of this series. This article will take our discussion further, and talk about directed acyclic graph.

Directed Acyclic Graph (DAG)

Directed acyclic graph solves the issue of scalability by taking a totally different approach. There are no blocks and no concept of mining. In a directed acyclic graph, one transaction validates the other to get approved. So, instead of a miner validating all the transaction in a block as in the case of blockchain, each new transaction validates old transactions in DAG. Every new transaction adds to the security of the directed acyclic graph. This results in a graph like structure instead of a chain of blocks.

So, what is a directed acyclic graph ?

A directed acyclic graph is composed of vertices and edges. Vertices represent transactions. An edge is directed from the new transaction (child) to a transaction (parent) it has validated. The first transaction of the network is the Genesis transaction. A parent vertex will never validate a child vertex which makes the graph acyclic. Transactions that don’t have any child transactions are referred as tips.

The graph is directed and acyclic, and hence the name.

If there is a directed edge from transaction A to transaction B, then we could say transaction A directly approves transaction B. If the length of the path from A to B is more than one, we could say transaction A indirectly approves transaction B.

Directed acyclic graph is also based on peer-to-peer network similar to blockchain. In DAG, nodes are distributed throughout the world. Each of them maintain their own copy of the ledger. The transactions are added in a fraction of time in the network. Thus, the DAG network is asynchronous, which makes the system fast. In a directed acyclic graph, you can have a bunch of transactions in parallel and the degree of parallelism adapts dynamically to the current load.

In case of blockchain, the blocks are linked linearly. Their spacing in time and their size are optimized for near-synchrony among nodes. This leads to a cap on the block size which results in a cap on the throughput of the network. If we increase the block size as per traffic, it takes too long for a block to propagate to all nodes in the network. In such situations, there is greater uncertainty about which block is the last block to be added to the network. This leads to chain reorganisation, as discussed in the part one of S-trilogy. More resources are wasted on extending chains that would later be orphaned.

To understand the technology, we will go through two hot projects currently based on DAG – IOTA and Byteball. The mechanism behind these two projects will also help you understand how directed acyclic graph solves the double spending problem .

IOTA

IOTA is, by design, a cryptocurrency for the Internet-of-Things (IoT) industry. The importance of micro-payments is indispensable in the rapidly developing IoT industry, and to pay a fee that is larger than the amount of the value being transferred is not logical. This makes blockchain-based cryptocurrencies such as Bitcoin and Ether unsuitable for such transactions. IOTA is based on DAG which is referred as Tangle in their whitepaper.

Instead of a miner validating a transaction, in IOTA, each transaction must validate at least two previous transactions to get approved. This is analogous to an examination hall where, instead of an invigilator checking for cheating in an exam, each student is programmed in a way that he checks at least two unchecked students.

Weight of a Transaction

There are two types of weights associated with a transaction. First is the transaction’s own weight and second is the cumulative weight.

• Transaction’s own weight refers to the amount of work (POW) put in by the node in issuing that transaction. This weight can only be in the form of 3^n.
• Cumulative weight of a transaction is the sum of its own weight and the self weights of all transactions directly or indirectly approving it. Cumulative weight is very important term as it represents the importance of a transaction.  More the weight of a transaction, less likely for it is to get orphaned.

In above figure, each transaction has cumulative weight and its own weight. Cumulative weight is represented in bold and the self weight is represented in the bottom right corner of that transaction.

For example, Transaction B has own weight of three and cumulative weight of four. Cumulative weight of B = own weight of B + own weight of A, since, A is the only transaction approving it.

In the above figure, when a new transaction X with its own weight equal to three is added to the tangle it approves tips A and C. It directly or indirectly increases the cumulative weight of every transaction by three.

Score of a Transaction

The score of a transaction = Sum of own weights of all transactions approved by this transaction + Own weight of the transaction itself.

Score of transaction A = own weight of transactions D,B,F,G + A’s own weight = 9
Score of transaction C = own weight of transactions D,E,F,G + C’s own weight = 7

Height of a transaction

Length of the longest path from the transaction to genesis transaction of Tangle.

Depth of a transaction

Length of the longest path from some tip to the transaction.

Lazy tip

A node might not want to keep up to date with the current state of the ledger. It might approve same old two transactions for all of its own new transactions. Such new transactions are called lazy tips. Also, this behavior is not appreciated as no new transactions are getting validated by this node. New transactions from honest and hard working nodes must not approve such tips.

Tip selection algorithm

The strategy for determining the two tips to approve is very important, and is the key to IOTA’s unique technology. Since there are usually no ways to enforce a particular tip selection strategy, there must be a good reason for nodes to voluntarily choose to follow a common strategy. A possible reason is knowing that a good portion of other nodes are following the same strategy.

If we choose any 2 random tips then our problem of lazy tips will not be solved. To solve this problem IOTA uses weighted random walks as described below.

In this algorithm, we start a walk from the genesis transaction towards the tips. At each transaction, we choose one of the transactions directly approving this transaction. More the cumulative weight of a transaction more is the probability of choosing that transaction. In this way, we ultimately choose a tip for approval.

How does this solve the lazy tip problem?

In figure 6, when we arrive at transaction 3, two transactions approving it are transaction 5 and transaction 14. The cumulative weight of transaction 14 will be much less than that of 5 until and unless 14 has very high own weight. If the cumulative weight of 5 is much more than probability of choosing 14 will become very low. Hence, we will be able to avoid lazy tips.

So, why not choose the transaction with most cumulative weight with the probability of 1?  In figure 6, suppose 4 is the genesis transaction. Transactions 5, 6 and 7 are approving it directly. Assume that the cumulative weight of the transaction 6 is highest. The algorithm will always choose transaction 6. This will cause a problem as the tips 12 and 13 will never be chosen. Thus, some of the transactions may never get approved.

If the probability is too high that might leave transactions unapproved. If the probability is zero that might approve a lazy tip. Thus, the value of probability, represented by α needs to be chosen cautiously. This algorithm is known as Markov Chain Monte Carlo algorithm.

How are IOTA tokens issued? Can someone mine IOTA tokens?

There is no mining of IOTA tokens. All tokens are considered to be present at an address in the beginning which were then transferred to founder addresses in the genesis transaction.

If there are no miners, how are transactions validated? What happens if a conflicting transaction is added in a Tangle?

Each node checks if the approved transactions are conflicting. If a node finds that a transaction is in conflict with the tangle history or it double spends other transaction, the node will not approve the conflicting transaction in either a direct or an indirect manner. If it validates a conflicting transaction, it fears that the majority of honest nodes will not approve the new transaction.

The local ledger of every node stores the conflicting transactions. Nodes don’t have to come to a consensus to decide which transaction has the right to be in a ledger, all they have to decide is to not approve conflicting transactions. The fraud transactions will ultimately get orphaned. An orphaned transaction is not dropped from the ledger. It will still be stored in the ledger.

But no one directly or indirectly approves the orphaned transactions.

In an IoT network, nodes are devices with specialized chips and they all follow the same set of protocols. It is not suitable for an attacker to submit a conflicting transaction. To do so, he must first reconfigure all other nodes to follow different set of protocols. So, it is best for a node to follow the same set of protocols as the rest of the network.

Confirmation Confidence

Suppose A pays to a merchant M in IOTAs for buying shoes. A might have double spent this same transaction to some other merchant also. Fraud transaction will be ultimately orphaned as discussed above. But, it will take some more time after the initial confirmation. 

How will M decide when to deliver shoes to him? 

The merchant can decide this, using the tip selection algorithm. Many iterations of tip selection algorithm are run and the percentage of tips that directly or indirectly approve the specified transaction is calculated. That represents confirmation confidence. If out of 100 tips 80 tips directly or indirectly approve the transaction, confirmation confidence is 80%. More the confidence more difficult to double spent that transaction. Merchant M can set his own criteria. He may fix a criteria that he will deliver only when confirmation confidence is more than 95%.

Byteball

Byteball is a decentralized system for storage and transfer of value. It can store arbitrary data and transferable values such as currencies, shares, property titles etc. All this data is stored in storage units. Likewise, transactions which transfer these values are stored as storage units. To make it easier to grasp, you should consider storage units as transactions for this blog, just as in case of IOTA. This article will also refer to ‘storage units’ just as ‘units’.

Each storage unit includes one or more hashes of earlier storage units. Hence, confirming them and establishing their partial order, i.e., which storage unit was stored first in the ledger. In IOTA , one transaction has to approve at least two other transactions, this is not compulsory in Byteball. A transaction has to confirm one or more storage units. This is discussed in detail ahead.

The set of storage units and their links form a directed acyclic graph.

Storage units are vertices and their links are edges in the graph. As more and more storage units are added older storage units get confirmations directly or indirectly just as in IOTA.

Everyone is allowed to add a new unit, provided that he signs it and pays a fee. Byteball charges fees, unlike IOTA. This fee plays an important role in keeping the system healthy.

Bytes

Bytes is an internal currency in Byteball network. To store 1 byte of data a user has to pay 1 byte. Anyone can issue their own currency which can then be transferred to any other user, just like the internal currency, bytes. All these transactions are stored as storage units. If we compare this with ethereum environment, bytes is similar to Ether and all these other currencies created by users on byteball platform are similar to tokens issued on Ethereum blockchain.

Blackbytes is another currency available on Byteball network. While bytes is easily traceable, it is much more difficult to trace blackbytes.

Fees in Byteball

As we have discussed before, to store some bytes of data a user has to pay equal number of bytes. This prevents spanning of the ledger with useless messages. The more space your unit takes, the more you have to pay.

For the purposes of calculating unit size, we assume that the unit has exactly two parents, irrespective of the number of the real parents. This is to prevent users who try to approve only a single unit to save fees. 

It is good for directed acyclic graph to be as narrow as possible. To achieve this, users are incentivized to confirm as many units as possible and as recent unit as possible. We can achieve this in two ways:

• Even if many parents are added, fees is same, as discussed above.
• A part of the fees that a new unit pays to store its data is payed to the units which include it first as parent. Other part of the fees is paid to witnesses as discussed later.

The total number of bytes in circulation is 10^15, and this number is constant. All bytes are issued in the genesis unit, then transferred from user to user.

Double Spending in Byteball

Two possible scenarios

There is a partial order between the two units that try to spend the same output, i.e. one of the units (directly or indirectly) includes the other unit, and therefore, comes after it. In this case, we can safely reject the later unit.

In figure 7 above, Red unit tries to double spent Green unit but ther is a partial order between these nodes as Red indirectly confirms Green. In this case, we reject the Red unit. There is no partial order between them. In this case, we accept both. We decide the total order between two units using the Main Chain. This is explained in the next section.

Witnesses

The DAG chain does not have a secure timestamp (or block number). The nodes need a reliable source of transactions that are guaranteed to be generated in a defined order. For this we need the help of the witnesses.

Witnesses are a list of users on Byteball who are non-anonymous and reputable people or companies, or their businesses depend on the health of the network. Part of the fees paid by all the users to get their transaction approved is allocated to witnesses. It is reasonable to expect them to behave honestly. It is also unreasonable to totally trust any single witness.

We have a fixed number of 12 witnesses. Even in case of hack or power out situation, Byteball network will be healthy. If anyone of these witnesses tries to cheat, it will be easy to identify which address cheated and as these addresses are non-anonymous everyone will know the deceiver, which will destroy his reputation as well as he will loose the incentive from Byteball. The task for these witnesses is to just post transactions serially i.e with a partial order and post these transactions frequently.

Main Chain

Based on the transactions posted by the witnesses, a single chain along child-parent links is chosen using an algorithm which can be referred from the Byteball whitepaper. We refer to this chain of transactions as Main Chain. All the units either lie on this chain or can be reached from this chain. This chain is like a highway connecting side roads.

The main chain is indexed from 0 (genesis) in an increasing order. The index number is referred as Main Chain Index (MCI). Units with higher MCI directly or indirectly approves all the units with lower MCI. Therefore, all the units lying on the main chain have their total order defined.

To solve the problem of double spent we need true order in all of the units in the DAG.

Total order needs to be defined for units that do not lie on the main chain. The total order of a unit which does not lie on the main chain is equal to the MCI of the unit (on main chain) which first includes the unit directly or indirectly.

The above figure shows two non-serial storage units (shaded in orange), both of these does not lie on the main chain. One of the transactions is first included by unit with MCI 5 and other is included first by unit with MCI 6. One with MCI 5 wins and is valid unit, the other unit is deemed invalid. In case if both the units have the same main chain index there is a tiebreaker rule that the unit with the lower hash value (as represented in base64 encoding) is valid.

Conclusion

This marks the end of S- trilogy. Thank you for diving deep with us into blockchain scalability issues. If you have any questions regarding this article, please contact the author at pgupta@deqode.com or drop your email here.

Sources

• IOTA Whitepaper.
• Byteball Whitepaper.
• https://medium.com/coinmonks/scaling-a-blockchain-vs-scaling-a-tangle-8b7182eda980
• https://hackernoon.com/a-hitchhikers-guide-to-consensus-algorithms-d81aae3eb0e3