Concurrency Control in DAG-Based Blockchains

NEZHA: Exploiting Concurrency for Transaction Processing in DAG-based Blockchains Jiang Xiao, Shijie Zhang, Zhiwei Zhang, Bo Li, Xiaohai Dai, and Hai Jin

* Directed Acyclic Graph (DAG)-based blockchain uses a DAG structure to organize transactions or blocks DAG-based blockchains do not require miners to authenticate its transactions; instead, two parent transactions confirm the validity of a subsequent transaction g

* Problem throughput performance of conventional blockchains is bad solution: DAG-based blockchain with concurrent transaction processing BUT, there is an increased number of concurrent reads and writes to the same address in a DAG-based blockchain, which leads to a considerable rise of potential conflicts

* Problem throughput performance of conventional blockchains is bad solution: DAG-based blockchain with concurrent transaction processing BUT, there is an increased number of concurrent reads and writes to the same address in a DAG-based blockchain, which leads to a considerable rise of potential conflicts

* Problem throughput performance of conventional blockchains is bad solution: DAG-based blockchain with concurrent transaction processing BUT, there is an increased number of concurrent reads and writes to the same address in a DAG-based blockchain, which leads to a considerable rise of potential conflicts how to effectively and efficiently detect and order conflicting transactions during concurrent transaction processing in DAG-based blockchains?

Solution: NEZHA NEZHA is a concurrency control scheme for DAG-based blockchains which employs addresses to detect all dependent transactions

Solution: NEZHA NEZHA is a concurrency control scheme for DAG-based blockchains which employs addresses to detect all dependent transactions specifically, NEZHA maps each transaction to the corresponding addresses rather than capturing dependencies between each pair of transactions

Solution: NEZHA NEZHA is a concurrency control scheme for DAG-based blockchains which employs addresses to detect all dependent transactions specifically, NEZHA maps each transaction to the corresponding addresses rather than capturing dependencies between each pair of transactions There are two essential steps to NEZHA: constructing an address-based conflict graph (ACG) implementing a hierarchical sorting (HS) algorithm

Address-based Conflict Graph (ACG) set which stores transactions corresponding to a particular address (e.g., A1) RW1 ACG is used for discovering dependent transactions through address dependencies RW2 RW3 represents a write-read dependency between two addresses (e.g., there is a transaction that writes to A2and reads from A3)

ACG Continued RWi: a read/write set which stores transaction units, TvRand TvW, that read and write, respectively, to address Ais.t. v [1, (# of transactions)] and i = 1, 2, , n RW1 a vertex is a read/write set, RWi , and an edge represents write-read dependency between two sets: address dependency RW2 RW3 TvW RW2 TvR RW3

Hierarchical Sorting (HS) Algorithm determines the specific order of each transaction based on ACG: generates a total order between transactions addresses are ranked by address dependencies to indicate their sorting priorities: prioritizes the address with the most dependencies

Hierarchical Sorting (HS) Algorithm determines the specific order of each transaction based on ACG: generates a total order between transactions addresses are ranked by address dependencies to indicate their sorting priorities: prioritizes the address with the most dependencies form a graph with each address as a vertex and, again, edges represent dependencies address ranking protocol: 1. find address with minimum number of incoming edges 2. if two addresses have the minimum number of incoming edges, then choose address with higher number of outgoing edges 3. if they both have an equal number of outgoing edges, then choose address with lower subscript value

1. address with minimum number of incoming edges

2. address with the most number of outgoing edges

3. address with lowest subscript value

HS Algorithm Continued assign sequence numbers to the read/write units on each address in the order of their respective sorting rank rules for assigning sequence numbers to read/write units on the same address: TvRhas a smaller sequence number than TuWif v u TvWhas a smaller sequence number than TuWif v < u read units can be assigned the same sequence number since there is no conflict between read operations

HS Algorithm Continued assign sequence numbers to the read/write units on each address in the order of their respective sorting rank transaction sorting protocol: 1. check if there exist read units that have been assigned sequence numbers a. if not, all read units are assigned the same initial sequence number; if so, use the minimum sequence number among them to assign the remaining read units 2. examine all write units that have assigned sequence numbers a. if we find a write unit whose read unit is also stored on this address, reassign this read and write unit a sequence number greater than the maximum one among read units

s is just a sequence number the transaction sorting result of the address with the most dependencies will affect the sorting of more addresses

* T1is an unserializable transaction: sequence number of a write unit is smaller than the maximum one among read units!

* Summary of NEZHA employs addresses to discover all dependent transactions and organizes them into the ACG and then sort transactions on each address successively to yield a total order utilizing the HS algorithm to rank addresses based on the ACG

Implementation of NEZHA they implement NEZHA using Go1 they chose OHIE2as an underlying DAG-based blockchain system 1https://golang.org 2https://arxiv.org/abs/1811.12628

Setup experiments are conducted on the Alibaba Cloud platform there s a cluster of 14 nodes that are located within the same region and connected via 100 Mbps Ethernet 12 nodes serve as miners to propose blocks in parallel 1 node serves as a full node to synchronize the entire system state 1 node serves as a client to propose transactions

Setup experiments are conducted on the Alibaba Cloud platform there s a cluster of 14 nodes that are located within the same region and connected via 100 Mbps Ethernet 12 nodes serve as miners to propose blocks in parallel 1 node serves as a full node to synchronize the entire system state 1 node serves as a client to propose transactions the maximum block concurrency as 12 (i.e., at most 12 parallel chains) the block size is 200 transactions each experiment is run at least four times, and the average value is taken as the final result

Compared Schemes serial (baseline): a serial transaction processing scheme adopted by current DAG-based blockchains conflict graph (CG): a graph used to guide the ordering of conflicting transactions (like ACG) which has been used in previous work for concurrency control in DAG-based blockchains

Overview of CG serial order for transaction commitment represents transaction dependency unserializable transactions found by cycle detection transaction

* Transaction Processing Latency: NEZHA and Serial

* Transaction Processing Latency: NEZHA and Serial

* Transaction Processing Latency: NEZHA and Serial

* Transaction Processing Latency: NEZHA and CG access skewness; follows Zipfian distribution

* Transaction Processing Latency: NEZHA and CG block concurrency is fixed to 4

* Transaction Abort Rate: NEZHA and CG increase is due to increase of unserializable transactions

* Effective Throughput: NEZHA, CG and Serial

Conclusion they present NEZHA, a concurrency control scheme for DAG-based blockchains experimental results demonstrate that NEZHA outperforms conventional schemes and shows stable performance with increasing conflict