Technical Whitepaper Harmony Team Version 2.0 1. Introduction Since the publication of the Bitcoin whitepaper in2008, theconcept of blockchainhasspread acrosstheworld.Whiledecentralizedmoneyandapplicationsarebecomingwell-publicizedideas, design limitationshavechallengedthecoreaspirationof Bitcoin. Theoriginal Bitcoinblockchain wasdesignedasapeer-to-peerpaymentsystem[13]thatallowspeopletotransfervaluewithout intermediaries like banks or payment processors. However, as Bitcoin gained popularity, its perance bottleneck became evident due to its limited throughput of 7transactions per second TPS, and its cost as a payment system became prohibitively expensive. In 2014, Buterin et. al. [27] proposeda newblockchain infrastructure calledEthereum, which enableddevelopers tocreate various kinds of blockchain applications using“smart contracts.” However, Ethereumdidn’t solvethescalabilityproblemand, withits15TPS, failedtosupport high-throughput applications such as gaming or decentralized exchanges. GivenEthereumandBitcoin’sperancelimitations,manyblockchainprojectsproposedvarious solutions [3,4,5,6,7,8,9,10,24,25] that attempt to increase transaction throughput. Various blockchains [3,4,5,6,24,25] proposed to replace Proof-of-Work PoW consensus with Proof-of-StakePoSconsensus.OtherblockchainslikeEOSuseDelegatedProofofStakeDPoS, where block proposers are electedby votingrather than by an on-chain algorithmic process. ProjectslikeIOTAreplacedthechain-of-blocksdatastructurewithaDAGDirectedAcyclicGraph data structure, which breaks the limitation of sequential processing of transactions. However,theseproposedsolutionscannotmakesignificantperancegainswithoutsacrificing other critical aspects, such as security and decentralization. The scalability solution that both preservessecurityanddecentralizationissharding, whichcreatesmultiplegroupsi.e.shardsof validators and lets themprocess transactions concurrently. As a result, the total transaction throughput increases linearly as the number of shards grows. Zilliqa [12] was the first public blockchain that proposed to address the scalability problemwith sharding. However, Zilliqas shardingapproachfallsshortintwoways.First,itdoesnotdividethestorageofblockchaindata statesharding. Thispreventsmachineswithlimitedresourcesfromparticipatinginthenetwork, thuscurtailingdecentralization.Second,Zilliqa’sshardingprocessissusceptibletoasingle-shard takeover attack due to its reliance on PoW as its randomness generation mechanism. We introduce Harmony, the next generation sharding-based blockchain that is fully scalable, provablysecure,andenergyefficient.Harmonyaddressestheproblemsofexistingblockchainsby combining the best research results and engineering practice in an optimally tuned system. Specifically, Harmony makes breakthroughs in following aspects ● Fully Scalable Harmony shards not only the network communication andtransaction validation like Zilliqa, but alsoshards the blockchain state. This makesHarmonyafully scalable blockchain. 1 ● Secure Sharding Harmony’s sharding process is provably secure thanks to the distributed randomness generation DRG process which is unpredictable, unbiaseable, verifiableandscalable.Harmonyalsoreshardsthenetworkinanon-interruptivemannerto prevent against slowly adaptive byzantine adversaries. ● Efficient and Fast Consensus Unlikeother sharding-basedblockchainswhichrequire PoWtoselectvalidators,HarmonyisbasedonPoSandthusenergyefficient.Consensus is reached with a linearly scalable BFT algorithm that’s 100 times faster than PBFT. ● Adaptive-Thresholded PoS ​The threshold of stakes required for a node tojoin the networkisadjustedbasedonthevolumeof total stakinginawaythatmaliciousstakers cannotconcentratetheirpowerinasingleshard.Moreover,thethresholdislowenoughso that small stakers can still participate in the network and earn rewards. ● Scalable Networking Infrastructure With RaptorQ fountain code, Harmony can propagate blocks quickly within shards or across network by using the Adaptive Ination Dispersal Algorithm. Harmony alsoadopts Kademlia routing[37] toachieve cross-shard transactions that scale logarithmically with the number of shards. ● Consistent Cross-Shard Transactions ​Harmony supports cross-shard transactions withshardsdirectlycommunicatingwitheachother.Anatomiclockingmechanismisused to ensure the consistency of cross-shard transactions. By innovating on both the protocol and network layers, Harmony provides the world with a scalable and secure blockchain system that is able to support the emerging decentralized economy. Harmony will enable applications which were not previously feasible on blockchain, including high-volume decentralized exchanges, interactive fair games, Visa-scale payment systems, andInternet-of-Thingstransactions. Harmonystrivestoscaletrustforbillionsofpeople and create a radically fair economy. 2. Consensus Mechanism Theconsensusprotocol isakeycomponent of anyblockchain. It determineshowsecurelyand quicklyblockchainvalidators reachconsensusonthenextblock.Thefirstblockchainconsensus 1protocol which powers Bitcoin is Proof-of-Work PoW consensus. PoWis aprocesswhereby minersracetofindthesolutiontoacryptographicpuzzlethewinnergetstherighttoproposethe next blockandearnssometokenrewards.PoW’ssecurityassumptionisthatmorethan50of thehashingpoweriscontrolledbyhonestnodes.Withsuchanassumption,theruleforconsensus is that the longest chain will be the canonical one, and thus PoWconsensus is alsocalled chain-based consensus​. Anothertypeofconsensusprotocol,onewhichhasbeenresearchedorethantwodecades inacademia,iscalledPBFTPracticalByzantineFaultTolerance[14].InPBFT,onenodeiselected as the “leader,” while the rest of the nodes are “validators.” Each roundof PBFTconsensus 1 The machines that support the blockchain network by validating transactions and reaching consensus. 2 involvestwomajor phases thepreparephaseandthecommitphase.Inthepreparephase,the leader broadcasts its proposal toall of thidators, whointurnbroadcast their votesonthe proposal toeveryoneelse. Thereasonfortherebroadcastingtoallvalidatorsisthatthevotesof eachvalidator needtobecountedbyallothervalidators.Thepreparephasefinisheswhenmore than consistentvotesareseen,where isthenumberofmaliciousvalidators,andthetotal f2 1 f number ofvalidatorsplustheleaderis .Thecommitphaseinvolvesasimilarvotecounting f3 1 process, and consensus is reached when consistent votes are seen. Due to the f2 1 rebroadcastingof votesamongvalidators,PBFThas communicationcomplexity,whichis N O 2 not scalable for a blockchain system with hundreds or thousands of nodes. Asanimprovement onPBFT[14], Harmony’sconsensusprotocol islinearlyscalableintermsof communication complexity, andthus we call it Fast ByzantineFault ToleranceFBFT. InFBFT, insteadof askingall validatorstobroadcast their votes, theleaderrunsamulti-signaturesigning processtocollect thidators’ votesina -sizedmulti-signatureandthenbroadcastit.So 1O instead of receiving signatures, each validator receives only one multi-signature, thus NO reducing the communication complexity from to .N O 2 NO The idea of using -sizedmulti-signatureisinspiredbyByzCoin’sBFT[15] whichusesthe 1O Schnorr signature scheme for constant-sizedmulti-signatureaggregationandsamulticast tree among validators to facilitate the message delivery. However, a Schnorr multi-signature requires a secret commitment round, which leads to a total of two round-trips for a single multi-signature. Harmony improves upon that by using BLS Boneh–Lynn–Shacham multi-signature[28],whichonlyrequiresoneround-trip.Therefore,FBFTisatleast50fasterthan ByzCoin’s BFT. Besides, Harmony adopts RaptorQ fountain code to speed up the block broadcastingprocessdiscussedin6.2.Thefountaincodebroadcastingtechniquealsoavoidsa security issue in ByzCoin’s original tree-based multicasting design [16,17]. Figure 1. Network communication during a single round of consensus. Specifically, Harmony’s FBFT consensus involves the following steps 3 1. The leader constructs the newblockandbroadcaststheblockheader toall validators. Meanwhile, the leader broadcasts the content of the block witherasurecodingdetails discussed in 6.2. This is called the “announce” phase. 2. The validators check thidityof theblockheader, signtheblockheader withaBLS signature, and send the signature back to the leader. 3. The leader waits for at least validsignaturesfromvalidatorsincludingtheleader f2 1 itself andaggregates themintoa BLSmulti-signature. Then theleader broadcaststhe aggregatedmulti-signature alongwith a bitmapindicatingwhichvalidatorshavesigned. Together with Step 2, this concludes the “prepare” phase of PBFT. 4. The validators check that the multi-signature has at least signers, verify the f2 1 transactionsintheblockcontentbroadcastedfromtheleaderinStep1,signthereceived message from Step 3, and send it back to the leader. 5. Theleader waitsfor at least validsignaturescanbedifferentsignersfromStep3 f2 1 fromStep4, aggregatesthemtogether intoaBLSmulti-signature,andcreatesabitmap logging all the signers. Finally, the leader commits the new block with all the multi-signaturesandbitmapsattached,andbroadcaststhenewblockforallvalidatorsto commit. Together with Step 4, this concludes the “commit” phase of PBFT. ThidatorsofHarmony’sconsensusareelectedbasedonProof-of-Stake.Therefore,theactual protocoldiffersslightlyfromtheonedescribedaboveinasensethatavalidatorwithmorevoting shareshasmorevotesthanothers,ratherthanone-signature-one-vote.Soinsteadofwaitingforat least signatures fromvalidators, the leader waits for signatures fromthidatorswho f2 1 collectively possess at least voting shares. The details of the proof-of-stake election f2 1 mechanism will be discussed in 3.3. 3. Sharding Blockchainshardingasascalabilitysolutionhasgainedlotsofattentionsincelate2017.Various sharding solutions have been proposed both in industry and academia. Inindustry,Zilliqa[12]wasthefirstsharding-basedpublicblockchainthatclaimedathroughputof 2,800 TPS. Zilliqa uses PoWas identity registration process i.e. Sybil attack [1] prevention. Zilliqa’snetworkcontainsasingledirectory-servicecommitteeandmultipleshardcommitteei.e. network sharding​, each containinghundreds of nodes. Transactions are assignedtodifferent shardsandprocessedseparatelyi.e. ​transaction sharding​. Theresultingblocksfromallshards arecollectedandmergedatthedirectory-servicecommittee.Zilliqaisnota​stateshardingsolution because each node has to hold the entire blockchain state to be able to process transactions. In academia, publications like Omniledger [8] andRapidChain[7] haveproposedsolutionsthat feature ​state sharding where each shard holds a subset of the blockchain state. Omniledger employsamulti-partycomputationschemecalledRandHound[25]togenerateasecurerandom number, which is used to randomly assign nodes intoshards. Omniledger assumes a ​slowly 4 adaptive ​corruptionmodelwhereattackerscancorruptagrowingportionofthenodesinashard over time. Under such security model, a singleshardcanbecorruptedeventually. Omniledger preventsthecorruptionofshardsbyreshufflingallnodesintheshardsatafixedtimeintervalcalled epoch​. RapidChainbuildsontopof Omniledger andproposestheuseof the​Bounded Cuckoo Rule​ to reshuffle nodes without interruptions [19]. Harmonydrawsinspirationfromthesethreeprevioussolutions[7,8,12]anddesignsaPoS-based full shardingscheme that’s linearly scalable andprovably secure. Harmony contains abeacon chainandmultipleshardchains.Thebeaconchainservesastherandomnessbeaconandidentity register, while the shard chains store separate blockchain states and process transactions concurrently. Harmonyproposesanefficient algorithmfor randomnessgenerationbycombining VerifiableRandomFunctionVRFandVerifiableDelayFunctionVDF.Harmonyalsoincorporates PoSintheshardingprocesswhichshiftsthesecurityconsiderationofashardfromtheminimum number of nodes [7,8,12] to the minimum number of voting shares. 3.1 Distributed Randomness Generation Background Variousapproacheshavebeenproposedtoassignnodesintoshardssuchasrandomness-based sharding[7,8], location-basedsharding[34], andcentrally-controlledsharding[35].Outofallthe approaches, randomness-basedshardinghas beenrecognizedasthemost securesolution. In randomness-basedsharding,amutuallyagreedrandomnumberisusedtodeterminethesharding assignment for each node. The random number must have the following properties 1. Unpredictable No one should be able to predict the random number before it is generated. 2. UnbiaseableTheprocessofgeneratingtherandomnumbershouldnotbebiasablebyany participant. 3. Verifiable The validity of the generated random number should be verifiable by any observer. 4. Scalable The algorithmof randomness generation should scale toa large number of participants. Omniledger[8]usestheRandHound[25]protocol,whichisaleader-drivendistributedrandomness generation DRG process that involves PVSSPubliclyVerifiableSecret Sharing andByzantine Agreement.RandHoundisan protocolthatdividesparticipantnodesintomultiplegroups n O *c2 of size . It achieves the first three properties above but is impractically slow to qualify as scalable.c RapidChain[7]takesasimplerapproachbylettingeachparticipantperVSSVerifiableSecret Sharing [22] andusingthecombinedsecret sharesastheresultingrandomn