11institutetext: Indian Institute of Technology Hyderabad, Kandi, Telangana
502285 11email:
<EMAIL_ADDRESS>
# Efficient and Concurrent Transaction Execution Module for Blockchains

Manaswini Piduguralla 11 Saheli Chakraborty 11 Parwat Singh Anjana 11 Sathya
Peri 11

###### Abstract

Blockchain technology is a distributed, decentralized, and immutable ledger
system. It is the platform of choice for managing smart contract transactions
(SCTs). Smart contracts are self-executing codes of agreement between
interested parties commonly implemented using blockchains. A block contains a
set of transactions representing changes to the system and a hash of the
previous block. The SCTs are executed multiple times during the block
production and validation phases across the network. Transaction execution is
sequential in most blockchain technologies.

In this work, we propose a parallel direct acyclic graph (DAG) based parallel
scheduler module for concurrent execution of SCTs. Using the module, which can
be seamlessly integrated into the blockchain framework, parallel transactions
can be executed more efficiently and the speed of transactions can be
increased. The dependencies among a block’s transactions are represented
through a concurrent DAG data structure that assists with throughput
optimization. We have created a DAG scheduler module that can be incorporated
into blockchain platforms for concurrent execution with ease. For evaluation,
our framework is implemented in Hyperledger Sawtooth V1.2.6. The performance
across multiple smart contract applications is measured for various scheduler
types. A performance comparison between the proposed framework and the
Sawtooth parallel SCT execution framework shows significant improvements.

###### Keywords:

Smart Contract Executions, Blockchains, Hyperledger Sawtooth

##  1 Introduction

Blockchain platforms help establish and maintain a decentralized and
distributed ledger system between untrusting parties [12]. The blockchain is a
collection of immutable blocks typically in the form of a chain. Each block
points to its previous block by storing its hash. A block in the blockchain
consists of several _smart contract transactions (SCTs)_ which are self-
executing contracts of agreement between two or more parties that are written
in the form of computer code. These help in the execution of agreements among
untrusted parties without the necessity for a common trusted authority to
oversee the execution. The development and deployment of smart contracts on
blockchain platforms is growing rapidly.

A blockchain network usually consists of several nodes (ranging from thousands
to millions depending on the blockchain), each of which stores the entire
blockchain’s contents. Any node in the blockchain can act as a _block
producer_. A producer node selects transactions from a pool of available
transactions and packages them into a block. The proposed block is then
broadcast to other nodes in the network. A node on receiving the block acts as
a _validator_. It validates the transactions in the block by executing them
one after another. Thus a node can act as a producer while producing the block
and as a validator while validating the block.

Agreement on the proposed block by the nodes of the blockchain is performed
through various consensus mechanisms, like proof of work (PoW)[12], proof of
stake (PoS)[16], proof of elapsed time (PoET)[10], etc. For a block to be
added to the blockchain, the transactions of the block are processed in two
contexts: (a) first time by the block producer when the block is produced; (b)
then by all the block validators as a part of the block validation. Thus the
SCT code is executed multiple times by the producer and the validators.

The majority of blockchain technologies execute the SCTs in a block serially
during the block creation and validation phases. This is one of the
bottlenecks for higher throughput and scalability of blockchain models [7].
Throughput of the blockchain can be improved by concurrent execution of
transactions. To process transactions simultaneously, it is necessary to make
sure that transactions that are dependent on each other are not run together.
In addition, concurrent execution of transactions at each validator should
result in the same end state in the database. In this work, a framework for
the concurrent execution of transactions on producers and validators is
proposed. The framework has been implemented in Hyperledger Sawtooth 1.2.6 to
determine the level of optimization it achieves.

The underlying architecture of Hyperledger Sawtooth and its introduction are
provided in Section 2. Section 3 details our framework for parallel
transaction execution as well as pseudocode for DAG creation, utilization, and
smart validation. This is followed by a discussion of the implementation
details, experiment design, and results presented in Section 4. Tests of our
scheduler have been extensively conducted, and the results of our experiments
have been analyzed in detail. We discuss our conclusions and next steps in
Section 6 of our paper.

##  2 Background

###  2.1 Hyperledger Sawtooth

The Hyperledger Foundation is an open-source collaboration project by the
Linux Foundation to establish and encourage cross-industry blockchain
technologies. Sawtooth is one of the most popular blockchain technologies
being developed for permission and permissionless networks. It is designed
such that transaction rules, permissions, and consensus algorithms can be
customized according to the particular area of application. Some of the
distinctive features of Sawtooth are modularity, multi-language support,
parallel transaction execution, and pluggable consensus. The modular structure
of Sawtooth helps in modifying particular operations without needing to make
changes throughout the architecture.

Figure 1: Structure of a Hyperledger Sawtooth block

In Sawtooth, smart contracts are referred to as transaction families, and the
logic for the contract is present in the respective families’ transaction
processors. Modifications to the state are performed through transactions and
they are always wrapped inside a batch. A batch is the atomic unit of change
in the system and multiple batches are combined to form a block (Figure 1).
The node architecture of Sawtooth includes five modules that play crucial
roles in blockchain development: global state, journal, transaction scheduler,
transaction executor, and transaction processor. The global state containing
the data of transaction families of Sawtooth is stored using a radix Merkel
tree data structure. The Journal module contains a block completer, block
validator and block publishers that deal with creating, verifying and
publishing blocks. It is the Transaction Scheduler module’s responsibility to
identify the dependencies between transactions and schedule transactions that
result in conflict-free execution. In order to execute a transaction, the
transaction executor collects the context of the transaction. The detailed
architecture is expained in appendix A [13].

Hyperledger Sawtooth architecture includes a parallel transaction scheduler
(tree-scheduler) that uses a Merkle-Radix tree with nodes that are addressable
by state addresses. This tree is called the predecessor tree. Each node in the
tree represents one address in the Sawtooth state and a read list and write
list are maintained at each node. Whenever an executor thread requests the
next transaction, the scheduler inspects the list of unscheduled transactions
and the status of their predecessors. The drawbacks of the tree scheduler are
that the status of predecessor transactions needs to be checked before a
transaction can be scheduled. The construction of the tree data structure is
serial. The number of addresses accessed in a block is generally higher than
the total number of transactions. The memory space utilized for an address
based data structure is more than a transaction based data structure. The
miners and validators both construct the tree at their end instead of sharing
the tree constructed by the miners.

The proposed framework for transaction execution on the blockchain would
improve the throughput of SCTs by making the block creation and validation
process concurrent. SCTs that are independent of each other are executed in
parallel in the framework. The dependencies are represented as a direct
acyclic graph (DAG) based on transaction inputs and outputs. DAG sharing and
smart validator module designs are also included in the framework to further
optimize block validation.

##  3 Proposed Framework

In this section, the proposed framework for parallel transaction execution in
blockchains through static analysis by miners and validators of the network is
detailed. This framework introduces _parallel scheduler_ and _smart validator_
modules into the blockchain node architecture. The parallel scheduler is
responsible for identifying the dependencies among the transactions in the
block and scheduling them for conflict-free execution. This is done by
determining the dependencies among the transactions. The identified
dependencies are represented by a direct acyclic graph (DAG) that is shared
along with the block to minimize the validation time of the blockchain. DAG
shared along with the blocks are validated by the _smart validator_ , which
determines if the miners have shared incorrect graph. In this section, a
detailed framework Figure 2 and the pseudo-codes of the modules are presented.
The implementation and experiments conducted in Hyperledger Sawtooth are
discussed in further sections.

Figure 2: Proposed framework in the blockchain

###  3.1 Parallel Scheduler

The parallel scheduler module is part of the miner in the proposed framework.
It performs the operations of DAG creation and conflict-free transaction
execution. Both operations are multi-threaded for higher throughput.

DAG creation: The DAG creation is initiated when the miner creates the next
block in the blockchain. In blockchains like Sawtooth, the addresses that the
transactions read from, and write to, are present in the transaction header.
Using this information, we can derive the addresses based on the transaction
details without having to execute the transaction. Analyzing these input
(read) and output (write) addresses, the parallel scheduler computes the
dependencies between transactions.

On receiving the block from the block producer, transaction ID is assigned to
the transactions based on the position of them in the block
($T_{1},T_{2},T_{3}$…). Multiple threads are deployed to generate the DAG.
Each thread in the parallel scheduler claims the next unclaimed transaction in
the block and a global atomic counter is maintained to keep track. The input
addresses of the transaction ($T_{a}$) are compared with all the output
addresses of transactions (e.g., $T_{b}$) with a higher ID. Correspondingly,
the output addresses of $T_{a}$ are compared with the input and output
addresses of $T_{b}$. If there are any common addresses identified in the
above checks, an edge is added from $T_{a}$ to $T_{b}$ in the DAG. An
adjacency matrix data structure is implemented for representing the graph, and
an atomic array to maintain the indegree count of the vertices. The linked
list DAG graph are illustrated in the Fig. 4. We have also implemented an
parallel scheduler module with concurrent linked list structure Fig. 4. The
pseudo-code is detailed in Algorithm 1.

Figure 3: Direct acyclic graph representation of the dependencies in the
block.

Figure 4: Linked list representation of the DAG.

Algorithm 1 Multi-threaded createDAG(): $m$ threads concurrently create the
DAG

1:procedure createDAG($block$)$\triangleright$ The block to be produced or
validated is the input

2: while $1$ do

3: $T_{i}\leftarrow txnCounter.get\&inc()$ $\triangleright$ Claim the next
transaction available

4: if $T_{i}>txn\\_count$ then

5: $txnCounter.dec()$

6: return $\triangleright$ Return if all the transactions are processed

7: end if

8: Graph_Node $*txn$ = new Graph_Node

9: DAG$\rightarrow$add_node($T_{i}$, $txn$)$\triangleright$ adding the node to
the graph

10: for $T_{j}=T_{i}+1$ to $txn\\_count$ do$\triangleright$ finding dependent
transactions

11: $flagEdge$=false

12: if $T_{i}.readList\cap T_{j}.writeList$ then$\triangleright$ Checking for
RW and WW conflicts

13: $flagEdge$=True

14: end if

15: if $T_{i}.writeList\cap T_{j}.readList$ then

16: $flagEdge$=True

17: end if

18: if $T_{i}.writeList\cap T_{j}.writeList$ then

19: $flagEdge$=True

20: end if

21: if $flagEdge$ then

22: DAG$\rightarrow$add_edge($T_{i}$, $T_{j}$)

23: end if

24: end for

25: end while

26:end procedure$\triangleright$ The threads end when the DAG is complete

Transaction execution: For parallel transaction execution, we initiate
multiple threads to process the transactions in the block. Each thread selects
a transaction for execution using the indegree array. If the indegree of a
transaction is zero this indicates that the transaction does not have any
predecessor dependent transactions and can be executed ($T_{1},T_{3},$ and
$T_{2}$ in Fig. 4). If no such transactions are available, the threads wait
until one is available or end execution if all the transactions have completed
execution. Upon selecting a transaction, it is executed and the indegree of
all the outgoing edge transactions ($T_{5}$ and $T_{6}$ for $T_{1}$) is
decremented by 1. The search for a transaction with indegree zero can be
further optimized by initiating the search from the last transaction ID
selected. This further reduces the time it takes to find the next transaction.
The pseudo-code that multiple threads execute while selecting a transaction is
present in Algorithm 2

Algorithm 2 Multi-threaded selectTxn(): threads concurrently search the DAG
for next transaction to execute

27:procedure selectTxn($DAG$)

28: for $T_{i}=pos$ To $txn\\_count$ do$\triangleright$ iterate over until all
transactions to find transaction for execution

29: if $T_{i}.indeg==0$ then$\triangleright$ Checking for txn with zero
indegree

30: if $T_{i}.indeg.CAS(0,-1)$ then

31: $pos\leftarrow T_{i}$ $\triangleright$ store the last position for fast
parsing

32: return $T_{i}$

33: end if

34: end if

35: end for

36: for $T_{i}=0$ To $pos$ do$\triangleright$ iterate over until all
transactions to find transaction for execution

37: if $T_{i}.indeg==0$ then$\triangleright$ Checking for txn with zero
indegree

38: if $T_{i}.indeg.CAS(0,-1)$ then

39: $pos\leftarrow T_{i}$ $\triangleright$ store the last position for fast
parsing

40: return $T_{i}$

41: end if

42: end if

43: end for

44: return $-1$ $\triangleright$ The threads end when a transaction is
selected or all the transaction are executed

45:end procedure

###  3.2 Smart Validatior

DAG sharing: In this phase, the DAG created by the block creator in the
blockchain network is shared with the validators in the network. In this way,
the blockchain network’s validators can conserve the time taken for DAG
creation. Malicious miners in the network can exploit the DAG sharing feature
to disrupt blockchain functioning. Sharing an inapt DAG with one or more edges
missing could lead to validators malfunctioning. A DAG with additional edges
will increase the validation process and slow the whole blockchain network.

DAG validation: The DAG created by the block creator in the blockchain network
is shared with the validators in the network. In this way, the blockchain
network’s validators can conserve the time taken for DAG creation. In order to
address this security risk that is present in DAG sharing, a smart validator
is designed for verifying DAGs. The smart validator checks for missing edges
or extra edges present in the DAG shared. This is performed by multiple
threads for swift graph verification. For all the addresses accessed in the
block, a read list and a write list are maintained. By parsing the
transactions in the block, transaction IDs are added to the read and write
lists of respective addresses. First the check for missing edges is performed
by making sure that the transactions in the write list of an address have an
edge with all the transactions present in the respective read and write lists.
A failed check indicates that the DAG shared has a missing edge. During the
check, the number of outgoing edges is calculated for each transaction. We
compare the sum of the outgoing edges obtained in the above operation with the
in-degree array shared along the block. This function identifies if any extra
edges are present in the DAG. As a result of this process, the smart validator
verifies the DAG information and recognizes malicious miners. The procedure to
handle such miners depends on the type and functionalities of blockchain
technology. Malicious miners in the network can exploit the DAG sharing
feature to disrupt blockchain functioning. Sharing an inapt DAG with one or
more edges missing could lead to validators malfunctioning. A DAG with
additional edges will increase the validation process and slow the whole
blockchain network.

Algorithm 3 Multi-threaded smartValidator(): $m$ threads concurrently verify
the DAG shared

46:procedure smartValidator($DAG$)

47: while $!mMiner$ do

48: $Adds\leftarrow addsCounter.get\&inc()$ $\triangleright$ Claim the next
address for analyzing

49: if $Adds>adds\\_count$ then

50: $addsCounter.dec()$

51: return $\triangleright$ Return if all the address are processed

52: end if

53: for $i=0$ To $lenght(Adds.readList)$ do$\triangleright$ procedure for
checking for missing edges

54: $T_{i}\leftarrow Adds.readList[i]$

55: for $j=0$ To $lenght(Adds.writeList)$ do$\triangleright$ read-write
dependencies

56: $T_{j}\leftarrow Adds.writeList[j]$

57: if !checkEdge($T_{i},T_{j}$) then

58: $mMiner\leftarrow True$

59: return

60: end if

61: incDeg($T_{i},T_{j}$) $\triangleright$ Increment the indegree of lower txn
and mark the edge

62: end for

63: end for

64: for $i=0$ To $lenght(Adds.writeList)$ do

65: $T_{i}\leftarrow Adds.writeList[i]$

66: for $j=0$ To $lenght(Adds.writeList)$ do$\triangleright$ write-write
dependencies

67: $T_{j}\leftarrow Adds.writeList[j]$

68: if !checkEdge($T_{i},T_{j}$) then

69: $mMiner\leftarrow True$

70: return

71: end if

72: incDeg($T_{i},T_{j}$) $\triangleright$ Increment the indegree of lower txn
and mark the edge

73: end for

74: end for

75: for $i=0$ To $txn\\_count$ do$\triangleright$ procedure for checking for
extra edges

76: if $T_{i}.inDeg!=T_{i}.calDeg$ then $\triangleright$ Check if shared
indegree is equal to calculated indegree

77: $mMiner\leftarrow True$

78: return

79: end if

80: end for

81: end while

82:end procedure

##  4 Experiments Analysis

###  4.1 Implementation details

We have chosen Hyperledger Sawtooth as our testing platform since it has a
parallel scheduler. To incorporate the DAG framework into the Sawtooth
architecture, we have to modify the current parallel scheduler module. Due to
the modular nature of Sawtooth, any modifications made to a module can be
restricted within the module itself without impacting the whole architecture.
For this we need to make sure the functions through which other modules
interact with the parallel scheduler module are modified with care.

We have now implemented the DAG sharing and Smart validator modules in
Sawtooth 1.2.6. Our modulues are in CPP language while the Sawtooth is a
combinatin of Rust and Python. We have choosen CPP for its concurrent
capabilities with low overhead cost. For DAG sharing, we have modified the
block after the block creator has verified that all the transactions in the
block are valid. In Sawtooth 1.2.6 we used the input and output addresses
present in the transaction structure. Every transaction in the DAG is
represented by a graph node and the outgoing edges indicate dependent
transactions. In order to ensure smart validation, the DAG is shared across
the block. We have used the dependencies list component of the transaction
structure to incorporate DAG into the block. This modified block is shared
with the network for validation.

Initially, we implemented the DAG using a linked list data structure. This is
ideal when the size of the graph is unknown and the graph needs to be dynamic.
Given that the number of transactions in a block does not change and there is
a limit to the number of transactions a block can contain, we have designed an
adjacency matrix implementation for DAG. The results have shown further
improvement over the linked list implementation. This is because the adjacency
matrix is direct access whereas the linked list implementation would require
parsing the list to reach the desired node.

In Sawtooth 1.2.6 block validators, the smart validator is implemented. The
DAG is recreated using the dependencies list provided in the transaction by
the block creator. This optimizes the time taken to create the DAG again in
the validators by comparing all the input and output addresses in the
transactions. Once created the smart validator first checks for missing edges
that should have been present in the DAG shared by the block creator. This is
done by generating a list of transactions that access each address and
verifying if an edge is present between them. While doing this, we all keep
track of the outgoing edge count for each transaction. If the count matches
the DAG shared by the block creator that indicates no edges are missing. This
way we verify the DAG shared faster than creating the DAG again, optimizing
the throughput.

Transaction Families:  We have implemented four transaction families
SimpleWallet, Intkey, Voting and Insurance. In SimpleWallet one can create
accounts, deposit, withdraw and transfer money. In Intkey clients are
increment and decrement values stored in different variables. In Voting
transaction family the transactions are create parties, add voters and voters
can vote to one of the parties. Insurance family is a data storage transaction
family where user details like ID, name, address details are stored and
manipulated. To control the percentage of conflicts between transactions, one
must have control over the keys created. We have modified the batch creation
technique in these transaction families to allow the user to submit multiple
transactions in a batch. This way we can not just control the number of
transactions in batch but also the conflicts among the transactions in a
batch. We individually observed each transaction family behaviour under
various experiments and a mix of all four types of types of transaction in a
block.

###  4.2 Experiments

We have extensively tested our proposed framework by implementing it in
Hyperledger Sawtooth 1.2.6. To test the framework across different scenarios
we have devised three conflict parameters (CP) that indicate the level of
dependency among the transaction. Conflict parameter one (CP1) is the portion
of transactions that have at least one dependency. CP2 ratio of dependencies
(edges) to total possibles dependencies. CP3 degree of parallelism in the DAG
i.e., the number of independent components in the graph. We have designed four
experiments, each varying one parameter while the rest of the parameters are
constant. The four parameters are number of blocks, number of transaction in
the block, degree of dependency and number of threads. Each named experiment
setup one to four respectively. We have named adjacency matrix implementation
of our proposed framework as _Adj_DAG_ , linked list implementation as
_LL_DAG_. The Sawtooth inbuilt parallel scheduler used tree data structure,
accordingly we have named it as _Tree_ and serial execution output as _Serial_
in our results. We have observed that due to the presence of global lock in
python, the change in number of threads has not impacted the performance
significantly. Due to this we have not presented the experiment four results
in this work but are available in appendix C [13].

It can be observed from Figure 5, that adjacency matrix and linked list
implementation of our proposed framework perform significantly better than the
tree based parallel scheduler in Sawtooth and serial execution. We have
illustrated here some of the experiments we have conducted and the rest can be
found in appendix C [13]. Figure 5(a), 5(d) and 5(g) illustrate the impact of
change in number of blocks on various schedulers. On average the speedup of
_Adj_DAG_ over _Serial_ is $1.58$ and _LL_DAG_ is $1.43$ times, while _Tree_
is $1.22$. The average speedup of _Adj_DAG_ over _Tree_ is $1.29$ and _LL_DAG_
is $1.17$ times.

(a) SimpleWallet: Experiment one, CP1

(b) SimpleWallet: Experiment two, CP2

(c) SimpleWallet: Experiment three, CP3

(d) Voting: Experiment one, CP3

(e) Voting: Experiment two, CP2

(f) Voting: Experiment three, CP1

(g) Mixed Block: Experiment one, CP3

(h) Mixed Block: Experiment two, CP2

(i) Mixed Block: Experiment three, CP1

(j) DS creation time varying the number of blocks

(k) DS creation time varying the number of transaction per Block

(l) DS creation time varying the dependency percentage

Figure 5: Detailed analysis of our proposed framework performance with both
adjacency matrix and linked list implementations in Hyperledger Sawtooth
1.2.6.

Experiment two results are depicted in Figures 5(b), 5(e) and 5(h). We can
observe that the gap between serial and the parallel schedulers increases with
increase in number of transactions in block. As higher number of transactions
more scope for concurrency. In Experiment three we have varied the degree of
dependency between the transactions to over its impact on the transactions per
second (TPS). The dependency amongs the tranactions is increased by making
multiple transactions access the same accounts/addresses. Ideally varying the
conflict percentage without changing the number of transactions should not
impact serial execution throughput. But decrease in number of memory accesses
improves the execution time. We can observe this phenomenon in serial
execution time in Figures 5(c), 5(f) and 5(i). We can also observe that while
in _ADJ_DAG_ and _LL_DAG_ the effects balance and we can observe a steady TPS,
in _Tree_ scheduler the performance further decreases the TPS.

Figures 5(d), 5(e) and 5(f) show the Voting transaction family behaviour under
experiements one, two and three. Unlike the rest of the transaction families,
The _Serial_ execution is faster in _Tree_ scheduler in Voting transaction
family. We have discovered that the entire voters list and the parties are
list are accesses for any transaction in this family instead of the one
particular voter and party addresses. We should note that the design of the
transaction family (smart contract) plays a crucial role in the performance
optimization of the blockchain. One can observe that the _ADJ_DAG_ and
_LL_DAG_ still perform better as they use transactions to represent the
dependency data structure unlike _Tree_ scheduler that uses addresses.

The _Smart Validator_ framework efficiently verifies the DAG shared by the
miner and eliminates the need to reconstruct the DAG at every block validator.
The execution time of the smart validator and adjacency DAG scheduler will
only vary in the dependency graph creation aspect. To highlight the
optimization acheived through smart validator we have analyzed the dependency
data structure (DS) creation and verification time for various schedulars in
Figure 5. One can observe that the _smart validator_ takes the least execution
time from the Figures 5(j), 5(k) and 5(l). From observing Figure 5(l) we can
state that the _smart validator_ is stable against the variations in the
dependency in the graph. The rest of the extensive experiments results
including experiments on _Intkey_ and _Insurance_ transaction families can be
found in appendix C [13].

##  5 Related research

In the past few years, blockchain technology has gained tremendous popularity
and is used in a wide variety of fields. Although blockchains are capable of
offering a variety of advantages, one of the most cited concerns is
scalability. Consensus protocols and transaction throughput are the two major
bottlenecks of blockchain performance. In contrast to proof of work (PoW),
alternative consensus protocols like proof of stake (PoS) and proof of elapsed
time (PoET) are introduced to minimize consensus time. However, transaction
throughput continues to be a hindrance to scalability. Exercising parallel
execution of transactions in a block is one of the solutions to optimize
blockchains.

Dickerson et al. [7] introduced the concept of parallel execution of Ethereum
[18] transactions using Software Transactional Memory (STM). The miners
execute transactions in the block using STM, and the serializable concurrent
state is discovered. This is then shared with the validators to achieve
deterministic execution. Following this there have been multiple STM-based
concurrent transaction execution frameworks for blockchains [1, 2, 8, 4].
Besides the significant overhead associated with executing transactions
through STMs, transactions sometimes fail due to dependencies and must be re-
executed. Another drawback is that they cannot have operations that cannot be
undone, which is a significant obstacle to smart contract design. During
concurrent execution, STM-based approaches identify conflicts among
transactions dynamically, i.e., during execution. This results in various
transactions failing or rolling back to resolve the conflict. This has a
significant impact on throughput and is not optimal for blocks with high
interdependencies. In general, a dynamic approach is ideal, but it is not
necessary for blockchains whose addresses are either included in the
transactions or are easily inferred. For such systems, we propose a parallel
execution framework for transactions in a block.

Sharding is another popular technique to address scaling issues in
blockchains. In this, the nodes present in the network are categorized into
small groups. Each group processes transactions parallelly with the other
groups. Sharding is being explored earnestly as a solution to scalability
issues [11, 19, 9, 20, 6, 15, 14, 5, 21]. The criteria for sharding are
different in each approach. Few are specifically designed for monetary
transactions in blockchains [9, 20]. This leads to smart contract transactions
being processed on a single shard leading to an inefficient distribution of
computational work. The implementation of transactions that span across smart
contracts becomes intricate with sharding. Protocols have to be designed
specifically for inter-shard communication further increasing the complexity
of the design [6]. The sharding technique limits the degree of parallelization
to the number of shards irrespective of actual capacity. If the shards are
dynamic, in the worst case the number of shards is equal to the number of
transactions. This framework is unsuitable for transactions with high
interdependencies.

##  6 Conclusion and future work

In this paper, we designed a framework for concurrent transaction execution in
blockchains through static analysis of miners and validators of the network.
This framework introduces parallel scheduler and smart validator modules into
the blockchain node architecture. The parallel scheduler is responsible for
identifying the dependencies among the transactions in the block and
scheduling them for conflict-free execution. The determined dependencies are
represented by a direct acyclic graph (DAG) and are shared along with the
block to minimize the validation time of the blockchain. DAGs are validated
using the smart validator, which determines if malicious miners have shared
inaccurate graphs. Our framework has been extensively tested in Hyperledger
Sawtooth 1.2.6. Next, we plan to improve fault tolerance and scalability for
each blockchain node individually.

## References

  * [1] Amiri, M.J., Agrawal, D., El Abbadi, A.: Parblockchain: Leveraging transaction parallelism in permissioned blockchain systems. In: 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS). pp. 1337–1347 (2019). https://doi.org/10.1109/ICDCS.2019.00134
  * [2] Anjana, P.S., Attiya, H., Kumari, S., Peri, S., Somani, A.: Efficient concurrent execution of smart contracts in blockchains using object-based transactional memory. In: Georgiou, C., Majumdar, R. (eds.) Networked Systems. pp. 77–93. Springer International Publishing, Cham (2021)
  * [3] Anjana, P.S., Kumari, S., Peri, S., Rathor, S., Somani, A.: An efficient framework for optimistic concurrent execution of smart contracts. In: 2019 27th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP). pp. 83–92 (2019). https://doi.org/10.1109/EMPDP.2019.8671637
  * [4] Anjana, P.S., Kumari, S., Peri, S., Rathor, S., Somani, A.: Optsmart: a space efficient optimistic concurrent execution of smart contracts. Distributed and Parallel Databases (May 2022). https://doi.org/10.1007/s10619-022-07412-y, https://doi.org/10.1007/s10619-022-07412-y
  * [5] Baheti, S., Anjana, P.S., Peri, S., Simmhan, Y.: Dipetrans: A framework for distributed parallel execution of transactions of blocks in blockchains. Concurrency and Computation: Practice and Experience 34(10), e6804 (2022). https://doi.org/https://doi.org/10.1002/cpe.6804, https://onlinelibrary.wiley.com/doi/abs/10.1002/cpe.6804
  * [6] Dang, H., Dinh, T.T.A., Loghin, D., Chang, E.C., Lin, Q., Ooi, B.C.: Towards scaling blockchain systems via sharding. In: Proceedings of the 2019 International Conference on Management of Data. p. 123–140. SIGMOD ’19, Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/3299869.3319889, https://doi.org/10.1145/3299869.3319889
  * [7] Dickerson, T., Gazzillo, P., Herlihy, M., Koskinen, E.: Adding concurrency to smart contracts. p. 303–312. PODC ’17, Association for Computing Machinery, New York, NY, USA (2017). https://doi.org/10.1145/3087801.3087835, https://doi.org/10.1145/3087801.3087835
  * [8] Gelashvili, R., Spiegelman, A., Xiang, Z., Danezis, G., Li, Z., Malkhi, D., Xia, Y., Zhou, R.: Block-stm: Scaling blockchain execution by turning ordering curse to a performance blessing (2022). https://doi.org/10.48550/ARXIV.2203.06871, https://arxiv.org/abs/2203.06871
  * [9] Kokoris-Kogias, E., Jovanovic, P., Gasser, L., Gailly, N., Syta, E., Ford, B.: Omniledger: A secure, scale-out, decentralized ledger via sharding. In: 2018 IEEE Symposium on Security and Privacy (SP). pp. 583–598 (2018). https://doi.org/10.1109/SP.2018.000-5
  * [10] Kunz, T., Black, J.P., Taylor, D.J., Basten, T.: POET: Target-System Independent Visualizations of Complex Distributed-Applications Executions. The Computer Journal 40(8) (1997)
  * [11] Luu, L., Narayanan, V., Zheng, C., Baweja, K., Gilbert, S., Saxena, P.: A secure sharding protocol for open blockchains. p. 17–30. CCS ’16, Association for Computing Machinery, New York, NY, USA (2016). https://doi.org/10.1145/2976749.2978389, https://doi.org/10.1145/2976749.2978389
  * [12] Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system (2009)
  * [13] Piduguralla, M., Chakraborty, S., Anjana, P.S., Peri, S.: An efficient framework for execution of smart contracts in hyperledger sawtooth (2023). https://doi.org/10.48550/ARXIV.2302.08452, https://arxiv.org/abs/2302.08452
  * [14] Pîrlea, G., Kumar, A., Sergey, I.: Cosplit (pldi 2021 artefact) (2021), https://doi.org/10.5281/zenodo.4674301
  * [15] Valtchanov, A., Helbling, L., Mekiker, B., Wittie, M.P.: Parallel block execution in socc blockchains through optimistic concurrency control. In: 2021 IEEE Globecom Workshops (GC Wkshps). pp. 1–6 (2021). https://doi.org/10.1109/GCWkshps52748.2021.9682147
  * [16] Vasin, P.: Blackcoin’s proof-of-stake protocol v2. URL: https://blackcoin. co/blackcoin-pos-protocol-v2-whitepaper. pdf 71 (2014)
  * [17] Weikum, G., Vossen, G.: Chapter three - concurrency control: Notions of correctness for the page model. In: Weikum, G., Vossen, G. (eds.) Transactional Information Systems, pp. 61–123. The Morgan Kaufmann Series in Data Management Systems, Morgan Kaufmann, San Francisco (2002). https://doi.org/https://doi.org/10.1016/B978-155860508-4/50004-1, https://www.sciencedirect.com/science/article/pii/B9781558605084500041
  * [18] Wood, G.: Ethereum: A secure decentralised generalised transaction ledger
  * [19] Zamani, M., Movahedi, M., Raykova, M.: Rapidchain: Scaling blockchain via full sharding. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. p. 931–948. CCS ’18, Association for Computing Machinery, New York, NY, USA (2018). https://doi.org/10.1145/3243734.3243853, https://doi.org/10.1145/3243734.3243853
  * [20] Zamani, M., Movahedi, M., Raykova, M.: Rapidchain: Scaling blockchain via full sharding. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. p. 931–948. CCS ’18, Association for Computing Machinery, New York, NY, USA (2018). https://doi.org/10.1145/3243734.3243853, https://doi.org/10.1145/3243734.3243853
  * [21] Zheng, P., Xu, Q., Luo, X., Zheng, Z., Zheng, W., Chen, X., Zhou, Z., Yan, Y., Zhang, H.: Aeolus: Distributed execution of permissioned blockchain transactions via state sharding. IEEE Transactions on Industrial Informatics 18(12), 9227–9238 (2022). https://doi.org/10.1109/TII.2022.3164433

## Appendix

##  Appendix 0.A Hyperledger Sawtooth

###  0.A.1 Introduction

Blockchain is a decentralized, distributed, immutable ledger system shared
across a network introduced in 2008. The Hyperledger Foundation is “an open-
source collaborative effort to advance cross-industry blockchain technologies.
It is a global collaboration, hosted by The Linux Foundation, including
leaders in finance, banking, IoT, supply chain, manufacturing, and technology”
[1]. One of the most popular Hyperledger products is Hyperledger Sawtooth. A
key goal of Sawtooth is to make Smart Contract execution safe, which is
crucial for enterprise applications [2]. Hyperledger Sawtooth is gaining
popularity for smart contract execution because of its highly modular
approach. It facilitates the Sawtooth core design such that the transaction
rules, permissions, and consensus algorithms can be customized according to
the particular area of application. Sawtooth has some distinctive features:

Separation: The separation between the application level and the core system.
With Sawtooth, users can build their models based on their business needs.
Transaction rules, permissions, and consensus settings are handled in the
Transaction Processing part. The Transaction Processors are the Server side of
the application, while validators manage the core functionalities like
verifying the transactions submitted using the particular consensus algorithm.

Multi Language Support: One of the striking features and the reason for the
popularity of Sawtooth is the multiple language support, including Python,
Javascript, Go, Rust, C++, etc., for the client and server sides. The language
best suited for the desired operation can be chosen using one of the SDKs
among the ones provided. Parallel transaction Execution: Parallel transaction
execution is one of the most sought-after features in blockchain to enhance
speed and performance. Hyperledger Sawtooth facilitates that by splitting
transactions into parallel flows.

Consensus: The consensus algorithm provides a way to ensure mutual agreement
and trust among a group of participants. As Sawtooth separates consensus from
transaction semantics, the user can implement multiple types of consensus on
the same blockchain. In addition, it allows the user to change the consensus
algorithm on a running blockchain. Other notable features of Sawtooth include
permissioned and permissionless architecture, compatibility with Seth Ethereum
Contracts.

###  0.A.2 Architecture

In Sawtooth, the modular design separates the application and core levels.
Sawtooth views smart contracts as a state machine or transaction processor
[3]. By creating and applying transactions, the state can be modified. One or
more transactions wrapped together form a batch. A batch is the atomic unit of
change in the system. Multiple batches are combined to form a block (Figure
1). The principal modules observed in Figure 7 of the Sawtooth blockchain node
are, Validator: A validator is made up of the state management, transaction
handling, and interconnection network components of a Sawtooth node.

Global State: Sawtooth uses an addressable Radix Merkle tree to store data for
transaction families. Like a Merkle tree the successive node hashes are stored
from leaf-to-root and like a Radix tree, the addresses uniquely identify the
paths to leaf nodes.

Journal: The Block Completer, Block Validator, and Chain Controller modules
make up the Journal of the node. All these modules work together to produce
and validate blocks in the network. The blocks under processing are stored in
BlockCache and BlockStore.

Transaction Scheduler: Transaction scheduler selects the transaction for
execution. Sawtooth parallel scheduler utilizes a tree structure to keep track
of dependencies using a Merkle tree. Each data location has read and write
lists that contain the ID of the transactions that are accessing them.

Transaction Executor: The transaction executor invokes the scheduler to select
a transaction for execution either for block production or block validation.
The context is collected from the context manager and submitted along with the
transaction to the transaction processor by the executor.

Transaction Families: Smart contracts are called transaction families in
Hyperledger Sawtooth. The logic of the smart contracts is encoded into the
transaction processor. Each smart contract has its own transaction processor
and client. The transaction client checks the syntax of the transaction
submitted and wraps them into a batch before submitting to the rest API.

Rest API: The clients interact with Sawtooth validator through Rest API
module. Clients can submit transactions to the network or read the blocks
added to the chain. Verifying the validity of the requests is the
responsibility of the validator of the Sawtooth node while the Rest API acts
as an intermediary.

The basic flow of execution can be, in short, described as:

  1. 1.

The client builds transactions and batches and signs them using the user’s
private key.

  2. 2.

The explicit dependencies within a batch are indicated through dependencies
filed in the transaction header.

  3. 3.

The transaction travels through a journal and is included in a block.

  4. 4.

The parallel scheduler calculates implicit dependencies.

  5. 5.

The batches are submitted to the validator via REST API.

  6. 6.

The validator combines the batches into blocks through the block publisher.

  7. 7.

Block publisher gives the batches to the scheduler.

  8. 8.

The scheduler submits the transactions to the executor.

  9. 9.

The executor gives the transaction and the related context to the transaction
processor.

  10. 10.

The transaction processor validates the transaction using the business logic
given

  11. 11.

Then the consensus protocol is implemented to see if the valid block should be
added to the chain or not.

Figure 6: Blockchain node architecture of Hyperledger Sawtooth

In Figure 7, the blue path is the block production and the green path is the
block validation process. Transactions in a block in blockchains are executed
by miners for block production and by validators for block validation. In most
of the frameworks designed for concurrent execution, the model is the same for
miners and validators. This is redundant as the analysis performed at the
miners’ end for concurrency is not utilized across the networks during
validation. In the Optsmart framework [4] STMs are implemented for efficient
concurrent execution and a DAG is used to represent conflicts between
transactions. In this work, the use of the shared DAG created by the miner is
presented. Additionally, it is discussed how it can be exploited by malicious
miners to disrupt the network. A smart multi-threaded validator (SMV) [3] is
proposed by Anjana et.al, which validates the DAG provided by the miner.
During execution, the smart multi-threaded validator verifies the DAG shared
dynamically by keeping track of transactions accessing various addresses
through global and local counters. There exists a flaw in the SMV design as it
is vulnerable to thread-serial execution (TSE). If fewer than the optimal
number of threads are executing the transactions, the SMV will fail to
identify missing edges. As the SMV identifies missing edges only when two or
more transactions are accessing an address simultaneously. Assume the
validators have low concurrent execution capability and did not execute the
transactions in parallel. In that case, even if the transactions accessing the
same address do not have edges, the SMV will not detect them. The SMV design
does not account for extra edges introduced into the DAG by a malicious miner.
Extra edges would result from forced serial execution of transactions. This
would result in lower throughput. We present a framework with a parallel
scheduler and a smart validator that overcomes the disadvantages discussed
here.

Figure 7: Lifecycle of Sawtooth transaction

##  Appendix 0.B Proofs

We aim to prove safety and liveliness of our proposed scheduler. We prove the
safety by proving that the history of the execution is conflict serializable
to the sequential execution of the transactions in the order they are present
in the batch. The liveness of the scheduler is proved by proving that all
transaction will eventually be committed.

######  Definition 1 (Dependency Graph)

The dependency graph ($DG$) is constructed to represent the dependency
information among the transactions in the block ($B$). The vertices of the
graph $DG$ represent the transactions while the edges represent the dependency
relation between the two transactions.

$DG$ is defined as:

$DG(B)=(V,E),$ where, $\\{t_{1},t_{2},...,t_{n}\\}\in V,$

$(t_{i},t_{j})\in E\iff t_{i}\neq t_{j}\land(\exists p\in t_{i})(\exists q\in
t_{j})$ $(p,q)\in conf(B)\land i<j$.

$p,q$ are operations in $t_{i}$ and $t_{j}$ respectively. $conf(B)$ are the
read-write, write-write and write-read conflicting operations to the same
address.

###### Lemma 1

The dependency graph $DG$ is acyclic

###### Proof

Let us assume that $DG(B)$ is cyclic.

This means that there a path from $t_{i}$ to $t_{i}$ through $t_{j}$ present
in $DG(B)$.

Let the path be $t_{i},t_{k_{1}},t_{k_{2}},...t_{j},...t_{k_{n}},t_{i}$

$\Rightarrow t_{i}<t_{k_{1}}<t_{k_{2}}<...t_{j}<...t_{k_{n}}<t_{i}$
(Definition: 1)

This gives a contradiction, $t_{i}<t_{j}\land t_{j}<t_{i}\land i\neq j$

Thus our initial assumption that $DG(B)$ not being acyclic is not true.

We can conclude that $DG(B)$ is acyclic.

######  Definition 2 (Possible histories ($H=DG(Gen)$))

The set $H$ is the set of all the possible histories using a given dependency
graph $DG$.

$\forall h\in H,h$ is a resultant history of execution using $DG(B)$

Given a $DG$ for a block B, the transactions with indegree zero ($t_{i}$) are
scheduled for execution and are flagged (marked that the txn is in execution).
Once the commit of the transaction is performed the outgoing edges from
$t_{i}$ are removed from the graph.

###### Lemma 2

For a given $h\in H$. $h$ is the topological sort of the graph $DG$

###### Proof

Topological sorting is a linear ordering of vertices of a graph such that if
an edge is present between $p$ and $q$, the vertex $p$ comes before $q$ in the
sort. The graph should be acyclic and directed.

Based on Lemma: 1, we know that $DG$ is acyclic. From the definition of Def:
2, we know that the possible histories contain all the transaction in the $DG$
and if an edge is present from $t_{i}$ to $t_{j}$, the indegree of $t_{j}$
would be greater than zero and $t_{j}$ will not be scheduled for execution
unless $t_{i}$ is committed.

This implies that all the operation of $t_{i}$ occur before any operations of
$t_{j}$. Therefore $t_{i}$ is present present before $t_{j}$ in the history
$h$.

######  Definition 3 (Conflict graph (G))

Let $s$ be a schedule. the conflict graph, also known as the serialization
graph, $G(s)=(V,E)$ of $s$, is defined by

$V=commit(s),$

$(t,t^{\prime})\in E\iff t\neq t^{\prime}\land(\exists p\in t)(\exists q\in
t^{\prime})(p,q)\in conf(s)$

###### Lemma 3

The dependency graph ($DG$) for a given block is isomorphic to the conflict
graph of all the schedules of set S.

###### Proof

let $DG(B)=(V,E)$,

$G(S)=(V^{\prime},E^{\prime})$

$V=V^{\prime}=\\{t_{1},t_{2},...,t_{n}\\}$

if $\exists(t_{i},t_{j})\in V^{\prime}\Rightarrow(\exists p\in t_{i})(\exists
q\in t_{j})(p,q)\in conf(s)$

$\Rightarrow(t_{i},t_{j})\in V$ (Lemma: LABEL:lemma:txn_order)

This implies $E=E^{\prime}$

###### Theorem 0.B.1

Any history $h\in H$ is conflict equivalent to
$h_{0}={t_{1},t_{2},t_{3}....t_{n-1},t_{n}}$ i.e., . the sequential execution
of ascending order of the transaction.

###### Proof

Two histories are conflict equivalent if they have same operations and same
conflict relations [17].

This is true for all elements of $h$

Therefore all the elements in $S$ are conflict equivalent to each
other.$\forall s\in S,G(s)$ is isometric to $DG(B)$.

###### Theorem 0.B.2

All the histories in set $S$ are conflict serializable (CSR).

###### Proof

Let $h$ be a history in $H$. $h\in CSR\iff CG(h)$ is acyclic [17].

We have show that $\forall h\in H,G(h)$ is isometric to $DG(B)$.

We can conclude that $DG(B)$ is acyclic implying $h\in CSR$

##  Appendix 0.C Results

###  0.C.1 SimpleWallet Transaction Family

Experiment 1:

No of Blocks | CP1 | CP2 | CP3
---|---|---|---
| ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial
10 | 139 | 158 | 142 | 241 | 175 | 181 | 179 | 212 | 173 | 202 | 177 | 275
20 | 292 | 331 | 296 | 473 | 343 | 377 | 357 | 426 | 349 | 405 | 351 | 577
30 | 419 | 474 | 431 | 887 | 505 | 564 | 534 | 633 | 523 | 599 | 523 | 908
40 | 580 | 638 | 583 | 1103 | 697 | 720 | 716 | 879 | 687 | 811 | 700 | 1210
50 | 699 | 834 | 725 | 1372 | 852 | 950 | 893 | 1076 | 859 | 986 | 881 | 1463

Experiment 2:

Txns per Block | CP1 | CP2 | CP3
---|---|---|---
| ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial
200 | 54 | 56 | 54 | 143 | 65 | 68 | 59 | 73 | 67 | 70 | 67 | 75
400 | 113 | 121 | 96 | 181 | 134 | 143 | 124 | 153 | 135 | 142 | 134 | 156
600 | 163 | 178 | 147 | 248 | 205 | 213 | 185 | 253 | 200 | 221 | 185 | 254
800 | 201 | 253 | 195 | 282 | 259 | 290 | 244 | 318 | 263 | 303 | 250 | 326
1000 | 279 | 332 | 252 | 375 | 343 | 366 | 313 | 413 | 352 | 405 | 329 | 426
1200 | 342 | 403 | 323 | 493 | 424 | 467 | 430 | 505 | 420 | 503 | 413 | 538

Experiment 3:

Dependency percentage | CP1 | CP2 | CP3
---|---|---|---
| ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial
0 | 372 | 378 | 350 | 712 | 364 | 354 | 341 | 773 | 363 | 358 | 347 | 774
20 | 354 | 393 | 335 | 786 | 364 | 438 | 356 | 767 | 355 | 482 | 322 | 726
40 | 365 | 454 | 347 | 717 | 361 | 489 | 350 | 758 | 359 | 500 | 322 | 763
60 | 348 | 501 | 351 | 742 | 360 | 513 | 344 | 760 | 362 | 503 | 327 | 748
80 | 354 | 579 | 350 | 767 | 350 | 545 | 341 | 779 | 352 | 523 | 329 | 745
100 | 349 | 624 | 336 | 708 | 354 | 571 | 382 | 726 | 354 | 664 | 395 | 755

###  0.C.2 Intkey Transaction Family

Experiment 1:

No of Blocks | CP1 | CP2 | CP3
---|---|---|---
| ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial
10 | 115 | 126 | 118 | 200 | 112 | 135 | 117 | 138 | 111 | 133 | 115 | 132
20 | 231 | 252 | 238 | 402 | 224 | 266 | 231 | 274 | 223 | 262 | 230 | 269
30 | 346 | 374 | 358 | 597 | 336 | 394 | 346 | 412 | 333 | 391 | 349 | 398
40 | 459 | 497 | 473 | 799 | 448 | 540 | 470 | 555 | 446 | 523 | 461 | 535
50 | 573 | 631 | 597 | 1009 | 562 | 671 | 583 | 690 | 551 | 656 | 577 | 668

Experiment 2:

Txns per Block | CP1 | CP2 | CP3
---|---|---|---
| ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial
200 | 39 | 41 | 39 | 54 | 39 | 42 | 39 | 47 | 39 | 41 | 39 | 48
400 | 83 | 84 | 87 | 121 | 81 | 94 | 84 | 106 | 82 | 91 | 89 | 96
600 | 127 | 138 | 134 | 198 | 122 | 147 | 131 | 163 | 126 | 146 | 130 | 172
800 | 181 | 191 | 188 | 281 | 172 | 205 | 181 | 214 | 172 | 203 | 179 | 201
1000 | 217 | 248 | 227 | 395 | 221 | 261 | 232 | 274 | 224 | 255 | 228 | 259
1200 | 268 | 302 | 281 | 573 | 280 | 327 | 285 | 345 | 229 | 264 | 237 | 263

Experiment 3:

Dependency percentage | CP1 | CP2 | CP3
---|---|---|---
| ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial
0 | 224 | 226 | 228 | 517 | 226 | 228 | 227 | 504 | 227 | 239 | 227 | 246
20 | 227 | 242 | 231 | 436 | 228 | 249 | 229 | 352 | 229 | 242 | 231 | 322
40 | 229 | 244 | 232 | 424 | 229 | 253 | 230 | 318 | 230 | 245 | 233 | 346
60 | 230 | 249 | 235 | 383 | 231 | 264 | 233 | 274 | 235 | 247 | 236 | 382
80 | 233 | 252 | 237 | 333 | 233 | 272 | 235 | 264 | 238 | 251 | 239 | 403
100 | 236 | 254 | 250 | 315 | 234 | 279 | 245 | 249 | 240 | 254 | 244 | 449

###  0.C.3 Voting Transaction Family

Experiment 1:

No of Blocks | CP1 | CP2 | CP3
---|---|---|---
| ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial
10 | 81 | 160 | 116 | 128 | 81 | 187 | 128 | 151 | 80 | 183 | 122 | 154
20 | 162 | 318 | 247 | 254 | 162 | 368 | 255 | 291 | 161 | 352 | 239 | 312
30 | 241 | 469 | 366 | 382 | 239 | 556 | 386 | 447 | 243 | 535 | 364 | 458
40 | 323 | 646 | 485 | 511 | 317 | 749 | 509 | 596 | 323 | 746 | 478 | 616
50 | 404 | 797 | 607 | 623 | 396 | 933 | 633 | 728 | 399 | 937 | 604 | 776

Experiment 2:

Txns per Block | CP1 | CP2 | CP3
---|---|---|---
| ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial
200 | 27 | 46 | 19 | 41 | 27 | 44 | 20 | 40 | 28 | 45 | 20 | 40
400 | 59 | 102 | 42 | 90 | 56 | 102 | 45 | 87 | 59 | 103 | 44 | 88
600 | 90 | 166 | 74 | 139 | 91 | 175 | 85 | 144 | 91 | 178 | 80 | 148
800 | 126 | 236 | 131 | 189 | 124 | 265 | 149 | 212 | 121 | 265 | 140 | 224
1000 | 160 | 317 | 212 | 250 | 160 | 370 | 246 | 299 | 157 | 345 | 230 | 307
1200 | 199 | 414 | 351 | 400 | 200 | 502 | 390 | 409 | 196 | 488 | 359 | 399

Experiment 3:

Dependency percentage | CP1 | CP2 | CP3
---|---|---|---
| ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial
0 | 157 | 460 | 230 | 408 | 155 | 457 | 234 | 408 | 156 | 466 | 230 | 407
20 | 159 | 456 | 233 | 398 | 157 | 427 | 240 | 365 | 158 | 441 | 230 | 392
40 | 160 | 434 | 233 | 372 | 158 | 382 | 246 | 307 | 158 | 401 | 231 | 343
60 | 161 | 396 | 246 | 331 | 159 | 339 | 255 | 271 | 161 | 363 | 231 | 291
80 | 162 | 338 | 256 | 265 | 160 | 294 | 266 | 225 | 163 | 300 | 234 | 226
100 | 162 | 273 | 250 | 175 | 160 | 272 | 250 | 169 | 164 | 274 | 249 | 174

###  0.C.4 Insurance Transaction Family

Experiment 1:

No of Blocks | CP1 | CP2 | CP3
---|---|---|---
| ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial
10 | 46 | 51 | 44 | 154 | 46 | 56 | 46 | 92 | 45 | 55 | 44 | 88
20 | 96 | 97 | 82 | 312 | 93 | 111 | 95 | 188 | 91 | 111 | 88 | 175
30 | 143 | 155 | 137 | 466 | 133 | 169 | 141 | 275 | 140 | 169 | 128 | 258
40 | 183 | 191 | 175 | 635 | 188 | 227 | 186 | 364 | 177 | 227 | 174 | 340
50 | 226 | 238 | 214 | 769 | 234 | 278 | 236 | 466 | 233 | 278 | 217 | 438

Experiment 2:

Txns per Block | CP1 | CP2 | CP3
---|---|---|---
| ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial
200 | 15 | 16 | 14 | 40 | 14 | 20 | 13 | 36 | 14 | 20 | 13 | 35
400 | 30 | 32 | 32 | 90 | 30 | 42 | 30 | 70 | 31 | 42 | 30 | 70
600 | 50 | 49 | 46 | 148 | 47 | 68 | 48 | 112 | 50 | 68 | 48 | 105
800 | 70 | 76 | 72 | 226 | 70 | 90 | 70 | 155 | 67 | 90 | 70 | 151
1000 | 96 | 106 | 97 | 309 | 95 | 109 | 88 | 206 | 90 | 109 | 88 | 192
1200 | 118 | 122 | 122 | 420 | 115 | 149 | 115 | 256 | 113 | 149 | 115 | 235

Experiment 3:

Dependency percentage | CP1 | CP2 | CP3
---|---|---|---
| ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial
0 | 93 | 87 | 82 | 398 | 91 | 99 | 84 | 404 | 89 | 90 | 81 | 164
20 | 94 | 95 | 83 | 367 | 92 | 108 | 89 | 247 | 94 | 93 | 84 | 250
40 | 96 | 98 | 86 | 329 | 93 | 112 | 94 | 213 | 96 | 97 | 90 | 301
60 | 98 | 101 | 87 | 295 | 94 | 114 | 95 | 194 | 98 | 99 | 93 | 340
80 | 100 | 102 | 91 | 244 | 97 | 132 | 98 | 191 | 102 | 105 | 96 | 386
100 | 103 | 106 | 93 | 205 | 103 | 148 | 102 | 175 | 105 | 117 | 100 | 421

###  0.C.5 Mixed Transaction Family

Experiment 1:

No of Blocks | CP1 | CP2 | CP3
---|---|---|---
| ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial
10 | 118 | 150 | 129 | 203 | 136 | 171 | 151 | 178 | 134 | 180 | 148 | 209
20 | 244 | 308 | 269 | 400 | 268 | 347 | 300 | 355 | 271 | 356 | 293 | 433
30 | 356 | 448 | 396 | 688 | 396 | 520 | 450 | 532 | 406 | 531 | 440 | 668
40 | 486 | 604 | 531 | 879 | 540 | 682 | 603 | 727 | 536 | 723 | 585 | 893
50 | 594 | 774 | 663 | 1094 | 665 | 876 | 751 | 893 | 667 | 891 | 736 | 1093

Experiment 2:

Txns per Block | CP1 | CP2 | CP3
---|---|---|---
| ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial
200 | 44 | 50 | 41 | 95 | 49 | 56 | 44 | 58 | 50 | 56 | 48 | 60
400 | 92 | 107 | 80 | 143 | 101 | 120 | 94 | 125 | 103 | 120 | 100 | 124
600 | 136 | 165 | 126 | 208 | 156 | 187 | 146 | 203 | 154 | 191 | 145 | 207
800 | 177 | 233 | 177 | 259 | 204 | 262 | 204 | 265 | 205 | 268 | 205 | 269
1000 | 234 | 307 | 235 | 349 | 267 | 341 | 276 | 350 | 272 | 353 | 279 | 354
1200 | 288 | 380 | 320 | 490 | 332 | 441 | 384 | 441 | 316 | 439 | 355 | 434

Experiment 3:

Dependency percentage | CP1 | CP2 | CP3
---|---|---|---
| ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial |  | ADJ
---
DAG
Tree |  | LL
---
DAG
Serial
0 | 281 | 361 | 290 | 587 | 277 | 348 | 286 | 614 | 277 | 355 | 288 | 551
20 | 273 | 371 | 284 | 602 | 278 | 388 | 296 | 563 | 274 | 411 | 276 | 542
40 | 280 | 397 | 290 | 557 | 277 | 403 | 294 | 535 | 277 | 411 | 277 | 554
60 | 271 | 412 | 296 | 550 | 278 | 407 | 294 | 516 | 280 | 404 | 280 | 542
80 | 275 | 437 | 298 | 533 | 273 | 414 | 296 | 512 | 276 | 399 | 283 | 530
100 | 274 | 444 | 293 | 476 | 275 | 423 | 315 | 468 | 278 | 464 | 320 | 533

###  0.C.6 Smart Validation: Mixed Transaction Family

Experiment 1:

No of Blocks | ADJ DAG | Tree | LL DAG |  | Smart
---
validation
10 | 0.80 | 0.27 | 0.37 | 0.10
20 | 1.62 | 0.59 | 0.65 | 0.31
30 | 2.31 | 0.79 | 1.00 | 0.42
40 | 2.37 | 0.86 | 1.50 | 0.65
50 | 2.95 | 1.25 | 1.70 | 0.65

Experiment 2:

Txn per Block | ADJ DAG | Tree | LL DAG |  | Smart
---
validation
200 | 0.32 | 0.16 | 0.16 | 0.10
400 | 0.64 | 0.23 | 0.30 | 0.18
600 | 0.97 | 0.30 | 0.44 | 0.20
800 | 1.27 | 0.39 | 0.59 | 0.31
1000 | 1.60 | 0.50 | 0.76 | 0.29
1200 | 1.94 | 0.51 | 0.76 | 0.45

Experiment 3:

| Dependency
---
Percentage
ADJ DAG | Tree | LL DAG |  | Smart
---
validation
0 | 0.08 | 0.02 | 0.03 | 0.02
20 | 0.07 | 0.02 | 0.03 | 0.02
40 | 0.06 | 0.02 | 0.04 | 0.02
60 | 0.06 | 0.02 | 0.04 | 0.02
80 | 0.06 | 0.02 | 0.04 | 0.02
100 | 0.06 | 0.03 | 0.05 | 0.02