# A Novel Epoch-Based Transaction Consistency Sorting Protocol for DAG Distributed Ledger

Authors: Rong Li; Shangping Wang; Na Xie
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Because of the characteristics of decentralization, immutability, and transparency, blockchain has gradually become a new and revolutionary technology, which has far-reaching significance for the development of modern technology. However, the traditional Bitcoin blockchain that supports synchronous consensus suffers from the fatal flaw of low throughput. To improve throughput, a number of DAG distributed ledgers have been proposed that support asynchronous consensus, all of which allow multiple nodes to process concurrent transactions asynchronously. However, most DAG distributed ledgers do not implement consistent sorting of transactions, making it difficult to deploy smart contracts. To overcome this problem, in this paper, an epoch-based transaction consistency sorting protocol for DAG distributed ledger is proposed, which not only provides the possibility for the deployment of smart contracts but also can be used to resolve conflicting transactions in the ledger. Transaction consistency sorting protocol provides a more reasonably ordered list of all transactions by taking scalars, such as the set of their own past and future, parent block, and timestamp. In addition, through theoretical analysis, the stability and rationality of the transaction consistency sorting protocol are proved, and there is no Condorcet cycle. Finally, the simulation results demonstrate the protocol is efficient and achieve a throughput of at least 2000 transactions per second.


---

## Body

## 1. Introduction

Since Satoshi Nakamoto published the white paper on Nakamoto and Bitcoin [1] in 2008, blockchain, as the underlying technology of distributed ledger, has become increasingly popular around the world. The immutability, decentralization, transparency, and other characteristics of blockchain ensure the privacy and security of distributed ledger, so it also promotes the rapid development of the Internet system, financial system, Internet of Things (IoT), healthcare, and other fields.The traditional Bitcoin blockchain adopts the Nakamoto consensus, which organizes all transactions into an orderly list of the blocks. Each generated block points to its parent block and contains multiple transactions. All blocks form an irreversible single chain. The nodes (miners) participating in the Nakamoto consensus compete for accounting rights through the Proof of Work (PoW) mechanism; that is, the winner can write a new block in the ledger. Then, through the broadcast of the gossip network, we wait for the whole network nodes to reach a consensus on whether to receive the new block or not. On this basis, a new round of accounting rights competition is launched. However, with the rapid development of IoT, due to the inadmissibility of fork and low blocking rate, traditional Bitcoin blockchain faces fatal defects of low transaction throughput and high resource consumption, which cannot meet the needs of practical applications.In order to solve the performance bottleneck of traditional blockchain (i.e., Nakamoto consensus), such as low transaction throughput. In recent years, some scholars have proposed a structure of a Directed Acyclic Graph (DAG) distributed ledger [2, 3]. In DAG distributed ledger, forks are allowed. Nodes can simultaneously release multiple transactions, and the system can also process multiple transactions at the same time. In addition, using Gossip Network [4], transactions or blocks can be broadcast to all nodes in the network in a short time. Compared with the traditional Bitcoin blockchain, this DAG distributed ledger effectively solves the problems of forks and low block generation rate, which greatly improves the transaction throughput of the system.Although many consensus of DAG distributed ledger have emerged in recent years, the issues of block sorting has not been fully resolved. For example, Conflux [5–7] consensus achieves good throughput, and the hash value is used to solve the problem of sequence between the two concurrent blocks. However, although the hash function is very efficient, it is unreasonable to use it to sort blocks because of its pseudorandomness. In other words, if there are two conflicting transactions, the pseudorandom hash function cannot reflect the actual order between them, which may lead to the result that the attacker wins. In order to reflect the real order between transactions and achieve the goal of deploying smart contracts in the DAG distributed ledger, we propose a new epoch-based consistent block sorting protocol for DAG distributed ledger. The main contributions of this paper are as follows:(1)
By selecting main blocks and determining the main chain in the DAG distributed ledger, the structure of an epoch-based DAG distributed ledger is formed. On this basis, a transaction consistency sorting protocol is designed, which not only provides the possibility to deploy smart contracts in the DAG distributed ledger but also can be used to resolve conflicting transactions in the ledger.(2)
It is proved by a derivation that the proposed transaction consistency sorting protocol does not have Condorcet cycles[8] when sorting blocks in pairs, thus ensuring that our sorting results are reasonable and unique.(3)
The theoretical analysis and performance estimation of the epoch-based transaction consensus sorting protocol are given in this paper. The results show that the protocol is efficient and can achieve a throughput of at least 2000 transactions per second.The rest of this paper is organized as follows: In Section2, we firstly introduce the related work. Secondly, we provide an overview of the epoch-based transaction consistent sorting protocol in Section 3. In Sections 4 and 5, the theoretical analysis and performance evaluation of the transaction consistent sorting protocol are given. Finally, we conclude this paper in Section 6.


## 2. Background

In the Bitcoin network, new transactions will first be placed in an unverified transaction pool. Miners will package new transactions from the transaction pool and then try to solve a difficult problem of PoW to prove the legitimacy of this block. The data structure of a blockchain is a single chain formed by blocks in chronological order, and the height of blocks represents the linear order of blocks. Therefore, there is no sorting problem in Bitcoin. The main problems of Bitcoin are low throughput, long confirmation delay, and high transaction fee.In order to solve the performance bottleneck of the Bitcoin blockchain, the idea of a DAG distributed ledger has emerged. In 2013, Sompolinsky et al. proposed a consensus protocol based on the tree DAG-GHOST (Greedy Heaviest-Observed Subtree) [2, 3]. GHOST introduced weights to measure the number of blocks in the additional subtrees on each block, and reached a consensus on the order of transactions on the main chain. In 2015, Lewenbegr et al. proposed Inclusive on the basis of the GHOST agreement [9]. Inclusive protocol introduces the concept of uncle block, reaches a consensus in the main chain based on DAG and then sorts all blocks according to the main chain and topological structure.In 2016, several blockchain consensus protocols based on DAG emerged: SPECTRE [9, 10], IOTA [11], Hashgraph [12, 13], Byteball [14], etc. IOTA is a micropayment system for IoT. It has no mining, no blocks, and no transaction fee. Anyone can participate in it, but it does not achieve the order of all transactions. Baird et al. proposed a Hashgraph [12, 13] consensus protocol based on the Gossip protocol and virtual voting algorithm, which is a completely asynchronous, decentralized, leaderless Byzantine fault-tolerant system, without PoW. Sompolinsky et al. proposed an unlicensed SPECTRE protocol allowing forks. This protocol uses a recursive weighted voting algorithm for topological sorting in blocks and is very suitable for DAG distributed ledger. However, this order is not linear, so the protocol does not support smart contracts. PHANTOM [15, 16] and SPECTRE are completely independent protocols. The difference is that the PHANTOM protocol eventually forms a linear sorting, but the order is not unique. Churyumov et al. proposed a DAG-based ledger Byteball [14]. In Byteball, the introduction of witnesses realizes the sequencing of transactions, but it also affects the complete decentralization of the system.Colin et al. proposed a nonpermissible protocol Nano [17], which uses a lattice structure. Each node maintains its own single chain, and it can freely trade between chains. However, it is not mentioned in the consensus article on how to achieve the order of all transactions between multiple chains. In the same year, Team Rocket proposed the avalanche agreement Avalanche [18, 19]. Through the Gossip algorithm and Epidemic network, the avalanche protocol connects the original transaction to DAG and constructs four consensuses at the bottom, namely, Slush, Snowflake, Snowball, and Avalanche. Finally, a Byzantine fault-tolerant consensus family without a leader, based on metastable state and independent of PoW is formed. The order between transactions in this protocol is topological.In 2018, Li et al. proposed a fast, scalable, decentralized blockchain system Conflux [5], which realized the throughput of thousands of transactions per second and used a hash function to reach a consensus on the overall order between blocks. In order to prevent liveness attacks [19], the team proposed another consensus GHAST in 2020. In 2019, Gupta and others proposed CDAG [20] (Converging Directed Acyclic Graph). The participants of CDAG used the Colosseum consensus to compete in pairs, and finally the winner won the right to record the new block. The CDAG consensus effectively solves the ranking problem of transactions in the DAG distributed ledger while ensuring efficiency. In the same year, Tong Zhou et al. proposed DLattice [21] with double DAG based on Nano protocol and realized the sorting between transactions.Furthermore, Yu proposed a novel permissionless blockchain protocol OHIE [22] which explicitly aims for simplicity. OHIE composes as many parallel instances of Bitcoin’s original (and simple) backbone protocol as needed to achieve excellent throughput. In 2020, Wang [23] systematically summarizes the research on DAG technology and provides a comprehensive analysis (SoK) of the blockchain system based on DAG. They summarized the main components and characteristics of open source systems, provided a comprehensive analysis of DAG-based blockchain systems, and pointed out the promising direction of their future research by reviewing the deconstruction and academic research of open source systems. Giridharan proposed Bull Shark [24] in 2022, the first asynchronous Byzantine atomic broadcast protocol based on directed acyclic graphs (DAG). It has optimal amortized communication complexity, it provides fairness and asynchronous liveness, and safety is guaranteed even under a quantum adversary. In recent years, many efficient and secure schemes have emerged, but these schemes need to be improved in the aspect of block sorting.Among these consensus algorithms of the DAG distributed ledger, only a few can deploy and realize smart contracts. Although Conflux supports smart contracts, the blocks in Conflux are sorted according to the hash value of the blocks, because the pseudorandomness of the hash function that cannot reflect the real order between transactions, which cannot be used to solve conflict transactions.


## 3. The Protocol of Epoch-Based Transaction Consistency Sorting for DAG Distributed Ledger

In this section, we provide a detailed overview of an epoch-based transaction consistency sorting protocol that is common to any DAG distributed ledger, including the motivation of research and specific scheme.


### 3.1. The Motivation of Research

As we all know, the DAG distributed ledger is a directed acyclic graph consisting of vertices and directed edges, represented byG=V,E. Among them, V=v is the set of vertices v and it is the vertex of the directed acyclic graph, also known as the block in the DAG distributed ledger, which can contain one or more transactions. In this article, we refer to them collectively as blocks. E is the set of directed edges between blocks (vertices), 〈u,v〉 represents the directed edges from block u to block v. A specific network structure example of G=V,E is shown in Figure 1, where G0 is Genesis, and the newly added block N that has not been verified is called a tip.Figure 1
A specific network structure example ofG=V,E.There are two kinds of directed edges in Figure1, which we call parent edges and reference edges, respectively [5]. The parent edges represent the voting relationship, represented by solid arrows. Since each block has only one parent, its parent edge is also unique and deterministic. The reference edges correspond to the generation order between blocks, represented by dashed arrows. A block can contain multiple reference blocks.Due to the use of an asynchronous concurrency model, DAG distributed ledgers allow multiple transactions to join the blockchain network at the same time, thereby significantly increasing transaction throughput. However, this method also brings some new problems. Asynchronous concurrency makes the transactions in the system do not have a clear order, so it cannot support the deployment of smart contracts, and it also brings inevitable conflict transactions to the system, which are difficult to solve.In response to these problems, we design an epoch-based transaction consistency sorting protocol for DAG distributed ledgers. The transaction consistency sorting protocol not only provides the possibility for DAG distributed ledger to deploy smart contracts but also can be used to resolve conflicting transactions in the ledger. Furthermore, our protocol is general to any DAG distributed ledger.


### 3.2. Specific Scheme

Specifically, the operation of the epoch-based transaction consistency sorting protocol we designed is as follows: First, in any DAG distributed ledger, the main block is selected according to the principle of the heaviest subtree to determine the main chain. Second, the original DAG distributed ledger is converted into an epoch-based DAG distributed ledger structure according to the order of the main blocks on the main chain. Then, use epoch sorting to get the rough order of blocks. Subsequently, for each epoch, the blocks are strictly ordered according to the rules for internal fine sorting. Finally, the global consistency sorting for DAG distributed ledger is obtained by integrating all of the internal fine sorting.In fact, the transaction consistency sorting protocol we designed can be divided into two main stages, including the construction stage of the epoch and the sorting stage of blocks. The former involves the determination of the main chain and the division of epochs, while the latter includes epoch rough sorting, epoch internal fine sorting, and global consistency sorting. Therefore, our transaction consistency sorting protocol consists of five steps, the process of which is shown in Figure2, and the specific sorting steps are as follows.Figure 2
The flow chart of epoch-based transaction consistency sorting.Step 1.
Determination of the main chain.
Given a DAG distributed ledgerG=V,E, the main chain is determined as shown in Algorithm 1.
The main chainMC is the heaviest chain formed by the linear connection of main blocks selected according to the heaviest subtree principle of GHOST [2, 3]. The main block mi is the child node selected according to the principle of the heaviest subtree of the previous main block mi−1, and it is the block with the largest Future⋅ value calculated according to the Future⋅ function of the node. Assuming that the main block mi−1 is known, the operation of selecting the next main block mi can be formally expressed as follows:(1)c,mi∈C:Futuremi≥Futurec,C=Childmi−1,Futurec=c′|c←c′∪c↞c′∪c.
Among them,mi represents the ith main block, and C=Childmi−1 represents the set of sub-blocks of block mi−1. Futurec represents the set of blocks that directly or indirectly refer to block c and contain c itself, and Future⋅ represents the number of elements in Future⋅. The symbol “←” represents a direct reference; the symbol “↞” represents an indirect reference. It is worth emphasizing that if the block with the largest Future⋅ is not unique, these blocks are hashed, and the one with the largest hash value is selected as the main block. Assuming that there are i main blocks in the DAG distributed ledger at this time, then the main chain can be formally expressed as follows:(2)MCmiG0,i=0,MCmi−1≺mi,otherwise,where the symbol “≺” means “is a prefix of”, m0=G0 is Genesis.
To sum up, taking the DAG distributed ledger shown in Figure1 as an example, according to the determination rules of the main chain, the main chain is determined as G0≺A≺C≺E≺H≺N.Algorithm 1: Main chain.
Input:G=V,EOutput:MCmn(1)
i=0(2)
m0←G0;(3)
fori=1,i<n,i++(4)
ifChildmi−1=∅then;(5)
returnMCmi−1(6)
else(7)
for all cj∈Childmi−1do(8)
wj=Futurecj(9)
wk=maxwj(10)
mi←ck(11)
returnMCmnStep 2.
Division of epoch.
Inspired by Conflux, we use the concept of epoch to partition the DAG distributed ledger. The traditional DAG distributed ledger divides epochs according to the blocks in the main chain, that is, each main block corresponds to an epoch. The epoch corresponding to the main blockmi is represented by the symbol Ei. E0 is the 0th epoch, and only contains a unique block G0 (ie, the Genesis). Specifically, blocks that satisfy one of the following conditions are divided into the same Epoch Ei:(1)
main blockmi.(2)
the block that the main blockmi can reach through directed edges, but not included in the previous epoch Ei−1, it can be formally expressed as follows:(3)Ei=PastG,mi−PastG,mi−1.
Therefore, for the DAG distributed ledger shown in Figure1, we transform it into an epoch-based architecture as shown in Figure 3. It is divided into 6 epochs: E0=G0,E1=A,E2=C,B,E3=D,E,F,E4=L,H,I,J,E5=K,N.
For convenience, we denote the ledger obtained by dividing the traditional DAG distributed ledgerG=V,E by epoch as G=V,E,MC,Epoch. Among them, V represents the blocks, E represents the directed edges, MC represents the main chain, and Epoch represents the sequence of all epochs. The difference between the new structure and the original DAG distributed ledger is that the former contains an epoch sequence and a main chain formed by a linear link of main blocks.Figure 3
Epoch-based DAG distributed ledger architecture.Step 3.
Epoch rough sorting.
Epoch rough sorting is to use the result of Step 2 division to perform the rough order of blocks. Follow the principle of time from far to near, that is, the earlier the time ofEi is, the more priority the blocks contained in Ei will be, namely, E0≺E1≺E2≺⋯≺Ei−1≺Ei≺Ei+1≺⋯.
According to this rule, we perform epoch rough sorting on the epoch-based DAG distributed ledger shown in Figure3, we have the following equation:(4)E0≺E1≺E2≺E3≺E4≺E5.
That is, the result of the rough sorting is(5)G0≺A≺BC≺DEF≺LJHI≺KN.Step 4.
The internal fine sorting of each epoch.
The internal fine sorting of each epoch is the process of strictly sorting the blocks in each epoch. Given a transformed epoch-based DAG distributed ledgerG=V,E,MC,Epoch, the process of sorting any two blocks x,y∈V without reference relationship in Ei is shown in Algorithm 2.
Assuming that all blocks in each epoch are to be sorted now, then we start from the firstEi containing two or more blocks that do not have a reference relationship, and calculate the set Past⋅ of any two unordered blocks in Ei. Pastx represents the set of blocks directly or indirectly referenced by block x, and includes x itself, which we can formalize as follows:(6)Pastx=∪i∈BeforexPasti,where Beforex represents a block generated before a given block x, which can be expressed as follows:(7)Beforex=x′|x′∈V,x,x′∈E.
Any two blocksx and block y that have no reference relationship in Ei are then sorted pairwise according to the following rules:(1)
ComparePast⋅ of block x and block y, where Past⋅ is the number of elements in set Past⋅. Following the principle from small to large, the smaller the value of Past⋅, the more priority the order of blocks is. There may be the following three situations:(a)
IfPastx<Pasty, then x≺y(b)
IfPastx>Pasty, then y≺x(c)
IfPastx=Pasty, then go to the next step(2)
Calculate and compareFuture⋅ of block x and block y, where Future⋅ is the number of elements in set Future⋅. The ordering obeys the principle from large to small. The larger the value of Future⋅ is, the more priority the order of blocks is. Similarly, the following three situations may occur:(a)
IfFuturex>Futurey, then x≺y(b)
IfFuturex<Futurey, then y≺x(c)
IfFuturex=Futurey, then jump to the next stepConsider the parent blocksparent⋅ of block x and block y, namely, parentx and parenty, and according to the principle of the earlier the parent block, the priority of the block, we have:(a)
Ifparentx<parenty, then x≺y(b)
Ifparentx>parenty, then y≺x(c)
Ifparentx=parenty, then then go to next step(3)
Whenparentx=parenty appears, the order between block x and block y is determined according to their timestamp. The earlier the time, the higher the priority of the block. While the probability of this happening is extremely small, it can still happen due to network delays caused by device functionality.
Through the above-given method, we can sort all unordered blocks without reference relationship in pairs and finally get the strict order of all blocks in the epoch. In addition, we prove that this pairwise sorting algorithm does not suffer from the Condorcet cycle problem in Section IV.A. The specific process of internal fine sorting of Epoch is shown in Figure4.Algorithm 2: The pairwise sorting of blocks.
Input:G=V,E,MC,Epoch, x,y∈V⊆EiOutput: the order of blocks x,y∈V(1)
ifPastx<Pastythen(2)
x≺y(3)
else(4)
ifPastx>Pastythen(5)
y≺x(6)
else(7)
Pastx=Pastythen(8)
ifFuturex>Futureythen(9)
x≺y(10)
else(11)
ifFuturex<Futureythen(12)
y≺x(13)
else(14)
ifparentx<parentythen(15)
x≺y(16)
else(17)
ifparentx>parentythen(18)
y≺x(19)
else(20)
Sorting them by their timestamp(21)
return the order of blocks x,y∈VFigure 4
The specific process of pairwise sorting.Step 5.
Integrate sorting results.
After the internal fine sorting of blocks in each epoch is determined, based on the order of eachEi, we perform a global consistency sorting on the entire DAG distributed ledger to get the strict order of all blocks.
The epoch-based transaction consistency sorting protocol for DAG distributed ledgers is not only suitable for ledgers with parent edges, such as Conflux. In particular, it can also be used for DAG distributed ledgers with only reference edges, where we only need to determine the order between blocks based on theirPast⋅, Future⋅, and Timestamp⋅ without comparing their parents block parent⋅.
To sum up, continue to sort the blocks in Figure1, and finally we can get the strict order of the blocks as follows:(8)G0≺A≺B≺C≺F≺D≺E≺L≺J≺I≺H≺K≺N.


## 3.1. The Motivation of Research

As we all know, the DAG distributed ledger is a directed acyclic graph consisting of vertices and directed edges, represented byG=V,E. Among them, V=v is the set of vertices v and it is the vertex of the directed acyclic graph, also known as the block in the DAG distributed ledger, which can contain one or more transactions. In this article, we refer to them collectively as blocks. E is the set of directed edges between blocks (vertices), 〈u,v〉 represents the directed edges from block u to block v. A specific network structure example of G=V,E is shown in Figure 1, where G0 is Genesis, and the newly added block N that has not been verified is called a tip.Figure 1
A specific network structure example ofG=V,E.There are two kinds of directed edges in Figure1, which we call parent edges and reference edges, respectively [5]. The parent edges represent the voting relationship, represented by solid arrows. Since each block has only one parent, its parent edge is also unique and deterministic. The reference edges correspond to the generation order between blocks, represented by dashed arrows. A block can contain multiple reference blocks.Due to the use of an asynchronous concurrency model, DAG distributed ledgers allow multiple transactions to join the blockchain network at the same time, thereby significantly increasing transaction throughput. However, this method also brings some new problems. Asynchronous concurrency makes the transactions in the system do not have a clear order, so it cannot support the deployment of smart contracts, and it also brings inevitable conflict transactions to the system, which are difficult to solve.In response to these problems, we design an epoch-based transaction consistency sorting protocol for DAG distributed ledgers. The transaction consistency sorting protocol not only provides the possibility for DAG distributed ledger to deploy smart contracts but also can be used to resolve conflicting transactions in the ledger. Furthermore, our protocol is general to any DAG distributed ledger.


## 3.2. Specific Scheme

Specifically, the operation of the epoch-based transaction consistency sorting protocol we designed is as follows: First, in any DAG distributed ledger, the main block is selected according to the principle of the heaviest subtree to determine the main chain. Second, the original DAG distributed ledger is converted into an epoch-based DAG distributed ledger structure according to the order of the main blocks on the main chain. Then, use epoch sorting to get the rough order of blocks. Subsequently, for each epoch, the blocks are strictly ordered according to the rules for internal fine sorting. Finally, the global consistency sorting for DAG distributed ledger is obtained by integrating all of the internal fine sorting.In fact, the transaction consistency sorting protocol we designed can be divided into two main stages, including the construction stage of the epoch and the sorting stage of blocks. The former involves the determination of the main chain and the division of epochs, while the latter includes epoch rough sorting, epoch internal fine sorting, and global consistency sorting. Therefore, our transaction consistency sorting protocol consists of five steps, the process of which is shown in Figure2, and the specific sorting steps are as follows.Figure 2
The flow chart of epoch-based transaction consistency sorting.Step 1.
Determination of the main chain.
Given a DAG distributed ledgerG=V,E, the main chain is determined as shown in Algorithm 1.
The main chainMC is the heaviest chain formed by the linear connection of main blocks selected according to the heaviest subtree principle of GHOST [2, 3]. The main block mi is the child node selected according to the principle of the heaviest subtree of the previous main block mi−1, and it is the block with the largest Future⋅ value calculated according to the Future⋅ function of the node. Assuming that the main block mi−1 is known, the operation of selecting the next main block mi can be formally expressed as follows:(1)c,mi∈C:Futuremi≥Futurec,C=Childmi−1,Futurec=c′|c←c′∪c↞c′∪c.
Among them,mi represents the ith main block, and C=Childmi−1 represents the set of sub-blocks of block mi−1. Futurec represents the set of blocks that directly or indirectly refer to block c and contain c itself, and Future⋅ represents the number of elements in Future⋅. The symbol “←” represents a direct reference; the symbol “↞” represents an indirect reference. It is worth emphasizing that if the block with the largest Future⋅ is not unique, these blocks are hashed, and the one with the largest hash value is selected as the main block. Assuming that there are i main blocks in the DAG distributed ledger at this time, then the main chain can be formally expressed as follows:(2)MCmiG0,i=0,MCmi−1≺mi,otherwise,where the symbol “≺” means “is a prefix of”, m0=G0 is Genesis.
To sum up, taking the DAG distributed ledger shown in Figure1 as an example, according to the determination rules of the main chain, the main chain is determined as G0≺A≺C≺E≺H≺N.Algorithm 1: Main chain.
Input:G=V,EOutput:MCmn(1)
i=0(2)
m0←G0;(3)
fori=1,i<n,i++(4)
ifChildmi−1=∅then;(5)
returnMCmi−1(6)
else(7)
for all cj∈Childmi−1do(8)
wj=Futurecj(9)
wk=maxwj(10)
mi←ck(11)
returnMCmnStep 2.
Division of epoch.
Inspired by Conflux, we use the concept of epoch to partition the DAG distributed ledger. The traditional DAG distributed ledger divides epochs according to the blocks in the main chain, that is, each main block corresponds to an epoch. The epoch corresponding to the main blockmi is represented by the symbol Ei. E0 is the 0th epoch, and only contains a unique block G0 (ie, the Genesis). Specifically, blocks that satisfy one of the following conditions are divided into the same Epoch Ei:(1)
main blockmi.(2)
the block that the main blockmi can reach through directed edges, but not included in the previous epoch Ei−1, it can be formally expressed as follows:(3)Ei=PastG,mi−PastG,mi−1.
Therefore, for the DAG distributed ledger shown in Figure1, we transform it into an epoch-based architecture as shown in Figure 3. It is divided into 6 epochs: E0=G0,E1=A,E2=C,B,E3=D,E,F,E4=L,H,I,J,E5=K,N.
For convenience, we denote the ledger obtained by dividing the traditional DAG distributed ledgerG=V,E by epoch as G=V,E,MC,Epoch. Among them, V represents the blocks, E represents the directed edges, MC represents the main chain, and Epoch represents the sequence of all epochs. The difference between the new structure and the original DAG distributed ledger is that the former contains an epoch sequence and a main chain formed by a linear link of main blocks.Figure 3
Epoch-based DAG distributed ledger architecture.Step 3.
Epoch rough sorting.
Epoch rough sorting is to use the result of Step 2 division to perform the rough order of blocks. Follow the principle of time from far to near, that is, the earlier the time ofEi is, the more priority the blocks contained in Ei will be, namely, E0≺E1≺E2≺⋯≺Ei−1≺Ei≺Ei+1≺⋯.
According to this rule, we perform epoch rough sorting on the epoch-based DAG distributed ledger shown in Figure3, we have the following equation:(4)E0≺E1≺E2≺E3≺E4≺E5.
That is, the result of the rough sorting is(5)G0≺A≺BC≺DEF≺LJHI≺KN.Step 4.
The internal fine sorting of each epoch.
The internal fine sorting of each epoch is the process of strictly sorting the blocks in each epoch. Given a transformed epoch-based DAG distributed ledgerG=V,E,MC,Epoch, the process of sorting any two blocks x,y∈V without reference relationship in Ei is shown in Algorithm 2.
Assuming that all blocks in each epoch are to be sorted now, then we start from the firstEi containing two or more blocks that do not have a reference relationship, and calculate the set Past⋅ of any two unordered blocks in Ei. Pastx represents the set of blocks directly or indirectly referenced by block x, and includes x itself, which we can formalize as follows:(6)Pastx=∪i∈BeforexPasti,where Beforex represents a block generated before a given block x, which can be expressed as follows:(7)Beforex=x′|x′∈V,x,x′∈E.
Any two blocksx and block y that have no reference relationship in Ei are then sorted pairwise according to the following rules:(1)
ComparePast⋅ of block x and block y, where Past⋅ is the number of elements in set Past⋅. Following the principle from small to large, the smaller the value of Past⋅, the more priority the order of blocks is. There may be the following three situations:(a)
IfPastx<Pasty, then x≺y(b)
IfPastx>Pasty, then y≺x(c)
IfPastx=Pasty, then go to the next step(2)
Calculate and compareFuture⋅ of block x and block y, where Future⋅ is the number of elements in set Future⋅. The ordering obeys the principle from large to small. The larger the value of Future⋅ is, the more priority the order of blocks is. Similarly, the following three situations may occur:(a)
IfFuturex>Futurey, then x≺y(b)
IfFuturex<Futurey, then y≺x(c)
IfFuturex=Futurey, then jump to the next stepConsider the parent blocksparent⋅ of block x and block y, namely, parentx and parenty, and according to the principle of the earlier the parent block, the priority of the block, we have:(a)
Ifparentx<parenty, then x≺y(b)
Ifparentx>parenty, then y≺x(c)
Ifparentx=parenty, then then go to next step(3)
Whenparentx=parenty appears, the order between block x and block y is determined according to their timestamp. The earlier the time, the higher the priority of the block. While the probability of this happening is extremely small, it can still happen due to network delays caused by device functionality.
Through the above-given method, we can sort all unordered blocks without reference relationship in pairs and finally get the strict order of all blocks in the epoch. In addition, we prove that this pairwise sorting algorithm does not suffer from the Condorcet cycle problem in Section IV.A. The specific process of internal fine sorting of Epoch is shown in Figure4.Algorithm 2: The pairwise sorting of blocks.
Input:G=V,E,MC,Epoch, x,y∈V⊆EiOutput: the order of blocks x,y∈V(1)
ifPastx<Pastythen(2)
x≺y(3)
else(4)
ifPastx>Pastythen(5)
y≺x(6)
else(7)
Pastx=Pastythen(8)
ifFuturex>Futureythen(9)
x≺y(10)
else(11)
ifFuturex<Futureythen(12)
y≺x(13)
else(14)
ifparentx<parentythen(15)
x≺y(16)
else(17)
ifparentx>parentythen(18)
y≺x(19)
else(20)
Sorting them by their timestamp(21)
return the order of blocks x,y∈VFigure 4
The specific process of pairwise sorting.Step 5.
Integrate sorting results.
After the internal fine sorting of blocks in each epoch is determined, based on the order of eachEi, we perform a global consistency sorting on the entire DAG distributed ledger to get the strict order of all blocks.
The epoch-based transaction consistency sorting protocol for DAG distributed ledgers is not only suitable for ledgers with parent edges, such as Conflux. In particular, it can also be used for DAG distributed ledgers with only reference edges, where we only need to determine the order between blocks based on theirPast⋅, Future⋅, and Timestamp⋅ without comparing their parents block parent⋅.
To sum up, continue to sort the blocks in Figure1, and finally we can get the strict order of the blocks as follows:(8)G0≺A≺B≺C≺F≺D≺E≺L≺J≺I≺H≺K≺N.


## 4. Theoretical Analysis

In this section, we will prove through theoretical analysis that there is no Condorcet cycle in the epoch-based transaction consensus sorting protocol, and the protocol is stable and reasonable.


### 4.1. Proof of No Condorcet Cycle

In this section, we first introduce the definition of the Condorcet cycle [8, 10] and then use Theorem 1 to show that our proposed transaction consistency sorting protocol does not exist Condorcet cycle (in the pairwise ordering of blocks).Definition 1.
The Condorcet cycle is shown in Figure5. When a pairwise sorting is performed on a set of blocks bi,bj,bk, the order of block bi and block bj is bi≺bj, and the order of block bj and block bk is bj≺bk. However, the order of block bi and block bk is bk≺bi. This situation is called a Condorcet cycle when the blocks are sorted in pairs.Figure 5
The Condorce cycle.Theorem 1.
Suppose there is a DAG distributed ledger, and blockx,y, and z are all belong to the same epoch in Ei, if both x≺y and y≺z hold, then x≺z. That is, there will be no Condorcet cycle in the transaction consistency sorting algorithm of the Epoch-based DAG distributed ledger.Proof.
Because whenx≺y appears, there may be the following situations:(1)
Pastx<Pasty(2)
Pastx=Pasty, but Futurex>Futurey(3)
Pastx=Pasty and Futurex=Futurey, but parentx<parenty(4)
Pastx=Pasty, Futurex=Futurey and parentx=parenty, but Timestampx<Timestampy
Similarly, becausey≺z, then one of the following four conditions occurs:(1)
Pasty<Pastz(2)
Pasty=Pastz, but Futurey>Futurez(3)
Pasty=Pastz and Futurey=Futurez, but parenty<parentz(4)
Pasty=Pastz, Futurey=Futurez and parenty=parentz, but Timestampy<Timestampz
Now,x≺z can be deduced according this pairwise ordering of x≺y and y≺z as follows:(1)
IfPastx<Pasty, i.e., x≺y(a)
IfPasty<Pastz, we have Pastx<Pasty<Pastz, then it is obvious that x≺z(b)
IfPasty=Pastz, but Futurey>Futurez, then we have y≺z, then x≺z can be deduced(c)
If|Pasty=Pastz and Futurey=Futurez, but parenty<parentz, then we have y≺z, therefore, x≺z can be deduced(d)
IfPasty=Pastz, Futurey=Futurez and parenty=parentz, but Timestampy<Timestampz, then we have y≺z, therefore, it is obvious that x≺z(2)
Pastx=Pasty and Futurex>Futurey, i.e., x≺y(a)
IfPasty<Pastz, we have x≺y and y≺z, then x≺z can be deduced(b)
IfPasty=Pastz, but Futurey>Futurez, then we have Futurex>Futurey>Futurez, then it is obvious that x≺z(c)
IfPasty=Pastz and Futurey=Futurez, but parenty<parentz, then we have y≺z, therefore, x≺z can be deduced(d)
IfPasty=Pastz, Futurey=Futurez and parenty=parentz, but Timestampy<Timestampz, then we have y≺z, therefore, x≺z can be deduced(3)
Pastx=Pasty and Futurex=Futurey, but parentx<parenty, i.e., x≺y(a)
IfPasty=Pastz, we have.x≺y. and y≺z, then x≺z can be deduced(b)
IfPasty=Pastz, but Futurey>Futurez, we have x<y and y≺z, then x≺z can be deduced(c)
IfPasty=Pastz and Futurey=Futurez, but parenty<parentz, then we have parentx<parenty<parentz, therefore, it is obvious that x≺z(d)
IfPasty=Pastz, Futurey=Futurez and parenty=parentz, but Timestampy<Timestampz, then we have y≺z, therefore, x≺z can be deduced(4)
Pastx=Pasty, Futurey=Futurez and parentx=parenty, but Timestampx<Timestampy, i.e., x≺y(a)
IfPasty<Pastz, we have x≺y and y≺z, then x≺z can be deduced(b)
IfPasty=Pastz, but Futurey>Futurez, we have x≺y and y<z, then x≺z can be deduced(c)
IfPasty=Pastz and Futurey=Futurez, butparenty<parentz, then we have y≺z, therefore, x≺z can be deduced(d)
IfPasty=Pastz, Futurey=Futurez and.parenty=parentz, but Timestampy<Timestampz, then we have Timestampx<Timestampy<Timestampz, therefore, it is obvious that x≺z
To sum up, using the block sorting rules of the Epoch-based DAG distributed ledger, when all blocks in an Epoch are sorted in pairs, there will be no Condorcet cycle, that is to say, there will be no contradictory sorting. This also shows that our sorting protocol is correct and reasonable.


### 4.2. Stability of Sorting under Network Latency

Considering that the state of the DAG distributed ledger is constantly updated, the setFuture⋅ of blocks changes in real time due to the concurrent network model. In this section, according to the conclusions of Proposition 6.1 and Lemma 6.4 in the literature [25], the stability of the transaction consistency sorting protocol based on the Epoch for DAG distributed ledger is deduced under the network delay. First, we introduce two definitions (FutureiB and RiskB,k [25]).Definition 2.
FutureiB is a set of blocks of height i that directly or indirectly reference block B and have FutureiB⊆FutureB.Definition 3.
Assuming that blockB and block B′ are honest blocks and malicious blocks containing conflicting transactions, k represents the number of times that honest blocks in the network are confirmed, then in the final consensus reached by nodes, malicious blocks replace honest blocks to proceed. The probability of sorting is defined as follows:(9)RiskB,k=Pr∑i=NN+k+1Rh,i<Ra,N+k+1,where Rh,i represents the number of blocks that directly or indirectly point to the honest block B when the height is i, namely,(10)Rh,i=FutureiB.
Therefore, we have the following equation:(11)∑i=NN+k+1Rh,i=∪i=N+1N+k+1FutureiB,and Ra,N+k+1 represents the number of blocks that directly or indirectly point to malicious block B′ when the height is N+k+1, namely,(12)Ra,N+k+1=FutureN+k+1B′.Lemma 1 (see [25]).
Suppose at timet, a block B is included in the DAG Gct (Gct represents the DAG observed by node c at time t), and at time s≫t has(13)limk⟶∞RiskB,k=0.Lemma 2 (see [25]).
For anyϵ>0,ϵ≪1, there is RiskB,k<ϵ, and the minimum number k of confirmations required for block B is(14)k≤3λD+11−ϵ4λ1−qD+1.These two lemmas have been proved in [25]. Using the Poisson distribution, the law of iterative expectations, and the law of total variance [26], the authors first obtained the expectations and variances of these random variables and then proved that RiskB,k approaches 0. On this basis, it is proved that the minimum number k of confirmations required for block B is finite (ie, Lemma 2). According to the above-given conclusions, this paper has such a derivation that if FutureB and FutureB′ both contain N blocks at time t, block B is a valid block published by an honest node, and block B′ is a malicious block broadcast by an attacker, Then, when there are N+k+1 blocks in FutureB, block B is finally approved. Furthermore, since k is finite, then for any ϵ>0,ϵ≪1, there is RiskB,k<ϵ; thus, we can get the following:Whenq⟶0 (q is the proportion of the attacker’s computing power in the entire network), k tends to 3/4;Whenq⟶0.1, k tends to 1.That is, the best case is to wait for no more than 2 new blocks to be added toFutureB, block B can be finally approved, and the recognition of block B′ (malicious block) will also decrease with the continuous expansion of the DAG distributed ledger.In summary, although the setFuture⋅ of blocks will change as the network expands, the Epoch-based transaction consistency sorting is stable.


### 4.3. The Rationality of Transaction Consistency Sorting

In the existing DAG distributed ledger, the SPECTRE protocol determines the order of blocks based on the process of pairwise voting. However, due to the existence of the Condorcet paradox, the pairwise ordering relationship of blocks in the SPECTRE protocol is not transitive of. PHANTOM classifies blocks into honest blocks and malicious blocks by solvingMCSk⋅. Then, according to a topological sorting algorithm, the honest blocks are prioritized, and finally the total ordering of blocks is given, but solving MCSk⋅ is NP difficult question. Transactions in IOTA are not completely ordered, and there may be some conflicting transactions that cannot be successfully verified due to a lack of liveness.Hashgraph uses consensus timestamps to order transactions and then uses XOR signatures to break the ordering tie. In Nano, transactions on a single chain are sorted according to the time they were received. The parachains of DEXON confirm each other through the reference field of the block and finally determine the global block order through these reference relationships.In addition, although Byteball and Conflux all give a global ordering scheme for transactions, they all use hash functions when conflicting transactions occur. While sorting with hashes can improve efficiency, hashes are pseudorandom, so sorting blocks using a hash function does not reflect the true order between transactions. Therefore, this method is considered unreasonable.As shown in Table1, by comparing the transaction throughput of these schemes, we can find that the sorting protocol in this paper is second only to the Conflux protocol in efficiency, but when there are more than three blockchains in the system, our scheme will be superior. On the other hand, the blocks in Conflux are sorted according to the hash function, while the sorting protocol in this paper uses more scalars to give a specific and reasonable order between transactions, including the past of blocks set Past(.), future set Future⋅ and parent block parent⋅, and the timestamp of the transaction itself. Moreover, in terms of advantages, since the hash function is pseudorandom, the block sorting result of conflux cannot reflect the real order between transactions, and it may even vote for dishonest nodes in the process of resolving conflicting transactions. However, the sorting protocol in this paper cleverly solves this problem by measuring multiple scalars to reflect the order of transactions as truly as possible, so as to avoid the serious harm caused by malicious attackers to the greatest extent.Table 1
Comparison of transaction sorting for different DAG distributed ledgers.
Idea designSchemeThroughputSpecific contentResolve conflicts in the ledger through voting mechanismSPECTRE [10]—The sequence of blocks is determined based on the process of pairwise votingPHANTOM [16]300Find honest blocks by subsetMCSk⋅, then do topological sortIOTA [11]500–800Transactions are not completely orderedThe peer entities maintain a relatively independent single chain, and the entities reach consensus certain mechanism.Hashgraph [12]—Sort by consensus timestampNano [17]800–1000Sort transactions on a single chain by consensus timestampDEXON [27]300–500Determine the global block order through reference relationshipsFirst, a consensus is reached in the main chain, and then the ledger is topologically sorted using the main chain.Byteball [14]—The units are sorted based on the main chain index (MCI), and the hash function is used for collisions.Conflux [5]3200Sort by Epoch first, then sort blocks in any Epoch by their hash valueOur scheme1000nn≥2Sort by Epoch first, then order the blocks in each epoch by combiningPast⋅, Future⋅, parent⋅ and Timestamp⋅


## 4.1. Proof of No Condorcet Cycle

In this section, we first introduce the definition of the Condorcet cycle [8, 10] and then use Theorem 1 to show that our proposed transaction consistency sorting protocol does not exist Condorcet cycle (in the pairwise ordering of blocks).Definition 1.
The Condorcet cycle is shown in Figure5. When a pairwise sorting is performed on a set of blocks bi,bj,bk, the order of block bi and block bj is bi≺bj, and the order of block bj and block bk is bj≺bk. However, the order of block bi and block bk is bk≺bi. This situation is called a Condorcet cycle when the blocks are sorted in pairs.Figure 5
The Condorce cycle.Theorem 1.
Suppose there is a DAG distributed ledger, and blockx,y, and z are all belong to the same epoch in Ei, if both x≺y and y≺z hold, then x≺z. That is, there will be no Condorcet cycle in the transaction consistency sorting algorithm of the Epoch-based DAG distributed ledger.Proof.
Because whenx≺y appears, there may be the following situations:(1)
Pastx<Pasty(2)
Pastx=Pasty, but Futurex>Futurey(3)
Pastx=Pasty and Futurex=Futurey, but parentx<parenty(4)
Pastx=Pasty, Futurex=Futurey and parentx=parenty, but Timestampx<Timestampy
Similarly, becausey≺z, then one of the following four conditions occurs:(1)
Pasty<Pastz(2)
Pasty=Pastz, but Futurey>Futurez(3)
Pasty=Pastz and Futurey=Futurez, but parenty<parentz(4)
Pasty=Pastz, Futurey=Futurez and parenty=parentz, but Timestampy<Timestampz
Now,x≺z can be deduced according this pairwise ordering of x≺y and y≺z as follows:(1)
IfPastx<Pasty, i.e., x≺y(a)
IfPasty<Pastz, we have Pastx<Pasty<Pastz, then it is obvious that x≺z(b)
IfPasty=Pastz, but Futurey>Futurez, then we have y≺z, then x≺z can be deduced(c)
If|Pasty=Pastz and Futurey=Futurez, but parenty<parentz, then we have y≺z, therefore, x≺z can be deduced(d)
IfPasty=Pastz, Futurey=Futurez and parenty=parentz, but Timestampy<Timestampz, then we have y≺z, therefore, it is obvious that x≺z(2)
Pastx=Pasty and Futurex>Futurey, i.e., x≺y(a)
IfPasty<Pastz, we have x≺y and y≺z, then x≺z can be deduced(b)
IfPasty=Pastz, but Futurey>Futurez, then we have Futurex>Futurey>Futurez, then it is obvious that x≺z(c)
IfPasty=Pastz and Futurey=Futurez, but parenty<parentz, then we have y≺z, therefore, x≺z can be deduced(d)
IfPasty=Pastz, Futurey=Futurez and parenty=parentz, but Timestampy<Timestampz, then we have y≺z, therefore, x≺z can be deduced(3)
Pastx=Pasty and Futurex=Futurey, but parentx<parenty, i.e., x≺y(a)
IfPasty=Pastz, we have.x≺y. and y≺z, then x≺z can be deduced(b)
IfPasty=Pastz, but Futurey>Futurez, we have x<y and y≺z, then x≺z can be deduced(c)
IfPasty=Pastz and Futurey=Futurez, but parenty<parentz, then we have parentx<parenty<parentz, therefore, it is obvious that x≺z(d)
IfPasty=Pastz, Futurey=Futurez and parenty=parentz, but Timestampy<Timestampz, then we have y≺z, therefore, x≺z can be deduced(4)
Pastx=Pasty, Futurey=Futurez and parentx=parenty, but Timestampx<Timestampy, i.e., x≺y(a)
IfPasty<Pastz, we have x≺y and y≺z, then x≺z can be deduced(b)
IfPasty=Pastz, but Futurey>Futurez, we have x≺y and y<z, then x≺z can be deduced(c)
IfPasty=Pastz and Futurey=Futurez, butparenty<parentz, then we have y≺z, therefore, x≺z can be deduced(d)
IfPasty=Pastz, Futurey=Futurez and.parenty=parentz, but Timestampy<Timestampz, then we have Timestampx<Timestampy<Timestampz, therefore, it is obvious that x≺z
To sum up, using the block sorting rules of the Epoch-based DAG distributed ledger, when all blocks in an Epoch are sorted in pairs, there will be no Condorcet cycle, that is to say, there will be no contradictory sorting. This also shows that our sorting protocol is correct and reasonable.


## 4.2. Stability of Sorting under Network Latency

Considering that the state of the DAG distributed ledger is constantly updated, the setFuture⋅ of blocks changes in real time due to the concurrent network model. In this section, according to the conclusions of Proposition 6.1 and Lemma 6.4 in the literature [25], the stability of the transaction consistency sorting protocol based on the Epoch for DAG distributed ledger is deduced under the network delay. First, we introduce two definitions (FutureiB and RiskB,k [25]).Definition 2.
FutureiB is a set of blocks of height i that directly or indirectly reference block B and have FutureiB⊆FutureB.Definition 3.
Assuming that blockB and block B′ are honest blocks and malicious blocks containing conflicting transactions, k represents the number of times that honest blocks in the network are confirmed, then in the final consensus reached by nodes, malicious blocks replace honest blocks to proceed. The probability of sorting is defined as follows:(9)RiskB,k=Pr∑i=NN+k+1Rh,i<Ra,N+k+1,where Rh,i represents the number of blocks that directly or indirectly point to the honest block B when the height is i, namely,(10)Rh,i=FutureiB.
Therefore, we have the following equation:(11)∑i=NN+k+1Rh,i=∪i=N+1N+k+1FutureiB,and Ra,N+k+1 represents the number of blocks that directly or indirectly point to malicious block B′ when the height is N+k+1, namely,(12)Ra,N+k+1=FutureN+k+1B′.Lemma 1 (see [25]).
Suppose at timet, a block B is included in the DAG Gct (Gct represents the DAG observed by node c at time t), and at time s≫t has(13)limk⟶∞RiskB,k=0.Lemma 2 (see [25]).
For anyϵ>0,ϵ≪1, there is RiskB,k<ϵ, and the minimum number k of confirmations required for block B is(14)k≤3λD+11−ϵ4λ1−qD+1.These two lemmas have been proved in [25]. Using the Poisson distribution, the law of iterative expectations, and the law of total variance [26], the authors first obtained the expectations and variances of these random variables and then proved that RiskB,k approaches 0. On this basis, it is proved that the minimum number k of confirmations required for block B is finite (ie, Lemma 2). According to the above-given conclusions, this paper has such a derivation that if FutureB and FutureB′ both contain N blocks at time t, block B is a valid block published by an honest node, and block B′ is a malicious block broadcast by an attacker, Then, when there are N+k+1 blocks in FutureB, block B is finally approved. Furthermore, since k is finite, then for any ϵ>0,ϵ≪1, there is RiskB,k<ϵ; thus, we can get the following:Whenq⟶0 (q is the proportion of the attacker’s computing power in the entire network), k tends to 3/4;Whenq⟶0.1, k tends to 1.That is, the best case is to wait for no more than 2 new blocks to be added toFutureB, block B can be finally approved, and the recognition of block B′ (malicious block) will also decrease with the continuous expansion of the DAG distributed ledger.In summary, although the setFuture⋅ of blocks will change as the network expands, the Epoch-based transaction consistency sorting is stable.


## 4.3. The Rationality of Transaction Consistency Sorting

In the existing DAG distributed ledger, the SPECTRE protocol determines the order of blocks based on the process of pairwise voting. However, due to the existence of the Condorcet paradox, the pairwise ordering relationship of blocks in the SPECTRE protocol is not transitive of. PHANTOM classifies blocks into honest blocks and malicious blocks by solvingMCSk⋅. Then, according to a topological sorting algorithm, the honest blocks are prioritized, and finally the total ordering of blocks is given, but solving MCSk⋅ is NP difficult question. Transactions in IOTA are not completely ordered, and there may be some conflicting transactions that cannot be successfully verified due to a lack of liveness.Hashgraph uses consensus timestamps to order transactions and then uses XOR signatures to break the ordering tie. In Nano, transactions on a single chain are sorted according to the time they were received. The parachains of DEXON confirm each other through the reference field of the block and finally determine the global block order through these reference relationships.In addition, although Byteball and Conflux all give a global ordering scheme for transactions, they all use hash functions when conflicting transactions occur. While sorting with hashes can improve efficiency, hashes are pseudorandom, so sorting blocks using a hash function does not reflect the true order between transactions. Therefore, this method is considered unreasonable.As shown in Table1, by comparing the transaction throughput of these schemes, we can find that the sorting protocol in this paper is second only to the Conflux protocol in efficiency, but when there are more than three blockchains in the system, our scheme will be superior. On the other hand, the blocks in Conflux are sorted according to the hash function, while the sorting protocol in this paper uses more scalars to give a specific and reasonable order between transactions, including the past of blocks set Past(.), future set Future⋅ and parent block parent⋅, and the timestamp of the transaction itself. Moreover, in terms of advantages, since the hash function is pseudorandom, the block sorting result of conflux cannot reflect the real order between transactions, and it may even vote for dishonest nodes in the process of resolving conflicting transactions. However, the sorting protocol in this paper cleverly solves this problem by measuring multiple scalars to reflect the order of transactions as truly as possible, so as to avoid the serious harm caused by malicious attackers to the greatest extent.Table 1
Comparison of transaction sorting for different DAG distributed ledgers.
Idea designSchemeThroughputSpecific contentResolve conflicts in the ledger through voting mechanismSPECTRE [10]—The sequence of blocks is determined based on the process of pairwise votingPHANTOM [16]300Find honest blocks by subsetMCSk⋅, then do topological sortIOTA [11]500–800Transactions are not completely orderedThe peer entities maintain a relatively independent single chain, and the entities reach consensus certain mechanism.Hashgraph [12]—Sort by consensus timestampNano [17]800–1000Sort transactions on a single chain by consensus timestampDEXON [27]300–500Determine the global block order through reference relationshipsFirst, a consensus is reached in the main chain, and then the ledger is topologically sorted using the main chain.Byteball [14]—The units are sorted based on the main chain index (MCI), and the hash function is used for collisions.Conflux [5]3200Sort by Epoch first, then sort blocks in any Epoch by their hash valueOur scheme1000nn≥2Sort by Epoch first, then order the blocks in each epoch by combiningPast⋅, Future⋅, parent⋅ and Timestamp⋅


## 5. The Estimation of Performance

### 5.1. Environment Setup

We use Golang as the programming language and Goland as the integrated compilation and development environment. Golang features easy deployment, excellent performance, a large number of built-in libraries, and cross-platform compilation. In addition, we also implement transaction consistency sorting for all DAG-type distributed ledgers by the creation and receiving of the block, the selection of the main chain, and complete sorting modules. This machine’s operating system and processor for win10 and 2.4 GHz, 4 core Inter core i5, the computing capacity of 23588 hashes per second.


### 5.2. Parameter Setting

The derivation process in this section follows the following assumptions and related parameters. Modeling a DAG network [2, 3] as G=V,E.MC,Epoch, the entire network generates blocks with a Poisson process of rate λ [28]. Whenever a node creates a new block, the new block is broadcast to the entire network immediately and waits for other nodes to verify it. Assume that each edge has a network delay D [3, 29], which is the time it takes for a message to reach the other end of a directed edge. Assuming that the sum of the computing power of the entire network is 1, the computing power of the attacker is qq<1, λa is the attacker’s block creation rate, λh is the block creation rate of honest nodes. Therefore, we have the following equation:(15)λa=qλ,λh=1−qλ,λ=λa+λh.


### 5.3. Estimation of Throughput in Main Chain

In an Epoch-based DAG distributed ledger, the creation of blocks is a Poisson process.λ is the average block generation rate of the entire network. TPS is the product of the main chain’s average block growth rate β, block size b, and average transaction size K [2], which can be formalized as follows:(16)TPSλ,b=βλ,b⋅b⋅K.Proposition 8.4 in [2] and Lemma 6 in [3] both demonstrate that the main chain growth rate of the heaviest chain is: β≥λ/1+2λD. From this we know that when all nodes follow the heaviest subtree rule, the transaction throughput on the main chain follows:(17)TPSλ,b=βλ,b⋅b⋅K≥λ⋅b⋅K1+2λD.According to Proposition 3.1 in the article [2] and the data provided by Decker and Wattenhofer [30], it is known that a 50% attack has no restrictions on the choice of block size b and block generation rate λ. At this time, TPS is only affected by the node’s physical limitations, such as bandwidth limitations, network delays. A test study of the data found a strong correlation between the size of a block and the time it takes to propagate a block [29]. Even if the size of a block is very small, there is a small delay in propagating it. Besides, for every 1 KB increase in block size, the latency increases linearly. This can be explained by the combination of the constant propagation delay of blocks on the link and transmission delay due to bandwidth constraints and block verification time, which is linearly related to the block size.Therefore, by fitting these two influencing factors, the obtained linear model can be formalized as follows:(18)D50%b=Dprop+Dbw⋅b.Dprop represents the metric value of the total propagation delay; Dbw represents the 1 KB delay metric value. After testing, the optimal parameters obtained are: Dprop=1.80, Dbw=0.066. From this, the time it takes for a block to reach 50% of the network nodes is 1.80+0.066⋅b. Therefore, for the transformed Epoch-based DAG distributed ledger, the transaction throughput of the main chain can be expressed as follows:(19)TPSλ,b=βλ,b⋅b⋅K≥λ⋅b⋅K1+21.80+0.066⋅bλ.Based on the above-given conclusions, we estimated the TPS of the main chain in Epoch’s DAG distributed ledger. The specific parameter settings are shown in Table2. By using the control variable method, each of the two variables in the block size b, the number K of transactions per KB, and the block creation rate λ are controlled separately to observe the impact of another variable on the TPS of the consensus main chain.Table 2
Evaluation parameter settings.
ParameterDbKunitsecondKB—value1.80+0.066⋅bb1=1024K1=32b2=2048K2=64b3=4096K3=128b4=5120K4=256In order to make the TPS optimal, we take the optimal values for each parameter. According to Figure6, when the parameter K is 256 and the block creation rate λ is equal to 10, the TPS increases with the block. It increases with the increase of the size of block b but tends to stabilize after a certain degree, so we take the optimal value of as 2048.Figure 6
The block sizeb impact on TPS.Figure7 depicts the relationship between the TPS of the main chain and the number K of transactions. With a fixed block size b=2048 and 4 different parameters K, it shows that the TPS on the main chain is mainly affected by the parameter K. Specifically, for different K1,K2,K3,K4, there are(20)TPS1λ,b=βλ,b⋅b⋅K1≥λ⋅2048⋅321+21.80+0.066⋅2048λ≥120,TPS2λ,b=βλ,b⋅b⋅K2≥λ⋅2048⋅641+21.80+0.066⋅2048λ≥240.8,TPS3λ,b=βλ,b⋅b⋅K3≥λ⋅2048⋅1281+21.80+0.066⋅2048λ≥481.6,TPS4λ,b=βλ,b⋅b⋅K4≥λ⋅2048⋅2561+21.80+0.066⋅2048λ≥963.2.Figure 7
TPS on main chain (whenb=2048KB).To sum up, without considering the throughput of the entire DAG network, the TPS of the main chain in the Epoch-based DAG distributed ledger is quite high, reaching a transaction throughput of close to 1000b=2048,K=256. For the entire DAG network, it is formed by n main chains, so the transaction throughput of the entire network can reach 1000n. Because of n≥2, this distributed ledger can achieve at least 2000 transactions per second.


## 5.1. Environment Setup

We use Golang as the programming language and Goland as the integrated compilation and development environment. Golang features easy deployment, excellent performance, a large number of built-in libraries, and cross-platform compilation. In addition, we also implement transaction consistency sorting for all DAG-type distributed ledgers by the creation and receiving of the block, the selection of the main chain, and complete sorting modules. This machine’s operating system and processor for win10 and 2.4 GHz, 4 core Inter core i5, the computing capacity of 23588 hashes per second.


## 5.2. Parameter Setting

The derivation process in this section follows the following assumptions and related parameters. Modeling a DAG network [2, 3] as G=V,E.MC,Epoch, the entire network generates blocks with a Poisson process of rate λ [28]. Whenever a node creates a new block, the new block is broadcast to the entire network immediately and waits for other nodes to verify it. Assume that each edge has a network delay D [3, 29], which is the time it takes for a message to reach the other end of a directed edge. Assuming that the sum of the computing power of the entire network is 1, the computing power of the attacker is qq<1, λa is the attacker’s block creation rate, λh is the block creation rate of honest nodes. Therefore, we have the following equation:(15)λa=qλ,λh=1−qλ,λ=λa+λh.


## 5.3. Estimation of Throughput in Main Chain

In an Epoch-based DAG distributed ledger, the creation of blocks is a Poisson process.λ is the average block generation rate of the entire network. TPS is the product of the main chain’s average block growth rate β, block size b, and average transaction size K [2], which can be formalized as follows:(16)TPSλ,b=βλ,b⋅b⋅K.Proposition 8.4 in [2] and Lemma 6 in [3] both demonstrate that the main chain growth rate of the heaviest chain is: β≥λ/1+2λD. From this we know that when all nodes follow the heaviest subtree rule, the transaction throughput on the main chain follows:(17)TPSλ,b=βλ,b⋅b⋅K≥λ⋅b⋅K1+2λD.According to Proposition 3.1 in the article [2] and the data provided by Decker and Wattenhofer [30], it is known that a 50% attack has no restrictions on the choice of block size b and block generation rate λ. At this time, TPS is only affected by the node’s physical limitations, such as bandwidth limitations, network delays. A test study of the data found a strong correlation between the size of a block and the time it takes to propagate a block [29]. Even if the size of a block is very small, there is a small delay in propagating it. Besides, for every 1 KB increase in block size, the latency increases linearly. This can be explained by the combination of the constant propagation delay of blocks on the link and transmission delay due to bandwidth constraints and block verification time, which is linearly related to the block size.Therefore, by fitting these two influencing factors, the obtained linear model can be formalized as follows:(18)D50%b=Dprop+Dbw⋅b.Dprop represents the metric value of the total propagation delay; Dbw represents the 1 KB delay metric value. After testing, the optimal parameters obtained are: Dprop=1.80, Dbw=0.066. From this, the time it takes for a block to reach 50% of the network nodes is 1.80+0.066⋅b. Therefore, for the transformed Epoch-based DAG distributed ledger, the transaction throughput of the main chain can be expressed as follows:(19)TPSλ,b=βλ,b⋅b⋅K≥λ⋅b⋅K1+21.80+0.066⋅bλ.Based on the above-given conclusions, we estimated the TPS of the main chain in Epoch’s DAG distributed ledger. The specific parameter settings are shown in Table2. By using the control variable method, each of the two variables in the block size b, the number K of transactions per KB, and the block creation rate λ are controlled separately to observe the impact of another variable on the TPS of the consensus main chain.Table 2
Evaluation parameter settings.
ParameterDbKunitsecondKB—value1.80+0.066⋅bb1=1024K1=32b2=2048K2=64b3=4096K3=128b4=5120K4=256In order to make the TPS optimal, we take the optimal values for each parameter. According to Figure6, when the parameter K is 256 and the block creation rate λ is equal to 10, the TPS increases with the block. It increases with the increase of the size of block b but tends to stabilize after a certain degree, so we take the optimal value of as 2048.Figure 6
The block sizeb impact on TPS.Figure7 depicts the relationship between the TPS of the main chain and the number K of transactions. With a fixed block size b=2048 and 4 different parameters K, it shows that the TPS on the main chain is mainly affected by the parameter K. Specifically, for different K1,K2,K3,K4, there are(20)TPS1λ,b=βλ,b⋅b⋅K1≥λ⋅2048⋅321+21.80+0.066⋅2048λ≥120,TPS2λ,b=βλ,b⋅b⋅K2≥λ⋅2048⋅641+21.80+0.066⋅2048λ≥240.8,TPS3λ,b=βλ,b⋅b⋅K3≥λ⋅2048⋅1281+21.80+0.066⋅2048λ≥481.6,TPS4λ,b=βλ,b⋅b⋅K4≥λ⋅2048⋅2561+21.80+0.066⋅2048λ≥963.2.Figure 7
TPS on main chain (whenb=2048KB).To sum up, without considering the throughput of the entire DAG network, the TPS of the main chain in the Epoch-based DAG distributed ledger is quite high, reaching a transaction throughput of close to 1000b=2048,K=256. For the entire DAG network, it is formed by n main chains, so the transaction throughput of the entire network can reach 1000n. Because of n≥2, this distributed ledger can achieve at least 2000 transactions per second.


## 6. Conclusion

In view of the general lack of transaction consistency sorting protocol in the DAG distributed ledger, we propose a transaction consistency sorting protocol based on Epoch in this paper. The protocol uses the heaviest chain as the main chain, and the blocks on the main chain determine the epoch. Then, the blocks are arranged by epoch to get the epoch rough sorting, and then the blocks in each epoch are sorted in pairs by combining the past setPast⋅ future set Future⋅ and parent block parent⋅, and finally get a global transaction order. The protocol not only makes it possible to deploy smart contracts on the DAG distributed ledger but also provides a new method for resolving conflicting transactions in the ledger. In addition, the stability and rationality of the proposed transaction consistency sorting protocol are proved by theoretical analysis, and there is no Condorcet cycle. Finally, the simulation results demonstrate the protocol is efficient, achieving at least 2000 transactions per second.



---

*Source: 3930858-2022-12-08.xml*