MultiversX 백서

MultiversX

원문

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

ble to find another set of parameters that defines the same point on the elliptic curve [28], [29]. Additionally, EdDSA doesn’t need a random number generator because it Algorithm Family Crypto systems Security level (bit) 80 128 192 256 Integer factorization RSA 1024 3072 7680 15360 Discrete logarithm DH, DSA, Elgamal 1024 3072 7680 15360 Elliptic curves ECDH, ECDSA 160 256 384 512 Symmetric key AES, 3DES 80 128 192 256 TABLE 1: Bit lengths of public-key algorithms for different security levels 9 uses a nonce, calculated as the hash of the private key and the message, so the attack vector of a broken random number generator that can reveal the private key is avoided. Schnorr signature variants are gaining more attention [8], [30] due to a native multi-signature capability and being provably secure in the random oracle model [31]. A multi- signature scheme is a combination of a signing and verification algorithms, where multiple signers, each with their own private and public keys, can sign the same message, producing a single signature [32], [33]. This signature can then be checked by a verifier which has access to the message and the public keys of the signers. A sub-optimal method would be to have each node calculate his own signature and then concatenate all results in a single string. However, such an approach is unfeasible as the generated string size grows with the number of signers. A practical solution would be to aggregate the output into a single fixed size signature, independent of the number of participants. There have been multiple proposals of such schemes, most of them are susceptible to rogue-key (cancellation) attacks. One solution for this problem would be to introduce a step where each signer needs to prove possession of the private key associated with its public key [34]. Bellare and Neven [35] (BN) proposed a secure multi- signature scheme without a proof of possession, in the plain public key model, under the discrete logarithm assumption [31]. The participants commit first to their share Ri by prop- agating its hash to all other signers so they cannot calculate a function of it. Each signer computes a different challenge for their partial signature. However, this scheme sacrifices the public key aggregation. In this case, the verification of the aggregated signature, requires the public key from each signer. A recent paper by Gregory Maxwell et al. [29] proposes another multi-signature scheme in the plain public key model [36], under the ’one more discrete logarithm’ assumption (OMDL). This approach improves the previous scheme [35] by reducing the communication rounds from 3 to 2, reintroducing the key aggregation with a higher complexity cost. BLS [4] is another interesting signature scheme, from the Weil pairing, which bases its security on the Computational Diffie-Hellman assumption on certain elliptic curves and gen- erates short signatures. It has several useful properties like batch verification, signature aggregation, public key aggrega- tion, making BLS a good candidate for threshold and multi- signature schemes. Dan Boneh, Manu Drijvers and Gregory Neven recently proposed a BLS multi-signature scheme [5], using ideas from the previous work of [35], [30] to provide the scheme with defenses against rogue key attacks. The scheme supports efficient verification with only two pairings needed to verify a multi-signature and without any proof of knowledge of the secret key (works in the plain public key model). Another advantage is that the multi-signature can be created in only two communication rounds. For traceability and security reasons, a consensus based on a reduced set of validators requires the public key from each signer. In this context, our analysis concludes that the most appropriate multi-signature scheme for block signing in MultiversX is BLS multi-signature [5], which is faster overall than the other options due to only two communication rounds. 2 Block signing in MultiversX For block signing, MultiversX uses curve cryptography based on the BLS multi-signature scheme over the bn256 bilinear group, which implements the Optimal Ate pairing over a 256-bit Barreto Naehrig curve. The bilinear pairing is defined as: e : g0 × g1 → gt (1) where g0, g1 and gt are elliptic curves of prime order p defined by bn256, and e is a bilinear map (i.e. pairing function). Let G0 and G1 be generators for g0 and g1. Also, let H0 be a hashing function that produces points on the curve g0: H0 : M →g0 (2) where M is the set of all possible binary messages of any length. The signing scheme used by MultiversX employs a second hasing function as well, with parameters known by all signers: H1 : M →Zp (3) Each signer i has its own private/public key pair (ski, P ki), where ski is randomly chosen from Zp. For each key pair, the property P ki = ski · G1 holds. Let L = P k1, P k2, ..., P kn be the set of public keys of all possible signers during a specific round which, in the case of MultiversX, is the set of public keys of all the nodes in the consensus group. Below, the two stages of block signing process is presented: signing and verification. Practical signing - Round 1 The leader of the consensus group creates a block with transactions, then signs and broadcasts this block to the consensus group members. Practical signing - Round 2 Each member of the consensus group (including the leader) who receives the block must validate it, and if found valid, it signs it with BLS and then sends the signature to the leader: Sigi = ski ∗ H0(m) (4) where Sigi is a point on g0. Practical signing - Round 3 The leader waits to receive the signatures for a specific timeframe. If it does not receive at least 23 · n + 1 signatures in that timeframe, the consensus round is aborted. But if the leader does receive 23 · n + 1 or more valid signatures, it uses them to generate the aggregated signature: SigAgg = X i H1(P ki) · Sigi · B[i] (5) where SigAgg is a point on g0. The leader then adds the aggregated signature to the block together with the selected signers bitmap B, where a 1 indicates that the corresponding signer in the list L had its signature added to the aggregated signature SigAgg . 10 Practical verification Given the list of public keys L, the bitmap for the signers B, the aggregated signature SigAgg , and a message m (block), the verifier computes the aggregated public key: P kAgg= X i H1(P ki) · P ki · Bi (6) The result, P kAgg, is a point on g1. The final verification is e(G1, SigAgg) == e(P kAgg, H0(m)) (7) where e is the pairing function. VII Cross-shard Execution For an in depth example of how the cross-shard transactions are being executed and how the communication between shards and the metachain occurs, we are simplifying the entire process to just two shards and the metachain. Assuming that a user generates a transaction from his wallet, which has an address in shard 0 and wants to send EGLD to another user that has a wallet with an address in shard 1, the steps depicted in Fig. 4 are required for processing the cross-shard transaction. As mentioned in chapter V - Consensus via Secure Proof of Stake, the blocks structure is represented by a block Header that contains information about the block (block nonce, round, proposer, validators timestamp etc), and a list of miniblocks for each shard that contain the actual transactions inside. Every miniblock contains all transactions that have either the sender in the current shard and the receiver in another shard or the sender in a different shard and the destination in the current shard. In our case, for a block in shard 0, there will normally be 3 miniblocks: • miniblock 0: containing the intrashard transactions for shard 0 • miniblock 1: containing cross-shard transactions with the sender in shard 0 and destination in shard 1 • miniblock 2: containing cross-shard transactions with sender in shard 1 and destination in shard 0. These transactions were already processed in the sender shard 1 and will be finalized after the processing also in the current shard. There is no limitation on the number of miniblocks with the same sender and receiver in one block. Meaning multiple miniblocks with the same sender and receiver can appear in the same block. 1 Processing Currently the atomic unit of processing in cross-shard execution is a miniblock: either all the transactions of the miniblock are processed at once or none and the miniblock’s execution will be retried in the next round. Our cross-shard transaction strategy uses an asynchronous model. Validation and processing is done first in sender’s shard and then in receivers’ shard. Transactions are first dispatched in the sender’s shard, as it can fully validate any transaction initiated from the account in this shard – mainly the current balance. Afterwards, in the receivers’ shard, the nodes only need proof of execution offered by metachain, do signature verification and check for replay attack and finally update the balance for the receiver, adding the amount from the transaction. Shard 0 processes both intra-shard transactions in miniblock 0 and a set of cross-shard transactions that have addresses from shard 1 as a receiver in miniblock 1. The block header and miniblocks are sent to the metachain. The metachain notarizes the block from shard 0, by creating a new metachain block (metablock) that contains the following information about each miniblock: sender shard ID, receiver shard ID, miniblock hash. Fig. 4: Cross-shard transaction processing 11 Shard 1 fetches the hash of miniblock 1 from metablock, requests the miniblock from shard 0, parses the transaction list, requests missing transactions (if any), executes the same miniblock 1 in shard 1 and sends to the metachain resulting block. After notarization the cross transaction set can be considered finalized. The next diagram shows the number of rounds required for a transaction to be finalized. The rounds are considered between the first inclusion in a miniblock until the last miniblock is notarised. VIII Smart Contracts The execution of smart contracts is a key element in all future blockchain architectures. Most of the existing solutions avoid to properly explain the transactions and data dependency. This context leads to the following two scenarios: 1) When there is no direct correlation between smart con- tract transactions, as displayed in Fig. 5, any architecture can use out of order scheduling. This means there are no additional constraints on the time and place (shard) where a smart contract is executed. 2) The second scenario refers to the parallelism induced by the transactions that involve correlated smart contracts [37]. This case, reflected in Fig. 6, adds additional pressure on the performance and considerably increases the complexity. Basically there must be a mechanism to ensure that contracts are executed in the right order and on the right place (shard). To cover this aspect, MultiversX protocol proposes a solution that assigns and moves the smart contract to the same shard where their static dependencies reside. This way most, if not all SC calls will have dependencies in the same shard and no cross-shard locking/unlocking will be needed. MultiversX focuses on the implementation of the Multi- versX Virtual Machine, an EVM compliant engine. The EVM Fig. 5: Independent transaction processing under simple smart contracts that can be executed out of order Fig. 6: Mechanism for correlated smart contracts that can be executed only sequentially Fig. 7: Abstraction Layer for Smart Contracts compliance is extremely important for adoption purposes, due to the large number of smart contracts built on Ethereum’s platform. The MultiversX Virtual Machine’s implementation will hide the underlying architecture isolating the smart contract de- velopers from system internals ensuring a proper abstraction layer, as displayed in Fig. 7. In MultiversX, cross chain interoperability can be imple- mented by using an adapter mechanism at the Virtual Machine level as proposed by Cosmos [38]. This approach requires spe- cialized adapters and an external medium for communication between adapter SC for each chain that will interoperate with MultiversX. The value exchange will be operated using some specialized smart contracts acting as asset custodians, capable of taking custody of adapted chain native tokens and issuing MultiversX native tokens. 1 VM Infrastructure MultiversX builds its VM infrastructure on top of the K Framework, which is an executable semantic framework where programming languages, calculi, as well as type systems or formal analysis tools can be defined [39]. The greatest advantage of using the K framework is that with it, smart contract languages can be unambiguously de- fined, eliminating the potential for unspecified behavior and bugs that are hard to detect. The K Framework is executable, in the sense that the seman- tic specifications of languages can be directly used as working interpreters for the languages in question. More specifically, one can either run programs against the specifications using the K Framework core implementation directly, or one can generate an interpreter in several programming languages. These are also referred to as ”backends”. For the sake of execution speed and ease of interoperability, MultiversX uses its own custom-built K Framework backend. 2 Smart contract languages One great advantage of the K Framework is that one can generate an interpreter for any language defined in K, without the need for additional programming. This also means that 12 interpreters produced this way are ”correct-by-construction”. There are several smart contract languages specified in the K Framework already, or with their specifications under de- velopment. MultiversX Network will support three low-level languages: IELE VM, KEVM, and W ASM. • IELE VM is an intermediate-level language, in the style of LLVM, but adapted for the blockchain. It was built directly in K, no other specification or implementation of it exists outside of the K framework [40]. Its purpose is to be human readable, fast, and to overcome some limita- tions of EVM. MultiversX uses a slightly altered version of IELE - most changes are related to account address management. Smart contract developers can program in IELE directly, but most will choose to code in Solidity and then use a Solidity to IELE compiler, as can be seen in Fig. 8. • KEVM is a version of the Ethereum Virtual Machine (EVM), written in K [41]. Certain vulnerabilities of EVM are fixed in the K version, or the vulnerable features are left out entirely. • Web Assembly (W ASM) is a binary instruction format for a stack-based virtual machine, which can be used for running smart contracts. A W ASM infrastructure enables developers to write smart contracts in C/C++, Rust, C#, and others. Having a language specification and generating the inter- preter is only half of the challenge. The other half is integrating the generated interpreter with the MultiversX network. We have built a common VM interface, that enables us to plug in any VM into an MultiversX node as shown in Fig. 9. Each VM then has an adapter that implements this interface. Each contract is saved as bytecode of the VM for which it was compiled and runs on its corresponding VM. 3 Support for formal modelling and verification Because the smart contract languages are formally defined in K Framework, it is possible to perform formal verification of smart contracts written in these languages. To do this, it Fig. 8: MultiversX VM execution Fig. 9: MultiversX VM components is necessary to also formally model their requirements, which can also be performed using the K Framework [42]. 4 Smart contracts on the sharded architecture Smart contracts on sharded architectures are still in the early stages of research and development and pose serious challenges. Protocols like Atomix [7] or S-BAC [9] represent a starting point. Dynamic smart contract dependencies cannot be resolved by moving the SCs into the same shard, as at deployment time, not all the dependencies can be calculated. Solution currently research in the space: 1) A locking mechanism that allows the atomic execution of smart contract from different shards, ensures that the involved SCs will be either all executed at the same time, or none at all. This requires multiple interaction messages and synchronization between consensuses of different shards. [9] 2) Cross-shard contract yanking proposal for Ethereum 2.0 would move that smart contract code and data into the caller shard at the execution time. Atomic execution is not needed, but the locking mechanism is mandatory on the moved SC, which would block the execution of SC for other transactions. The locking mechanism is simpler, but it needs to transfer the whole internal state of the SC. [43] Following Ethereum’s model, MultiversX has the following transaction types: 1) SC construction and deployment: transactions receiver address is empty and data field contains the smart contract code as byte array; 2) SC method invoking: transaction has a non empty re- ceiver address and that address has an associated code; 3) Payment transactions: transaction has a non empty re- ceiver and that address does not have code. MultiversX’ approach to this problem is to use asyn- chronous cross-shard execution model in case of smart con- tracts. The user creates a smart contract execution transaction. If the smart contract is not in the current shard, the transaction is treated as a payment transaction, the value of the transaction is subtracted from the sender account and it is added to the block where the sender shard resides, into a miniblock with the destination shard where the receiver account is. The transaction is notarized by metachain, then processed by the destination shard. In the destination shard, the transaction is treated as SC method invoking, as the receiver address is a smart contract which exists in this shard. For the smart contract call a temporary account which shadows the sender 13 account is created, with the balance from the transaction value and the smart contract is called. After the execution, the smart contract might return results which affects a number of accounts from different shards. All the results, which affect in-shard accounts are executed in the same round. For those accounts which are not in the shard where the smart contract was executed, transactions called Smart Contract Results will be created, saving the smart contract execution output for each of these accounts. SCR miniblocks are created for each destination shard. These miniblocks are notarized the same way as cross-shard transactions by metachain, then processed by the respective shards, where the accounts resides. In case one smart contract calls dynamically another smart contract from another shard, this call is saved as an intermediate result and treated the same as for accounts. The solution has multiple steps and the finalization of a cross-shard smart contract call will need at least 5 rounds, but it does not need locking and state movement across shards. IX Bootstrapping and Storage 1 Timeline division Proof of Stake systems tend to generally divide timeline into epochs and each epoch into smaller rounds [19]. The timeline and terminology may differ between architectures but most of them use a similar approach. Epochs In MultiversX Protocol, each epoch has a fixed duration, initially set to 24 hours (might suffer updates after sev- eral testnet confirmation stages). During this timeframe, the configuration of the shards remains unchanged. The system adapts to scalability demands between epochs by modifying the number of shards. To prevent collusion, after an epoch, the configuration of each shard needs to change. While reshuffling all nodes between shards would provide the highest security level, it would affect the system’s liveness by introducing a
프로젝트로 돌아가기