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프로젝트로 돌아가기