MultiversX 백서

MultiversX

원문

bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 5쪽 중 1쪽

1 MultiversX A Highly Scalable Public Blockchain via Adaptive State Sharding and Secure Proof of Stake [Technical whitepaper — release 2 — revision 2] Updated: renaming to MultiversX June 19, 2019 - The MultiversX Team https://www.multiversx.com/ Abstract—The advent of secure public blockchains through Bitcoin and later Ethereum, has brought forth a notable degree of interest and capital influx, providing the premise for a global wave of permissionless innovation. Despite lofty promises, creating a decentralized, secure and scalable public blockchain has proved to be a strenuous task. This paper proposes MultiversX, a novel architecture which goes beyond state of the art by introducing a genuine state sharding scheme for practical scalability, eliminating energy and computational waste while ensuring distributed fairness through a Secure Proof of Stake (SPoS) consensus. Having a strong focus on security, MultiversX’ network is built to ensure resistance to known security problems like Sybil attack, Nothing at Stake attack and others. In an ecosystem that strives for interconnectivity, our solution for smart contracts offers an EVM compliant engine to ensure interoperability by design. Preliminary simulations and testnet results reflect that Mul- tiversX exceeds Visa’s average throughput and achieves an im- provement beyond three orders of magnitude or 1000x compared to the existing viable approaches, while drastically reducing the costs of bootstrapping and storage to ensure long term sustainability. I Introduction 1 General aspects Cryptocurrency and smart contract platforms such as Bit- coin and Ethereum have sparked considerable interest and have become promising solutions for electronic payments, decentralized applications and potential digital stores of value. However, when compared to their centralized counterparts in key metrics [1], the current state of affairs suggests that present public blockchain iterations exhibit severe limitations, particularly with respect to scalability, hindering their main- stream adoption and delaying public use. In fact, it has proved extremely challenging to deal with the current engi- neering boundaries imposed by the trade-offs in the blockchain trilemma paradigm [2]. Several solutions have been proposed, but few of them have shown significant and viable results. Thus, in order to solve the scalability problem, a complete rethinking of public blockchain infrastructures was required. 2 Defining the challenges Several challenges must be addressed properly in the pro- cess of creating an innovative public blockchain solution designed to scale: • Full decentralization - Eliminating the need for any trusted third party, hence removing any single point of failure; • Robust security - Allowing secure transactions and preventing any attacks based on known attack vectors; • High scalability - Enabling the network to achieve a performance at least equal to the centralized counterpart, as measured in TPS; • Efficiency - Performing all network services with mini- mal energy and computational requirements; • Bootstrapping and storage enhancement - Ensuring a competitive cost for data storage and synchronization; • Cross-chain interoperability - Enforced by design, per- mitting unlimited communication with external services. Starting from the above challenges, we’ve created Multi- versX as a complete rethinking of public blockchain infras- tructure, specifically designed to be secure, efficient, scalable and interoperable. MultiversX’ main contribution rests on two cornerstone building blocks: 1) A genuine State Sharding approach: effectively parti- tioning the blockchain and account state into multiple shards, handled in parallel by different participating validators; 2) Secure Proof of Stake consensus mechanism: an improved variation of Proof of Stake (PoS) that ensures long term security and distributed fairness, while elimi- nating the need for energy intensive PoW algorithms. 3 Adaptive State Sharding MultiversX proposes a dynamically adaptive sharding mech- anism that enables shard computation and reorganizing based on necessity and the number of active network nodes. The reassignment of nodes in the shards at the beginning of each epoch is progressive and nondeterministic, inducing no temporary liveness penalties. Adaptive state sharding comes with additional challenges compared to the static model. One of the key-points resides in how shard-splitting and shard- merging is done to prevent overall latency penalties introduced by the synchronization/communication needs when the shard number changes. Latency, in this case, is the communication overhead required by nodes, in order to retrieve the new state, once their shard address space assignment has been modified. 2 MultiversX proposes a solution for this problem below, but first some notions have to be defined: users and nodes. Users are external actors and can be identified by an unique account address; nodes are computers/devices in the Multi- versX network that run our protocol. Notions like users, nodes, addresses will be further described in chapter II.1 - Entities. MultiversX solves this challenge by: 1) Dividing the account address space in shards, using a binary tree which can be built with the sole requirement of knowing the exact number of shards in a certain epoch. Using this method, the accumulated latency is reduced and the network liveness is improved in two ways. First, thanks to the designed model, the dividing of the account address space is predetermined by hierarchy. Hence, there is no split overhead, meaning that one shard breaks into two shards, each of them keeping only one half of the previous address space in addition to the associated state. Second, the latency is reduced through the state redundancy mechanism, as the merge is prepared by retaining the state in the sibling nodes. 2) Introducing a technique of balancing the nodes in each shard, to achieve overall architecture equilibrium. This technique ensures a balanced workload and reward for each node in the network. 3) Designing a built-in mechanism for automatic transac- tion routing in the corresponding shards, considerably reduces latency as a result. The routing algorithm is de- scribed in chapter IV .4 - MultiversX sharding approach. 4) In order to achieve considerable improvements with respect to bootstrapping and storage, MultiversX makes use of a shard pruning mechanism. This ensures sus- tainability of our architecture even with a throughput of tens of thousands of transactions per second (TPS). 4 Secure Proof of Stake (SPoS) We introduce a Secure Proof of Stake consensus mecha- nism, that expands on Algorand’s [3] idea of a random se- lection mechanism, differentiating itself through the following aspects: 1) MultiversX introduces an improvement which reduces the latency allowing each node in the shard to determine the members of the consensus group (block proposer and validators) at the beginning of a round. This is possible because the randomization factor r is stored in every block and is created by the block proposer using a BLS signature [4] on the previous r. 2) The block proposer is the validator in the consensus group who’s hash of the public key and randomization factor is the smallest. In contrast to Algorand’s [3] ap- proach, where the random committee selection can take up to 12 seconds, in MultiversX the time necessary for random selection of the consensus group is considerably reduced (estimated under 100 ms) excluding network latency. Indeed, there is no communication requirement for this random selection process, which enables Mul- tiversX to have a newly and randomly selected group that succeeds in committing a new block to the ledger in each round. The tradeoff for this enhancement relies on the premise that an adversary cannot adapt faster than the round’s time frame and can choose not to propose the block. A further improvement on the security of the randomness source, would be the use of verifiable delay functions (VDFs) in order to prevent any tampering possibilities of the randomness source until it is too late. Currently, the research in VDFs is still ongoing - there only a few working (and poorly tested) VDF implementations. 3) In addition to the stake factor generally used in PoS architectures as a sole decision input, MultiversX refines its consensus mechanism by adding an additional weight factor called rating. The node’s probability to be selected in the consensus group takes into consideration both stake and rating. The rating of a block proposer is recal- culated at the end of each epoch, except in cases where slashing should occur, when the actual rating decrease is done instantly, adding another layer of security by promoting meritocracy. 4) A modified BLS multisignature scheme [5] with 2 communication rounds is used by the consensus group for block signing 5) MultiversX considers formal verification for the critical protocol implementations (e.g. SPoS consensus mecha- nism) in order to validate the correctness of our algo- rithms. II Architecture Overview 1 Entities There are two main entities in MultiversX: users and nodes. Users, each holding a (finite) number of public / private (Pk/sk) key pairs (e.g. in one or multiple wallet apps), use the MultiversX network to deploy signed transactions for value transfers or smart contracts’ execution. They can be identified by one of their account addresses (derived from the public key). The nodes are represented by the devices that form the MultiversX network and can be passive or actively engaged in processing tasks. Eligible validators are active participants in MultiversX’ network. Specifically, they are responsible for running consensus, adding blocks, maintaining the state and being rewarded for their contribution. Each eligible validator can be uniquely identified by a public key constructed through Fig. 1: Relations between MultiversX entities 3 a derivation of the address that staked the necessary amount and the node id. Relations between entities in the MultiversX protocol are shown in Fig. 1. Furthermore, the network is divided into smaller units called shards. An eligible validator is assigned to a shard based on an algorithm that keeps the nodes evenly distributed across shards, depending on the tree level. Each shard contains a randomly selected consensus group. Any block proposer is responsible to aggregate transactions into a new block. The validators are responsible to either reject, or approve the proposed block, thereby validating it and committing it to the blockchain. 2 Intrinsic token MultiversX grants access to the usage of its network through intrinsic utility token called eGold, in short EGLD. All costs for processing transactions, running smart contracts and rewards for various contributions to the network will be paid in EGLD. References to fees, payments or balances are assumed to be in EGLD. 3 Threat model MultiversX assumes a byzantine adversarial model, where at least 23n+1 of the eligible nodes in a shard are honest. The protocol permits the existence of adversaries that have stake or good rating, delay or send conflicting messages, compromise other nodes, have bugs or collude among themselves, but as long as 23n+1 of the eligible validators in a shard are honest/not compromised, the protocol can achieve consensus. The protocol assumes highly adaptive adversaries, which however cannot adapt faster than a round’s timeframe. The computational power of an adversary is bounded, therefore the cryptographic assumptions granted by the security level of the chosen primitives hold firmly within the complexity class of problems solvable by a Turing machine in polynomial time. The network of honest nodes is assumed to form a well connected graph and the propagation of their messages is done in a bounded time ∆. Attack vectors’ prevention 1) Sybil attacks: mitigated through the stake locking when joining the network. This way the generation of new identities has a cost equal to the minimum stake; 2) Nothing at stake: removed through the need of multiple signatures, not just from proposer, and the stake slashing. The reward per block compared to the stake locked will discourage such behavior; 3) Long range attacks: mitigated by our pruning mech- anism, the use of a randomly selected consensus group every round (and not just a single proposer) and stake locking. On top of all these, our pBFT consensus algo- rithm ensures finality; 4) DDoS attacks: the consensus group is randomly sam- pled every round (few seconds); the small time frame making DDoS almost impossible. Other attack vectors we have taken into consideration are: shard takeover attack, transaction censorship, double spend, bribery attacks, etc. 4 Chronology In MultiversX’ network, the timeline is split into epochs and rounds. The epochs have a fixed duration, set to one day (can be modified as the architecture evolves), at the end of which the shards reorganization and pruning is triggered. The epochs are further divided into rounds, lasting for a fixed timeframe. A new consensus group is randomly selected per shard in each round, that can commit a maximum of one block in the shard’s ledger. New validators can join the network by locking their stake, as presented in chapter V .2 - Secure Proof of Stake. They are added to the unassigned node pool in the current epoch e, are assigned to the waiting list of a shard at the beginning of epoch e + 1, but can only become eligible validators to participate in consensus and get rewarded in the next epoch e + 2. The timeline aspects are further detailed in section IX.1. III Related Work MultiversX was designed upon and inspired by the ideas from Ethereum [6], Omniledger [7], Zilliqa [8], Algorand [3] and ChainSpace [9]. Our architecture goes beyond state of the art and can be seen as an augmentation of the existing models, improving the performance while focusing to achieve a better nash equilibrium state between security, scalability and decentralization. 1 Ethereum Much of Ethereum’s [6] success can be attributed to the introduction of its decentralized applications layer through EVM [10], Solidity [11] and Web3j [12]. While Dapps have been one of the core features of ethereum, scalability has proved a pressing limitation. Considerable research has been put into solving this problem, however results have been negligible up to this point. Still, few promising improvements are being proposed: Casper [13] prepares an update that will replace the current Proof of Work (PoW) consensus with a Proof of Stake (PoS), while Plasma based side-chains and sharding are expected to become available in the near future, alleviating Ethereum’s scalability problem at least partially [14]. Compared to Ethereum, MultiversX eliminates both energy and computational waste from PoW algorithms by imple- menting a SPoS consensus while using transaction processing parallelism through sharding. 2 Omniledger Omniledger [7] proposes a novel scale-out distributed ledger that preserves long term security under permission-less op- eration. It ensures security and correctness by using a bias- resistant public-randomness protocol for choosing large, statis- tically representative shards that process transactions. To com- mit transactions atomically across shards, Omniledger intro- duces Atomix, an efficient cross-shard commit protocol. The concept is a two-phase client-driven ”lock/unlock” protocol that ensures that nodes can either fully commit a transaction across shards, or obtain ”rejection proofs” to abort and unlock 4 the state affected by partially completed transactions. Om- niledger also optimizes performance via parallel intra-shard transaction processing, ledger pruning via collectively-signed state blocks, and low-latency ”trust-but-verify” validation for low-value transactions. The consensus used in Omniledger is a BFT variation, named ByzCoinX, that increases performance and robustness against DoS attacks. Compared to Omniledger, MultiversX has an adaptive ap- proach on state sharding, a faster random selection of the consensus group and an improved security by replacing the validators’ set after every round (a few seconds) not after every epoch (1 day). 3 Zilliqa Zilliqa [8] is the first transaction-sharding architecture that allows the mining network to process transactions in parallel and reach a high throughput by dividing the mining network into shards. Specifically, its design allows a higher transaction rate as more nodes are joining the network. The key is to ensure that shards process different transactions, with no overlaps and therefore no double-spending. Zilliqa uses pBFT [15] for consensus and PoW to establish identities and prevent Sybil attacks. Compared to Zilliqa, MultiversX pushes the limits of shard- ing by using not only transaction sharding but also state shard- ing. MultiversX completely eliminates the PoW mechanism and uses SPoS for consensus. Both architectures are building their own smart contract engine, but MultiversX aims not only for EVM compliance, so that SC written for Ethereum will run seamlessly on our VM, but also aims to achieve interoperability between blockchains. 4 Algorand Algorand [3] proposes a public ledger that keeps the con- venience and efficiency of centralized systems, without the inefficiencies and weaknesses of current decentralized imple- mentations. The leader and the set of verifiers are randomly chosen, based on their signature applied to the last block’s quantity value. The selections are immune to manipulations and unpredictable until the last moment. The consensus relies on a novel message-passing Byzantine Agreement that enables the community and the protocol to evolve without hard forks. Compared to Algorand, MultiversX doesn’t have a single blockchain, instead it increases transaction’s throughput using sharding. MultiversX also improves on Algorand’s idea of ran- dom selection by reducing the selection time of the consensus group from over 12 seconds to less than a second, but assumes that the adversaries cannot adapt within a round. 5 Chainspace Chainspace [9] is a distributed ledger platform for high integrity and transparent processing of transactions. It uses language agnostic and privacy-friendly smart contracts for extensibility. The sharded architecture allows a linearly scal- able transaction processing throughput using S-BAC, a novel distributed atomic commit protocol that guarantees consistency and offers high auditability. Privacy features are implemented through modern zero knowledge techniques, while the consen- sus is ensured by BFT. Compared to Chainspace, where the TPS decreases with each node added in a shard, MultiversX’ approach is not influenced by the number of nodes in a shard, because the con- sensus group has a fixed size. A strong point for Chainspace is the approach for language agnostic smart contracts, while MultiversX focuses on building an abstraction layer for EVM compliance. Both projects use different approaches for state sharding to enhance performance. However, MultiversX goes a step further by anticipating the blockchain size problem in high throughput architectures and uses an efficient pruning mechanism. Moreover, MultiversX exhibits a higher resistance to sudden changes in node population and malicious shard takeover by introducing shard redundancy, a new feature for sharded blockchains. IV Scalability via Adaptive State Sharding 1 Why sharding Sharding was first used in databases and is a method for dis- tributing data across multiple machines. This scaling technique can be used in blockchains to partition states and transaction processing, so that each node would process only a fraction of all transactions in parallel with other nodes. As long as there is a sufficient number of nodes verifying each transaction so that the system maintains high reliability and securi
프로젝트로 돌아가기