LINIX Protocol Technical Spotlight— Partial Order in Directed Acyclic Graph based Digital Ledger Systems

Wei Duong
Wei Duong
Jan 31 · 13 min read

Directed Acyclic Graph, abbreviated as DAG, is a data structure that arises naturally and has many applications in mathematics and computer science, ranging from task scheduling, network flow, to integrated circuit board design.

More recently, DAG has been suggested as the data structure that can be used to replace blockchain in implementing decentralized digital ledger systems.

A Directed Acyclic Graph is a finite directed graph with no directed cycles. A blockchain is, in fact, a specific kind of Directed Acyclic Graph, where each vertex only links to one other vertex and forms a linear chain in shape; in this sense, DAG can be seen as a generalization of a blockchain structure.

Current State

The main idea of existing DAG based digital ledgers is the following: to issue a transaction, participant nodes must work to approve previously issued unconfirmed transactions. When proposing a new transaction, the participant node can be assumed to be performing work to validate previous transactions that the new transaction is linking to. If a node finds that a transaction is in conflict with the history of the graph, the node will not approve the conflicting transaction in either a direct or indirect manner.

However, there are fundamental limitation to current DAG based ledgers.

No Accessible Global State. Unlike traditional blockchain based ledgers, network participants in a DAG ledger do not necessarily have an easily accessible global view of the entire ledger at any given point in time. Participant nodes only need to have state information of a portion of the graph to propose new transactions, and to require knowledge of the global state would mean sacrificing the scaling advantages of a DAG based ledger over a blockchain based ledger.

However, without knowledge of the global state, it becomes impossible to safely shard the network without creating vulnerabilities to double spending attacks. An attacker could simply present a transaction to multiple shards that don’t have a shared view of each other, and the transaction would be considered valid on all shards. The problem exacerbates as the DAG scales up and shards have a smaller chance of overlapping with each other.

A potential solution is to store an updated view of the global state on some of the nodes, however this leads to the next problem.

Centralization. Some DAG based ledgers introduced centralized authorities, such as coordinators or super nodes, into the network in order to circumvent the above mentioned problem. This sacrifices the decentralized principle of blockchain to achieve correctness and improve performance, exposing the network to attacks from compromised central authorities, that are far below the typical Byzantine Fault Tolerance (BFT). Although these centralized authorities are intended to only be present in the beginning stage of the network’s life cycle, there has not been any evidence of the network being able to operate and stabilize without them. Even assuming the network could reach maturity phase, it will always be possible to cripple a portion of the network, and revert it back to this original centralized state, and thus again losing BFT.

Lack of Finality. Transactions stored on a DAG ledger generally can never achieve economic finality or probabilistic finality the same way that a transaction on a blockchain can be, due to the lack of a strict ordering of transactions. A pair of transactions on a simple DAG based ledger may not be temporally related to each other, and only spatially connected through edges, and thus larger portions of the graph can be orphaned or abandoned if a competing history has a higher cumulative weight or wins out in some other comparison.

The lack of finality makes it difficult for transactions on a DAG based ledger to be used for transferring assets that have real life value, because it’s often difficult to reverse a transaction once it has been approved in real life. The guarantee of irreversibility and finality for a valid transaction is crucial for many applications and platforms that could potentially adopt cryptocurrency.

LINIX Protocol

With LINIX Protocol, we seek to propose a new decentralized, trust-less framework for processing cryptocurrency transactions that utilizes a hybrid topology of a partially ordered Directed Acyclic Graph, and a canonical chain of State Matrices. This architecture enables greater scalability than traditional blockchain technology by allowing participant nodes to process transactions concurrently at arbitrarily high rates, bounded only by network constraints and computing power, while having Byzantine tolerance to most methods of attack.

Figure 1: Example Directed Acyclic Graph

Notations and Definitions

We need to introduce some basic graph theory and set theory concepts before we delve into the discussion for the sake of clarity.

A graph, G, is defined by its set of vertices V(G) and its set of edges E(V). A directed graph, or a digraph, is a graph where all the edges are directed from one vertex to another.

Two vertices that are contained in an edge, or two edges joined by one vertex are called adjacent; an edge and a vertex contained in that edge are called incident. Incidence and adjacency matrices are space efficient ways of representing graphs.

A subgraph of G is a graph H such that V (H) ⊆ V (G) and E(H) ⊆ E(G).

The neighborhood of v in a graph G is the subgraph of G induced by all vertices adjacent to v, and is denoted by N(v) = {u|uv ∈ E}.

The degree of v is d(v) = |N(v)|. For digraphs, the degree of edges pointing to v is called the indegree of v, and the degree of edges leading out is called the outdegree.

The Ordering of a Set. One of the innate properties of a set is the ordering of elements within it. A set can be largely categorized as having one of three types of orderings:

Two ordered sets, X and Y, are considered order isomorphic, if there a bijection f: X → Y such that both f and its inverse preserve order. Such functions are said to preserve monotonicity, and are called isotones.

Applications to Distributed Ledger Technology

But why is order theory relevant to the field of blockchain technology, and in designing a distributed digital ledger? The answer is primarily because of the double-spending problem. The double-spending problem can be loosely defined as the potential flaw of digital currency being spent more than once. Double-spending is unique to digital currencies because digital information can be reproduced relatively easily.

One of the greatest achievements of the Bitcoin protocol is that it solves the double spending problem without the need of a central authority, thus making cryptocurrencies viable as a store of value. Bitcoin and other traditional blockchain based ledgers follow a total ordering with respect to its single chain of blocks. Newly mined blocks are linked to existing blocks through a Merkel tree root hash that preserves the strict ordering of the chain. This ordering is then used to reject potential double spending transactions, since older blocks become increasingly difficult to overwrite through a longest chain attack as more newly mined blocks are affixed to the tail of the chain, and the transactions recorded on those older blocks can be considered probabilistically finalized.

However, this strict single chain architecture for storing transactions causes a performance and scalability bottleneck for Bitcoin and other similarly structured ledgers. Only one block can be mined at a time for a given chain height, and shortening the time it takes to mine a block past a certain threshold causes many conflicting blocks to be created in parallel, and performance suffers greatly due to redundant computations.

In search of solutions to scale blockchain based ledgers, the double spending problem arises again when we shift from a one dimensional chain based digital ledger to a DAG based digital ledger, because it’s no longer possible to enforce a total ordering of events through the sequential order of the chain structure — the very same structure that causes the underlying scalability issues of blockchain based ledgers.

Order Type in DAG Based Ledgers

Given a generic Directed Acyclic Graph, such as the one shown in Figure 1, there are multiple ways of traversing and ordering the vertices of the graph so two transactions involving the same address cannot be strictly ordered through a binary relations. The diagram shows one arbitrary ordering through the naming of the vertices, but there are potentially many other possible orderings that increase exponentially with the number of vertices (the number of possible orderings given a set of n items with no other restrictions is equal to n!).

Without an order on the set of vertices representing transactions, it is impossible to choose which transaction should have priority and which should be discarded as invalid in the case of a double spending attack. Such DAG based ledgers would have to discard conflicting transactions arbitrarily, causing unpredictable state changes in the network.

This lack of ordering on the DAG also means that knowledge of the entire graph is necessary to verify that a transaction is valid, because without global knowledge, another unknown transaction involving the same account address(es) in question could exist somewhere on the graph, and the unknown transaction could put all known transactions involving the same parties into a conflicted state. As the DAG grows, requiring global knowledge of the entire graph will become prohibitively expensive, not to mention the need for centralization to make such global knowledge accessible.

Topological Ordering: A topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph.

Given that all directed acyclic graphs can be topologically sorted naturally, would this be sufficient to guarantee an ordering for resolving conflicting transactions in a DAG based ledger? Let’s take a look at the sample DAG structure in Figure 1 again, there exists multiple valid topological orders for the graph, including:

Then, for example, if the conflicting transactions were C and G, or F and G , we still would not have a fixed order between them, and would be unable to resolve the conflict in a consistent way. Hence, for a generic DAG, its topological ordering could potentially be non-unique, and cannot be relied on as a partial order to resolve all potentially conflicting transactions consistently.

Figure 2: Example of a Hamiltonian Path on a planar graph

Computational Complexity of Finding a Hamiltonian Path

In fact, the topological order of a directed acyclic graph is unique, and can be used as a linear order, if and only if a Hamiltonian path exists on the graph. Hamiltonian path, also called a Hamilton path, is a graph path between two vertices of a graph that visits each vertex exactly once, i.e. it must be a traceable graph.

Notice how the last three vertices in the possible topological orders of diagram 1 are always E, B, A, that’s because the subgraph induced by the vertex set {A, B, E} contains a Hamiltonian path, and is a traceable graph, and thus its topological order is unique.

Outside of specific classes of graphs such as 4-connected planar graphs, or 3-connected 3-regular bipartite graphs, finding a Hamilton path is an NP Complete problem. In computational complexity theory, the NP Complete class of problems are solved in nondeterministic polynomial time, meaning that while a known solution can be verified quickly, there is no known way to find a solution in non exponential complexity.

Because of the high computational complexity to find a Hamiltonian path on an arbitrary Directed Acyclic Graph, we cannot rely on its natural topological ordering to be unique, and thus we want to construct a partial order to guarantee that certain subsets of the vertices of the resulting graph are well ordered and can be compared.

Entity-Relationship Model and Constructing a Partial Ordering

Figure 2: Example DAG with a Genealogical Partial Order

An entity–relationship model (ER model for short) describes interrelated things of interest in a specific domain of knowledge. A basic ER model is composed of entity types (which classify the things of interest) and specifies relationships that can exist between instances of those entity types.

We construct a partial order on the set of vertices of the graph through defining a genealogical binary relation on the set, such that:1. Vertices that share receiving or sending addresses are related;2a. Related vertices are partially ordered by the genealogical binary relation such that any newly affixed vertex must be the child of the latest generation of the related vertices of each involved address in the transaction;2b. The generation of a given address of the vertex is defined by its distance from the Genesis vertex, D(Gs), in the shortest unique path that crosses all its ancestral vertices;3. If a vertex has no existing relatives in the graph for any or all of its involved addresses, it is considered a descendant of the Genesis vertex, Gs;4a. Given a tuple of addresses, (a1, a2, a3, ...), and the corresponding tuple of generation numbers, (GN1, GN2, GN3, ...), we define the cohort set, Cohort{(a1, a2, a3, ...),(GN1, GN2, GN3, ...)}, as the set of children vertices with identical tuple of parental addresses and tuple of generation numbers;4b. The children vertices within the same cohort are comparable according to a binary relation - the child vertex with the earlier creation time is defined as having precedence;4c. If more than one child exists within a cohort set, the earliest one by creation time is regarded as having the highest precedence and valid, and all others are considered lower precedence and potentially invalid;5. Unrelated vertices are not ordered under this partial order.

Desirable Properties

The construction of this partial order on the Directed Acyclic Graph alleviates several problems that plague less well-ordered DAG’s, and still affords us the increased scalability of a non linear data structure.

The relational sharding algorithm can be summed up in the following pseudocode:Input: Directed Acyclic Graph of period, p, G(p).
Output: A set of connected subgraphs of G(p) that are partitioned by vertices which are related to each other.
Step 1: Traverse the graph, G(p), and remove and process all singleton vertices that are directed connected to the Genesis vertex, Gs.
Step 2:
Remove Gs, and all edges in its incoming edge set.
Step 3: Collect the remaining subgraphs of G(p) and return as the output.
Figure 3: Resulting graph after Relational Sharding of Figure 2

This article gives some background and outlines why order type is an important intrinsic property for Directed Acyclic Graph based ledgers, and describes the construction of a genealogy based partial order from the LINIX protocol that has a number of desirable properties.

The next entry in the LINIX Technical Spotlight series will focus on another technical aspect of the LINIX platform, topic to be announced. Stay tuned!

Stay tuned, and we thank you for all the support!

| WEBSITE | MEDIUM | TELEGRAM | TWITTER
|
LINKEDIN | FACEBOOK | INSTAGRAM
| EMAIL:
official@linix.foundation

LNX Protocol

The New Paradigm

Wei Duong

Written by

Wei Duong

Crypto Algorithm Research

LNX Protocol

The New Paradigm

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade