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-conuence (I-conuence). The I-

conuent applications can execute in a coordination-free man-

ner beneting from the improved performance compared to

the coordination-based approaches. The safety and liveness of

I-conuent 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-conuent 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 [

] is the trusted execution

of transactions in a trustless, decentralized environment. To

oer trust and prevent Byzantine behaviors such as Sybil at-

tacks [

], blockchains use consensus protocols, such as

the Proof-of-Work-based (PoW) protocols used in Bitcoin [

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 [

]. Although the participants’ identity is known,

they do not trust each other. Permissioned blockchains, such

as Hyperledger Fabric (Fabric) [

], take advantage of their per-

missioned property to implement more ecient coordination-

based consensus protocols. However, the coordination-based

nature of these protocols remains a bottleneck [

In general, decreasing coordination plays a vital role in

improving the performance of distributed systems [

]. 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 [

]. 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-Conuent (I-

conuent) invariant conditions [

]. For example, transactions

that only deposit funds to an account can execute without co-

ordination. In other words, the I-conuent 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-conuent transactions is Conict-free Replicated Data Types

(CRDTs) [

]. CRDTs are abstract data types that converge to

the same state in a coordination-free environment.

Bailis et al. [

] demonstrated that unordered transactions

preserve the I-conuent invariants of applications in non-

Byzantine and eventually consistent environments. In other

words, applications with I-conuent 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 [

]. By

providing a Byzantine coordination-free environment where

I-conuent applications continue to be safe and live, we ben-

et from improved performance while ensuring trust in a

trustless environment. In this work, we present Orderless-

Chain, a coordination-free permissioned blockchain without

arXiv:2210.01477v3 [cs.DC] 24 Oct 2023

total global order of transactions. OrderlessChain uses the

properties of permissioned blockchains and CRDTs to oer 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 oer the following contributions in this paper:

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.

We demonstrate a novel approach for creating Turing-

complete blockchain applications based on CRDTs. Our

approach preserves the I-conuent invariants of appli-

cations in a coordination-free Byzantine environment.

We implement a prototype of OrderlessChain and

demonstrate the improved throughput and latency of

the coordination-free approach for I-conuent applica-

tions compared to existing permissioned blockchains.

The remainder of the paper is organized as follows. First,

we provide a background on I-conuence 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 eects 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 Conuence – Dier-

ent applications have dierent 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 den-

ing a set of invariant conditions

{I1,...,Is}

on the application’s

state. Each

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 dierent 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. [

] studied preserving invariants in a non-

Byzantine coordination-free distributed system and intro-

duced the notion of Invariant Conuence (I-conuence). A set

of transactions

{TS1,...,TSm}

are I-conuent with regard to an

invariant condition

, if the transactions can be applied in

dierent orders on dierent nodes while preserving

. Con-

sider the mentioned withdrawal transactions as an example

of a non-I-conuent transaction set. However, two deposit

transactions

Deposit(50)

and

Deposit(60)

are I-conuent, as

applying these transactions in any order on dierent nodes

does not violate the non-negative invariant condition. Hence,

the I-conuent 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-conuent trans-

actions could be executed on a coordination-free distributed

system and non-I-conuent transactions require coordination

among the system’s nodes [6].

Conict-free Replicated Data Types – One available

technique that provides commutative and convergent trans-

actions as required by I-conuence is Conict-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 [

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 conicting values,

CRDTs use built-in mechanisms to resolve conicts without

coordination. Shapiro et al. [

] 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 [

CRDTs synchronize among dierent nodes through propa-

gating commutative transactions [

]. 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, modications 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, dening its behavior in the

presence of concurrent modications. This is achieved with

the help of the happened-before relation [

] that denes the

causal order between two events based on logical clocks [

The theoretical foundation for dening the requirements of

several CRDTs has been studied thoroughly [28, 44].

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 identier 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 dene 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 [

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

. 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 dene

the application’s world state

STApp

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 dening a set of invariant condi-

tions

{I1,...,Is}

STApp

. Each invariant

species a constraint

over STApp. We dene the application correctness as follows:

Denition 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-conuent

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 species 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:

Denition 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-conuent concerning the invariant conditions. Then,

TSi

is valid if and only if it satises 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 dene the transaction TSito be committed as follows:

Denition 3.3. Commied 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, diering 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 dened as follows:

Denition 3.4. Safety. Only valid transactions are success-

fully committed.

Denition 3.5. Liveness. Every valid transaction is eventu-

ally successfully committed.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

OrderlessChain:DoPermissionedBlockchainsNeedTotalGlobalOrderofTransactions?∗PezhmanNasirifardTechnicalUniversityofMunichGermanyp.nasirifard@tum.deRubenMayerTechnicalUniversityofMunichGermanyHans-ArnoJacobsenUniversityofTorontoCanadaAbstractExistingpermissionedblockchainsoftenrelyoncoordination-based...

展开>> 收起<<

OrderlessChain Do Permissioned Blockchains Need Total Global Order of Transactions.pdf

共15页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

OrderlessChain Do Permissioned Blockchains Need Total Global Order of Transactions

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: