Applied Science, Faculty of
Engineering, School of (Okanagan)
DSpace
UBCO
Niu, Jianyu
Doctor of Philosophy - PhD
University of British Columbia
Bitcoin also known as the first-generation blockchain protocol, has suffered from scalability barriers. For example, Bitcoin can only process $7$ transactions per second, and users have to wait up to one hour to confirm transactions. To address this, Ethereum, Bitcoin-NG, and HotStuff (also known as the next-generation blockchains) are proposed. Each protocol represents an elegant approach and has further influenced many subsequent blockchain protocols. Informally speaking, Ethereum promotes Bitcoin's scalability by elaborately tuning system parameters (e.g., block production rate); Bitcoin-NG achieves better scalability by decoupling Bitcoin's blockchain operation into two planes: leader election and transaction serialization; HotStuff differs from Bitcoin by renovating classic Byzantine fault tolerance (BFT) consensus protocol. However, the security and performance of these protocols have not been fully explored in the literature. Specifically, Ethereum introduces the so-called uncle and nephew rewards on top of the (standard) block rewards used in Bitcoin, making the analysis of the selfish mining attack in Bitcoin hard to be directly applied to Ethereum. This calls for new analysis. In this dissertation, a 2-dimensional Markov process is proposed to model the selfish mining attack. Besides, a probabilistic reward computing method is used to tracks block rewards. Bitcoin-NG relies on two types of blocks (namely, key blocks and microblocks) to realize the leader election and transaction serialization. However, an in-depth incentive analysis is still missing to evaluate the impact of these types of blocks under network capacity constraints. To address this, the interval between two consecutive key blocks is modeled as an exponential random variable, and the generation rate of microblocks is introduced to capture the impact of network capacity. Besides, a Markov decision process (MDP) model is used to jointly analyze the incentive of key blocks and microblock. HotStuff leverages the chain structure and pipelining techniques to simplify BFT protocol design, which, unfortunately, introduces new attacks to deteriorate the system performance. To evaluate these attacks, a multi-metric evaluation framework including chain growth rate, chain quality, and latency is proposed. Besides, two attacks, namely the forking attack and delay attack, are systematically studied. With the framework, some engineering designs in DiemBFT, a variant of HotStuff used in Facebook's Diem blockchain, are also evaluated.
On the Security and Performance ofNext-Generation BlockchainsbyJianyu NiuM.A.Sc., Northwestern Polytechnical University, 2017B.Sc., Northwestern Polytechnical University, 2014A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinTHE COLLEGE OF GRADUATE STUDIES(Electrical Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)July 2021© Jianyu Niu, 2021The following individuals certify that they have read, and recommend to theCollege of Graduate Studies for acceptance, a thesis/dissertation entitled:On the Security and Performance of Next-Generation Blockchainssubmitted by Jianyu Niu in partial fulfilment of the requirements of thedegree of Doctor of Philosophy.Dr. Chen Feng, School of Engineering, The University of British ColumbiaSupervisorDr. Julian Cheng, School of Engineering, The University of British ColumbiaSupervisory Committee MemberDr. Zheng Liu, School of Engineering, The University of British ColumbiaSupervisory Committee MemberDr. Apurva Narayan, Computer Science, The University of British ColumbiaUniversity ExaminerDr. Majid Khabbazian, Electrical & Computer Engineering, The University of AlbertaExternal ExamineriiAbstractBitcoin also known as the first-generation blockchain protocol, has suf-fered from scalability barriers. For example, Bitcoin can only process 7transactions per second, and users have to wait up to one hour to confirmtransactions. To address this, Ethereum, Bitcoin-NG, and HotStuff (alsoknown as the next-generation blockchains) are proposed. Each protocolrepresents an elegant approach and has further influenced many subsequentblockchain protocols. Informally speaking, Ethereum promotes Bitcoin’sscalability by elaborately tuning system parameters (e.g., block produc-tion rate); Bitcoin-NG achieves better scalability by decoupling Bitcoin’sblockchain operation into two planes: leader election and transaction serial-ization; HotStuff differs from Bitcoin by renovating classic Byzantine faulttolerance (BFT) consensus protocol.However, the security and performance of these protocols have not beenfully explored in the literature. Specifically, Ethereum introduces the so-called uncle and nephew rewards on top of the (standard) block rewardsused in Bitcoin, making the analysis of the selfish mining attack in Bitcoinhard to be directly applied to Ethereum. This calls for new analysis. Inthis dissertation, a 2-dimensional Markov process is proposed to model theselfish mining attack. Besides, a probabilistic reward computing method isused to tracks block rewards.Bitcoin-NG relies on two types of blocks (namely, key blocks and mi-croblocks) to realize the leader election and transaction serialization. How-ever, an in-depth incentive analysis is still missing to evaluate the impact ofthese types of blocks under network capacity constraints. To address this,the interval between two consecutive key blocks is modeled as an exponen-tial random variable, and the generation rate of microblocks is introducedto capture the impact of network capacity. Besides, a Markov decision pro-cess (MDP) model is used to jointly analyze the incentive of key blocks andmicroblock.HotStuff leverages the chain structure and pipelining techniques to sim-plify BFT protocol design, which, unfortunately, introduces new attacks todeteriorate the system performance. To evaluate these attacks, a multi-iiiAbstractmetric evaluation framework including chain growth rate, chain quality, andlatency is proposed. Besides, two attacks, namely the forking attack anddelay attack, are systematically studied. With the framework, some engi-neering designs in DiemBFT, a variant of HotStuff used in Facebook’s Diemblockchain, are also evaluated.ivLay SummaryThis dissertation takes an in-depth examination of three of the most in-fluential next-generation blockchain protocols: Ethereum, Bitcoin-NG, andHotStuff. Specifically, Ethereum introduces the so-called uncle and nephewrewards on top of the (standard) block rewards used in Bitcoin, making theanalysis of the selfish mining attack in Bitcoin hard to be directly appliedto Ethereum. This calls for new analysis. Bitcoin-NG relies on two typesof blocks (namely, key blocks and microblocks) to realize the leader elec-tion and transaction serialization. However, an in-depth incentive analysisis still missing to evaluate the impact of these types of blocks under networkcapacity constraints. HotStuff leverages the chain structure and pipeliningtechniques to simplify BFT protocol design, which, unfortunately, introducesnew attacks to deteriorate the system performance. A theoretical analysisis lacking on such performance deterioration. To fill in these research gaps,this dissertation analyzes the selfish mining attack in Ethereum, extendsincentive analysis of Bitcoin-NG under network capacity constraints, andexplores the performance of HotStuff under new attacks.vPrefaceA list of my publications at The University of British Columbia is pro-vided in the following.Refereed Journal PublicationsJ2. Mohammad Jalalzai, Chen Feng, Costas Busch, Golden, Richard III,Jianyu Niu, “The Hermes BFT for Blockchains” under revision forIEEE Transactions on Dependable and Secure Computing (TDSC).(Submitted in May 2020, revised for the first round in March 2021,revised for the second round in May 2021.)J1. Jianyu Niu, Ziyu Wang, Fangyu Gai, and Chen Feng, “IncentiveAnalysis of Bitcoin-NG, Revisited,” in Elsevier journal PerformanceEvaluation (PEVA). Volume 144, pages 102144, Nov 2020.Refereed Conference PublicationsC5. Fangyu Gai, Ali Farahbakhsh, Jianyu Niu, Chen Feng, Ivan Beschast-nikh, and Hao Duan, “Dissecting the Performance of Chained-BFT”in the 41th IEEE International Conference on Distributed ComputingSystems (ICDCS), Virtual Event, July 2021.C4. Fangyu Gai, Jianyu Niu, Chen Feng, Seyed Ali Tabatabaee, ChenFeng, Mohammad Mussadiq Jalalzai, “Cumulus: A Secure BFT-basedSidechain for Off-chain Scaling,” short paper, in the IEEE/ACM In-ternational Symposium on Quality of Service (IWQoS), Virtual Event,June 2021.C3. Jianyu Niu, Fangyu Gai, Mohammad Mussadiq Jalalzai, and ChenFeng “On the Performance of Pipelined HotStuff,” in the 40th IEEEInternational Conference on Computer Communications (INFOCOM),Virtual Event, May 2021.C2. Jianyu Niu, Ziyu Wang, Fangyu Gai, and Chen Feng, “IncentiveAnalysis of Bitcoin-NG, Revisited,” in the 38th IFIP WG7.3 Perfor-viPrefacemance 2020, Virtual Event, Nov 2020.C1. Jianyu Niu, and Chen Feng, “Selfish Mining in Ethereum,” in the39th IEEE International Conference on Distributed Computing Sys-tems (ICDCS), Texas, USA, Jul 2019.viiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiList of Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . xivList of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . xviChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.1 Bitcoin as First-Generation Blockchain Protocol . . . . . . . 11.2 Next-Generation Blockchain Protocols . . . . . . . . . . . . . 21.3 Motivation and Contributions . . . . . . . . . . . . . . . . . . 41.3.1 Selfish Mining in Ethereum . . . . . . . . . . . . . . . 51.3.2 Incentive Analysis of Bitcoin-NG . . . . . . . . . . . . 61.3.3 Performance of Pipelined HotStuff . . . . . . . . . . . 61.4 Thesis Organizations . . . . . . . . . . . . . . . . . . . . . . . 7Chapter 2: Background . . . . . . . . . . . . . . . . . . . . . . . 82.1 Bitcoin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2 Next-Generation Blockchain Protocols . . . . . . . . . . . . . 92.2.1 Ethereum . . . . . . . . . . . . . . . . . . . . . . . . . 92.2.2 Bitcoin-NG . . . . . . . . . . . . . . . . . . . . . . . . 10viiiTABLE OF CONTENTS2.2.3 HotStuff . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3 Security Issues . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3.1 Incentive-based Attacks . . . . . . . . . . . . . . . . . 122.3.2 Consistency-based Attacks . . . . . . . . . . . . . . . . 12Chapter 3: Selfish Mining on Ethereum . . . . . . . . . . . . . 143.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.2 Mining Strategy . . . . . . . . . . . . . . . . . . . . . . . . . 153.3 Analysis of Selfish Mining . . . . . . . . . . . . . . . . . . . . 183.3.1 Markov Process . . . . . . . . . . . . . . . . . . . . . . 183.3.2 The Stationary Distribution . . . . . . . . . . . . . . . 193.3.3 Reward Analysis . . . . . . . . . . . . . . . . . . . . . 213.3.4 Revenue Analysis . . . . . . . . . . . . . . . . . . . . . 223.3.5 Absolute Revenue . . . . . . . . . . . . . . . . . . . . 243.4 Evaluation Results . . . . . . . . . . . . . . . . . . . . . . . . 253.4.1 Validation of the Theory Results . . . . . . . . . . . . 253.4.2 Impact of the Uncle Reward . . . . . . . . . . . . . . . 253.4.3 Comparison with Bitcoin . . . . . . . . . . . . . . . . 263.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.5.1 Uncle Block Rewards . . . . . . . . . . . . . . . . . . . 293.5.2 Mining Difficulty Adjustment . . . . . . . . . . . . . . 303.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31Chapter 4: Incentive Analysis of Bitcoin-NG, Revisited . . . 334.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.1.1 Mining Model . . . . . . . . . . . . . . . . . . . . . . . 334.1.2 Mining Rewards . . . . . . . . . . . . . . . . . . . . . 344.1.3 Mining Revenue . . . . . . . . . . . . . . . . . . . . . 354.2 Incentive Analysis for Microblock . . . . . . . . . . . . . . . . 354.2.1 Microblock Mining Strategies . . . . . . . . . . . . . . 354.2.2 Exiting Analysis . . . . . . . . . . . . . . . . . . . . . 374.2.3 Limitations of Existing Analysis . . . . . . . . . . . . 394.3 Revisiting Incentive Analysis for Microblock . . . . . . . . . . 404.3.1 Resisting Transaction Inclusion Attack . . . . . . . . . 414.3.2 Resisting Longest Chain Extension Attack . . . . . . . 434.3.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 454.4 Incentive Analysis for both Microblock and Key Block . . . . 474.4.1 Markov Decision Process (MDP) . . . . . . . . . . . . 474.4.2 Evaluation Results . . . . . . . . . . . . . . . . . . . . 53ixTABLE OF CONTENTS4.4.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 554.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56Chapter 5: On the Performance of Pipelined HotStuff . . . . 575.1 System Model and Preliminaries . . . . . . . . . . . . . . . . 575.1.1 System Model . . . . . . . . . . . . . . . . . . . . . . . 575.1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 585.2 Pipelined HotStuff and DiemBFT Algorithms . . . . . . . . . 595.2.1 Pipelined HotStuff Algorithm . . . . . . . . . . . . . . 595.2.2 DiemBFT Algorithm . . . . . . . . . . . . . . . . . . . 615.3 Performance Metrics and Attacks . . . . . . . . . . . . . . . . 615.3.1 Performance Metrics . . . . . . . . . . . . . . . . . . . 615.3.2 Attack Strategies . . . . . . . . . . . . . . . . . . . . . 635.4 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . 655.4.1 Pipelined HotStuff . . . . . . . . . . . . . . . . . . . . 665.4.2 DiemBFT . . . . . . . . . . . . . . . . . . . . . . . . . 705.4.3 Countermeasures . . . . . . . . . . . . . . . . . . . . . 715.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735.5.1 Testnet Setup . . . . . . . . . . . . . . . . . . . . . . . 735.5.2 Pipelined HotStuff and DiemBFT . . . . . . . . . . . 745.5.3 Countermeasures . . . . . . . . . . . . . . . . . . . . . 755.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 765.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79Chapter 6: Conclusions . . . . . . . . . . . . . . . . . . . . . . . 816.1 Summary of Contributions . . . . . . . . . . . . . . . . . . . . 816.2 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . 82Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93Appendix A: Concentration Bounds . . . . . . . . . . . . . . . . . 93Appendix B: The Multiple Summations Function . . . . . . . . . . 94Appendix C: Reward Analysis . . . . . . . . . . . . . . . . . . . . . 95Appendix D: HotStuff Analysis . . . . . . . . . . . . . . . . . . . . 103D.1 Pipelined HotStuff . . . . . . . . . . . . . . . . . . . . . . . . 103D.2 DiemBFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105xList of TablesTable 3.1 The distribution of honest miners’ uncle block withdifferent referencing block distances . . . . . . . . . . . 30Table 4.1 State transition and reward matrices for the optimalselfish mining (Prob.: probability; Cond.: condition). . 49xiList of FiguresFigure 1.1 An illustration of the blockchain data structure. . . . 2Figure 2.1 An illustration of the chain structure in Bitcoin. . . . 9Figure 2.2 Different block types in Ethereum. . . . . . . . . . . . 10Figure 2.3 An illustration of Bitcoin-NG. . . . . . . . . . . . . . 11Figure 3.1 An example to illustrate private branch length andpublic branch length. . . . . . . . . . . . . . . . . . . 16Figure 3.2 The Markov process of the selfish mining in Ethereum. 18Figure 3.3 Revenue rate for the selfish pool and honest miners . 26Figure 3.4 Revenue rate for the selfish pool under different uncleblock reward . . . . . . . . . . . . . . . . . . . . . . . 27Figure 3.5 The profitable threshold of hash power in Bitcoin andEthereum. . . . . . . . . . . . . . . . . . . . . . . . . 28Figure 4.1 An example of the transaction inclusion attack. . . . 36Figure 4.2 An example of the longest chain extension attack. . . 37Figure 4.3 Bitcoin-NG fee distribution rule. . . . . . . . . . . . . 38Figure 4.4 A simple example to illustrate the limitation of theprevious analysis. . . . . . . . . . . . . . . . . . . . . 40Figure 4.5 The comparison of the transaction fee distribution ratio. 46Figure 4.6 The selfish miner’s relative revenue. . . . . . . . . . . 53Figure 4.7 The selfish miner’s relative revenue with different α. . 54Figure 4.8 The selfish miner’s relative revenue with different splitratio r. . . . . . . . . . . . . . . . . . . . . . . . . . . 55Figure 5.1 Overview of a sequence of the leader-based round(LBR) instances. . . . . . . . . . . . . . . . . . . . . . 58Figure 5.2 The chained blocks in pipelined HotStuff. . . . . . . . 60Figure 5.3 The overriding attack on pipelined HotStuff. . . . . . 63Figure 5.4 The delay attack on pipelined HotStuff. . . . . . . . . 65xiiLIST OF FIGURESFigure 5.5 The state transition of the delay attack on pipelinedHotStuff. . . . . . . . . . . . . . . . . . . . . . . . . . 68Figure 5.6 The state transition of the delay attack on DiemBFT. 70Figure 5.7 The committing rule with broadcasting QCs in PipelinedHotStuff. . . . . . . . . . . . . . . . . . . . . . . . . . 72Figure 5.8 The state transition of the delay attack on pipelinedHotStuff with broadcasting QCs. . . . . . . . . . . . . 73Figure 5.9 The chain growth rate under the overriding attack. . 75Figure 5.10 The chain quality under the overriding attack. . . . . 76Figure 5.11 The average latency of honest blocks under the delayattack. . . . . . . . . . . . . . . . . . . . . . . . . . . 77Figure 5.12 The chain growth rate pipelined HotStuff with andwithout broadcasting QCs. . . . . . . . . . . . . . . . 78Figure 5.13 The chain quality of pipelined HotStuff with and with-out broadcasting QCs. . . . . . . . . . . . . . . . . . 79Figure 5.14 The average latency of pipelined HotStuff with andwithout broadcasting QCs. . . . . . . . . . . . . . . . 80Figure C.1 The two subcases of Case 1. . . . . . . . . . . . . . . 96Figure C.2 The three subsubcases of Case 1. . . . . . . . . . . . . 97Figure C.3 The three subcases of Case 4. . . . . . . . . . . . . . 98Figure C.4 The subcase 1 of Case 7. . . . . . . . . . . . . . . . . 99Figure C.5 The subcase 2 of Case 7. . . . . . . . . . . . . . . . . 100Figure C.6 The subsubcase 1 of Case 7. . . . . . . . . . . . . . . 100Figure C.7 The subsubcase 2 of Case 7. . . . . . . . . . . . . . . 101Figure D.1 The state transition of the delay attack on pipelinedHotStuff. . . . . . . . . . . . . . . . . . . . . . . . . . 104Figure D.2 The state transition of the delay attack on pipelinedHotStuff. . . . . . . . . . . . . . . . . . . . . . . . . . 105Figure D.3 The state transition of the delay attack on pipelinedHotStuff. . . . . . . . . . . . . . . . . . . . . . . . . . 106xiiiList of AcronymsAcronyms DefinitionsNC Nakamoto ConsensusPoW Proof-of-WorkLCR Longest Chain RulePoS Proof-of-StakeBFT Byzantine Fault ToleranceBitcoin-NG Bitcoin-Next GenerationSMR State Machine ReplicationMDP Markov Decision ProcessPKI public Key InfrastructureGST Global Stabilization TimeQC Quorum CertificateLBR Leader-based RoundDDoS Distributed Denial of ServicexivList of SymbolsSymbols Definitionsmax {·} The maximum value of the functionmin {·} The minimum value of the functions.t. Subject toE[·] The statistical expectation operationPr(·) The probability of an event| · | The absolute value of the argumentxvAcknowledgementsI would like to sincerely thank my advisor, Dr. Chen Feng, for his tirelessguidance, advice, encouragement and support since we first met four yearsago. He has guided me not only in my research but also in my life. I am sofortunate to have such a research journey with him.I would like to thank my dear colleagues: Chunpu Wang, Renming Qi,Yonghui Lu, Junyuan Leng, Yuwei Guo, Jinfeng Tong, Yiqun Duan, FangyuGai, Mohammad Mussadiq Jalalzai, and Maryam Sadeghi for sharing theiracademic experiences and constructive viewpoints during my PhD study atthe University of British Columbia. I also would like to thank all my dearfriends Yakang Xia, Xingjie Fan, Xiao Chen, Jintao Han, Ruoyao Li, PengxiaWu, Renzhi Yuan, Run Yao, Weichen Tang, Xiao Yang, Kexin Zhou, whohelped me a lot when I was in Kelowna and I miss the fun we had together.I would also like to express my thanks to Dr. Majid Khabbazian fromUniversity of Alberta to serve as my external examiner. I am honored tohave him on my committee. I would like to thank Dr. Julian Chen and Dr.Zheng Liu for being my committee members, and Dr. Apurva Narayan forbeing my University Examiner. I really appreciate their valuable time.Last but not least, I’d like to thank my wife, Xiaoxia Qu, for the greatsupport as well as the joy that you have brought to my life over the lastseven years. I would also like to thank my parents for their patience, under-standing, and unconditional love over all these years. All my achievementswould not have been possible without their constant encouragement andsupport.xviChapter 1IntroductionIn 2008, Nakamoto invented Bitcoin in the seminal paper titled “Bit-coin: A Peer-to-Peer Electronic Cash System”. Bitcoin is aimed to realizea decentralized electronic cash system that does not rely on a central au-thority for currency issuance and transaction processing. One year later,the Bitcoin network was launched based on the open-source code developedby Nakamoto. By now, as the biggest cryptocurrency, Bitcoin has a mar-ket value of more than 1 trillion US dollars by the dollar/bitcoin exchangerate in April 2021.1 The huge success of Bitcoin is largely owing to itscore technological innovation—the so-called Nakamoto consensus protocol,which can realize a public, immutable, and distributed ledger widely knownas a blockchain today.In a blockchain, users can create and exchange transactions to modifytheir monetary amounts, and new transactions can be batched into blocksfor processing. Particularly, each block is linked to its previous block with acryptographic hash, forming a chain of blocks accepted by the users (whichexplains the name of blockchain). A simple illustration of the blockchaindata structure is provided in Fig. 1.1. In addition to changing users’ mone-tary amounts, transactions enable users to execute arbitrary computer code(written in the form of smart contracts), supporting more complex applica-tions. Due to the unique features in decentralization, security and privacy,blockchain technology has been envisioned as a fundamental trust infras-tructure for supporting various future decentralized Internet applications,ranging from IoT, health care, to supply chain management [46, 60].1.1 Bitcoin as First-Generation BlockchainProtocolIn Bitcoin, a node that collects users’ transactions and batches them intoblocks is called a miner. The miners compete to solve computational puzzlesin order to generate new blocks (which is often known as Proof-of-Work1Today’s Cryptocurrency Prices by Market Cap: https://coinmarketcap.com/.11.2. Next-Generation Blockchain ProtocolsTransactionsBlock 1PrevhashTimestampNonceBlock 2 Block 3TransactionsPrevhashTimestampNonceTransactionsPrevhashTimestampNonceFigure 1.1: An illustration of the blockchain data structure. Eachblock contains a batch of transactions, a hash value of its previous blockand other metadata.(PoW)) and follow the longest chain rule (LCR) to reach an agreement on anincreasing sequence of blocks. Each block included in the longest chain canbring its miner some rewards including a block reward and some transactionfees. The block reward incentivizes miners to produce new blocks, while thetransaction fees encourage miners to include as many transactions as possiblein their blocks (up to the block-size limit). Despite its surprising simplicity,Bitcoin enjoys several desirable properties: it doesn’t require participants’identities as a setup (i.e., a fully permissionless setting) and can work aslong as more than half of the computation power is controlled by honestparticipates who follow the protocol. Nevertheless, Bitcoin still suffers fromscalability barriers. For example, Bitcoin only processes up to 7 transactionsper second. Also, Bitcoin takes more than one hour to confirm transactions.Such low throughput and long latency hinder wide applications of Bitcoin-like blockchain protocols.1.2 Next-Generation Blockchain ProtocolsTo address the scalability issues, a large number of blockchain protocols(also known as the next-generation blockchains) have been proposed re-cently [5, 21, 64, 70, 73, 74]. Among them, Ethereum [70], Bitcoin-NG [21]and HotStuff [73] are the three most influential ones; each represents adifferent but elegant approach to improving blockchain scalability. Infor-mally speaking, Ethereum prompts Bitcoin’s scalability by elaborately tun-ing system parameters. The key insight behind this approach is that thelow throughput and long latency of Bitcoin are mostly due to its choice of21.2. Next-Generation Blockchain Protocolstwo system parameters: small block size (originally 1 MB) and long blockinterval (on average 10 minutes). Ethereum sets its block size to about 20KB and block interval to 10 − 20 seconds, resulting in higher throughput(of tens of transactions per second) and shorter latency (of several min-utes) [27]. This approach of fine-tuning system parameters is also adoptedby other blockchains such as Litecoin2, Dogecoin3, etc. However, recentstudies show that this approach cannot fundamentally overcome the scala-bility barriers. This is because increasing the block size or shortening theblock interval will reduce the security level of a blockchain since forks aremore likely to occur [25, 56, 65]. Indeed, a complete redesign of blockchainprotocols seems to be needed to address the scalability barriers withoutsacrificing security [16, 21, 65].By redesigning the Bitcoin protocol, Eyal et al. proposed Bitcoin-NG(Next Generation), which decouples Bitcoin’s operation into two planes:leader election and transaction serialization. Specifically, Bitcoin-NG cre-atively employs two types of blocks: 1) a key block that is very similar to aconventional block in Bitcoin except that it doesn’t carry any transactions,and 2) a microblock that carries transactions. Every key block is generatedthrough the leader election process (often known as the mining process),and the leader can issue multiple microblocks to serialize transactions untilthe next key block is generated. In Bitcoin-NG, key blocks are producedat a rate similar to that in Bitcoin, whereas the elected leaders can pro-duce microblocks as quickly as what the underlying network can support.In other words, Bitcoin-NG can approach the near-optimal throughput sup-ported by its underlying network. This decoupling idea behind Bitcoin-NGhas inspired many other blockchain protocols such as ByzCoin [40], Hybridconsensus [58], and Prism [5].Another approach to addressing the scalability issues is leveraging theclassical Byzantine fault tolerance (BFT) consensus [12, 59], which is also re-ferred to as BFT state machine replication (SMR) and has been extensivelystudied for the past four decades. Unlike the above-mentioned blockchainprotocols that can only provide probabilistic safety guarantees (i.e., thereis a small chance for a confirmed transaction to become unconfirmed in thefuture), classical BFT protocols can provide a strong safety guarantee (i.e.,a confirmed transaction will never be unconfirmed). Hence, clients do notneed to wait for a long time in order to have high confidence (say, with99.99% confidence) in confirming transactions. This reduces the transac-2Litecoin:https://litecoin.com/en/.3Dogechain: https://dogechain.info/.31.3. Motivation and Contributionstion latency without compromising security. Perhaps for this reason, BFTprotocols have recently attracted considerable attention with many novelBFT protocols proposed in the past five years [9, 11, 28, 45, 73]. Amongthem, HotStuff proposed by Yin et al. [73] is a state-of-the-art BFT con-sensus. HotStuff creatively adopts a three-phase commit rule (rather thanthe widely used two-phase commit rule in classical BFT [12]) to enable theprotocol to reach consensus at the pace of actual network delay (a propertycalled responsiveness) and leverages the threshold signature to realize lin-ear message complexity. HotStuff can be further pipelined, which enablesfrequent leader rotation. Therefore, HotStuff achieves strong scalability,prominent simplicity, and good practicability for large-scale applications likeglobal payment systems. Facebook adopts a variant of pipelined HotStuffcalled DiemBFT [7] for its global payment system, Diem blockchain whichaims to thrive FinTech innovations and to enable billions of consumers andbusinesses to conduct instantaneous, low-cost, highly secure transactions.4In addition, Dapper Lab describes how to deploy HotStuff in its Flow plat-form [34], and Cypherium Blockchain [30] combines HotStuff with NC to-gether to build a permissionless blockchain.1.3 Motivation and ContributionsThe goal of this research is to examine the security of these promisingnext-generation blockchain protocols, with a particular focus on incentiveanalysis. Although the security of blockchain protocols has been studied in alarge variety of research papers and theses, we believe it is still necessary torevisit the security analyses of these protocols for three reasons. First, theseprotocols are deployed or being deployed for many important applicationssuch as digital cryptocurrency and global payment systems. Thus, a hiddensecurity issue of these protocols may lead to a loss of millions of dollarsor more. Therefore, it is crucial to provide more accurate and comprehen-sive security analyses. Second, the security analyses of blockchain protocolsvary according to their consensus algorithms, reward design, underlying net-works, and even system parameter settings. So, the existing analysis of oneprotocol may not be directly applied to another protocol even if the two pro-tocols share a lot of common designs. For example, although Bitcoin and itsvariants Litecoin and Dogecoin adopt the same consensus protocol, it is stillnecessary to develop a quantitative framework to take into account theirdifferences in network parameters and consensus settings (in terms of block4Diem was formerly known as Libra, and DiemBFT was formerly called LibraBFT.41.3. Motivation and Contributionssize and block generation interval) [27]. Third, blockchain technology is stillfast developing; every day there are novel protocol designs proposed or newsecurity attacks found. Thus, it is necessary to timely revisit the security ofexisting protocols, updating the knowledge of their security. For example,the security issue of transaction order manipulation (e.g., transactions cen-sorship, selective inclusion, reordering, and injection) is recently attractingconsiderable attention, and a new property called the fair ordering propertyis defined for consensus protocols [38, 77]. However, the traditional speci-fications of correctness for consensus protocols don’t have any language foraddressing such security concerns.For all of the above reasons, this dissertation takes an in-depth ex-amination of the security analyses of the three influential next-generationblockchain protocols: Ethereum, Bitcoin-NG, and HotStuff. Although thesethree protocols take different approaches to the scalability issue, they stillshare many common designs, such as the chain structure and frequent leaderrotation.5 Our studies show that the chain structure and frequent leader ro-tation may lead to several attacks, which can either enable an adversary toruin the incentive compatibility and deteriorate the system performance interms of the chain growth or chain quality. What is more, since the lead-ership is usually randomly generated for the unpredictability of the lead-ers and repeated for continuous block production, the attack process canbe viewed as a stochastic process. This key observation enables us to usesimilar mathematical tools such as the Markov process or Markov decisionprocess (MDP) to analyze them. Through our studies, we hope to fill someresearch gaps in analyzing these protocols and shed light on the securityanalyses of other protocols. The following are summaries of our particularcontributions.1.3.1 Selfish Mining in EthereumEyal and Sirer first formally studied the selfish mining attack in Bitcoin,in which a selfish miner can strategically delay publication of its generatedblocks to gain more block rewards than following the protocol [22]. In otherwords, this attack encourages rational miners to deviate from the suggestedprotocol in order to obtain higher revenue, which will affect the overall se-curity of blockchain. Indeed, due to the huge market capitalization andinfluence of Bitcoin, the security concerns to this attack have attracted con-5In Bitcoin, Ethereum, and Bitcoin-NG, blocks (except microblocks in Bitcoin-NG) areproduced by PoW. The mining process can be viewed as a random leader election amongall miners. Once winning the leadership, a miner can produce one block.51.3. Motivation and Contributionssiderable attention from academia with a large number of papers publishedon this topic [27, 32, 48, 62, 75]. By contrast, there are few studies of theselfish mining attack in Ethereum, even if Ethereum is the second largestcryptocurrency only to Bitcoin [70]. Ethereum differs from Bitcoin in thereward design; Ethereum provides the so-called uncle and nephew rewardsin addition to the (standard) block rewards. These rewards will affect theselfish mining strategies and also influence the security of Ethereum. Thisdissertation demystifies the selfish mining attack in Ethereum. In particu-lar, we propose a 2-dimensional Markov process to model the behavior ofa selfish mining strategy inspired by [22]. This new model enables us tobetter evaluate the security threat caused by the selfish mining attack andto provide useful guidance for the reward design in Ethereum.1.3.2 Incentive Analysis of Bitcoin-NGBitcoin-NG creatively employs two types of blocks: key blocks and mi-croblocks. Each key block included in the longest chain can bring its miner ablock reward, while the transactions in microblocks can reward their minerswith some transaction fees. More specifically, not all of the transaction feesin a microblock are distributed to the microblock creator. Instead, thesetransaction fees will be split between the microblock creator and the ownerof the next key block. This mechanism is designed to prevent the transac-tion inclusion attack and the longest chain extension attack [21]. Althoughthe incentive analysis of these two attacks has been conducted in multiplepapers [21, 69, 71], none of them considers the impact of network capacity.In addition, an adversary can launch the selfish mining attack for key blockson top of these two attacks. This new attack receives little attention in theliterature. This dissertation provides a new probabilistic analysis to addressthese limitations, providing a comprehensive security study of Bitcoin-NG.1.3.3 Performance of Pipelined HotStuffBFT protocols have been studied by the distributed systems communityfor almost three decades before the inception of Bitcoin. Two well-definedproperties, i.e., safety and liveness, were proposed to evaluate the security ofBFT protocols. Specifically, liveness means that users’ transactions will beeventually accepted by honest nodes (who strictly follow the protocol), andsafety (also referred to as consistency in the literature) means that all honestnodes will accept the same sequence of transactions. As a BFT protocol,HotStuff has been carefully designed to satisfy these two properties. Addi-61.4. Thesis Organizationstionally, HotStuff’s performances including throughput and latency are alsowell measured under the happy case (i.e., assuming all nodes are honest).However, we have found that there are several new attacks in pipelined Hot-Stuff due to its pipelining and chain structure. These attacks do not ruin thesafety property but may affect liveness, especially on the throughput anddelay performance. This dissertation proposes three new metrics (namely,the chain growth rate, chain quality, and latency) to measure the perfor-mance of pipelined HotStuff under these attacks and develop an evaluationframework to characterize the impact of these attacks.1.4 Thesis OrganizationsThe following chapters are organized as follows. Chapter 2 first providesthe necessary background of several blockchain protocols including Bitcoin,Ethereum, Bitcoin-NG as well as HotStuff, and then introduces blockchainsecurity issues. Chapter 3 analyzes the selfish mining attack in Ethereum.Chapter 4 extends the incentive analysis of Bitcoin-NG, especially underthe network capacity constraints. Chapter 5 evaluates the performance ofpipelined HotStuff under attacks. Chapter 6 concludes this dissertation anddiscusses future work.7Chapter 2BackgroundThis chapter provides the necessary background of several influentialblockchain protocols including Bitcoin, Ethereum, Bitcoin-NG, as well asHotStuff.2.1 BitcoinBitcoin is the most influential and largest cryptocurrency by marketcapitalization. Bitcoin relies on Nakamoto Consensus (NC) to make a groupof distributed and mutually distrusting participants reach an agreement on atransparent and immutable ledger, also known as a blockchain. A blockchainis a list of blocks linked by hash values with each block containing a batchof ordered transactions. To make all participants agree on the same chain ofblocks, NC leverages two components: the Proof-of-Work (PoW) mechanismand the longest chain rule (LCR). Each participant in NC (also referred toas a miner) collects valid and unconfirmed transactions from the network,then orders and packs these transactions into a block. A valid block needsto contain a proof-of-work, i.e., its owner needs to find a value of the nonce(i.e., a changeable data filed) such that the hash value of this block hasrequired leading zeros [47]. The length of leading zeros is also known as themining difficulty, which can be tuned by the system to make sure new blocksare mined every ten minutes on average.Once a new block is produced, it will be immediately broadcast to theentire network. Ideally, the block should be accepted by all participantsbefore the next block is produced. In reality, two new blocks might bemined around the same time, leading to a fork in which two “child” blocksshare a common “parent” block. See Fig. 2.1 for an illustration. To resolvesuch a fork, an honest miner always accepts the longest chain as the validone, which is referred to as the main chain. The common prefix of all themain chains is called the system main chain. In Bitcoin, a block miner willreceive a block reward (if its block is eventually included in the system mainchain) as well as transaction fees as another type of reward. These incentivesencourage miners to devote their computational resources to the system.82.2. Next-Generation Blockchain ProtocolsB1 B2 B4B3B5Figure 2.1: An illustration of the chain structure stored in a miner.The miner tries to produce a block on the longest chain it observes.2.2 Next-Generation Blockchain Protocols2.2.1 EthereumEthereum is the second largest cryptocurrency by market capitaliza-tion and today’s biggest decentralized platform that runs smart contracts.Roughly speaking, a smart contract is a set of functions defined in a Turing-complete environment. Clients in Ethereum can issue transactions to createnew contracts, to send Ether (internal cryptocurrency of Ethereum) to con-tracts or to other clients, or to invoke some functions of a contract. Whenfirst launched, the Ethereum system adopted PoW for block mining and theheaviest subtree rule [66] for agreeing on the same system main chain, whichis usually regarded as a variant of NC.6Like Bitcoin, miners in Ethereum can get block rewards and gas costfrom executing transactions (similar to transaction fees in Bitcoin), oncetheir blocks are included in the system main chain. However, there aretwo additional block rewards in Ethereum, namely, uncle block reward andnephew block reward [10, 20]. To explain these rewards, we shall introducethe concepts of regular and stale blocks. A block is called regular if it isincluded in the system main chain, and is called stale block otherwise. Inaddition, an uncle block is a stale block that is a “direct child” of the systemmain chain. In other words, the parent of an uncle block is always a regularblock. An uncle block receives certain rewards if it is referenced by somefuture regular block, called a nephew block, through the use of referencelinks. See Fig. 2.2 for an illustration of uncle and nephew blocks. Thevalues of uncle rewards depend on the “distance” between the uncle andnephew blocks. This distance is well defined because all the blocks form a6Although Ethereum claimed to apply the heaviest subtree rule [66], it seems to applythe longest chain rule instead [27].92.2. Next-Generation Blockchain ProtocolsA B2B1B3C1 D1D2E1 F1C2Regular Block & Nephew BlockStale Block Stale Block & Uncle BlockRegular BlockFigure 2.2: Different block types in Ethereum. Here, regular blocksinclude {A,B2, C1, D1, E1, F1} and stale blocks include {B1, B3, C2, D2}.Similarly, uncle blocks are {B1, B3, D2} and nephew blocks are {C1, F1}.Uncle block B3 (uncle block D2, resp.) is referenced with distance one (two,resp.).tree. For instance, in Fig. 2.2, the distance between uncle block B3 (uncleblock D2, resp.) and its nephew block is 1 (2, resp.). In Ethereum, ifthe distance is 1, the uncle reward is 78 of the (static) block reward; if thedistance is 2, the uncle reward is 68 of the block reward and so on. Once thedistance is greater than 6, the uncle reward will be zero. By contrast, thenephew reward is always 132 of the block reward.Note that Ethereum will gradually replace NC with Proof-of-Stake (PoS),which is widely believed to be more energy efficient. To realize this, Ethereumhas four milestones: Frontier, Homestead, Metropolis, and Serenity. Cur-rently, Ethereum is underway for a major upgrade to Serenity, also known asEthereum 2.0. Specifically, Ethereum 2.0 is designed to be launched in threephases. The first phase was launched in December 2020, while the other twophases are still developing. Although our studies focus on Ethereum 1.0,they can lay a solid foundation for the future study of Ethereum 2.0.2.2.2 Bitcoin-NGIn Bitcoin, block mining has two functionalities: 1) electing leaders (i.e.,the owners of valid blocks) by NC, and 2) ordering and verifying trans-actions. By differentiating block functionalities, Bitcoin-NG decouples theleader election with the transaction serialization. Specifically, Bitcoin-NG102.2. Next-Generation Blockchain ProtocolsBjBj+2Bj+1Figure 2.3: An illustration of Bitcoin-NG. A square (respectively, circle)block denotes a key block (respectively, microblock). The microblocks areissued by the three key-block miners Bj ,Bj+1,Bj+2 with their signaturesσj , σj+1, σj+2, respectively.uses key blocks mined through PoW to elect a leader at a stable rate (e.g.,one key block per 100 seconds). Each leader can produce several microblockscontaining unconfirmed transactions at another rate, often higher than thekey block rate (e.g., one microblock per 20 seconds). In a nutshell, a keyblock is very similar to a conventional block in Bitcoin except that it doesnot carry any transactions. On the other hand, microblocks contain trans-actions but do not contain any proof-of-work. Although the rate of mi-croblocks is usually much larger than the key block generation rate, it hasto be bounded to prevent adversarial leaders from swamping the systemwith microblocks. This decoupling enables Bitcoin-NG to process many mi-croblocks between two consecutive key blocks, which significantly increasesits transaction throughput. Fig. 2.3 illustrates these two types of blocks.Bitcoin-NG adopts a similar fork choice rule as Bitcoin. In Bitcoin-NG, microblocks carry no weight, not even a secondary index for miners tochoose which key block to mine. For instance, in Fig. 2.3, there are twoforking branches with the same number of key blocks but different numbersof microblocks. Honest miners treat these two forking branches as equaland adopt a uniform tie-breaking rule to choose one branch [21]. Honestminers then mine on the latest microblock in this branch. To sum up,an honest miner still follows LCR to choose a “right” key block (i.e., thelast key block in the longest chain consisting of key blocks only), and thenmines on the latest microblock produced by the key-block miner. Thus,without microblocks, the mining process of key blocks is the same as theone in Bitcoin. In fact, the selfish mining attack in Bitcoin can be usedhere to attack key blocks in Bitcoin-NG. However, as Bitcoin-NG introducesadditional microblocks, there are several new attacks for microblocks (whichwill be introduced Chapter 4).112.3. Security Issues2.2.3 HotStuffHotStuff proposed by Yin et al. [73] is a state-of-the-art BFT consensusprotocol designed for large-scale applications like blockchains. Unlike classi-cal BFT [12] that use two-phase commit rule, HotStuff adds one more phaseto enable the protocol to reach consensus at the pace of actual network delay(i.e., the responsiveness defined in the literature) and leverages the advancedcryptography such as threshold signature to realize linear message complex-ity. To enable frequent leader rotation, HotStuff can be further pipelined.The pipelined HotStuff can use the chain structure, which becomes simpleand practical to build large-scale blockchains. Perhaps for this reason, Thepipelined HotStuff is also referred to as chained HotStuff [73].2.3 Security IssuesThe security issues of blockchain can be broadly categorized into twotypes: incentive-based and consistency-based attacks. Informally speaking,in an incentive-based attack, an attacker aims to gain more profits than itsfair share. The most famous example is the selfish mining attack [22]. Ina consistency-based attack, an attacker tries to ruin the consistency of theblockchain system (e.g., reverting a block confirmed by nodes). A repre-sentative example is the private double-spending attack [47]. Sometimes,an attacker can combine these two types of attacks, obtaining more profitsthan what a single attack can achieve [27, 62].2.3.1 Incentive-based AttacksAlthough NC is designed to fairly reward miners according to their con-tributions to the system (i.e., miners’ revenue should be proportional totheir devoted computation power), the studies in [22, 27, 48, 62] show thatan attacker can gain more revenue than its fair share by deviating fromthe protocol. Such mining attack is often referred to as selfish mining. Inthis attack, an attacker can withhold its newly generated blocks and thenstrategically publish these private blocks to invalidate honest blocks, therebyobtaining higher block rewards than it deserves.2.3.2 Consistency-based AttacksIn Bitcoin white paper [47], a specific attack, called the private double-spending attack, is proposed. In a successful private double-spending attack,122.3. Security Issuesan attacker first creates a payment using its digital token (e.g., Bitcoin) tothe merchant for some service or goods. Once the transaction is confirmedin a public chain, and the service or goods are delivered, the attacker willinvalidate the public chain by publishing its longer private chain, whichcontains a conflicting transaction to transfer the token back to itself. In thisway, a successful double-spending attack ruins the consistency of the system.In addition to this attack, Pass et al. [56] introduced a delay attack on theconsistency of NC, in which an attacker simply delays all honest blocks aslong as possible to slow the growth rate of the honest chain. Meanwhile,the attacker mines secretly on its private chain and strategically publishesprivate blocks to maintain a forking chain with the same length as the honestchain. Despite the above and other possible attacks, it has been shown thatNC preserves consistency under all possible attacks as long as the attackeronly controls the minority computation power [24, 39, 56].13Chapter 3Selfish Mining on EthereumThis chapter aims to analyze selfish mining in Ethereum. Ethereumis the second-largest cryptocurrency by market capitalization and today’sbiggest decentralized platform that runs smart contracts. However, com-pared with the considerable studies of selfish mining (e.g., [27, 48, 62]) anddefenses mechanisms suggested (e.g., [32, 75]) in Bitcoin, selfish mining inEthereum has not received much attention. Besides, Ethereum differs fromBitcoin in that it provides the so-called uncle and nephew rewards in ad-dition to the (standard) block rewards [70], which complicates the selfishmining analysis, and also makes most existing research on Bitcoin hard tobe directly applied to Ethereum. To fill in this research gap, we first in-troduce a 2-dimensional Markov process to model the behavior of a selfishmining strategy inspired by [22]. We then derive the stationary distributionof our Markov model and compute long-term average mining rewards. Bydoing this, we can determine the threshold of computational power whichmakes selfish mining profitable in Ethereum. We finally perform extensivesimulations to verify our mathematical results and obtain several engineeringinsights.3.1 System ModelWe consider a system of n miners. The ith miner has mi fraction of totalhash power. Clearly, we have∑ni=1mi = 1. We assume miners are eitherhonest (those who follow the protocol) or selfish (those who deviate from theprotocol in order to maximize their profit). Let S denote the set of selfishminers and H denote the set of honest miners. Let α denote the fraction oftotal hash power controlled by selfish miners and β denote the fraction oftotal hash power controlled by honest miners. We have α =∑i∈S mi andβ =∑i∈Hmi. Clearly, α + β = 1. Without loss of generality, we assume asingle selfish mining pool with α fraction of hash power.The PoW mining process can be viewed as a series of Bernoulli trials,each of which independently finds a valid nonce to generate a new blockwith the same probability, depending on the difficulty level. Recall that a143.2. Mining StrategyBernoulli process can be approximated by a Poisson process if the durationof a trial is very short and the success probability is very low [23]. Bothconditions are held in the context of Bitcoin and Ethereum. Therefore, wecan model the mining process of the ith miner as a Poisson process withrate fmi. Here, f denotes the block mining rate of the entire system (e.g.,10 minutes per block in Bitcoin and 10−20 seconds per block in Ethereum).That is, the ith miner generates new blocks at rate fmi. Hence, the selfishpool generates blocks at rate fα, and the honest miners generate blocksat rate fβ. This model has been widely used in the literature. See, e.g.,[47],[55], [4].We use Ks, Ku, and Kn to denote static, uncle, and nephew rewards,respectively. Without loss of generality, we assume that Ks = 1 so that Ku(Kn, resp.) represents the ratio of uncle reward (nephew reward, resp.) tothe static reward. In particular, Kn < Ku < 1 and Ku is a function of thedistance. As we will see later, our analysis allows Ku and Kn to be anyfunctions of the distance. In addition, we ignore the gas cost in our analysissince it is usually dwarf with these block rewards.We follow the network model of [22, 27, 62] which assumes that the timeit takes to broadcast a block is negligible. In particular, we introduce thesame parameter γ as in [22], which denotes the ratio of honest miners thatare mining on blocks produced by the selfish pool (rather than by the honestminers) whenever they observe a fork of two branches of equal length. Forexample, if the honest miners apply the uniform tie-breaking rule (when theyobserve a fork of two branches of equal length), then γ = 12 . On the otherhand, if the pool can launch a network attack to influence honest miners’block propagation, then only a few honest miners can see any new blockproduced by some honest miners. In this case, the parameter γ is close to 1.Therefore, the parameter γ captures the pool’s communication capability.In the following analysis, we assume that γ takes values in the interval [0, 1].3.2 Mining StrategyWe now describe the mining strategies for honest and selfish miners.The honest miners follow the protocol. Each honest miner observes a treeof blocks. It chooses a main chain from the tree and mines new blocks onits main chain. Once a new block is produced, the miner broadcasts theblock to everyone in the system. Also, it includes as many reference linksas possible to (unreferenced) uncle blocks in the tree.By contrast, the selfish pool can withhold its newly mined blocks and153.2. Mining StrategyA B2 D2 E2B1 C E1D1 F GSelfish miners' secret blockSelfish miners' published blockHonest miners' blockFigure 3.1: An example to illustrate private branch length and public branchlength.publish them strategically to maximize its revenue. The basic idea behindselfish mining is to increase the selfish pool’s share of static rewards and,at the same time, to gain as many uncle and nephew rewards as possible.Specifically, the selfish pool keeps its newly discovered blocks private, cre-ating a fork on purpose. The pool then continues to mine on this privatebranch, while honest miners still mine on public branches (which are oftenshorter than the private branch).Fig. 3.1 gives an example in which “circle” blocks are mined by thepool and “square” blocks are mined by honest miners. In this example, theprivate branch consists of 4 blocks (D1, E1, F,G), all of which are minedby the pool with (D1, E1) published and (F,G) still private. There are twopublic branches, namely, (D1, E1) and (D2, E2), because honest miners cansee both branches. Each honest miner then chooses one public branch tomine new blocks according to certain rules (e.g., the longest chain rule).Here, the two public branches are of equal length. This is not a coincidence.We can show that public branches always have the same length under ourselfish mining strategy.Let Ls(t) be the length of the private branch seen by the selfish poolat time t. Similarly, let Lh(t) be the length of public branches seen byhonest miners at time t. (Note that Lh(t) is well defined because all publicbranches have the same length.) We are now ready to describe our selfishmining strategy, which is based on the strategy in [22].Algorithm 1 presents the mining strategy. When the selfish pool minesa new block (see lines 1 to 7), it will keep this block private and con-163.2. Mining StrategyAlgorithm 1 A Selfish Mining Strategy in Ethereumon The selfish pool mines a new block1: reference all (unreferenced) uncle blocks based on its private branch2: Ls ← Ls + 13: if (Ls, Lh) = (2, 1) then4: publish its private branch5: (Ls, Lh)← (0, 0) (since all the miners achieve a consensus)6: else7: keep mining on its private branch8: end ifon Some honest miners mine a new block9: The miner references all (unreferenced) uncle blocks based on its publicbranches10: Lh ← Lh + 111: if Ls < Lh then12: (Ls, Lh)← (0, 0)13: keep mining on this new block14: else if Ls = Lh then15: publish the last block of the private branch16: else if Ls = Lh + 1 then17: publish its private branch18: (Ls, Lh)← (0, 0) (since all the miners achieve a consensus)19: else20: publish first unpublished block in its private branch21: set (Ls, Lh) = (Ls −Lh + 1, 1) if the new block is mined on a publicbranch that is a prefix of the private branch22: end iftinue mining on its private branch until its advantage is very limited (i.e.,(Ls, Lh) = (2, 1)) which will be discussed later.When some honest miners mine a new block, the length of a publicbranch will be increased by 1. We have the following cases. Case 1) Ifthe new public branch is longer than the private branch, the pool willadopt the public branch and mine on it. (That is why the pool will set(Ls, Lh) = (0, 0).) Case 2) If the new public branch has the same lengthas the private branch, the pool will publish its private block immediatelyhoping that as many honest miners will choose its private branch as possi-ble (since honest miners will see two branches of the same length when the173.3. Analysis of Selfish Mining1,00,0 2,0 3,0j+1,2......i+2,i4,01,13,14,25,3...4,15,26,3 ...5,16,27,3...ai+1,i-1 i+3,i-1a a a ai+2,i-1i+3,i i+4,ia aa aaa aa a..................j-1,0j,1...j+2,3i+j-2,i-1i+j-1,ij+2,2j,0...j+3,3i+j-1,i-1i+j,iaaaaaabj+1,1bbb b bab(1-g) bgHonest miners mine a block on the selfish pool's block with rate bgbgb(1-g)bgb(1-g)bgb(1-g)bgb(1-g)bgb1-g)b(1-g)b(1-g)b(1-g)b(1-g)b(1-g)b(1-g)b(1-g)b(1-g)b(1-g)b(1-g) b(1-g) b(1-g)b(1-g) b(1-g) b(1-g)aaaaaa........................ ... ... ... ... ...Figure 3.2: The Markov process of the selfish mining in Ethereum.private branch is published). Case 3) If the new public branch is shorterthan the private branch by just 1, the pool will publish its private branch sothat all the honest miners will adopt the private branch. Case 4) If the newpublic branch is shorter than the private branch by at least 2, the pool willpublish the first unpublished block since the pool still has a clear advantage.Moreover, if the new block is mined on a public branch that is a prefix ofthe private branch, the pool will set (Ls, Lh) = (Ls − Lh + 1, 1) due to anew forking (caused by the honest miner).3.3 Analysis of Selfish MiningIn this section, we will study the long-term behavior of the selfish min-ing strategy using a Markov model with a particular focus on the miningrevenue.3.3.1 Markov ProcessFor ease of presentation, we re-scale the time axis so that the selfish poolgenerates new blocks at rate α and the honest miners generate new blocks atrate β. We are now ready to define the system state. Recall that Ls(t) is thelength of the private branch and Lh(t) is the length of the public branchesat time t. Clearly, (Ls(t), Lh(t)) captures the system state at time t. The183.3. Analysis of Selfish Miningstate space contains the following states: (0, 0), (1, 0), (1, 1), as well as (i, j)with i− j ≥ 2 and j ≥ 0. It is easy to verify that (Ls(t), Lh(t)) evolves as aMarkov process under our selfish mining strategy and the network model, asillustrated in Fig. 3.2. Moreover, we can show that the process (Ls(t), Lh(t))is positive recurrent and so it has a unique stationary distribution.3.3.2 The Stationary DistributionTo compute the stationary distribution of the process (Ls(t), Lh(t)), weneed to derive the transition rates for the state evolution. The results areprovided below.− q(0,0),(0,0) = βThis transition happens if any honest miner produces a new block,broadcasts it to everyone. Then, the selfish pool adopts the publicbranch and mines on it. Thus, the rate is β.− q(0,0),(1,0) = αThis transition happens if the pool produces a new block and keeps itprivate. Thus, the rate is α.− q(1,0),(2,0) = αThis transition happens if the pool produces a new block and keeps itprivate. Thus, the rate is α.− q(1,0),(1,1) = βThis transition happens if any honest miner produces a new blockand the pool immediately publishes its private block (because the newpublic branch has the same length as the private branch). Thus, therate is β.− q(1,1),(0,0) = α+ β = 1This transition happens if any of the following events happens. 1) Thepool produces a new block and publishes its private branch (because(Ls, Lh) = (2, 1)); 2) Any honest miner produces a new block and thepool has to publish its private branch (because Ls = Lh + 1). Thus,the rate is α+ β = 1.− q(i,j),(i+1,j) = α for i ≥ 2 and j ≥ 0This transition happens if the pool produces a new block and keeps itprivate. Thus, the rate is α.− q(i,j),(i−j,1) = βγ for i− j ≥ 3 and j ≥ 1This transition happens if any honest miner mines a new block on apublic branch which is a prefix of the private branch. Then, the poolpublishes a private block accordingly. Thus, the rate is βγ.193.3. Analysis of Selfish Mining− q(i,j),(0,0) = β for i− j = 2 and j ≥ 1This transition happens if any honest miner produces a new block andthen the pool publishes its private branch (because Ls = Lh + 1).Thus, the rate is β.− q(2,0),(0,0) = βThis transition happens if any honest miner produces a new block andthen the pool publishes its private branch (because Ls = Lh + 1).Thus, the rate is β.− q(i,0),(i,1) = β for i ≥ 3This transition happens if any honest miner produces a new block andthe pool publishes a private block. Thus, the rate is β.− q(i,j),(i,j+1) = β(1− γ) for i− j ≥ 3 and j ≥ 1This transition happens if any honest miner mines a new block on apublic branch which is not a prefix of the private branch. Thus, therate is β(1− γ).Let {pii,j} be the steady-state distribution of the Markov process (Ls(t), Lh(t)).Then, the set {pii,j} satisfies the following global balance equations accordingto the above transition rates.pi0,0 = βpi0,0 + pi1,1 + β∑∞j=0 pi2+j,j ,pi1,1 = βpi1,0,pi3,1 = βpi3,0 +∑∞j=1 βγpi3+j,j ,pii,0 = αpii−1,0, for i ≥ 1,pii,1 = βpii,0 + αpii−1,1 +∑∞j=1 βγpii+j,j , for i ≥ 4,pii,i−2 = β (1− γ)pii,i−1, for i ≥ 4,pii,j = αpii−1,j + β (1− γ)pii,j−1, for j ≥ 2, i ≥ 5.(3.1)Solving the global balance equations, we obtain the following results forthe stationary distribution:pi0,0 =1− 2α2α3 − 4α2 + 1,pii,0 = αipi0,0 for i ≥ 1,pi1,1 =(α− α2)pi0,0,pii,j = αi (1− α)j (1− γ)j f(i, j, j)pi0,0+αi−jγ (1− γ)j−1(1(1− α)i−j−1− 1)pi0,0−γ (1− γ)j−1j∑k=1αi−k (1− α)j−k f(i, j, j − k)pi0,0203.3. Analysis of Selfish Miningfor i ≥ j + 2 and j ≥ 1, where the function f(x, y, z) is defined asf(x, y, z) =x∑sz=y+2sz∑sz−1=y+1..s2∑s1=y−z+3︸ ︷︷ ︸z1, z ≥ 1, x ≥ y + 2,0, otherwise.(3.2)The function f(x, y, z) is a multiple summations. See Appendix B for someconcrete examples. We have the following remarks for the stationary distri-bution in Equation (3.2).Remark 3.1. When 0 < α < 12 , we have 0 < pi0,0 < 1. Specifically, thedistribution pi0,0 only depends on the parameter α and is monotonicallydecreasing. The tendency of pi0,0 suggests that with more hash power, theselfish pool can obtain more lead blocks and so stay in state (0, 0) lessfrequently.Remark 3.2. The distributions pii,0 with i ≥ 1 are decreasing geometricallyand are less than 10−6 when i ≥ 15 when α = 0.4. It suggests that we cantruncate the states in the numerical calculation.3.3.3 Reward AnalysisIn this subsection, we conduct the reward analysis for each state transi-tion. Our analysis differs from the previous analysis (e.g., [22, 48]) in thatwe track various block rewards in a probabilistic way. Recall that each statetransition induces a new block (mined by an honest miner or the pool). Ingeneral, it is impossible to decide the number of rewards associated with thisnew block when it is just created because the “destiny” of this new blockdepends on the evolution of the system. For this reason, we will insteadcompute the expected rewards for the new block. In contrast, the previousanalysis tracks published blocks associated with a state transition (whosedestiny is already determined) rather than the new block and so it cancompute the exact rewards. This gives rise to the following two questions.1. What is wrong with tracking published blocks?2. How shall we compute the expected rewards for a new block at thetime of its creation?To answer the first question, one shall notice that tracking publishedblocks don’t provide enough information to compute the uncle and nephewrewards. Recall from Sec. 2.2.1 that a published regular block can receive213.3. Analysis of Selfish Miningnephew rewards by referencing outstanding uncle blocks. The amount ofnephew rewards depends on the number of outstanding uncle blocks. Assuch, we need to keep track of all the outstanding uncle blocks in the systemtogether with their depth information (which is needed to determine thenumber of uncle rewards). This greatly complicates the state space.To answer the second question, one shall notice that it suffices to computethe expected rewards for a new block by using the following information: theprobability that it becomes a regular block, the probability that it becomesan uncle block, the distance to its potential nephew block (if it indeed be-comes an uncle block). Perhaps a bit surprisingly, all the information can bedetermined when this new block is generated for our selfish mining strategy.The complete analysis is provided in Appendix B [49] for a better presen-tation flow. Here, we just provide a simple example to illustrate our analysis.Assume that the selfish pool has already mined two blocks and kept themprivate at time t. Then, some honest miners generate a new block. Accord-ing to Algorithm 1, the pool publishes its private branch immediately. Assuch, this new block will become an uncle block with probability 1. Fur-thermore, we can show that this block will have a distance of 2 with itspotential nephew block. Thus, this new block will receive an uncle rewardof Ku(2). Similarly, its potential nephew block will receive a nephew re-ward of Kn(2). Moreover, this reward will belong to some honest minerswith probability β(1 + αβ(1 − γ)) and belong to the pool with probability1−β(1+αβ(1−γ)). (See Case 7 in Appendix B [49] for details.) Therefore,the expected rewards associated with this new block are Ku(2) +Kn(2) intotal among which Ku(2) +Kn(2)β(1 + αβ(1 − γ)) rewards will belong tohonest miners (and the remaining will belong to the pool).3.3.4 Revenue AnalysisIn this subsection, we apply the previous reward analysis to computevarious rewards received by the selfish pool and honest miners. First, wecompute the static block rewards for the selfish pool (denoted as rsb) andhonest miners (denoted as rhb ). We have the following results:rsb =(α(1− pi0,0) + (α2 + α2β + αβ2γ)pi0,0)= α− αβ2(1− γ)pi0,0,=α(1− α)2(4α+ γ(1− 2α))− α32α3 − 4α2 + 1(3.3)223.3. Analysis of Selfish Miningandrhb = β(pi0,0 + pi1,1) + β2(1− γ)pi1,0=(1− 2α)(1− α)(α(1− α)(2− γ) + 1)2α3 − 4α2 + 1.(3.4)Note that rsb and rhb represent the long-term average static rewards per timeunit. Since all the miners generate new blocks at rate 1, the maximumlong-term average reward is 1 per time unit. Hence, we have rsb + rhb ≤ 1.Remark 3.3. If we only consider static rewards, the above results are thesame as those in [22], though our approach is different from that in [22].Next, we can compute the uncle block rewards for the selfish pool (de-noted as rsu):rsu = αβ2(1− γ)Ku(1)pi0,0=(1− 2α)(1− α)2α(1− γ)2α3 − 4α2 + 1Ku(1).(3.5)Similarly, we can compute the uncle block rewards for the honest miners(denoted as rhu):rhu = (αβ+β2γ)Ku(1)pi1,0+∞∑i=2βKu(i)pii,0+∞∑i=2∞∑j=1βγKu(i)pii+j,j . (3.6)Remark 3.4. In the current version of Ethereum, the function Ku(·) is givenbelow:Ku(l) ={(8− l)/8, 1 ≤ l ≤ 60, otherwise.(3.7)Our analysis applies to an arbitrary function of Ku(·).Then, we can compute the nephew block rewards for the selfish pool(denoted as rsn) and honest miners (denoted as rhn):rsn = αβKs(1)pi1,0 +∞∑i=2∞∑j=1βi−1γ(α− αβ2(1− γ))Ks(i)pii+j,j (3.8)rhn = αβ2(1−γ)Ks(1)pi0,0+β2γKs(1)pi1,0+∞∑i=2∞∑j=1βiγ(1+αβ(1−γ))Ks(i)pii+j,j .(3.9)Finally, we can obtain the total mining revenue rtotal asrtotal = rsb + rhb + rsu + rhu + rsn + rhn. (3.10)233.3. Analysis of Selfish MiningHence,Rs =rsb + rsu + rsnrtotalgives the share of the mining revenue by the selfish pool.3.3.5 Absolute RevenueWe now define the absolute revenue Us for the selfish pool. As we willsoon see, although the absolute revenue is equivalent to the relative revenue(i.e., the share Rs) in Bitcoin, it is different from the relative revenue inEthereum due to the presence of uncle and nephew rewards.Recall that Bitcoin adjusts the mining difficulty level so that the regularblocks are generated at a stable rate, say 1 block per time unit. Thus, thelong-term average total revenue is fixed to be 1 block reward per time unitwith or without selfish mining. This makes the absolution revenue equivalentto the relative revenue. The situation is different in Ethereum. Even if theregular blocks are generated at a stable rate, the average total revenue stilldepends on the generation rate of uncle blocks, which is affected by selfishmining as we will see shortly. Indeed, Ethereum didn’t take into account thegeneration rate of uncle blocks when adjusting the difficulty level until itsthird milestone. This motivates us to consider two scenarios in our analysis:1) the regular block generation rate is 1 block per time unit, and 2) theregular and uncle block generation rate is 1 block per time unit.In our previous analysis, the regular block generation rate is rsb + rhb ,which is smaller than 1 as explained before. Thus, we can re-scale the timeto make the regular block generation rate to be 1 block per time unit. Inthis scenario, the long-term absolute revenue for the selfish pool isUs =rsb + rsu + rsnrsb + rhb, (3.11)and the long-term absolute revenue for honest miners isUh =rhb + rhu + rhnrsb + rhb. (3.12)Similarly, we can re-scale the time to make the regular and uncle blockgeneration rate to be 1 block per time unit and define long-term absoluterevenues for the selfish pool and honest miners accordingly.243.4. Evaluation Results3.4 Evaluation ResultsIn this section, we build an Ethereum selfish mining simulator to validateour theoretical analysis. In particular, we simulate a system with n =1000 miners, each with the same block generation rate. In our simulations,the selfish pool controls at most 450 miners (i.e., α ≤ 0.45) and runs ourAlgorithm 1, while the honest miners follow the designed protocol in Sec. 3.2.Our simulation results are based on an average of 10 runs, where each rungenerates 100, 000 blocks.3.4.1 Validation of the Theory ResultsIn this subsection, we validate the long-term average absolute revenuesfor the selfish pool and honest miners. Fig. 3.3 plots the results obtainedfrom analysis and simulations. From the results, we can see when γ = 0.5,Ku = 4/8Ks and α changes from 0 to 0.45, the simulation results match ourtheoretical results7. In addition, when α is above 0.163, the selfish pool canalways gain higher revenue from selfish mining than following the protocol.More importantly, when α is below the threshold 0.163, the selfish pool losesjust a small amount of revenue due to the additional uncle block rewards,which is quite different from the results in Bitcoin [22].3.4.2 Impact of the Uncle RewardIn this subsection, we explore the impact of the uncle block rewardson the selfish pool’s revenue and honest miners’ revenues. To this end, wefirst use the uncle reward function Ku(·) in Ethereum (see Sec. 3.3.4 fordetails) and then set the uncle reward as a fixed value regardless of thedistance, ranging from 2/8Ks to 7/8Ks. Here, the fixed uncle reward valuecan directly show its impacts and simplify our understanding.Fig. 3.4 shows that the higher the uncle reward is, the more absoluterevenue both the selfish pool and honest miners can obtain, which is quiteintuitive. It also reveals that the total revenue increases with the selfishpool’s computation power α and soars to 135% of the revenue without self-ish mining, when Ku = 7/8Ks and α = 0.45. This is because, without theconsideration of uncle blocks into difficulty adjustment, the selfish miningcan produce additional uncle and nephew rewards, resulting in the fluctu-ation of total revenue. Additionally, the uncle reward function Ku(·) used7To simplify the numerical calculations of our results, we only consider the states (i, j)with i and j less than 200. This approximation turns out to be accurate when α ≤ 0.45.253.4. Evaluation Results0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45Selfish Miners’ Computaion Power α00.10.20.30.40.50.60.70.80.91AverageAbsoluteRevenueHonest MiningSelfish MinersSelfish Miners (sim)Honest MinersHonest Miners (sim)Figure 3.3: Revenue rate for the selfish pool and honest miners when γ = 0.5,Ku = 4/8Ks and α changes from 0 to 0.45.in Ethereum has the same effect as simply setting Ku = 7/8Ks for selfishpool’s revenue (as explained in Sec. 3.3.4). In contrast, Ku(·) functions com-plicatedly for the honest miners’ revenue. When α is small, its impact issimilar to the case of Ku = 7/8Ks, and when α is close to 0.45, its impactis similar to the case of Ku = 4/8Ks. This is because, with the increaseof α, the average referencing distances of honest miners’ uncle blocks willincrease, which further leads to the decrease of honest miners’ average unclerewards when using the function Ku(·).3.4.3 Comparison with BitcoinIn this subsection, we compare the hash power thresholds of makingselfish mining profitable in Ethereum and Bitcoin under different values263.4. Evaluation Results0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45Selfish Miners’ Hash Power α00.10.20.30.40.50.60.70.80.911.11.21.31.4AverageAbsoluteRevenueKu = 2/8, Selfish MinersKu = 4/8, Selfish MinersKu = 7/8, Selfish MinersKu(·), Selfish MinersKu = 2/8, Honest MinersKu = 4/8, Honest MinersKu = 7/8, Honest MinersKu(·), Honest MinersKu = 2/8, TotalKu = 4/8, TotalKu = 7/8, TotalKu(·) TotalFigure 3.4: Revenue rate for the selfish pool, honest miners under differentuncle block reward Ku.of γ. In Ethereum, we use function Ku(·) to compute the uncle rewards.Particularly, we compute the thresholds for the two scenarios: 1) the regularblock generation rate is 1 block per time unit, and 2) the regular and uncleblock generation rate is 1 block per time unit.From Fig. 3.4.3, we can see that the higher γ is, the lower the hash powerneeded for making selfish mining profitable. Especially, when γ = 1, theselfish mining in Bitcoin and Ethereum can always be profitable regardlessof their hash power. Besides that, the results show that the hash powerthresholds of Ethereum in scenario 1 are always lower than in Bitcoin. Bycontrast, the hash power thresholds in scenario 2 are higher than Bitcoinwhen γ ≥ 0.39. This is because the larger γ is, the more blocks minedby honest miners are uncle blocks. However, in scenario 2 the additionalreferenced uncle blocks will reduce the generation rate of regular blocks,resulting in the decrease of selfish pools’ block rewards. Thus the selfishpool needs to have higher hash power to make selfish mining profitable. This273.4. Evaluation Results0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1Network Capacity γ00.050.10.150.20.250.30.35Selfishminers’ThresholdαIttay Model in BitcoinScenario 1 in EthereumScenario 2 in EthereumFigure 3.5: The profitable threshold of hash power in Bitcoin and Ethereum.suggests that Ethereum should consider the uncle blocks into the difficultyadjustment under the mining strategy given in Algorithm 1.Remark 3.5. There are two gaps between the simulation and the real-worldexperiments. First, in the real world, nodes execute PoW to produce blocks,whereas, in our simulation, blocks are produced by using the Poisson process.However, the difference does not affect the accuracy of our results. This isbecause, many measurements and studies show that the block mining pro-cess in PoW can be well approximated by the Poisson process [4, 17, 55].Moreover, nowadays, the total computation power in the Ethereum networkis huge, which makes it impossible to have a real-world experiment. Sec-ond, in our simulation, blocks immediately arrive at all nodes once they arepublished. This setting is consistent with the assumption that we don’t con-sider block propagation delay in the analysis. This assumption is reasonablewhen the block propagation delay is much smaller than the block genera-tion interval. However, to make the simulation closer to the experiments in283.5. Discussionthe real world, we can use the existing measurement data of the Ethereumnetwork to characterize the point-to-point channels between nodes [26, 27].Specifically, each channel can be characterized by two parameters: latencyand bandwidth, which abstract the message transmission path in the realworld. In this way, we can capture the impact of today’s Ethereum network.We leave it as one of our future work.3.5 Discussion3.5.1 Uncle Block RewardsIn Ethereum, uncle and nephew rewards are initially designed to solve themining centralization bias—miners form or join in some big mining pools [].This is because, due to propagation delay, mining pools with huge hashpower are less likely to generated stale blocks and can be more profitablefor mining. Thus, rewarding the stale block can reduce the mining pools’advantage [19] and make them less attractive for small miners. However,as analyzed previously, the uncle reward (computed by using the functionKu(·)) can greatly reduce the cost of launching selfish mining. To mitigatethis issue, here we propose a simple uncle reward function motivated by ouranalysis in Sec. 3.3.3. It shows that the uncle blocks mined by the selfish poolcan always be referenced with block distance one, i.e., the maximum unclereward 7/8Ks using the function Ku(·). In contrast, the honest miners’uncle blocks cannot obtain such high rewards. To illustrate the explicitsituation, we provide the distribution of the honest miners’ uncle block withdifferent referencing block distances in Table 3.1 given γ = 0.5. The resultsshow that with the increase of α, the average referencing distance of honestminers’ blocks is increasing. Thus, we should decrease the reward for uncleblocks with distance one and increase the reward for the uncle blocks withlonger distances. In particular, we can simply set the uncle reward functionKu(·)) as a fixed value, say Ku = 4/8Ks, if uncle blocks’ referencing blockdistance is between 1 and 6. We recompute the threshold of making selfishmining profitable using this new function and find that when γ = 0.5, thethreshold increases from 0.054 to 0.163 in scenario 1, and from 0.270 to 0.356in scenario 2. In other words, this simple change makes it harder for theselfish pool to be profitable.293.6. Related WorkTable 3.1: The distribution of honest miners’ uncle block with differentreferencing block distancesReferencing distance α = 0.3 α = 0.451 0.527 0.2842 0.295 0.2493 0.111 0.1714 0.043 0.1255 0.017 0.0966 0.007 0.075Expectation 1.75 2.723.5.2 Mining Difficulty AdjustmentIn the previous analysis, we focus on analyzing the revenues for the self-ish miner when the mining difficulty becomes stable after the attack. Thetheoretical results show that when a selfish miner has enough fraction of com-putation power, it can obtain more revenue than honest mining. However,this does not hold before the mining difficulty becomes stable (Ethereumadjusts mining difficulty according to block intervals, and this proceduretakes a period until difficulty becomes stable after the attack). This is be-cause selfish mining in this period always yields fewer rewards than honestmining. Ideally8, the selfish miner can obtain a regular block reward for ev-ery mined block. By contrast, when launching the selfish mining attack, theselfish miner has the possibility to make its blocks stale (i.e., uncle blocks).As we know, an uncle block reward is smaller than a regular block reward.Hence, the absolute revenue of the selfish miner is always smaller than thatin honest mining.3.6 Related WorkThe research of selfish mining is mostly focused on Bitcoin with roughlytwo directions: 1) optimizing the selfish mining strategies to increase the rev-enue and lower the threshold of launching selfish mining attacks; 2) propos-ing defense mechanisms. In [22], Eyal and Sirer developed a Markov process8Without considering block propagation delay, these are no forking blocks, i.e., everymined block is included in the longest chain.303.7. Summaryto model the Selfish-Mine Strategy and to evaluate the selfish pool’s relativerevenue. Moreover, they proposed a uniform tie-breaking defense againstselfish mining, which is adopted in Ethereum. Inspired by this seminal pa-per, Sapirshtein et al. [62] and Nayak et al. [48] demonstrated that byadopting the optimized strategies, the threshold of the hashing power tomake selfish mining profitable can be reduced to 23.2% even when honestminers adopt the uniform tie-breaking defense. Furthermore, the authors in[31] took the propagation delay into the analysis of selfish mining.As for defense mechanisms, Heilman proposed a defense mechanismcalled Freshness Preferred [32], in which by using the latest unforgeabletimestamp issued by a trusted party, the threshold can be increased to 32%.Bahack in [6] introduced a fork-punishment rule to make selfish mining un-profitable. Specifically, each miner in the system can include fork evidencein their block. Once confirmed, the miner can get half of the total rewards ofthe winning branch. Solat and Potop-Butucaru [63] propose a solution calledZeroBlock, which can make selfish miners’ block expire and be rejected by allthe honest miners without using forgeable timestamps. In [75], the authorsproposed a backward-compatible defense mechanism called weighted FRPwhich considers the weights of the forked chains instead of their lengths.This is similar in spirit to the GHOST protocol [66].There exist very few studies about the selfish mining attack in Ethereum.The work by Gervais et al. [27] is among the first to develop a quantita-tive framework to analyze selfish mining as well as double-spending in var-ious PoW blockchains. Particularly, they developed optimal selfish-miningstrategies for various PoW blockchains. However, their work didn’t considerthe general functions of uncle and nephew rewards. Instead, they focused ona special case when the uncle reward is always 78 of the block reward. Theauthor in [43] proposed to exploit the flaw of difficulty adjustment to mineadditional uncle blocks, which is shown less profitable than our selfish min-ing strategy. In [61] Ritz and Zugenmaier built a Monte Carlo simulationplatform to quantify the security of the Ethereum after EIP100. However,their paper contains no mathematical analysis and cannot directly capturethe effects of uncle block rewards and nephew rewards.3.7 SummaryIn this chapter, we analyze selfish mining in Ethereum. Specifically,we have proposed a Markov model to analyze a selfish mining strategy inEthereum. Our model enables us to evaluate the impact of the uncle and313.7. Summarynephew rewards, which is generally missing in the previous analysis for self-ish mining in Bitcoin. In particular, we have shown how these rewardsinfluence the security of Ethereum mining. Additionally, we have computedthe hashing power threshold of making selfish mining profitable under differ-ent scenarios, which is essential for us to evaluate the security of Ethereummining and to design new reward functions.As one of our major findings, we notice that it is important to con-sider uncle blocks when adjusting the mining difficulty level. Otherwise,Ethereum would be much more vulnerable to selfish mining than Bitcoin.This finding supports the emendation adopted by the third milestone ofEthereum. However, once the mining mechanism is changed, the selfishpool is likely to change its new mining strategies to maximize its profit.32Chapter 4Incentive Analysis ofBitcoin-NG, RevisitedThis chapter revisits the incentive analysis of Bitcoin-NG. The previousincentive analysis of Bitcoin-NG has two limitations. First, the previousanalysis completely ignores the impact of network capacity [21, 69, 71].Second, previous analysis mostly focuses on microblocks. To address thefirst limitation, we develop a new probabilistic analysis that takes networkcapacity into account. In particular, we model the interval between twoconsecutive key blocks as an exponential random variable and introducethe generation rate of microblocks to capture the impact of network capac-ity. Then, we apply the Chernoff-type bounding techniques to derive thelong-term average revenue of the adversary. To address the second limita-tion, we leverage a Markov decision process (MDP) model to jointly analyzethe incentive of key blocks and microblocks. Although similar analysis hasbeen conducted by Sapirshtein et al. [62] in the context of Bitcoin9, the mi-croblock structure in Bitcoin-NG introduces additional complexity for theMDP design (e.g., more mining strategies and rewards). To make the MDPtractable, we confine our analysis to a family of selfish mining strategies10.4.1 System Model4.1.1 Mining ModelFollowing the mining models [21, 22, 49], we consider a collection ofn miners, denoted by the set N . We assume a subset of miners S ⊂ Nare selfish and can deviate from the protocol to maximize their profit. Theother miners in N \S are honest and follow the protocol. The i-th miner hasmi fraction of the total hash power. In addition, the selfish (respectively,honest) miners control α (respectively, β) fraction of total mining power.9Due to the similarity, the MDP can be directly used to model the key-block miningin Bitcoin-NG.10This family is broader than that in the existing analysis, as discussed in Sec. 4.4.3.334.1. System ModelThat is, α =∑i∈S mi and β =∑i∈N\S mi. Clearly, α+ β = 1. We assumethat all the selfish miners form a mining pool controlled by a single player,which is referred to as the selfish miner.The mining process of the key block can be modeled as a Poisson processwith rate f , as shown in [5, 47]11. The key block mining process of the ithminer is also a Poisson process with the rate mif . Hence, the selfish minergenerates key blocks at rate αf , and the remaining honest miners (as awhole) generate key blocks at rate βf . In addition, the miner of each keyblock becomes a leader and can issue a series of microblocks containingas many transactions as possible (up to the maximum microblock size) ata constant rate v until the next key block is mined. Specifically, a block(including key block and microblock) mined by an honest (respectively, theselfish) miner is referred to as honest (respectively, selfish) block.Following the network model of Bitcoin [22, 49], we assume that honestminers are fully connected through the underlying network, and an hon-est miner spends negligible time to broadcast a key block or microblock inBitcoin-NG12. In addition, we assume that the selfish miner can broadcastits private blocks immediately after it sees a new honest key block.4.1.2 Mining RewardsIn Bitcoin-NG, there are two types of rewards, namely key-block rewardand transaction fee. Every miner obtains a key-block reward if it mines akey block by successfully solving a PoW puzzle and its key block ends up inthe longest chain. In addition, each transaction has a fee (i.e., transactionfee) as a reward to incentive a key-block miner to verify and execute thistransaction. This fee encourages miners to include as many transactions aspossible (up to the microblock size limit). For simplicity, we assume twotypes of transactions according to their transaction fees: “whale” transac-tions with a high fee and regular transactions with a low fee. Also, weassume that the vast majority of transactions are regular ones. Next, weassume that the transaction size is fixed, and so the maximum number oftransactions included in a microblock is also fixed. We also assume that11The key block is mined by solving the PoW puzzle, and the value of f can be calculatedby the average block interval, which is 10 minutes in Bitcoin and 100 seconds per blockin Bitcoin-NG.12This assumption is reasonable for key blocks because the inter-arrival time of twoconsecutive key blocks is often much larger than the block propagation delay. On theother hand, this assumption can be relaxed for microblocks, as we will show later.344.2. Incentive Analysis for Microblockminers have enough pending transactions to be included in microblocks13.We call a microblock regular if it contains only regular transactions. Inaddition, we refer to the total transaction fees included in a regular mi-croblock as the microblock fee and use Rt to denote it. In addition, weuse Rb to denote the key-block reward. Let k = Rb/Rt denote the ratio ofthe block reward to the microblock fee. This ratio k ranges from (0,∞).When k approaches 0 (respectively, ∞), it implies that the transaction fee(respectively, key-block reward) dominates the reward. The different valuesof k exhibit the various impact of rewards on the Bitcoin-NG system.4.1.3 Mining RevenueThe selfish miner is incentivized to find an optimal selfish mining strategyto increase its revenue. Specifically, the utility of the selfish miner can bedefined as its relative revenue [22, 62], i.e., the ratio of the selfish miner’srevenue (including key-block reward and transaction fees) to all miners’revenue. In other words, the selfish miner would like to increase its shareof key-block reward and transaction fees generated by the system, which isgiven byu = limt→∞ra(t) + ta(t)ra(t) + rh(t) + ta(t) + th(t). (4.1)Here, ra(t) and ta(t) are the key-block rewards and transaction fees won byselfish miners during time [0, t], respectively. . Similarly, rh(t) and th(t) arethe key-block rewards and transaction fees won by honest miners. Note thatall of them are random variables. As t→∞, the ratio in (4.1) converges bythe law of large numbers.4.2 Incentive Analysis for MicroblockIn this section, we first introduce the mining strategies for microblocksand then present the existing incentive analysis. Finally, we discuss thelimitations of the existing analysis.4.2.1 Microblock Mining StrategiesIn Bitcoin-NG, an honest key-block miner includes transactions in mi-croblocks and publishes these microblocks to win transaction fees. This is13This assumption is reasonable in Bitcoin and Ethereum-like public blockchains. Forinstance, a mempool visualization website [35] shows that the number of pending trans-actions is around 136k in May 2021.354.2. Incentive Analysis for MicroblockBjBj+1Bj+1...Selfish key block Honest key block MicroblockFigure 4.1: An example of the transaction inclusion attack. The firsttwo microblocks after the selfish Bj have been published and so they arepublic to honest miners. The other microblocks are kept private. A dashedsquare block denotes a future mined block.called the transaction inclusion rule. In addition, an honest miner shouldaccept as many microblocks issued by the previous key-block miner as pos-sible and mine on the latest received microblock, i.e., obeying the longestchain extension rule. By contrast, a selfish miner could break the transac-tion inclusion and the longest chain extension rules to maximize its profitas explained below:− Transaction inclusion attack. When the selfish miner publishes onekey block and generates multiple microblocks, it keeps the last severalmicroblocks private. That is, the selfish miner continues to mine on topof its latest microblock chain, while honest miners can only mine on top ofthe last published microblock. Fig. 4.1 shows the case in which the selfishminer withholds some of its microblocks mined after the key block Bj ,and honest miners mine on the last public microblock of the selfish miner.This attack is incentivized if transaction fees in microblocks go primarilyto the next key-block owner. (See the transaction fee distribution inSec 4.2.)− Longest chain extension attack. When the selfish miner adopts anhonest key block, it can reject some (or all) microblocks and mine directlyon the last accepted microblock (or the last key block, respectively). Inother words, the selfish miner rejects the transactions in these microblocksissued by the previous honest key-block miner. This attack is illustratedin Fig. 4.2. This attack is incentivized if transaction fees go primarily tothe current key-block owner.364.2. Incentive Analysis for Microblock...Selfish key block Honest key blockBjBjBjMicroblockFigure 4.2: An example of the longest chain extension attack. Theselfish miner rejects all the microblocks and mines it key block on top of thehonest Bj . A dashed square block denotes a future mined block.4.2.2 Exiting AnalysisIn this section, we present the prior incentive analysis of microblocks[21, 71]. In particular, the analysis does not consider the selfish miningof key blocks. That is, it assumes that the selfish miner always adoptshonest miners’ key blocks and immediately publishes its new key blocks.This assumption is justified shortly and will be relaxed by considering thejoint mining of microblocks and key blocks in Sec. 4.4. In addition, as thepropagation delay of key blocks is negligible, forked key blocks are also notconsidered.To resist the transaction inclusion attack and the longest chain exten-sion attack, Bitcoin-NG divides the transaction fees included in microblocksbetween two consecutive key-block miners into two parts. The first key-block miner gets the r fraction (r ∈ [0, 1]), while the second one obtainsthe remaining 1 − r fraction. Fig. 4.3 illustrates this fee distribution rule.The remaining subsections explain how to decide the value of r to resist themicroblock mining attacks.Resisting Transaction Inclusion AttackRecall from Sec. 4.2.1 that the selfish miner can withhold a microblockto avoid sharing its transaction fees with the subsequent key-block miner.(We refer readers to the original paper [21] for more details.). Note thatthe probability for the selfish (respectively, honest) miner mines a blockis α (respectively, β = 1 − α). To guarantee the average revenue of the374.2. Incentive Analysis for MicroblockBj...Honest key block MicroblockBT  1rFigure 4.3: Bitcoin-NG fee distribution rule.selfish miner launching the above attack is smaller than what it deserves,the distribution ratio r should satisfywin 100%︷ ︸︸ ︷α× 100% +Lose 100%, but mine after txn︷ ︸︸ ︷(1− α)× α× (100%− r) < r, (4.2)therefore r > 1 − 1−α1+α−α2 . This ratio requirement encourages the selfishminer to place a transaction in a public microblock.Later, Yin et al.[71] found that the above computation neglects a case:the incumbent leader can be re-elected as the next leader and gain an extraα(1−r) fraction of the transaction fee. Thus, the distribution ratio r shouldsatisfywin 100%︷ ︸︸ ︷α× 100% +Lose 100%, but mine after txn︷ ︸︸ ︷(1− α)× α× (100%− r) < r + α(1− r), (4.3)therefore r > α1−α .Resisting Longest Chain Extension AttackTo increase revenue from some transactions, the selfish miner can ig-nore these transactions in an honest microblock and mine on a previousmicroblock. Later on, if the selfish miner mines a key block, it can placethese transactions in its own microblock. To resist this attack, the selfishminer’s revenue in this case must be smaller than the revenue obtained byobeying the longest chain extension rule. Therefore, we haveMine next key block︷ ︸︸ ︷α× r +Mine the third key Block︷ ︸︸ ︷α2 × (100%− r) <Mine on microblock︷ ︸︸ ︷α(100%− r) , (4.4)384.2. Incentive Analysis for Microblockwhich leads to r < 1−α2−α . Taking the upper bound into consideration, thedistribution ratio r satisfies 1 − 1−α1+α−α2 < r <1−α2−α . In particular, when αis less than 25%, we obtain 37% < r < 43%. Hence, r = 40% is chosen inthe Bitcoin-NG [21].4.2.3 Limitations of Existing AnalysisWe now describe some limitations of the previous analysis, which canhelp us to better understand the differences between the above analysis andour analysis in the following section.Before giving detailed descriptions, let us replay the longest chain ex-tension attack, as shown in Fig. 4.4. We make two simplifications to betterillustrate the analysis limitation: 1) each leader is allowed to only create onemicroblock; 2) each microblock is allowed to only contain one transaction.Consider a scenario where an honest miner produces a key block Bj as wellas a microblock containing a transaction tx. If the selfish miner obeys thelongest chain extension rule and finds the next key block with probability α,it will get a 1 − r fraction of the transaction fee (which corresponds to thelast item in Equation (4.4)). However, the selfish miner can directly mine onthe key block Bj , hoping to win a higher transaction fee of tx. If the selfishminer happens to create the next key block Bj+1 with probability α, it canwin r fraction of the transaction fee by including tx in its microblock (whichcorresponds to the first item in Equation (4.4)). If the selfish miner is luckyto mine the next consecutive key block Bj+2, it will win the remaining 1− rof the transaction fee. Combining all conditions leads to Equation (4.4).The above simple analysis is quite reasonable if the selfish miner justhopes to get a higher fee from a targeted transaction tx. However, in real-ity, the selfish miner usually aims to increase its revenue from all transac-tions instead of just a targeted one. From the above discussion, we can seethat if the selfish miner applies the strategy to all the transactions ratherthan a single targeted one, it will quickly use up the space of its futuremicroblocks. As a result, the selfish miner cannot include another trans-action in its microblock, thereby losing the associated transaction fee. Inother words, the existing analysis ignores the impact of transaction size andmicroblock capacity, which magnifies the selfish miner’s potential revenuefrom the attack. On the other hand, the existing analysis works well forwhale transactions with high fees, which are rare so that we don’t need toworry about the space. As we explained before, most of the transactions incurrent blockchain systems have low fees. Therefore, we need to develop anew analysis for those transactions.394.3. Revisiting Incentive Analysis for MicroblockBjBj+1 BtxtxFigure 4.4: A simple example to illustrate the limitation of theprevious analysis. The selfish miner mines directly on block Bj and triesto include transaction tx in its future microblock.Next, we turn our attention to another limitation of the existing analysis.It assumes that the selfish miner always adopts honest miners’ key blocksand immediately publishes its new key blocks (i.e., honest mining of keyblocks). In other words, it does not consider the impact of key-block selfishmining. This assumption can only be justified when the selfish miner’s com-putation power is less than the threshold of making key-block selfish miningprofitable because the optimal mining strategy for key blocks is indeed hon-est mining [21, 22, 62]. However, once the selfish miner’s computation powerα is above the threshold, the selfish miner has the incentive to launch thekey-block mining attack and so the impact of the key-block selfish miningcannot be ignored anymore. This motivates us to study the selfish miningof both microblock and key block in Sec. 4.4 when α is above the threshold.4.3 Revisiting Incentive Analysis for MicroblockIn this section, we consider the scenario where α is smaller than thethreshold of making key-block selfish mining profitable. This allows us tofocus only on incentive analysis for microblocks. Recall that there are twotypes of transactions: whale transactions and regular transactions. As ex-plained in Sec. 4.2.3, whale transactions are so rare that they use little mi-croblock space. For this reason, we can ignore their space requirement (evenunder the network capacity constraints) and apply the existing analysis.On the other hand, regular transactions consume most of the microblockspace. Hence, we can no longer ignore their space requirement and need todevelop a new analysis. To this end, we consider the revenue of transactionfees in terms of regular transactions for the selfish miner and honest minersduring a time interval [0, t]. Without loss of generality, we assume that404.3. Revisiting Incentive Analysis for Microblockthere exists a block B0 that the selfish miner and honest miners both agreeto mine on at the starting time. (For example, B0 can be the genesis block.)Let M(t) be the number of key blocks mined during the time interval [0, t].Let Xi (i ∈ [0,M(t)]) denote an indicator random variable which equals oneif the i-th key block is a selfish key block, as described belowXi ={1, selfish key block0, honest key block.Without loss of generality, we assume block B0 is an honest key block. Forother key blocks, the possibility that it is a selfish key block is equal to α.After mining a key block, its owner can issue a series of microblocks at aconstant rate v until the next key block is mined. Here, the rate v capturesthe network capacity constraints. Let Yi denote the interval between thei-th key block and (i + 1)-th key block. Thus, the number of producedmicroblocks between i-th and (i + 1)-th key blocks is vYi. In addition,each microblock contains a total fee of Rt because we only consider regulartransactions here. We are now ready to compute the suitable value of r toresist the two microblock attacks for regular transactions.4.3.1 Resisting Transaction Inclusion AttackRecall the attack from Sec. 4.2.1 that the selfish miner hides some ofits microblocks generated after a key block but keeps mining on top of themicroblock chain. Hence, honest miners directly mine on top of the selfishminer’s last published block. Let ρ denote the fraction of the unpublishedmicroblocks among all the selfish microblocks between two consecutive keyblocks. In particular, ρ = 1 means that the selfish miner hides all themicroblocks it has generated between two consecutive key blocks. Thus,if any two consecutive key blocks satisfy (Xi, Xi+1) = (1, 0) , there are(1 − ρ)vYi microblocks between them from the view of an honest miner;otherwise, there are vYi microblocks.Let Zi denote an indicator random variable equal to one if {Xi =1, Xi+1 = 0}, and equal to zero otherwise. Next, let Z =∑M(t)−1i=1 Zi.Suppose M(t) = m. The following lemma will aid us to bound the value ofZ with high probability:Lemma 4.1. Form consecutive key blocks, the number of block pairs (Xi, Xi+1) =(1, 0) has the following Chernoff-type bound: For 0 < δ < 1,Pr(|Z − αβ(m− 1)| > δαβ(m− 1)) < e−Ω(δ2αβm). (4.5)414.3. Revisiting Incentive Analysis for MicroblockProof. Without loss of generality, we assume that m is odd. Let Zodd =Z1+Z3+ · · ·+Zm−2 and Zeven = Z2+Z4+ · · ·+Zm−1. Then, Z = Zodd+Zeven. It is easy to show that E (Zodd) = E (Zeven) = αβ(m − 1)/2, sinceP{Zi = 1} = P{Xi = 1}P{Xi+1 = 0} = αβ. Note that {Z1, Z3, . . . , Zm−2}are independent random variables, because Zi is a function of (Xi, Xi+1).Hence, Zodd is a sum of i.i.d. random variables. So is Zeven. By Lemma A.1,we havePr (Z < (1− δ)αβ(m− 1)) < e−Ω(δ2αβ(m−1)) = e−Ω(δ2αβm).Similarly, we have Pr (Z > (1 + δ)αβ(m− 1)) < e−Ω(δ2αβm).This lemma shows that asm increases, the number of key pairs (Xi, Xi+1) =(1, 0) is between (1− δ)αβm and (1 + δ)αβm with high probability.Next, we compute the selfish miner’s relative revenue for large m. Onthe one hand, the total amount of transaction fees for all the miners is givenby∑m−1i=1 (vYiRt − ρvZiYiRt). To see this, note that there are∑m−1i=1 vYimicroblocks produced with associated transaction fees∑m−1i=1 vYiRt. Notealso that once Zi = 1, there are ρvYi microblocks not being included inthe longest chain due to the transaction inclusion attack. Hence, the associ-ated loss of transaction fees is∑m−1i=1 ρvZiYiRt. On the other hand, the totaltransaction fees for the selfish miner is given by∑m−1i=1 (αvYiRt − rρvZiYiRt).To see this, note that without any attack, the selfish miner can get α fractionof the total transaction fees given by∑m−1i=1 αvYiRt. Note also that with thetransaction inclusion attack, the selfish miner will lose r fraction of the totalloss of transaction fees as the first leader. Combining the above analysis, wehave the following lemma for large m.Lemma 4.2. The selfish miner’s relative revenue u converges to α−rαβρ1−αβρwith high probability as m→∞.Proof. According to the previous analysis, we haveu = limm→∞∑m−1i=1 (αvYiRt − rρvZiYiRt)∑m−1i=1 (vYiRt − ρvZiYiRt)= limm→∞∑m−1i=1 (αvYiRt − rρvZiYiRt)/(m− 1)∑m−1i=1 (vYiRt − ρvZiYiRt)/(m− 1)→vRt(α− rαβρ)/fvRt(1− αβρ)/f=α− rαβρ1− αβρ,(4.6)424.3. Revisiting Incentive Analysis for Microblockwhere the third step comes from the facts that (1) Yi follows the exponentialdistribution with mean 1/f and that (2) Yi is independent of Zi. Morespecifically, we have limm→∞∑m−1i=1Yim−1 → 1/f by the law of large numbersand limm→∞∑m−1i=1ZiYim−1 → αβ/f by Lemma 4.1.This lemma says that for large m, the selfish miner’s relative revenue is(α−rαβρ)(1−αβρ) . Recall that the key block generation process is a Poisson processwith rate f , and so M(t) is a Poisson arrival process. Hence, when t tendsto infinity, M(t)/t → f holds with high probability. Therefore, with highprobability, the maximum relative revenue of the selfish miner during [0, t]isu = max0≤ρ≤1α− rαβρ1− αβρ= r + max0≤ρ≤1α− r1− αβρ.(4.7)If r ≤ α, the optimal ρ = 1 and the correspondingu = r +α− r1− αβ.In this case, u is always larger than α since 1−αβ < 1. This means that theselfish miner can always have a relative revenue greater than its fair shareby utilizing this attack. On the other hand, if r > α, the optimal ρ = 0and u = α. This means that the maximum relative revenue that the selfishminer can obtain is honest mining (i.e., ρ = 0). Therefore, we should setr > α to guarantee the adversary cannot gain more from the transactioninclusion attack.consider the scenario where α is smaller than the threshold of makingkey-block selfish mining profitable. This allows us to focus only on incentiveanalysis for microblocks. Recall that there are two types of transactions:whale transactions and regular transactions. Whale transactions are usuallyrare such that they use little microblock space. For this reason, we can ignoretheir space requirement (even under the network capacity constraints) andapply the existing analysis.4.3.2 Resisting Longest Chain Extension AttackRecall the attack from Sec. 4.2.1 that the selfish miner can bypass somehonest microblocks and mines directly on an old honest block. Similarly,let ρ denote the rejected microblock fraction. In particular, ρ = 1 meansthat the selfish miner rejects all honest microblocks and mines directly on434.3. Revisiting Incentive Analysis for Microblockthe last honest key block. More precisely, if two consecutive key blocks are(Xi, Xi+1) = (0, 1), there are (1− ρ)vYi honest microblocks accepted by thelongest chain. Let Ki denote an indicator random variable equal to one if{Xi = 0, Xi+1 = 1}, and equal to zero otherwise. Let K =∑m−1i=1 Ki. Thefollowing lemma will aid us to bound the expectation of K for m blocks:Lemma 4.3. For them block sequence, the number of block-pair (Xi, Xi+1) =(0, 1) has the following Chernoff-type bound: For 0 < δ < 1,Pr(|K − αβ(m− 1)| > δαβ(m− 1)) < e−Ω(δ2αβm). (4.8)Proof. The proof is similar to Lemma 4.1. We omit it here due to spaceconstraints.Next, we compute the selfish miner’s relative revenue for large m. Onthe one hand, the total amount of transaction fees for all the miners is givenby∑m−1i=1 (vYiRt − ρvKiYiRt). To see this, recall that there are∑m−1i=1 vYimicroblocks produced with associated transaction fees∑m−1i=1 vYiRt. OnceKi = 1, there are ρvYi microblocks not being included in the longest chaindue to the longest chain extension attack. Hence, the associated loss oftransaction fees is∑m−1i=1 ρvKiYiRt. On the other hand, the total transactionfees for the selfish miner is given by∑m−1i=1 (αvYiRt − rρvZiYiRt). To seethis, recall that without any attack, the selfish miner can get α fraction ofthe total transaction fees given by∑m−1i=1 αvYiRt. With the longest chainextension attack, the selfish miner will lose 1 − r fraction of the total lossof transaction fees as the second leader. Combining the above analysis, wehave the following lemma for larger mLemma 4.4. The selfish miner’s relative revenue µ converges to α−(1−r)αβρ1−αβρwith high probability as m→∞.Proof. According to the previous analysis, we haveu = limm→∞∑m−1i=1 (αvYiRt − (1− r)ρvKiYiRt)∑m−1i=1 (vYiRt − ρvKiYiRt)= limm→∞∑m−1i=1 (αvYiRt − (1− r)ρvKiYiRt)/(m− 1)∑m−1i=1 (vYiRt − ρvKiYiRt)/(m− 1)→vRt(α− (1− r)αβρ)/fvRt(1− αβρ)/f=α− (1− r)αβρ1− αβρ,(4.9)444.3. Revisiting Incentive Analysis for Microblockwhere the third step comes from the facts that Yi follows the exponentialdistribution with mean 1/f and that Yi is independent of Ki.This lemma says that for large m, the selfish miner’s relative revenue isα−(1−r)αβρ1−αβρ . Similar with the previous analysis, we can show that as t→∞,with high probability, the maximum relative revenue of the selfish minerduring [0, t] isu = max0≤ρ≤1α− (1− r)αβρ1− αβρ= 1− r + max0≤ρ≤1r − β1− αβρ.(4.10)If r ≥ β, the optimal ρ = 1 and the correspondingu = 1− r +r − β1− αβ.In this case, u is always larger than α since 1 − αβ < 1. This means thatthe selfish miner can always have a relative revenue greater than its fairshare by launching this attack. On the other hand, if r < β, the optimalρ = 0 and u = α. This means that the maximum relative revenue that theselfish miner can obtain is honest mining (i.e., ρ = 0). Therefore, we shouldset r < β to guarantee the adversary cannot gain more from the longestchain extension attack. Combining the two incentive sub-mechanisms oftransaction inclusion and longest chain extension, the value of r needs tosatisfy thatα < r < β.4.3.3 DiscussionWe show that the existing analysis in [21, 71] can be used to boundthe split ratio r for whale transactions. Also, we develop a new analysisto bound the ratio r for regular transactions under network capacity con-straints. These bounds are depicted in Fig. 4.5. As we can see, our boundα < r < β (for regular transactions) contains the previous two bounds1 − 1−α1+α−α2 < r <1−α2−α andα1−α < r <1−α2−α (for whale transactions). Thisleads to several interesting implications.First, introducing network capacity constraints doesn’t make it harderto maintain the incentive compatibility of Bitcoin-NG. This is because thebounds for whale transactions are the same as the previous ones and thebound for regular transactions contains the previous ones. Second, when αis smaller than 29%, we can find a value of r that satisfies all the bounds.454.3. Revisiting Incentive Analysis for MicroblockThis means that the incentive compatibility of Bitcoin-NG can be main-tained for all types of transactions even under network capacity constraintsin this regime. Third, when α is larger than 29%, we cannot find a valueof r that satisfies all the bounds, because the two bounds for whale trans-actions both become invalid. This means that the incentive compatibilityof Bitcoin-NG can be maintained only for regular transactions but not forwhale transactions in this regime. In other words, the presence of whaletransactions might cause instability of the whole system in this regime. Assuch, some defense mechanisms should be designed accordingly.0.0 0.1 0.2 0.3 0.4 0.5The selfish computation power α0.00.20.40.60.81.0The split ratio rOur extended regionYin et al. [38] extended regionEyal et al. [10] regionFigure 4.5: The comparison of the transaction fee distribution ratio.464.4. Incentive Analysis for both Microblock and Key Block4.4 Incentive Analysis for both Microblock andKey BlockIn this section, we consider the scenario where α is larger than the thresh-old of making key-block selfish mining profitable. This requires us to studythe selfish mining strategies for key blocks and microblocks jointly. To thebest of our knowledge, we are among the first to conduct such an analysis,since most previous analysis only focuses on the incentive of microblocks.4.4.1 Markov Decision Process (MDP)We apply MDP to model various selfish mining strategies. AlthoughMDP has been used to model the selfish mining strategies in Bitcoin (see,e.g., [62]), its application to Bitcoin-NG is new and non-trivial due to thepresence of the transaction inclusion attack and the longest chain extensionattack.To make our analysis tractable, we introduce two simplifications. First,we assume that the key block interval is 1/f and so the number of mi-croblocks produced between two consecutive key blocks is v/f . (Note thatthe key block interval is assumed to follow the exponential distribution withmean 1/f in Sec. 4.3.) Second, we only consider binary choices: publish-ing or hiding all selfish microblocks in the transaction inclusion attack, andaccepting or rejecting all honest microblocks in the longest chain extensionattack. (This is consistent with the fact that ρ = 0 or 1 in Sec. 4.3.)We are now ready to describe our MDP model, which can be presentedby a 4-tuple M := (S,A, P,R), where S is the state space, A is the actionspace, P is the stochastic state transition matrix, andR is the reward matrix.Specifically, S contains all possible states in the selfish mining process; Aincludes the available actions (e.g., publishing or hiding blocks by the selfishminer) at each state; P contains the transition probabilities from the currentstate to the next state according to the taken action; R records how muchthe selfish miner obtains when there are some state transitions. Table 4.1illustrates the MDP of selfish mining in Bitcoin-NG. Note that blocks areassumed to be transmitted without delay (see Sec. 3.1), and so forks arenot considered in the analysis. Below we will discuss each component of the4-tuple:Actions. The selfish miner has eight available actions in our model.− Adopt and include. The selfish miner accepts all honest key blocksand the corresponding honest microblocks. In other words, the selfish474.4. Incentive Analysis for both Microblock and Key Blockminer will mine its key block on the last honest block and abandon itsprivate chain. This action is referred to as adopt.− Adopt and exclude. The selfish miner accepts all honest key blocksand microblocks except for microblocks produced after the last honestkey block. Specifically, the selfish miner directly mines on top of the lasthonest key block, which is referred to as adoptE.− Override and publish. The selfish miner publishes all its key blocksand corresponding microblocks whenever its private chain is longer thanthe honest one. The chain length is counted by the key block. This actionis denoted as override.− Override and hide. The selfish miner publishes all its key blocks andthe microblocks except for these mined after the last selfish key blockwhenever its private chain is longer than the honest one. This action isdenoted as overrideH.− Match and publish. When an honest miner finds one new key block,the selfish miner publishes its key block of the same height and the mi-croblocks built after this key block. This action is available when theselfish miner has one block in advance and is referred to as match.− Match and hide. When an honest miner generates a new key block,the selfish miner publishes its key block of the same height while hidesthe microblocks built after this key block. This action is also availablewhen the selfish miner has one block in advance. This action is denotedas matchH.− Wait. In this action, the selfish miner does not publish any new keyblocks and microblocks, while keeps mining on its private chain until anew key block and corresponding microblocks are found.− Revert. The selfish miner reverts its previous actions. Specifically, theselfish miner can publish its hidden microblocks when there is no honestkey block mined after its block; the selfish miner can include the honestmicroblocks (decided to excluded in the previous decision) or excludes thehonest microblocks (decided to included in the previous decision) oncethere is no selfish key block mined on an honest block.484.4. Incentive Analysis for both Microblock and Key BlockTable 4.1: State transition and reward matrices for the opti-mal selfish mining (Prob.: probability; Cond.: condition).State×Action State Prob. Reward Cond.(la, lh, ·, Sh) (lh, lh, 0, 0)−adopt (1, 0,α(la, lh, ·, Sp) noTie, Hin) (lh, lh − r,adopt (0, 1,1− α0, r)(la, lh, ·, {Hin, Hex}) noTie, Hin) (lh, lh − 1,adopt 0, 0)(la, lh, ·, Sh) (lh, lh, 0, 0)−adoptE (1, 0,α(la, lh, ·, Sp) noTie, Hex) (lh, lh − r,adoptE (0, 1,1− α0, r)(la, lh, ·, {Hin, Hex}) noTie, Hex) (lh, lh − 1,adoptE 0, 0)(la, lh, ·, Hex) (0, 0, lh + 1,la > lhoverride (la − lh, 0, αlh + 1)(la, lh, ·, Hin) noTie, Sp) (0, r, lh + 1,override (la − lh − 1, 1− αlh + (1− r))(la, lh, ·, {Sp, Sh}) 1, noTie, Sp) (0, 0,override lh + 1, lh)(la, lh, ·, Hex) (0, 0, lh + 1,la > lhoverrideH (la − lh, 0, αlh + 1)(la, lh, ·, Hin) noTie, Sh) (0, r, lh + 1,overrideH (la − lh − 1, 1− αlh + (1− r))(la, lh, ·, {Sp, Sh}) 1, noTie, Sh) (0, 0,overrideH lh + 1, lh)(la + 1, lh,(0, 0, 0, 0) −(la, lh, noTie, ·) noTie, ∗) αwait (la, lh + 1, 1− αnoTie, ∗)(la + 1, lh, α (0, 0, 0, 0)la ≥ lh(la, lh, noTie, Hin) tie, Hin)match (la − lh, 1, γ(1− α)(0, r, lh,(la, lh, tie, Hin) noTie, Sp) lh − r)wait (la, lh + 1, (1− γ)× (0, 0, 0, 0)noTie, Hin) (1− α)(la + 1, lh, α (0, 0, 0, 0)la ≥ lh(la, lh, noTie, Hex) tie, Hex)match (la − lh, 1, γ(1− α)(0, 0, lh,(la, lh, tie, Hex) noTie, Sp) lh − 1)wait (la, lh + 1, (1− γ)× (0, 0, 0, 0)noTie, Hex) (1− α)(la, lh, noTie, (la + 1, lh, α (0, 0, 0, 0)la ≥ lh 494.4. Incentive Analysis for both Microblock and Key BlockState×Action State Prob. Reward Cond.{Sp, Sh}) tie, ∗)match (la − lh, 1, γ(1− α) (0, 0, lh, lh)(la, lh, tie, noTie, Sp){Sp, Sh}) (la, lh + 1, (1− γ)× (0, 0, 0, 0)wait noTie, ∗) (1− α)(la + 1, lh, α (0, 0, 0, 0)la ≥ lh(la, lh, noTie, Hin) tie′, Hin)matchH (la − lh, 1, γ(1− α)(0, r, lh,(la, lh, tie′, Hin) noTie, Sp) lh − r)wait (la, lh + 1, (1− γ)× (0, 0, 0, 0)noTie, Hin) (1− α)(la + 1, lh, α (0, 0, 0, 0)la ≥ lh(la, lh, noTie, Hex) tie′, Hex)matchH (la − lh, 1, γ(1− α)(0, 0, lh,(la, lh, tie′, Hex) noTie, Sp) lh − 1)wait (la, lh + 1, (1− γ)× (0, 0, 0, 0)noTie, Hex) (1− α)(la, lh, noTie, (la + 1, lh, α (0, 0, 0, 0)la ≥ lh{Sp, Sh}) tie′, ∗)matchH (la − lh, 1, γ(1− α) (0, 0, lh, lh)(la, lh, tie′, noTie, Sp){Sp, Sh}) (la, lh + 1, (1− γ)× (0, 0, 0, 0)wait noTie, ∗) (1− α)(la, lh, tie′, ·), revert (la, lh, tie, ∗) 1 (0, 0, 0, 0) −(la, lh, ·, Sh), revert (la, lh, ∗, Sp) 1 (0, 0, 0, 0) lh = 0(la, lh, ·, Hex), revert (la, lh, ∗, Hin) 1 (0, 0, 0, 0) la = 0∗ denotes the state element remains the same in the state transition.The adopt, override match, and wait actions include all possible actionson the selfish mining of key blocks, while hide, publish and revert actionscover all possible actions on the transaction inclusion and longest chainextension attacks of microblocks. Note that in match action, the selfishminer publishes its key block of the same height to match honest miners’key block. Therefore, there are two forking branches of the same length.In Bitcoin-NG, honest miners adopt a uniform tie-breaking rule to choosewhich branch to mine on. See Sec. 2.2.2 for more details about the forkchoice rule in Bitcoin-NG. In particular, we introduce a variable γ, whichdenotes the fraction of honest miners that mine on the selfish miner’s branch.State space. The state space S is also composed by 4-tuple (la, lh, fork,lastMicroBlock).− la accounts for the length of the chain mined by the selfish miner after504.4. Incentive Analysis for both Microblock and Key Blockthe last common ancestor key block. More precisely, the last commonancestor key block is the last key block in the longest chain acceptedby both the selfish miner and all honest miners, and is updated once theselfish miner adopts the public chain or all honest miners adopt the selfishminer’s chain. In addition, the chain length is counted by the selfish keyblocks in this branch.− lh is the length of the public chain after the last common ancestor keyblock. This chain can be viewed by both the selfish miner and honestminers.− fork. The field fork obtains three possible values, dubbed noTie, tie andtie′. Specifically, tie means the selfish miner publishes lh selfish key blockand the corresponding microblocks; tie′ presents the selfish miner pub-lishes lh selfish key block and the corresponding microblocks except forthese after the last selfish key block; noTie signifies that there are nottwo public branches with the equivalent length.− lastMicroBlock. This field also includes four possible values, dubbed Hin,Hex, Sp, and Sh. Specifically, Hin (respectively, Hex) represents the com-mon ancestor is an honest key block, and the corresponding microblocksare accepted (respectively, rejected) by the selfish miner. While Sp (orSh) which stands for the common ancestor is a selfish key block, and thecorresponding microblocks mined are published (or hidden, respectively)by the selfish miner.State Transition and Reward. We use a 4-tuple (Rh, Th, Ra,Ta) to indi-cate the rewards won by the selfish and honest miners in the state transitions.Specifically, Rh (respectively, Ra) is the key block rewards for honest (re-spectively, the selfish) miners , while Th (respectively, Ta) is the transactionfee for honest (respectively, the selfish) miners.Recall that there are two types of transactions. Here, we focus on regulartransactions and will discuss whale transactions later. Recall also that themicroblock fee of a regular microblock is denoted by Rt. For convenience,instead of recording the number of rewards, each field only records the num-ber of key block rewards or transaction fees (the total transaction fee in v/fmicroblocks as one unit) won by miners. More importantly, the transactionfees included in the microblocks after the common ancestor key block arenot assigned to miners until the next ancestor key block is decided. Thisis because these transaction fees are affected by some future actions of theselfish miner (see Sec. 4.3).In adopt or adoptE actions, the selfish miner accepts lh honest key blocksand the microblocks mined before these key blocks. Honest miners obtain514.4. Incentive Analysis for both Microblock and Key BlocklhRb key block rewards and (lh − 1)v/fRt transaction fees. In override oroverrideH actions, the selfish miner publishes lh+1 selfish key blocks. Honestminers accept these key blocks and the microblocks produced before the keyblocks. Thus, the selfish miner obtains (lh + 1)Rb key block rewards andlhv/fRt transaction fees. In the match actions, the next state depends onwhether the next key block is created by the selfish miner (w.p. α), by somehonest miners working on the honest branch (w.p. (1−γ)(1−α)), or by theleft honest miners mining on the selfish branch (w.p. γ(1−α)). In the lattercase, the selfish miner effectively overrides the honest miners’ branch. It canobtain lhRb key block reward and (lh− 1)v/fRt transaction fees. Note thatthe value of γ is decided by the adopted fork solution (e.g., γ = 0.5 in theuniform tie-break policy).Once the common ancestor key block is changed, the transaction feesin the microblocks produced after the previous ancestor key block will beassigned. There are two cases.− The previous common ancestor key block is mined by an honest miner.This case can be further divided into two subcases: 1) the next key blockis mined by honest miners, and honest miners get v/fRt transaction fees;2) the next key block is mined by the selfish miner and lastMicroBlock =Hin, honest miners get rv/fRt transaction fees and the selfish miner gets(1− r)v/fRt transaction fees.− The previous common ancestor key block is mined by the selfish miner.This case can be further divided into two subcases: 1) the next keyblock is mined by the selfish miner, and the selfish miner gets v/fRttransaction fees; 2) the next key block is mined by some honest minersand lastMicroBlock = Sp, the selfish miner gets rv/fRt transaction feesand honest miners get (1− r)v/fRt transaction fees.Finally, we turn our attention from regular transactions to whale trans-actions. Since whale transactions are rare and unpredictable, we model themicroblock fee as a random variable taking two values: Rt or Rt plus thefee of a whale transaction. Let R¯t be the expected microblock fee. Clearly,R¯t > Rt. The long-term effect of whale transactions is to decrease the ratiok from Rb/Rt to Rb/R¯t. As we will see in our evaluation shortly, such aneffect slightly increases the relative revenue of the selfish miner.524.4. Incentive Analysis for both Microblock and Key Block0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45Adversarial Mining Power α00.10.20.30.40.50.60.70.8RelativeRevenueHonest MiningBlock Reward OnlyEqual Block and Transaction RewardTransaction Reward Only0.2321Figure 4.6: The selfish miner’s relative revenue.4.4.2 Evaluation ResultsWe use the MDP toolbox developed in MATLAB [13] to obtain theselfish miner’s relative revenue, denoted in the equation (4.1).14 Note thatin the following evaluations, Bitcoin-NG adopts the uniform tie-breakingpolicy (γ = 0.5).The selfish mining threshold. Fig. 4.6 shows the relative revenues of theselfish miner when r = 0.4 (used in Bitcoin-NG [21]) and α ∈ [0, 0.45]. Weconsider three reward settings: k → 0, k = v/f , and k →∞. Specifically, inthe first setting, the transaction fees dominate the miners’ revenue; in thesecond setting, the transaction fees included in v/f microblocks betweentwo consecutive key blocks have the same weight with one key block reward;in the third setting, the key block rewards dominate miners’ revenue. Notethat the key block reward dominated case has a similar reward distribution14With the MDP toolbox, we can numerically obtain the optimal policies under eachscenario. We do not provide them due to space constraints.534.4. Incentive Analysis for both Microblock and Key Block0 0.35 0.4 0.45 0.5Adversarial Mining Power α00.10.20.30.40.50.60.70.80.9RelativeRevenue0.350.4510.4540.4570.40.5960.6060.6180.450.7770.7950.815Honest MiningBlock Reward OnlyEqual Block and Transaction RewardTransaction Reward OnlyFigure 4.7: The selfish miner’s relative revenue with different α.as Bitcoin, i.e., the microblock architecture does not impact the system.The figure shows that the thresholds of making selfish mining profitablein these three settings are all 23.21%, which is the same as the selfish miningthreshold in Bitcoin. In other words, by adopting the suitable r (i.e., α <r < 1 − α), the microblock architecture in Bitcoin-NG does not affect thesystem security compared with Bitcoin. In addition, the selfish miner’srevenues in the three settings are still the same even when α > 29%, whichverifies our analysis in Sec. 4.3 and supports that Bitcoin-NG is as resilientas Bitcoin.When α > 35%, the differences between the selfish miner’s revenues inthe three settings and the honest revenue are exhibited in Fig. 4.7. It’s easyto see that the selfish miner can obtain the highest revenue in the transac-tion fee dominated case. This implies that the microblock architecture canslightly increase the selfish miner’s revenue, but the increase is much smallerthan the results [69]. We will explain the reason shortly.The selfish revenue with different split ratio. Fig. 4.8 shows theselfish miner’s relative revenue when α = 23.21% and r is set to different544.4. Incentive Analysis for both Microblock and Key Block0 0.2 0.4 0.6 0.8 1Split Ratio r0.250.260.270.280.290.3RelativeRevenueEqual Block and Transaction RewardTransaction Reward OnlyFigure 4.8: The selfish miner’s relative revenue with different split ratio r.values. In Fig. 4.8, we consider two settings: k → 0 and k = v/f (whichare introduced above). We can see when r ranges from 0.2321 to 0.7679,the selfish revenues in the two settings are both the lowest. Therefore, theresults support our findings in Sec. 4.3. This is when adopting the suitabler (i.e., α < r < 1− α), the selfish miner cannot gain more from microblockselfish mining.4.4.3 DiscussionFirst, we validate that when adopting the suitable r, the selfish miningthreshold in Bitcoin-NG is the same as the threshold in Bitcoin [62]. Thismeans that Bitcoin-NG and Bitcoin have the same security level. In otherwords, our result supports the security claim of Bitcoin-NG [21] by usingMDP.Second, we find out that when α > 35%, the selfish miner in Bitcoin-NG can gain more revenue than in Bitcoin. However, the increase is muchless significant as shown in the previous result [69]. This is because Wang554.5. Related Worket al. [69] treated the selfish mining of key blocks and microblocks as twoindependent issues and take the outputs of the key-block mining attack(i.e., the fraction of selfish key blocks) as input to the microblock mininganalysis. Their method amplifies the selfish miner’s revenue by serializingthe key block and microblocks mining. By contrast, our MDP approachmore accurately integrates the selfish mining of key blocks and microblocks,leading to theoretical results closer to reality.4.5 Related WorkIn this section, we introduce the prior works of incentive analysis inBitcoin-NG. We refer the reader to Chapter 3.6 for more prior works onthe selfish mining in Bitcoin. Yin et al. [71] extended the transaction feedistribution ratio after considering another situation that the original pa-per omits [21]. Wang et al. [69] considered advanced selfish mining strate-gies, i.e., stubborn mining strategies, when an attacker may manipulate themicroblock chains between two honest parties. Wang et al. [68] proposeda Bitcoin-NG advance attack in their formalized game-theoretical model.However, these prior works have several limitations in the incentive analy-sis, as explained previously.4.6 SummaryThis chapter revisits the incentive analysis of Bitcoin-NG, particularlyon addressing the limitations of the previous analysis. We have proposed anew incentive analysis of Bitcoin-NG considering the network capacity. Ourmodel enables us to evaluate the impact of key-block generation intervaland microblock generation rate, which is missing in the previous analysis.In particular, we have shown that Bitcoin-NG can still maintain incentivecompatibility against the microblock mining attack even under network ca-pacity constraints. In addition, we have modeled the selfish mining of keyblocks and microblocks jointly into an MDP and shown the threshold ofBitcoin-NG is a little lower than in Bitcoin only when the selfish miningpower α is greater than 35%. We hope that our in-depth incentive analysisfor Bitcoin-NG can shed some light on the mechanism design and incentiveanalysis of next-generation blockchain protocols.56Chapter 5On the Performance ofPipelined HotStuffThis chapter develops a multi-metric evaluation framework to quanti-tatively analyze pipelined HotStuff’s performance with respect to its chaingrowth rate, chain quality, and latency. Several attack strategies introducedby HotStuff are proposed, and their effects on the performance by using theframework are evaluated. Furthermore, we use our framework to evaluatesome engineering optimizations adopted by DiemBFT, which is one variantof pipelined HotStuff adopted by the Diem project of Facebook. Finally, Weprovide one countermeasure to thwart these attacks.5.1 System Model and Preliminaries5.1.1 System ModelWe consider a system with n nodes denoted by the set N . We assume apublic-key infrastructure (PKI), and each node has a pair of keys for signingmessages (e.g., blocks and votes). We assume that a subset of f nodes isByzantine, denoted by the set F , and can behave arbitrarily. The othernodes in N \F are honest and strictly follow the protocol. In order to ensuresecurity, we have n ≥ 3f + 1. We use α (resp. β) to denote the fraction ofByzantine (resp. honest) nodes. That is, α = f/n. For simplicity, all theByzantine nodes are assumed to be controlled by a single adversary, whichis computationally bounded and cannot (except with negligible probability)forge honest nodes’ messages.Network Model. We assume honest nodes are fully and reliably con-nected, i.e., every pair of honest nodes is connected with an authenticatedand reliable communication link. We adopt the partial synchrony model ofDwork et al. [18]. In the model, there is a known bound ∆ and an unknownGlobal Stabilization Time (GST), such that after GST, all message trans-missions between two honest nodes arrive within a bound ∆. Hence, thesystem is running in synchronous mode after GST and asynchronous mode575.1. System Model and PreliminariesTimerLBRLeader-based phaseRound-change phaseRoundn...TimerLBRLeader-based phaseRoundn+1Round-change phaseFigure 5.1: Overview of a sequence of the leader-based round (LBR)instances. The leader-base phase is in charge of driving progress, while theround-change phase is to synchronize nodes to the same round.if GST never occurs.5.1.2 PreliminariesQuorum Certificate. A block’s quorum certificate (QC) is proof that morethan 2n/3 nodes (out of n) have signed this block. Here, a QC could beimplemented as a simple set of individual signatures or a threshold signature.We say a block is certified when its QC is received and certified blocks’freshness is ranked by their round numbers. In particular, we refer to acertified block with the highest round number that a node knows as thenewest certified block. Each node keeps track of all signatures for all blocksand keeps updating the newest certified block to its knowledge.Block and Block Tree. Clients send transactions to leaders, who thenbatch transactions into blocks. A block has four-tuple 〈round, cmd, parent qc, σ〉,where round denotes the round number at which the block is proposed, cmdis a batch of transactions, parent qc is the QC for the parent block, and σ isthe block owner’s signature of 〈round, cmd, parent qc〉. Every block exceptthe genesis block must specify its parent block and include a QC for theparent block. In this way, blocks are chained. (Note that in Bitcoin [47],blocks are chained through hash references rather than QCs.) As there maybe forks, each node maintains a block tree (referred to as blockTree) ofreceived blocks.Leader-based Round Abstraction. Pipelined HotStuff is executed intoa sequence of rounds, and each round has a designated leader15. Each roundcan be further divided into two phases: 1) leader-based phase in which adesignated leader proposes a new block and collects votes from other nodesto form a quorum certificate of this block (introduced shortly), and 2) round-change phase in which nodes safely wedge to next round if the current-round15Rounds are also referred to as views [12, 73], terms [54], instance values/epoch [36] orballot numbers in the literature585.2. Pipelined HotStuff and DiemBFT Algorithmsleader is faulty or no certified block is generated before the timeout, as shownin Fig. 5.1. By following recent work [67], we assume that each round can beencapsulated in a leader-based round (LBR) abstraction, which provides twoimportant modules: pacemaker and leader-election modules. The pacemakermodule can guarantee that honest validators are synchronized to execute thesame rounds for sufficient overlap, and leaders propose a block that will besupported by honest nodes when the network is synchronous [73]. That is,an honest leader can send its block proposal to all the other honest nodes andreceive their votes in one round. The leader-election module can guaranteethat nodes are fairly elected as leaders. That is, during synchronous periods,each node has the same chance to win the leadership for one round16. Forconvenience, a leader who is elected from honest nodes (resp. Byzantinenodes) is referred to as honest (resp. adversarial) leader. In the same way,a block proposed by an honest (resp. adversarial) leader is referred to ashonest (resp. adversarial) block.5.2 Pipelined HotStuff and DiemBFT Algorithms5.2.1 Pipelined HotStuff AlgorithmWe describe the leader-based phase of pipelined HotStuff at round i. Inthe beginning, a unique leader, called leaderi, is randomly selected by theleader-election module. The leader’s identity is known and can be verifiedby all nodes. Then, the leader proposes a block to extend the newestcertified block it has seen17, and broadcasts this block to all other nodes.Every node votes for the first block it receives from the leader18, as long asthe block satisfies certain conditions introduced shortly. A vote for a blockis a signature on the block. When the leader receives at least 2n/3 uniquesignatures (including its signature), it aggregates these signatures into a QCand sends it to the next-round leader, namely, leaderi+1.We are now ready to describe the condition for voting. Every nodemaintains two local parameters: i) last voted round, the last round forwhich the node has voted, and ii) locked round, the highest known round16During asynchronous periods, some honest nodes may not be synchronized to thehighest round and participate in the leader-election. Thus, the adversary can have ahigher chance than α to be elected as leaders.17For simplicity, we follow the same way with DiemBFT, i.e., leaders extend the prede-cessor block with a direct child. However, in pipelined HotStuff, a leader has to includedummy blocks in its proposal if there are no certified blocks generated in previous rounds.18Recall that an adversarial leader can propose multiple blocks.595.2. Pipelined HotStuff and DiemBFT Algorithmsround k k+1 k+2 k+4CommitQC Bk+1 QC Bk+2 QC Bk+4QC BkFigure 5.2: The chained blocks in pipelined HotStuff. Blocks Bk,Bk+1, and Bk+2 are three consecutive blocks, and nodes will commit blockBk when receiving block Bk+4.number of the grand-parent block that has been received. For example,in Fig. 5.2, when a node first receives the block Bk+2 and votes for it, itslast voted round is updated to k + 2, and the newest grandparent block isBk, and so locked round is k. After receiving block Bk+4, the node updateslast voted round to k + 4 and locked round to k + 1. A node will vote forthe first block proposed by the current-round leader if the block extends theblock generated at locked round (regardless of round numbers) or the roundnumber of the received block’s parent block is greater than locked round.Concretely, a block satisfies the above condition if and only if: i) its roundnumber is greater than last voted round, and ii) the round number of itsparent block is greater than or equal to locked round.19After voting for a new block, a node will insert the block to its blockTreeand then update its state as follows: i)update last voted round to the roundnumber of this block, and ii) update the node’s locked round to the roundnumber of this block’ grandparent block if the latter is higher. Meanwhile,the node checks whether there are new committed blocks in its blockTree.Specifically, if there are three blocks Bk, Bk+1 and Bk+2 proposed in threeconsecutive rounds k, k+1, and k+2, and an additional block extends blockBk+2, the node will commit block Bk and all its predecessor blocks. Thefirst three consecutive blocks are referred to as 3-direct chain20. A simplecase, in which block Bk is committed, is shown in Fig. 5.2. Note that nodesmaintain a chain containing committed blocks, and this chain is referred toas the main chain in our later analysis.19This condition is adopted by DiemBFT and is shown to be equivalent to the previouscondition [7, 8].20A 3-direct chain requires an additional block extending 3 consecutive blocks. If weonly have 3 consecutive blocks, we don’t call them a 3-direct chain. Note that for simplicityof analysis, the 3-direct chain is different from the Three-Chain defined in [73], but thedifferences do not affect the results.605.3. Performance Metrics and AttacksTo sum up, in pipelined HotStuff, leaders propose new blocks, and ev-ery node votes for a new block according to certain voting conditions andsometimes commits blocks if there is a 3-direct chain followed by anotherblock. Also, every node starts a timer to track progress for each round.Whenever the timeout happens or a block’s QC is received, a node moves tothe next round. Such a round synchronization procedure is provided by thepacemaker module. The pacemaker module can also guarantee a new leaderto have the newest certified block and/or its parent block, which guaranteesthe leader can propose a block voted by honest nodes (see Sec. 5.1).5.2.2 DiemBFT AlgorithmDiemBFT is a variant of pipelined HotStuff with two subtle differences.First, in DiemBFT, a node sends its vote directly to the next-round leader(rather than the current-round leader) so that the next leader can form aQC and embed the QC in its block. In this way, the current leader doesn’tneed to relay the QC to the next leader. That is, this optimization can cutoff the delay of the relay operation.21 Second, DiemBFT introduces a newblock type called Nil block. This is when the timer expires, and nodes havenot received a proposal for the round, they can broadcast a vote on a Nilblock (in a predetermined format). If more than 2n/3 nodes have voted, theaggregated signatures can serve as a QC for the Nil block. The certified Nilblock can guarantee that blocks are produced in consecutive rounds despitehaving faulty leaders, which can further accelerate the block commitment.For example, in Fig. 5.2, when the leader of round k+3 is faulty, and thereis no block produced, nodes cannot commit block Bk+1 even if receivingblock Bk+4 in pipelined HotStuff. By contrast, in DiemBFT, there will bea certified Nil block at round k+3, and nodes will commit block Bk+1 afterreceiving block Bk+4.5.3 Performance Metrics and AttacksIn this section, we first introduce a multi-metric framework to evaluatethe impact of various attacks and then propose several attack strategies.5.3.1 Performance MetricsWe focus on three performance metrics, namely, chain growth rate, chainquality, and latency. All of these metrics are meaningful only after the GST,21The latest version of HotStuff also adopted this optimization [72].615.3. Performance Metrics and Attackswhich implies that the network is in synchronous mode22.Chain Growth RateFor a given adversarial strategy that controls a fraction α of total nodes,the chain growth rate u1(α) is defined as the rate of honest blocks appendedto the main chain over the long run. Let Bh(m) denote the total number ofhonest blocks appended to the main chain in m rounds. (Note that Bh(m)can be a random variable because of the randomness in the leader selection.)We have:u1(α) = limm→∞Bh(m)m. (5.1)The chain growth rate corresponds to the liveness in the context of blockchains.Chain QualityFor a given adversarial strategy that controls a fraction α of total nodes,the chain quality u2(α) is defined as the fraction of honest blocks includedin the main chain over the long run. Let Ba(m) denote the total number ofadversarial blocks appended to the main chain in m rounds. We have:u2(α) = limm→∞Bh(m)Bh(m) +Ba(m). (5.2)This metric affects the reward distribution. In blockchains, each block in themain chain brings its proposer a reward [47]. This reward incentivizes nodesto participate in the consensus and compete to win the leadership. Addi-tionally, nodes are expected to get rewards, proportional to their devotedresources (e.g., hash power in Poof-of-Work [47], and stakes in Proof-of-Stake [28]). Intuitively, a chain quality less than 1 − α implies that theadversary can win a higher fraction of rewards than what it deserves, whichruins the incentive compatibility [22, 49, 53, 57].LatencyFor a given adversarial strategy that controls a fraction α of total nodes,the latency u3(α) is defined as the average rounds that honest blocks takefrom being included in the main chain until being committed over the longrun. Let Di denote the number of rounds that the i-th honest block takes22Before the GST, there may have no certified blocks at all, and so the three metricsbecome meaningless.625.3. Performance Metrics and Attacksround k k+1 k+2kQ Q Q Q ffFigure 5.3: The overriding attack on pipelined HotStuff. The adver-sary is elected as a leader in round k + 3. It proposes a block Bk+3 afterblock Bk (or Bk+1) to override blocks Bk+1 and Bk+2 (or block Bk+2).to be committed by all honest nodes (rather than the first honest leader)during the m rounds.23 We have:u3(α) = limm→∞∑Bh(m)i=1 DiBh(m). (5.3)Remark 5.1. Note that the chain growth rate and latency are measured interms of rounds rather than in time. This round abstraction allows us toignore the specific implementation of the pacemaker module and focus onthe core of pipelined HotStuff.5.3.2 Attack StrategiesWe introduce two attacks here. The overriding attack launched by theadversary aims to minimize the chain growth rate and the chain quality byoverriding honest blocks. The delay attack aims to maximize the latency bydelaying the commitment of honest blocks. Both attacks, which are inspiredby the selfish mining attack for Bitcoin, are new in the context of pipelinedHotStuff. The optimality of these attacks will be discussed in future work.Here, we emphasize that since the performance metrics are measured af-ter the GST, we do not need to consider network-level attacks, such aseclipse attack[33] and Distributed Denial of Service (DDoS) attack, whichmay cause a network partition (i.e., asynchronous network) and blockingthe progress.23Note that leaders first commit blocks locally, and then send out the proofs of the3-direct chain to convince other nodes to commit these blocks. It is trivial to extend ouranalysis to get the results under this model.635.3. Performance Metrics and AttacksOverriding attackIn pipelined HotStuff, an adversarial leader can create forking blocks onpurpose to override honest blocks without any loss. For example, in Fig. 5.3,if blocks Bk and Bk+1 are both honest blocks, and the adversarial leader atround k + 3 has no adversarial certified block with a round number largerthan locked round = k, the adversarial leader will build a block on blockBk. As block Bk+3 satisfies the voting condition (i.e., the round number ofBk+3’s parent block is no less than honest nodes’ locked round = k), nodeswill vote for Bk+3 and all subsequent leaders will extend Bk+3. Similarly, ifonly block Bk+2 is an honest block, the adversary can build on block Bk+1to override this block. In both cases, the adversarial leader overrides somehonest blocks and suffers no loss of adversarial blocks. Also, note that theadversarial leader cannot override block Bk and its predecessor blocks, sinceblock Bk+3 cannot reference a certified parent block, which has a roundnumber no less than k. In general, if there exist some adversarial certifiedblocks with round numbers no less than locked round, the adversarial leaderextends the newest adversarial certified block. Otherwise, the adversarialleader extends the block produced at locked round.Delay AttackThe main goal of the delay attack is to break the block commitmentcondition to increase the average delay of honest blocks in the main chain.More specifically, the delay attack is to prevent honest blocks to form the3-direct chain. Recall that a block is committed if and only if three blocksextend it, and the first two blocks are produced in consecutive rounds afterthe block’s round (i.e., the 3-direct chain structure). Note that once theblock is committed, all its predecessor blocks are also committed.Delay Attack in pipelined HotStuff. Recall that an honest leader alwaysproposes a block on the newest certified block. By contrast, an adversarialleader can propose a block on a non-newest certified block or propose noblock at all. An example is provided in Case A of Fig. 5.4 in which theadversarial leader of round k + 4 observes three non-consecutive blocks Bk,Bk+2, and Bk+3. In this case, the leader proposes no block at all (leading toa timeout). As a result, subsequent honest leaders have to restart buildinga 3-direct chain. Another example is illustrated in Case B of Fig. 5.4 inwhich the adversarial leader of round k+4 observes three consecutive blocksBk+1, Bk+2, and Bk+3. In this case, the leader proposes block Bk+4 on topof Bk+2. This will override block Bk+3 as explained before. In general,645.4. Performance Analysisround k k+2 fiflffi !"#$ !" !"#% !"#&fifl'fifl(round k+1 k+2fiflffi !"#$ !"#) !"#% !"#*fifl( !"#&fifl'Case ACase BFigure 5.4: The delay attack on pipelined HotStuff. The adversaryproposes no block at all (in Case A) or overrides honest blocks at roundk+4 (in Case B) according to whether there exist three consecutive blocks.if there exist three consecutive blocks that ended with the newest certifiedblock, the subsequent adversarial leader overrides the newest certified block.Otherwise, the adversarial leader proposes no block.Delay Attack in DiemBFT. Delay attack in DiemBFT is slightly differentfrom that in pipelined HotStuff. First, due to the Nil block, the adversarycannot propose no block, because otherwise a certified Nil block will beproduced that can be part of a 3-direct chain. Hence, the adversarial leadercan create a block, and then send this block to half of the honest nodes.In this way, half of the honest nodes will vote for this block, while the lefthalf honest nodes will vote for the Nil block. As a result, neither a certifiedblock nor a certified Nil block will be produced in this round. Second, inDiemBFT, as nodes send block votes to the next leader, an adversarial leadercan hide the collected QC of a block proposed in the previous round. So,when there are three consecutive blocks, the adversarial leader can hide theQC for the last one. In this way, subsequent honest leaders cannot form a3-direct chain based on the three consecutive blocks.5.4 Performance AnalysisIn this section, we first analyze the performance of pipelined HotStuffin terms of chain growth rate, chain quality, and latency under forking anddelay attacks. Then, we evaluate some optimizations adopted by DiemBFT.Specifically, we consider a sequence of m rounds (when the network is in655.4. Performance Analysissynchronous mode) and number these rounds as 1, 2, ...,m. For each round,the possibility that the elected leader is honest (resp, adversarial) is β (resp,α). Now, Let Xj (j ∈ [1,m]) denote an indicator random variable whichequals one if the leader of the jth round is honest and equals zero otherwise.As the network is synchronous, nodes can receive a block within ∆ timeafter an honest leader sends the block. For simplicity, nodes are assumedto receive the block by the end of each round. In addition, honest leadersare assumed to be able to get the newest honest certified blocks from othernodes before proposing new blocks.5.4.1 Pipelined HotStuffChain Growth RateRecall that an honest block proposed at round i will be overridden byan adversarial leader in round (i+ 1) or (i+ 2) under the overriding attack(See Sec. 5.3.2 for details.). In other words, an honest block can be keptin the main chain if and only if the subsequent two blocks are produced byhonest leaders. Let Zi denote an indicator random variable, which equalsto one if {Xi = 1, Xi+1 = 1, Xi+2 = 1} and equals to zero otherwise. Next,let Z =∑mi=1 Zi. The following lemma bounds the value of Z.Lemma 5.2. For m consecutive rounds, the number of block fragments(Xi, Xi+1, Xi+2) = (1, 1, 1) has the following Chernoff-type bound: For 0 <δ < 1,Pr(|Z − β3m| > δβ3m) < e−Ω(δ2β3m). (5.4)Proof. Without loss of generality, we assume that m is a multiple of 3. LetZj =∑m/3−1i=0 Zj+3i (j ∈ [0, 1, 2]). Then, Z = Z0 + Z1 + Z2. It is easyto show that E(Zj)= β3m/3, since P{Zi = 1} = P{Xi = 1}P{Xi+1 =1}P{Xi+2 = 1} = β3. Note that {Z0, Z3, . . . , Zm−1} are independent ran-dom variables, because Zi is a function of (Xi, Xi+1, Xi+2). Hence, Zj is asum of i.i.d. random variables. By Lemma 4 in [52], we havePr(Z < (1− δ)β3m)< e−δ2β3m/6 = e−Ω(δ2β3m).Similarly, we have Pr(Z > (1 + δ)β3m)< e−δ2β3m/9 = e−Ω(δ2β3m).This lemma shows that as m increases, the number of block fragments(Xi, Xi+1, Xi+2) = (1, 1, 1) is between (1− δ)β3m and (1+ δ)β3m with highprobability. Moreover, each block fragment corresponds to one honest block665.4. Performance Analysisincluded in the main chain. This leads to the following theorem for the chaingrowth rate.Theorem 5.3. The chain growth rate of pipelined HotStuff under the over-riding attack converges to β3 with high probability as m→∞.Proof. By Lemma 5.2 and the definition of u1(α), we haveu1(α) = limm→∞m−1∑i=0Zi/m→ β3.Note that when there does not exist the overriding attack, the chaingrowth rate is β, for the probability that an honest node is elected as aleader is β. In other words, this theorem states that the overriding attackreduces the chain growth rate from β to β3. For instance, if β = 2/3, thechain growth rate is reduced from 2/3 to 8/27.Remark 5.4. The chain growth rate is measured in terms of rounds. If it ismeasured in time, the overriding attack can reduce the chain growth rateeven more. This is because an adversarial leader can push the duration ofits round close to the timeout value, which is usually much longer than theactual network delay for producing a certified block.Chain QualityRecall that the adversary suffers no loss of blocks when launching theoverriding attack. That is, every adversarial block can be kept in the mainchain. Therefore, the adversary can produce αm adversarial blocks on expec-tation over m rounds. This observation, together with Theorem 5.3, allowsus to derive the following chain quality theorem for pipelined HotStuff.Theorem 5.5. The chain quality of pipelined HotStuff under the overridingattack converges to β3β3−β+1 with high probability as m→∞.Proof. As m → ∞, Ba(m)m (the number of adversarial blocks divided by m)converges to α by Lemma 3 in [52], and Bh(m)m (the number of honest blocksin the main chain divided by m) converges to β3 by Lemma 5.2. Hence, thechain quality converges to β3β3−β+1 . Note that α = 1− β.675.4. Performance AnalysisS0 S1 S2 S3a abb babaFigure 5.5: The state transition of the delay attack on pipelined HotStuff.For example, if α = 1/3, the chain quality under the overriding attack is8/17, whereas it should be 2/3 without the overriding attack. If each blockcan bring its owner a reward, the adversary can obtain a fraction of rewardsαβ3−β+1 by launching the overriding attack, which is always higher than thedeserved fraction α, for β3 − β + 1 < 1. In other words, incentive com-patibility of pipelined HotStuff cannot hold anymore under the overridingattack.LatencyHere, we compute the latency of honest blocks in the main chain. Toachieve this goal, we need to track each honest block included in the mainchain and obtain its associated delay to be committed. More precisely, thechance that an honest block is kept in the main chain and its delay is affectedby the delay attack strategies, which further depend on the chain structure.For example, in Fig. 5.4, as shown in Case A, as there is no 3-chain structureof the latest blocks, the adversary proposes no block and honest blocks Bk+2and Bk+3 are kept in the main chain; however, they will be overridden inCase B. Therefore, we need to track the previous block structure of everyhonest block. To this end, we define four states as follows:− S0: the state where the previous round is a timeout and no certified blockis produced;− Si for i ∈ {1, 2, 3}: the state where there exists i consecutive blocks thatare not committed yet.Under the delay attack described in Sec 5.3.2, we can develop a Markovmodel of state transitions in Fig. 5.5. Recall that α (respectively, β) is theprobability that an honest (respectively, adversarial) leader proposes a newblock. Each transition denotes a new round and there exists a designatedleader. An honest leader always proposes a new block that extends thenewest certified block (denoted as the red line in Fig. 5.5). This Markov685.4. Performance Analysismodel allows us to track the previous chain structure for any new honestblock as well as to obtain its chance to be included in the main chain and theassociated delay. We have the following theorem on the delay of pipelinedHotStuff.Theorem 5.6. The latency of pipelined HotStuff under the delay attackconverges to β7+3β6−4β5+2β4+β3−2β2+β+12β7−2β6+β4 with high probability as m→∞.Proof. First, by solving the above Markov model, we can obtain the steady-state distribution of each state as follows:pi0 =(1 + β)(1− β)2β3 − β2 + 1, pi1 =β(1− β)β3 − β2 + 1,pi2 =β2(1− β)β3 − β2 + 1, pi3 =β3β3 − β2 + 1.Next, we can analyze the latency of honest blocks in each state transition.In particular, we focus on the blocks that eventually end up in the mainchain.− Case a: S0β−→ S1. All proposed honest blocks will be kept in the mainchain, and their average delay is β3+β+1β4.− Case b: S1β−→ S2. The honest blocks have α probability to be committedwith an average delay β4+2β3+β+1β4, αβ probability to be committed withan average delay 2β4+β3+β+1β4, and β2 probability to be committed withan average delay 2β4+β3−β2+1β4.− Case c: S2β−→ S3 and S3β−→ S4. The honest blocks have β2 probabilityto be committed with an average delay 2β4+β3−β2+1β4and αβ probabilityto be committed with an average delay 2β4+β3+β+1β4.Due to space constraint, the detailed proofs of these cases are provided inAppendix B1 of our technical report [52]. With these results, it is easy toobtain the latency as:u3(α) =β7 + 3β6 − 4β5 + 2β4 + β3 − 2β2 + β + 12β7 − 2β6 + β4. (5.5)This completes the proof.The theorem shows that when the adversary controls 1/3 of Byzantinenodes (i.e., α = 1/3 and β = 2/3), the average latency for committing one695.4. Performance AnalysisS0 S1 S2 S3a abb babaFigure 5.6: The state transition of the delay attack on DiemBFT.The red line denotes a different action adopted by the adversarial leader inDiemBFT.block under the delay attack is about 8.33 rounds. By contrast, withoutthe delay attack, a block is committed if the next three consecutive blocksextend it with a latency of 3 rounds.5.4.2 DiemBFTWe analyze the performance of DiemBFT under the attack strategies. Inparticular, we will evaluate the differences between pipelined HotStuff andDiemBFT. These differences made by DiemBFT aim to cut off the delay ofrelaying blocks’ QCs or fasten the block commitment (see Sec. 5.2).On the one hand, as the overriding attack strategies are the same, Diem-BFT has the same chain growth rate and chain quality as pipelined HotStuff.In other words, these changes do not affect these two metrics. On the otherhand, we can develop a similar Markov model to analyze the delay attackin DiemBFT as shown in Fig. 5.6. This allows us to obtain the followingtheorem on the latency for DiemBFT.Theorem 5.7. The latency of DiemBFT under the delay attack convergesto β7+β+1β7−β6+β4 with high probability as m→∞.Proof. First, by solving the above Markov model, we can obtain the steady-state distribution of each state as follows:pi0 = 1− β, pi1 = β(1− β), pi2 = β2(1− β), pi3 = β3.Next, we can analyze the latency of honest blocks in each state transition.We detail honest blocks on each event below.− Case a: S0β−→ S1 and S1β−→ S2. All honest blocks produced after aprevious timeout round or just one consecutive block will be kept in themain chain, and their average delay is β2+β+1β4.705.4. Performance Analysis− Case b: S2β−→ S3 and S3β−→ S4. The honest blocks have β2 probabilityto be committed with an average delay 2β4+1β4and αβ probability to becommitted with an average delay 2β4+β3+β2+β+1β4.Due to space constraint, the detailed proofs of these cases are provided inAppendix B2 of our technical report [52]. With these results, it is easy toobtain the latency as:u3(α) =β7 + β + 1β7 − β6 + β4. (5.6)This completes the proof.The theorem shows that when β = 2/3, the average latency for commit-ting one block under the delay attack is about 10.25 rounds. Compared withthe delay in pipelined HotStuff, it suggests that the mechanism of sendingvotes to the next-round leader makes the system more vulnerable to thedelay attack.5.4.3 CountermeasuresOne countermeasure is that current-round leaders broadcast QCs to allnodes (rather than just relaying QCs to next-round leaders)24. Broadcast-ing QCs can provide two benefits. First, when nodes receive QCs, theycan update their locked round, which can effectively thwart the overridingattack. For example, in Fig. 5.7, when honest nodes receive QC for blockBk+2, they can update locked round from k to k+1. As a result, the adver-sarial leader of round k+ 3 can only override block Bk+2; however, withoutthis mechanism, the adversarial leader can override both blocks Bk+1 andBk+2. Second, broadcasting QCs can fasten block commitments. Specifi-cally, when nodes observe a 3-direct chain of Bk, Bk+1, and Bk+2, as wellas block Bk+2’s QC, they can commit block Bk, as shown in Fig. 5.7. Bycontrast, in pipelined HotStuff, without broadcasting QCs, nodes need towait until the subsequent block carrying block Bk+2’s QC is received andthen commit block Bk. As said in Sec. 5.4.1, this enables an adversarialleader at round k + 3 to hide Bk+2’s QC and ruin the 3-direct chain toincrease block delay. Additionally, even in the ideal case, broadcasting QCcan accelerate the block commitment; the latency for committing one blockis reduced to two rounds. In the following, we provide a formal analysis ofthe improvement in chain growth rate, chain quality, and delay.24An earlier version of DiemBFT has adopted this mechanism.715.4. Performance Analysisround k round k+1 round k+2CommitQC Bk+1QC Bk QC Bk+2 QCFigure 5.7: The committing rule with broadcasting QCs in Pipelined Hot-Stuff.Chain Growth Rate and Chain QualityWith broadcasting QCs, an honest block proposed at round i can onlybe overridden by an adversarial leader at round (i+ 1). In other words, anhonest block can be kept in the main chain if and only if the subsequentleader is honest. Let Yi denote an indicator random variable, which equalsto one if {Xi = 1, Xi+1 = 1} and equals to zero otherwise. Next, let Y =∑mi=1 Yi. By following our previous analysis, we can bound the value of Y :Lemma 5.8. For m consecutive rounds, the number of block fragments(Xi, Xi+1) = (1, 1) has the following Chernoff-type bound: For 0 < δ < 1,Pr(|Y − β2m| > δβ2m) < e−Ω(δ2β2m). (5.7)Proof. The analysis is very similar to that for Lemma 5.2.With this lemma, we can easily derive the following theorems on chaingrowth rate and chain quality, respectively.Theorem 5.9. The chain growth rate of pipelined HotStuff with broadcastingQCs under the overriding attack converges to β2 with high probability asm→∞.Theorem 5.10. The chain quality of pipelined HotStuff with broadcastingQCs under the overriding attack converges to β2β2−β+1 with high probabilityas m→∞.These two theorems can be easily proved by following our previous anal-ysis for pipelined HotStuff. Due to space constraints, we do not provide theproofs here. When β = 2/3, the chain growth rate improves by 1.5x, whilethe chain quality improves by 1.2x.725.5. EvaluationS0 S1 S2a abbabFigure 5.8: The state transition of the delay attack on pipelined HotStuffwith broadcasting QCs.LatencyFollowing our previous analysis, we can develop a Markov model of thedelay attack in Fig. 5.8. Note that as the adversarial leader always chooses topropose no blocks, all honest blocks can be kept in the main chain. Moreover,by solving the above Markov model, we have the following theorem.Theorem 5.11. The latency of pipelined HotStuff with broadcasting QCsunder the delay attack converges to β+1β3with high probability as m→∞.Proof. All produced honest blocks will be kept in the main chain, and theiraverage delay is β+1β3. Due to space constraints, the detailed proofs of thesecases are provided in Appendix B3 of our technical report [52].This theorem shows that when β = 2/3, the average latency for com-mitting one block under the delay attack is 5.63 rounds. It suggests thatbroadcasting QCs can reduce the average block latency by almost 3 rounds.Note that broadcasting QCs also brings additional delay. Therefore, it is adesign tradeoff, which should be evaluated in real settings to decide whetherto adopt it.5.5 EvaluationWe implement a proof-of-concept of pipelined HotStuff to evaluate itsperformance in terms of chain growth rate, chain quality, and latency underthe forking and delay attacks.5.5.1 Testnet SetupWe consider a system of 16 nodes, and the number of Byzantine nodesis up to 5. For simplicity, nodes are set to have synchronized clocks, and735.5. Evaluationso the protocol proceeds in synchronized rounds25. We build a full-fledgedimplementation of pipelined HotStuff using Golang (around 3, 600 LoC).We simulate on a late 2013 Apple MacBook Pro, 2.7GHz Intel Core i7.In our experiments, the adversary runs the attack strategies in Sec. 5.3.2.Our simulation results are based on an average of 10 runs, where each rungenerates 100,000 blocks.5.5.2 Pipelined HotStuff and DiemBFTWe evaluate the performance of pipelined HotStuff as well as DiemBFTthrough extensive experiments. Since DiemBFT has the same chain growthrate and chain quality as pipelined HotStuff, these two performance metricsare only given for pipelined HotStuff.Chain Growth Rate. Fig. 5.9 shows the chain growth rate of pipelinedHotStuff with different fractions of Byzantine nodes. First, we observe thatthe simulation results well match the analysis results. Second, the resultsshow that as the fraction α of Byzantine nodes increases, the gap betweenthe chain growth rates with and without the overriding attack also increases.When α is close to 0.3, the chain growth rate under the attack can drops toalmost half of that without attacks.Chain Quality. Fig. 5.10 shows the chain quality of pipelined HotStuffwith different fractions of Byzantine nodes. First, the evaluation resultsmatch our previous analysis. Second, The results show that by the overridingattack, the adversary can lower the chain quality and obtain a higher fractionof blocks in the main chain than what it deserves. If each block in the mainchain brings to its owner a reward, this implies that the adversary can alwaysgain a higher fraction of rewards. In other words, the incentive compatibilitycannot be held anymore under the attack. For example, when α is close to0.3, the chain quality drops to 0.51. This implies that 0.3 of Byzantine nodescan produce almost half of the blocks in the main chain (and obtain half ofthe rewards).Latency. Fig. 5.11 shows the average latency of honest blocks in the mainchain in pipelined Hotstuff and DiemBFT. First, the evaluation results, onceagain, validate our analysis. Second, the results show that as the fractionα of Byzantine nodes increases, both the latency in pipelined Hotstuff andDiemBFT increase. In addition, the latency in DiemBFT is larger thanthat in pipelined HotStuff, which implies that the engineering optimizationsadopted by DiemBFT may make it more vulnerable to the delay attack.25In a partially synchronous network, nodes can establish a synchronized clock as longas they have clocks with bounded drift [18].745.5. Evaluation0.05 0.1 0.15 0.2 0.25 0.3 0.35Byzantine nodes fraction α00.20.40.60.81Chaingrowthrateu1(α)AnalysisSimulationNo attacksFigure 5.9: The chain growth rate under the overriding attack.Note that in both pipelined HotStuff and DiemBFT, the latency for com-mitting one block is three rounds without attacks. Therefore, when α isclose to 0.3, the average latency of honest blocks under the delay attacks isalmost 3x of that without attacks.5.5.3 CountermeasuresWe evaluate the performance of pipelined HotStuff with broadcastingQCs. Fig. 5.12 and 5.13 show that as the fraction α of Byzantine nodesincreases, the gap between the chain growth rates (and chain qualities)of pipelined HotStuff with and without broadcasting QCs also increases.This implies that the higher α is, the higher performance improvement thatbroadcasting QCs brings. Fig. 5.14 shows that the latency of pipelined Hot-Stuff with broadcasting QCs is at least one round shorter than the originalHotStuff. In addition, when α is close to 0.3, the average latency of honest755.6. Related Work0.05 0.1 0.15 0.2 0.25 0.3 0.35Byzantine nodes fraction α0.40.50.60.70.80.91Chainqualityu2(α)AnalysisSimulationNo attacksFigure 5.10: The chain quality under the overriding attack.blocks can drop by almost 3 rounds. As previously explained, broadcast-ing QCs also brings additional delay. Therefore, it is a design tradeoff thatshould be evaluated in real settings.5.6 Related WorkReaching consensus in face of Byzantine failures was formulated as theByzantine agreement problem by Lamport et al. [42], and has been studiedfor several decades. Various BFT consensus protocols such as PBFT [12],Zyzzyva [41], and Q/U [2] have been proposed. However, these classicalBFT protocols suffer from poor scalability, notorious complexity, and leaderfairness issues and are hard to be used in large-scale blockchains. To ad-dress these issues, several state-of-the-art BFT protocols for are proposed forbuilding large-scale blockchains [3, 9, 11, 15, 29, 37, 44, 45, 50, 73]. Here, wemainly introduce some related leader-based BFT protocols for the partially765.6. Related Work0.05 0.1 0.15 0.2 0.25 0.3 0.35Byzantine nodes fraction α345678910Averagelantecyu3(α)Pipelined HotStuff (ana)Pipelined HotStuff (sim)DiemBFT (ana)DiemBFT (sim)Figure 5.11: The average latency of honest blocks under the delay attack.synchronous network.Tendermint. Tendermint [9] features a continuous leader rotation (alsocalled the democracy-favoring leader rotation [15]) based on PBFT proto-col. Specifically, Tendermint embeds the round-change mechanism into thecommon-case pattern, and the leader is re-elected from all the nodes bysome desired policy after every block, resulting in better leadership fairness.Casper FFG. Buterin and Griffith [11] proposed a protocol called CasperFFG, which works as an overlay atop NC to provide a finality gadget. CasperFFG applies an elegant pipelining idea to the classical BFT protocol, i.e.,if each block required two rounds of voting, one can piggyback the secondround on the next block’s voting. This pipelining idea enables the system tohave one identical round (rather than multiple rounds with different func-tionalities and names26), and so significantly simplifies the protocol design.26In PBFT, for committing one proposal, there are two phases: prepare and commit775.6. Related Work0.05 0.1 0.15 0.2 0.25 0.3 0.35Byzantine nodes fraction α00.20.40.60.81Chaingrowthrateu1(α)Pipelied HotStuffBroadcasting QCsNo attacksFigure 5.12: The chain growth rate pipelined HotStuff with and withoutbroadcasting QCs.Pala and Streamlet. Pala [15] is a simple BFT consensus protocol thatalso adopts the pipelining idea. However, for high throughput, it uses astability-favoring leader rotation policy. Based on this work, Chan et al. [14]proposed Streamlet, which further simplifies the voting rule. Streamlet aimsto provide a unified, simple protocol for both teaching and implementation.HotStuff and Fast-HotStuff. HotStuff proposed by Yin et al. [73] cre-atively adopts a three-phase commit rule (rather than the two-phase com-mit rule used in Casper FFG, Pala, and Streamlet) to enable the protocolto reach consensus at the pace of actual network delay. In addition, Hot-Stuff adopts the threshold signature to realize linear message complexity,and can also be pipelined into a practical protocol for building large-scaleblockchains. Fast-HotStuff proposed by Jalalzai et al. [37] has lower latencycompared to the HotStuff and provides better resilience against overridingattacks. However, Fast-HotStuff adds a small overhead to the block duringphases, and each phase has different functionalities.785.7. Summary0.05 0.1 0.15 0.2 0.25 0.3 0.35Byzantine nodes fraction α0.40.50.60.70.80.91Chainqualityu2(α)Pipelied HotStuffBroadcasting QCsNo attacksFigure 5.13: The chain quality of pipelined HotStuff with and without broad-casting QCs.an unhappy path (when the primary fails).5.7 SummaryIn this chapter, we propose a multi-metric evaluation framework includ-ing chain growth rate, chain quality, and latency. We also propose twoattacks, namely the overriding attack and delay attack, and systematicallystudy the impacts of these two attacks on the performance of pipelinedHotStuff. Also, we leverage the framework to evaluate some engineeringdesigns in DiemBFT. Finally, we propose some countermeasures to enhancethe performance of pipelined HotStuff against these attacks. We hope thatour framework can contribute to proposing new variants of HotStuff as wellas making HotStuff more understandable for developers and practitioners interms of performance.795.7. Summary0.05 0.1 0.15 0.2 0.25 0.3 0.35Byzantine nodes fraction α23456789Averagelantecyu3(α)Pipelined HotStuffBroadcating QCsFigure 5.14: The average latency of pipelined HotStuff with and withoutbroadcasting QCs.80Chapter 6ConclusionsThis chapter summarizes the contributions of this thesis and presentsseveral potential future research topics that are related to the accomplishedworks.6.1 Summary of ContributionsThis thesis carefully examines the security of three of the most influentialnext-generation blockchain protocols: Ethereum, Bitcoin-NG, and HotStuff.Specifically, we first evaluate the impact of uncle and nephew block rewardson the selfish mining attack in Ethereum. Then, we extend the incentiveanalysis of Bitcoin-NG by considering the network capacity and the jointattack of the key block and microblock mining. Furthermore, we propose anevaluation framework for pipelined HotStuff and evaluate its performanceunder attacks. Here we summarize the results obtained in each chapter.Contribution 1: We have proposed a Markov model to analyze a selfishmining strategy in Ethereum. Our model enables us to evaluate the impactof the uncle and nephew rewards, which is generally missing in the previousanalysis for selfish mining in Bitcoin. In particular, we have shown how theserewards influence the security of Ethereum mining. Additionally, we havecomputed the hashing power threshold of making selfish mining profitableunder different scenarios, which is essential for us to evaluate the securityof Ethereum mining and to design new reward functions.As one of our major findings, we notice that it is important to con-sider uncle blocks when adjusting the mining difficulty level. Otherwise,Ethereum would be much more vulnerable to selfish mining than Bitcoin.This finding supports the emendation adopted by the third milestone ofEthereum. However, once the mining mechanism is changed, the selfishpool is likely to change its new mining strategies to maximize its profit.Our analysis has inspired several subsequent works on selfish miningin Ethereum. For example, the subsequent work [76] extends our analysisfrom the scenario of a single selfish miner to the scenario of multiple selfishminers. Also, Zhang et al [76] generalize our analysis by quantitatively816.2. Future Worksevaluating the selfish mining in Ethereum under an imperfect blockchainnetwork. Although we assume an ideal network, our results of the selfishmining in Ethereum turn out to be pretty close to theirs.Contribution 2: We have proposed a new incentive analysis of Bitcoin-NG considering the network capacity. Our model enables us to evaluatethe impact of key-block generation interval and microblock generation rate,which is missing in the previous analysis. In particular, we have shown thatBitcoin-NG can still maintain incentive compatibility against the microblockmining attack even under network capacity constraints. In addition, wehave modeled the selfish mining of key blocks and microblocks jointly intoan MDP and shown the threshold of Bitcoin-NG is a little lower than inBitcoin only when the selfish mining power α is greater than 35%. We hopethat our analysis can shed light on the incentive analysis of Bitcoin-NG-likeblockchain protocols under network capacity.Contribution 3: We have proposed a multi-metric evaluation frame-work including chain growth rate, chain quality, and latency. We also pro-posed two attacks, namely the forking attack and delay attack, and sys-tematically study the impacts of these two attacks on the performance ofpipelined HotStuff. Also, we have leveraged the framework to evaluate someengineering designs in DiemBFT. Finally, we have proposed some counter-measures to enhance the performance of pipelined HotStuff against theseattacks.As one of our major findings, we notice that some introduced “optimiza-tions” may not optimize the system performance. This is because, usually,these optimizations are designed to promote protocol performance underthe happy case (i.e., all nodes are honest). However, in a Byzantine envi-ronment, an adversary may exploit these optimizations to deteriorate thesystem. This means that any new optimizations should be fully evaluated—especially under attacks—before being adopted. Overall, we hope that ourframework would be helpful in proposing new variants of HotStuff as wellas making HotStuff more understandable for developers and practitioners interms of performance.6.2 Future WorksThis dissertation has filled in several research gaps in the literature bydeveloping new theoretical tools for evaluating the security and performanceof three next-generation blockchain protocols. Still, there are other inter-esting research gaps out there. Here, we provide several examples.826.2. Future WorksIn Chapter 3, we analyzed a selfish mining strategy in Ethereum withoutconsidering block propagation delay. First, this selfish mining strategy isnot optimal, we will leave the study of finding the optimal mining strategyand evaluate its impact as one of our future works. We believe that ouranalysis developed in this thesis (especially the probabilistic tracking) wouldbe useful in studying other mining strategies. Second, in reality, blocks needto take a while to reach all the nodes. In particular, due to the propagationdelay, there may exist chain forks. Due to the longest chain rule, someforking blocks may not be included in the longest chain, and these blocksare often called stable blocks. Since stale blocks are not in the main chain,they increase the advantage of the selfish miner to take block leads in theattack, and so can be regarded as the waste of honest miners’ computationpower against the attack. Hence, the more stale blocks, the more wastingcomputation power. An in-depth study on these factors is still needed.In Chapter 4, to make the MDP tractable, we confined our analysis toa family of selfish mining strategies. Removing the restriction is one ofour future works. In Chapter 5, we analyzed the performance of pipelinedHotStuff under several attacks. We argue that these attacks are optimalunder our settings, but did not provide formal proof. Naturally, one of ourfuture works is to prove this claim rigorously.83Bibliography[1] Tendermint: Byzantine fault tolerance in the age of blockchains.(2016).2016. → pages[2] Michael Abd-El-Malek, Gregory R. Ganger, Garth R. Goodson,Michael K. Reiter, and Jay J. Wylie. Fault-scalable Byzantine fault-tolerant services. SIGOPS Oper. Syst. Rev., 39(5):59–74, October 2005.→ pages 76[3] Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman. Asymptoti-cally optimal validated asynchronous Byzantine agreement. In Proceed-ings of the ACM Symposium on Principles of Distributed Computing,PODC ’19, pages 337–346, 2019. → pages 76[4] Vivek Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, and PramodViswanath. Deconstructing the blockchain to approach physical limits.arXiv preprint arXiv:1810.08092, 2018. → pages 15, 28[5] Vivek Kumar Bagaria, Sreeram Kannan, David Tse, Giulia C. Fanti,and Pramod Viswanath. Prism: Deconstructing the blockchain to ap-proach physical limits. In Proceedings of the 2019 ACM SIGSAC Con-ference on Computer and Communications Security, CCS 2019, Lon-don, UK, November 11-15, 2019., pages 585–602, 2019. → pages 2, 3,34[6] Lear Bahack. Theoretical Bitcoin attacks with less than half of thecomputational power (draft). arXiv preprint arXiv:1312.7013, 2013.→ pages 31[7] Shehar Bano, Mathieu Baudet, Avery Ching, Andrey Chursin, GeorgeDanezis, Franc¸ois Garillot, Zekun Li, Dahlia Malkhi, Oded Naor,Dmitri Perelman, et al. State machine replication in the Librablockchain, May 2020. → pages 4, 6084Bibliography[8] Shehar Bano, Alberto Sonnino, Andrey Chursin, Dmitri Perelman, andDahlia Malkhi. Twins: White-glove approach for BFT testing. arXivpreprint arXiv:2004.10617, 2020. → pages 60[9] Ethan Buchman. Tendermint: Byzantine fault tolerance in the age ofblockchains. M. eng. thesis, The University of Guelph, June 2016. →pages 4, 76, 77[10] Vitalik Buterin et al. A next-generation smart contract and decentral-ized application platform. white paper, 2014. → pages 9[11] Vitalik Buterin and Virgil Griffith. Casper the friendly finality gadget.arXiv preprint arXiv:1710.09437, 2017. → pages 4, 76, 77[12] Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance.In Proceedings of the Third Symposium on Operating Systems Designand Implementation, OSDI ’99, pages 173–186, 1999. → pages 3, 4, 12,58, 76[13] Iadine Chade`s, Guillaume Chapron, Marie-Jose´e Cros, Fre´de´rick Gar-cia, and Re´gis Sabbadin. Mdptoolbox: a multi-platform toolbox to solvestochastic dynamic programming problems. Ecography, 37(9):916–920,2014. → pages 53[14] Benjamin Y. Chan and Elaine Shi. Streamlet: Textbook streamlinedblockchains. IACR Cryptol. ePrint Arch., page 88, 2020. → pages 78[15] T-H Hubert Chan, Rafael Pass, and Elaine Shi. Pala: A simple partiallysynchronous blockchain. IACR Cryptology ePrint Archive, page 981,2018. → pages 76, 77, 78[16] Kyle Croman, Christian Decker, Ittay Eyal, Adem Efe Gencer, AriJuels, Ahmed E. Kosba, Andrew Miller, Prateek Saxena, Elaine Shi,Emin Gu¨n Sirer, Dawn Song, and Roger Wattenhofer. On scaling de-centralized blockchains - (A position paper). In Financial Cryptographyand Data Security, pages 106–125, Berlin, Heidelberg, 2016. SpringerBerlin Heidelberg. → pages 3[17] C. Decker and R. Wattenhofer. Information propagation in the Bitcoinnetwork. In IEEE P2P 2013 Proceedings, pages 1–10, Sep. 2013. →pages 2885Bibliography[18] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in thepresence of partial synchrony. Journal of the ACM (JACM), 35(2):288–323, 1988. → pages 57, 74[19] Ethereum. Design rationale: Uncle incentivizatinon. github, Aug, 2018.→ pages 29[20] Ethereum. Mining rewards, 2018. → pages 9[21] Ittay Eyal, Adem Efe Gencer, Emin Gun Sirer, and Robbert Van Re-nesse. Bitcoin-NG: A scalable blockchain protocol. In 13th USENIXSymposium on Networked Systems Design and Implementation (NSDI16), pages 45–59, 2016. → pages 2, 3, 6, 11, 33, 37, 39, 40, 45, 53, 55,56[22] Ittay Eyal and Emin Gu¨n Sirer. Majority is not enough: Bitcoin miningis vulnerable. Commun. ACM, 61(7):95–102, June 2018. → pages 5, 6,12, 14, 15, 16, 21, 23, 25, 30, 33, 34, 35, 40, 62[23] Robert G Gallager. Stochastic processes: theory for applications. Cam-bridge University Press, 2013. → pages 15[24] Juan Garay, Aggelos Kiayias, and Nikos Leonardos. The Bitcoin back-bone protocol: Analysis and applications. In Advances in Cryptology -EUROCRYPT 2015, pages 281–310. Springer, 2015. → pages 13[25] Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. The Bitcoinbackbone protocol: Analysis and applications. In Advances in Cryp-tology - EUROCRYPT 2015, pages 281–310. Springer, 2015. → pages3[26] Adem Efe Gencer, Soumya Basu, Ittay Eyal, Robbert Van Renesse, andEmin Gu¨n Sirer. Decentralization in bitcoin and ethereum networks. InInternational Conference on Financial Cryptography and Data Security,pages 439–457. Springer, 2018. → pages 29[27] Arthur Gervais, Ghassan O. Karame, Karl Wu¨st, Vasileios Glykantzis,Hubert Ritzdorf, and Srdjan Capkun. On the security and performanceof proof of work blockchains. In Proceedings of the 2016 ACM SIGSACConference on Computer and Communications Security, CCS ’16, pages3–16. ACM, 2016. → pages 3, 5, 6, 9, 12, 14, 15, 29, 3186Bibliography[28] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nicko-lai Zeldovich. Algorand: Scaling Byzantine agreements for cryptocur-rencies. In Proceedings of the 26th Symposium on Operating SystemsPrinciples, SOSP ’17, pages 51–68. ACM, 2017. → pages 4, 62[29] Bingyong Guo, Zhenliang Lu, Qiang Tang, Jing Xu, and ZhenfengZhang. Dumbo: Faster asynchronous BFT protocols. In Proceedings ofthe 2018 ACM SIGSAC Conference on Computer and CommunicationsSecurity, CCS ’20, pages 803–818, 2020. → pages 76[30] Yangrui Guo, Qiandong Yang, Hui Zhou, WeiQiang Lu, and ShengZeng. Syetem and methods for selection and utilizing a committee ofvalidator nodes in a distributed system. Cypherium Blockchain, Feb2020. Patent. → pages 4[31] J. Go¨bel, H.P. Keeler, A.E. Krzesinski, and P.G. Taylor. Bitcoinblockchain dynamics: The selfish-mine strategy in the presence of prop-agation delay. Performance Evaluation, 104:23 – 41, 2016. → pages 31[32] Ethan Heilman. One weird trick to stop selfish miners: Fresh bitcoins, asolution for the honest miner. In International Conference on FinancialCryptography and Data Security, pages 161–162. Springer, 2014. →pages 6, 14, 31[33] Ethan Heilman, Alison Kendler, Aviv Zohar, and Sharon Goldberg.Eclipse attacks on Bitcoin’s peer-to-peer network. In Proceedings of the24th USENIX Conference on Security Symposium, page 129–144, 2015.→ pages 63[34] Alexander Hentschel, Yahya Hassanzadeh-Nazarabadi, Ramtin Seraj,Dieter Shirley, and Layne Lafrance. Flow: Separating consen-sus and compute–block formation and execution. arXiv preprintarXiv:2002.07403, 2020. → pages 4[35] Jochen Hoenicke. Unconfirmed transaction count (mempool), 2020. →pages 35[36] Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, and BenjaminReed. Zookeeper: Wait-free coordination for internet-scale systems.In Proceedings of the 2010 USENIX Conference on USENIX AnnualTechnical Conference (USENIX ATC), page 11, 2010. → pages 5887Bibliography[37] Mohammad M. Jalalzai, Jianyu Niu, Chen Feng, and Fangyu Gai.Fast-HotStuff: A fast and resilient HotStuff protocol. arXiv preprintarXiv:2010.11454, 2020. → pages 76, 78[38] Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels. Order-fairness for byzantine consensus. In Annual International CryptologyConference, pages 451–480. Springer, 2020. → pages 5[39] Lucianna Kiffer, Rajmohan Rajaraman, and Abhi Shelat. A bettermethod to analyze blockchain consistency. In Proceedings of the 2018ACM SIGSAC Conference on Computer and Communications Security,CCS ’18, pages 729–744. ACM, 2018. → pages 13[40] Eleftherios Kokoris Kogias, Philipp Jovanovic, Nicolas Gailly, IsmailKhoffi, Linus Gasser, and Bryan Ford. Enhancing Bitcoin security andperformance with strong consistency via collective signing. In 25thUSENIX Security Symposium (USENIX Security 16), pages 279–296,2016. → pages 3[41] Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, andEdmund Wong. Zyzzyva: speculative Byzantine fault tolerance. ACMSIGOPS Operating Systems Review, 41(6):45–58, 2007. → pages 76[42] Leslie Lamport, Robert E. Shostak, and Marshall C. Pease. The Byzan-tine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382–401,1982. → pages 76[43] SD Lerner. Uncle mining, an Ethereum consensus protocol flaw. Bitslogblog, Apr, 2016. → pages 31[44] Yuan Lu, Zhenliang Lu, Qiang Tang, and Guiling Wang. Dumbo-MVBA: Optimal multi-valued validated asynchronous Byzantine agree-ment, revisited. In Proceedings of the ACM Symposium on Principlesof Distributed Computing, PODC ’20, pages 129–138, 2020. → pages76[45] Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song.The honey badger of BFT protocols. In Proceedings of the 2016 ACMSIGSAC Conference on Computer and Communications Security, CCS’16, pages 31–42. ACM, 2016. → pages 4, 76[46] Bhabendu Kumar Mohanta, Debasish Jena, Somula Ramasubbareddy,Mahmoud Daneshmand, and Amir H. Gandomi. Addressing security88Bibliographyand privacy issues of iot using blockchain technology. IEEE Internet ofThings Journal, 8(2):881–888, 2021. → pages 1[47] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system.Working Paper, 2008. → pages 8, 12, 15, 34, 58, 62[48] K. Nayak, S. Kumar, A. Miller, and E. Shi. Stubborn mining: Gen-eralizing selfish mining and combining with an eclipse attack. In 2016IEEE European Symposium on Security and Privacy (EuroS P), pages305–320. IEEE, March 2016. → pages 6, 12, 14, 21, 31[49] J. Niu and C. Feng. Selfish mining in ethereum. In 2019 IEEE 39thInternational Conference on Distributed Computing Systems (ICDCS),pages 1306–1316, July 2019. → pages 22, 33, 34, 62[50] Jianyu Niu and Chen Feng. Leaderless Byzantine fault tolerant con-sensus. arXiv preprint arXiv:2012.01636, 2020. → pages 76[51] Jianyu Niu, Chen Feng, Hoang Dau, Yu-Chih Huang, and JinggeZhu. Analysis of Nakamoto consensus, revisited. arXiv preprintarXiv:1910.08510, 2019. → pages 93[52] Jianyu Niu, Fangyu Gai, Mohammad M. Jalalzai, and Chen Feng. Onthe performance of pipelined HotStuff. In 2021 IEEE Conference onComputer Communications, INFOCOM, virtual, May 10-13, 2021. →pages 66, 67, 69, 71, 73[53] Jianyu Niu, Ziyu Wang, Fangyu Gai, and Chen Feng. Incentive analysisof Bitcoin-NG, revisited. In Performance Evaluation: An InternationalJournal, volume 144, page 102144. Elsevier, 2020. → pages 62[54] Diego Ongaro and John Ousterhout. In search of an understandableconsensus algorithm. In 2014 USENIX Annual Technical Conference(USENIX ATC), pages 305–319, June 2014. → pages 58[55] Nikolaos Papadis, Sem C. Borst, Anwar Walid, Mohamed Grissa, andLeandros Tassiulas. Stochastic models and wide-area network measure-ments for blockchain design and analysis. In 2018 IEEE Conferenceon Computer Communications, INFOCOM 2018, Honolulu, HI, USA,April 16-19, 2018, pages 2546–2554, 2018. → pages 15, 28[56] Rafael Pass, Lior Seeman, and Abhi Shelat. Analysis of the blockchainprotocol in asynchronous networks. In Advances in Cryptology – EU-ROCRYPT 2017, pages 643–673. Springer, 2017. → pages 3, 1389Bibliography[57] Rafael Pass and Elaine Shi. Fruitchains: A fair blockchain. In Proceed-ings of the ACM Symposium on Principles of Distributed Computing,PODC ’17, pages 315–324. ACM, 2017. → pages 62[58] Rafael Pass and Elaine Shi. Hybrid consensus: Efficient consensus inthe permissionless model. In 31st International Symposium on Dis-tributed Computing (DISC 2017), volume 91 of Leibniz InternationalProceedings in Informatics (LIPIcs), pages 39:1–39:16, 2017. → pages3[59] M. Pease, R. Shostak, and L. Lamport. Reaching agreement in thepresence of faults. J. ACM, page 228–234, April 1980. → pages 3[60] Partha Pratim Ray, Biky Chowhan, Neeraj Kumar, and Ahmad Al-mogren. Biothr: Electronic health record servicing scheme in iot-blockchain ecosystem. IEEE Internet of Things Journal, pages 1–1,2021. → pages 1[61] Fabian Ritz and Alf Zugenmaier. The impact of uncle rewards on selfishmining in Ethereum. In 2018 IEEE European Symposium on Securityand Privacy Workshops (EuroS PW), pages 50–57. IEEE, April 2018.→ pages 31[62] Ayelet Sapirshtein, Yonatan Sompolinsky, and Aviv Zohar. Optimalselfish mining strategies in Bitcoin. In International Conference onFinancial Cryptography and Data Security, pages 515–532. Springer,2016. → pages 6, 12, 14, 15, 31, 33, 35, 40, 47, 55[63] Siamak Solat and Maria Potop-Butucaru. Zeroblock: Preventing self-ish mining in Bitcoin. Technical report, Sorbonne Universites, UPMCUniversity of Paris 6, 2016. → pages 31[64] Yonatan Sompolinsky and Aviv Zohar. Secure high-rate transactionprocessing in Bitcoin. In Financial Cryptography and Data Security,pages 507–527. Springer, 2015. → pages 2[65] Yonatan Sompolinsky and Aviv Zohar. Secure high-rate transactionprocessing in Bitcoin. In Financial Cryptography and Data Security,pages 507–527. Springer, 2015. → pages 3[66] Yonatan Sompolinsky and Aviv Zohar. Secure high-rate transactionprocessing in bitcoin. In International Conference on Financial Cryp-tography and Data Security, pages 507–527. Springer, 2015. → pages 9,3190Bibliography[67] Alexander Spiegelman and Arik Rinberg. ACE: Abstract consensusencapsulation for liveness boosting of state machine replication. arXivpreprint arXiv:1911.10486, 2019. → pages 59[68] Taotao Wang, Xiaoqian Bai, Hao Wang, Soung Chang Liew, andShengli Zhang. Game-theoretic analysis of mining strategy in Bitcoin-NG blockchain protocol. CoRR, abs/1911.00900, 2019. → pages 56[69] Ziyu Wang, Jianwei Liu, Zongyang Zhang, Yanting Zhang, Jiayuan Yin,Hui Yu, and Wenmao Liu. A combined micro-block chain truncationattack on bitcoin-ng. In Information Security and Privacy, pages 322–339. Springer International Publishing, 2019. → pages 6, 33, 54, 55,56[70] Gavin Wood. Ethereum: A secure decentralised generalised transactionledger Byzantium version. Ethereum project yellow paper, pages 1–32,2018. → pages 2, 6, 14[71] Jiayuan Yin, Changren Wang, Zongyang Zhang, and Jianwei Liu. Re-visiting the incentive mechanism of Bitcoin-ng. In Information Securityand Privacy, pages 706–719. Springer, 2018. → pages 6, 33, 37, 38, 45,56[72] Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, andIttai Abraham. Hotstuff: BFT consensus in the lens of blockchain.arXiv preprint arXiv:1803.05069, 2018. → pages 61[73] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, andIttai Abraham. HotStuff: BFT consensus with linearity and respon-siveness. In Proceedings of the ACM Symposium on Principles of Dis-tributed Computing, PODC ’19, pages 347–356. ACM, 2019. → pages2, 4, 12, 58, 59, 60, 76, 78[74] Haifeng Yu, Ivica Nikolic, Ruomu Hou, and Prateek Saxena. Ohie:Blockchain scaling made simple. In Proceedings of the 41th IEEE Sym-posium on Security and Privacy, S&P. IEEE, 2020. → pages 2[75] Ren Zhang and Bart Preneel. Publish or perish: A backward-compatible defense against selfish mining in Bitcoin. In Cryptographers’Track at the RSA Conference, pages 277–292. Springer, 2017. → pages6, 14, 3191Bibliography[76] Shiquan Zhang, Kaiwen Zhang, and Bettina Kemme. Analysing thebenefit of selfish mining with multiple players. In 2020 IEEE Interna-tional Conference on Blockchain (Blockchain), pages 36–44, 2020. →pages 81[77] Yunhao Zhang, Srinath Setty, Qi Chen, Lidong Zhou, and LorenzoAlvisi. Byzantine ordered consensus without byzantine oligarchy. In14th USENIX Symposium on Operating Systems Design and Imple-mentation (OSDI 20), pages 633–649. USENIX Association, November2020. → pages 592Appendix AConcentration BoundsLemma A.1 (Chernoff bound for a sum of dependent random variables [51]).Let T be a positive integer. Let X(j) =∑n−1i=0 Xj+iT be the sum of n inde-pendent indicator random variables and µj = E(X(j))for j ∈ {1, . . . , T}.Let X = X(1) + · · · + X(T ). Let µ = minj{µj}. Then, for 0 < δ < 1,Pr (X ≤ (1− δ)µT ) ≤ e−δ2µ/2.93Appendix BThe Multiple SummationsFunctionThe function f(x, y, z) used in Sec. 3.3.2 involves multiple summationswhen z > 1. We provide several examples to explain this function.Example B.1 (z = 1, x ≥ y + 2).f(x, y, 1) =x∑s1=y+21= x− y − 1.Example B.2 (z = 2, x ≥ y + 2).f(x, y, 2) =x∑s2=y+2s2∑s1=y+11=x∑s2=y+2(s2 − y)= 2 + · · ·+ (x− y)=(x− y − 1)(x− y + 2)2.94Appendix CReward AnalysisLemma C.1. Consider a new block associated with a state transition fromstate (i, j) with i− j ≥ 2. It will be a regular block with probability 1 if andonly if it is mined by the selfish pool.Proof. Suppose that the current system state is (i, j) with i− j ≥ 2. If theselfish pool mines a new block, then the state becomes (i+ 1, j). Now, theprivate branch has an advantage of at least 3 blocks (since i+1−j ≥ 3) overpublic branches. As the system evolves, the private branch will be publishedwith probability 1 and become part of the system main chain, according toAlgorithm 1. In other words, the new block will be a regular block withprobability 1. On the other hand, if some honest miners mine a new block,we consider two cases.1. i − j = 2. In this case, we have Lh = j + 1 and Ls = Lh + 1. Hence,the pool will publish its private branch and the new block becomes astale block.2. i − j ≥ 3. In this case, the system state becomes either (i, j + 1) or(i − j, 1). The private branch has an advantage of at least 3 blocks(since i − j ≥ 3). Hence, it will be published with probability 1. Inother words, the new block will be a stale block with probability 1.We are now ready to analyze every state transition. We call a new blockassociated with a transition a target block.Case 1: (0, 0)β→ (0, 0)In this case, the target block generated by some honest miners will beadopted by all the miners. Thus, it will be a regular block and receive astatic reward Ks.Case 2: (0, 0)α→ (1, 0)In this case, the selfish pool produces the target block, keeps it private,and continues mining on it. First, we analyze the static reward by deter-mining whether the target block will be a regular block or not. To this end,we consider the following two subcases, which are illustrated in Fig. C.1.95Appendix C. Reward AnalysisA1A2B1A1Selfish miners' secret blockSelfish miners' published blockHonest miners' blockA1 A1Case 1: Subcase 1 Case 1: Subcase 2Figure C.1: The two subcases of Case 1: 1) the selfish pool mines a subse-quent block; 2) some honest miners mine a new block.1. Subcase 1 : The subsequent block is mined by the pool, which happenswith probability α. As a result, the pool owns a lead of two blocks.By Lemma C.1, the target block will be a regular block and receive astatic reward of Ks.2. Subcase 2 : The subsequent block is mined by some honest miners,which happens with probability β. Then, the pool will publish thistarget block. To determine whether it will be a regular block, weneed to consider the following three subsubcases. See Fig. C.2 for anillustration.Subsubcase 1 : The pool mines a new block on its private branch andpublishes it immediately. (This happens with probability α.) Now,the target block becomes a regular block.Subsubcase 2 : Some honest miners mine a new block on the targetblock. (This happens with probability βγ.) Now, the target blockbecomes a regular block.Subsubcase 3 : Some honest miners mine a new block and referencethe target block. (This happens with probability β(1− γ).) Now, thetarget block becomes an uncle block.To sum up, the target block in Case 2 will eventually be a regular block withprobability α+ αβ + β2γ and be an uncle block with probability β2(1− γ).(Note that these two probabilities sum up to 1.)Next, we analyze the uncle and nephew rewards associated with the tar-get block. Based on our previous case-by-case discussion, only in subsubcase96Appendix C. Reward AnalysisSelfish miners' secret blockSelfish miners' published blockHonest miners' blockCase 1: Subsubcase 1 Case 1: Subsubcase 3A1A2A1A2A1A2Case 1:Subsubcase 2B1B2 B2Uncle blocks' referenceFigure C.2: The three subsubcases of Case 1: 1) the selfish pool mines anew block and publishes it; 2) the honest miners find a new block on thetarget block; 3) some honest miners mine a new block and reference thetarget block.3, the target block will be an uncle block. Also, the distance between thetarget block and its nephew block is 1. As such, the target block will bringthe pool an uncle reward of Ku(1) and some honest miners will receive anephew reward of Kn. (This happens with probability β2(1− γ).)Case 3: (1, 0)α→ (2, 0)In this case, the pool produces the target block, keeps it private, andcontinues mining on it. By Lemma C.1, the target block will be a regularblock and receive a static reward of Ks.Case 4: (1, 0)β→ (1, 1)In this case, some honest miners mine the target block, then the poolpublishes its private block. First, we analyze the static reward by determin-ing whether the target block is a regular block. To this end, we consider thefollowing subcases. See Fig. C.3 for an illustration.1. Subcase 1 : The pool mines a new block on its private branch, refer-ences the target block, and publishes its private branch. (This happenswith probability α.) Now, the target block becomes an uncle block.2. Subcase 2 : Some honest miners mine a new block not on the targetblock and reference the target block. (This happens with probabilityβγ.) Now, the target block becomes an uncle block.3. Subcase 3 : Some honest miners mine a new block on the target block.(This happens with probability β(1 − γ).) Now, the target block be-97Appendix C. Reward Analysiscomes a regular block.Selfish miners' secret blockSelfish miners' published blockHonest miners' blockCase 4: Subcase 1 Case 4: Subcase 3A1A2A1A2A1A2Case 4:Subcase 2B1B2 B2Uncle blocks' referenceFigure C.3: The three subcases of Case 4: 1) the selfish pool mines a newblock on its branch and references the target block; 2) some honest minersfind a new block not on the target block and reference the target block; 3)some honest miners mine a new block on the target block.To sum up, the target block will eventually be a regular block with proba-bility β(1− γ), and be an uncle block with probability α+ βγ.Next, we analyze the uncle and nephew rewards associated with thetarget block. Based on our previous case-by-case discussion, the target blockwill become an uncle block only in subcases 1 and 2, where the distance is 1.Thus, the target block will bring honest miners an uncle reward of Ku(1).As for the nephew reward, in Subcase 1, the pool receives it, and in Subcase2, some honest miners receive it. To sum up, honest miners will receivean uncle block reward of Ku(1) with probability α + βγ, receive a nephewreward of Kn with probability βγ, and the pool will receive a nephew rewardof Kn with probability α.Case 5: (1, 1)1→ (0, 0)In this case, the target block will always be a regular block no matterwho mines it. Hence, the pool receives a static reward with probability α,and some honest miners receive a static reward with probability β.Case 6: (i, j)α→ (i+ 1, j) with i ≥ 2 and j ≥ 0In this case , the pool mines the target block, keeps it private, andcontinues mining. By Lemma C.1, the target block will eventually becomea regular block, receiving a static reward of Ks.98Appendix C. Reward AnalysisCase 7: (i, j)βγ→ (i− j, 1) with i− j ≥ 3 and j ≥ 1In this case, some honest miners mine the target block on a public branchthat is a prefix of the private branch. Then, the pool publishes its firstunpublished block. By Lemma C.1, the target block will eventually becomean uncle block.Next, we analyze the uncle and nephew rewards associated with the tar-get block. We begin with the special case of (4, 1)→ (3, 1) before discussingthe general case. We consider the following three subcases.1. Subcase 1 : The pool mines a subsequent block and references thetarget block. See Fig. C.4 for an illustration. (This happens withprobability α.) By Lemma C.1, the target block will become an uncleblock, receiving an uncle reward of Ku(3). The pool will receive anephew reward.B1A1 C1 D1A2B1A1 C1A2B2D1B2E1Selfish miners' secret blockSelfish miners' published blockHonest miners' blockUncle blocks' referenceFigure C.4: The subcase 1 of Case 7, in which the pool mines a subsequentblock, references the target block and eventually wins the associated nephewreward.2. Subcase 2 : Some honest miners mine a subsequent block on the targetblock. (This happens with probability β(1 − γ).) Then, the poolwill publish its private branch. See Fig. C.5 for an illustration. Todetermine the uncle and nephew rewards, we need to consider thefollowing subsubcases.Subsubcase 1 : Some honest miners mine a new block and references thetarget block. See Fig. C.6. This subsubcase happens with probabilityβ(1−γ)β. The honest miner receives a nephew reward, and the targetblock receives an uncle reward of Ku(3) since the distance is 3.Subsubcase 2 : The pool mines a new block and keeps it private. Thissubsubcase happens with probability β(1−γ)α. Now, if the new block99Appendix C. Reward AnalysisC2B1A1 C1 D1A2B1A1 C1A2B2D1B2Selfish miners' secret blockSelfish miners' published blockHonest miners' blockUncle blocks' referenceFigure C.5: The subcase 2 of Case 7, in which some honest miners mine asubsequent block on the target block.C2B1A1 C1A2D1B2Selfish miners' secret blockSelfish miners' published blockHonest miners' blockUncle blocks' referenceC2B1A1 C1A2D1B2E2Figure C.6: The subsubcase 1 of Case 7, in which some honest miners minea block in state (0, 0) and win the associated nephew reward.later becomes a regular block (with probability α + αβ + β2γ due tothe discussion for Case 2 ), the pool will receive a nephew reward andthe target block will receive an uncle reward of Ku(3). Otherwise, ifthe new block later becomes a stale block (with probability β2(1− γ)due to the discussion for Case 2 ), some honest miners will receive anephew reward and the target block will again receive an uncle rewardof Ku(3).3. Subcase 3 : Some honest miners don’t mine a subsequent block onthe target block. (This happens with probability βγ.) In terms ofthe analysis of uncle and nephew rewards, Subcase 3 is the same asSubcase 2.100Appendix C. Reward AnalysisC2B1A1 C1A2D1B2Selfish miners' secret blockSelfish miners' published blockHonest miners' blockUncle blocks' referenceC2B1A1 C1A2D1B2E2E1F2Figure C.7: The subsubcase 2 of Case 7, in which the selfish pool mines anew block in state (0, 0), but finally loses to the nephew reward.To sum up, for the special case of (4, 1) → (3, 1), the target block willalways receive an uncle reward of Ku(3). As for the nephew reward, onecan draw a tree diagram summarizing all the subcases discussed above andconclude that it will be received by honest miners with probability β2(1 +αβ(1− γ)) and by the pool with probability 1− β2(1 + αβ(1− γ)).Here, we note that the probability β2(1 + αβ(1 − γ)) (that the nephewreward will be received by honest miners) can be explained as follows. First,the honest miners have to “push” the system state from (3, 1) to (0, 0)while the pool mines nothing. (Otherwise, the pool will receive the nephewreward by Lemma C.1.) This happens with probability β. Second, startingfrom (0, 0), the honest miners can win the nephew reward with probabilityβ(1 + αβ(1− γ)). This interpretation allows us to analyze the general case.First, the honest miners have to “push” the system state from (i−j, 1) to(0, 0) while the pool mines nothing. This happens with probability βi−j−2.Second, starting from (0, 0), the honest miners can win the nephew rewardwith probability β(1 + αβ(1 − γ)). Therefore, the nephew reward will bereceived by honest miners with probability βi−j−1(1 + αβ(1 − γ)) and bythe pool with probability 1− βi−j−1(1 + αβ(1− γ)).Case 8: (i, j)βγ→ (0, 0) with i− j = 2 and j ≥ 1In this case, some honest miners mine the target block. Then, the poolpublishes its private branch. Now, the target block becomes an uncle block.Similar to Case 7, the target block will receive an uncle reward of Ru(2),and the nephew reward will be received by honest miners with probabilityβ(1 + αβ(1− γ)) and by the pool with probability 1− β(1 + αβ(1− γ)).Case 9: (2, 0)β→ (0, 0) with i ≥ 2101Appendix C. Reward AnalysisIn this case, some honest miners mine the target block. Then, the poolpublishes its private branch. The remaining discussion is the same as Case8.Case 10: (i, 0)β→ (i, 1) with i ≥ 3In this case, some honest miners mine the target block. Then, the poolpublishes its first unpublished block. By Lemma C.1, the target block willeventually become an uncle block. Similar to the discussion for Case 7,we conclude that the target block will receive an uncle reward of Ku(i),and the nephew reward will be received by honest miners with probabilityof βi−1(1+αβ(1−γ)) and by the pool with probability 1−βi−1(1+αβ(1−γ)).Case 11: (i, j)β(1−γ)→ (i, j + 1) with i− j ≥ 3 and j ≥ 1In this case, some honest miners mine the target block. Then, the poolpublishes its first unpublished block. By Lemma C.1, the target block willeventually become a stale block. Since its parent block is not in the systemmain chain, the target block will not be an uncle block.Case 12: (i, j)β(1−γ)→ (0, 0) with i− j = 2 and j ≥ 1In this case, some honest miners mine the target block. Then, the poolpublishes its private branch. Similar to Case 11, the target block will neitherbe a regular block nor an uncle block.102Appendix DHotStuff AnalysisD.1 Pipelined HotStuffBased on the defined states in Sec.5.4.1, we introduce an additional stateSx, where the newest certified block together with its predecessor blocksform a 3-chain structure. By the aforementioned commit rule, when nodesobserver a 3-chain structure, the first block in the 3-chain structure togetherwith its predecessor blocks are all committed (see Sec. 5.2.1). This furthermeans when an honest block is kept in the main chain, and its descendantblocks first form a 3-chain structure, it will be committed.By slightly modified the Markov model in Fig. 5.5, we can show thestate transitions for a node to observe some new committed blocks (i.e.,entering state Sx) in Fig. D.1. Furthermore, we can compute the expectedrounds for a state Si (i ∈ {0, 1, 2, 3}) to first enter state Sx. To realize this,we introduce a new variable Xi, which denotes the number of rounds thatstarting from state Si, the state first hits state Sx. In addition, we use E [Xi]to denote the expectation of Xi. With the state transitions, we can havethe following equation.E [X0] = αE [X0] + βE [X1] + 1E [X1] = αE [X0] + βE [X2] + 1E [X2] = αE [X0] + βE [X3] + 1E [X3] = αE [X1] + 1(D.1)By solving the equation (D.1), we can get:E [X0] =2β3 + β + 1β4, E [X1] =β3 + β + 1β4,E [X2] =(1 + β)(β2 − β + 1)β4, E [X3] =β3 − β2 + 1β4.Next, we can track honest blocks kept in the main chain and their asso-ciated delay. In addition, we refer to these tracked honest blocks as target103D.1. Pipelined HotStuffS0 S1 S2 S3a abb babaSxFigure D.1: The state transition of the delay attack on pipelined HotStuff.blocks. As we said previously, the chance that an honest block is kept inthe main chain and its delay is affected by the delay attack strategies, whichfurther depend on the chain structure. Hence, according to its predecessorblocks structure, we can divide honest blocks into the following three cases:− Case a: S0β−→ S1. This state transition denotes that a target block isproposed after a previous timeout round. By the delay attack strategiesin Sec. 5.3.2, the honest block will always be kept in the main chain.Further, as the current system state is S1, the delay for the target blockto be committed is E [X1].− Case b: S1β−→ S2. This state transition denotes that a target blocktogether with its parent block can only form two consecutive blocks.According to the subsequent leaders (and blocks), the delay for this targetblock can be divided into three subcases:Subcase 1 : The next leader is adversarial and proposes no block. Thissubcase happens with probability α. By then, the system state is S0, andthe average delay for this target block to be committed is E [X0] + 1.Subcase 2 : Some honest leaders propose the next block, and then thisblock is overridden by a block of the subsequent adversarial leader. Thissubcase happens with probability βα. By then, as the state is S1, theaverage delay for this target block to be committed is E [X1] + 2.Subcase 3 : Some honest leader propose the next two blocks. This sub-case happens with probability β2. As the state is S3, the average delayfor this target block to be committed is E [X3] + 2.− Case c: S2β−→ S3 and S3β−→ S4. This state transition denotes that a tar-get block together with its predecessor blocks can form three consecutiveblocks. According to the subsequent leaders (and blocks), the delay forthis target block can be divided into two subcases:Subcase 1 : Some honest leader propose a block, and then this new blockis overridden by the next adversarial block. This subcase happens withprobability βα. As the system state is S1, the average delay for this104D.2. DiemBFTS0 S1 S2 S3a abb babaSxFigure D.2: The state transition of the delay attack on pipelined HotStuff.target block to be committed is E [X1] + 2.Subcase 2 : Some honest leader propose two consecutive block. Thissubcase happens with probability β2. As the system state is S3, theaverage delay for this target block to be committed is E [X3] + 2.D.2 DiemBFTBy following a similar analysis of pipelined HotStuff, we first can showthe state transitions for the system to enter the next state Sx in Fig. D.2.Furthermore, we can compute the expected rounds for a state Si (i ∈{0, 1, 2, 3}) to first enter state Sx and have the following equation.E [X0] = αE [X0] + βE [X1] + 1E [X1] = αE [X0] + βE [X2] + 1E [X2] = αE [X0] + βE [X3] + 1E [X3] = αE [X0] + 1(D.2)By solving the equation (D.2), we can get:E [X0] =β3 + β2 + β + 1β4, E [X1] =β2 + β + 1β4,E [X2] =β + 1β4, E [X3] =1β4Next, we can track honest blocks kept in the main chain and their as-sociated delay. According to its predecessor blocks structure, we can dividehonest blocks into two cases as followings.− Case a: S0β−→ S1 and S1β−→ S2. By the delay attack strategies inSec. 5.3.2, the honest block will always be kept in the main chain. Further,as the current system state is S1, the delay for the honest block to becommitted is E [X1].105D.2. DiemBFTS0 S1 S2a abbabSxFigure D.3: The state transition of the delay attack on pipelined HotStuff.− Case b: S2β−→ S3 and S3β−→ S4. This state transition denotes that anhonest block together with its predecessor blocks can only form threeconsecutive blocks. According to the subsequent leaders (and blocks),the delay for this target block can be divided into two subcases:Subcase 1 : Some honest leader propose a block, and then the subsequentadversarial leader hides the QC and proposes no block. This subcasehappens with probability βα. As the system state is S0, the averagedelay for this target block to be committed is E [X0] + 2.Subcase 2 : Some honest leader propose two consecutive block. Thissubcase happens with probability β2. As the system state is S3, theaverage delay for this target block to be committed is E [X3] + 2.Broadcasting QCBy following the previous analysis, we first can show the state transitionsfor the system to enter the next state Sx in Fig. D.3. Furthermore, we cancompute the expected rounds for a state Si (i ∈ {0, 1, 2, 3}) to first enterstate Sx, and have the following equation.E [X0] = αE [X0] + βE [X1] + 1E [X1] = αE [X0] + βE [X2] + 1E [X2] = αE [X0] + 1(D.3)By solving the equation (D.3), we can get:E [X0] =β2 + β + 1β3, E [X1] =β + 1β3, E [X2] =1β3.Next, we can track honest blocks kept in the main chain and their associateddelay. Note that all honest blocks will be kept in the main chain by the delayattack strategies in pipelined HotStuff with broadcasting QCs. Furthermore,as the system state is S1, the delay for the honest block to be committed isE [X1].106
Thesis/Dissertation
eng
Electrical Engineering
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Feng, Chen
On the security and performance of next-generation blockchains
Text