Directed Acyclic Graph Topology in Public Distributed Ledgers: Nano, ByteBalls, IOTA

From CoinBureau:

Directed acyclic graphs are a general category in graph theory, computer science and mathematics which essentially constitute a topological ordering where vertices (e.g., a nodes, tasks or events) are coupled with edges (directed arrows, dependency relationships or transactions) in an asynchronous fashion (nodes cannot loop back to themselves but the flow goes in one direction, i.e. directed).

DAGs are applied in modeling many kinds of information where collections of events must be represented in how they influence each other (probabilistic structures in Bayesian networks, records of historical data, distributed revision control systems, etc.)

This departures from the paradigm of blockchain technology in that the blockchain fabric operates by chaining flat sequences of lists and grouping them in blocks. With blockchain, every block references the one before and including it, which leads to bottlenecks when too many transactions begin arriving too frequently.

This makes it difficult to achieve consensus on valid blocks (the notorious scalability issue). In a DAG structured environment there is no theoretical limit on transaction throughput as transactions are directly linked rather than grouped and serialized on a single lane.

The DAG technical design also allows for a broader range of algorithms which could be applied and thus broader flexibility. There are a few DAG-based projects out there, all very different from each other and noteworthy, all having built their codebase from scratch (as opposed to another Bitcoin codebase hack).

Here are some common properties they share:

• Acyclicity: Time flows in one direction. Newer transactions reference older ones, but not the other way around. In cycles group of tasks depend on each other (if there were cycles there wouldn’t be topological ordering). In a DAG, every node depends on previous ones referencing it. This allows that transactions can be executed locally or even off-line and processed, confirmed or finalized at later points.

• Latency: Speed of execution and confirmation times are not constrained by block-size, but bandwidth between communicating peers. There is no theoretical limit to how much the system can scale.

• Feeless (“pre-mined”): Fixed supply, no mining involved. Every transaction issuer is simultaneously a validator, or otherwise there are representatives or witnesses involved in cases of conflicts or disputes. This enables feeless micro and nano transactions limiting environmental impact.

• Zero-value transactions: E.g. messages, or non-value transactions whether or not requiring digital signatures and fitting in a UDP packet.

• Database pruning: Called pruning in Nano and snapshotting in IOTA. No such mechanism yet with Byteballs. It allows for keeping database slim and different nodes can save only the history they are interested in or is relevant to them.

DAG technology has already been used in a number of cryptocurrencies as developers actively look for alternatives to the current blockchain architecture. Below we will look into the underlying technology of three of the most well known DAG based cryptocurrencies.

...following comparison of Nano, Byteballs and IOTA.