{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T17:03:10Z","timestamp":1773766990552,"version":"3.50.1"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,23]],"date-time":"2021-10-23T00:00:00Z","timestamp":1634947200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,23]],"date-time":"2021-10-23T00:00:00Z","timestamp":1634947200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Many blockchain-based algorithms, such as Bitcoin, implement a decentralized asset transfer system, often referred to as a cryptocurrency. As stated in the original paper by Nakamoto, at the heart of these systems lies the problem of preventing double-spending; this is usually solved by achieving consensus on the order of transfers among the participants. In this paper, we treat the asset transfer problem as a concurrent object and determine its consensus number, showing that consensus is, in fact, not necessary to prevent double-spending. We first consider the problem as defined by Nakamoto, where only a single process\u2014the account owner\u2014can withdraw from each account. Safety and liveness need to be ensured for correct account owners, whereas misbehaving account owners might be unable to perform transfers. We show that the consensus number of an asset transfer object is 1. We then consider a more general <jats:italic>k<\/jats:italic>-shared asset transfer object where up to <jats:italic>k<\/jats:italic> processes can atomically withdraw from the same account, and show that this object has consensus number <jats:italic>k<\/jats:italic>. We establish our results in the context of shared memory with benign faults, allowing us to properly understand the level of difficulty of the asset transfer problem. We also translate these results in the message passing setting with Byzantine players, a model that is more relevant in practice. In this model, we describe an asynchronous Byzantine fault-tolerant asset transfer implementation that is both simpler and more efficient than state-of-the-art consensus-based solutions. Our results are applicable to both the permissioned (private) and permissionless (public) setting, as normally their differentiation is hidden by the abstractions on top of which our algorithms are based.<\/jats:p>","DOI":"10.1007\/s00446-021-00399-2","type":"journal-article","created":{"date-parts":[[2021,10,23]],"date-time":"2021-10-23T09:02:43Z","timestamp":1634979763000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["The consensus number of a cryptocurrency"],"prefix":"10.1007","volume":"35","author":[{"given":"Rachid","family":"Guerraoui","sequence":"first","affiliation":[]},{"given":"Petr","family":"Kuznetsov","sequence":"additional","affiliation":[]},{"given":"Matteo","family":"Monti","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5147-3890","authenticated-orcid":false,"given":"Matej","family":"Pavlovic","sequence":"additional","affiliation":[]},{"given":"Dragos-Adrian","family":"Seredinschi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,23]]},"reference":[{"key":"399_CR1","unstructured":"Abraham, I., Gueta, G., Malkhi, D., Alvisi, L., Kotla, R., Martin, J.P.: Revisiting fast practical byzantine fault tolerance (2017). arXiv:1712.01367"},{"key":"399_CR2","unstructured":"Abraham, I., Malkhi, D., Nayak, K., Ren, L., Spiegelman, A.: Solida: a blockchain protocol based on reconfigurable byzantine consensus (2016). arXiv:1612.02916"},{"issue":"4","key":"399_CR3","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1145\/153724.153741","volume":"40","author":"Y Afek","year":"1993","unstructured":"Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. JACM 40(4), 873\u2013890 (1993)","journal-title":"JACM"},{"key":"399_CR4","doi-asserted-by":"publisher","unstructured":"Androulaki, E., Barger, A., Bortnikov, V., Cachin, C., Christidis, K., De\u00a0Caro, A., Enyeart, D., Ferris, C., Laventman, G., Manevich, Y., Muralidharan, S., Murthy, C., Nguyen, B., Sethi, M., Singh, G., Smith, K., Sorniotti, A., Stathakopoulou, C., Vukoli\u0107, M., Cocco, S.W., Yellick, J.: Hyperledger fabric: A distributed operating system for permissioned blockchains. In: Proceedings of the Thirteenth EuroSys Conference, EuroSys \u201918, pp. 30:1\u201330:15. ACM, New York (2018). https:\/\/doi.org\/10.1145\/3190508.3190538","DOI":"10.1145\/3190508.3190538"},{"key":"399_CR5","doi-asserted-by":"publisher","unstructured":"Antoniadis, K., Guerraoui, R., Malkhi, D., Seredinschi, D.A.: State machine replication is more expensive than consensus. In: Schmid, U., Widder, J. (eds.) 32nd International Symposium on Distributed Computing (DISC 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 121, pp. 7:1\u20137:18. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl (2018). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.7. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/9796","DOI":"10.4230\/LIPIcs.DISC.2018.7"},{"issue":"2","key":"399_CR6","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/176575.176576","volume":"12","author":"H Attiya","year":"1994","unstructured":"Attiya, H., Welch, J.L.: Sequential consistency versus linearizability. ACM TOCS 12(2), 91\u2013122 (1994)","journal-title":"ACM TOCS"},{"key":"399_CR7","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/978-3-662-53357-4_10","volume-title":"Financial Cryptography and Data Security","author":"I Bentov","year":"2016","unstructured":"Bentov, I., Gabizon, A., Mizrahi, A.: Cryptocurrencies without proof of work. In: Clark, J., Meiklejohn, S., Ryan, P.Y., Wallach, D., Brenner, M., Rohloff, K. (eds.) Financial Cryptography and Data Security, pp. 142\u2013157. Springer, Berlin (2016)"},{"key":"399_CR8","doi-asserted-by":"publisher","unstructured":"Berman, P., Garay, J.A., Perry, K.J.: Towards optimal distributed consensus. In: 30th Annual Symposium on Foundations of Computer Science (FOCS), pp. 410\u2013415. IEEE, Research Triangle Park (1989). https:\/\/doi.org\/10.1109\/SFCS.1989.63511","DOI":"10.1109\/SFCS.1989.63511"},{"key":"399_CR9","doi-asserted-by":"crossref","unstructured":"Bonneau, J., Miller, A., Clark, J., Narayanan, A., Kroll, J.A., Felten, E.W.: SoK: research perspectives and challenges for bitcoin and cryptocurrencies (2015)","DOI":"10.1109\/SP.2015.14"},{"issue":"4","key":"399_CR10","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1145\/4221.214134","volume":"32","author":"G Bracha","year":"1985","unstructured":"Bracha, G., Toueg, S.: Asynchronous consensus and broadcast protocols. JACM 32(4), 824\u2013840 (1985). https:\/\/doi.org\/10.1145\/4221.214134","journal-title":"JACM"},{"key":"399_CR11","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1007\/3-540-44647-8_31","volume-title":"Advances in Cryptology\u2014CRYPTO 2001","author":"C Cachin","year":"2001","unstructured":"Cachin, C., Kursawe, K., Petzold, F., Shoup, V.: Secure and efficient asynchronous broadcast protocols. In: Kilian, J. (ed.) Advances in Cryptology\u2014CRYPTO 2001, pp. 524\u2013541. Springer, Berlin (2001)"},{"key":"399_CR12","doi-asserted-by":"crossref","unstructured":"Cachin, C., Vukoli\u0107, M.: Blockchains consensus protocols in the wild (2017). arXiv:1707.01873","DOI":"10.1109\/EDCC.2017.36"},{"issue":"4","key":"399_CR13","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1145\/571637.571640","volume":"20","author":"M Castro","year":"2002","unstructured":"Castro, M., Liskov, B.: Practical byzantine fault tolerance and proactive recovery. ACM Trans. Comput. Syst. 20(4), 398\u2013461 (2002). https:\/\/doi.org\/10.1145\/571637.571640","journal-title":"ACM Trans. Comput. Syst."},{"key":"399_CR14","unstructured":"Churyumov, A.: Byteball: a decentralized system for storage and transfer of value (2016). https:\/\/byteball.org\/Byteball.pdf"},{"key":"399_CR15","unstructured":"Clement, A., Wong, E.L., Alvisi, L., Dahlin, M., Marchetti, M.: Making byzantine fault tolerant systems tolerate byzantine faults. In: NSDI, pp. 153\u2013168. USENIX Association, Berkeley (2009)"},{"key":"399_CR16","doi-asserted-by":"publisher","unstructured":"Collins, D., Guerraoui, R., Komatovic, J., Kuznetsov, P., Monti, M., Pavlovic, M., Pignolet, Y., Seredinschi, D., Tonkikh, A., Xygkis, A.: Online payments by merely broadcasting messages. In: 2020 50th Annual IEEE\/IFIP International Conference on Dependable Systems and Networks (DSN), pp. 26\u201338 (2020). https:\/\/doi.org\/10.1109\/DSN48063.2020.00023","DOI":"10.1109\/DSN48063.2020.00023"},{"key":"399_CR17","doi-asserted-by":"publisher","unstructured":"Decker, C., Seidel, J., Wattenhofer, R.: Bitcoin meets strong consistency. In: Proceedings of the 17th International Conference on Distributed Computing and Networking, ICDCN \u201916, pp. 13:1\u201313:10. ACM, New York (2016). https:\/\/doi.org\/10.1145\/2833312.2833321","DOI":"10.1145\/2833312.2833321"},{"key":"399_CR18","doi-asserted-by":"publisher","unstructured":"Duan, S., Reiter, M.K., Zhang, H.: Beat: asynchronous BFT made practical. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS \u201918, pp. 2028\u20132041. ACM, New York (2018). https:\/\/doi.org\/10.1145\/3243734.3243812","DOI":"10.1145\/3243734.3243812"},{"key":"399_CR19","unstructured":"Eyal, I., Gencer, A.E., Sirer, E.G., Van\u00a0Renesse, R.: Bitcoin-NG: a scalable blockchain protocol (2016)"},{"key":"399_CR20","unstructured":"Fidge, J.C.: Timestamps in message-passing systems that preserve partial ordering. In: Proceedings of the 11th Australian Computer Science Conference, vol. 10(1), pp. 56\u201366 (1988)"},{"issue":"2","key":"399_CR21","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"MJ Fischer","year":"1985","unstructured":"Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. JACM 32(2), 374\u2013382 (1985)","journal-title":"JACM"},{"key":"399_CR22","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/978-3-662-46803-6_10","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2015","author":"J Garay","year":"2015","unstructured":"Garay, J., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: analysis and applications. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology\u2014EUROCRYPT 2015, pp. 281\u2013310. Springer, Berlin (2015)"},{"key":"399_CR23","doi-asserted-by":"publisher","unstructured":"Garay, J.A., Katz, J., Kumaresan, R., Zhou, H.S.: Adaptively secure broadcast, revisited. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC \u201911, pp. 179\u2013186. ACM, New York, NY, USA (2011). https:\/\/doi.org\/10.1145\/1993806.1993832","DOI":"10.1145\/1993806.1993832"},{"key":"399_CR24","doi-asserted-by":"publisher","unstructured":"Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: scaling byzantine agreements for cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles, SOSP \u201917, pp. 51\u201368. ACM, New York (2017). https:\/\/doi.org\/10.1145\/3132747.3132757","DOI":"10.1145\/3132747.3132757"},{"key":"399_CR25","unstructured":"Guerraoui, R., Pavlovic, M., Seredinschi, D.A.: Blockchain protocols: the adversary is in the details. In: Symposium on Foundations and Applications of Blockchain (2018). https:\/\/scfab.github.io\/2018\/assets\/papers\/fab18_submission_04.pdf"},{"key":"399_CR26","unstructured":"Gupta, S.: A non-consensus based decentralized financial transaction processing model with support for efficient auditing. Master\u2019s thesis, Arizona State University, USA (2016)"},{"key":"399_CR27","first-page":"97","volume-title":"Distributed Systems, Chap.\u00a05","author":"V Hadzilacos","year":"1993","unstructured":"Hadzilacos, V., Toueg, S.: Fault-tolerant broadcasts and related problems. In: Mullender, S.J. (ed.) Distributed Systems, Chap.\u00a05, pp. 97\u2013145. Addison-Wesley, Reading (1993)"},{"key":"399_CR28","unstructured":"Hearn, M.: Corda: a distributed ledger. Corda Technical White Paper (2016)"},{"issue":"1","key":"399_CR29","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1145\/114005.102808","volume":"13","author":"M Herlihy","year":"1991","unstructured":"Herlihy, M.: Wait-free synchronization. TOPLAS 13(1), 123\u2013149 (1991)","journal-title":"TOPLAS"},{"issue":"3","key":"399_CR30","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"MP Herlihy","year":"1990","unstructured":"Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463\u2013492 (1990). https:\/\/doi.org\/10.1145\/78969.78972","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"399_CR31","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/3-540-56188-9_5","volume-title":"Distributed Algorithms","author":"P Jayanti","year":"1992","unstructured":"Jayanti, P., Toueg, S.: Some results on the impossibility, universality, and decidability of consensus. In: Segall, A., Zaks, S. (eds.) Distributed Algorithms, pp. 69\u201384. Springer, Berlin (1992)"},{"key":"399_CR32","doi-asserted-by":"publisher","unstructured":"Karlsson, K., Jiang, W., Wicker, S., Adams, D., Ma, E., van Renesse, R., Weatherspoon, H.: A Partition-Tolerant Blockchain for the Internet-of-Things. In: 38th IEEE International Conference on Distributed Computing Systems, ICDCS 2018, Vienna, Austria, IEEE Computer Society, pp. 1150\u20131158. https:\/\/doi.org\/10.1109\/ICDCS.2018.00114, https:\/\/dblp.org\/rec\/conf\/icdcs\/KarlssonJWAMRW18.bib","DOI":"10.1109\/ICDCS.2018.00114"},{"key":"399_CR33","unstructured":"Kogias, E.K., Jovanovic, P., Gailly, N., Khoffi, I., Gasser, L., Ford, B.: Enhancing bitcoin security and performance with strong consistency via collective signing. USENIX Security (2016)"},{"key":"399_CR34","doi-asserted-by":"crossref","unstructured":"Kokoris-Kogias, E., Jovanovic, P., Gasser, L., Gailly, N., Syta, E., Ford, B.: OmniLedger: Asecure, Scale-Out, Decentralized Ledger via Sharding IEEE. Symp. Secur. Priv. 583\u2013598 (2018)","DOI":"10.1109\/SP.2018.000-5"},{"key":"399_CR35","unstructured":"LeMahieu, C.: Nano: a feeless distributed cryptocurrency network. Nano. https:\/\/nano.org\/en\/whitepaper (2018). Accessed 18 Jan 2019"},{"key":"399_CR36","doi-asserted-by":"crossref","unstructured":"Malkhi, D., Merritt, M., Rodeh, O.: Secure reliable multicast protocols in a WAN. In: ICDCS (1997)","DOI":"10.3233\/JCS-1997-5203"},{"issue":"2","key":"399_CR37","doi-asserted-by":"publisher","first-page":"113","DOI":"10.3233\/JCS-1997-5203","volume":"5","author":"D Malkhi","year":"1997","unstructured":"Malkhi, D., Reiter, M.K.: A high-throughput secure reliable multicast protocol. J. Comput. Secur. 5(2), 113\u2013128 (1997). https:\/\/doi.org\/10.3233\/JCS-1997-5203","journal-title":"J. Comput. Secur."},{"key":"399_CR38","unstructured":"Mazieres, D.: The stellar consensus protocol: a federated model for internet-level consensus. Stellar Development Foundation (2015)"},{"key":"399_CR39","unstructured":"Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008)"},{"issue":"2","key":"399_CR40","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s004460100061","volume":"15","author":"F Pedone","year":"2002","unstructured":"Pedone, F., Schiper, A.: Handling message semantics with generic broadcast protocols. Distrib. Comput. 15(2), 97\u2013107 (2002)","journal-title":"Distrib. Comput."},{"key":"399_CR41","unstructured":"Rapoport, P., Leal, R., Griffin, P., Sculley, W.: The ripple protocol (2014)"},{"key":"399_CR42","unstructured":"Sompolinsky, Y., Zohar, A.: Accelerating Bitcoin\u2019s transaction processing: fast money grows on trees, not chains. IACR Cryptology ePrint Archive 881 (2013)"},{"key":"399_CR43","doi-asserted-by":"crossref","unstructured":"Sousa, J., Bessani, A., Vukolic, M.: A byzantine fault-tolerant ordering service for the hyperledger fabric blockchain platform. In: IEEE DSN (2018)","DOI":"10.1109\/DSN.2018.00018"},{"key":"399_CR44","doi-asserted-by":"crossref","unstructured":"Szabo, N.: Formalizing and securing relationships on public networks. First Monday 2(9) (1997)","DOI":"10.5210\/fm.v2i9.548"},{"key":"399_CR45","unstructured":"Team-Rocket: Snowflake to avalanche: a novel metastable consensus protocol family for cryptocurrencies. White Paper (2018). Revision: 05\/16\/2018 21:51:26 UTC"},{"key":"399_CR46","doi-asserted-by":"publisher","unstructured":"Toueg, S.: Randomized byzantine agreements. In: Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, PODC \u201984, pp. 163\u2013178. ACM, New York (1984). https:\/\/doi.org\/10.1145\/800222.806744","DOI":"10.1145\/800222.806744"},{"key":"399_CR47","doi-asserted-by":"crossref","unstructured":"Vukoli\u0107, M.: The quest for scalable blockchain fabric: proof-of-work vs. BFT replication. In: International Workshop on Open Problems in Network Security (2015)","DOI":"10.1007\/978-3-319-39028-4_9"},{"key":"399_CR48","unstructured":"Wood, G.: Ethereum: a secure decentralized generalized transaction ledger. White paper (2015)"}],"updated-by":[{"DOI":"10.1007\/s00446-022-00422-0","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T00:00:00Z","timestamp":1645574400000}}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00399-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-021-00399-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00399-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,27]],"date-time":"2022-02-27T08:03:54Z","timestamp":1645949034000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-021-00399-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,23]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["399"],"URL":"https:\/\/doi.org\/10.1007\/s00446-021-00399-2","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s00446-022-00422-0","asserted-by":"object"}]},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,23]]},"assertion":[{"value":"10 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 October 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2022","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00446-022-00422-0","URL":"https:\/\/doi.org\/10.1007\/s00446-022-00422-0","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}