OrderlessChain: A CRDT-based BFT Coordination-free

Blockchain Without Global Order of Transactions

Pezhman Nasirifard Ruben Mayer Hans-Arno Jacobsen
Technical University of Munich University of Bayreuth University of Toronto
Germany Germany Canada
[Link]@[Link] [Link]@[Link] jacobsen@[Link]

ABSTRACT 1 INTRODUCTION
Existing permissioned blockchains often rely on coordination-based The main property contributing to blockchains’ popularity is the
consensus protocols to ensure the safe execution of applications trusted execution of transactions in a trustless, decentralized envi-
in a Byzantine environment. Furthermore, the protocols serialize ronment. To offer trust and prevent Byzantine behavior, blockchains
the transactions by ordering them in a global order. The serializ- use consensus protocols, such as the Proof-of-Work-based (PoW) pro-
ability preserves the correctness of the application’s state stored tocol used in Bitcoin [53]. Another essential property of consensus
on the blockchain. However, coordination-based protocols limit protocols is to enable the system to agree on the total global order of
the throughput and scalability and induce high latency. In contrast, transactions for a serialized execution. The serializability is required
application-level correctness requirements exist that are not depen- to preserve the correctness of the application’s state stored on the
dent on the order of transactions, known as invariant-confluence blockchain. For example, serialization prevents a user’s negative
(I-confluence). The I-confluent applications can execute transactions account balance in the case of Bitcoin, as every node sequentially
in a coordination-free manner, benefiting from the improved scal- executes the transactions in the same order. However, the consen-
ability compared to the coordination-based approaches. The safety sus protocols in several blockchains are severe bottlenecks to their
and liveness of I-confluent applications are studied in non-Byzantine throughput and latency [35, 68].
environments, but the correct execution of such applications remains In contrast to public blockchains, permissioned blockchains are
a challenge in Byzantine coordination-free environments. We intro- only accessible by authenticated and authorized participants [11, 68].
duce OrderlessChain, a novel permissioned blockchain based on a Although the participants’ identity is known, they do not trust each
novel BFT coordination-free protocol for the safe and live execution other. Permissioned blockchains, such as Hyperledger Fabric (Fab-
of I-confluent applications in a Byzantine environment. We imple- ric) [2], take advantage of their permissioned property to implement
mented a prototype of our system, and our evaluation results show more efficient coordination-based consensus protocols. However,
that our coordination-free approach performs significantly better the coordination-based nature of these protocols remains a bottle-
than coordination-based blockchains. neck [14, 15, 71].
Decreasing coordination plays a vital role in improving the scala-
CCS CONCEPTS bility of any distributed system [4]. A coordination-free blockchain
could enable the concurrent execution of transactions, leading to
• Computer systems organization → Distributed architec-
improved throughput and latency. However, simply eliminating
tures.
the coordination may jeopardize the application’s correctness. For
example, a payment processing application may require rejecting
KEYWORDS transactions that result in negative account balances. A coordination-
Permissioned Blockchain, CRDT, I-confluence, Byzantine Fault Tol- free blockchain cannot preserve this [4, 38].
erance, Coordination-free In contrast, there exist application-level correctness requirements
that can be preserved in a coordination-free distributed system,
ACM Reference Format: which are known as Invariant-Confluent (I-confluent) invariant con-
Pezhman Nasirifard, Ruben Mayer, and Hans-Arno Jacobsen. 2023. Or- ditions [4]. For example, transactions that only deposit funds to
derlessChain: A CRDT-based BFT Coordination-free Blockchain Without an account can be executed without coordination. In other words,
Global Order of Transactions. In 24th International Middleware Conference
the I-confluent transactions can be processed in any order while
(Middleware ’23), December 11–15, 2023, Bologna, Italy. ACM, New York, NY,
USA, 14 pages. [Link]
preserving application-level correctness, and the final state of the
application is independent of the order of the transactions. One
technique that can create I-confluent transactions is Conflict-free
Replicated Data Types (CRDTs) [70]. CRDTs are abstract data types
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed that converge to the same state in a coordination-free environment.
for profit or commercial advantage and that copies bear this notice and the full citation Bailis et al. [4] demonstrated that unordered transactions preserve
on the first page. Copyrights for components of this work owned by others than the
author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or
the I-confluent invariants of applications in non-Byzantine and even-
republish, to post on servers or to redistribute to lists, requires prior specific permission tually consistent environments. In other words, applications with I-
and/or a fee. Request permissions from permissions@[Link]. confluent invariants are safe and live in non-Byzantine coordination-
Middleware ’23, December 11–15, 2023, Bologna, Italy
© 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.
free environments. The authors also showed coordination-free ap-
ACM ISBN 979-8-4007-0177-1/23/12. . . $15.00 proaches’ improved scalability, throughput, and latency. However,
[Link]
Middleware ’23, December 11–15, 2023, Bologna, Italy P. Nasirifard, et al.

preserving the safety and liveness of applications in a Byzantine envi- of the withdrawal transactions of Withdraw(50) and Withdraw(60).
ronment depends on paying a high coordination cost in other systems Applying both transactions would result in a negative account bal-
and is challenging without coordination [14, 25, 35, 68, 71, 83]. By ance and violates the application’s invariants. Without coordination,
providing a BFT coordination-free environment where I-confluent the nodes cannot agree to accept one of the two transactions.
applications remain safe and live, we benefit from improved perfor- Bailis et al. [4] studied preserving invariants in a non-Byzantine
mance and scalability while ensuring trust in a trustless environment. coordination-free distributed system and introduced the notion of In-
In this work, we present OrderlessChain, a coordination-free per- variant Confluence (I-confluence). A set of transactions {TS1,...,TSm }
missioned blockchain without a total global order of transactions. is I-confluent with regard to an invariant condition Ij , if the trans-
OrderlessChain uses the properties of permissioned blockchains actions can be applied in different orders on different nodes while
and CRDTs to offer an innovative BFT coordination-free two-phase preserving Ij . Consider the mentioned withdrawal transactions as an
execute-commit protocol for creating safe and live applications. We example of a non-I-confluent transaction set. However, two deposit
also built five applications on OrderlessChain to show its practi- transactions Deposit (50) and Deposit (60) are I-confluent, as apply-
cability. ing these transactions in any order on different nodes does not violate
In summary, we offer the following contributions in this paper: the non-negative balance invariant condition. Hence, the I-confluent
(1) We introduce a novel BFT coordination-free protocol without transactions must have these two properties: (1) Commutativity:
requiring the nodes to coordinate to reach a consensus. We The transactions can be applied in any order. (2) Convergence: The
also offer proof of its BFT property. final state is independent on the order of transactions. Bailis et al.
(2) We present OrderlessChain, a novel permissioned blockchain proved that only I-confluent transactions could be executed on a
based on our BFT protocol, capable of executing safe and live coordination-free distributed system, and non-I-confluent transac-
applications. Our system eliminates the coordination over- tions require coordination among the system’s nodes [4].
head and significantly improves the throughput and scalabil- Conflict-free Replicated Data Types – One available tech-
ity over coordination-based blockchains. nique that provides commutative and convergent transactions as
(3) We present a novel approach for creating Turing-complete I-confluence requires is Conflict-free Replicated Data Types (CRDTs).
blockchain applications based on CRDTs, which preserves the CRDTs represent abstract data types that converge to the same state
I-confluent invariants of applications in a coordination-free in the presence of concurrent transactions in a coordination-free
Byzantine environment and is more scalable than the existing distributed system [70]. These data types encapsulate common data
CRDT-enabled blockchain. structures such as maps and provide APIs for reading and modifying
(4) We implement a prototype of OrderlessChain and demon- their values. Since concurrent transactions can result in conflicting
strate our approach’s improved throughput and latency for values, CRDTs use built-in mechanisms to resolve conflicts without
I-confluent applications compared to coordination-based per- coordination. Shapiro et al. [70] formalized CRDTs and proved their
missioned blockchains. strong eventual consistency property (SEC) in an eventually con-
The remainder of the paper is organized as follows. First, we pro- sistent system. An SEC system has two requirements: (1) Eventual
vide a background on I-confluence and CRDTs in Section 2 followed delivery of transactions: If a transaction is delivered to one correct
by our system model in Section 3. Then, we explain our protocol in node, then all correct nodes will eventually receive the transaction.
Section 4. We discuss the applications of OrderlessChain and its (2) Strong convergence of nodes: If the same set of transactions is
implementation in Sections 5 and 6. We also explain our approach for applied on every correct node, then the nodes’ state immediately
preserving application-level correctness requirements in Section 7, converges to the same state [70].
and the effects of Byzantine participants in Section 8. We present CRDTs synchronize among different nodes through propagat-
evaluations in Section 9 and review related work in Section 10. ing commutative transactions [44]. When extending common data
structures with CRDT features, the transactions may inherently be
2 BACKGROUND commutative or not. For example, a counter is easily modeled as a
Invariant Conditions and Invariant Confluence – Different CRDT since increment transactions are intrinsically commutative.
applications have different correctness requirements. For example, However, modifications for several other data types are not commu-
a banking application may be required to prevent the customers’ tative. For instance, assigning a value to a single-value register is not
account balances from dropping below zero. Developers specify the inherently commutative. For converting a register to a CRDT, the
correctness of an application by defining a set of invariant conditions register needs to be extended with metadata, defining its behavior
{I1,...,Is } on the application’s state. Each Ij represents a requirement in the presence of concurrent modifications. This is achieved with
that nodes must preserve during the application’s lifecycle. Pre- the help of the happened-before relation [70] that defines the causal
serving invariants in a distributed system with globally serialized order between two events based on logical clocks [41]. The theoret-
transactions is relatively straightforward. Provided that each transac- ical foundation for defining the requirements of several CRDTs has
tion preserves the invariants, serialization enables the nodes to apply been studied thoroughly [37, 64].
the transactions in a sequentially isolated manner and preserve the
invariants. However, serialization comes at a high coordination cost.
In a coordination-free distributed system, the nodes may receive the 3 SYSTEM MODEL
transactions in different orders. Hence, preserving invariants is chal- System Model – OrderlessChain is a strongly eventually consis-
lenging. For example, a node that stores the account balance of a cus- tent, asynchronous permissioned blockchain. An OrderlessChain
tomer with an account balance of {Balance : 100} can accept only one network consists of a set of organizations {O1,...,On } and a set of
OrderlessChain: A CRDT-based BFT Coordination-free Blockchain Without Global Order of Transactions Middleware ’23, December 11–15, 2023, Bologna, Italy

clients {C1,...,Cr }. Organizations can communicate with other non- organizations must endorse and commit the voter’s vote. Further-
failed organizations by sending and receiving messages. A unique more, we identify one invariant condition: maximally one vote per
identifier is assigned to each organization and client. The identity of voter. The application is correct if the maximally one vote per voter
each organization is known to every other organization and client invariant is preserved over STApp and committing transactions do
in the network. An organization represents entities that range from not violate this invariant.
large corporations to small businesses or even individuals. The pur- Transaction Model – A transaction is valid as follows:
pose of organizations is to define trust boundaries in the system.
Definition 3.2. Transaction Validity. Let the application’s en-
Although the organizations’ identity is known to each other, the
dorsement policy be EP : {q of n}. Let STApp be correct concerning the
organizations do not necessarily trust each other.
invariant conditions. Let the transaction TSi be I-confluent concerning
Running Example – To better convey our system model and
the invariant conditions. Then, TSi is valid if and only if it satisfies
design, we create a voting application to which we refer throughout
these two requirements: (1) Signature validity: TSi is endorsed by at
the paper. Each voter Voteri can vote for one party among the can-
least q organizations and the client signed the transaction. (2) Invariant
didate parties in {P1,...,Pn }. The network consists of n organizations,
conditions validity: Applying TSi does not violate any invariants.
each representing one distinct party. Each organization receives and
stores votes from voters. We consider the application correct if each We define the transaction TSi to be committed as follows:
voter votes for at most one party. We chose this use case since vot- Definition 3.3. Committed Transaction. Let the application’s
ing applications are among popular blockchain use cases [30]. Also, endorsement policy be EP : {q of n}. Let the transaction TSi be valid.
studies have shown that coordination in such highly concurrent Then, TSi is successfully committed if and only if at least q organizations
use cases is a bottleneck [71]. For example, on Fabric, up to 90% of individually process and commit the transaction successfully.
transactions in a voting application may fail [14].
Application’s World State – Each organization stores a replica For the voting example with EP1 : {2 of 4}, a transaction is valid if
of the application’s state as a set of key-value pairs represented it is signed by the client and is endorsed by at least two organizations.
by STOi , which represents the application state at organization Oi . Additionally, the valid transaction must not violate the maximally
Since OrderlessChain is an SEC system, the replicated applica- one vote per voter invariant. Also, at least two organizations must
tion states STO1 ,...,STOn at organizations O1,...,On may diverge from commit a valid transaction.
each other, but will eventually converge to the same state. At any Failure Model – We consider the organizations and clients po-
given point in time, we define the application’s world state STApp as tentially Byzantine. Byzantine organizations or clients can fail ar-
STApp = ∪ni=1 STOi , that is as the union of the application state at all bitrarily. We consider an organization non-faulty if and only if the
organizations where the values of identical keys are merged based organization processes every transaction according to the Order-
on the techniques discussed in this paper. lessChain’s protocol. The transactions can be delivered in any order
Invariant Conditions – An application’s correctness is imposed differing from the sent order; they may also be duplicated, lost, or
by the developer by defining a set of invariant conditions {I1,...,Is } on corrupted during transmission. The safety and liveness properties
STApp . Each invariant Ij specifies a constraint over STApp . We define of applications running on OrderlessChain are defined as follows:
the application correctness as follows: Definition 3.4. Safety. Only valid transactions are successfully
Definition 3.1. STApp Correctness. Let STApp be the applica- committed.
tion’s world state that does not violate the invariant conditions {I1,...,Is }. Definition 3.5. Liveness. Every valid transaction is eventually
Let the transaction set {TS1,...,TSm } be I-confluent with regard to successfully committed.
{I1,...,Is }. Then, committing the transactions {TS1,...,TSm } does not
We have two kinds of failures: (1) Signature failure: When a trans-
violate any invariant conditions {I1,...,Is } over STApp .
action does not receive the required endorsements based on the
Application’s Endorsement Policy – The developers specify endorsement policy, or the client’s signature is invalid. (2) Organiza-
the endorsement policy for the application. The endorsement policy tion failure: Any Byzantine failures of the organizations, including
specifies which organizations must sign and commit the transac- crash and omission failures and the organizations’ arbitrary behav-
tions. The process of obtaining the signature is called endorsing. The ior, such as intentionally jeopardizing the system through tampering
application’s endorsement policy has the format EP : {q of n}, where with messages, forging signatures, or software bugs.
n is the number of organizations in the system, and q is the min- Intuitively speaking, consider the two possible endorsement poli-
imum number of organizations required for endorsing as well as cies for our voting example. EP1 requires the endorsement and com-
committing a transaction. In other words, the endorsement policy mitting of at least two organizations. Therefore, at most, one of the
determines the trust requirements of the application and enables the four organizations can be Byzantine, so the other non-faulty orga-
developer to adjust the amount of trust required. nizations can prevent committing invalid transactions and keep the
application safe. With more than one Byzantine organization, the
In the context of our voting example, consider an election with client may collude with the Byzantine organizations and collect the
four participating parties P1,P2 ,P3 ,P4 where each party is repre- two required endorsements and commits for the invalid transactions,
sented by a corresponding organization OP1 ,OP2 ,OP3 ,OP4 . Consider and the non-faulty organizations cannot prevent it. However, the
the following two possible endorsement policies: EP1 : {2 of 4} and voting application with EP2 is safe for up to three Byzantine orga-
EP2 : {4 of 4}. EP1 requires that votes are endorsed and committed nizations, as the remaining one non-faulty organization can prevent
by at least two of the four organizations. EP2 indicates that all four the successful commit of invalid transactions. For liveness with EP1 ,
Middleware ’23, December 11–15, 2023, Bologna, Italy P. Nasirifard, et al.

the client must communicate with at least two organizations. As Phase 1 / Execution Phase – The client prepares a transaction pro-
there are four organizations, liveness can tolerate two Byzantine posal TPi containing the client’s identification, the smart contract’s
failures. However, the liveness of EP2 cannot tolerate any Byzantine identifier, the function to be invoked, and the input parameters. The
failures, as any faulty organization can hinder the transaction from client broadcasts the proposal to at least q organizations accord-
being endorsed or committed by all four organizations. ing to the endorsement policy (EP) (Step 1 in Figure 1). Organiza-
Formally speaking, for an application with the endorsement policy tions receive the proposal and execute the smart contract with the
EP : {q of n} and with up to f Byzantine organizations, the applica- provided parameters. The execution result is a set of I-confluent
tion is safe if q ≥ f +1. The application is also live if n−q ≥ f . We operations for modifying the application’s state, created based on
provide proof of the safety and liveness of OrderlessChain in Sec- the CRDT methodology. These I-confluent operations preserve the
tion 8. The safety and liveness condition of OrderlessChain in a application’s invariant conditions, which we explain in detail in the
Byzantine environment differs from the conventional 3f +1 require- following sections. The operations are added to a write-set. Then, the
ment, as we do not require the organizations to coordinate to reach a organization hashes and signs the write-set with its private key and
consensus. Instead, we use the permissioned property of the system creates a signature. Finally, the organization delivers the write-set
and the organizations’ known identity to endorse the transactions, with the created signature as a response (endorsement) to the client
where consequently, the non-faulty organizations prevent endorsing (Step 2 in Figure 1). This signature ensures that the client or other or-
and committing invalid transactions. ganizations cannot tamper with the operations in the endorsement’s
In the case of a network partition, an application with the en- write-set, as tampering makes the signature invalid.
dorsement policy of EP : {q of n} can remain available if the number
of organizations in every partition satisfies the safety and liveness Execution Phase Commit Phase
requirements. Hence, OrderlessChain is available under network Organizationn-1 Organizationn-1
Step 2 Step 4 RCPT2
TP3
partitions according to the CAP theorem [23], if in every partition Smart Contract TP2
REJ3
TS1
there exist at least q organizations, and once the network partition TP1 RCPT1
TP1 TS1 TS3
TS1
is resolved, the state of partitions can be merged based on the tech- DB
Append-
only Log
TP2
TS3 TS2
niques discussed in this paper. TP3
TS2
TS2

Step 1 Step 3

Step 5
4 ARCHITECTURE AND PROTOCOL Step 1
Organizationn
Step 3
Organizationn TS2
TP3
OrderlessChain Architecture – Organizations are responsible TP2
Client TS1 TS3
Smart Contract
for hosting smart contracts, receiving and executing transactions, TP1 TP1 RCPT1 TS3
TS1 TS1
and managing a replica of the application’s ledger. Every applica- Append-
TP2 REJ3
TP3 TS2 TS2
tion running on OrderlessChain makes use of an isolated ledger, DB only Log
Step 2 Step 4 RCPT2

which contains the application state STOi . The application’s ledger

on every organization consists of two components: (1) an append-
Figure 1: Transaction lifecycle on OrderlessChain.
only hash-chain log and (2) a database. The hash-chain log contains
all transactions the organization has received since the beginning
of time in a hash-chain data structure, ensuring the integrity of Phase 2 / Commit Phase – The client waits until it receives the min-
transactions. If a Byzantine organization tampers with one trans- imum number of endorsements required by the EP. If the write-sets
action, the signature on the log and all succeeding transactions in of all endorsements contain identical operations, the client assem-
the hash-chain log will be invalid. By sequentially executing every bles a transaction TSi . The identical operations in the endorsements
transaction in the hash-chain log, we reach the application state show that organizations followed the same protocol for executing
STOi . For a more efficient approach and to avoid executing every the smart contract. Suppose some Byzantine organizations do not
transaction each time STOi is required, an organization applies each execute the smart contract defined by the developer or based on
transaction to its database when appended to the log. Therefore, the the provided input parameters. In that case, the operations will not
database represents the current application state STOi . match those created by non-Byzantine organizations and will cause
The messages are authenticated using digital signatures based on the transaction to fail. The client adds the endorsement’s write-set
a standard Public Key Infrastructure (PKI) [49]. Organizations and to the TSi ’s write-set. The client hashes and signs the transaction’s
clients use PKI to authenticate and sign transactions and verify the write-set with its private key to create a signature to ensure its in-
integrity of the messages. tegrity and includes it in the transaction. The client also includes
Developers create smart contracts, which are programs contain- the received endorsements in the transaction. The client sends back
ing the application’s logic. The system supports executing Turing- the transactions to at least q organizations as specified by the EP
complete logic. Each smart contract can contain several functions (Step 3). These organizations could be different from those who ini-
that encapsulate the logic of the application’s tasks. tially endorsed the proposal. If an organization has yet to commit
Protocol and Transaction Lifecycle – OrderlessChain fol- the transaction, it validates and commits each received transaction
lows a two-phase execute-commit protocol. Clients first submit trans- according to the definitions above. Before committing a transaction,
action proposals to be executed by organizations. If the first phase organizations verify whether the transaction’s endorsements and
succeeds, clients send the transactions to the organizations to be the client’s signature are valid (signature validation) and whether
committed. Figure 1 demonstrates the complete transaction lifecycle endorsements satisfy the EP to offer BFT. For verifying the validity
for an application with endorsement policy EP : {q of n}. of endorsements and the client’s signature, the organization hashes
OrderlessChain: A CRDT-based BFT Coordination-free Blockchain Without Global Order of Transactions Middleware ’23, December 11–15, 2023, Bologna, Italy

the transaction’s write-set and uses the public keys of endorsing or- Table 1: Modification and read APIs of supported CRDTs.
ganizations and the client to verify their signatures. This verification
shows that the endorsing organizations created identical write-sets, CRDT Modification APIs Read API

and the client did not tamper with them. If the transaction passes the G-Counter AddValue (value,clock) Read ()
CRDT Map InsertValue (key,value,clock) Read (key)
signature validation, it is marked as valid and otherwise is invalid. MV-Register AssignValue (value,clock) Read ()
The organizations update their database with the write-set of
valid transactions, whereas all valid and invalid transactions are
appended to the hash-chain log. The invalid transactions are added to its previous bid. The bidder must be able only to increase its last
to the ledger for bookkeeping purposes. Since Byzantine clients can bid. Based on this description, we realize one invariant condition:
create invalid transactions for Distributed Denial-of-Service (DDoS) increase-only bids.
attacks, we discuss countermeasures of such behaviors in Section 8. One possible design is as shown in Figure 2(b): Each auction is
For appending the transaction to the log, the organization creates modeled as a map containing key-value pairs. The key is the bidder’s
a block Blockh :< TSi ,Hash(Blockh−1 ) >, which contains the transac- identification, and the value is a counter. The counter stores the cumu-
tion and the hash of the last block Blockh−1 in the log. Then, the lative bids of the bidders. The counter’s value can only be increased,
organization appends the created block to the log. For valid trans- and the value is increased with every new bid sent by the bidder.
actions, a receipt RCPTi : HashAndSign( Blockh ,Valid), including the
Party1 Map Auction Map
signed hash of the block containing the transaction, is sent to the ........ ........
Keys: Voter1 Votern Keys: Bidder1 Biddern
client (Step 4). If the transaction is invalid, the organization sends
a rejection REJi : HashAndSign(Blockh ,Invalid) to the client. As the Values: Register: ........ Register: Values: Counter:10 ........ Counter:25
Empty True
receipt contains the hash of the block, which is dependent on the
hash of previous blocks in the log, the organization cannot modify (a) Data structure of a participating party. (b) Data structure of an auction.
the content of the transaction without destroying and invalidating
RCPTi of TSi and other transactions. The client awaits receiving the Figure 2: Application modeling for the voting and auction.
minimum number of receipts the EP requires. The client can archive
the transaction’s receipts for bookkeeping purposes. CRDT Abstractions – CRDTs provide a solution for creating
After sending the client’s receipt, the organization periodically commutative convergent operations, and we use CRDTs in smart
gossips the transactions to other organizations to ensure every orga- contracts. OrderlessChain’s protocol is independent of CRDTs
nization receives the client’s transactions (Step 5). Upon receiving used in smart contracts. CRDTs are also replaceable with alternative
a transaction from another organization, the organization checks techniques that provide commutative operations, such as Opera-
the ledger to determine if the transaction has already been received tional Transformation [73]. However, many CRDTs exist for various
from other organizations or clients. If the transaction has already data types whose specifications must be supported by the smart
been processed, the organization ignores it and avoids committing contract execution environment. In the current implementation,
it again; otherwise, it is committed following the above-explained OrderlessChain supports the specifications of grow-only coun-
procedure. If a client sends a transaction that the organization has ters (G-Counter) [70], CRDT Maps [37], and multi-value registers
received from other organizations or a duplicate transaction from (MV-Register) [37]. We chose these three CRDTs as they satisfy
the client itself, it does not commit it again. Instead, a receipt or the requirements of the voting and auction applications. Other use
rejection is sent to the client. cases may require further CRDTs. For enabling the support for other
CRDTs, their design requirements, based on the available literature,
5 ORDERLESSCHAIN APPLICATIONS must be added to the system [64, 70].
By discussing two use cases, we explain the possible use cases of The three CRDTs represent the following data structures: (1)
OrderlessChain and the system’s internal approach for creating G-Counter: It is a monotonically increasing numeric variable. (2)
CRDT-based I-confluent applications. CRDT Map: This CRDT is built upon a map data structure containing
Application Modeling – To implement a use case in a smart key-value pairs. The key is an identifier, and the value can be any
contract, we need to model the application as data structures that object. (3) MV-Register: This is a shared variable capable of contain-
match the use case’s description and contain the application’s data. ing multiple values simultaneously. Every CRDT provides read APIs
We discuss modeling two use cases: and modification APIs for incrementing the G-Counter, inserting
Voting Application – One possible solution for modeling our run- a key-value pair to the CRDT Map, and assigning a value to the
ning voting example in a smart contract is shown in Figure 2(a): For MV-Register as shown in Table 1. Using the read APIs in the smart
every party participating in the election, we require a map contain- contracts causes no side effects and requires no CRDT operation.
ing key-value pairs. The key is the voter’s identification, and the The developers create operations in the smart contract containing
value is a register that stores a Boolean value for the vote sent by the the modification API calls. The value must be null for deleting a
voter for this party. value. The modification APIs contain a logical clock used to infer the
Auction Application – Auction applications are among the com- happened-before relations. For creating more complex data struc-
mon use cases of blockchains [22]. An auction is a highly concurrent tures, maps can be nested, where the value of the key-value pairs
use case that can benefit from a coordination-free approach. Con- can be either a new CRDT Map, G-Counter, or MV-Register.
sider an auction and a set of bidders {Bidder1, ...,Biddern }. The bidder These CRDTs are used for voting and auction applications as fol-
Bidderi submits bids. Each bid contains the amount it wishes to add lows. Voting application: As previously shown in Figure 2(a), each
Middleware ’23, December 11–15, 2023, Bologna, Italy P. Nasirifard, et al.

party is modeled as a map, and the voter’s votes are modeled as Smart Contracts – Developers use our Smart Contract Library
key-value pairs in the party’s map where the values are registers. (SCL) for developing smart contracts and defining the logic of ap-
Therefore, we use a CRDT Map to model the party’s map and the plications. The smart contract includes functions that encapsulate
MV-Register as the votes’ register. Auction application: As shown in different functionalities of the application. To enable developers
Figure 2(b), we use a map for modeling the auction and increase-only to interact with data stored on the ledger, SCL offers interfaces for
counters for bids. Hence, we use a CRDT Map to model the auction’s defining operations called CRDT APIs. Each client keeps track of a
map and G-Counters to model the bids. Lamport clock [41], passed into the smart contract with proposals.
To evaluate an operation’s effects, the operation must be ap- The client increments the clock with every submitted proposal. Each
plied to the CRDT, which may cause conflicts. The CRDTs must client’s Lamport clock is independent of the clock of other clients.
provide a built-in mechanism for resolving conflicts. We identify Furthermore, each CRDT object has a unique identification on the
the conflicting operations of the three CRDTs and offer a conflict ledger. The read API does not require creating any operation, and
resolution accordingly. (1) G-Counter: As the operations increase SCL only requires the identification of the CRDT object to retrieve
the counter’s value, the modification operations are inherently com- it. For modifications, in addition to the identification of the CRDT
mutative and cause no conflict. (2) CRDT Map: The modification object, each operation includes four components: (1) Operation iden-
operations that modify different keys in the map are commutative tifier: The identification of the operation is unique per CRDT object
and non-conflicting and can be applied concurrently. However, the and is a combination of the client’s identification and the client’s
operations that modify identical keys are conflicting. The conflict is Lamport clock. (2) Modification value and type: The value that the op-
resolved based on the happened-before relations among operations. eration modifies and the type of CRDT. (3) Client’s clock: The client’s
If the happened-before relation can be inferred, the operations are ap- Lamport clock. (4) Operation path: Developers can create nested
plied based on the relation; however, if the happened-before relation CRDT structures for creating more complex data structures. The
cannot be inferred, a new map is created, and the conflicting values path specifies the location of the modification, starting from the root
are added to the new map as new key-value pairs, as shown in Fig- of the CRDT object. For example, in the voting application with four
ure 3. (3) MV-Register: On MV-Register, every modification operation parties, the function in the smart contract creates four operations
is conflicting, and the value of the register is determined based on for voting for party P1 . One operation sets the voter’s MV-Register
the happened-before relation among clocks. If the happened-before on party P1 to true, and the other three operations set the voter’s
relation cannot be inferred from the clocks, the register stores all MV-Register on the other three parties to false. These four operations
values, as shown in Figure 4. are included in the write-set of proposals for vote submission.
Party1 Map Party1 Map Party1 Map Party1 Map
Applying Transactions – Developers can implement functions
Voter1 in smart contracts for invoking read APIs and retrieving the values
Voter1
Clock3 Clock4
of CRDT objects. Subsequently, clients can submit proposals to an
Empty Empty
VoteRegister2: VoteRegister3: VoteRegister4:
organization Oi for reading the values. In our voting example, the
Empty Empty Empty developer can implement a function to read the number of votes
Clock1 happened-before Clock2 No happened-before relation between Clock3 and Clock4
submitted to a party. As OrderlessChain is an SEC system, the
Operation1: InsertValue(Voter1, VoteRegister1, Clock1) Operation3: InsertValue(Voter1, VoteRegister3, Clock3) application state STOi may diverge from the application states on
Operation2: InsertValue(Voter1, VoteRegister2, Clock2) Operation4: InsertValue(Voter1, VoteRegister4, Clock4) other organizations. Therefore, reading the values at Oi only reflects
the modifications applied at Oi .
Figure 3: Applying CRDT Map modification operations. To compute the CRDT object’s value in response to read API
calls, the organization should retrieve and apply every operation
in the ledger submitted for the CRDT object. As the number of op-
Party1 Map Party1 Map Party1 Map Party1 Map erations increases, the time required for applying operations also
Voter1 Voter1 Voter1 Voter1 increases. This increasing overhead is a well-known problem of
VoteRegister1:
CRDTs [8, 39]. Hence, we implemented an optimization to address
VoteRegister1: VoteRegister1: VoteRegister1:
Empty False Empty [True, False] this issue. Section 4 explains that the ledger contains a database
Clock1 happened-before Clock2 No happened-before relation between Clock3 and Clock4 besides the hash-chain log. The database is updated with every valid
Operation1: AssignValue(True, Clock1) Operation3: AssignValue(True, Clock3)
transaction. It consists of a conventional key-value database, namely
Operation2: AssignValue(False, Clock2) Operation4: AssignValue(False, Clock4)
LevelDB [24], and an in-memory cache. Upon the transaction com-
mit, the operations are inserted into LevelDB. We do so as retrieving
the operations from LevelDB is more efficient than retrieving them
Figure 4: Applying MV-Register modification operations.
from the log during a cache miss. The value of the CRDT object in
the cache is updated with the transaction’s operations according to
Algorithm 1. In response to read API calls, the organizations return
6 IMPLEMENTATION the value of the CRDT object from the cache. This approach offers
We implemented a prototype of OrderlessChain with the Go lan- read-your-writes consistency from the client’s point of view [60].
guage [3] and gRPC [20]. We open-sourced the code and the smart Algorithm 1 demonstrates our approach for applying each opera-
contracts discussed in this paper 1 . tion to the CRDT object. For every operation, before applying it, the
CRDT object is traversed from its root until it reaches the location
1 [Link] defined by the operation’s path (Line 3). As the object can be a nested
OrderlessChain: A CRDT-based BFT Coordination-free Blockchain Without Global Order of Transactions Middleware ’23, December 11–15, 2023, Bologna, Italy

structure, parts of the path might not have been added to the object Voter1 submitted two votes for two different parties, where there
yet. Therefore, the missing parts are created and added. Additionally, exists a happened-before relation between operations in TSVote1 Voter1
the location contains the clocks of the previously applied operations. Voter1
and TSVote2 . Therefore, independent of the order they are processed,
Once the location for modification is reached (Line 4), the changes based on the CRDT’s conflict resolution mechanism, operations in
are applied (Line 5). For applying the changes, as we explained in Voter1 overwrite the effects of operations in TS Voter1 . Hence, we
TSVote2 Vote1
the CRDT abstractions, the built-in conflict resolution is applied count only one of the votes submitted by the Voter1 . The maximally
depending on the type of object and the clocks of previously applied one vote per voter invariant is preserved, and the transactions are
operations. Additionally, the operation’s clock is appended to the I-confluent concerning the invariant.
location’s clocks. The time and space complexity of Algorithm 1 is We can similarly reason that the auction application is I-confluent
O(n), where 𝑛 is the number of operations being applied. concerning the increase-only bids invariant.
Party1 Map

Voter1
Algorithm 1: Applying operations to the CRDT. TSVoter1Vote1 (Vote of Voter1 for Party1)
1 ApplyOperations (CRDTObj,Operations) Operation1: {[Party1/Voter1], MV-Register, True, Voter1Clock1}
input : CRDTObj , a reference to the CRDT object. VoteRegister1:
Operation2: {[Party2/Voter1], MV-Register, False, Voter1Clock1} False
input : Operations, the modification operations.
2 foreach Opi in Operations do TSVoter1Vote2 (Vote of Voter1 for Party2) Party2 Map
3 [Link] (Opi .OpPath)
4 Location = [Link] (Opi .OpPath) Operation3: {[Party1/Voter1], MV-Register, False, Voter1Clock2} Voter1

5 [Link] (Location,Opi .Val,Opi .ValType,Opi .Clock) Operation4: {[Party2/Voter1], MV-Register, True, Voter1Clock2}
VoteRegister1:
True

Voter1Clock1 and Voter1Clock2 from Voter1. Hence, Voter1Clock1 happened-before Voter1Clock2

In Section 8, we prove the SEC property. However, first, we demon-
strate that the application state STOi is independent of the order of
transactions. We formulate the following lemma: Figure 5: Preserving the invariant for the voting application.

Lemma 6.1. Independent of the processing order of transactions in

the transaction set {TS1,...,TSm } in organization Oi , application state 8 BYZANTINE ACTORS
STOi converges to the same state for all i. Organizations or clients are potentially Byzantine. We identify four
types of Byzantine faults by clients: (1) A Byzantine client may send
Proof. The write-set of every transaction in {TS1,...,TSm } only proposals to the organizations without sending the transaction to
contains CRDT modification operations. As CRDTs are provided be committed. This does not leave any lasting side effects. However,
with a built-in conflict resolution mechanism, applying the opera- it can be used for Distributed Denial-of-Service (DDoS) attacks. As
tions in the write-set of operations using Algorithm 1 ensures that only authenticated clients can communicate with the organizations,
transactions can be processed in any order while converging to the OrderlessChain can employ existing DDoS attack detection mech-
same state. Hence, the convergence of STOi is independent of the anisms [16] to revoke Byzantine clients’ permissions. (2) A Byzantine
order of transactions. □ client may only send transactions to a subset of organizations during
the commit phase. As the organizations gossip the transactions to
7 PRESERVING INVARIANT CONDITIONS other organizations after committing the transaction, all organiza-
As explained in Section 2, organizations can commit a set of I- tions eventually receive the transactions. (3) Byzantine clients may
confluent transactions in a coordination-free manner without addi- send different logical timestamps to different organizations for a pro-
tional validations while preserving the invariants. Since the CRDT posal. In this case, the operations in the endorsements do not match,
operations in the write-set of transactions modify the application’s which prevents the creation of a valid transaction. (4) If the client
state, the operations must be I-confluent. Developers who define the does not increment the clock with every proposal, the organizations
logic for creating operations in a smart contract must implement the cannot infer happened-before relations between operations during
identified invariants as I-confluent operations. commit. As explained in Section 5, the proposed CRDT approach
In the case of our voting application, we realized the maximally can resolve the conflict of such operations without affecting other
one vote per voter invariant. To determine that the invariant can be clients’ operations. Therefore, Byzantine clients cannot jeopardize
preserved by creating I-confluent operations, we reason as follows: the system.
Consider an election with two participating parties. As explained in To discuss the safety and liveness concerning Byzantine organi-
Section 6, every transaction TSVote that submits a vote has two oper- zations, we introduce the following theorem:
ations in the write-set. One operation sets the voter’s MV-Register in
Theorem 8.1. Let the endorsement policy for an application be
the elected party’s map to true. The other operation sets the voter’s
EP : {q of n} with n ≥ q > 0. Then, for up to f Byzantine organizations,
MV-Register for the non-elected parties to false.
the application is safe if and only if q ≥ f +1. Furthermore, the appli-
As there is no coordination among organizations, the voter can
cation is live if and only if n−q ≥ f .
submit several votes. However, the maximally one vote per voter
invariant requires that we only count one of the votes. Consider the Proof. According to our definition of safety and liveness, the
Voter1 ,TS Voter1 }, submitted by Voter ,
following transaction set {TSVote1 safe and live OrderlessChain must prevent committing invalid
Vote2 1
as shown in Figure 5. Each transaction contains two operations. transactions and eventually commit valid transactions. We identify
Middleware ’23, December 11–15, 2023, Bologna, Italy P. Nasirifard, et al.

two types of Byzantine faults by organizations. Byzantine organi- In Lemma 6.1, we proved that independent of the order of transac-
zations may attempt to jeopardize the system by either responding tions in the transaction set {TS1,...,TSm }, the application state STOi
with wrong messages or avoiding responding altogether. Wrong at organization Oi converges to the same state for all i. Since the even-
messages include forged signatures from organizations and clients, tual delivery of transactions requirement for the safe and live applica-
transactions with tampered or corrupted write-set operations, in- tion is satisfied, when the transaction set {TS1,...,TSm } is delivered
correctly executed smart contracts, or duplicated or lost messages. to the non-faulty organization Oi , the same set is delivered to every
As the integrity of messages sent by organizations and clients can other non-faulty organization. Therefore, according to Lemma 6.1,
be examined, the signatures cannot be forged, and the organizations all STOi converges to the same state, and the requirement strong
can independently prove the validity of organizations’ and clients’ convergence of nodes is satisfied. Hence, the application’s world state
signatures. As the system commits every transaction only once, and STApp of a safe and live application on OrderlessChain is SEC. □
multiple executions of proposals do not leave any lasting side effects,
duplication of messages has no effect. If the messages are suspected
to be lost, they can be resent. Additionally, if a client’s transaction
fails due to the Byzantine organizations’ wrong messages, the client 9 EVALUATION
can resubmit the proposals to another set of organizations and resend We first evaluate OrderlessChain. Then, we compare it to Fab-
the transaction. On OrderlessChain, the developers identify and ric [2], FabricCRDT [54], BIDL [66] and Sync HotStuff [1]. Fabric is
define the application logic for creating I-confluent update opera- a permissioned blockchain capable of executing Turing-complete
tions. Therefore, the invariants are preserved as long as the write-set applications. FabricCRDT (built as an extension on top of Fabric)
operations are not tampered with and the smart contract is executed runs CRDT-enabled applications. BIDL is a permissioned blockchain
as defined by the developer. Since the write-set of every endorse- optimized for data center networks inspired by Fabric. Sync Hot-
ment must include identical operations, as long as there exists at least Stuff introduces a synchronous BFT consensus protocol based on
one non-faulty organization among the q endorsing organizations, the HotStuff protocol [80]. Fabric, FabricCRDT, and BIDL’s network
which creates the write-set operations that can be differentiated from comprise organizations. We adjusted Sync HotStuff to employ the
the tampered operations or the incorrectly executed smart contract, concept of organizations. On Fabric and FabricCRDT, the clients
creating a valid transaction is impossible, and the application is safe. send the transactions to an ordering service for consensus and to
Hence, the application is safe if and only if q ≥ f +1. create a global order by batching transactions into blocks. Before the
Byzantine organizations may not respond to clients. For the appli- transaction commits, Fabric’s organizations perform a multi-version
cation to be live, the client must endorse and commit the transaction concurrency control validation (MVCC validation) to ensure that the
on q among n organizations. Therefore, the transaction can reach at application’s invariants are preserved. FabricCRDT does not per-
least q organizations if and only if n−q ≥ f . Therefore, the application form an MVCC validation and only merges the transaction values
is live if and only if n−q ≥ f . □ using JSON CRDT techniques [37]. BIDL uses a central sequencer for
sequencing transactions. Afterward, it executes the transactions and
We demonstrated that liveness and safety depend on the appli- performs coordination-based consensus in parallel. Sync HotStuff
cation’s endorsement policy. In other words, the safety and liveness uses coordination- and leader-based consensus for ordering and
can be tailored to the application’s requirements. For example, for executing transactions.
the voting application with four parties, the regulation of a fair elec- We compare OrderlessChain to Fabric, FabricCRDT, BIDL, and
tion may dictate that all parties endorse every vote. Therefore, we Sync HotStuff prototypes. We implemented the prototypes by study-
need EP : {4 of 4}. If the regulations demand the endorsement of at ing the available source code and following their concepts using
most two parties, we can have an EP : {2 of 4}. Furthermore, since Go, gRPC, and LevelDB. We implemented these prototypes because
the Byzantine behavior of organizations can be observed, and the the original Fabric, FabricCRDT, and BIDL offer many security and
identity of organizations is known to each other, the organizations network-related features we do not implement in OrderlessChain.
have the incentive to behave honestly, as otherwise, they may face These features impose performance penalties and would have caused
the consequences. For example, a Byzantine party jeopardizing the an increased transaction latency. For example, in the case of Fabric,
election may face legal consequences. Gorenflo et al. [25] and Chacko et al. [14] offer extensive insights
The following theorem demonstrates that STApp is SEC. on the performance penalties. We replicated the original implemen-
Theorem 8.2. Let the application be safe and live. Then, the appli- tations for a fair comparison since we intended to compare our
cation’s world state STApp is SEC. coordination-free protocol to their coordination-based protocols
independently of the implementation of the rest of the system. Fur-
Proof. According to the definition of SEC in Section 2, an SEC sys- thermore, the CRDT approach in FabricCRDT does not use the cache
tem must satisfy two requirements of eventual delivery of transactions we implemented as an optimization. For fairness, we also imple-
and strong convergence of nodes. In Theorem 8.1, we demonstrated mented such a cache in FabricCRDT’s CRDT approach.
that every valid transaction is committed for a safe and live applica- Experimental Applications – We developed a synthetic ap-
tion. Additionally, non-faulty organizations gossip the transaction plication for evaluating OrderlessChain. Based on the examples
to other non-faulty organizations. Therefore, provided that the ap- discussed, we also implemented voting and auction applications
plication is safe and live, every non-faulty organization eventually for comparing OrderlessChain to the other four systems. Every
receives a valid transaction. Hence, eventual delivery of transactions application consists of one smart contract, and in total, we developed
is satisfied. eleven smart contracts (available in the Git repository mentioned in
OrderlessChain: A CRDT-based BFT Coordination-free Blockchain Without Global Order of Transactions Middleware ’23, December 11–15, 2023, Bologna, Italy

Section 6). Each smart contract has one modify-function for modify- Each experiment is executed at least three times, and the results
ing the data on the ledger and one read-function for retrieving data are averaged. At the end of each experiment, the performance metrics
from the ledger. are collected. We measure the transaction throughput, the average
Synthetic Application – For a controlled evaluation of Order- transaction latency, the 1st percentile transaction latency, and the 99th
lessChain, we implemented a synthetic application. The appli- percentile transaction latency. The transaction throughput is the total
cation’s smart contract includes two functions Modify(ClientIdi , number of successfully committed transactions divided by the total
Clocki ,ObjCount,OpsPerObjCount,CRDTType) and Read (ObjCount). time taken to commit these transactions. The transaction latency is
The Modify function receives the client identification and clock, the the response time per transaction from sending the proposal until
number of CRDT objects and operations per each CRDT object modi- receiving the commit receipts from organizations, according to the
fication, and the CRDT type. The write-set of the transaction includes endorsement policy.
ObjCount ×OpsPerObjCount operations. The Read function reads a Experimental Setup – Each organization of the five studied
specific number of CRDT objects as specified by ObjCount. systems runs on an individual KVM-based Ubuntu 20.04 virtual ma-
Voting Application – We developed voting applications for all five chine (VM), and different organizations do not share VM resources.
evaluated systems. The application’s smart contract for Orderless- Each VM uses 9.8 GB of RAM and four vCPUs. Since the VMs are
Chain has two functions: Vote(Voteri , Clocki ,Partyj ,Electionl ) and located within a single cluster and are connected via LAN, we used
ReadVoteCount (Partyj ,Electionl ). For an election with n parties, the Ubuntu’s NetEm (network emulation) and tc (traffic control) facilities
Vote function results in n total operations (one operation per object) for adding 100 ms ping delay, 4 ms jitter, and 100 Mb rate control to all
in the write-set as explained in Section 6. ReadVoteCount retrieves links for emulating a WAN. We chose these values by observing the
the current number of votes of Partyj . The smart contracts of the delays and bandwidth between two Ubuntu servers in two cities in
other four systems also include Vote and ReadVoteCount functions, Europe and North America, provided by two cloud providers. Based
which are implemented based on the best practices for developing on studies that also use emulated WANs [14] and our observations,
smart contracts on these systems [14, 54, 66]. this setting fairly accurately emulates a realistic WAN. The ordering
Auction Application – The auction application’s smart contract service of Fabric, FabricCRDT, and BIDL, the sequencer of BIDL, and
of OrderlessChain has two functions: Bid (Bidderi ,Clocki , the leader of Sync HotStuff runs on separate VMs. We also developed
BidIncreasei ,Auctionj ) and GetHighestBid (Auctionj ). The Bid func- a benchmarking tool that orchestrates a distributed deployment
tion includes one operation in its write-set for increasing the bid- of clients, generates and submits transactions, and collects perfor-
der’s G-Counter. GetHighestBid reads the current highest bid. The mance metrics. The benchmarking tool is inspired by Hyperledger
smart contracts of the other four systems also include a Bid and a Caliper [65], and its code is published with the system’s code.
GetHighestBid function.
Workloads, Control Variables and Metrics – Each experiment
Table 2: Control variables of synthetic application.
is executed on an initially empty ledger. We submit a workload con-
taining transactions invoking the modify- and read-functions in the Control Variable Default Executed Configuration
smart contracts, also referred to as modify- and read-transactions. The (1) TS Arrival Rate 3000 tps {1000 tps, ..., 10,000 tps}
workload includes a specific percentage of modify-transactions and (2) Number of Orgs 16 Orgs {8 Orgs, ..., 32 Orgs}
(3) Endorsement Policy {4 of 16 } { {2 of 16 }, ..., {16 of 16 }}
read-transactions, uniformly distributed during the execution of the (4) Number of Obj 1 Obj {2 Objs, ..., 16 Objs}
experiment. Each organization receives a specific percentage of the (5) Operations per Obj 1 Op {2 Ops, ..., 16 Ops}
(6) CRDT Type G-Counter {G-Counter, MV-Register, Map}
load on the system. We define the transaction arrival rate in transac- (7) Workload (Read/Mdfy) R50M50 {R10M90, ..., R90M10}
(8) Workload per Org Uniform {Uniform, Normal Distribution}
tions per second (tps) of the system as the total number of transactions (9) Gossip Ratio 1 Org {1 Org, ..., 15 Orgs}
per second submitted by all clients to the system. The other control (10) Byzantine Orgs 0 Failure {1 , 2 , 3 } Failures
(11) Byzantine Clients 0% Failure {50%, 75%, 100% } Failures
variables are the number of organizations, endorsement policies, the (12) Byzantine Orgs/Clients 0/0% Failure {3/50%, 3/75%, 3/100% } Failures
Byzantine failures, and the number of organizations to which each
organization gossips the transaction, which we refer to as the Gossip
Ratio. The gossips are propagated at one-second intervals. For the Experimental Results for Synthetic Application on Order-
endorsement policies of EP : {q of n}, the clients send the proposals lessChain – Table 2 displays the control variables, their default val-
and transactions to exactly q organizations. Each organization has ues, and the executed experimental configurations for the synthetic
one node on Fabric, FabricCRDT, BIDL, and Sync HotStuff. Each application on OrderlessChain. One of the control variables is set to
experiment is executed for 180 seconds. Fabric, FabricCRDT, and the executed configurations, and the other control variables are set to
BIDL use the Solo ordering service [2]. the default value. As shown in Figure 6(a), the throughput increases
For the synthetic application, we used 1000 clients. ObjCount, with an increasing transaction arrival rate, but the latency rises.
OpsPerObjCount, and CRDTType are control variables. We defined We studied the effect of increasing the number of organizations on
1000 voters, eight elections, and eight parties per election for the throughput and latency, as shown in Figure 6(b). We set the endorse-
voting application. We defined 1000 bidders, eight auctions, and a ment policy for each experiment to EP : {4 of NumberOfOrgs}. We
gradually growing number of bids for the auction application. We observe that the system scales for increasing organizations without
chose these values according to the scalability evaluation of Fab- affecting the throughput and latency. As shown in Figure 7, we also
ric done by other authors [14]. The input parameters for modify- compared the average latency to throughput for an increasing num-
and read-transactions are randomly selected from these predefined ber of organizations and arrival rates and observed that Orderless-
values based on a uniform distribution during the experiment. Chain scales. With an increasing number of organizations required
Middleware ’23, December 11–15, 2023, Bologna, Italy P. Nasirifard, et al.

·104

Throughput (tps)
1 3,000
Latency (ms)

1,000
600
400 2,000
500 0.5
200 1,000
0 0 0 0
s s s s s s s s s s s s s s s s s s s s s gs gs gs s gs gs s
tp tp tp tp tp tp tp tp tp tp tp tp tp tp tp tp tp tp tp tp rg Or Or Or rg Or Or rg
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 8O 16 24 32 8O 16 24 2O
10 20 30 40 50 60 70 80 90 100 10 20 30 40 50 60 70 80 90 100 3
(a) Transaction Arrival Rate (b) Number of Organizations
·104

Throughput (tps)
3,000 1.5 3,000
Latency (ms)

2,000
2,000 1 2,000
1,000 1,000 0.5 1,000
0 0 0 0
f16 f16 f16 f16 f16 f16 f16 f16 f16 f16 f16 f16 f16 f16 f16 f16 bjs bjs bjs bjs bjs bjs bjs bjs Objs Objs Objs Objs Objs Objs Objs Objs
2o 4o 6o 8o 10o 12o 14o 16o 2o 4o 6o 8o 10o 12o 14o 16o 2O 4O 6O 8O10O12O14O16O 2 4 6 8 10 12 14 16
(c) Endorsement Policy (d) Number of Objects

Modify Transactions Read Transactions Modify and Read Combined

Figure 6: Throughput, average, 1st, and 99th percentiles transaction latencies for executed configurations of synthetic application.

by the endorsement policy, we ob- a specific period while all clients are non-faulty. The Byzantine orga-
600 serve that the latency increases nizations either randomly avoid responding to clients or endorse the
Latency (ms)

as the load on the organization proposals incorrectly. The Byzantine organizations also randomly
400
16 Orgs increases, as shown in Figure 6(c). avoid forwarding the transactions to other organizations. We in-
200 24 Orgs We observe in Figure 6(d) that cluded three Byzantine organizations as, based on the EP : {4 of 16},
32 Orgs the latency increases for a larger the safety and liveness of the application can tolerate up to three
0 number of objects in the trans- Byzantine failures, and this is the worst-case scenario for organiza-
0 0.5 1
Throughput (tps) ·104 action due to the locking mecha- tions. We observed that the throughput decreases with every Byzan-
nism used in the cache to avoid tine failure. However, the latency is not affected (not shown in the
concurrent reads and writes. The figures). The decreasing throughput is due to clients being unable to
Figure 7: Average latency results of experiments with con- collect the minimally required valid endorsements. Since clients can
to throughput. figurations 5 to 9 are explained in observe organizations that wrongly endorse or do not respond while
the following and are not shown others respond with lower latency, they can avoid Byzantine orga-
in the figures due to space limitations. We observe that throughput nizations. To demonstrate this, we ran experiments where clients
and latency are unaffected by the increasing number of operations randomly selected another organization. As shown in Figure 8(b), the
and are independent of CRDT types. We gradually decreased the throughput returns to its pre-failure value immediately after clients
modify-transactions in the workload from 90 percent to 10 percent, avoid the Byzantine organizations, as shown by the solid green lines.
and we observed that the latency and throughput were unaffected. We also ran experiments where all organizations were non-faulty
We also changed the distributed workload per organization from a with an increasing percentage of Byzantine clients, randomly either
uniform to a normal distribution, where some organizations received not sending the transactions for commit after the execution phase
a higher percentage of the workload. We did not observe a significant or tampering with the transaction’s write-set. We observed that all
difference except for the slight increase in latency for the higher- faulty transactions are rejected while the latency is unaffected, show-
loaded organizations. We did not observe a significant change in ing the system stays safe and live (results are not plotted). Finally,
latency and throughput for an increasing gossip ratio either. we executed experiments with three Byzantine organizations with
an increasing percentage of Byzantine clients. Similar to previous
30 s 70 s 110 s 150 s 30 s 70 s 110 s 150 s
Byzantine experiments, we observed the decreased throughput with-
Throughput (tps)

Throughput (tps)

3,000 3,000
out affecting latency, and the system remained safe and live with no
extra cost due to Byzantine failures.
2,000 2,000
Vote and Auction Applications – We compared Orderless-
1,000 1,000
f :1 f :2 f :3 f :0 f :1 f :2 f :3 f :0 Chain with Fabric and FabricCRDT with 8 organizations for each
0 0
0 50 100 150 0 50 100 150 system and the EP : {4 of 8}. Then, we compared it with BIDL and
(a) Experiment Time (s) (b) Experiment Time (s) Sync HotStuff with 16 organizations for each of the three systems
and the EP : {4 of 16}. We did so as the configuration with 16 organi-
Figure 8: Experiments with Byzantine organizations. zations for Fabric and FabricCRDT caused the failure of a significant
portion of transactions due to their coordination-based approach
We studied the effects of Byzantine failures. First, as shown in Fig- limitations, which prevented us from providing meaningful insights.
ure 8(a), three randomly selected organizations behave arbitrarily for Also, for FabricCRDT and Sync HotStuff, we observed that latency
OrderlessChain: A CRDT-based BFT Coordination-free Blockchain Without Global Order of Transactions Middleware ’23, December 11–15, 2023, Bologna, Italy

(c) Voting Application Latency for an Increasing Transaction Arrival Rate (tps) (a) Voting Application Throughput
·105 ·105

Throughput (tps)
600 1
Latency (ms)

572 / 601
1 1,000

522 / 520

532 / 529

550 / 547

145 / 144
400

92 / 144

56 / 56
0.5 0.5 500
200
0 0 0 0
ps tp
s
tp
s
tp
s
tp
s
tp
s
tp
s
tp
s
tp
s
tp
s ps tps tps tps tps ps tps tps tps tps 0t 00 00 00 00
0 0 0 0 0 0t 0 0 0 0 0t 0 0 0 0 50 10 15 20 25
50 100 150 200 250 50 100 150 200 250 50 100 150 200 250

(d) Auction Application Latency for an Increasing Transaction Arrival Rate (tps) (b) Auction Application Throughput
·105 ·105

Throughput (tps)
600 1 4
Latency (ms)

1,000
538 / 538

529 / 528

540 / 540

697 / 702
400 3
0.5 2 500
200 1
0 0 0 0
ps tp
s
tp
s
tp
s
tp
s
ps ps ps ps ps ps ps ps ps ps ps tps tps tps tps 0t 00 00 00 00
0 0t 00t 00t 00t 00t 0 0t 00t 00t 00t 00t 0t 0 0 0 0 50 10 15 20 25
5 10 15 20 25 5 10 15 20 25 50 100 150 200 250

OrderlessChain Fabric FabricCRDT

OrderlessChain Modify Fabric Modify FabricCRDT Modify OrderlessChain Read Fabric Read FabricCRDT Read

Figure 9: Experiments with voting and auction applications on OrderlessChain, Fabric, and FabricCRDT.

significantly increases for a higher transaction arrival rate due to We observe that for identical configurations, the organizations of
FabricCRDT’s CRDT implementation and Sync HotStuff’s leader- all five systems utilize the same amount of memory on average. For ex-
based approach, so we limited the transaction latency for them to ample, each organization of OrderlessChain and Fabric consumes
240 seconds, after which they are timed out and not considered for on average 400 Mb of Heap for the 2500 tps of the voting application.
throughput and latency evaluation. However, the CPU utilization of OrderlessChain is higher than the
As shown in Figures 9(a) and (b), we observe that Orderless- utilization of other systems. For example, the Fabric organization’s
Chain demonstrates a higher throughput for both applications. On CPU utilization for the 2500 tps of the voting application is, on aver-
Fabric, the failed transactions due to the MVCC validation, explain its age, at 30%, whereas the OrderlessChain organization is at 50%.
low throughput. Although we used caching for the CRDT approach This higher utilization is attributed to applying the CRDT operations
in FabricCRDT, the CRDT approach still is a bottleneck. As shown to the cache. However, as applying the modifications to the cache
in Figures 9(c) and (d) (for the lower values, the average latencies is done sequentially due to the employed locking mechanism, the
are written on the plots), OrderlessChain’s latency remains con- higher CPU utilization for cache operations is bounded. The main
stant under increasing arrival rates. Fabric’s latency significantly limitation of OrderlessChain is the cache’s locking mechanism to
increases for higher arrival rates. The reason is that Fabric’s central avoid concurrent reads and writes due to Go language constraints,
ordering service for consensus is a bottleneck, as shown in Table 3 which can be addressed using other technologies that offer lock-free
for the 2500 tps of the voting application (the results do not include data structures.
the added WAN network latency on the client side). The increased
latency causes more transactions to fail due to MVCC validation. Table 3: Breakdown average transaction processing time.
FabricCRDT demonstrates irregular latency patterns as timed-out
transactions are not considered. As demonstrated in Figures 10(a) OrderlessChain (ms) Fabric (ms) BIDL (ms) Sync HotStuff (ms)
and (b), we observe that although both BIDL and Sync HotStuff scale P1/Execution: 64 P1/Endorse: 59 P1/Sequence: 346 P1/Consensus: 5532
P2/Commit: 110 P2/Consensus: 17270 P2/Consensus: 6803 P2/Commit: 6
better than Fabric and FabricCRDT, OrderlessChain demonstrates P3/Commit: 11 P3/Execution: 54
P4/Commit: 1
a higher throughput for both applications. Furthermore, Order-
lessChain’s latency stays constant as the latency of BIDL and Sync
HotStuff significantly increases for higher arrival rates. As the design Discussion – We do not require coordination for preserving
of BIDL is highly optimized for data center networks with high band- I-confluent invariants. However, coordination is required for ap-
width and low network latency, their proposed coordination-based plications with non-I-confluent invariants. Suppose we require an
approach for consensus and BIDL’s central sequencer, becomes a invariant to specify a deadline for the end of an election, after which
bottleneck in a WAN setup with limited bandwidth and higher net- the votes are rejected. This is a non-I-confluent invariant and re-
work latency, as shown in Table 3 for the 4000 tps of the voting quires coordination. One approach for enabling OrderlessChain
application. These results corroborate the findings in the BIDL paper. to preserve such invariants is extending it with coordination-based
For Sync HotStuff, the main bottleneck is the leader component in protocols of Fabric and enabling this protocol when required. For
their coordination-based approach. example, given that the end of an election specifies only a short time
of the whole time this event runs, which can be up to a few hours or
days, the coordination-based protocol can be enabled only when we
Middleware ’23, December 11–15, 2023, Bologna, Italy P. Nasirifard, et al.

(c) Voting Application Latency for an Increasing Transaction Arrival Rate (tps) (a) Voting Application Throughput
·105 ·104

Throughput (tps)
4 2,000
Latency (ms)

600

408 / 407
388 / 387
391 / 389
3

280 / 278
268 / 266
272 / 271
276 / 275
281 / 282
437 / 417
1 1,500

445/442
503/512
400 2 1,000
0.5
200 1 500
0 0 0 0
ps tp
s
tp
s
tp
s
tp
s
tp
s
tp
s
tp
s
ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps 0t 00 00 00 00 00 00 00
0 0t 00t 00t 00t 00t 00t 00t 00t 00t 00t 00t 00t 00t 00t 00t 00t 0t 0t 0t 0t 0t 0t 0t 0t 50 10 15 20 25 30 35 40
5 10 15 20 25 30 35 40 5 10 15 20 25 30 35 40 50 100 150 200 250 300 350 400

(d) Auction Application Latency for an Increasing Transaction Arrival Rate (tps) (b) Auction Application Throughput
·105 ·104

Throughput (tps)
6 2,000
Latency (ms)

600

285 / 285
266 / 266
271 / 270
274 / 274
281 / 280
551 / 537
400 / 399
387 / 386
390 / 390
1

440/441
508/509
1,500
4
400 1,000
0.5 2
200 500
0 0 0 0
ps tp
s
tp
s
tp
s
tp
s
tp
s
tp
s ps
ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps ps 0t 00 00 00 00 00 00 00
t
0t 0t 0t 0t 0t 0t 0t 0t 0t 0t 0t 0t 0t 0t 0t 0t 0t 0t 0t 0t 0t 0t 0t 0t 50 10 15 20 25 30 35 40
50 100 150 200 250 300 350 400 50 100 150 200 250 300 350 400 50 100 150 200 250 300 350 400

OrderlessChain BIDL Sync HotStuff

OrderlessChain Modify BIDL Modify Sync HotStuff Modify OrderlessChain Read BIDL Read Sync HotStuff Read

Figure 10: Experiments with voting and auction applications on OrderlessChain, BIDL, and Sync HotStuff.

are near the end. Otherwise, we use our scalable coordination-free for preserving invariants. Some works reduce coordination while
protocol. offering BFT and preserving invariants [27, 38, 48, 63, 67]. However,
There exists an extensive range of I-confluent CRDT-based use they do not eliminate the coordination or have limited use cases.
cases [10, 13, 17, 32, 33, 39, 47, 50, 52, 58, 69, 74–77, 81, 82], from Bailis et al. [4] introduced I-confluence, which shares similarities
key-value stores to collaborative environments, which can be im- with Left Commuting Operations [21] for identifying the possible
plemented on OrderlessChain. Also, CRDT-based and I-confluent order of operations to persevere the application’s serializability. It
development tools such as Automerge [36], Katara [40] and Lucy [78] also shares similarities with the CALM theorem [29], demonstrating
for modeling and expressing various applications can be adapted to that monotonic transactions can be processed coordination-free.
OrderlessChain to offer BFT. Katara offers a solution for automati- Studies propose coordination-based BFT approaches for exe-
cally creating CRDTs from sequential non-CRDT implementations. cuting CRDT applications [18, 19, 72, 83]. However, only some
Lucy provides an environment for determining whether invariant works study CRDTs in blockchains. Vegvisir [34] study integrat-
conditions are I-confluent. We developed other applications [55– ing CRDTs with a Directed Acyclic Graph-structured blockchain
57] (not evaluated here) as proof of concept. We implemented an without support for executing smart contracts. RAMBLE [31] pro-
IoT-based supply chain use case to monitor the health of temperature- poses a blockchain-based Twitter-like messaging protocol based
sensitive products during transit. We also implemented a trusted on CRDT sets. MEChain [79] proposes a CRDT-enabled blockchain-
distributed file storage system and a private Federated Learning sys- based system for storing electronic health records. Setchain [12]
tem by extending OrderlessChain with customized CRDTs. The decreases coordination in blockchains by only partially ordering
development of these applications on OrderlessChain was straight- transactions. However, their solution is only limited to grow-only
forward. sets and still requires some round of coordination. FabricCRDT [54]
uses coordination-based JSON CRDT techniques. The difference
10 RELATED WORK between FabricCRDT and OrderlessChain, besides our system
The low scalability of PoW-based protocols makes them infeasible enabling BFT CRDTs in a coordinate-free environment, is Fabric-
for permissioned blockchains such as MultiChain [26], R3 Corda [28], CRDT’s state-based CRDT approach. For every modification on
Quorum [51], and Fabric [2], which use various non-PoW-based FabricCRDT, the entire object stored on the ledger must be retrieved
coordination-based protocols. Although these protocols improve and modified and then sent to organizations to be merged with the
performance, the required coordination among nodes negatively existing objects. On FabricCRDT, the objects gradually become large,
affects performance. Also, many transactions fail due to Fabric’s opti- negatively affecting the performance, as observed here.
mistic coordination-based protocol [14, 71]. Also, the Raft-based [59]
ordering service of Fabric is not BFT. Other studies propose BFT or- 11 CONCLUSIONS
derers [7, 9]. We presented OrderlessChain, a BFT coordination-free permis-
sioned blockchain capable of hosting and executing an extensive
Reducing coordination to improve scalability while preserving in- range of safe and live CRDT-based I-confluent applications. Our
variants has been an active field of research. Several studies propose evaluation shows that a coordination-free permissioned blockchain
solutions in non-Byzantine systems [5, 6, 42–46, 61, 62]. However, performs significantly better than coordination-based approaches
they do not consider the added complexity of Byzantine failures for applications with I-confluent invariant conditions.
OrderlessChain: A CRDT-based BFT Coordination-free Blockchain Without Global Order of Transactions Middleware ’23, December 11–15, 2023, Bologna, Italy

REFERENCES [26] G. Greenspan. 2015. Multichain Private Blockchainm White Paper. , 57–60 pages.
[1] I. Abraham, D. Malkhi, K. Nayak, L. Ren, and M. Yin. 2020. Sync HotStuff: Simple [Link] Accessed:
and Practical Synchronous State Machine Replication. In 2020 IEEE Symposium on 2023-08-28.
Security and Privacy. IEEE, 106–118. [Link] [27] R. Guerraoui, P. Kuznetsov, M. Monti, M. Pavlovič, and D.-A. Seredinschi. 2019.
[2] E. Androulaki, A. Barger, V. Bortnikov, C. Cachin, K. Christidis, A. De Caro, D. The Consensus Number of a Cryptocurrency. In Proceedings of the 2019 ACM
Enyeart, C. Ferris, G. Laventman, Y. Manevich, S. Muralidharan, C. Murthy, B. Symposium on Principles of Distributed Computing. ACM, 307–316. [Link]
Nguyen, M. Sethi, G. Singh, K. Smith, A. Sorniotti, C. Stathakopoulou, M. Vukolić, org/10.1145/3293611.3331589
S. W. Cocco, and J. Yellick. 2018. Hyperledger Fabric: A Distributed Operating [28] M. Hearn and R. G. Brown. 2016. Corda: A Distributed Ledger. Corda Technical
System for Permissioned Blockchains. In Proceedings of the Thirteenth EuroSys White Paper 2016 (2016).
Conference. ACM, 30:1–30:15. [Link] [29] J. M. Hellerstein. 2010. The Declarative Imperative: Experiences and Conjectures
[3] The Go Authors. 2023. Golang, Go Programming Language. [Link] in Distributed Logic. SIGMOD Rec. (2010), 5–19. [Link]
Accessed: 2023-09-12. 1860704
[4] P. Bailis, A. Fekete, M. J. Franklin, A. Ghodsi, J. M. Hellerstein, and I. Stoica. 2014. [30] J. Huang, D. He, M. S. Obaidat, P. Vijayakumar, M. Luo, and Kim-Kwang R. Choo.
Coordination Avoidance in Database Systems. Proc. VLDB Endow. (2014), 185–196. 2021. The Application of the Blockchain Technology in Voting Systems: A Review.
[Link] ACM Comput. Surv. (2021). [Link]
[5] V. Balegas, S. Duarte, C. Ferreira, R. Rodrigues, N. Preguiça, M. Najafzadeh, and M. [31] M. Imam, S. Takiar, and J. Wang. 2017. RAMBLE: Reliable Asynchronous Messaging
Shapiro. 2015. Putting Consistency Back into Eventual Consistency. In Proceedings for Byzantine Linked Entities. (2017).
of the Tenth European Conference on Computer Systems. ACM. [Link] [32] K. Jannes, B. Lagaisse, and W Joosen. 2021. OWebSync: Seamless Synchronization
1145/2741948.2741972 of Distributed Web Clients. IEEE Transactions on Parallel and Distributed Systems
[6] V. Balegas, D. Serra, S. Duarte, C. Ferreira, M. Shapiro, R. Rodrigues, and N. Preguiça. (2021), 2338–2351. [Link]
2015. Extending Eventually Consistent Cloud Databases for Enforcing Numeric [33] T. Jungnickel and L. Oldenburg. 2017. Pluto: The CRDT-Driven IMAP Server. In Pro-
Invariants. In 2015 IEEE 34th Symposium on Reliable Distributed Systems. IEEE, ceedings of the 3rd International Workshop on Principles and Practice of Consistency
31–36. [Link] for Distributed Data. ACM. [Link]
[7] A. Barger, Y. Manevich, H. Meir, and Y. Tock. 2021. A Byzantine Fault-Tolerant [34] K. Karlsson, W. Jiang, S. Wicker, D. Adams, E. Ma, R. van Renesse, and H. Weather-
Consensus Library for Hyperledger Fabric. In 2021 IEEE International Conference spoon. 2018. Vegvisir: A Partition-Tolerant Blockchain for the Internet-of-Things.
on Blockchain and Cryptocurrency. IEEE, 1–9. [Link] In 2018 IEEE 38th International Conference on Distributed Computing Systems. IEEE,
2021.9461099 1150–1158. [Link]
[8] J. Bauwens and E. Gonzalez Boix. 2019. Memory Efficient CRDTs in Dynamic [35] S. Kim, Y. Kwon, and S. Cho. 2018. A Survey of Scalability Solutions on Blockchain.
Environments. In Proceedings of the 11th ACM SIGPLAN International Workshop In 2018 International Conference on Information and Communication Technology
on Virtual Machines and Intermediate Languages. ACM, 48–57. [Link] Convergence. 1204–1207. [Link]
1145/3358504.3361231 [36] M. Kleppmann. 2020. Automerge, A JSON-like CRDT. [Link]
[9] A. Bessani, J. Sousa, and M. Vukolić. 2017. A Byzantine Fault-Tolerant Ordering automerge/automerge Accessed: 2023-10-11.
Service for the Hyperledger Fabric Blockchain Platform. In Proceedings of the 1st [37] M. Kleppmann and A. R. Beresford. 2017. A Conflict-Free Replicated JSON Datatype.
Workshop on Scalable and Resilient Infrastructures for Distributed Ledgers. ACM. IEEE Transactions on Parallel and Distributed Systems (2017), 2733–2746. https:
[Link] //[Link]/10.1109/TPDS.2017.2697382
[10] R. Brown, S. Cribbs, C. Meiklejohn, and S. Elliott. 2014. Riak DT Map: A Composable, [38] M. Kleppmann and H. Howard. 2020. Byzantine Eventual Consistency and the
Convergent Replicated Dictionary. In Proceedings of the First Workshop on Principles Fundamental Limits of Peer-to-Peer Databases. CoRR (2020). arXiv:2012.00472
and Practice of Eventual Consistency. ACM, 1–1. [Link] [39] M. Kleppmann, A. Wiggins, P. van Hardenberg, and M. McGranaghan. 2019. Local-
2596633 First Software: You Own Your Data, in Spite of the Cloud. In Proceedings of the
[11] C. Cachin and M. Vukolic. 2017. Blockchain Consensus Protocols in the Wild. 2019 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and
CoRR (2017). arXiv:1707.01873 Reflections on Programming and Software. ACM, 154–178. [Link]
[12] M. Capretto, M. Ceresa, A. F. Anta, A. Russo, and C. Sánchez. 2022. Setchain: 3359591.3359737
Improving Blockchain Scalability with Byzantine Distributed Sets and Barriers. [40] S. Laddad, C. Power, M. Milano, A. Cheung, and J. M. Hellerstein. 2022. Katara:
arXiv:2206.11845 Synthesizing CRDTs with Verified Lifting. Proc. ACM Program. Lang. (2022).
[13] S. J. Castiñeira and A. Bieniusa. 2015. Collaborative Offline Web Applications [Link]
Using Conflict-free Replicated Data Types. In Proceedings of the First Workshop on [41] L. Lamport. 1978. Time, Clocks, and the Ordering of Events in a Distributed System.
Principles and Practice of Consistency for Distributed Data. ACM. [Link] Commun. ACM 21, 7 (1978), 558–565. [Link]
10.1145/2745947.2745952 [42] L. Lamport. 2005. Generalized Consensus and Paxos. (2005).
[14] J. A. Chacko, R. Mayer, and H-A. Jacobsen. 2021. Why Do My Blockchain Transac- [43] L. Lamport. 2006. Lower Bounds for Asynchronous Consensus. Distributed
tions Fail? A Study of Hyperledger Fabric. ACM, 221–234. [Link] Computing (2006), 104–125. [Link]
3448016.3452823 [44] C. Li, D. Porto, A. Clement, J. Gehrke, N. Preguiça, and R. Rodrigues. 2012. Making
[15] J. A. Chacko, R. Mayer, and H.-A. Jacobsen. 2023. How To Optimize My Blockchain? Geo-Replicated Systems Fast as Possible, Consistent When Necessary. In OSDI.
A Multi-Level Recommendation Approach. Proc. ACM Manag. Data (2023). https: USENIX Association, 265–278.
//[Link]/10.1145/3588704 [45] J. Liu, T. Magrino, O. Arden, M. D. George, and A. C. Myers. 2014. Warranties for
[16] R. Chaganti, B. Bhushan, and V. Ravi. 2022. The Role of Blockchain in DDoS Attacks Faster Strong Consistency. In USENIX NSDI. USENIX Association, 503–517.
Mitigation: Techniques, Open Challenges and Future Directions. arXiv:2202.03617 [46] W. Lloyd, M. J. Freedman, M. Kaminsky, and D. G. Andersen. 2011. Don’t Settle
[17] B. Chandramouli, G. Prasaad, D. Kossmann, J. Levandoski, J. Hunter, and M. Barnett. for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS. In
2018. FASTER: A Concurrent Key-Value Store with In-Place Updates. In SIGMOD. Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles.
ACM, 275–290. [Link] ACM, 401–416. [Link]
[18] G. A. Di Luna, E. Anceaume, and L. Querzoni. 2020. Byzantine Generalized Lattice [47] Y. Mao, Z. Liu, and H.-A. Jacobsen. 2022. Reversible Conflict-Free Replicated Data
Agreement. In IEEE IPDPS. Types. In Proceedings of the 23rd ACM/IFIP International Middleware Conference.
[19] S. Duan, M. K. Reiter, and H. Zhang. 2017. Secure Causal Atomic Broadcast, ACM, 295–307. [Link]
Revisited. In 2017 47th Annual IEEE/IFIP International Conference on Dependable [48] J.-P. Martin and L. Alvisi. 2006. Fast Byzantine Consensus. (2006), 402–411.
Systems and Networks. IEEE, 61–72. [Link] [Link]
[20] Cloud Native Computing Foundation. 2023. gRPC, a High Performance, Open- [49] U. Maurer. 1996. Modelling a Public-Key Infrastructure. In European Symposium
Source Universal RPC Framework. [Link] Accessed: 2023-10-10. on Research in Computer Security. Springer, 325–350.
[21] R. Friedman and K. Birman. 1996. Trading Consistency for Availability in Distributed [50] D. Mealha, N. Preguiça, M. C. Gomes, and J. Leitão. 2019. Data Replication on
Systems. Technical Report. the Cloud/Edge. In Proceedings of the 6th Workshop on Principles and Practice of
[22] H. S. Galal and A. M. Youssef. 2019. Verifiable Sealed-Bid Auction on the Ethereum Consistency for Distributed Data. ACM. [Link]
Blockchain. In Financial Cryptography and Data Security. Springer Berlin Heidel- [51] J. P. Morgan Chase. 2018. A Permissioned Implementation of Ethereum. https:
berg, 265–278. //[Link]/ConsenSys/quorum Accessed: 2023-10-08.
[23] S. Gilbert and N. Lynch. 2012. Perspectives on the CAP Theorem. Computer 45 [52] M. Najafzadeh, M. Shapiro, and P. Eugster. 2018. Co-Design and Verification of an
(2012), 30–36. [Link] Available File System. In Verification, Model Checking, and Abstract Interpretation.
[24] Google. 2021. LevelDB. [Link] Accessed: 2023-10-08. Springer International Publishing, 358–381.
[25] C. Gorenflo, S. Lee, L. Golab, and S. Keshav. 2019. FastFabric: Scaling Hyperledger [53] S. Nakamoto. 2008. Bitcoin: A Peer-to-Peer Electronic Cash System.
Fabric to 20,000 Transactions per Second. (2019), 455–463. [Link] [54] P. Nasirifard, R. Mayer, and H.-A. Jacobsen. 2019. FabricCRDT: A Conflict-Free
1109/BLOC.2019.8751452 Replicated Datatypes Approach to Permissioned Blockchains. In Proceedings of
the 20th International Middleware Conference. ACM, 110–122. [Link]
Middleware ’23, December 11–15, 2023, Bologna, Italy P. Nasirifard, et al.

1145/3361525.3361540 [79] H. Y. Wu, L. Jie Li, H.-Y. Paik, and S. S. Kanhere. 2021. MEChain: A Multi-layer
[55] P. Nasirifard, R. Mayer, and H.-A. Jacobsen. 2022. OrderlessChain: A CRDT- Blockchain Structure with Hierarchical Consensus for Secure EHR System. In 2021
Enabled Blockchain without Total Global Order of Transactions: Poster Abstract. IEEE 20th International Conference on Trust, Security and Privacy in Computing and
In Proceedings of the 23rd International Middleware Conference Demos and Posters. Communications. IEEE, 976–987. [Link]
ACM, 5–6. [Link] 00136
[56] P. Nasirifard, R. Mayer, and H.-A. Jacobsen. 2022. OrderlessFile: A CRDT-Enabled [80] M. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta, and I. Abraham. 2019. HotStuff:
Permissioned Blockchain for File Storage: Poster Abstract. In Proceedings of the BFT Consensus with Linearity and Responsiveness. In Proceedings of the 2019
23rd International Middleware Conference Demos and Posters. ACM, 15–16. https: ACM Symposium on Principles of Distributed Computing. ACM, 347–356. https:
//[Link]/10.1145/3565386.3565491 //[Link]/10.1145/3293611.3331591
[57] P. Nasirifard, R. Mayer, and H.-A. Jacobsen. 2022. OrderlessFL: A CRDT-Enabled [81] G. Younes, A. Shoker, P. S. Almeida, and C. Baquero. 2016. Integration Challenges
Permissioned Blockchain for Federated Learning: Poster Abstract. In Proceedings of Pure Operation-based CRDTs in Redis. In First Workshop on Programming Models
of the 23rd International Middleware Conference Demos and Posters. ACM, 7–8. and Languages for Distributed Computing. ACM, 7:1–7:4. [Link]
[Link] 2957319.2957375
[58] P. Nicolaescu, K. Jahns, M. Derntl, and R. Klamma. 2016. Near Real-Time Peer- [82] M. Zawirski, N. Preguiça, S. Duarte, A. Bieniusa, V. Balegas, and M. Shapiro. 2015.
to-Peer Shared Editing on Extensible Data Types. In Proceedings of the 2016 ACM Write Fast, Read in the Past: Causal Consistency for Client-Side Applications.
International Conference on Supporting Group Work. ACM, 39–49. [Link] In Proceedings of the 16th Annual Middleware Conference. ACM, 75–87. https:
10.1145/2957276.2957310 //[Link]/10.1145/2814576.2814733
[59] D. Ongaro and J. Ousterhout. 2014. In Search of an Understandable Consensus [83] W. Zhao, M. Babi, W. Yang, X. Luo, Y. Zhu, J. Yang, C. Luo, and Mary Y. 2016.
Algorithm. In 2014 USENIX Annual Technical Conference. USENIX Association, Byzantine Fault Tolerance for Collaborative Editing with Commutative Operations.
305–319. In 2016 IEEE International Conference on Electro Information Technology. IEEE, 246–
[60] Oracle. 2021. Read-Your-Writes Consistency. [Link] Accessed: 251. [Link]
2023-09-20.
[61] P. E. O’Neil. 1986. The Escrow Transactional Method. ACM Trans. Database Syst.
(1986), 405–430. [Link]
[62] F. Pedone and A. Schiper. 1999. Generic Broadcast. In Distributed Computing.
Springer-Verlag, 94–108.
[63] M. Pires, S. Ravi, and R. Rodrigues. 2017. Generalized Paxos Made Byzantine
(and Less Complex). In Stabilization, Safety, and Security of Distributed Systems.
Springer International Publishing, 203–218.
[64] N. Preguiça. 2018. Conflict-free Replicated Data Types: An Overview.
arXiv:1806.10254
[65] Hyperledger Project. 2023. Hyperledger Caliper. [Link]
caliper/ Accessed: 2023-10-02.
[66] J. Qi, X. Chen, Y. Jiang, J. Jiang, T. Shen, S. Zhao, S. Wang, G. Zhang, L. Chen,
M. H. Au, and H. Cui. 2021. BIDL: A High-Throughput, Low-Latency Permissioned
Blockchain Framework for Datacenter Networks. In Proceedings of the ACM SIGOPS
28th Symposium on Operating Systems Principles. ACM, 18–34. [Link]
1145/3477132.3483574
[67] P. Raykov, N. Schiper, and F. Pedone. 2011. Byzantine Fault-Tolerance with Com-
mutative Commands. In Principles of Distributed Systems. 329–342.
[68] L. S. Sankar, M. Sindhu, and M. Sethumadhavan. 2017. Survey of Consensus
Protocols on Blockchain Applications. In 2017 4th International Conference on
Advanced Computing and Communication Systems. 1–5. [Link]
ICACCS.2017.8014672
[69] M. Shapiro, A. Bieniusa, N. M. Preguiça, V. Balegas, and C. Meiklejohn. 2018.
Just-Right Consistency: Reconciling Availability and Safety. CoRR (2018).
arXiv:1801.06340
[70] M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski. 2011. Conflict-Free Repli-
cated Data Types. In Symposium on Self-Stabilizing Systems. Springer, 386–400.
[71] A. Sharma, F. M. Schuhknecht, D. Agrawal, and J. Dittrich. 2019. Blurring the Lines
Between Blockchains and Database Systems: The Case of Hyperledger Fabric. In
Proceedings of the 2019 International Conference on Management of Data. ACM,
105–122. [Link]
[72] A. Shoker, H. Yactine, and C. Baquero. 2017. As Secure as Possible Eventual
Consistency: Work in Progress. In Proceedings of the 3rd International Workshop
on Principles and Practice of Consistency for Distributed Data. ACM. [Link]
org/10.1145/3064889.3064895
[73] D. Sun, S. Xia, C. Sun, and D. Chen. 2004. Operational Transformation for Collabora-
tive Word Processing. In Proceedings of the 2004 ACM Conference on Computer Sup-
ported Cooperative Work. ACM, 437–446. [Link]
[74] V. Tao, M. Shapiro, and V. Rancurel. 2015. Merging Semantics for Conflict Updates
in Geo-Distributed File Systems. In Proceedings of the 8th ACM International Systems
and Storage Conference. ACM. [Link]
[75] A. van der Linde, P. Fouto, J. Leitão, N. Preguiça, S. Castiñeira, and A. Bieniusa.
2017. Legion: Enriching Internet Services with Peer-to-Peer Interactions. In
Proceedings of the 26th International Conference on World Wide Web. ACM. https:
//[Link]/10.1145/3038912.3052673
[76] P. van Hardenberg and M. Kleppmann. 2020. PushPin: Towards Production-Quality
Peer-to-Peer Collaboration. In Proceedings of the 7th Workshop on Principles and
Practice of Consistency for Distributed Data. ACM. [Link]
3393683
[77] S. Weiss, P. Urso, and P. Molli. 2009. Logoot: A Scalable Optimistic Replication
Algorithm for Collaborative Editing on P2P Networks. In 2009 29th IEEE Inter-
national Conference on Distributed Computing Systems. IEEE, 404–412. https:
//[Link]/10.1109/ICDCS.2009.75
[78] M. Whittaker and J. M. Hellerstein. 2020. Checking Invariant Confluence, In Whole
or In Parts. SIGMOD (2020), 7–14. [Link]