# MetaShard: A Novel Sharding Blockchain Platform for Metaverse Applications

Cong T. Nguyen, Dinh Thai Hoang, Diep N. Nguyen, Yong Xiao, Dusit Niyato, and
Eryk Dutkiewicz Preliminary results of this work have been reported at the
IEEE 95th Vehicular Technology Conference (VTC2022-Spring), Helsinki, Finland.
[1]. Cong T. Nguyen, Diep N. Nguyen, Dinh Thai Hoang, and Eryk Dutkiewicz are
with the School of Electrical and Data Engineering, University of Technology
Sydney, Australia. E-mail<EMAIL_ADDRESS>and {diep.nguyen,
hoang.dinh<EMAIL_ADDRESS>Yong Xiao is with the School of
Electronic Information and Communications at the Huazhong University of
Science and Technology, Wuhan 430074, China, also with the Peng Cheng
Laboratory, Shenzhen, Guangdong 518055, China, and also with the Pazhou
Laboratory (Huangpu), Guangzhou, Guangdong 510555, China (e-mail:
yongxiao@hust.edu.cn). Dusit Niyato is with the Nanyang Technological
University, Singapore 639798 (e-mail:DNIYATO@ntu.edu.sg).

###### Abstract

Due to its security, transparency, and flexibility in verifying virtual
assets, blockchain has been identified as one of the key technologies for
Metaverse. Unfortunately, blockchain-based Metaverse faces serious challenges
such as massive resource demands, scalability, and security/privacy concerns.
To address these issues, this paper proposes a novel sharding-based blockchain
framework, namely MetaShard, for Metaverse applications. Particularly, we
first develop an effective consensus mechanism, namely Proof-of-Engagement,
that can incentivize MUs’ data and computing resource contribution. Moreover,
to improve the scalability of MetaShard, we propose an innovative sharding
management scheme to maximize the network’s throughput while protecting the
shards from 51% attacks. Since the optimization problem is NP-complete, we
develop a hybrid approach that decomposes the problem (using the binary search
method) into sub-problems that can be solved effectively by the Lagrangian
method. As a result, the proposed approach can obtain solutions in polynomial
time, thereby enabling flexible shard reconfiguration and reducing the risk of
corruption from the adversary. Extensive numerical experiments show that,
compared to the state-of-the-art commercial solvers, our proposed approach can
achieve up to 66.6% higher throughput in less than 1/30 running time.
Moreover, the proposed approach can achieve global optimal solutions in most
experiments.

###### Index Terms:

Blockchain, Metaverse, sharding, 51% attacks, security.

##  1 Introduction

Being considered as the future of Internet applications, Metaverse has
recently attracted massive attention from both the industry and academia.
Metaverse is commonly referred to as virtual 3D environments where humans,
represented by their digital avatars, can take part in a wide range of
activities such as meetings, education, gaming, and so on. Compared to
traditional 3D virtual worlds, Metaverse offers users the unique ability to
seamlessly move between different virtual worlds with their avatars to enjoy a
wide range of services, thereby enabling much greater immersive experiences
and user freedom [2, 3, 4, 5]. With promising potential, Metaverse has
attracted huge investments, e.g., from Meta (Facebook), Roblox [6], Adidas
[7], and Microsoft [8]. As a result, it is expected that Metaverse
applications will become an increasingly important part of the future Internet
and rival traditional Internet applications.

However, the development of Metaverse applications has been facing several
novel challenges. First, since Metaverse applications are expected to serve
hundreds of millions of Metaverse users (MUs), the demands for communication
and computing resources may exceed the capacity of existing digital
infrastructure, e.g., 100 times more demanding in terms of computing resources
[9]. Moreover, high interoperability among different applications is necessary
to allow MUs to seamlessly move between different virtual worlds. Furthermore,
ensuring security and privacy for MUs in such a complex environment is a
challenging task for Metaverse Service Providers (MSPs) [2, 3, 4, 5].

To address those challenges, blockchain technology has been identified as one
of the key technologies for Metaverse [2, 3, 4]. Particularly, blockchain
technology enables a decentralized platform to securely store and manage data
and complex interactions in the Metaverse. For example, with the ability to
ensure data integrity, blockchain can be utilized to verify and authenticate
MUs’ identities, digital assets, and transactions. Moreover, due to its
decentralized nature, blockchain can avoid single-point-of-failure, alleviate
the heavy burden on central servers, as well as utilize resources from
millions of MUs. Furthermore, blockchain can help to improve MUs’ privacy,
while maintaining a high level of transparency and trust for MUs.

Despite its undeniable role in the development of Metaverse, blockchain
technology has several limitations. In particular, traditional blockchain
solutions based on Proof-of-Work (PoW), are usually very slow in processing
with high-demand of computing resource [10, 11], which makes them unsuitable
for Metaverse applications. Unfortunately, Metaverse applications may require
high levels of scalability to support a huge number of MUs and transactions,
which is beyond the capacity of conventional blockchain technology [10, 11].
Furthermore, interoperability is another critical issue that blockchain
technology is facing. Specifically, different blockchain networks and
protocols are often incompatible with each other, making it difficult for them
to exchange data and information [13].

Several recent efforts have been made to address those challenges.
Particularly, recent blockchain networks have been employing the Proof-of-
Stake (PoS) consensus mechanism which replaces the compute-intensive puzzle-
solving process of PoW with the stake ownership requirement. As a result, PoS
has higher transaction processing capabilities while consuming negligible
computing resources, compared to the PoW-based consensus mechanisms [10, 11,
12]. However, despite its outstanding benefits, conventional PoS consensus
mechanisms’ transaction processing capabilities are still inadequate to meet
the huge demands of Metaverse applications. To address this issue and improve
the scalability of the solution, sharding mechanism [28, 29] has been recently
developed to divide the blockchain network into multiple sub-networks
(shards). Each shard can process transactions independently and in parallel to
other shards, thereby significantly improving the transaction processing
speed. There are, however, trade-offs between security and speed, i.e., the
more shards a network is divided into, the less secure the network becomes.
Particularly, dividing the blockchain into multiple shards makes it easier for
the adversary to conduct 51% attacks [34]. For example, if a PoS-based
blockchain network is divided into 10 shards, the adversary might only need 6%
of the network total stakes (coins) to successfully perform a 51% attack,
whereas it will need at least 51% of stakes if there is no shard in the
network. Therefore, it is crucial to determine the number of shards as well as
the MU allocation in each shard to ensure that the adversary cannot attack any
shard in the network. Unfortunately, this problem has not been well
investigated in the literature (as discussed in more detail in Section 2).
Furthermore, these approaches, e.g., PoS and sharding, cannot address the
massive resource demands of Metaverse applications. Therefore, an intelligent
blockchain framework that can address these challenges and at the same time
meet the high resource demands of Metaverse is in urgent need.

Motivated by the above, we develop MetaShard, a novel sharding-based
blockchain framework that can not only leverage MUs resources contributions to
alleviate the burdens on the MSP but also improve scalability while ensuring
the security of the whole system. To this end, we first develop an innovative
consensus mechanism, namely Proof-of-Engagement (PoE), that can incentivize
MUs to participate in the consensus process and contribute computing resources
and/or collected IoT data to the Metaverse applications. Based on their
engagement (determined by their contributions and assets), MUs can be rewarded
with blockchain tokens via the block reward. As a result, PoE can utilize MUs
resources to alleviate the huge resources burden for MSP and create a more
engaged MUs community. Moreover, to improve scalability, we propose a sharding
management scheme to divide the network into multiple shards to enable
parallel transaction processing, thereby significantly improving the network
throughput. Furthermore, to protect the shards from 51% attack, we formulate
an optimization problem to find the optimal number of shards and MUs
allocation, thereby maximizing the network throughput while ensuring that the
risk of attacks in individual shards is minimal. Since the problem is NP-
complete, we develop a hybrid approach that first decomposes the problem using
binary search and then solves the relaxed sub-problems using Lagrange
multipliers. As a result, the proposed approach can quickly obtain solutions,
improve the network performance, and at the same time enhance security
compared to those of state-of-the- art solvers. The main contributions of this
paper can be summarized as follows:

  * •

We propose MetaShard, a novel sharding blockchain framework for Metaverse
applications that not only leverage MUs’ resources and data for Metaverse
applications but also enhance network throughput.

  * •

We develop PoE, a new consensus mechanism that can incentivize MUs’ data and
computing resources contribution via the block rewards, thereby alleviating
the massive resource demands and incentivizing MUs to be more engaged in the
Metaverse.

  * •

We propose a sharding management scheme to improve the scalability of
MetaShard. Specifically, we first formulate an optimization problem to
maximize the network throughput while protecting the shards from 51% attacks.
We then develop a lightweight hybrid approach to quickly obtain solutions,
thereby allowing flexible shard reconfiguration.

  * •

We conduct extensive simulations to evaluate the performance of our proposed
approach. The results show that, compared to the state-of-the-art commercial
solvers, our proposed approach can achieve up to 66.6% higher throughput in
less than 1/30 running time. Moreover, the proposed approach can achieve
global optimal solutions in most experiments. Furthermore, we study the
impacts of key parameters on the performance of the system and show that the
proposed approach can further improve the robustness of the system.

The rest of the paper is organized as follows. The related work is discussed
in Section 2. Section 3 presents MetaShard’s system overview. The proposed PoE
consensus mechanism and sharding management scheme are presented in detail in
Section 4. Section 5 presents the sharding management problem and our proposed
lightweight approach. Finally, Section 6 shows the system performance and
Section 7 concludes the paper.

##  2 Related Work

###  2.1 Blockchain for Metaverse

As Metaverse is an emerging topic, applications of blockchain in Metaverse are
still very limited. There are just a few recent works [14, 16, 15] focusing on
this topic. Specifically, in [14], the authors propose a blockchain-based
secure mutual authentication scheme for Metaverse environments. In this
approach, the MUs need to send their pseudo-identity, personal information,
and public key to a central authority to verify. If the verification is
successful, the central authority stores the MUs’ identities and public keys
in a public blockchain for Metaverse applications to query. Similarly, the
authors in [15] develop a blockchain-based framework for Metaverse to manage
MUs’ identities and transactions. Particularly, the proposed framework is
composed of four parts, namely New User Engine, Transaction Centre,
Authenticator Engine, and Repo. In this framework, the New User Engine is
responsible to provide new MUs with blockchain addresses. MUs can then send
their transactions to the Transaction Centre to process, and the Authenticator
Engine’s responsibility is to validate the MUs’ identities and transactions.
If the transaction is successfully validated, it will be recorded in the Repo
(which is a distributed ledger) along with the resulting change in MUs’
accounts. In [16], the authors propose a blockchain-enabled framework for
Metaverse service management. Particularly, in the proposed framework, the
mobile network operators can offer their services to MUs with different
service level agreements and prices. The MUs can then choose one of the
options based on a proposed utility function with a trade-off between service
quality and prices. In this framework, the blockchain serves as a platform to
verify MUs’ identities, and the blockchain tokens are used as the currency for
payment.

From the above, we can observe that [14, 16, 15] only utilize conventional
blockchain technology for managing MUs identities and transactions without
taking into account specific challenges of Metaverse, such as the huge
resource demand or the associated scalability issues. To the best of our
knowledge, our proposed MetaShard framework is the first in the literature
that can encourage MUs to contribute resources to the Metaverse and blockchain
network as well as address the scalability issue of blockchain.

###  2.2 Sharding in Blockchain

In [17], the authors propose a sharding protocol for public blockchain
networks. Although the protocol is proven to be secure, it utilizes PoW to
authenticate the consensus participants’ identities. Another PoW-based
sharding scheme is proposed in [18], where nodes with high computing power in
the system can participate in several shards simultaneously. Similar to [17],
this scheme requires consensus participants to solve a PoW puzzle to become
validators, and shards’ security is proven based solely on the number of
consensus participants. However, since the consensus participants are required
to solve a PoW puzzle, the adversary can split their computing power to
simultaneously solve different puzzles and thus able to gain more slots. As a
result, the computing power distribution needs to be taken into account, but
it is not discussed in [17] and [18]. Another PoW-based sharding scheme is
proposed in [19]. Although the scheme’s security is proven, it relies on PoW,
which is unsuitable for Metaverse due to the high delay and huge energy
consumption.

To address the limitations of PoW, other sharding protocols were developed
with energy-saving alternative ways to select consensus participants. For
example, in [20], a sharding protocol is developed based on Byzantine Fault
Tolerance (BFT) and Trusted Execution Environment (TEE). Particularly, the
consensus participants need a special type of hardware to ensure the TEE. A
similar approach that relies on TEE is proposed in [21]. Particularly, a
sharding scheme is developed that utilizes two separate blockchains to
decouple the transaction recording and consensus processes. Similar to [20],
the proposed scheme relies on TEE, and thus it also requires special hardware
to participate in the consensus process. Although the schemes in [20] and [21]
can enhance the security of the network, the hardware requirement makes them
much less attractive to public users, especially MUs who already need a lot of
computing power for AR/VR rendering. In [22], the authors develop a sharding
scheme based on Practical Byzantine Fault Tolerance (PBFT). Although the
security of the protocol is proven, how to select the consensus participants
is not discussed. Moreover, similar to [17], this protocol relies on the
number of consensus participants, without taking into account the ability of
the adversary to create many identities to gain more consensus participants
slots. In [23], a reputation-based sharding scheme is developed. Particularly,
the consensus participants are selected based on their reputation scores
stored in a separate blockchain. Then, the selected consensus participants
execute a BFT-based protocol for each shard’s consensus process. However, the
adversary in this case can also create many identities to increase the number
of consensus participants it controls, as the reputation is based solely on
previous behaviors. In [24], a BFT-based sharding protocol is developed.
However, similar to [17] and [23], the protocol relies on the number of
consensus participants, which can be adversely impacted by the adversary. In
[25], a dynamic sharding protocol is proposed in which the consensus
participants are selected via smart contracts. Moreover, to mitigate Sybil
attacks, the proposed protocol requires that each consensus participant must
come from a different IP address. Nevertheless, this still cannot prevent the
adversary from influencing the selection process, as IP addresses can be fake.

From the abovementioned approaches, we can observe that they rely on the PoW
consensus mechanism which is inappropriate for Metaverse due to the huge
energy consumption and large delay. In contrast, our proposed PoE consensus
mechanism is much more energy-efficient. Moreover, the security of these
approaches relies on the number of consensus participants without considering
that this number can be unfairly affected by the adversary. On the contrary,
our proposed approach considers the MUs’ engagement instead of the number of
participants, thereby enhancing the security and robustness of the system
against Sybil attacks.

##  3 System Overview

###  3.1 System Overview

Figure 1: An illustration of the proposed system.

Fig. 1 illustrates an overview of the proposed MetaShard framework. In this
framework, there is an MSP operating a Metaverse running multiple Metaverse
applications. Each Metaverse application is a self-contained environment that
offers a wide range of services and experiences, e.g., virtual office, virtual
concerts, gaming, and virtual tourism, for MUs. Compared to traditional
virtual applications, the core difference here is that applications in the
Metaverse are fully interconnected, allowing the MUs to freely and seamlessly
move between different applications, e.g., Meta Horizon Worlds [26]. The MUs
also have various interactions with each other and the MSP, such as exchanging
assets, purchasing services and items, contributing resources, and
participating in the blockchain’s consensus process. A blockchain-based system
can be applied to record and facilitate those interactions.

###  3.2 Metaverse Users (MUs) and Metaverse Service Provider (MSP)

An MU is a user that can join and use different Metaverse applications and
services provided by the MSP. The MUs have unique avatars that represent them
in the Metaverse, allowing them to interact with each other as well as the
virtual worlds. There can be various interactions among the MUs, as well as
between the MUs and the MSP. First, the MUs can easily exchange digital
assets, such as Metaverse tokens and virtual items, with each other using
blockchain transactions. For example, MUs who purchased virtual concert
tickets (but could not attend) can sell their tickets to others. All these
digital assets and transactions can be verified and stored in the blockchain,
providing a secure transparent way to manage assets without the need for a
central authority.

Moreover, the MUs can pay the MSP to gain access to services or buy digital
items. This process can be automated by smart contracts, i.e., a user-defined
program that can be automatically executed when the conditions within are met
[27]. For example, the MSP can broadcast its virtual meeting options, e.g.,
duration, number of people, and fees, by publishing a smart contract on the
blockchain. Then, MUs who want to purchase this service can send a transaction
that contains the specified options to the smart contract. After the
transaction is validated, the smart contract can automatically send the MU a
transaction that contains a proof for the purchase. When the MU requests to
enter the virtual meeting room, the Metaverse application can query the
blockchain to verify the proof and grant the involved MUs access to the room.

Furthermore, in our proposed MetaShard, MUs can also contribute data or
computing resources to Metaverse applications. For example, in Metaverse
virtual tourism applications, the MSP needs up-to-date 3D image/video data
from tourist attractions to provide more immersive experiences to MUs. In this
scenario, the MSP can encourage MUs who live near the tourist attraction to
contribute the data, thereby saving costs and increasing MUs’ engagement.
Moreover, in compute-intensive AR/VR applications, the MSP can incentivize MUs
to execute the rendering locally instead of offloading to the MSP’s servers.
Additionally, the MSP can offload computing tasks to MUs with idle resources
to alleviate the heavy burden on the edge/cloud servers. For those
contributions, MUs can be rewarded with digital assets such as Metaverse items
or tokens. This can help to encourage more MUs to participate in the Metaverse
and alleviate the high resource demands of Metaverse applications. Similarly,
smart contracts can be utilized to provide a transparent and trusted way to
reward the MUs for their contributions because the conditions written within a
smart contract are visible to everyone. For example, the MSP can publish a
smart contract that specifies the payment for different amounts of data
contributed. When the MUs send the data to the smart contract, they can be
automatically paid for their data.

###  3.3 Blockchain and Sharding

In MetaShard, the blockchain serves as a platform to store and manage MUs and
applications data, interactions, and assets. Blockchain enables the MUs and
the MSP to manage their identities, avatars, and digital assets in a
decentralized manner, thereby significantly enhancing transparency and trust
for MUs. Moreover, smart contracts can automate and facilitate various
interactions among MUs and applications. Furthermore, the blockchain can also
provide a transparent way to manage and reward MUs’ data and computing
resources contribution, thereby creating a more engaged and motivated MUs
community. However, managing such a huge amount of data and interactions for
many MUs requires very high transaction processing capabilities, which
conventional blockchain technology cannot handle. Particularly, most current
blockchain networks are still employing the PoW consensus mechanism which
consumes a huge amount of energy and has very low processing capability.

Therefore, we propose a PoS-based consensus mechanism for MetaShard. With PoS,
the energy consumption is negligible, and the transaction processing
capability can be significantly improved. Moreover, different from the
conventional PoS that only considers the user assets (stakes), we develop a
PoE consensus mechanism that will also take into account MUs’ data and
resources contribution and reward MUs for their engagement. In this way, PoE
can not only leverage MUs’ resources to alleviate the massive resource demands
for the MSP but also encourage more MUs to join the Metaverse for the rewards,
thereby creating a more engaged MUs community. This PoE consensus mechanism
will be discussed in detail in Section 4. Moreover, scalability is a major
constraint that hinders the applicability of conventional blockchain
technology for Metaverse applications with a huge number of MUs. Therefore, we
propose to employ the sharding mechanism [28, 29] for MetaShard. With
sharding, the blockchain network can be divided into multiple smaller networks
that allow the parallel processing of transactions and smart contracts,
thereby improving scalability and processing speed and reducing the workload
on individual consensus nodes. Furthermore, each Metaverse application can be
adaptively allocated a different number of shards according to their
processing demands. For example, we can allocate more shards to virtual office
applications during working hours and more shards to virtual concert
applications at night.

Although dividing a blockchain into shards can significantly enhance the
network throughput (in terms of the number of transactions successfully
verified and processed per time unit), it also causes some potential risks for
network security as shown in [28, 29]. Particularly, the security of a
blockchain network depends on the honest majority. For example, if the
adversary can control the majority (51%) of stakes in PoS, it can successfully
perform various attacks, such as double-spending and transaction denial
attacks [10, 11, 12], on the network. However, if the stakes are not allocated
properly into the shards, then the adversary may not need too many stakes to
successfully attack a shard. Therefore, it is crucial to determine the proper
number of shards and MUs allocation such that the security of the whole
network is still ensured. To this end, in Section 5, we will formulate this
sharding management optimization problem and propose an efficient approach to
quickly obtain solutions, thereby significantly improving the network
performance and security.

##  4 Proposed PoE Consensus Mechanism and Sharding

###  4.1 Epoch and Time Slots

Figure 2: An illustration of the proposed sharding management and election
processes.

In our proposed PoE consensus mechanism, time is divided into epochs. Each
epoch is then divided into time slots. During epoch $e_{k}$, our proposed
sharding management process is executed to determine the number of shards and
MUs allocation for epoch $e_{k+1}$, as illustrated in Fig. 2. Note that
frequent and dynamic adjustment of the number of shards can be beneficial for
the system, e.g., adding more shards to address the varying transaction
processing demands or closing shards to reduce unnecessary communication [30].
This sharding management process is run once for each epoch, which is
beneficial for network security [28, 29]. Moreover, it is also more desirable
for the MUs, e.g., an MU who contributes more in this epoch should have a
higher chance to be elected as a leader and earn block rewards (e.g., in
Metaverse tokens) in the next epoch.

Moreover, during the epoch, the committee members (selected from MUs who
participate in the consensus process) of each shard execute the Publicly
Verifiable Secret Sharing (PVSS) protocol [31] to create random seeds. The
PVSS protocol is guaranteed to produce unbiased random strings, and it allows
network participants to verify those strings, as long as 51% of the protocol
participants are honest [31]. Therefore, the PVSS protocol can be employed to
create publicly verifiable random seeds. At the beginning of each epoch, these
random seeds, along with the number of shards and MUs allocation, are then
used as the input of a hash function, e.g., Follow-the-Satoshi (FTS) algorithm
[12], to choose the leaders for the current epoch and committee members for
the next epoch. If the numbers of shards of two epochs are different, the
random seeds can be used to determine which shard will create more (or fewer)
random seeds. For example, if there is one more shard in the next epoch, then
a random shard in this epoch will create two seeds instead of one.

###  4.2 MU Engagement and Reward

In MetaShard, MUs are incentivized to contribute data and computing resources.
To reward this contribution, MUs are given contribution scores that are stored
in the blockchain. These scores are then used along with the MUs assets, e.g.,
Metaverse items and tokens, to determine the MUs’ total engagement scores.
Particularly, each MU has a data contribution score $D_{n}$, a computing
resource contribution score $C_{n}$, and an amount of Metaverse tokens
$T_{n}$. The data and computing resource score rewarded to the MUs can be
determined by the MSP, e.g., based on the amount or frequency of resources and
data contribution [32, 33]. The total engagement score of MU $n$ can be
calculated by

$\eta_{n}=\alpha_{D}D_{n}+\alpha_{C}C_{n}+\alpha_{T}T_{n},$ (1)

where $\alpha_{D},\alpha_{C}$, and $\alpha_{D}$ are the weight factors for
data contribution, computing resources contribution, and Metaverse token,
respectively. These weight factors are determined by the MSP, and they can
also reflect the MSP’s priority. For example, if the MSP needs more computing
resource contribution, it can set $\alpha_{C}$ higher than $\alpha_{T}$ and
$\alpha_{D}$.

Every MU can choose to participate in the consensus processes to be able to
earn the block rewards. Since each shard runs its own consensus process, the
probability that MU $n$ is selected to be the leader of shard $s$ is given by:

$\rm{Pr}^{s}_{n}=\dfrac{\eta_{n}^{s}}{\sum_{i=1}^{N}\eta_{i}^{s}}.$ (2)

Besides the benefits of MUs’ resource contribution, our proposed leader
selection approach can also enhance the security of the network. The reason is
that MUs who are more engaged (with high contributions and own a lot of
assets) might want to protect the network more. Moreover, in existing
approaches such as [17, 24, 18, 21, 19, 22, 23, 25], the leader is not
selected based on stakes/scores (BFT-based approaches). Instead, these
approaches rely only on the number of validators. However, the adversary can
target those protocols by conducting Sybil attacks, i.e., creating multiple
accounts, to improve their chance of being selected as validators. In
contrast, the leaders are chosen based on their engagement in MetaShard, and
thus creating multiple accounts with no contributions or assets cannot
adversely affect the leader selection process.

###  4.3 Threat Model and Shard Security

Threat Model: In this work, we consider the type of adversary that tries to
gain the majority in any shard to conduct 51% attacks. Particularly, the
adversary possesses multiple accounts (adversarial MUs) in the system. These
accounts, along with the other MUs’ accounts, are allocated into different
shards in the system. If the total score of the adversary exceeds 51% of the
total score of any shard in the system, the adversary can successfully conduct
various attacks, such as double-spending and transaction denial attacks [10,
11, 12], and unfairly affect the seeds generation of the PVSS protocol.
Moreover, the adversary can corrupt honest MUs, but the corruption will take
effect after a period of time [19, 17, 24, 28]. When an MU is corrupted, it
will be controlled by the adversary, and its score will count toward the
adversary’s total score.

Given the above adversary model, there are two serious threats. First, when
the adversary controls more than 51% of a shard, the adversary can influence
the leader election process to conduct other types of attacks such as double-
spending and transaction denial attacks [10, 11, 12] on the shard.
Consequently, the Metaverse transactions might be reverted, or transactions
from specific MUs might be blocked by the adversary. Therefore, it is crucial
to allocate scores to each shard such that the adversary has a minimal chance
to attack every shard. However, a major challenge is that we do not know which
MU is adversarial, and thus we can only minimize the chance that the adversary
can control the majority of scores in any shard. Second, if the epoch is too
long, the adversary might be able to corrupt the honest MUs during the epoch
and successfully gain control of the shard. Therefore, the score allocation
needs to be regularly reconfigured, e.g., Ethereum’s epoch only lasts for 6.4
minutes [35].

To address these threats, we develop a sharding management approach to
determine the number of shards and allocate MUs scores such that the
adversary’s chance to successfully attack any shard is minimal, e.g., lower
than 0.1%. Moreover, the proposed approach can quickly obtain solutions,
thereby reducing the time for the adversary to corrupt honest MUs. The
proposed approach is presented in detail in the next section.

##  5 Sharding Management Problem and Solution

###  5.1 Problem Formulation

We first formulate the sharding management problem as follows. In the
considered system, there is a set $\mathcal{N}=(1,\ldots,N)$ of MUs. Since we
do not know which MU is adversarial, we can consider the total engagement
score of the adversary, denoted by $\eta^{A}_{s}$, to be a sum of independent
random variables. Let $p^{A}_{n}$ denote the probability that MU $n$ is
adversarial. $p^{A}_{n}$ can be determined based on the MUs’ assets and
contribution, i.e., MUs who owns more assets or contribute frequently to the
Metavese are less likely to be adversarial, or using Machine Learning
approaches such as those in [36, 37, 38]. The expected value of the total
engagement score of the adversary in shard $s$ can then be determined by:

$\mathbb{E}[\eta^{A}_{s}]=\mathbb{E}[\sum_{n=1}^{N}p^{A}\eta^{s}_{n}]=\sum_{n=1}^{N}p^{A}\eta^{s}_{n}.$
(3)

Since $\eta^{A}_{s}$ is a sum of independent random variables, we want to
determine the probability that $\eta^{A}_{s}$ exceeds 50% of the total
engagement scores in any shard, i.e., when the adversary gains the majority in
a shard. To find this probability, we apply the Hoeffding bound [42] to
determine the bounds on the tail distribution of $\eta^{A}_{s}$ .
Particularly, let $\theta_{s}=\sum_{n=1}^{N}\eta^{s}_{n}$ denote the total
engagement score of all MUs (including the adversary) in shard $s$. Based on
(3), the probability that the adversary’s score exceeds 50% of the total
scores in shard $s$ can be determined by:

$\begin{split}\textrm{Pr}[\eta^{A}_{s}\geq
0.5\theta_{s}]&=\textrm{Pr}[\eta^{A}_{s}\geq\mathbb{E}[\eta^{A}_{s}]+t]\leq\textrm{exp}\big{(}\dfrac{-2t^{2}}{\sum_{n=1}^{N}(\eta_{n}^{s})^{2}}\big{)}\end{split}$
(4)

where $t$ denotes the deviation from the expected value of $\eta^{A}_{s}$ such
that the adversary can gain majority in the shard, i.e., $\eta^{A}_{s}\geq
0.5\theta_{s}$. This deviation can be determined by:

$\begin{split}0.5\theta_{s}=\mathbb{E}[\eta^{A}_{s}]+t,\\\
\sum_{n=1}^{N}0.5\eta^{s}_{n}=t+\sum_{n=1}^{N}p^{A}_{n}\eta^{s}_{n},\\\
t=\sum_{n=1}^{N}(0.5-p^{A}_{n})\eta^{s}_{n}.\end{split}$ (5)

The inequality in (4) comes from Hoeffding bound [42]. To keep the probability
in (4) lower than a certain safety threshold $\tau$ (e.g., $\tau=0.001$), we
have

$\begin{split}\text{exp}(\dfrac{-2t^{2}}{\sum_{n=1}^{N}(\eta_{n}^{s})^{2}})\leq\tau,\\\
-2\dfrac{\bigg{(}\sum_{n=1}^{N}(0.5-p^{A}_{n})\eta^{s}_{n}\bigg{)}^{2}}{\sum_{n=1}^{N}(\eta_{n}^{s})^{2}}\leq\ln(\tau),\\\
(\sum_{n=1}^{N}(0.5-p^{A}_{n})\eta^{s}_{n})^{2}\geq-0.5\ln(\tau)\sum_{n=1}^{N}(\eta_{n}^{s})^{2}.\\\
\end{split}$ (6)

This means that to make all the shards to be secured, we need to allocate the
scores $\eta_{n}^{s}$ of the MUs in each shard such that they satisfy (6). Let
$S$ denote the maximum possible number of shards111In theory, we do not have
the maximum possible number of shards, e.g., an MU can participate in many
shards. However, in practice, this number cannot be unlimited because an MU
does not want to participate in too many shards (same rewards but needs much
more computational and communication resources).. We formulate the optimal
sharding management problem (P1) below.

$\displaystyle(\textbf{P1})$
$\displaystyle\max_{\boldsymbol{\eta},\mathbf{x},\varsigma}T\varsigma$ (7)
s.t. $\displaystyle\hskip
5.0pt(\sum_{n=1}^{N}(0.5-p^{A}_{n})\eta^{s}_{n})^{2}\geq-0.5x_{s}\ln(\tau)\sum_{n=1}^{N}(\eta_{n}^{s})^{2},$
$\displaystyle\hskip 140.00021pt\forall s=1,\ldots,S$ (8) $\displaystyle
x_{s}\geq\dfrac{\varsigma-s+1}{S},\hskip 75.0001pt\forall s=1,\ldots,S$ (9)
$\displaystyle x_{s}\leq\varsigma-s+1,\hskip 75.0001pt\forall s=1,\ldots,S$
(10) $\displaystyle\sum_{s=1}^{S}\eta_{n}^{s}=\eta_{n},\hskip
85.00012pt\forall n\in\mathcal{N}.$ (11)

In (P1), the objective (7) is to maximize the total network throughput, which
can be obtained by multiplying the number of shards $\varsigma$ with the
maximum number of transactions that a shard can process per second $T$.
Constraints (8) follow (6). Note that out of these $S$ constraints, only
$\varsigma$ constraints are active to ensure the security for $\varsigma$
shards, while the constraints for the other (dummy) shards need to be
inactive. To this end, we use auxiliary decision variables $\mathbf{x}$ to
make the constraints active for the shards from 1 to $\varsigma$, and inactive
for the other shards. Particularly, constraints (9) and (10) ensure that
$x_{s}=1,\forall s=1,\ldots,\varsigma$, while $x_{s}=0,\forall
s=\varsigma,\ldots,S$. Then, for shards from 1 to $\varsigma$, the right-hand-
side of constraints (8) become
$-0.5x_{s}\ln(\tau)\sum_{n=1}^{N}(\eta_{n}^{s})^{2}$ (active). For shards from
$\varsigma+1$ to $S$, the right-hand-side of constraints (8) become zero, and
thus they are always satisfied (inactive). Finally, constraints (11) ensure
that the MUs scores are fully allocated. The reason for these constraints is
that the MUs’ rewards for consensus participation are proportional to their
engagement scores, and thus the MUs will want to use all their scores for
consensus participation.

From (8), we can observe that (P1) is a Mixed Integer Non-linear Programming
(MINLP) problem [39, 40] which is NP-complete [43]. As later shown in Section
6, commercial solvers such as CPLEX [40] can only solve instances of (P1) with
a small number of shards. For larger values of $S$, it becomes intractable and
infeasible to obtain optimal solutions. However, the score allocation needs to
be regularly reconfigured, e.g., Ethereum’s epoch only lasts for 6.4 minutes
[35]. Such frequent shard reconfiguration can bring various benefits. First,
the MUs who contribute more resources in one epoch can have their scores
updated earlier to earn more rewards in the next epoch. Moreover, if the epoch
is short, the adversary will have less time to corrupt the honest MUs.

###  5.2 Proposed Hybrid Algorithm

####  5.2.1 Problem decomposition and the proposed Lagrangian approach

To address the abovementioned problems, we develop a lightweight approach
based on Lagrange multipliers and binary search that can quickly obtain
solutions in a very short time, thereby enabling flexible scores reallocation
and improving the shards’ security. To that end, we first decompose (P1) into
multiple relaxed sub-problems (P2) as follows:

$\displaystyle(\textbf{P2})$ $\displaystyle\max_{\boldsymbol{\eta}}T\sigma$
(12) s.t. $\displaystyle\hskip
5.0pt\big{(}\sum_{n=1}^{N}(0.5-p^{A}_{n})\eta^{s}_{n}\big{)}^{2}\geq-0.5\ln(\tau)\sum_{n=1}^{N}(\eta_{n}^{s})^{2},$
$\displaystyle\hskip 140.00021pt\forall s=1,\ldots,\sigma$ (13)
$\displaystyle\sum_{s=1}^{\sigma}\eta_{n}^{s}=\eta_{n},\hskip
85.00012pt\forall n\in\mathcal{N}$ (14)

Particularly, in (P2), we fix the value of $\varsigma=\sigma$. In this way, we
do not need to determine $\varsigma$ and $\mathbf{x}$, and thus constraints
(8) become constraints (13). Moreover, constraints (9) and (10) can be
omitted. Furthermore, the objective function (12) becomes a constant, and thus
we only need to find a feasible solution to (P2), instead of optimizing it. As
a result, (P2) becomes a Nonlinear Programming (NLP) problem, which is easier
to solve compared to MINLP problems [39, 40]. Then, we can solve (P2) for all
values of $\sigma=1,\ldots,S$, and the largest value of $\sigma$ for which we
can find a feasible solution is the global optimal solution of (P1).
Nevertheless, (P2) is non-convex and nonlinear due to (13), and thus it still
requires exponential time to solve [41], as later shown in Section 6.

To address this limitation, we reformulate the optimization problem (P3) as
follows:

$\displaystyle(\textbf{P3})$
$\displaystyle\max_{\boldsymbol{\eta}}\sum_{s=1}^{\sigma}\bigg{(}\big{(}\sum_{n=1}^{N}(0.5-p^{A}_{n})\eta^{s}_{n}\big{)}^{2}+0.5\ln(\tau)\sum_{n=1}^{N}(\eta_{n}^{s})^{2}\bigg{)}$
(15) s.t. $\displaystyle\hskip
5.0pt\sum_{s=1}^{\sigma}\eta_{n}^{s}=\eta_{n},\hskip 85.00012pt\forall
n\in\mathcal{N}$ (16)

The core idea of (P3) is that, instead of finding feasible solutions that
satisfy (13) and (14), we try to maximize the left-hand-side of (13), subject
to (14). Then, we can check the optimal solution $\boldsymbol{\eta}^{\prime}$
obtained from (P3). Then, we adopt the Lagrange multipliers method to solve
(P3) as follow. We first define the Lagrange function:

$\begin{split}\mathcal{L}(\boldsymbol{\eta},\boldsymbol{\lambda})&=f(\boldsymbol{\eta})-\boldsymbol{\lambda}g(\boldsymbol{\eta}),\\\
&=\sum_{s=1}^{\sigma}\bigg{(}\big{(}\sum_{n=1}^{N}(0.5-p^{A}_{n})\eta^{s}_{n}\big{)}^{2}+0.5\ln(\tau)\sum_{n=1}^{N}(\eta_{n}^{s})^{2}\bigg{)}\\\
&-\sum_{j=1}^{N}\lambda_{j}\bigg{(}\sum_{s=1}^{\sigma}\eta_{n}^{s}-\eta_{n}\bigg{)}.\end{split}$
(17)

Then, we solve the following set of equations:

$\nabla_{\boldsymbol{\eta},\boldsymbol{\lambda}}\mathcal{L}(\boldsymbol{\eta},\boldsymbol{\lambda})=0,$
(18)

which is equivalent to

$\begin{split}\lambda_{k}+\ln({\tau})\sum_{n=1}^{N}(\eta_{n}^{s})+2p^{A}_{k}\sum_{n=1}^{N}(0.5-p^{A}_{n})\eta^{s}_{n}=0,\\\
\forall k\in\mathcal{N},\forall s=1,\ldots,\sigma,\\\
\sum_{s=1}^{\sigma}\eta_{n}^{s}-\eta_{n}=0,\forall
n\in\mathcal{N}.\end{split}$ (19)

Instead of solving the NLP problem (P2), we only need to solve (19) which is a
set of $(\sigma+1)N$ equations with $(\sigma+1)N$ variables. Moreover, in
(19), all the equations are linear, and thus it is a system of linear
equations. As a result, this system of equations can be solved effectively in
a very short period of time compared to (P2).

Finally, we implement Algorithm 1 which combines binary search and the
Lagrange multiplier method to obtain optimal solutions for the original
problem (P1). Particularly, Algorithm 1 first finds the optimal solution
$\boldsymbol{\eta}^{\prime}$ of (P3), using the system of equations in (19),
with $\sigma=S$. Then, if $\boldsymbol{\eta}^{\prime}$ satisfies (13), it is
the optimal solution of (P1). Otherwise, we apply binary search to speed up
the optimization process as illustrated in Fig. 3. Particularly, we first set
$high=S-1$, $low=2$, and $\sigma^{\prime}=(high+low)/2$. Then, we solve (19)
to find $\boldsymbol{\eta}^{\prime}$. Next, if $\boldsymbol{\eta}^{\prime}$
satisfies (13) (which means $\sigma$ is the best solution so far), we set
$high=S-1$, $low=\sigma$, and $\sigma^{\prime}=(high+low)/2$. Otherwise, we
set $high=\sigma$, $low=2$, and $\sigma^{\prime}=(high+low)/2$. In both cases,
the loop is repeated until $\sigma^{\prime}=high$. During the loop, the
algorithm records the best solution found (that can satisfy (13)) in
$\boldsymbol{\eta}^{*}$ and $\sigma^{*}$, and it will return
$\boldsymbol{\eta}^{*}$ when the loop ends. With $\boldsymbol{\eta}^{*}$ and
$\sigma^{*}$, $x^{*}$ can be straightforwardly deduced for the original
problem (P1) as shown in the proof of Theorem 1.

Algorithm 1 Proposed hybrid algorithm for (P1)

Input: Optimization problem (P1)
Output: $\boldsymbol{\eta}^{*}$

1:$\sigma\leftarrow S$.

2:Solve (19) to obtain $\boldsymbol{\eta}^{\prime}$

3:if $\boldsymbol{\eta}^{\prime}$ satisfies (13) then

4:
$\boldsymbol{\eta}^{*}\leftarrow\boldsymbol{\eta}^{\prime},\varsigma^{*}\leftarrow
S$, stop algorithm.

5:else

6: $high\leftarrow S-1,low\leftarrow 2\sigma^{\prime}\leftarrow(high+low)/2$

7: repeat

8: Solve (19) to obtain $\boldsymbol{\eta}^{\prime}$

9: if $\boldsymbol{\eta}^{\prime}$ satisfies (13) then

10: $low\leftarrow\sigma^{\prime}$, $\sigma^{\prime}\leftarrow(high+low)/2$

11:
$\varsigma^{*}=\sigma^{\prime},\boldsymbol{\eta}^{*}\leftarrow\boldsymbol{\eta}^{\prime}$

12: else

13: $high\leftarrow\sigma^{\prime}$, $\sigma^{\prime}\leftarrow(high+low)/2$

14: end if

15: until $\sigma^{\prime}=high$

16:end if

Figure 3: An illustration of Algorithm 1.

####  5.2.2 Optimality analysis

In Lemma 1, we first prove that the solution obtained from solving (19) is the
global optimal solution of (P3).

######  Lemma 1.

Let $\boldsymbol{\eta}^{\prime}$ denote a solution of (19).
$\boldsymbol{\eta}^{\prime}$ is also the global optimal solution of (P3).

###### Proof:

We will prove that $\boldsymbol{\eta}^{\prime}$ satisfies the
Karush–Kuhn–Tucker (KKT) conditions for non-convex optimization problems [41].
Moreover, since (15) and (16) are differentiable and satisfy linearity
constraint qualification, strong duality holds, and thus
$\boldsymbol{\eta}^{\prime}$ is the global optimal solution of (P3). Next, we
prove that $\boldsymbol{\eta}^{\prime}$ satisfies the KKT conditions as
follows. The first condition is:

$f_{i}(\boldsymbol{\eta}^{\prime})\leq 0.$ (20)

This condition is always satisfied since there is no inequality constraint
($f_{i}(\cdot)$) in (P3). The second condition is:

$h_{k}(\boldsymbol{\eta}^{\prime})=0=\sum_{s=1}^{\sigma}(\eta_{k}^{s})-\eta_{k},\forall
k\in\mathcal{N}.$ (21)

The second condition is always satisfied since it is included in (19). The
third condition is

$\lambda_{k}\geq 0,\forall k\in\mathcal{N}.$ (22)

From (19), we have

$\begin{split}\lambda_{k}&=-\ln({\tau})\sum_{n=1}^{N}(\eta_{n}^{s})-2p^{A}_{k}\sum_{n=1}^{N}(0.5-p^{A}_{n})\eta^{s}_{n},\\\
&=\big{(}-\ln({\tau})-p^{A}_{k})\big{)}\sum_{n=1}^{N}(\eta_{n}^{s})+2p^{A}_{k}\sum_{n=1}^{N}(\eta_{n}^{s}).\end{split}$
(23)

Since $\tau\leq 0.001$ and $p_{k}^{A}<1$, we have $\lambda_{k}>0$, and thus
the third condition is satisfied. The fourth condition is:

$\lambda_{k}h_{k}(\boldsymbol{\eta}^{\prime})=0.$ (24)

Similar to (21), this condition is always satisfied since there is no
inequality constraint in (P3). The fifth condition is

$\begin{split}\nabla
f_{o}(\boldsymbol{\eta}^{\prime})+\sum_{k=1}^{N}\lambda_{k}\nabla
h_{k}(\boldsymbol{\eta}^{\prime})=0,\\\
=\lambda_{k}+\ln({\tau})\sum_{n=1}^{N}(\eta_{n}^{s})+2p^{A}_{k}\sum_{n=1}^{N}(0.5-p^{A}_{n})\eta^{s}_{n}=0,\\\
\forall k\in\mathcal{N},\forall s=1,\ldots\sigma,\end{split}$ (25)

which is included in (19). As a result, $\boldsymbol{\eta}^{\prime}$ satisfies
all KKT conditions, and thus the proof is completed. ∎

Then, in Lemma 2, we prove that for any given $\sigma$, if the solution
obtained from (19) satisfies (13), it is the global optimal solution of (P2).

######  Lemma 2.

If the solution $\boldsymbol{\eta}^{\prime}$ obtained from (19) satisfies
(13), $\boldsymbol{\eta}^{\prime}$ is the global optimal solution of (P2).

###### Proof:

It follows from Lemma 1 that $\boldsymbol{\eta}^{\prime}$ is the global
optimal solution of (P3), and thus it satisfies (16). Moreover, constraints
(16) and (14) are identical. Therefore, $\boldsymbol{\eta}^{\prime}$ satisfies
(14). Furthermore, the objective function (12) of (P2) is constant. As a
result, if $\boldsymbol{\eta}^{\prime}$ satisfies (13),
$\boldsymbol{\eta}^{\prime}$ is the global optimal solution of (P2). The proof
is completed. ∎

Next, in Theorem 1, we prove that for any given $\sigma$, if the solution
$\boldsymbol{\eta}^{\prime}$ obtained from solving (19) satisfies (13), then
we can straightforwardly derive an equivalent feasible solution of (P1).
Moreover, if the optimal solution of (P3) satisfies (13) in the case where
$\sigma=S$, we can derive the global optimal solution of (P1). Note that when
the optimal solution of (P3) cannot satisfy (15), it does not imply the
absence of a feasible solution of (P1) for a given $\sigma$. Despite this
limitation, the proposed Lagrangian method can still find solutions that are
better than those from commercial solvers in a significantly shorter amount of
time. Moreover, the proposed method can find the global optimal solution in
most experiments as later shown in Section 6.

######  Theorem 1.

For any given $\sigma$, if the solution $\boldsymbol{\eta}^{\prime}$ obtained
from (19) satisfies (13), then
$\\{\boldsymbol{\eta}^{\prime},\mathbf{x},\sigma\\}$ is a feasible solution to
(P1), where $\mathbf{x}$ can be straightforwardly derived from $\sigma$.

###### Proof:

First, we prove that for any specific $\sigma$, we can straightforwardly
derive $\mathbf{x}$. Substituting $\varsigma=\sigma$ into (9), we have

$x_{s}\geq\dfrac{\sigma-s+1}{S},\forall s=1,\ldots,S.$ (26)

This means that $x_{s}>0$, $\forall s\leq\sigma$. Then, substituting
$\varsigma=\sigma$ into (10), we have

$x_{s}\leq\sigma-s+1,\forall s=1,\ldots,S.$ (27)

This means that $x_{s}\leq 0$, $\forall s>\sigma$. Moreover, since
$\mathbf{x}$ are binary, we have $x_{s}=1$ , $\forall s=1,\ldots,\sigma$ and
$x_{s}=0$, $\forall s>\sigma$.

As a result, (8) becomes

$\bigg{(}\sum_{n=1}^{N}(0.5-p^{A}_{n})\eta^{s}_{n}\bigg{)}^{2}\geq-0.5\ln(\tau)\sum_{n=1}^{N}(\eta_{n}^{s})^{2},\forall
s\leq\sigma,$ (28)

and

$\bigg{(}\sum_{n=1}^{N}(0.5-p^{A}_{n})\eta^{s}_{n}\bigg{)}^{2}\geq 0,\forall
s>\sigma.$ (29)

Since $\boldsymbol{\eta}^{\prime}$ satisfies (13), it also satisfies (28).
Moreover, since $p^{A}_{n}<0.5$ and $\eta_{n}^{s}>0$, (29) is always
satisfied. As a result, $\\{\boldsymbol{\eta}^{\prime},\mathbf{x},\sigma\\}$
satisfy all constraints of (P1), and thus it is a feasible solution to (P1).
The proof is now completed. ∎

####  5.2.3 Complexity analysis

The main component of Algorithm 1 is solving (19) to obtain
$\boldsymbol{\eta}^{\prime}$ in Steps 2 and 8. Using methods such as Gaussian
elimination [41], each instance of (19) can be solved with time complexity
$O\big{(}(\sigma N+N)^{3}\big{)}$. Additionally, because we utilize binary
search, (19) needs to be solved at most $\textrm{log}(S)$ times, and thus the
total time complexity of Algorithm 1 is $O\big{(}\textrm{log}(S)(\sigma
N+N)^{3}\big{)}$. In contrast, the time complexity of solving (P1) is
exponential [41], and (P1) involves more variables. As a result, Algorithm 1
can be frequently deployed to reconfigure the shards, thereby reducing the
risk of corruption from the adversary.

Figure 4: $\rm{Pr}_{51\%}$ achieved by the three methods.

##  6 Performance Evaluation

###  6.1 Simulation Settings

To evaluate the performance of our proposed approach, we conduct various
numerical experiments in five problem instances with different parameters
(number of nodes, maximum difference, mean, and standard deviation (STD) of
MUs score distribution) as shown in Table I. Moreover, in all experiments, we
set $T=2000$ Tx/s and $\alpha_{C}=\alpha_{D}=\alpha_{T}=1$. In these
experiments, we compare the performance of three methods as follows:

  * •

$SVP1$: We solve (P1) directly using the commercial solver CPLEX [40].

  * •

$SVP2$: We apply an iterative algorithm similar to Algorithm 1. However,
instead of solving (19) in Steps 2 and 8 as done in Algorithm 1, we solve (P2)
using the commercial solver CPLEX [40].

  * •

$LGRN$: We solve (P3) using the proposed Lagrangian approach as described in
Algorithm 1.

TABLE I: Problem instance parameters. Instance |  No. of nodes |  Maximum difference |  Mean |  STD
---|---|---|---|---
1 |  25 |  29 |  39.0 |  7.9
2 |  50 |  31 |  36.8 |  6.7
3 |  100 |  38 |  38.4 |  4.8
4 |  150 |  109 |  89.9 |  19.9
5 |  200 |  170 |  123.8 |  32.9

In the first set of experiments, we examine the best solution found by the
three methods under a limited running time (1 minute). Particularly, for each
instance, we vary $\varsigma$ and $\tau$ to examine the best possible solution
found by each method. The results show the lowest probability that the
adversary can control more than 51% of a shard’s score, denoted by
$\rm{Pr}_{51\%}$ ($\rm{Pr}_{51\%}$ can be calculated using (4)). For each
method, we record the lowest $\rm{Pr}_{51\%}$ given a specific number of
shards.

In the second set of experiments, we let all three methods run up to 10
minutes and then compare their running time and achievable throughput. For
$SVP2$, we set the time limit of each iteration (Step 2 and Step 8 in
Algorithm 1) to 1 minute. Moreover, we conduct experiments with different
values of $S$ to show the impact of $S$ on the performance of the considered
methods.

In the third set of experiments, we vary the values of $p_{n}^{A}$ to study
the impacts of the adversarial probability on the performance and security of
the network. Particularly, we gradually increase $p_{n}^{A}$ and examine the
best achieved $\rm{Pr}_{51\%}$ of the three methods for various numbers of
shards. Moreover, we also measure the highest throughput achieved by the
considered methods.

Finally, we study the impact of the MUs’ scores on the security of the system.
In particular, for a network of 50 nodes, we randomly generate instances with
different user engagement scores, as reflected by the different standard
deviations and average values of engagement scores. Then, for each instance,
we examine the best $\rm{Pr}_{51\%}$ achieved by the proposed $LGRN$ method to
study how different distributions of scores can affect network security.

###  6.2 Simulation Results

Fig. 4 illustrates the best $\rm{Pr}_{51\%}$ obtained by the three methods for
different numbers of shards in all problem instances. For example, in
Instance-1 with 25 nodes, when we want to optimize the score allocation for 2
shards, the three methods achieve similar results, e.g., around 0.003
possibility to be attacked. However, if we want to have more shards in the
system, $\rm{Pr}_{51\%}$ increases drastically if we use the $SVP1$ and $SVP2$
methods, e.g., 0.006 for 3 shards, 0.01 for 4 shards, and more than 0.01 for
higher numbers of shards. In contrast, even for 20 shards, the value of
$\rm{Pr}_{51\%}$ achieved by the $LGRN$ method is only around 0.003. Moreover,
for all other instances, the $LGRN$ method can achieve $\rm{Pr}_{51\%}$ lower
than the safety threshold (0.001) for up to 20 shards in the system. In
contrast, $SVP1$ and $SVP2$ can only ensure security, i.e.,
$\rm{Pr}_{51\%}<0.001$, for up to 4, 8, 10, and 11 shards in instances 2, 3,
4, and 5, respectively. Furthermore, compared to $SVP1$ and $SVP2$, $LGRN$ can
achieve smaller $\rm{Pr}_{51\%}$ in all cases. Note that since the values of
$\rm{Pr}_{51\%}$ achieved by $LGRN$ does not vary much compared to the other
methods, it is not shown clearly in the figure. For example, in Instance-3,
the values of $\rm{Pr}_{51\%}$ achieved by $LGRN$ ranges from 6x$10^{-10}$ to
9x$10^{-10}$, whereas those achieved by $SVP1$ ranges from 3x$10^{-8}$ to
0.012.

Figure 5: Throughput achieved by the three methods.

Fig. 5 shows the throughput achieved by the three methods for Instance-2 to
Instance-5. We do not show the achieved throughput for Instance-1 because, in
this instance, all three methods cannot ensure that $\rm{Pr}_{51\%}$ is lower
than the safety threshold even for 2 shards, and thus the network cannot be
divided into shards. For all the remaining instances, we can observe that the
proposed $LGRN$ method performs better than the other methods, especially for
high numbers of shards. For example, in Instance 2, $LGRN$ can achieve a
throughput up to $20,000$ Tx/s, while the other methods can achieve at most
$8,000$ Tx/s. Moreover, the $SVP1$ fails to find a feasible solution for
$S>5$, and thus the network cannot be divided into shards in these cases.
Similarly, $LGRN$ performs better than the other methods by up to $25\%$,
$50\%$, and $66.6\%$, in Instances 3, 4, and 5, respectively. Moreover, in
Instance-2 to Instance-5, $LGRN$ can achieve global optimal solutions for all
values of $S$, whereas $SVP1$ and $SVP2$ can not for higher values of $S$.

Figure 6: Running time of the three methods.

Fig. 6 shows the running time of the three methods in Instance-2 to
Instance-5. As observed, the computational time of the proposed $LGRN$ is
trivial compared to the other methods, particularly for high numbers of
shards. For example, in Instance 2, $LGRN$ needs only 2.3 seconds to find the
solution to divide the network into 10 shards. In contrast, $SVP2$ needs more
than 187 seconds, whereas $SVP1$ can only find solutions for up to 4 shards.
For more than 5 shards, $SVP1$ exceeds the running time limit without being
able to find any feasible solution. Similarly, for the remaining instances,
$LGRN$ can find better solutions in a much shorter time, i.e., more than 30,
16, and 8 times faster than $SVP2$. Meanwhile, $SVP1$ fails to find any
feasible solution for 9, 13, and 12 shards in Instance-3, Instance-4, and
Instance-5, respectively. Because of that, the graphs in Fig. 6 do not show
the running time of $SVP1$ in the cases where $SVP1$ cannot find any feasible
solution. Additionally, we can observe that the running time of $LGRN$ scales
almost linearly with $S$, while the running time of the other methods
increases exponentially as $S$ increases.

Figure 7: $\rm{Pr}_{51\%}$ under increasing adversarial probability.

Fig. 7 illustrates the results of the third set of experiments in terms of
security, i.e., the change in $\rm{Pr}_{51\%}$ as the adversarial probability
($p_{n}^{A}$) increases. As observed from the figure, $LGRN$ can ensure the
safety ($\rm{Pr}_{51\%}<0.1\%$) of a network with 50 nodes and 10 shards even
when $p_{n}^{A}$ increases by nearly 150%. In contrast, if we use $SVP1$ and
$SVP2$, $\rm{Pr}_{51\%}$ is nearly 0.04. Moreover, as $p_{n}^{A}$ increases,
$\rm{Pr}_{51\%}$ obtained from $SVP1$ and $SVP2$ increases drastically to over
0.1. This means that these methods cannot be employed for sharding when the
adversary controls a high portion of MUs. Furthermore, we can also observe
that $SVP2$ performs slightly better than $SVP1$ as the adversarial
probability increases.

Figure 8: Throughput under increasing adversarial probability.

Fig. 8 shows the highest throughput achieved by the three methods as
$p_{n}^{A}$ increases. It can be observed that the highest throughput $LGRN$
can achieve is 20,000 Tx/s (global optimal) with up to 145% increase in
adversarial probability. In contrast, $SVP1$ and $SVP2$ only attain a maximum
of 8,000 Tx/s and their throughput decreases when $p_{n}^{A}$ exceeds 115%.
When $p_{n}^{A}$ continues to rise, $SVP1$ and $SVP2$ fail to divide the
network into shards at 120% and 140% respectively, while $LGRN$ can still
sustain a throughput of 14,000 Tx/s at 155%. $LGRN$ only fails to find a
feasible solution after $p_{n}^{A}$ increases by more than 160%.

Figure 9: Impacts of mean and standard deviation.

Fig. 9 illustrates the $\rm{Pr}_{51\%}$ achieved by $LGRN$ for different
distributions of engagement scores. As observed from the figure, the more
spread out the engagement scores are (i.e., the standard deviation is high),
the higher the possibility of the network being attacked by the adversary.
Moreover, the higher score the network has (i.e., higher mean), the more
secure it becomes. For example, the instance with the largest standard
deviation has the greatest likelihood of being attacked. Moreover, among
instances with similar standard deviations, the ones with a higher mean (which
corresponds to a higher total score) have a lower probability of being
attacked. Therefore, while the network operators cannot influence the score
distribution, they can try to attract more MUs to the network (thereby
increasing the total score) to improve network security and performance.

##  7 Conclusion

In this paper, we have developed a novel sharding blockchain framework for
Metaverse applications. Particularly, we have developed a PoE consensus
mechanism that can encourage and reward MUs’ resources contribution, thereby
alleviating the huge resource demands for MSP and creating a more engaged MU
community. Moreover, we have proposed a sharding management scheme and
formulated an optimization problem to find the optimal number of shards and
MUs allocation. Since the optimization problem is NP-complete, we have
developed a hybrid approach that decomposes the problem (using the binary
search method) into sub-problems that can be solved effectively by the
Lagrangian method. As a result, the proposed approach can obtain solutions in
polynomial time, thereby enabling flexible shard reconfiguration and reducing
the risk of corruption from the adversary. Extensive numerical experiments
have been conducted, and their results have shown that, compared to the state-
of-the-art commercial solvers, our proposed approach can achieve up to 66.6%
higher throughput in less than 1/30 running time. Moreover, the proposed
approach can achieve global optimal solutions in most experiments.
Furthermore, we have studied the impacts of key parameters on the performance
of the system and shown that the proposed approach can further improve the
robustness of the system.

## References

  * [1] C. T. Nguyen, D. T. Hoang, D. N. Nguyen and E. Dutkiewicz, “MetaChain: A novel blockchain-based framework for Metaverse applications,” in _2022 IEEE 95th Vehicular Technology Conference: (VTC2022-Spring)_ , Helsinki, Finland, June 19-22, 2022, pp. 1-5.
  * [2] Y. Wang et al., “A survey on Metaverse: Fundamentals, security, and privacy,” IEEE Communications Surveys & Tutorials, vol. 25, no. 1, pp. 319-352, Firstquarter 2023.
  * [3] L. H. Lee et al., “All one needs to know about Metaverse: A complete survey on technological singularity, virtual ecosystem, and research agenda,”, Oct. 2021, _arXiv:2110.05352_
  * [4] T. Huynh-The et al., “Artificial intelligence for the metaverse: A survey,” Engineering Applications of Artificial Intelligence, vol. 117, no. 1, pp. 105581-605, Jan. 2023.
  * [5] D. T. Hoang, D. N. Nguyen, C. T. Nguyen, E. Hossain, and D. Niyato, Eds., Metaverse Communication and Computing Networks: Applications, Technologies, and Approaches. IEEE-Wiley, 2023.
  * [6] S. Kovach, “Next for the Metaverse: Convincing you it’s not just for kids,” _CNBC_ , Dec. 22, 2021. [Online]. Available: https://www.cnbc.com/2021/12/22/here-are-the-companies-building-the-Metaverse-meta-roblox-epic.html. [Accessed: 12-Feb-2023].
  * [7] Adidas, “Impossible is (probably) nothing,” _Adidas_. [Online]. Available: https://www.adidas.com/metaverse. [Accessed: 12-Feb-2023].
  * [8] S. Frier and D. Bass, “Microsoft makes a $69 billion down payment on the Metaverse,” _Bloomberg_ , Jan. 20, 2022. [Online]. Available: https://www.bloomberg.com/news/articles/2022-01-19/microsoft-msft-activision-blizzard-atvi-deal-shows-big-tech-metaverse-push#xj4y7vzkg. [Accessed: 12-Feb-2023].
  * [9] Y. Cai, J. Llorca, A. M. Tulino and A. F. Molisch, “Compute- and data-intensive networks: The key to the Metaverse,” in 2022 1st International Conference on 6G Networking (6GNet), Paris, France, July 6-8, 2022, pp. 1-8.
  * [10] W. Wang et al., “A survey on consensus mechanisms and mining strategy management in blockchain networks,” _IEEE Access_ , vol. 7, pp. 22328–22370, Jan. 2019.
  * [11] Y. Xiao, N. Zhang, W. Lou and Y. T. Hou, “A survey of distributed consensus protocols for blockchain networks,” _IEEE Communications Surveys & Tutorials_, vol. 2, no. 22, pp. 1432-1465, Jan, 2020.
  * [12] C. T. Nguyen, D. T. Hoang, D. N. Nguyen, D. Niyato, H. T. Nguyen, and E. Dutkiewicz, “Proof-of-Stake consensus mechanisms for future blockchain networks: Fundamentals, applications and opportunities,” _IEEE Access_ , vol. 7, pp. 85727–85745, June 2019.
  * [13] C. T. Nguyen et al., “FedChain: Secure Proof-of-Stake-based Framework for Federated-blockchain Systems,” IEEE Transactions on Services Computing, 2023, Early Access.
  * [14] J. Ryu, S. Son, J. Lee, Y. Park and Y. Park, “Design of secure mutual authentication scheme for Metaverse environments using blockchain,” _IEEE Access_ , vol. 10, pp. 98944-98958, Sep. 2022.
  * [15] M. Ersoy and R. Gürfidan, “Blockchain‐based asset storage and service mechanism to metaverse universe: Metarepo” _Transactions on Emerging Telecommunications Technologies_. vol. 34, no. 1, pp. 4658-4675, Jan. 2023.
  * [16] T. Maksymyuk, J. Gazda, G. Bugár, V. Gazda, M. Liyanage and M. Dohler, “Blockchain-empowered service management for the decentralized Metaverse of Things,” _IEEE Access_ , vol. 10, pp. 99025-99037, Sep. 2022.
  * [17] M. Zamani, M. Movahedi and M. Raykova “Rapidchain: Scaling blockchain via full sharding,” in _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_ , Oct. 2018, pp. 931-948.
  * [18] Z. Hong, S. Guo and P. Li, “Scaling blockchain via layered sharding,” IEEE Journal on Selected Areas in Communications, vol. 40, no. 12, pp. 3575-3588, Dec. 2022.
  * [19] L. Luu, V. Narayanan, C. Zheng, K. Baweja, S. Gilbert, and P. Saxena, “A secure sharding protocol for open blockchains,” in _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , Oct. 2016, pp. 17-30.
  * [20] H. Dang, T. T. Dinh, D. Loghin, E. C. Chang, Q. Lin and B. C. Ooi, “Towards scaling blockchain systems via sharding,” in _Proceedings of the 2019 International Conference on Management of Data_ , June 2019, pp. 123-140.
  * [21] Z. Cai et al., “Benzene: Scaling blockchain with cooperation-based sharding,” IEEE Transactions on Parallel and Distributed Systems, vol. 34, no. 2, pp. 639-654, Feb. 2023.
  * [22] X. Cai et al., “A sharding scheme-based many-objective optimization algorithm for enhancing security in blockchain-enabled Industrial Internet of Things,” _IEEE Transactions on Industrial Informatics_ , vol. 17, no. 11, pp. 7650-7658, Nov. 2021.
  * [23] C. Huang et al., “RepChain: A reputation-based secure, fast, and high incentive blockchain system via sharding,” _IEEE Internet of Things Journal_ , vol. 8, no. 6, pp. 4291-4304, Mar. 2021.
  * [24] E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta and B. Ford, “OmniLedger: A secure, scale-out, decentralized ledger via sharding,” in _2018 IEEE Symposium on Security and Privacy (SP)_ , San Francisco, CA, USA, May 20-24, 2018, pp. 583-598.
  * [25] D. Tennakoon and V. Gramoli, “Dynamic blockchain sharding,” in _5th International Symposium on Foundations and Applications of Blockchain 2022 (FAB 2022)_ , California, USA, June 3, 2022, pp. 1-17.
  * [26] “Jump in and be a part of Meta Horizon Worlds,” _Meta_. [Online]. Available: https://www.meta.com/au/horizon-worlds/. [Accessed: 12-Feb-2023].
  * [27] L. Luu, D. Chu, H. Olickel, P. Saxena, and A. Hobor, “Making smart contracts smarter,” in _Proceedings of the ACM SIGSAC Conference on Computer and Communications Security_ , Oct. 2016, pp. 254-269.
  * [28] G. Yu, X. Wang, K. Yu, W. Ni, J. A. Zhang and R. P. Liu, “Survey: Sharding in blockchains,” IEEE Access, vol. 8, pp. 14155-14181, Jan. 2020.
  * [29] J. Xie, F. R. Yu, T. Huang, R. Xie, J. Liu and Y. Liu, “A Survey on the scalability of blockchain systems,” IEEE Network, vol. 33, no. 5, pp. 166-173, Oct. 2019.
  * [30] Tennakoon D and Gramoli V “Dynamic blockchain sharding,” in 5th International Symposium on Foundations and Applications of Blockchain, Oakland , California, USA, June 3, 2022, pp. 1-17.
  * [31] B. Schoenmakers, “A simple publicly verifiable secret sharing scheme and its application to electronic voting,” in Annual International Cryptology Conference, Santa Barbara, California, USA, Aug. 15-19, 1999, pp. 148-164.
  * [32] H. Liu, Y. Zhang and T. Yang, “Blockchain-enabled security in electric vehicles cloud and edge computing,” IEEE Network, vol. 32, no. 3, pp. 78-83, June 2018.
  * [33] I. Martinez, S. Francis and A. S. Hafid, “Record and reward Federated Learning contributions with blockchain,” in International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC), Guilin, China, Oct. 17-19, 2019, pp. 50-57.
  * [34] A. Hafid, A. S. Hafid and M. Samih, “New mathematical model to analyze security of sharding-based blockchain protocols,” IEEE Access, vol. 7, pp. 185447-185457, Dec. 2019.
  * [35] C. Beekhuizen , “Validated, staking on eth2: #3 - sharding consensus,” _Ethereum_ , Mar. 27, 2020. [Online]. Available: https://blog.ethereum.org/2020/03/27/sharding-consensus. [Accessed: 12-Feb-2023].
  * [36] T. Ghosh, A. Roy and S. Misra, “B2H: Enabling delay-tolerant blockchain network in healthcare for Society 5.0,” Computer Networks, vol. 210, pp. 108860-70, June. 2022.
  * [37] J. Gridley and O. Seneviratne, “Significant digits: Using large-scale blockchain data to predict fraudulent addresses,” 2023, arXiv:2301.01809.
  * [38] M. Masmoudi, C. A. Zayani, I. Amous and F. Sèdes, “A new blockchain-based trust management model”, Procedia Computer Science, vol. 192, pp. 1081-91, Jan. 2021.
  * [39] M. X. Goemans, _Advanced Algorithms_. Cambridge, MA: MIT Laboratory for Computer Science, 1994.
  * [40] J. Kronqvist, D. E. Bernal, A. Lundell and I. E. Grossmann, “A review and comparison of solvers for convex MINLP” _Optimization and Engineering_. vol. 20, no. 2, pp. 397-455, June, 2019.
  * [41] S. P. Boyd and L. Vandenberghe, Convex optimization.Cambridge, UK: Cambridge University Press, 2011.
  * [42] M. Mitzenmacher and E. Upfal, _Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis_. Cambridge, UK: Cambridge University Press, 2017.
  * [43] R. M. Karp, “Reducibility among combinatorial problems,” in _50 Years of Integer Programming 1958-2008_. M. Junger et al, Eds. Heidelberg, Germany:Springer, 2010.

|  Cong T. Nguyen received his B.E. degree in Electrical Engineering and
Information from the Frankfurt University of Applied Sciences in 2014, his
M.Sc. degree in Global Production Engineering and Management from the
Technical University of Berlin in 2016. Since 2019, he has been a Ph.D.
student at the UTS-HCMUT Joint Technology and Innovation Research Centre
between Ho Chi Minh University of Technology and the University of Technology
Sydney (UTS). His research areas include operations research, blockchain
technology, game theory and optimizations.
---|---
|  Dinh Thai Hoang (M’16-SM’22) is currently a faculty member at the School of
Electrical and Data Engineering, University of Technology Sydney, Australia.
He received his Ph.D. in Computer Science and Engineering from the Nanyang
Technological University, Singapore, in 2016. His research interests include
emerging topics in wireless communications and networking such as machine
learning, edge intelligence, cybersecurity, IoT, and Metaverse. He has
received several awards including Australian Research Council and IEEE TCSC
Award for Excellence in Scalable Computing (Early Career Researcher).
Currently, he is an Editor of IEEE Transactions on Wireless Communications,
IEEE Transactions on Cognitive Communications and Networking, IEEE
Transactions on Vehicular Technology, and Associate Editor of IEEE
Communications Surveys & Tutorials.
---|---
|  Diep N. Nguyen (M’13-SM’19) received the M.E. degree in electrical and
computer engineering from the University of California at San Diego (UCSD) and
the Ph.D. degree in electrical and computer engineering from The University of
Arizona (UA). He is currently a Faculty Member with the Faculty of Engineering
and Information Technology, University of Technology Sydney (UTS). Before
joining UTS, he was a DECRA Research Fellow with Macquarie University and a
Member of Technical Staff with Broadcom Corporation, Irvine, CA, USA, and
ARCON Corporation, Boston, MA, USA, and consulting the Federal Administration
of Aviation on turning detection of UAVs and aircraft, and the U.S. Air Force
Research Laboratory on anti-jamming. His research interests include computer
networking, wireless communications, and machine learning application, with
emphasis on systems’ performance and security/privacy. He received several
awards from LG Electronics, UCSD, UA, the U.S. National Science Foundation,
and the Australian Research Council. He is currently an Editor, Associate
Editor, Guest Editor of the IEEE Transactions on Mobile Computing, IEEE
Access, Sensors journal, IEEE Open Journal of the Communications Society (OJ-
COMS), and Scientific Reports (Nature’s).
---|---
|  Yong Xiao (S’09-M’13-SM’15) received his B.S. degree in electrical
engineering from China University of Geosciences, Wuhan, China in 2002, M.Sc.
degree in telecommunication from Hong Kong University of Science and
Technology in 2006, and his Ph. D degree in electrical and electronic
engineering from Nanyang Technological University, Singapore in 2012. He is
now a professor in the School of Electronic Information and Communications at
the Huazhong University of Science and Technology (HUST), Wuhan, China. He is
also with Peng Cheng Laboratory, Shenzhen, China and Pazhou Laboratory
(Huangpu), Guangzhou, China. He is the associate group leader of the network
intelligence group of IMT-2030 (6G promoting group) and the vice director of
5G Verticals Innovation Laboratory at HUST. Before he joins HUST, he was a
research assistant professor in the Department of Electrical and Computer
Engineering at the University of Arizona where he was also the center manager
of the Broadband Wireless Access and Applications Center (BWAC), an NSF
Industry/University Cooperative Research Center (I/UCRC) led by the University
of Arizona. His research interests include machine learning, game theory,
distributed optimization, and their applications in semantic communications,
semantic-aware networks, cloud/fog/mobile edge computing, green communication
systems, and Internet-of-Things (IoT).
---|---
|  Dusit Niyato (M’09-SM’15-F’17) is a professor in the School of Computer
Science and Engineering, at Nanyang Technological University, Singapore. He
received B.Eng. from King Mongkuts Institute of Technology Ladkrabang (KMITL),
Thailand in 1999 and Ph.D. in Electrical and Computer Engineering from the
University of Manitoba, Canada in 2008. His research interests are in the
areas of Internet of Things (IoT), machine learning, and incentive mechanism
design.
---|---
|  Eryk Dutkiewicz (M’05–SM’15) received his B.E. degree in Electrical and
Electronic Engineering from the University of Adelaide in 1988, his M.Sc.
degree in Applied Mathematics from the University of Adelaide in 1992 and his
PhD in Telecommunications from the University of Wollongong in 1996. His
industry experience includes management of the Wireless Research Laboratory at
Motorola in early 2000’s. Prof. Dutkiewicz is currently the Head of School of
Electrical and Data Engineering at the University of Technology Sydney,
Australia. He is a Senior Member of IEEE. He also holds a professorial
appointment at Hokkaido University in Japan. His current research interests
cover 5G/6G and IoT networks.
---|---