SCIENCE CHINA Information Sciences, Volume 63 , Issue 3 : 130105(2020) https://doi.org/10.1007/s11432-019-2698-1

Analysis of bitcoin backbone protocol in the non-flat model

Peifang NI 1,2,3, Hongda LI 1,2,3,*, Dongxue PAN 1,2,3
More info
  • ReceivedJun 15, 2019
  • AcceptedOct 30, 2019
  • PublishedFeb 11, 2020



This work was supported by National Key RD Program of China (Grant No. 2017YFB0802500) and Beijing Municipal Science and Technology Project (Grant No. Z191100007119007).


Appendix A.


[1] Nakamoto S. Bitcoin: a peer-to-peer electronic cash system. 2008. Google Scholar

[2] Dwork C, Naor M. Pricing via processing or combatting junk mail. In: Advances in Cryptology - CRYPTO'92. 1993. 139--147. Google Scholar

[3] Rivest R L. Time-lock puzzles and timed-release Crypto. 2001. Google Scholar

[4] Garay J, Kiayias A, Leonardos N. The bitcoin backbone protocol: analysis and applications. In: Advances in Cryptology - EUROCRYPT 2015. Berlin: Springer, 2015. 281--310. Google Scholar

[5] Pass R, Seeman L, Shelat A. Analysis of the Blockchain Protocol in Asynchronous Networks. In: Advances in Cryptology - EUROCRYPT. Berlin: Springer, 2017. 643--673. Google Scholar

[6] Garay J, Kiayias A, Leonardos N. The bitcoin backbone protocol with chains of variable difficulty. In: Advances in Cryptology - CRYPTO 2017. Berlin: Springer, 2017. 291--323. Google Scholar

[7] Ratnasamy S, Francis P, Handley M. A scalable content-addressable network. SIGCOMM Comput Commun Rev, 2001, 31: 161-172 CrossRef Google Scholar

[8] Druschel P, Rowstron A. Past: persistent and anonymous storage in a peer-to-peer networking environment. In: Proceedings of IEEE Workshop on Hot Topics in Operating Systems, 2001. 65--70. Google Scholar

[9] Castro M, Liskov B. Practical byzantine fault tolerance and proactive recovery. ACM Trans Comput Syst, 2002, 20: 398-461 CrossRef Google Scholar

[10] Abd-El-Malek M, Ganger G R, Goodson G R. Fault-scalable Byzantine fault-tolerant services. SIGOPS Oper Syst Rev, 2005, 39: 59-74 CrossRef Google Scholar

[11] Clement A, Wong E L, Alvisi L, et al. Making byzantine fault tolerant systems tolerate byzantine faults. In: Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, Boston, 2009. 153--168. Google Scholar

[12] Decker C, Wattenhofer R. Information propagation in the Bitcoin network. In: Proceedings of International Conference on Peer-To-Peer Computing, 2013. 1--10. Google Scholar

[13] Sompolinsky Y, Zohar A. Secure high-rate transaction processing in bitcoin. In: Financial Cryptography and Data Security. Berlin: Springer, 2015. 507--527. Google Scholar

[14] Wei P, Yuan Q, Zheng Y, et al. Security of the blockchain against long delay attack. In: Advances in Cryptology - ASIACRYPT 2018. Berlin: Springer, 2018. 250--275. Google Scholar

[15] Tsabary I, Eyal I. The gap game. In: Proceedings of ACM International Conference on Systems and Storage, 2018. 132--132. Google Scholar

[16] Eyal I, Sirer E G. Majority is not enough: bitcoin mining is vulnerable. Communications of The ACM, 2018, 61: 95-102. Google Scholar

[17] Sarkar P. Multi-stage proof-of-work blockchain. IACR Cryptology ePrint Archive, 2019, 2019: 162. Google Scholar

[18] Szalachowski P, Reijsbergen D, Homoliak I, et al. StrongChain: transparent and collaborative proof-of-work consensus. 2019,. arXiv Google Scholar

[19] David B, Peter Gavzi, Kiayias A, et al. Ouroboros praos: an adaptively-secure, semi-synchronous proof-of-stake blockchain. In: Proceedings of International Conference on the Theory & Applications of Cryptographic Techniques. Berlin: Springer, 2018. 66--98. Google Scholar

[20] Badertscher C, Gazi P, Kiayias A, et al. Ouroboros genesis: composable proof-of-stake blockchains with dynamic availability. In: Proceedings of Computer and Communications Security, 2018. 913--930. Google Scholar

[21] Chaum D, Rivest R L, Sherman A T. Blind signatures for untraceable payments. In: Advances in Cryptology. Berlin: Springer, 1983. 199--203. Google Scholar

[22] Baldimtsi F, Chase M, Fuchsbauer G, et al. Anonymous transferable e-cash. In: Public-Key Cryptography -- PKC 2015. Berlin: Springer, 2015. 101--124. Google Scholar

[23] Tewari H, Hughes A. Fully anonymous transferable ecash. IACR Cryptol ePrint Archive, 2016, 2016: 107. Google Scholar

[24] Canard S, Pointcheval D, Sanders O. Divisible e-cash made practical. 9020 CrossRef Google Scholar

[25] Miers I, Garman C, Green M, et al. Zerocoin: anonymous distributed e-cash from bitcoin. In: Proceedings of 2013 IEEE Symposium on Security and Privacy, 2013. 397--411. Google Scholar

[26] Sasson E B, Chiesa A, Garman C, et al. Zerocash: decentralized anonymous payments from bitcoin. In: Proceedings of 2014 IEEE Symposium on Security and Privacy (SP), 2014. 459--474. Google Scholar

[27] Canetti R. Security and Composition of Multiparty Cryptographic Protocols. J Cryptology, 2000, 13: 143-202 CrossRef Google Scholar

[28] Canetti R. Universal composable security: a new paradigm for cryptographic protocols. In: Proceedings of IEEE Symposium on Foundations of Computer Science, 2001. Google Scholar

[29] Kiayias A, Panagiotakos G. Speed-Security Tradeoffs in Blockchain Protocols. 2015. Google Scholar

  • Table 1   The parameters and symbols used in our analysis$^{\rm~a)}$
    $k$Security parameter
    $\lambda$The proportion of honest parties in number
    $\lambda'$The proportion of honest parties in the amount of computational power
    $\delta$The advantage of honest parties, ($\lambda'>\frac{1}{1-\delta}$)
    $(\Delta,s)$Determines how the amount of computational power fluctuates across rounds
    $\varepsilon$Determines the amount of computational power in a valid block
    $\varphi$The distance between variable and expectation in standard execution
    $K'$The number of consecutive blocks for recalculating difficult target
    $t$The number of consecutive rounds for chain-growth property
    $l$The number of consecutive blocks for chain-quality property
    $K$The number of consecutive blocks for common-prefix property


  • Table 2   The execution environments of analytical models
    Environment Ref. [4]Ref. [5] Ref. [6]Ours
    Permissionless setting No No YesNo
    Asynchronous network No Yes NoNo
    Non-flat parties No NoNoYes
    AssumptionsHMA and SA HMA and SAHMA and SAHMA
  • Table 3   The comparison of results between and ours
    Parameter Ref. [4] Ours
    HPoHP $\alpha''~=~\frac{q(n-t)}{1+pq(n-t)}$$\alpha\geq\frac{q(n-t)}{1+pc'}$
    HPoA $\beta''=qt$ $\beta=qt$
    CGR $g'=(1-\varphi)\alpha''$ $g=(1-\varphi)\alpha$
    CQ $\mu'=(1+\frac{\delta}{2})\frac{t}{n-t}$ $\mu=(1-\delta)\frac{t}{n-t}$