Abstract
We propose Meshcash, a protocol for implementing a permissionless ledger (blockchain) via proofs of work, suitable for use as the underlying consensus mechanism of a cryptocurrency. Unlike most existing proof-of-work based consensus protocols, Meshcash does not rely on leader-election (e.g., the single miner who managed to extend the longest chain). Rather, we use ideas from traditional (permissioned) Byzantine agreement protocols in a novel way to guarantee convergence to a consensus from any starting state. Our construction combines a local “hare” protocol that guarantees fast consensus on recent blocks (but doesn’t, by itself, imply irreversibility) with a global “tortoise” protocol that guarantees irreversibility. Our global protocol also allows the ledger to “self-heal” from arbitrary violations of the security assumptions, reconverging to consensus after the assumptions hold again.
Meshcash is designed to be race-free: there is no “race” to generate the next block and honestly-generated blocks are always rewarded. This property, which we define formally as a game-theoretic notion, turns out to be useful in analyzing rational miners’ behavior: we prove (using a generalization of the blockchain mining games of Kiayias et al.) that race-free blockchain protocols are incentive-compatible and satisfy linearity of rewards (i.e., a party receives rewards proportional to its computational power). Because Meshcash can tolerate a high block rate regardless of network propagation delays (which will only affect latency), it allows us to lower both the variance and the expected time between blocks for honest miners; together with linearity of rewards, this makes pooled mining far less attractive. Moreover, race-free protocols scale more easily (in terms of transaction rate). This is because the race-free property implies that the network propagation delays are not a factor in terms of rewards, which removes the main impediment to accommodating a larger volume of transactions.
We formally prove that all of our guarantees hold in the bounded-delay communication model of Pass, Seeman and shelat, and against a constant fraction of Byzantine (malicious) miners; not just rational ones.
A full version of this paper is available as [4]
P. Hubáček—This work was performed while at the Foundations and Applications of Cryptographic Theory (FACT) center, IDC Herzliya, Israel
T. Moran—This work was supported in part by the Bar-Ilan Cyber Center
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
For optimization purposes, a cryptocurrency built on top of the ledger can add additional restrictions to prevent clearly invalid transactions from entering the ledger in the first place, but we ignore that here.
- 2.
The code can be found on https://github.com/anon444/meshcash.git.
References
Andrychowicz, M., Dziembowski, S.: Pow-based distributed cryptography with no trusted setup. In: Gennaro, R., Robshaw, M. (eds.) Advances in Cryptology - CRYPTO 2015–35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16–20, 2015, Proceedings, Part II, volume 9216 of Lecture Notes in Computer Science, pp. 379–399. Springer (2015). https://doi.org/10.1007/978-3-662-48000-7_19
Babaioff, M., Dobzinski, S., Oren, S., Zohar, A.: On Bitcoin and red balloons. In: ACM Conference on Electronic Commerce, pp. 56–73 (2012)
Barak, B., Canetti, R., Lindell, Y., Pass, R., Rabin, T.: Secure computation without authentication. In: CRYPTO, Yehuda Lindell (2005)
Bentov, I., Hubáček, P., Moran, T., Nadler, A.: Tortoise and hares consensus: the meshcash framework for incentive-compatible, scalable cryptocurrencies. Cryptology ePrint Archive, Report 2017/300 (2017). https://eprint.iacr.org/2017/300
Carlsten, M., Kalodner, H., Weinberg, S.M., Narayanan, A.: On the instability of bitcoin without the block reward. In: ACM CCS, pp. 154–167 (2016)
Croman, K.: On scaling decentralized blockchains. In: Financial Cryptography 3rd Bitcoin Workshop (2016)
Eyal, I.: The miner’s dilemma. In: IEEE S&P (2015)
Eyal, I.: Gencer, A.E., Sirer, E.G., van Renesse, R.: A scalable blockchain protocol. In: NSDI, Bitcoin-NG (2016)
Eyal, I., Sirer, E.: Majority is not enough: Bitcoin mining is vulnerable. In: Financial Cryptography (2014)
Garay, J., Kiayias, A., Leonardos, N.: The Bitcoin backbone protocol: analysis and applications. In: Eurocrypt (2015). http://eprint.iacr.org/2014/765
Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: scaling byzantine agreements for cryptocurrencies. In: SOSP, pp. 51–68. ACM (2017). https://eprint.iacr.org/2017/454
Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: a provably secure proof-of-stake blockchain protocol. In: Katz, J., Shacham, H. (eds.) Advances in Cryptology - CRYPTO 2017–37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20–24, 2017, Proceedings, Part I, volume 10401 of Lecture Notes in Computer Science, pp. 357–388. Springer (2017)
Kiffer, L., Rajaraman, R., Shelat, A.: A better method to analyze blockchain consistency. In: ACM CCS 2018 (2018)
Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. Prog. Lang. Syst. 4(3), 382–401 (1982)
Lewenberg, Y., Sompolinsky, Y., Zohar, A.: Inclusive block chain protocols. In: Financial Cryptography and Data Security, pp. 528–547 (2015)
Liao, K., Katz, J.: Incentivizing double-spend collusion in Bitcoin. In: Financial Cryptography Bitcoin Workshop (2017)
Luu, L., Teutsch, J., Kulkarni, R., Saxena, P.: Demystifying incentives in the consensus computer. In: 22nd ACM CCS (2015)
Maxwell, G.: (2015). https://bitcointalk.org/index.php?topic=1108304.msg11786046#msg11786046
Miller, A., Kosba, A.E., Katz, J., Shi, E.: Nonoutsourceable scratch-off puzzles to discourage Bitcoin mining coalitions. In: 22nd ACM CCS (2015)
Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system. Bitcoin.org (2008). http://www.bitcoin.org/bitcoin.pdf
Pass, R., Seeman, L., Shelat, A.: Analysis of the blockchain protocol in asynchronous networks. In: Eurocrypt 2017 (2017). http://eprint.iacr.org/2016/454
“Maged” (pseudonym). Re: Unfreezable blockchain (2012). URL: https://bitcointalk.org/index.php?topic=57647.msg686497#msg686497
Sapirshtein, A., Sompolinsky, Y., Zohar, A.: Optimal selfish mining strategies in Bitcoin. In: Financial Cryptography (2016)
Sompolinsky, Y., Lewenberg, Y., Zohar, Spectre, A.: A fast and scalable cryptocurrency protocol (2016). https://eprint.iacr.org/2016/1159
Sompolinsky, Y., Zohar, A.: Secure high-rate transaction processing in Bitcoin. In: 19th Financial Cryptography and Data Security (2015)
Sompolinsky, Y., Zohar, A.: PHANTOM: a scalable blockdag protocol. IACR Cryptology ePrint Archive, 2018:104 (2018). http://eprint.iacr.org/2018/104
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Bentov, I., Hubáček, P., Moran, T., Nadler, A. (2021). Tortoise and Hares Consensus: The Meshcash Framework for Incentive-Compatible, Scalable Cryptocurrencies. In: Dolev, S., Margalit, O., Pinkas, B., Schwarzmann, A. (eds) Cyber Security Cryptography and Machine Learning. CSCML 2021. Lecture Notes in Computer Science(), vol 12716. Springer, Cham. https://doi.org/10.1007/978-3-030-78086-9_9
Download citation
DOI: https://doi.org/10.1007/978-3-030-78086-9_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-78085-2
Online ISBN: 978-3-030-78086-9
eBook Packages: Computer ScienceComputer Science (R0)