1 Technical Report Analytical Modeling and Throughput

2025-04-28 0 0 763.34KB 36 页 10玖币

侵权投诉

Technical Report

Analytical Modeling and Throughput

Computation of Blockchain Sharding

Pourya Soltani and Farid Ashtiani

Abstract

Sharding has shown great potential to scale out blockchains. It divides nodes into smaller groups which

allow for partial transaction processing, relaying and storage. Hence, instead of running one blockchain,

we will run multiple blockchains in parallel, and call each one a shard. Sharding can be applied to

address shortcomings due to compulsory duplication of three resources in blockchains, i.e., computation,

communication and storage. The most pressing issue in blockchains today is throughput. Hence, usually

the main focus is to shard computation which leads to concurrent transaction processing. In this report,

we propose new queueing-theoretic models to derive the maximum throughput of sharded blockchains. We

consider two cases, a fully sharded blockchain and a computation sharding. In the former nodes are exclusive

to each shard in terms of their responsibilities, i.e., block production, relaying and storage. In the latter though,

only block production is exclusive and nodes relay and store every piece of information.We model each with

a queueing network that exploits signals to account for block production as well as multi-destination cross-

shard transactions. We make sure quasi-reversibility for every queue in our models is satisﬁed so that they

fall into the category of product-form queueing networks. We then obtain a closed-form solution for the

maximum stable throughput of these systems with respect to block size, block rate, number of destinations

in transactions and the number of shards. Comparing the results obtained from the two introduced sharding

systems, we conclude that the extent of sharding in different domains plays a signiﬁcant role in scalability.

Index Terms

Blockchain scalability, sharding, throughput, product-form queueing networks, quasi-reversibility

1 INTRODUCTION

THROUGHPUT in Bitcoin and Ethereum networks are way below the satisfactory levels.

Although most of the participating nodes in mentioned blockchains have evolved through

time, it has not led to much improvement in scalability. It so happens that blockchains do not scale

very easily. This stems from the well-known scalability trilemma in blockchains [1] which states

that only two properties among decentralization, security and scalability can fully be satisﬁed

in a system. In blockchains today, scalability is sacriﬁced for the sake of the other two. Different

The authors are with the Department of Electrical Engineering, Sharif University of Technology (SUT). Tehran 11155-4363, Iran (Email:

pourya.soltani@sharif.edu, ashtianimt@sharif.edu)

A condensed version of this technical report has been submitted as a journal paper.

arXiv:2210.04599v1 [cs.DC] 19 Sep 2022

solutions have been proposed to address the blockchain scalability problem [2], [3]. In this report,

we focus on one of the most promising solutions, i.e., sharding [4], [5].

Sharding partitions the network into small, manageable groups, called shards, that run parallel

to one another. The compulsory duplication of three resources (i.e., communication, data storage,

and computation) can now be avoided for each participating node, while these overheads must

be incurred by all full nodes in traditional non-sharded blockchains. Consequently, grouping

(sharding) can be performed in three domains, i.e., computation (block production), network

(communication) and storage. The main focus usually is to shard the computation, however,

other types can also be simultaneously achieved alongside it (e.g., RapidChain [6]). In particular,

computation sharding allows partial transaction processing on a single node, since now each

shard is only responsible for processing the jobs within the group.

Despite the simplicity of this idea, many new problems will arise in sharding since it is

being used in a decentralized system. Main challenges usually are with respect to intra-shard

consensus safety and cross-shard atomicity1[4], [7]. Intra-shard consensus safety stems from the

fact that in sharded networks, attackers can dominate a single shard more easily than dominating

the whole network. Shard takeover, also called 1% attack, is analogous to 51% attack in non-

sharded blockchains where adversary has enough resources to change the state of the system.

The other issue is related to the transactions (TXs) that target multiple shards, leading to cross-

shard transactions. There must be a shard interoperability mechanism in order to communicate

and verify the transactions that are cross-shard. Even so, guaranteeing the system consistency

is a challenge. The occurrence of orphaned blocks as the consequence of fork resolution, can

compromise the validity of system state.

Nevertheless, none of the above challenges concern us here. In this report, we model a

pre-conﬁgured sharding scheme using queueing networks (QNs) to derive its maximum sta-

ble throughput. Even so, there can still be many conﬁgurations for our sharding scenario. In

particular, sharding domains play a signiﬁcant role in deriving a proper model. They deﬁne

participants responsibilities and thus the measure of their engagement in any of the main tasks,

i.e., block production, relaying and storage. These responsibilities (especially those overlapped

among shards’ participants) will then be used to deﬁne system characteristics of our interest.

Thus, it is imperative to know in how many domains and to what extent sharding is applied.

In this report, our main focus will be on a fully sharded scenario. Each node then processes,

relays and stores only the information that are assigned to its exclusive shard. We ﬁrst introduce

the preliminary characteristics of our sharded blockchain, upon which we present an analytical

model based on a QN to best ﬁt the description. We then obtain a closed-from solution for the

maximum stable throughput of this system, which is the limit before system overloads and delay

goes to inﬁnity. We also brieﬂy introduce and examine a computation sharding scenario without

1. In order to guarantee consistency in the whole system, either all operations in a transaction must complete or none of them.

any network or storage sharding. In this setup, all the information is broadcast to, validated

and stored by every node in the system. Nonetheless, block production is restricted only to the

information related to the corresponding shard. Our contributions are as follows:

•We propose a QN model to best ﬁt the characteristics of fully sharded blockchains where

each shard has its own set of distinct miners. In the proposed model, we exploit multi-

class negative and positive signals [8] in order to model the block production as well as

multi-destination cross-shard TXs in the blockchain.

•Using the proposed model, we derive the maximum stable throughput of the system with

respect to block size, block rate, number of shards and the number of destinations in TXs.

We show that though the probability of TXs to become cross-shard approaches one as the

number of shards in the system increases [9], in a fully sharded blockchain, throughput

growth with respect to the number of shards still converges to be linear.

•To further illuminate the effect of sharding domains in the modeling, we modify our

proposed QN model to examine a computation sharding scenario without any network or

storage sharding.

•Since the shared network in the computation sharding scenario can ultimately become the

bottleneck, we consider a parameter limiting the load on the shared network in order to

limit the fork rate, then we derive the maximum throughput satisfying the constraints. In

this case, the system throughput cannot grow as freely as the fully sharded blockchain

scenario. Comparing the results obtained from the two introduced sharding scenarios,

we conclude that the extent of sharding in different domains plays a signiﬁcant role in

scalability.

It is worth noting that there are different perspectives towards the scalability performance

metrics. Transaction throughput and transaction conﬁrmation latency are the two most talked-

about [2]. Nonetheless, in this report, we consider throughput as the performance metric for

blockchain scalability.

The rest of this report is organized as follows: In Section 2 we brieﬂy review important features

of a well-known asynchronous sharding scheme, Monoxide [9], as well as some of the state of the

art papers which beneﬁted from queueing concepts in their blockchain modeling and analysis.

We describe our system model in Section 3 which completely concentrates on a fully sharded

blockchain. We then propose an analytical model based on a queueing network in Section 4 that

is able to capture the behavior and characteristics of our system. This model is restricted to the

case with single-destination TXs. The extension to the case with multi-destination TXs is presented

in Section 5. For both cases in Sections 4 and 5 we derive the maximum stable throughput. We

then introduce the computation sharding scenario and the required changes to be made to our

original fully sharded model to derive its throughput in Section 6. Some numerical evaluations

are given in Section 7 and ﬁnally, this report is concluded in Section 8.

2 LITERATURE REVIEW

There are many rich proposals in the ﬁeld of blockchain sharding [1], [6], [7], [9], [10]. Monoxide

[9] is the ﬁrst asynchronous sharding scheme proposed and it is quite well known. Hence, we

conﬁne ourselves to review the key concepts of this proposal here, since it is the most similar

to our line of work. Interested readers can refer to [4], [5] for more in-depth information about

sharding schemes.

Monoxide partitions demands based on their issuer’s account address. Hence, each shard is

responsible for providing service for a speciﬁc set of addresses (accounts) assigned to it. Shards

then make use of Chu-ko-nu mining, a proof of work (PoW) variant, which further helps the

system to handle the shard takeover problem [9]. Chu-ko-nu mining allows miners to use a

single PoW solution to create multiple blocks at different shards simultaneously (a.k.a. block

batching). Consequently, miner’s mining power is ampliﬁed (multiplied) by the number of shards

a miner participates in. Fortunately, this rule doesn’t apply to attackers targeting a single speciﬁc

shard, since Chu-ko-nu does not allow more than one block per-shard with each PoW solution.

Hence, even though total hash power is divided by the number of shards, taking over a shard

could become as hard as its non-sharded counterpart if the average number of shards miners

participate in, approaches the total number of shards.

Monoxide follows a lock-free scheme for handling cross-shard TXs which relies on receipts

(RXs). Monoxide proposes eventual atomicity where a single cross-shard TX is decoupled into

an originated TX in the local shard, and a relay TX (a.k.a. receipt) being put into the outbound

transaction set. Though, this scheme leads to higher utilization and throughput, with eventual

atomicity, the consequence of fork resolution in one shard may affect the validity of relay TXs

forwarded and conﬁrmed in another shard. Therefore, the relay TX cannot be committed in

destination shard until its initiative TX is placed in enough depth of the originating shard chain,

incurring additional delay for cross-shard transactions.

Unlike sharding, literature on using queueing theory in analyzing blockchain characteristics is

not as plentiful as it could be. Still, some inspiring line of research can be found in the literature.

In [11], the authors modeled the Bitcoin blockchain via a single server queue with batch service

departure. Their ultimate goal was to derive the transaction conﬁrmation time which is the time

since the TX is issued and the time it has become part of a block. TXs arrive according to a

Poisson process and service time interval in their model is general. Nevertheless, there were

some deviations between their obtained results and reports from Bitcoin performance. They

later addressed this issue in [12] by considering exponential-type distributions for service time

intervals. Consequently, they were able to estimate the mean transaction-conﬁrmation time more

accurately. To capture the effect of Bitcoin fees on TX conﬁrmation times, the authors in [13]

proposed a priority queueing model with batch departures for the block production process. As

the highlight of their work, they then managed to show that increasing the block size is not a

fundamental solution for the scalability problem.

To better ﬁt the real world scenario, the authors in [14] proposed a model for mining process

in Bitcoin using two queues, i.e., block-generation and blockchain-building queues. Speciﬁcally,

they decomposed service time into two different exponential service stages of mining process and

network latency. This model further simpliﬁed the computations. Using this method, they derived

the average number of TXs in each queue, the average number of TXs in a block, and the average

TX conﬁrmation time under system stable condition. The authors in [15] modeled each node in

the network as a queue to capture the impact of many criteria such as node connectivity and block

size on the data delivery protocols used in blockchains. They further investigated many aspects of

forks in blockchains like forking probability and the duration of the ledger inconsistency period.

3 SYSTEM MODEL

We consider a generic pre-conﬁgured sharding mechanism to analyze its characteristics and

behavior. The details about how shards are formed or how nodes are moved between them

through time is out of the scope of this report. We just need them to be working continuously

and securely. In our model, Nakamoto consensus family is used for intra-shard consensus, and

similar to many works (e.g., [12], [14], [16]), PoW block production time is considered to be an

exponential distribution. Hence, the resulting shards operate asynchronously with respect to one

another. Nonetheless, as long as the objective is system throughput, the results also apply to

the synchronous conﬁgurations as well. In this setup, we use the words “miners” and “nodes”,

interchangeably, for full nodes participating in the consensus process. We assume all miners are

honest and do not deviate from the system protocol.

We consider an account-based sharding where jobs are assigned to a speciﬁc shard based on

the address of their senders. In other words, each shard is responsible for giving service to a

speciﬁc set of addresses assigned to it. TXs are then distributed uniformly among shards. We

assume that the issued TXs arrive at different shards as independent Poisson processes. Upon

arrival, they are ﬁrst broadcast throughout the corresponding shard network, which are then

added to the shard miners’ memory pool (mempool) upon validation. Each TX offers a fee in

order to be added to a block by miners, which can further specify its quality of service (QoS) in

terms of delay. We assume fees are such that they give enough incentives to all miners present

in a shard to produce blocks even in the least populated mempools. Miners will then collect fees

from TXs forming the block they had just mined and inform other participants in their shard

network of the new state.

We consider a fully sharded blockchain, where each shard has its own set of distinct min-

ers. Each node mines only in one shard where also its relaying and storage responsibilities

are restricted to that one shard. In other words, each miner mines, relays and stores only the

information that are assigned to its exclusive shard. We consider nodes with rather the same

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

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

10 玖币 0人已下载

立即下载

摘要：

1TechnicalReportAnalyticalModelingandThroughputComputationofBlockchainShardingPouryaSoltaniandFaridAshtianiAbstractShardinghasshowngreatpotentialtoscaleoutblockchains.Itdividesnodesintosmallergroupswhichallowforpartialtransactionprocessing,relayingandstorage.Hence,insteadofrunningoneblockchain,wewil...

展开>> 收起<<

1 Technical Report Analytical Modeling and Throughput.pdf

共36页,预览5页

还剩页未读，继续阅读

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

1 Technical Report Analytical Modeling and Throughput

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: