OrderlessChain Do Permissioned Blockchains Need Total Global Order of Transactions
2025-04-29
0
0
1.1MB
15 页
10玖币
侵权投诉
OrderlessChain: Do Permissioned Blockchains Need
Total Global Order of Transactions?∗
Pezhman Nasirifard
Technical University of Munich
Germany
p.nasirifard@tum.de
Ruben Mayer
Technical University of Munich
Germany
Hans-Arno Jacobsen
University of Toronto
Canada
Abstract
Existing permissioned blockchains often rely on coordination-
based consensus protocols to ensure the safe execution of
applications in a Byzantine environment. Furthermore, these
protocols serialize the transactions by ordering them into a
total global order. The serializability preserves the correctness
of the application’s state stored on the blockchain. However,
using coordination-based protocols to attain the global or-
der of transactions can limit the throughput and induce high
latency. In contrast, application-level correctness require-
ments exist that are not dependent on the order of trans-
actions, known as invariant-conuence (I-conuence). The I-
conuent applications can execute in a coordination-free man-
ner beneting from the improved performance compared to
the coordination-based approaches. The safety and liveness of
I-conuent applications are studied in non-Byzantine environ-
ments, but the correct execution of such applications remains
a challenge in Byzantine coordination-free environments.
This work introduces OrderlessChain, a coordination-free
permissioned blockchain for the safe and live execution of
I-conuent applications in a Byzantine environment. We im-
plemented a prototype of our system, and our evaluation
results demonstrate that our coordination-free approach per-
forms better than coordination-based blockchains.
1 Introduction
The main property contributing to blockchains’ popularity
since the introduction of Bitcoin [
36
] is the trusted execution
of transactions in a trustless, decentralized environment. To
oer trust and prevent Byzantine behaviors such as Sybil at-
tacks [
46
,
56
], blockchains use consensus protocols, such as
the Proof-of-Work-based (PoW) protocols used in Bitcoin [
36
].
Another essential property of consensus protocols enables
the system to agree on the total global order of transactions
for a serialized execution. The serializability is required to
preserve the correctness of the application’s state stored on
the blockchain. For example, serialization prevents a user’s
negative account balance in the case of Bitcoin, as every node
sequentially executes the transactions in the same order. How-
ever, the consensus protocols in several blockchains are severe
bottlenecks to their throughput and latency [27, 45].
∗
This paper is a preprint of the work published at the 24th ACM
International Middleware Conference (Middleware ’23). DOI:
https://doi.org/10.1145/3590140.3629111. Please cite the original Mid-
dleware conference version of the paper.
In contrast to public blockchains, permissioned blockchains
are only accessible by authenticated and authorized partic-
ipants [
12
,
45
]. Although the participants’ identity is known,
they do not trust each other. Permissioned blockchains, such
as Hyperledger Fabric (Fabric) [
5
], take advantage of their per-
missioned property to implement more ecient coordination-
based consensus protocols. However, the coordination-based
nature of these protocols remains a bottleneck [
14
,
15
,
22
,
49
].
In general, decreasing coordination plays a vital role in
improving the performance of distributed systems [
6
]. A
coordination-free blockchain could enable the concurrent
execution of transactions, leading to higher throughput and
lower latency. However, simply eliminating the coordination
may jeopardize the correctness depending on the application.
For example, a payment processing application may require
rejecting transactions that result in the payee’s account’s bal-
ance turning negative [
31
]. A coordination-free blockchain
cannot preserve this requirement [6, 29].
In contrast, there exist application-level correctness re-
quirements that can be preserved in a coordination-free dis-
tributed system, which are known as Invariant-Conuent (I-
conuent) invariant conditions [
6
]. For example, transactions
that only deposit funds to an account can execute without co-
ordination. In other words, the I-conuent transactions can be
processed in any order while preserving application-level cor-
rectness, and the nal state of the application is independent
of the order of the transactions. One technique that can create
I-conuent transactions is Conict-free Replicated Data Types
(CRDTs) [
48
]. CRDTs are abstract data types that converge to
the same state in a coordination-free environment.
Bailis et al. [
6
] demonstrated that unordered transactions
preserve the I-conuent invariants of applications in non-
Byzantine and eventually consistent environments. In other
words, applications with I-conuent invariants are safe and
live in non-Byzantine coordination-free environments. The
authors also showed the improved throughput and latency
of taking advantage of coordination-free approaches. How-
ever, preserving the safety and liveness of applications in a
Byzantine environment is dependent on paying a high co-
ordination cost in other systems [
14
,
16
,
22
,
27
,
45
,
49
]. By
providing a Byzantine coordination-free environment where
I-conuent applications continue to be safe and live, we ben-
et from improved performance while ensuring trust in a
trustless environment. In this work, we present Orderless-
Chain, a coordination-free permissioned blockchain without
1
arXiv:2210.01477v3 [cs.DC] 24 Oct 2023
total global order of transactions. OrderlessChain uses the
properties of permissioned blockchains and CRDTs to oer an
innovative two-phase execute-commit protocol for creating
safe and live applications in a Byzantine coordination-free
environment. We also built ve applications on Orderless-
Chain to show its practicability.
We oer the following contributions in this paper:
1.
We introduce OrderlessChain, a novel permissioned
blockchain capable of executing safe and live appli-
cations in a Byzantine coordination-free environment.
Our system achieves this without the coordination over-
head for creating a total global order of transactions,
improving the throughput and scalability.
2.
We demonstrate a novel approach for creating Turing-
complete blockchain applications based on CRDTs. Our
approach preserves the I-conuent invariants of appli-
cations in a coordination-free Byzantine environment.
3.
We implement a prototype of OrderlessChain and
demonstrate the improved throughput and latency of
the coordination-free approach for I-conuent applica-
tions compared to existing permissioned blockchains.
The remainder of the paper is organized as follows. First,
we provide a background on I-conuence and CRDTs in Sec-
tion 2 followed by the system model in Section 3. Then, we
explain our protocol in Section 4. We discuss the applications
of OrderlessChain and the implementation in Sections 5 and
6. We also explain our approach for preserving application-
level correctness requirements in Section 7 and the eects of
Byzantine participants in Section 8. We present evaluations
in Section 9 and review related work in Section 10.
2 Background
Invariant Conditions and Invariant Conuence – Dier-
ent applications have dierent correctness requirements. For
example, a banking application may be required to prevent
the customers’ account balances from dropping below zero.
Developers specify the correctness of an application by den-
ing a set of invariant conditions
{I1,...,Is}
on the application’s
state. Each
Ij
represents a requirement that nodes must pre-
serve during the application’s lifecycle. Preserving invariants
in a distributed system with globally serialized transactions
is relatively straightforward. Provided that each transaction
preserves the invariants, serialization enables the nodes to
apply 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 re-
ceive the transactions in dierent orders. Hence, preserving
invariants is challenging. For example, a node that stores the
account balance of a customer with an account balance of
{Balance :100}
can accept only one of the withdrawal trans-
actions of
Withdraw(50)
and
Withdraw(60)
. Applying both
transactions results in a negative account balance and violates
the application’s invariants. Without coordination, the nodes
cannot agree to accept one of the two transactions.
Bailis et al. [
6
] studied preserving invariants in a non-
Byzantine coordination-free distributed system and intro-
duced the notion of Invariant Conuence (I-conuence). A set
of transactions
{TS1,...,TSm}
are I-conuent with regard to an
invariant condition
Ij
, if the transactions can be applied in
dierent orders on dierent nodes while preserving
Ij
. Con-
sider the mentioned withdrawal transactions as an example
of a non-I-conuent transaction set. However, two deposit
transactions
Deposit(50)
and
Deposit(60)
are I-conuent, as
applying these transactions in any order on dierent nodes
does not violate the non-negative invariant condition. Hence,
the I-conuent transactions must have these two properties:
(1) Commutativity: The transactions can be applied in any or-
der. (2) Convergence: The nal state is independent of the order
of transactions. Bailis et al. proved that only I-conuent trans-
actions could be executed on a coordination-free distributed
system and non-I-conuent transactions require coordination
among the system’s nodes [6].
Conict-free Replicated Data Types – One available
technique that provides commutative and convergent trans-
actions as required by I-conuence is Conict-free Replicated
Data Types (CRDTs). CRDTs represent abstract data types
that converge to the same state in the presence of concurrent
transactions in a coordination-free distributed system [
48
].
These data types encapsulate common data structures such as
maps and provide APIs for reading and modifying their values.
Since concurrent transactions can result in conicting values,
CRDTs use built-in mechanisms to resolve conicts without
coordination. Shapiro et al. [
48
] formalized CRDTs and proved
their strong eventual consistency property (SEC) in an eventu-
ally consistent system. An SEC system has two requirements:
(1) Eventual delivery of transactions: If a transaction is deliv-
ered to one correct node, then all correct nodes will eventually
receive the transaction. (2) Strong convergence of nodes: If the
same set of transactions is applied on every correct node, then
the nodes’ state immediately converges to the same state [
48
].
CRDTs synchronize among dierent nodes through propa-
gating commutative transactions [
33
]. When extending com-
mon data structures with CRDT features, the transactions
may inherently be commutative or not. For example, a counter
is easily modeled as a CRDT since increment transactions are
intrinsically commutative. However, modications for several
other data types are not commutative. For instance, assigning
a value to a single-value register is not inherently commuta-
tive. For converting a register to a CRDT, the register needs
to be extended with metadata, dening its behavior in the
presence of concurrent modications. This is achieved with
the help of the happened-before relation [
48
] that denes the
causal order between two events based on logical clocks [
32
].
The theoretical foundation for dening the requirements of
several CRDTs has been studied thoroughly [28, 44].
2
3 System Model
System Model – OrderlessChain is a strongly eventually
consistent, asynchronous permissioned blockchain. An Or-
derlessChain network consists of a set of organizations
{O1,...,On}
and a set of clients
{C1,...,Cr}
. Organizations can
communicate with other non-failed organizations by sending
and receiving messages.
A unique identier is assigned to each organization and
client. The identity of each organization is known to every
other organization and client in the network. An organization
represents entities that range from large corporations to small
businesses or even individuals. The purpose of organizations
is to dene trust boundaries in the system. Although the orga-
nizations’ identity is known to each other, the organizations
do not necessarily trust each other.
Running Example – To better convey our system model
and design, we create a voting application, to which we refer
throughout the paper. Each voter
Voteri
can vote for one party
among the candidate parties in
{P1,...,Pn}
. The network con-
sists of norganizations, where each organization represents
one distinct party. Each organization receives and stores votes
from voters. We consider the application correct if each voter
votes for at most one party. We chose this use case since vot-
ing applications are among popular blockchain use cases [
24
].
Additionally, studies have shown that coordination in such
highly concurrent use cases is a bottleneck [14, 49].
Application’s World State – Each organization stores a
replica of the application’s state as a set of key-value pairs
represented by
STOi
, which represents the application state
at organization
Oi
. Since OrderlessChain is an SEC system,
the replicated application states
STO1,...,STOn
at organizations
O1,...,On
may diverge from each other, but will eventually con-
verge to the same state. At any given point in time, we dene
the application’s world state
STApp
as
STApp =∪n
i=1STOi
as the
union of the application state at all organizations where the
values of identical keys are merged based on the techniques
discussed in this paper.
Invariant Conditions – An application’s correctness is
imposed by the developer by dening a set of invariant condi-
tions
{I1,...,Is}
on
STApp
. Each invariant
Ij
species a constraint
over STApp. We dene the application correctness as follows:
Denition 3.1.
STApp
Correctness. Let
STApp
be the applica-
tion’s world state that does not violate the invariant conditions
{I1,...,Is}
. Let the transaction set
{TS1,...,TSm}
be I-conuent
with regard to
{I1,...,Is}
. Then, committing the transactions
{TS1,...,TSm}
does not violate any invariant conditions
{I1,...,Is}
over STApp.
Application’s Endorsement Policy – The application
developers specify the endorsement policy for the applica-
tion. The endorsement policy species which organizations
must sign and commit the transactions. The process of ob-
taining the signature is called endorsing. The application’s
endorsement policy has the format
EP :{q of n}
, where nis the
number of organizations in the system, and qis the minimum
number of organizations required for endorsing as well as
committing a transaction. In other words, the endorsement
policy determines the trust requirements of the application
and enables the developer to adjust the amount of trust re-
quired.
In the context of our voting example, consider an election
with four participating parties
P1,P2,P3,P4
where each party is
represented by a corresponding organization
OP1,OP2,OP3,OP4
.
Consider the following two possible endorsement policies:
EP1:{2 of 4}
and
EP2:{4 of 4}
.
EP1
requires that votes are en-
dorsed and committed by at least two out of the four organiza-
tions.
EP2
indicates that all four organizations must endorse
and commit the voter’s vote. Furthermore, we identify one
invariant condition: maximally one vote per voter. The appli-
cation is correct if the maximally one vote per voter invariant
is preserved over
STApp
and committing transactions do not
violate this invariant.
Transaction Model – A transaction is valid as follows:
Denition 3.2. Transaction Validity. Let the application’s
endorsement policy be
EP :{q of n}
. Let
STApp
be in a correct
state concerning the invariant conditions. Let the transaction
TSi
be I-conuent concerning the invariant conditions. Then,
TSi
is valid if and only if it satises these two requirements: (1)
Signature validity:
TSi
is endorsed by at least qorganizations
and the client signed the transaction. (2) Invariant conditions
validity: Applying TSidoes not violate any invariants.
We dene the transaction TSito be committed as follows:
Denition 3.3. Commied Transaction. Let the applica-
tion’s endorsement policy be
EP :{q of n}
. Let the transaction
TSi
be valid. Then,
TSi
is successfully committed if and only if
at least qorganizations individually process and commit the
transaction successfully.
For the voting example with
EP1:{2 of 4}
, a transaction is
valid if it is signed by the client and is endorsed by at least
two organizations. Additionally, the valid transaction must
not violate the maximally one vote per voter invariant. Also,
at least two organizations must commit a valid transaction.
Failure Model – We consider the organizations and clients
to be potentially Byzantine. Byzantine organizations or clients
can fail arbitrarily. We consider an organization to be non-
faulty if and only if the organization processes every transac-
tion according to the OrderlessChain’s protocol. The trans-
actions can be delivered in any order, diering from the sent
order; they may also be duplicated, lost, or corrupted during
transmission. The safety and liveness properties of applica-
tions running on OrderlessChain are dened as follows:
Denition 3.4. Safety. Only valid transactions are success-
fully committed.
Denition 3.5. Liveness. Every valid transaction is eventu-
ally successfully committed.
3
摘要：
展开>>
收起<<
OrderlessChain:DoPermissionedBlockchainsNeedTotalGlobalOrderofTransactions?∗PezhmanNasirifardTechnicalUniversityofMunichGermanyp.nasirifard@tum.deRubenMayerTechnicalUniversityofMunichGermanyHans-ArnoJacobsenUniversityofTorontoCanadaAbstractExistingpermissionedblockchainsoftenrelyoncoordination-based...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
分类：图书资源
价格：10玖币
属性：15 页
大小：1.1MB
格式：PDF
时间：2025-04-29
渝公网安备50010702506394
