MultiversX 백서

MultiversX

원문

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

ty, then splitting a blockchain into shards will allow it to process many transactions in parallel, and thus greatly improving transaction throughput and efficiency. Sharding promises to increase the throughput as the validator network expands, a property that is referred to as horizontal scaling. 2 Sharding types A comprehensive and thorough introduction [16] empha- sizes the three main types of sharding: network sharding, transaction sharding and state sharding. Network sharding handles the way the nodes are grouped into shards and can be used to optimize communication, as message propagation inside a shard can be done much faster than propagation to the entire network. This is the first challenge in every sharding approach and the mechanism that maps nodes to shards has to take into consideration the possible attacks from an attacker that gains control over a specific shard. Transaction sharding handles the way the transactions are mapped to the shards where they will be processed. In an account-based system, the transactions could be assigned to shards based on the sender’s address. State sharding is the most challenging approach. In contrast to the previously described sharding mechanisms, where all nodes store the entire state, in state- sharded blockchains, each shard maintains only a portion of the state. Every transaction handling accounts that are in different shards, would need to exchange messages and update states in different shards. In order to increase resiliency to malicious attacks, the nodes in the shards have to be reshuffled from time to time. However, moving nodes between shards 5 introduces synchronization overheads, that is, the time taken for the newly added nodes to download the latest state. Thus, it is imperative that only a subset of all nodes should be redistributed during each epoch, to prevent down times during the synchronization process. 3 Sharding directions Some sharding proposals attempt to only shard transactions [8] or only shard state [17], which increases transaction’s throughput, either by forcing every node to store lots of state data or to be a supercomputer [2]. Still, more recently, at least one claim has been made about successfully performing both transaction and state sharding, without compromising on storage or processing power [13]. But sharding introduces some new challenges like: single- shard takeover attack, cross-shard communication, data avail- ability and the need of an abstraction layer that hides the shards. However, conditional on the fact that the above problems are addressed correctly, state sharding brings con- siderable overall improvements: transaction throughput will increase significantly due to parallel transaction processing and transaction fees will be considerably reduced. Two main criterias widely considered to be obstacles transforming into advantages and incentives for mainstream adoption of the blockchain technology. 4 MultiversX sharding approach While dealing with the complexity of combining network, transaction and state sharding, MultiversX’ approach was designed with the following goals in mind: 1) Scalability without affecting availability: Increasing or decreasing the number of shards should affect a negligibly small vicinity of nodes without causing down- times, or minimizing them while updating states; 2) Dispatching and instant traceability: Finding out the destination shard of a transaction should be determinis- tic, trivial to calculate, eliminating the need for commu- nication rounds; 3) Efficiency and adaptability: The shards should be as balanced as possible at any given time. Method Description To calculate an optimum number of shards Nsh in epoch ei+1 (Nsh,i+1), we have defined one threshold coefficient for the number of transactions in a block, θT X. Variable optN represents the optimal number of nodes in a shard, ϵsh is a positive number and represents the number of nodes a shard can vary by. totalNi is the total number of nodes (eligible validators, nodes in the waiting lists and newly added nodes in the node pool) on all shards in epoch ei, while NT XB,i is the average number of transactions in a block on all shards in epoch ei. Nsh,0 will be considered as 1. The total number of shards Nsh,i+1 will change if the number of nodes totalNi in the network changes and if the blockchain utilization needs it: if the number of nodes increases above a threshold nSplit from one epoch to another and the average number of transactions per block is greater than the threshold number of transactions per block NT XB,i > θT X or if the number of nodes decreases below a threshold nM ergeas shown in function ComputeShardsN . 1: function COMPUTE SHARDS N(totalNi+1, Nsh,i) 2: nSplit ← (Nsh,i + 1) ∗ (optN + ϵsh) 3: nM erge← (Nsh,i − 1) ∗ a 4: Nsh,i+1 ← Nsh,i 5: if (totalNi+1 > nSplitand NT XB,i> θT X) then 6: Nsh,i+1 ← totalNi+1/(optN + ϵsh) 7: else if totalNi+1 < nM ergethen 8: Nsh,i+1 ← totalNi+1/(optN ) 9: return Nsh,i+1 From one epoch to another, there is a probability that the number of active nodes changes. If this aspect influences the number of shards, anyone can calculate the two masks m1 and m2, used in transaction dispatching. 1: function COMPUTE M1 AND M2(Nsh) 2: n ← math.ceil(log2Nsh) 3: m1 ← (1 << n) − 1 4: m2 ← (1 << (n − 1)) − 1 5: return m1, m2 As the main goal is to increase the throughput beyond thousands of transactions per second and to diminish the cross-shard communication, MultiversX proposes a dispatch- ing mechanism which determines automatically the shards involved in the current transaction and routes the transaction accordingly. The dispatcher will take into consideration the account address (addr) of the transaction sender/receiver. The result is the number of the shard (shard) the transaction will be dispatched to. 1: function COMPUTE SHARD (Nsh, addr, m1, m2) 2: shard ← (addr and m1) 3: if shard > Nsh then 4: shard ← (addr and m2) 5: return shard The entire sharding scheme is based on a binary tree structure that distributes the account addresses, favors the scalability and deals with the state transitions. A representation of the tree can be seen in Fig. 2. The presented tree structure is merely a logical represen- tation of the account address space used for a deterministic mapping; e.g. shard allocation, sibling computation etc. The leaves of the binary tree represent the shards with their ID number. Starting from root (node/shard 0), if there is only one shard/leaf (a), all account addresses are mapped to this one and all transactions will be executed here. Further on, if the formula for Nsh dictates the necessity of 2 shards (b), the address space will be split in equal parts, according to the last bits in the address. Sometimes, the tree can also become unbalanced (c) if Nsh is not a power of 2. This case only affects the leaves on the 6 Fig. 2: Example of a sharding tree structure last level. The structure will become balanced again when the number of shards reaches a power of 2. The unbalancing of the binary tree causes the shards located in the lowest level to have half the address space of nodes of a shard located one level higher, so it can be argued that the active nodes allocated to these shards will have a lower fee income - block rewards are not affected. However, this problem is solved by having a third of each shard nodes redistributed randomly each epoch (detailed in the Chronology section) and having a balanced distribution of nodes according to the tree level. Looking at the tree, starting from any leaf and going through branches towards the root, the encoding from branches represents the last n bits of the account addresses that will have their associated originating transactions processed by that leaf/shard. Going the other way around, from root to leaf, the information is related to the evolution of the structure, sibling shards, the parent shard from where they split. Using this hierarchy, the shard that will split when Nsh increases or the shards that will merge when Nsh decreases can easily be calculated. The entire state sharding mechanism benefits from this structure by always keeping the address and the associated state within the same shard. Knowing Nsh, any node can follow the redistribution pro- cess without the need of communication. The allocation of ID’s for the new shards is incremental and reducing the number of shards involves that the higher numbered shards will be removed. For example, when going from Nsh to Nsh- 1, two shards will be merged, the shard to be removed is the highest numbered shard ( shmerge=Nsh-1). Finding the shard number that shmerge will be merged with is trivial. According to the tree structure, the resulting shard has the sibling’s number: 1: function COMPUTE SIBLING (shmerge, n) 2: sibling ← (shmerge xor (1 << (n − 1))) 3: return sibling For shard redundancy, traceability of the state transitions and fast scaling, it is important to determine the sibling and parent of a generic shard with number p: 1: function COMPUTE PARENT SIBLINGS (n, p, Nsh) 2: mask1 ← 1 << (n − 1) 3: mask2 ← 1 << (n − 2) 4: sibling ← (p xor mask1) 5: parent ← min(p, sibling) 6: if sibling ≥ Nsh then 7: sibling ← (p xor mask2) 8: sibling2 ← (sibling xor mask1) 9: parent ← min(p, sibling) 10: if sibling2 ≥ Nsh then ▷ sibling is a shard 11: return parent, sibling, N U LL 12: else 13: ▷ sibling is a subtree with 14: ▷ shards(sibling, sibling2) 15: return parent, sibling, sibling2 16: else ▷ sibling is a shard 17: return parent, sibling, N U LL Shard redundancy On blockchain, state sharding is susceptible to shard failure when there is an insufficient number of online nodes in a shard or the distribution is localized geographically. In the unlikely case when one shard fails (either the shard cannot be contacted - all nodes are offline, or consensus cannot be reached - more than 13 of nodes are not responding), there is a high risk that the entire architecture relies only on super- full nodes [2], which fully download every block of every shard, fully verifying everything. As displayed in Fig. 3, our protocol has a protection mechanism that introduces a tradeoff in the state holding structure by enforcing the shards from the last tree level to also hold the state from their siblings. This mechanism reduces the communication and eliminates the bootstrapping when sibling shards are merging since they already have the data. Context switching To preserve security in sharded public blockchains, context switching becomes crucial [7]. This refers to the realloca- tion of the active nodes between shards on a fixed time interval by some random criteria. In MultiversX’ approach, the context switching represents a security improvement, but also increases the complexity required to maintain consis- tency between multiple states. The state transition has the 7 Fig. 3: Shard redundancy across epochs biggest footprint on performance since the movement of active nodes requires to resync the state, blockchain and transactions alongside the eligible nodes in the new shard. At the start of each epoch, in order to maintain liveness, only less than 13 of these nodes will be uniformly re-distributed across shards. This mechanism is highly effective against forming malicious groups. 5 Notarization (Meta) chain All network and global data operations (node joining the network, node leaving the network, eligible validator lists computation, nodes assignment to the shard’s waiting lists, consensus agreement on a block in a specific shard challenges for invalid blocks will be notarized in the metachain. The metachain consensus is run by a different shard that com- municates with all other shards and facilitates cross-shard operations. Every round of every epoch, the metachain receives block headers from the other shards and, if necessary, proofs for the challenges of the invalid blocks. This information will be aggregated into blocks on the metachain on which consensus has to be run. Once the blocks are validated in the consensus group, shards can request information about blocks, miniblocks (see chapter VII), eligible validators, nodes in waiting lists etc., in order to securely process cross-shard transactions. Further details about the cross-shard transaction execution, communication between shards and metachain will be presented in Chapter VII Cross-shard transaction process- ing. V Consensus via Secure Proof of Stake 1 Consensus Analysis The first blockchain consensus algorithm based on Proof of Work (PoW), is used in Bitcoin, Ethereum and other blockchain platforms. In Proof of Work each node is required to solve a mathematical puzzle (hard to calculate but easy to verify). And the first node that finishes the puzzle will collect the reward [18]. Proof of Work mechanisms successfully prevent double-spending, DDoS and Sybil attacks at the cost of high energy consumption. Proof of Stake (PoS) is a novel and more efficient con- sensus mechanism proposed as an alternative to the intensive energy and computational use in Proof of Work consensus mechanisms. PoS can be found in many new architectures like Cardano [19] and Algorand [3] or can be used in next version of Ethereum. In PoS the node that proposes the next block is selected by a combination of stake (wealth), randomness and/or age. It mitigates the PoW energy problem but also puts two important issues on the table: the Nothing at Stake attack and a higher centralization risk. Proof of Meme as envisioned in Constellation [20], is an algorithm based on the node’s historical participation on the network. Its behaviour is stored in a matrix of weights in the blockchain and supports changes over time. Also, it allows new nodes to gain trust by building up reputation. The main drawback regarding Sybil attacks is alleviated through the NetFlow algorithm. Delegated Proof of Stake (DPoS) found in Bitshares [21], Steemit [22] and EOS [23] is a hybrid between Proof of Authority and Proof of Stake in which the few nodes respon- sible for deploying new blocks are elected by stakeholders. Although it has a high throughput, the model is susceptible to human related social problems such as bribing and corruption. Also, a small number of delegates makes the system prone to DDoS attacks and centralization. 2 Secure Proof of Stake (SPoS) MultiversX’s approach to consensus is made by combining random validators’ selection, eligibility through stake and rating, with an optimal dimension for the consensus group. The algorithm is described in the steps below: 1) Each node ni is defined as a tuple of public key ( P k), rating (default is 0) and the locked stake. If ni wishes to participate in the consensus, it has to first register through a smart contract, by sending a transaction that contains an amount equal to the minimum required stake and other information ( P ks, a public key derived from P kand nodeid that will be used for the signing process in order not to use a real wallet address). 2) The node ni joins the node pool and waits for the shard assignment at the end of the current epoch e. The shard assignment mechanism creates a new set of nodes containing all the nodes that joined in epoch e and all 8 the nodes that need to be reshuffled (less than 13 of every shard). All nodes in this set will be reassigned to the waiting lists of shards. Wj represents j’s shard waiting list and Nsh represents the number of shards. A node also has a secret key sk that by nature is not to be made public. ni = (P ki, ratingi, stakei) ni ∈ Wj, 0 ≤ j < Nsh 3) At the end of the epoch in which it has joined, the node will be moved to the list of eligible nodes (Ej) of a shard j, where e is the current epoch. ni ∈ Wj,e−1 → ni ̸∈ Wj,e, ni ∈ Ej,e 4) Each node from the list Ej can be selected as part of an optimally dimensioned consensus group (in terms of se- curity and communication), by a deterministic function, based on the randomness source added to the previous block, the round r and a set of variation parameters. The random number, known to all shard nodes through gossip, cannot be predicted before the block is actually signed by the previous consensus group. This property makes it a good source of randomness and prevents highly adaptive malicious attacks. We define a selection function to return the set of chosen nodes (consensus group) Nchosen with the first being the block proposer, that takes following parameters: E, r and sigr−1 - the previous block signature. Nchosen = f (E, r, sigr−1), where Nchosen ⊂ E 5) The block will be created by the block proposer and the validators will co-sign it based on a modified practical Byzantine Fault Tolerance (pBFT). 6) If, for any reason, the block proposer did not create a block during its allocated time slot (malicious, offline, etc.), round r will be used together with the randomness source from the last block to select a new consensus group. If the current block proposer acts in a malicious way, the rest of the group members apply a negative feedback to change its rating, decreasing or even cancelling out the chances that this particular node will be selected again. The feedback function for the block proposer (ni) in round number r, with parameter ratingM odif ier∈ Z is computed as: f eedbackf unction= f f(ni, ratingM odif ier, r) When ratingM odif ier <0, slashing occurs so the node ni loses its stake. The consensus protocol remains safe in the face of DDoS attacks by having a high number of possible validators from the list E (hundreds of nodes) and no way to predict the order of the validators before they are selected. To reduce the communication overhead that comes with an increased number of shards, a consensus will be run on a composite block. This composite block is formed by: • Ledger block: the block to be added into the shard’s ledger, having all intra shard transactions and cross shard transactions for which confirmation proof was received; • Multiple mini-blocks: each of them holding cross shard transactions for a different shard; The consensus will be run only once, on the composite block containing both intra- and cross-shard transactions. After consensus is reached, the block header of each shard is sent to the metachain for notarization. VI Cryptographic Layer 1 Signature Analysis Digital signatures are cryptographic primitives used to achieve information security by providing several properties like message authentication, data integrity and non-repudiation [24]. Most of the schemes used for existing blockchain platforms rely on the discrete logarithm (DL) problem: one-way expo- nentiation function y → αymod p. It is scientifically proven that calculating the discrete logarithm with base is hard [25]. Elliptic curve cryptography (ECC) uses a cyclic group of points instead of a cyclic group of integers. The scheme reduces the computational effort, such that for key lengths of only 160 - 256 bits, ECC provides same security level that RSA, Elgamal, DSA and others provide for key lengths of 1024 - 3072 bits (see Table 1 [24]). The reason why ECC provides a similar security level for much smaller parameter lengths is because existing attacks on elliptic curve groups are weaker than the existing integer DL attacks, the complexity of such algorithms require on average√p steps to solve. This means that an elliptic curve using a prime p of 256 bit length provides on average a security of 2128 steps needed to break it [24]. Both Ethereum and Bitcoin use curve cryptography, with the ECDSA signing algorithm. The security of the algorithm is very dependent on the random number generator, because if the generator does not produce a different number on each query, the private key can be leaked [26]. Another digital signature scheme is EdDSA, a Schnorr variant based on twisted Edwards curves that support fast arithmetic [27]. In contrast to ECDSA, it is provably non- malleable, meaning that starting from a simple signature, it is impossi
프로젝트로 돌아가기