Elrond Whitepaper

Monday, January 13, 2020
Download document
Save for later
Add to list

1 Elrond A Highly Scalable Public Blockchain via Adaptive State Sharding and Secure Proof of Stake [Technical whitepaper — release 2 — revision 1] Updated chapters: [5 - 13] June 19, 2019 - The Elrond Team https://www.elrond.com/ Abstract—The advent of secure public blockchains through • Full decentralization - Eliminating the need for any Bitcoin and later Ethereum, has brought forth a notable degree trusted third party, hence removing any single point of of interest and capital influx, providing the premise for a failure; global wave of permissionless innovation. Despite lofty promises, • Robust security - Allowing secure transactions and creating a decentralized, secure and scalable public blockchain has proved to be a strenuous task. preventing any attacks based on known attack vectors; This paper proposes Elrond, a novel architecture which goes • High scalability - Enabling the network to achieve a beyond state of the art by introducing a genuine state sharding performance at least equal to the centralized counterpart, scheme for practical scalability, eliminating energy and com- as measured in TPS; putational waste while ensuring distributed fairness through a • Efficiency - Performing all network services with mini- Secure Proof of Stake (SPoS) consensus. Having a strong focus on security, Elrond’s network is built to ensure resistance to known mal energy and computational requirements; security problems like Sybil attack, Nothing at Stake attack and • Bootstrapping and storage enhancement - Ensuring a others. In an ecosystem that strives for interconnectivity, our competitive cost for data storage and synchronization; solution for smart contracts offers an EVM compliant engine to • Cross-chain interoperability - Enforced by design, per- ensure interoperability by design. Preliminary simulations and testnet results reflect that Elrond mitting unlimited communication with external services. exceeds Visa’s average throughput and achieves an improvement Starting from the above challenges, we’ve created Elrond beyond three orders of magnitude or 1000x compared to the as a complete rethinking of public blockchain infrastructure, existing viable approaches, while drastically reducing the costs specifically designed to be secure, efficient, scalable and inter- of bootstrapping and storage to ensure long term sustainability. operable. Elrond’s main contribution rests on two cornerstone building blocks: I Introduction 1) A genuine State Sharding approach: effectively parti- tioning the blockchain and account state into multiple 1 General aspects shards, handled in parallel by different participating Cryptocurrency and smart contract platforms such as Bit- validators; coin and Ethereum have sparked considerable interest and 2) Secure Proof of Stake consensus mechanism: an have become promising solutions for electronic payments, improved variation of Proof of Stake (PoS) that ensures decentralized applications and potential digital stores of value. long term security and distributed fairness, while elimi- However, when compared to their centralized counterparts nating the need for energy intensive PoW algorithms. in key metrics [1], the current state of affairs suggests that present public blockchain iterations exhibit severe limitations, 3 Adaptive State Sharding particularly with respect to scalability, hindering their main- stream adoption and delaying public use. In fact, it has Elrond proposes a dynamically adaptive sharding mecha- proved extremely challenging to deal with the current engi- nism that enables shard computation and reorganizing based neering boundaries imposed by the trade-offs in the blockchain on necessity and the number of active network nodes. The trilemma paradigm [2]. Several solutions have been proposed, reassignment of nodes in the shards at the beginning of but few of them have shown significant and viable results. each epoch is progressive and nondeterministic, inducing no Thus, in order to solve the scalability problem, a complete temporary liveness penalties. Adaptive state sharding comes rethinking of public blockchain infrastructures was required. 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 2 Defining the challenges by the synchronization/communication needs when the shard Several challenges must be addressed properly in the pro- number changes. Latency, in this case, is the communication cess of creating an innovative public blockchain solution overhead required by nodes, in order to retrieve the new state, designed to scale: once their shard address space assignment has been modified.

2 Elrond proposes a solution for this problem below, but first each round. The tradeoff for this enhancement relies on some notions have to be defined: users and nodes. Users are the premise that an adversary cannot adapt faster than external actors and can be identified by an unique account the round’s time frame and can choose not to propose address; nodes are computers/devices in the Elrond network the block. A further improvement on the security of the that run our protocol. Notions like users, nodes, addresses will randomness source, would be the use of verifiable delay be further described in chapter II.1 - Entities. functions (VDFs) in order to prevent any tampering Elrond solves this challenge by: possibilities of the randomness source until it is too 1) Dividing the account address space in shards, using a late. Currently, the research in VDFs is still ongoing binary tree which can be built with the sole requirement - there only a few working (and poorly tested) VDF of knowing the exact number of shards in a certain implementations. epoch. Using this method, the accumulated latency is 3) In addition to the stake factor generally used in PoS reduced and the network liveness is improved in two architectures as a sole decision input, Elrond refines its ways. First, thanks to the designed model, the dividing of consensus mechanism by adding an additional weight the account address space is predetermined by hierarchy. factor called rating. The node’s probability to be selected Hence, there is no split overhead, meaning that one in the consensus group takes into consideration both shard breaks into two shards, each of them keeping stake and rating. The rating of a block proposer is recal- only one half of the previous address space in addition culated at the end of each epoch, except in cases where to the associated state. Second, the latency is reduced slashing should occur, when the actual rating decrease through the state redundancy mechanism, as the merge is done instantly, adding another layer of security by is prepared by retaining the state in the sibling nodes. promoting meritocracy. 2) Introducing a technique of balancing the nodes in each 4) A modified BLS multisignature scheme [5] with 2 shard, to achieve overall architecture equilibrium. This communication rounds is used by the consensus group technique ensures a balanced workload and reward for for block signing each node in the network. 5) Elrond considers formal verification for the critical pro- 3) Designing a built-in mechanism for automatic transac- tocol implementations (e.g. SPoS consensus mechanism) tion routing in the corresponding shards, considerably in order to validate the correctness of our algorithms. reduces latency as a result. The routing algorithm is described in chapter IV.4 - Elrond sharding approach. II Architecture Overview 4) In order to achieve considerable improvements with re- spect to bootstrapping and storage, Elrond makes use of 1 Entities a shard pruning mechanism. This ensures sustainability There are two main entities in Elrond: users and nodes. of our architecture even with a throughput of tens of Users, each holding a (finite) number of public / private thousands of transactions per second (TPS). (Pk/sk) key pairs (e.g. in one or multiple wallet apps), use the Elrond network to deploy signed transactions for value transfers or smart contracts’ execution. They can be identified 4 Secure Proof of Stake (SPoS) by one of their account addresses (derived from the public We introduce a Secure Proof of Stake consensus mecha- key). The nodes are represented by the devices that form the nism, that expands on Algorand’s [3] idea of a random se- Elrond network and can be passive or actively engaged in lection mechanism, differentiating itself through the following processing tasks. Eligible validators are active participants in aspects: Elrond’s network. Specifically, they are responsible for running 1) Elrond introduces an improvement which reduces the consensus, adding blocks, maintaining the state and being latency allowing each node in the shard to determine rewarded for their contribution. Each eligible validator can the members of the consensus group (block proposer and be uniquely identified by a public key constructed through a validators) at the beginning of a round. This is possible derivation of the address that staked the necessary amount and 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] approach, where the random committee selection can take up to 12 seconds, in Elrond 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 Elrond to have a newly and randomly selected group that Fig. 1: Relations between Elrond entities succeeds in committing a new block to the ledger in

3 the node id. Relations between entities in the Elrond protocol 4 Chronology are shown in Fig. 1. In Elrond’s network, the timeline is split into epochs and Furthermore, the network is divided into smaller units called rounds. The epochs have a fixed duration, set to one day (can shards. An eligible validator is assigned to a shard based on be modified as the architecture evolves), at the end of which an algorithm that keeps the nodes evenly distributed across the shards reorganization and pruning is triggered. The epochs shards, depending on the tree level. Each shard contains a are further divided into rounds, lasting for a fixed timeframe. randomly selected consensus group. Any block proposer is A new consensus group is randomly selected per shard in each responsible to aggregate transactions into a new block. The round, that can commit a maximum of one block in the shard’s validators are responsible to either reject, or approve the ledger. proposed block, thereby validating it and committing it to the New validators can join the network by locking their stake, blockchain. as presented in chapter V.2 - Secure Proof of Stake. They are added to the unassigned node pool in the current epoch e, are 2 Intrinsic token assigned to the waiting list of a shard at the beginning of epoch e + 1, but can only become eligible validators to participate Elrond grants access to the usage of its network through in consensus and get rewarded in the next epoch e + 2. intrinsic utility tokens called Elronds, in short ERDs. All The timeline aspects are further detailed in section IX.1. costs for processing transactions, running smart contracts and rewards for various contributions to the network will be paid in ERDs. References to fees, payments or balances are assumed III Related Work to be in ERDs. Elrond was designed upon and inspired by the ideas from Ethereum [6], Omniledger [7], Zilliqa [8], Algorand [3] and 3 Threat model ChainSpace [9]. Our architecture goes beyond state of the art and can be seen as an augmentation of the existing Elrond assumes a byzantine adversarial model, where at models, improving the performance while focusing to achieve least 23 n+1 of the eligible nodes in a shard are honest. The a better nash equilibrium state between security, scalability protocol permits the existence of adversaries that have stake or and decentralization. good rating, delay or send conflicting messages, compromise other nodes, have bugs or collude among themselves, but as long as 23 n+1 of the eligible validators in a shard are honest/not 1 Ethereum compromised, the protocol can achieve consensus. Much of Ethereum’s [6] success can be attributed to the The protocol assumes highly adaptive adversaries, which introduction of its decentralized applications layer through however cannot adapt faster than a round’s timeframe. The EVM [10], Solidity [11] and Web3j [12]. While Dapps have computational power of an adversary is bounded, therefore been one of the core features of ethereum, scalability has the cryptographic assumptions granted by the security level of proved a pressing limitation. Considerable research has been the chosen primitives hold firmly within the complexity class put into solving this problem, however results have been of problems solvable by a Turing machine in polynomial time. negligible up to this point. Still, few promising improvements The network of honest nodes is assumed to form a well are being proposed: Casper [13] prepares an update that will connected graph and the propagation of their messages is done replace the current Proof of Work (PoW) consensus with a in a bounded time ∆. Proof of Stake (PoS), while Plasma based side-chains and Attack vectors’ prevention sharding are expected to become available in the near future, 1) Sybil attacks: mitigated through the stake locking when alleviating Ethereum’s scalability problem at least partially joining the network. This way the generation of new [14]. identities has a cost equal to the minimum stake; Compared to Ethereum, Elrond eliminates both energy and 2) Nothing at stake: removed through the need of multiple computational waste from PoW algorithms by implementing a signatures, not just from proposer, and the stake slashing. SPoS consensus while using transaction processing parallelism The reward per block compared to the stake locked will through sharding. discourage such behavior; 3) Long range attacks: mitigated by our pruning mech- 2 Omniledger anism, the use of a randomly selected consensus group Omniledger [7] proposes a novel scale-out distributed ledger every round (and not just a single proposer) and stake that preserves long term security under permission-less op- locking. On top of all these, our pBFT consensus algo- eration. It ensures security and correctness by using a bias- rithm ensures finality; resistant public-randomness protocol for choosing large, statis- 4) DDoS attacks: the consensus group is randomly sam- tically representative shards that process transactions. To com- pled every round (few seconds); the small time frame mit transactions atomically across shards, Omniledger intro- making DDoS almost impossible. duces Atomix, an efficient cross-shard commit protocol. The Other attack vectors we have taken into consideration are: concept is a two-phase client-driven ”lock/unlock” protocol shard takeover attack, transaction censorship, double spend, that ensures that nodes can either fully commit a transaction bribery attacks, etc. across shards, or obtain ”rejection proofs” to abort and unlock

4 the state affected by partially completed transactions. Om- and offers high auditability. Privacy features are implemented niledger also optimizes performance via parallel intra-shard through modern zero knowledge techniques, while the consen- transaction processing, ledger pruning via collectively-signed sus is ensured by BFT. state blocks, and low-latency ”trust-but-verify” validation for Compared to Chainspace, where the TPS decreases with low-value transactions. The consensus used in Omniledger is a each node added in a shard, Elrond’s approach is not influ- BFT variation, named ByzCoinX, that increases performance enced by the number of nodes in a shard, because the con- and robustness against DoS attacks. sensus group has a fixed size. A strong point for Chainspace Compared to Omniledger, Elrond has an adaptive approach is the approach for language agnostic smart contracts, while on state sharding, a faster random selection of the consensus Elrond focuses on building an abstraction layer for EVM group and an improved security by replacing the validators’ compliance. Both projects use different approaches for state set after every round (a few seconds) not after every epoch (1 sharding to enhance performance. However, Elrond goes a day). step further by anticipating the blockchain size problem in high throughput architectures and uses an efficient pruning 3 Zilliqa mechanism. Moreover, Elrond exhibits a higher resistance to sudden changes in node population and malicious shard Zilliqa [8] is the first transaction-sharding architecture that takeover by introducing shard redundancy, a new feature for allows the mining network to process transactions in parallel sharded blockchains. 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 IV Scalability via Adaptive State Sharding to ensure that shards process different transactions, with no 1 Why sharding overlaps and therefore no double-spending. Zilliqa uses pBFT Sharding was first used in databases and is a method for dis- [15] for consensus and PoW to establish identities and prevent tributing data across multiple machines. This scaling technique Sybil attacks. can be used in blockchains to partition states and transaction Compared to Zilliqa, Elrond pushes the limits of sharding processing, so that each node would process only a fraction of by using not only transaction sharding but also state sharding. all transactions in parallel with other nodes. As long as there Elrond completely eliminates the PoW mechanism and uses is a sufficient number of nodes verifying each transaction so SPoS for consensus. Both architectures are building their own that the system maintains high reliability and security, then smart contract engine, but Elrond aims not only for EVM com- splitting a blockchain into shards will allow it to process many pliance, so that SC written for Ethereum will run seamlessly transactions in parallel, and thus greatly improving transaction on our VM, but also aims to achieve interoperability between throughput and efficiency. Sharding promises to increase the blockchains. throughput as the validator network expands, a property that is referred to as horizontal scaling. 4 Algorand Algorand [3] proposes a public ledger that keeps the con- 2 Sharding types venience and efficiency of centralized systems, without the inefficiencies and weaknesses of current decentralized imple- A comprehensive and thorough introduction [16] empha- mentations. The leader and the set of verifiers are randomly sizes the three main types of sharding: network sharding, chosen, based on their signature applied to the last block’s transaction sharding and state sharding. Network sharding quantity value. The selections are immune to manipulations handles the way the nodes are grouped into shards and can and unpredictable until the last moment. The consensus relies be used to optimize communication, as message propagation on a novel message-passing Byzantine Agreement that enables inside a shard can be done much faster than propagation the community and the protocol to evolve without hard forks. to the entire network. This is the first challenge in every Compared to Algorand, Elrond doesn’t have a single sharding approach and the mechanism that maps nodes to blockchain, instead it increases transaction’s throughput using shards has to take into consideration the possible attacks from sharding. Elrond also improves on Algorand’s idea of random an attacker that gains control over a specific shard. Transaction selection by reducing the selection time of the consensus group sharding handles the way the transactions are mapped to the from over 12 seconds to less than a second, but assumes that shards where they will be processed. In an account-based the adversaries cannot adapt within a round. 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 5 Chainspace mechanisms, where all nodes store the entire state, in state- Chainspace [9] is a distributed ledger platform for high sharded blockchains, each shard maintains only a portion of integrity and transparent processing of transactions. It uses the state. Every transaction handling accounts that are in language agnostic and privacy-friendly smart contracts for different shards, would need to exchange messages and update extensibility. The sharded architecture allows a linearly scal- states in different shards. In order to increase resiliency to able transaction processing throughput using S-BAC, a novel malicious attacks, the nodes in the shards have to be reshuffled distributed atomic commit protocol that guarantees consistency from time to time. However, moving nodes between shards

5 introduces synchronization overheads, that is, the time taken number of transactions per block NT XB,i > θT X or if the for the newly added nodes to download the latest state. Thus, number of nodes decreases below a threshold nM erge as it is imperative that only a subset of all nodes should be shown in function ComputeShardsN . redistributed during each epoch, to prevent down times during the synchronization process. 1: function C OMPUTE S HARDS N(totalNi+1 , Nsh,i ) 2: nSplit ← (Nsh,i + 1) ∗ (optN + sh ) 3: nM erge ← (Nsh,i − 1) ∗ a 3 Sharding directions 4: Nsh,i+1 ← Nsh,i Some sharding proposals attempt to only shard transactions 5: if (totalNi+1 > nSplit and NT XB,i > θT X ) then [8] or only shard state [17], which increases transaction’s 6: Nsh,i+1 ← totalNi+1 /(optN + sh ) throughput, either by forcing every node to store lots of state 7: else if totalNi+1 < nM erge then data or to be a supercomputer [2]. Still, more recently, at 8: Nsh,i+1 ← totalNi+1 /(optN ) least one claim has been made about successfully performing 9: return Nsh,i+1 both transaction and state sharding, without compromising on storage or processing power [13]. But sharding introduces some new challenges like: single- From one epoch to another, there is a probability that the shard takeover attack, cross-shard communication, data avail- number of active nodes changes. If this aspect influences the ability and the need of an abstraction layer that hides the number of shards, anyone can calculate the two masks m1 and shards. However, conditional on the fact that the above m2 , used in transaction dispatching. problems are addressed correctly, state sharding brings con- siderable overall improvements: transaction throughput will 1: function C OMPUTE M1 AND M2(Nsh ) increase significantly due to parallel transaction processing 2: n ← math.ceil(log2 Nsh ) and transaction fees will be considerably reduced. Two main 3: m1 ← (1 << n) − 1 criterias widely considered to be obstacles transforming into 4: m2 ← (1 << (n − 1)) − 1 advantages and incentives for mainstream adoption of the 5: return m1 , m2 blockchain technology. As the main goal is to increase the throughput beyond thousands of transactions per second and to diminish the cross- 4 Elrond sharding approach shard communication, Elrond proposes a dispatching mecha- While dealing with the complexity of combining network, nism which determines automatically the shards involved in transaction and state sharding, Elrond’s approach was designed the current transaction and routes the transaction accordingly. with the following goals in mind: The dispatcher will take into consideration the account address 1) Scalability without affecting availability: Increasing (addr) of the transaction sender/receiver. The result is the or decreasing the number of shards should affect a number of the shard (shard) the transaction will be dispatched negligibly small vicinity of nodes without causing down- to. times, or minimizing them while updating states; 2) Dispatching and instant traceability: Finding out the 1: function C OMPUTE S HARD(Nsh , addr, m1 , m2 ) destination shard of a transaction should be determinis- 2: shard ← (addr and m1 ) tic, trivial to calculate, eliminating the need for commu- 3: if shard > Nsh then nication rounds; 4: shard ← (addr and m2 ) 3) Efficiency and adaptability: The shards should be as 5: return shard balanced as possible at any given time. Method Description The entire sharding scheme is based on a binary tree To calculate an optimum number of shards Nsh in epoch structure that distributes the account addresses, favors the ei+1 (Nsh,i+1 ), we have defined one threshold coefficient scalability and deals with the state transitions. A representation for the number of transactions in a block, θT X . Variable of the tree can be seen in Fig. 2. optN represents the optimal number of nodes in a shard, The presented tree structure is merely a logical represen- sh is a positive number and represents the number of nodes tation of the account address space used for a deterministic a shard can vary by. totalNi is the total number of nodes mapping; e.g. shard allocation, sibling computation etc. The (eligible validators, nodes in the waiting lists and newly added leaves of the binary tree represent the shards with their ID nodes in the node pool) on all shards in epoch ei , while number. Starting from root (node/shard 0), if there is only one NT XB,i is the average number of transactions in a block on shard/leaf (a), all account addresses are mapped to this one all shards in epoch ei . Nsh,0 will be considered as 1. The and all transactions will be executed here. Further on, if the total number of shards Nsh,i+1 will change if the number of formula for Nsh dictates the necessity of 2 shards (b), the nodes totalNi in the network changes and if the blockchain address space will be split in equal parts, according to the last utilization needs it: if the number of nodes increases above a bits in the address. threshold nSplit from one epoch to another and the average Sometimes, the tree can also become unbalanced (c) if Nsh number of transactions per block is greater than the threshold is not a power of 2. This case only affects the leaves on the

6 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 C OMPUTE S IBLING(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 C OMPUTE PARENT S IBLINGS(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 Fig. 2: Example of a sharding tree structure 13: . sibling is a subtree with 14: . shards (sibling, sibling2 ) 15: return parent, sibling, sibling2 last level. The structure will become balanced again when the 16: else . sibling is a shard number of shards reaches a power of 2. 17: return parent, sibling, N U LL The unbalancing of the binary tree causes the shards located in the lowest level to have half the address space of nodes Shard redundancy of a shard located one level higher, so it can be argued that On blockchain, state sharding is susceptible to shard failure the active nodes allocated to these shards will have a lower when there is an insufficient number of online nodes in a fee income - block rewards are not affected. However, this shard or the distribution is localized geographically. In the problem is solved by having a third of each shard nodes unlikely case when one shard fails (either the shard cannot redistributed randomly each epoch (detailed in the Chronology be contacted - all nodes are offline, or consensus cannot be section) and having a balanced distribution of nodes according reached - more than 31 of nodes are not responding), there is to the tree level. a high risk that the entire architecture relies only on super- Looking at the tree, starting from any leaf and going full nodes [2], which fully download every block of every through branches towards the root, the encoding from branches shard, fully verifying everything. As displayed in Fig. 3, our represents the last n bits of the account addresses that will protocol has a protection mechanism that introduces a tradeoff have their associated originating transactions processed by that in the state holding structure by enforcing the shards from leaf/shard. Going the other way around, from root to leaf, the last tree level to also hold the state from their siblings. the information is related to the evolution of the structure, This mechanism reduces the communication and eliminates sibling shards, the parent shard from where they split. Using the bootstrapping when sibling shards are merging since they this hierarchy, the shard that will split when Nsh increases or already have the data. the shards that will merge when Nsh decreases can easily be Context switching calculated. The entire state sharding mechanism benefits from To preserve security in sharded public blockchains, context this structure by always keeping the address and the associated switching becomes crucial [7]. This refers to the realloca- state within the same shard. tion of the active nodes between shards on a fixed time Knowing Nsh , any node can follow the redistribution pro- interval by some random criteria. In Elrond’s approach, the cess without the need of communication. The allocation of context switching represents a security improvement, but also ID’s for the new shards is incremental and reducing the increases the complexity required to maintain consistency number of shards involves that the higher numbered shards between multiple states. The state transition has the biggest

7 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 Fig. 3: Shard redundancy across epochs 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. footprint on performance since the movement of active nodes Delegated Proof of Stake (DPoS) found in Bitshares [21], requires to resync the state, blockchain and transactions along- Steemit [22] and EOS [23] is a hybrid between Proof of side the eligible nodes in the new shard. At the start of Authority and Proof of Stake in which the few nodes respon- each epoch, in order to maintain liveness, only less than 31 sible for deploying new blocks are elected by stakeholders. of these nodes will be uniformly re-distributed across shards. Although it has a high throughput, the model is susceptible to This mechanism is highly effective against forming malicious human related social problems such as bribing and corruption. groups. Also, a small number of delegates makes the system prone to DDoS attacks and centralization. 5 Notarization (Meta) chain 2 Secure Proof of Stake (SPoS) All network and global data operations (node joining the network, node leaving the network, eligible validator lists Elrond’s approach to consensus is made by combining computation, nodes assignment to the shard’s waiting lists, random validators’ selection, eligibility through stake and consensus agreement on a block in a specific shard challenges rating, with an optimal dimension for the consensus group. for invalid blocks will be notarized in the metachain. The The algorithm is described in the steps below: metachain consensus is run by a different shard that com- 1) Each node ni is defined as a tuple of public key (P k), municates with all other shards and facilitates cross-shard rating (default is 0) and the locked stake. If ni wishes operations. Every round of every epoch, the metachain receives to participate in the consensus, it has to first register block headers from the other shards and, if necessary, proofs through a smart contract, by sending a transaction that for the challenges of the invalid blocks. This information contains an amount equal to the minimum required stake will be aggregated into blocks on the metachain on which and other information (P ks , a public key derived from consensus has to be run. Once the blocks are validated in P k and nodeid that will be used for the signing process the consensus group, shards can request information about in order not to use a real wallet address). blocks, miniblocks (see chapter VII), eligible validators, nodes 2) The node ni joins the node pool and waits for the in waiting lists etc., in order to securely process cross-shard shard assignment at the end of the current epoch e. The transactions. Further details about the cross-shard transaction shard assignment mechanism creates a new set of nodes execution, communication between shards and metachain will containing all the nodes that joined in epoch e and all

8 the nodes that need to be reshuffled (less than 13 of ledger, having all intra shard transactions and cross shard every shard). All nodes in this set will be reassigned transactions for which confirmation proof was received; to the waiting lists of shards. Wj represents j’s shard • Multiple mini-blocks: each of them holding cross shard waiting list and Nsh represents the number of shards. A transactions for a different shard; node also has a secret key sk that by nature is not to be The consensus will be run only once, on the composite made public. block containing both intra- and cross-shard transactions. After ni = (P ki , ratingi , stakei ) consensus is reached, the block header of each shard is sent to the metachain for notarization. ni ∈ Wj , 0 ≤ j < Nsh 3) At the end of the epoch in which it has joined, the node VI Cryptographic Layer will be moved to the list of eligible nodes (Ej ) of a 1 Signature Analysis shard j, where e is the current epoch. Digital signatures are cryptographic primitives used to ni ∈ Wj,e−1 → ni 6∈ Wj,e , ni ∈ Ej,e achieve information security by providing several properties like message authentication, data integrity and non-repudiation 4) Each node from the list Ej can be selected as part of an [24]. optimally dimensioned consensus group (in terms of se- Most of the schemes used for existing blockchain platforms curity and communication), by a deterministic function, rely on the discrete logarithm (DL) problem: one-way expo- based on the randomness source added to the previous nentiation function y → αy mod p. It is scientifically proven block, the round r and a set of variation parameters. that calculating the discrete logarithm with base is hard [25]. The random number, known to all shard nodes through Elliptic curve cryptography (ECC) uses a cyclic group of gossip, cannot be predicted before the block is actually points instead of a cyclic group of integers. The scheme signed by the previous consensus group. This property reduces the computational effort, such that for key lengths makes it a good source of randomness and prevents of only 160 - 256 bits, ECC provides same security level that highly adaptive malicious attacks. We define a selection RSA, Elgamal, DSA and others provide for key lengths of function to return the set of chosen nodes (consensus 1024 - 3072 bits (see Table 1 [24]). group) Nchosen with the first being the block proposer, The reason why ECC provides a similar security level for that takes following parameters: E, r and sigr−1 - the much smaller parameter lengths is because existing attacks on previous block signature. elliptic curve groups are weaker than the existing integer DL Nchosen = f (E, r, sigr−1 ), where Nchosen ⊂ E attacks, the complexity of such algorithms require on average √ p steps to solve. This means that an elliptic curve using a 5) The block will be created by the block proposer and the prime p of 256 bit length provides on average a security of validators will co-sign it based on a modified practical 2128 steps needed to break it [24]. Byzantine Fault Tolerance (pBFT). Both Ethereum and Bitcoin use curve cryptography, with 6) If, for any reason, the block proposer did not create a the ECDSA signing algorithm. The security of the algorithm block during its allocated time slot (malicious, offline, is very dependent on the random number generator, because etc.), round r will be used together with the randomness if the generator does not produce a different number on each source from the last block to select a new consensus query, the private key can be leaked [26]. group. Another digital signature scheme is EdDSA, a Schnorr If the current block proposer acts in a malicious way, the rest variant based on twisted Edwards curves that support fast of the group members apply a negative feedback to change its arithmetic [27]. In contrast to ECDSA, it is provably non- rating, decreasing or even cancelling out the chances that this malleable, meaning that starting from a simple signature, it particular node will be selected again. The feedback function is impossible to find another set of parameters that defines for the block proposer (ni ) in round number r, with parameter the same point on the elliptic curve [28], [29]. Additionally, ratingM odif ier ∈ Z is computed as: EdDSA doesn’t need a random number generator because it f eedbackf unction = f f (ni , ratingM odif ier, r) Algorithm Crypto Security level (bit) When ratingM odif ier < 0, slashing occurs so the node Family systems 80 128 192 256 ni loses its stake. Integer RSA 1024 3072 7680 15360 factorization The consensus protocol remains safe in the face of DDoS Discrete DH, DSA, attacks by having a high number of possible validators from 1024 3072 7680 15360 logarithm Elgamal the list E (hundreds of nodes) and no way to predict the order Elliptic ECDH, 160 256 384 512 of the validators before they are selected. curves ECDSA To reduce the communication overhead that comes with an Symmetric AES, 80 128 192 256 key 3DES increased number of shards, a consensus will be run on a composite block. This composite block is formed by: TABLE 1: Bit lengths of public-key algorithms for different • Ledger block: the block to be added into the shard’s security levels

9 uses a nonce, calculated as the hash of the private key and is BLS multi-signature [5], which is faster overall than the the message, so the attack vector of a broken random number other options due to only two communication rounds. generator that can reveal the private key is avoided. Schnorr signature variants are gaining more attention [8], 2 Block signing in Elrond [30] due to a native multi-signature capability and being For block signing, Elrond uses curve cryptography based provably secure in the random oracle model [31]. A multi- on the BLS multi-signature scheme over the bn256 bilinear signature scheme is a combination of a signing and verification group, which implements the Optimal Ate pairing over a 256- algorithms, where multiple signers, each with their own private bit Barreto Naehrig curve. The bilinear pairing is defined as: and public keys, can sign the same message, producing a single signature [32], [33]. This signature can then be checked by e : g0 × g1 → gt (1) a verifier which has access to the message and the public keys of the signers. A sub-optimal method would be to have where g0 , g1 and gt are elliptic curves of prime order p defined each node calculate his own signature and then concatenate by bn256, and e is a bilinear map (i.e. pairing function). Let all results in a single string. However, such an approach is G0 and G1 be generators for g0 and g1 . Also, let H0 be a unfeasible as the generated string size grows with the number hashing function that produces points on the curve g0 : of signers. A practical solution would be to aggregate the H0 : M → g0 (2) output into a single fixed size signature, independent of the number of participants. There have been multiple proposals where M is the set of all possible binary messages of any of such schemes, most of them are susceptible to rogue-key length. The signing scheme used by Elrond employs a second (cancellation) attacks. One solution for this problem would hasing function as well, with parameters known by all signers: be to introduce a step where each signer needs to prove possession of the private key associated with its public key H1 : M → Zp (3) [34]. Bellare and Neven [35] (BN) proposed a secure multi- Each signer i has its own private/public key pair (ski , P ki ), signature scheme without a proof of possession, in the plain where ski is randomly chosen from Zp . For each key pair, the public key model, under the discrete logarithm assumption property P ki = ski · G1 holds. [31]. The participants commit first to their share Ri by prop- Let L = P k1 , P k2 , ..., P kn be the set of public keys of agating its hash to all other signers so they cannot calculate all possible signers during a specific round which, in the a function of it. Each signer computes a different challenge case of Elrond, is the set of public keys of all the nodes in for their partial signature. However, this scheme sacrifices the the consensus group. Below, the two stages of block signing public key aggregation. In this case, the verification of the process is presented: signing and verification. aggregated signature, requires the public key from each signer. Practical signing - Round 1 A recent paper by Gregory Maxwell et al. [29] proposes The leader of the consensus group creates a block with another multi-signature scheme in the plain public key model transactions, then signs and broadcasts this block to the [36], under the ’one more discrete logarithm’ assumption consensus group members. (OMDL). This approach improves the previous scheme [35] by reducing the communication rounds from 3 to 2, reintroducing Practical signing - Round 2 the key aggregation with a higher complexity cost. Each member of the consensus group (including the leader) BLS [4] is another interesting signature scheme, from the who receives the block must validate it, and if found valid, it Weil pairing, which bases its security on the Computational signs it with BLS and then sends the signature to the leader: Diffie-Hellman assumption on certain elliptic curves and gen- erates short signatures. It has several useful properties like Sigi = ski ∗ H0 (m) (4) batch verification, signature aggregation, public key aggrega- where Sigi is a point on g0 . tion, making BLS a good candidate for threshold and multi- signature schemes. Practical signing - Round 3 Dan Boneh, Manu Drijvers and Gregory Neven recently The leader waits to receive the signatures for a specific proposed a BLS multi-signature scheme [5], using ideas from timeframe. If it does not receive at least 32 · n + 1 signatures the previous work of [35], [30] to provide the scheme with in that timeframe, the consensus round is aborted. But if the defenses against rogue key attacks. The scheme supports leader does receive 23 · n + 1 or more valid signatures, it uses efficient verification with only two pairings needed to verify them to generate the aggregated signature: a multi-signature and without any proof of knowledge of the X secret key (works in the plain public key model). Another SigAgg = H1 (P ki ) · Sigi · B[i] (5) advantage is that the multi-signature can be created in only i two communication rounds. where SigAgg is a point on g0 . For traceability and security reasons, a consensus based on The leader then adds the aggregated signature to the block a reduced set of validators requires the public key from each together with the selected signers bitmap B, where a 1 signer. In this context, our analysis concludes that the most indicates that the corresponding signer in the list L had its appropriate multi-signature scheme for block signing in Elrond signature added to the aggregated signature SigAgg.

10 Practical verification • miniblock 1: containing cross-shard transactions with the Given the list of public keys L, the bitmap for the signers B, sender in shard 0 and destination in shard 1 the aggregated signature SigAgg, and a message m (block), • miniblock 2: containing cross-shard transactions with the verifier computes the aggregated public key: sender in shard 1 and destination in shard 0. These X transactions were already processed in the sender shard P kAgg = H1 (P ki ) · P ki · Bi (6) 1 and will be finalized after the processing also in the i current shard. The result, P kAgg, is a point on g1 . The final verification is There is no limitation on the number of miniblocks with e(G1 , SigAgg) == e(P kAgg, H0 (m)) (7) the same sender and receiver in one block. Meaning multiple miniblocks with the same sender and receiver can appear in where e is the pairing function. the same block. VII Cross-shard Execution 1 Processing Currently the atomic unit of processing in cross-shard For an in depth example of how the cross-shard transactions execution is a miniblock: either all the transactions of the are being executed and how the communication between miniblock are processed at once or none and the miniblock’s shards and the metachain occurs, we are simplifying the entire execution will be retried in the next round. process to just two shards and the metachain. Assuming that Our cross-shard transaction strategy uses and asynchronous a user generates a transaction from his wallet, which has an model. Validation and processing is done first in sender’s shard address in shard 0 and wants to send ERDs to another user that and then in receivers’ shard. Transactions are first dispatched has a wallet with an address in shard 1, the steps depicted in in the sender’s shard, as it can fully validate any transaction Fig. 4 are required for processing the cross-shard transaction. initiated from the account in this shard – mainly the current As mentioned in chapter V - Consensus via Secure Proof of balance. Afterwards, in the receivers’ shard, the nodes only Stake, the blocks structure is represented by a block Header need proof of execution offered by metachain, do signature that contains information about the block (block nonce, round, verification and check for replay attack and finally update proposer, validators timestamp etc), and a list of miniblocks the balance for the receiver, adding the amount from the for each shard that contain the actual transactions inside. Every transaction. miniblock contains all transactions that have either the sender Shard 0 processes both intra-shard transactions in miniblock in the current shard and the receiver in another shard or the 0 and a set of cross-shard transactions that have addresses from sender in a different shard and the destination in the current shard 1 as a receiver in miniblock 1. The block header and shard. In our case, for a block in shard 0, there will normally miniblocks are sent to the metachain. The metachain notarizes be 3 miniblocks: the block from shard 0, by creating a new metachain block • miniblock 0: containing the intrashard transactions for (metablock) that contains the following information about each shard 0 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 Fig. 7: Abstraction Layer for Smart Contracts 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- is extremely important for adoption purposes, due to the large tract transactions, as displayed in Fig. 5, any architecture number of smart contracts built on Ethereum’s platform. can use out of order scheduling. This means there are The Elrond Virtual Machine’s implementation will hide the no additional constraints on the time and place (shard) underlying architecture isolating the smart contract developers where a smart contract is executed. from system internals ensuring a proper abstraction layer, as 2) The second scenario refers to the parallelism induced by displayed in Fig. 7. the transactions that involve correlated smart contracts In Elrond, cross chain interoperability can be implemented [37]. This case, reflected in Fig. 6, adds additional by using an adapter mechanism at the Virtual Machine level as pressure on the performance and considerably increases proposed by Cosmos [38]. This approach requires specialized the complexity. Basically there must be a mechanism adapters and an external medium for communication between to ensure that contracts are executed in the right order adapter SC for each chain that will interoperate with Elrond. and on the right place (shard). To cover this aspect, The value exchange will be operated using some specialized Elrond protocol proposes a solution that assigns and smart contracts acting as asset custodians, capable of taking moves the smart contract to the same shard where their custody of adapted chain native tokens and issuing Elrond static dependencies reside. This way most, if not all SC native tokens. calls will have dependencies in the same shard and no cross-shard locking/unlocking will be needed. 1 VM Infrastructure Elrond focuses on the implementation of the Elrond Virtual Elrond builds its VM infrastructure on top of the K Frame- Machine, an EVM compliant engine. The EVM compliance work, 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 Fig. 5: Independent transaction processing under simple interpreters for the languages in question. More specifically, smart contracts that can be executed out of order 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, Elrond uses its own custom-built K Framework backend. 2 Smart contract languages One great advantage of the K Framework is that one can Fig. 6: Mechanism for correlated smart contracts that can be generate an interpreter for any language defined in K, without executed only sequentially the need for additional programming. This also means that interpreters produced this way are ”correct-by-construction”.

12 There are several smart contract languages specified in the K Framework already, or with their specifications under develop- ment. Elrond Network will support three low-level languages: IELE VM, KEVM, and WASM. • 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 Fig. 9: Elrond VM components it exists outside of the K framework [40]. Its purpose is to be human readable, fast, and to overcome some limitations of EVM. Elrond uses a slightly altered version 4 Smart contracts on the sharded architecture of IELE - most changes are related to account address management. Smart contract developers can program in Smart contracts on sharded architectures are still in the IELE directly, but most will choose to code in Solidity early stages of research and development and pose serious and then use a Solidity to IELE compiler, as can be seen challenges. Protocols like Atomix [7] or S-BAC [9] represent in Fig. 8. a starting point. Dynamic smart contract dependencies cannot • KEVM is a version of the Ethereum Virtual Machine be resolved by moving the SCs into the same shard, as at (EVM), written in K [41]. Certain vulnerabilities of EVM deployment time, not all the dependencies can be calculated. are fixed in the K version, or the vulnerable features are Solution currently research in the space: left out entirely. 1) A locking mechanism that allows the atomic execution • Web Assembly (WASM) is a binary instruction format of smart contract from different shards, ensures that the for a stack-based virtual machine, which can be used for involved SCs will be either all executed at the same running smart contracts. A WASM infrastructure enables time, or none at all. This requires multiple interaction developers to write smart contracts in C/C++, Rust, C#, messages and synchronization between consensuses of and others. different shards. [9] Having a language specification and generating the inter- 2) Cross-shard contract yanking proposal for Ethereum 2.0 preter is only half of the challenge. The other half is integrating would move that smart contract code and data into the the generated interpreter with the Elrond network. We have caller shard at the execution time. Atomic execution is built a common VM interface, that enables us to plug in any not needed, but the locking mechanism is mandatory VM into an Elrond node as shown in Fig. 9. Each VM then on the moved SC, which would block the execution has an adapter that implements this interface. Each contract is of SC for other transactions. The locking mechanism saved as bytecode of the VM for which it was compiled and is simpler, but it needs to transfer the whole internal runs on its corresponding VM. state of the SC. [43] Following Ethereum’s model, Elrond has the following 3 Support for formal modelling and verification transaction types: Because the smart contract languages are formally defined 1) SC construction and deployment: transactions receiver in K Framework, it is possible to perform formal verification address is empty and data field contains the smart of smart contracts written in these languages. To do this, it contract code as byte array; is necessary to also formally model their requirements, which 2) SC method invoking: transaction has a non empty re- can also be performed using the K Framework [42]. 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. Elrond’s approach to this problem is to use asynchronous cross-shard execution model in case of smart contracts. 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 account is created, with the balance from the transaction value Fig. 8: Elrond VM execution and the smart contract is called. After the execution, the smart contract might return results which affects a number

13 of accounts from different shards. All the results, which affect 6) The reshuffled nodes from the assigned node pool are in-shard accounts are executed in the same round. For those redistributed with higher ratios to shards’ waiting lists accounts which are not in the shard where the smart contract that will need to split in the next epoch ei+2 . was executed, transactions called Smart Contract Results will be created, saving the smart contract execution output for Rounds each of these accounts. SCR miniblocks are created for each Each round has a fixed time duration of 5 seconds (might destination shard. These miniblocks are notarized the same suffer updates after several testnet confirmation stages). During way as cross-shard transactions by metachain, then processed each round, a new block can be produced within every shard by the respective shards, where the accounts resides. In case by a randomly selected set of block validators (including one one smart contract calls dynamically another smart contract block proposer). From one round to another the set is changed from another shard, this call is saved as an intermediate result using the eligible nodes list, as detailed in the chapter IV. and treated the same as for accounts. As described before, the reconfiguration of shards within The solution has multiple steps and the finalization of a epochs and the arbitrary selection of validators within rounds cross-shard smart contract call will need at least 5 rounds, but discourages the creation of unfair coalitions, diminishes the it does not need locking and state movement across shards. possibility of DDoS and bribery attacks while maintaining decentralization and a high transactions throughput. IX Bootstrapping and Storage 2 Pruning 1 Timeline division A high throughput will lead to a distributed ledger Proof of Stake systems tend to generally divide timeline into that rapidly grows in size and increases bootstrapping cost epochs and each epoch into smaller rounds [19]. The timeline (time+storage), as highlighted in section XI.1. and terminology may differ between architectures but most of This cost can be addressed by using efficient pruning them use a similar approach. algorithms, that can summarize the blockchain’s full state in a more condensed structure. The pruning mechanism is similar Epochs to the stable checkpoints in pBFT [15] and compresses the In Elrond Protocol, each epoch has a fixed duration, initially entire ledger state. set to 24 hours (might suffer updates after several testnet con- Elrond protocol makes use of an efficient pruning algorithm firmation stages). During this timeframe, the configuration of [7] detailed below. Let us consider that e is the current epoch the shards remains unchanged. The system adapts to scalability and a is the current shard: demands between epochs by modifying the number of shards. To prevent collusion, after an epoch, the configuration of each 1) the shard nodes keep track of the account balances of e shard needs to change. While reshuffling all nodes between in a Merkle tree [44]; shards would provide the highest security level, it would affect 2) at the end of each epoch, the block proposer creates a the system’s liveness by introducing additional latency due to state block sb(a, e), which stores the hash of the Merkle bootstrapping. For this reason, at the end of each epoch, less tree’s root in the block’s header and the balances in the than 13 of the eligible validators, belonging to a shard will be block’s body; redistributed non-deterministically and uniformly to the other 3) validators verify and run consensus on sb(a, e); shards’ waiting lists. 4) if consensus is reached, the block proposer will store Only prior to the start of a new epoch, the validator sb(a, e) in the shard’s ledger, making it the genesis block distribution to shards can be determined, without additional for epoch e + 1; communication as displayed in Fig. 10. 5) at the end of epoch e + 1, nodes will drop the body of The node shuffling process runs in multiple steps: sb(a, e) and all blocks preceding sb(a, e). 1) The new nodes registered in the current epoch ei land Using this mechanism, the bootstrapping of the new nodes in the unassigned node pool until the end of the current should be very efficient. Actually, they start only from the epoch; last valid state block and compute only the following blocks 2) Less than 13 of the nodes in every shard are randomly instead of its full history. selected to be reshuffled and are added to the assigned node pool; X Security Evaluation 3) The new number of shards Nsh,i+1 is computed based on the number of nodes in the network ki and network 1 Randomness source usage; Elrond makes use of random numbers in its operation e.g. 4) Nodes previously in all shard’s waiting lists, that are cur- for the random sampling of block proposer and validators into rently synchronized, are added to the eligible validator’s consensus groups and the shuffling of nodes between shards lists; at the end of an epoch. Because these features contribute 5) The newly added nodes from the unassigned node pool to Elrond’s security guarantees, it is therefore important to are uniformly random distributed across all shards’ make use of random numbers that are provably unbiasable and waiting lists during epoch ei+1 ; unpredictable. In addition to these properties, the generation

14 Fig. 10: Shuffling the nodes at the end of each epoch of random numbers also needs to be efficient so that it can be block header as new randomness source, then broadcasts used in a scalable and high throughput blockchain architecture. this block to the consensus group. These properties can be found in some asymmetric cryptog- 3) Each member of the consensus group validates the raphy schemes, like the BLS signing scheme. One important randomness source as part of block validation, and sends property of BLS is that using the same private key to sign their block signature to the block proposer. the same message always produces the same results. This is 4) Block proposer aggregates the validators block signa- similar to what is achieved using ECDSA with deterministic tures and broadcasts the block with the aggregated block k generation and is due to the scheme not using any random signature and the new randomness source to the whole parameters: shard. sig = sk · H(m) (8) The evolution of randomness source in each round can be where H is a hashing function that hashes to points on the seen as an unbiasable and verifiable blockchain, where each used curve and sk is the private key. new random number can be linked to and verified against the previous random number. 2 Randomness creation in Elrond One random number is created in every round, and added 3 ”K” block finality scheme by the block proposer to every block in the blockchain. This The signed block at round n is final, if and only if blocks ensures that the random numbers are unpredictable, as each n + 1, n + 2, ..., n + k are signed. Furthermore, a final block random number is the signature of a different block proposer cannot be reverted. The metachain notarizes only final blocks over the previous randomness source. The creation of random to ensure that a fork in one shard does not affect other shards. numbers is detailed below as part of one consensus round: Shards only take into consideration the final metachain blocks, 1) New consensus group is selected using the randomness in order to not be affected if the metachain forks. Finality and source from the previous block header. Consensus group correctness is verified at block creation and at block validation is formed by a block proposer and validators. as well. The chosen k parameter is 1 and this ensures forks 2) The block proposer signs the previous randomness of maximum 2 blocks length. The probability that a malicious source with BLS, adds the signature to the proposed super majority (> 23 · n + 1) is selected in the shard for the

15 same round in the same consensus is 10−9 , even if 33% of across the other shards, to prevent collusion. This method adds the nodes from the shard are malicious. In that case they can bootstrapping overhead for the nodes that were redistributed, propose a block and sign it - let’s call it block m, but it will but doesn’t affect liveness as shuffled nodes do not participate not be notarized by the metachain. The metachain notarizes in the consensus in the epoch they have been redistributed. block m, only if block m + 1 is built on top of it. In order to The pruning mechanism will decrease this time to a feasible create block m + 1 the next consensus group has to agree with amount, as explained in section IX.2. block m. Only a malicious group will agree with block m, so the next group must have a malicious super majority again. 6 Consensus group selection As the random seed for group selection cannot be tampered After each round a new set of validators are selected using with, the probability of selecting one more malicious super the random seed of the last commited block, current round and majority group is 10−9 (5.38 · 10−10 , to be exact). The the eligible nodes list. In case of network desynchronization probability of signing two consecutive malicious blocks equals due to the delays in message propagation, the protocol has with selecting two subgroups with at least ( 23 · n + 1) members a recovery mechanism, and takes into consideration both the from the malicious group consequently. The probability for round r and the randomness seed from the last committed this is 10−18 . Furthermore, the consequently selected groups block in order to select new consensus groups every round. must be colluding, otherwise the blocks will not be signed. This avoids forking and allows synchronization on last block. The small time window (round time) in which the validators 4 Fisherman challenge group is known, minimizes the attack vectors. When one invalid block is proposed by a malicious majority, 7 Node rating the shard state root is tampered with an invalid result (after Beside stake, the eligible validator’s rating influences the including invalid changes to the state tree). By providing the chances to be selected as part of the consensus group. If the combined merkle proof for a number of accounts, an honest block proposer is honest and its block gets committed to the node could raise a challenge with a proof. The honest nodes blockchain, it will have its rating increased, otherwise, it’s will provide the block of transactions, the previous reduced rating will be decreased. This way, each possible validator merkle tree with all affected accounts before applying the is incentivized to be honest, run the most up-to-date client challenged block and the smart contract states, thus demon- software version, increase its service availability and thus strating the invalid transaction / state. If a challenge with the ensuring the network functions as designed. proof is not provided in the bounded time frame, the block is considered valid. The cost of one invalid challenge is the 8 Shard redundancy entire stake of the node which raised the challenge. The nodes that were distributed in sibling shards on the The metachain detects the inconsistency, either an invalid tree’s lowest level (see section IV.4) keep track of each other’s transaction, or an invalid state root, through the presented blockchain data and application state. By introducing the challenges and proofs. This can be traced and the consensus concept of shard redundancy, when the number of nodes in group can be slashed. At the same time the challenger can be the network decreases, some of the sibling shards will need rewarded with part of the slashed amount. Another problem to be merged. The targeted nodes will instantly initiate the is when a malicious group hides the invalid block from other process of shard merging. nodes - non-malicious ones. However, by making it mandatory for the current consensus to propagate the produced block to XI Understanding the real problems the sibling shard and to the observer nodes, the data cannot 1 Centralized vs Decentralized be hidden anymore. The communication overhead is further Blockchain was initially instantiated as an alternative to reduced by sending only the intrashard miniblock to the sibling the centralized financial system of systems [45]. Even if the shard. The cross shard miniblocks are always sent on different freedom and anonymity of distributed architectures remains an topics accessible by interested nodes. In the end, challenges undisputed advantage, the performance has to be analyzed at can be raised by multiple honest nodes. Another security pro- a global scale in a real-world environment. tection is given by the setup of P2P topics. The communication The most relevant metric measuring performance is transac- from one shard toward the metachain is done through a defined tions per second (TPS), as seen in Table 2. A TPS comparison set of topics / channels, which can be listened to by any of traditional centralized systems with decentralized novel honest validator - the metachain will not accept any other architectures that were validated as trusted and efficient on messages from other channels. This solution introduces some a large scale, reflects an objective yet unsettling reality [46], delay in the metachain only in case of challenges, which are [47], [48], [49]. very low in number and highly improbable since if detected The scalability of blockchain architectures is a critical (high probability of being detected) the nodes risk their entire but still unsolved problem. Take, for instance, the example stake. determining the data storage and bootstrapping implications of current blockchain architectures suddenly functioning at Visa 5 Shard reorganization level throughput. By performing such exercises, the magnitude After each epoch, less than 31 · n of the nodes from each of multiple secondary problems becomes obvious (see Fig. shard are redistributed uniformly and non-deterministically 11).

16 Archi- TPS TPS System size Type Dispersion tecture (average) (max limit) Expanding the number of nodes in existing validated archi- Distributed tectures forces a serious performance degradation and induces VISA Centralized 3500 55000 virtualization a higher computational price that must be paid. Sharding Distributed seems to be a good approach, but the shard size plays a Paypal Centralized 200 450 virtualization major role. Smaller shards are agile but more likely to be Private affected by malicious groups, bigger shards are safer, but their Ripple Permissioned 1500 55000 Blockchain reconfiguration affects the system liveness. Private NEO Mixed 1000 10000 Blockchain Transaction volume Public With a higher relevance compared to the others, the last item Ethereum Decentralized 15 25 Blockchain on the list represents the transaction processing performance. Public In order to correctly measure the impact of this criteria, this Bitcoin Decentralized 2 7 Blockchain must be analyzed considering the following two standpoints: • C1 transaction throughput - how many transactions a TABLE 2: Centralized vs Decentralized TPS comparison system can process per time unit, known as TPS, an output of a system [51]; • C2 transaction finality - how fast one particular trans- XII The blockchain performance paradigm action is processed, referring to the interval between its The process of designing distributed architectures on launch and its finalization - an input to output path. blockchain faces several challenges, perhaps one of the most C1. T ransaction throughput in single chain architectures is challenging being the struggle to maintain operability under very low and can be increased by using workarounds such contextual pressure conditions. The main components that as sidechain [52]. In a sharded architecture like ours, the determine the performance pressure are: transaction throughput is influenced by the number of shards, • complexity the computing capabilities of the validators/block proposers • system size and the messaging infrastructure [8]. In general, as displayed • transaction volume in Fig. 13, this goes well to the public, but despite the importance of the metric, it provides only a fragmented view. Complexity C2. T ransaction f inality - A more delicate aspect that The first element that limits the system performance, is the emphasizes that even if the system may have a throughput of consensus protocol. A more complicated protocol determines 1000 TPS, it may take a while to process a particular transac- a bigger hotspot. In PoW consensus architectures a big perfor- tion. Beside the computing capabilities of the validators/block mance penalty is induced by the mining complexity that aims proposers and the messaging infrastructure, the transaction to keep the system decentralized and ASIC resilient [50]. To finality is mainly affected by the dispatching algorithm (when overrun this problem PoS makes a trade-off, simplifies the the decision is made) and the routing protocol (where should network management by concentrating the computing power the transaction be executed). Most of the existing state of the to a subset of the network, but yields more complexity on the art architectures refuse to mention this aspect but from a user control mechanism. standpoint this is extremely important. This is displayed in Fig. 11: Storage Estimation - Validated distributed architectures working at an average of VISA TPS

17 Fig. 13: Transaction throughput Fig. 14: Transaction finality Fig. 14, where the total time required to execute a certain 2 Ongoing and future research transaction from start to end is considered. In Elrond, the dispatching mechanism (detailed in section V) Our team is constantly re-evaluating and improving Elrond’s allows an improved time to finality by routing the transactions design, in an effort to make this one of the most com- directly to the right shard, mitigating the overall delays. pelling public blockchain architectures; solving scalability via adaptive state sharding, while maintaining security and high energy efficiency through a secure Proof of Stake consensus mechanism. Some of our next directions of improvement XIII Conclusion include: 1 Performance 1) Reinforcement learning: we aim to increase the ef- ficiency of the sharding process by allocating the fre- Performance tests and simulations, presented in Fig. 12, quently trading clients in the same shard to reduce the reflect the efficiency of the solution as a highly scalable overall cost; distributed ledger. As more and more nodes join the network 2) AI supervision: create an AI supervisor that detects our sharding approach shows a linearly increasing throughput. malicious behavioral patterns; it is still uncertain how The chosen consensus model involves multiple communication this feature can be integrated in the protocol without rounds, thus the result is highly influenced by the network disrupting the decentralization; quality (speed, latency, availability). Simulations using our 3) Reliability as a consensus factor: the existing protocol testnet using worldwide network speed averages, at its max- weighs between stake and rating but we plan to add imum theoretical limit, suggest Elrond exceeds the average reliability, as a metric that should be computed in a VISA level with just 2 shards, and approaches peak VISA distributed manner after applying a consensus protocol level with 16 shards. on previously submitted blocks from the very recent Fig. 12: Network throughput measured in transactions per seconds with a global network speed of 8 MB/s

18 history; [11] “Solidity — Solidity 0.4.21 documentation.” [Online]. Available: 4) Cross-chain interoperability: implements and con- https://solidity.readthedocs.io/en/v0.4.21/ [12] “web3j,” 2018. [Online]. Available: https://github.com/web3j tribute to standards like those initiated by the De- [13] “Casper,” 2018. [Online]. Available: http://ethresear.ch/c/casper centralized Identity Foundation [53] or the Blockchain [14] “The State of Ethereum Scaling, March 2018 – Highlights from Interoperability Alliance [54]; EthCC on Plasma Cash, Minimum Viable Plasma, and More. . . – Medium,” 2018. [Online]. Available: https://medium.com/loom-network/ 5) Privacy preserving transactions: use Zero-Knowledge the-state-of-ethereum-scaling-march-2018-74ac08198a36 Succinct Non-Interactive Argument of Knowledge [55] [15] M. Castro and B. Liskov, “Practical Byzantine Fault Tolerance,” to protect the identity of the participants and offer in Proceedings of the Third Symposium on Operating Systems Design and Implementation, ser. OSDI ’99. Berkeley, CA, USA: auditing capabilities while preserving the privacy. USENIX Association, 1999, pp. 173–186. [Online]. Available: http://dl.acm.org/citation.cfm?id=296806.296824 3 Overall Conclusions [16] Y. Jia, “Op Ed: The Many Faces of Sharding for Blockchain Scalability,” 2018. [Online]. Available: https://bitcoinmagazine.com/ Elrond is the first highly scalable public blockchain that articles/op-ed-many-faces-sharding-blockchain-scalability/ uses the newly proposed Secure Proof of Stake algorithm [17] “Using Merklix tree to shard block validation | Deadalnix’s in a genuine state-sharded architecture to achieve VISA den,” 2016. [Online]. Available: https://www.deadalnix.me/2016/11/06/ using-merklix-tree-to-shard-block-validation/ level throughput and confirmation times of seconds. Elrond’s [18] S. Nakamoto, “Bitcoin: A Peer-to-Peer Electronic Cash System,” p. 9, novel approach on adaptive state sharding improves on Om- 2008. niledger’s proposal increasing security and throughput, while [19] “Why we are building Cardano - Introduction.” [Online]. Available: https://whycardano.com/ the built-in automatic transaction routing and state redundancy [20] “Constellation - a blockchain microservice operating system - White mechanisms considerably reduce latencies. By using a shard Paper,” 2017, original-date: 2018-01-05T20:42:05Z. [Online]. Available: pruning technique the bootstrapping and storage costs are https://github.com/Constellation-Labs/Whitepaper [21] “Bitshares - Delegated Proof-of-Stake Consensus,” also considerably reduced compared to other approaches. The 2014. [Online]. Available: https://bitshares.org/technology/ newly introduced Secure Proof of Stake consensus algorithm delegated-proof-of-stake-consensus/ ensures distributed fairness and improves on Algorand’s idea [22] dantheman, “DPOS Consensus Algorithm - The Missing White Paper,” May 2017. [Online]. Available: https://steemit.com/dpos/@dantheman/ of random selection, reducing the time needed for the random dpos-consensus-algorithm-this-missing-white-paper selection of the consensus group from 12 seconds to 100 [23] “EOS.IO Technical White Paper v2,” 2018, original-date: 2017- ms. Our method of combining state sharding and the very 06-06T07:55:17Z. [Online]. Available: https://github.com/EOSIO/ Documentation/blob/master/TechnicalWhitePaper.md efficient Secure Proof of Stake consensus algorithm has shown [24] C. Paar and J. Pelzl, Understanding Cryptography: A Textbook for promising results in our initial estimations, validated by our Students and Practitioners. Berlin Heidelberg: Springer-Verlag, 2010. latest testnet results. [Online]. Available: //www.springer.com/gp/book/9783642041006 [25] C. Schnorr, “Efficient signature generation by smart cards,” Journal of Cryptology, vol. 4, pp. 161–174, Jan. 1991. References [26] K. Michaelis, C. Meyer, and J. Schwenk, “Randomly Failed! [1] G. Hileman and M. Rauchs, “2017 Global Cryptocurrency The State of Randomness in Current Java Implementations,” in Benchmarking Study,” Social Science Research Network, Rochester, Topics in Cryptology – CT-RSA 2013, ser. Lecture Notes in NY, SSRN Scholarly Paper ID 2965436, Apr. 2017. [Online]. Available: Computer Science. Springer, Berlin, Heidelberg, Feb. 2013, pp. https://papers.ssrn.com/abstract=2965436 129–144. [Online]. Available: https://link.springer.com/chapter/10.1007/ [2] “The Ethereum Wiki - Sharding FAQ,” 2018, original-date: 2014-02- 978-3-642-36095-4 9 14T23:05:17Z. [Online]. Available: https://github.com/ethereum/wiki/ [27] D. J. Bernstein, P. Birkner, M. Joye, T. Lange, and C. Peters, “Twisted wiki/Sharding-FAQ Edwards Curves,” in Progress in Cryptology – AFRICACRYPT [3] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich, “Algorand: 2008, ser. Lecture Notes in Computer Science. Springer, Berlin, Scaling Byzantine Agreements for Cryptocurrencies,” in Proceedings of Heidelberg, Jun. 2008, pp. 389–405. [Online]. Available: https: the 26th Symposium on Operating Systems Principles, ser. SOSP ’17. //link.springer.com/chapter/10.1007/978-3-540-68164-9 26 New York, NY, USA: ACM, 2017, pp. 51–68. [Online]. Available: [28] A. Poelstra, “Schnorr Signatures are Non-Malleable in the Random http://doi.acm.org/10.1145/3132747.3132757 Oracle Model,” 2014. [Online]. Available: https://download.wpsoftware. [4] D. Boneh, B. Lynn, and H. Shacham, “Short signatures from the weil net/bitcoin/wizardry/schnorr-mall.pdf pairing,” in Advances in Cryptology – ASIACRYPT ’01, LNCS. Springer, [29] C. Decker and R. Wattenhofer, “Bitcoin Transaction Malleability and 2001, pp. 514–532. MtGox,” arXiv:1403.6676 [cs], vol. 8713, pp. 313–326, 2014, arXiv: [5] D. Boneh, M. Drijvers, and G. Neven, “Compact multi-signatures for 1403.6676. [Online]. Available: http://arxiv.org/abs/1403.6676 smaller blockchains,” in Advances in Cryptology – ASIACRYPT 2018, [30] G. Maxwell, A. Poelstra, Y. Seurin, and P. Wuille, “Simple Schnorr ser. Lecture Notes in Computer Science, vol. 11273. Springer, 2018, Multi-Signatures with Applications to Bitcoin,” Tech. Rep. 068, 2018. pp. 435–464. [Online]. Available: https://eprint.iacr.org/2018/068 [6] V. Buterin, “Ethereum: A Next-Generation Smart Contract and [31] Y. Seurin, “On the Exact Security of Schnorr-Type Signatures Decentralized Application Platform,” 2013. [Online]. Available: https: in the Random Oracle Model,” in Advances in Cryptology – //www.ethereum.org/pdfs/EthereumWhitePaper.pdf EUROCRYPT 2012, ser. Lecture Notes in Computer Science. Springer, [7] E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta, Berlin, Heidelberg, Apr. 2012, pp. 554–571. [Online]. Available: and B. Ford, “OmniLedger: A Secure, Scale-Out, Decentralized https://link.springer.com/chapter/10.1007/978-3-642-29011-4 33 Ledger via Sharding,” Tech. Rep. 406, 2017. [Online]. Available: [32] K. Itakura and K. Nakamura, “A public-key cryptosystem suitable for https://eprint.iacr.org/2017/406 digital multisignatures,” 1983. [8] “The ZILLIQA Technical Whitepaper,” 2017. [Online]. Available: [33] S. Micali, K. Ohta, and L. Reyzin, “Accountable-subgroup https://docs.zilliqa.com/whitepaper.pdf Multisignatures: Extended Abstract,” in Proceedings of the 8th [9] M. Al-Bassam, A. Sonnino, S. Bano, D. Hrycyszyn, and G. Danezis, ACM Conference on Computer and Communications Security, ser. “Chainspace: A Sharded Smart Contracts Platform,” arXiv:1708.03778 CCS ’01. New York, NY, USA: ACM, 2001, pp. 245–254. [Online]. [cs], Aug. 2017, arXiv: 1708.03778. [Online]. Available: http: Available: http://doi.acm.org/10.1145/501983.502017 //arxiv.org/abs/1708.03778 [34] T. Ristenpart and S. Yilek, “The Power of Proofs-of-Possession: [10] G. Wood, “Ethereum: A Secure Decentralised Generalised Securing Multiparty Signatures against Rogue-Key Attacks,” in Transaction Ledger,” 2017. [Online]. Available: https://ethereum. Advances in Cryptology - EUROCRYPT 2007, ser. Lecture Notes github.io/yellowpaper/paper.pdf in Computer Science. Springer, Berlin, Heidelberg, May 2007, pp.

19 228–245. [Online]. Available: https://link.springer.com/chapter/10.1007/ 978-3-540-72540-4 13 [35] M. Bellare and G. Neven, “Multi-signatures in the Plain public-Key Model and a General Forking Lemma,” in Proceedings of the 13th ACM Conference on Computer and Communications Security, ser. CCS ’06. New York, NY, USA: ACM, 2006, pp. 390–399. [Online]. Available: http://doi.acm.org/10.1145/1180405.1180453 [36] D.-P. Le, A. Bonnecaze, and A. Gabillon, “Multisignatures as Secure as the Diffie-Hellman Problem in the Plain Public-Key Model,” in Pairing-Based Cryptography – Pairing 2009, ser. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, Aug. 2009, pp. 35–51. [Online]. Available: https://link.springer.com/chapter/10.1007/ 978-3-642-03298-1 3 [37] T. Dickerson, P. Gazzillo, M. Herlihy, and E. Koskinen, “Adding Concurrency to Smart Contracts,” in Proceedings of the ACM Symposium on Principles of Distributed Computing, ser. PODC ’17. New York, NY, USA: ACM, 2017, pp. 303–312. [Online]. Available: http://doi.acm.org/10.1145/3087801.3087835 [38] J. Kwon and E. Buchman, “Cosmos Network - Internet of Blockchains,” 2017. [Online]. Available: https://cosmos.network/whitepaper [39] G. Ros, u and T. F. S, erbănută, “An overview of the k semantic frame- work,” The Journal of Logic and Algebraic Programming, vol. 79, no. 6, pp. 397–434, 2010. [40] T. Kasampalis, D. Guth, B. Moore, T. Serbanuta, V. Serbanuta, D. Fi- laretti, G. Rosu, and R. Johnson, “Iele: An intermediate-level blockchain language designed and implemented using formal semantics,” Tech. Rep., 2018. [41] E. Hildenbrandt, M. Saxena, X. Zhu, N. Rodrigues, P. Daian, D. Guth, and G. Rosu, “Kevm: A complete semantics of the ethereum virtual machine,” Tech. Rep., 2017. [42] “How Formal Verification of Smart Contracts Works | RV Blog.” [Online]. Available: https://runtimeverification.com/blog/ how-formal-verification-of-smart-contracts-works/ [43] “Cross-shard contract yanking.” [Online]. Available: https://ethresear. ch/t/cross-shard-contract-yanking/1450 [44] R. C. Merkle, “A Certified Digital Signature,” in Advances in Cryptology — CRYPTO’ 89 Proceedings, ser. Lecture Notes in Computer Science. Springer, New York, NY, Aug. 1989, pp. 218–238. [Online]. Available: https://link.springer.com/chapter/10.1007/0-387-34805-0 21 [45] A. Veysov and M. Stolbov, “Financial System Classification: From Conventional Dichotomy to a More Modern View,” Social Science Research Network, Rochester, NY, SSRN Scholarly Paper ID 2114842, Jul. 2012. [Online]. Available: https://papers.ssrn.com/abstract=2114842 [46] “XRP - The Digital Asset for Payments.” [Online]. Available: https://ripple.com/xrp/ [47] “Visa - Annual Report 2017,” 2018. [Online]. Avail- able: https://s1.q4cdn.com/050606653/files/doc financials/annual/2017/ Visa-2017-Annual-Report.pdf [48] “PayPal Reports Fourth Quarter and Full Year 2017 Results (NASDAQ:PYPL),” 2018. [Online]. Available: https://investor. paypal-corp.com/releasedetail.cfm?releaseid=1055924 [49] M. Schwarz, “Crypto Transaction Speeds 2018 - All the Major Cryptocurrencies,” 2018. [Online]. Available: https://www.abitgreedy. com/transaction-speed/ [50] “The Ethereum Wiki - Mining,” 2018, original-date: 2014-02- 14T23:05:17Z. [Online]. Available: https://github.com/ethereum/wiki/ wiki/Mininghttps://github.com/ethereum/wiki [51] “Transaction throughput.” [Online]. Available: https://docs.oracle.com/ cd/E17276 01/html/programmer reference/transapp throughput.html [52] W. Martino, M. Quaintance, and S. Popejoy, “Chainweb: A Proof- of-Work Parallel-Chain Architecture for Massive Throughput,” 2018. [Online]. Available: http://kadena.io/docs/chainweb-v15.pd [53] “DIF - Decentralized Identity Foundation.” [Online]. Available: http://identity.foundation/ [54] H. I. World, “Blockchain Interoperability Alliance: ICON x Aion x Wanchain,” Dec. 2017. [Online]. Available: https://medium.com/helloiconworld/ blockchain-interoperability-alliance-icon-x-aion-x-wanchain-8aeaafb3ebdd [55] S. Goldwasser, S. Micali, and C. Rackoff, “The Knowledge Complexity of Interactive Proof-systems,” in Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, ser. STOC ’85. New York, NY, USA: ACM, 1985, pp. 291–304. [Online]. Available: http://doi.acm.org/10.1145/22145.22178