{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T04:28:12Z","timestamp":1772252892433,"version":"3.50.1"},"reference-count":38,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T00:00:00Z","timestamp":1581033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>Blockchains such as the bitcoin blockchain depend on reaching a global consensus on the distributed ledger; therefore, they suffer from well-known scalability problems. This paper proposes an algorithm that avoids double-spending in the short term with just O(\u221an) messages instead of O(n); each node receiving money off-chain performs the due diligence of consulting k\u221an random nodes to check if any of them is aware of double-spending. Two nodes receiving double-spent money will in this way consult at least one common node with very high probability, because of the \u2018birthday paradox\u2019, and any common honest node consulted will detect the fraud. Since the velocity of money in the real world has coins circulating through at most a few wallets per day, the size of the due diligence communication is small in the short term. This \u2018k-root-n\u2019 algorithm is suitable for an environment with synchronous or asynchronous (but with fairly low latency) communication and with Byzantine faults. The presented k-root-n algorithm should be practical to avoid double-spending with arbitrarily high probability, while feasibly coping with the throughput of all world commerce. It is resistant to Sybil attacks even beyond 50% of nodes. In the long term, the k-root-n algorithm is less efficient. Therefore, it should preferably be used as a complement, and not a replacement, to a global distributed ledger technology.<\/jats:p>","DOI":"10.3390\/info11020090","type":"journal-article","created":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T11:50:28Z","timestamp":1581076228000},"page":"90","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["k-Root-n: An Efficient Algorithm for Avoiding Short Term Double-Spending Alongside Distributed Ledger Technologies such as Blockchain"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9832-4315","authenticated-orcid":false,"given":"Zvi","family":"Schreiber","sequence":"first","affiliation":[{"name":"Ex-Imperial College, Cambridge University, London SE16, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,2,7]]},"reference":[{"key":"ref_1","unstructured":"Nakamoto, S. (2020, January 15). Bitcoin: A Peer-to-Peer Electronic Cash System. Available online: https:\/\/bitcoin.org\/bitcoin.pdf."},{"key":"ref_2","unstructured":"Chohan, U. (2020, January 15). Available online: https:\/\/papers.ssrn.com\/sol3\/papers.cfm?abstract_id=3338560."},{"key":"ref_3","unstructured":"(2020, January 15). Scalability. Available online: https:\/\/en.bitcoin.it\/wiki\/Scalability."},{"key":"ref_4","unstructured":"Garzik, J. (2020, January 15). Making Decentralized Economic Policy. Available online: http:\/\/gtf.org\/garzik\/bitcoin\/BIP100-blocksizechangeproposal.pdf."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"801","DOI":"10.1016\/j.joule.2018.04.016","article-title":"Bitcoin\u2019s Growing Energy Problem","volume":"2","author":"Vries","year":"2018","journal-title":"Joule"},{"key":"ref_6","unstructured":"Canneti, R., and Rabin, T. (1992). Optimal Asynchronous Byzantine Agreement, Computer Science Department, Hebrew University. Technical Report #92-15."},{"key":"ref_7","unstructured":"Castro, M., and Liskov, B. (1999, January 22\u201325). Practical Byzantine Fault Tolerance. Proceedings of the Third Symposium on Operating Systems Design and Implementation, New Orleans, LA, USA."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/3-540-45748-8_24","article-title":"The Sybil Attack, Peer-to-Peer Systems","volume":"2429","author":"Douceur","year":"2002","journal-title":"Lect. Notes Comput. Sci."},{"key":"ref_9","unstructured":"Live Bitcoin Transactions (2020, January 15). Blockchain Unconfirmed Transactions. Available online: https:\/\/www.blockchain.com\/btc\/unconfirmed-transactions."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Azzolini, D., Riguzzi, F., and Lamma, E. (2019). Studying Transaction Fees in the Bitcoin Blockchain with Probabilistic Logic Programming. Information, 10.","DOI":"10.3390\/info10110335"},{"key":"ref_11","unstructured":"(2020, January 15). Irreversible Transactions. Available online: https:\/\/en.bitcoin.it\/wiki\/Irreversible_Transactions."},{"key":"ref_12","unstructured":"Luu, L., Narayanan, V., Baweja, K., Zheng, C., Gilbert, S., and Saxena, P. (2016). SCP: A Computationally-Scalable Byzantine Consensus Protocol for Blockchains. IACR Cryptol., 20. Available online: https:\/\/www.weusecoins.com\/assets\/pdf\/library\/SCP."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Gilad, Y., Hemo, R., Micali, S., Vlachos, G., and Zeldovich, N. (2017, January 28\u201331). Algorand: Scaling Byzantine Agreements. Proceedings of the SOSP 17 26th Symposium on Operating Systems Principles, Shanghai, China.","DOI":"10.1145\/3132747.3132757"},{"key":"ref_14","unstructured":"Eyal, I., Gencer, A.E., Sirerr, E.G., and van Renesse, R. (2016, January 16\u201318). Bitcoin-NG: A Scalable Blockchain Protocol. Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16), Santa Clara, CA, USA."},{"key":"ref_15","unstructured":"Apeltsin, L. (2014). A CryptoCubic Protocol for Hacker-Proof Off-Chain Bitcoin Transactions, Cornell University."},{"key":"ref_16","unstructured":"Dryja, J., and Poon, T. (2020, January 15). The Bitcoin Lightning Network: Scalable Off-Chain Instant Payments. Available online: https:\/\/www.bitcoinlightning.com\/wp-content\/uploads\/2018\/03\/lightning-network-paper.pdf."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Chohan, U.W. (2017). The Double Spending Problem and Cryptocurrencies. Bank. Insur. J. Soc. Sci. Res. Netw.","DOI":"10.2139\/ssrn.3090174"},{"key":"ref_18","unstructured":"Heilman, E., Kendler, A., Zohar, A., and Goldberg, S. (2015, January 12\u201314). Eclipse Attacks on Bitcoin\u2019s Peer-to-Peer Network, SEC\u201915. Proceedings of the 24th USENIX Conference on Security Symposium, Washington, DC, USA."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Apostolaki, M., Zohar, A., and Vanbever, L. (2017). Hijacking Bitcoin: Routing Attacks on Cryptocurrencies. IEEE Symp. Secur. Priv.","DOI":"10.1109\/SP.2017.29"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.entcs.2016.12.006","article-title":"Double-spend Attack Models with Time Advantange for Bitcoin","volume":"329","author":"Rocha","year":"2016","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"ref_21","unstructured":"Ittay, E., Peter, G., Aljosha, J., Sarah, M., Nicholas, S., Itay, T., Edgar, W., and Alexei, Z. (2019). Pay-To-Win: Incentive Attacks on Proof-of-Work Cryptocurrencies. IACR Cryptol. ePrint Arch., 775."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"180410","DOI":"10.1098\/rsos.180410","article-title":"Committing to quantum resistance: A slow defence for Bitcoin against a fast quantum computing attack","volume":"5","author":"Stewart","year":"2018","journal-title":"R. Soc. Open Sci."},{"key":"ref_23","first-page":"3487","article-title":"Exploring the Attack Surface of Blockchain: A Systematic Overview","volume":"1904","author":"Saad","year":"2019","journal-title":"arXiv"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2732196","article-title":"Misbehavior in Bitcoin: A Study of Double-Spending and Accountability","volume":"18","author":"Karame","year":"2015","journal-title":"ACM Trans. Inf. Syst. Secur."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s10207-018-0422-4","article-title":"Double-spending prevention for Bitcoin zero-confirmation transactions","volume":"18","year":"2019","journal-title":"Int. J. Inf. Secur."},{"key":"ref_26","first-page":"48","article-title":"Cryptocurrency and Double Spending History: Transactions with Zero Confirmation","volume":"16","author":"Kang","year":"2019","journal-title":"Munich Pers. RePEc Arch."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"G\u00f6bel, J., and Krzesinski, A.E. (2017, January 22\u201324). Increased Block Size and Bitcoin Blockchain Dynamics. Proceedings of the 27th International Telecommunication Networks and Applications Conference (ITNAC), Melbourne, Australia.","DOI":"10.1109\/ATNAC.2017.8215367"},{"key":"ref_28","unstructured":"Ericsson, N.R., Hendry, D.F., and Hood, S.B. (2017). Milton Friedman and Data Adjustment. IFDP Notes, Board of Governors of the Federal Reserve System."},{"key":"ref_29","unstructured":"Ball, W.W.R. (1960). Probability. Mathematical Recreations and Essays, Macmillan."},{"key":"ref_30","unstructured":"UNDESA (2019). The World Population Prospects 2019: Highlights, Population Division of the UN Department of Economic and Social Affairs."},{"key":"ref_31","first-page":"32","article-title":"How Many People Use Bitcoin in 2019?","volume":"643","author":"Lielacher","year":"2019","journal-title":"Bitcoin Mark. J."},{"key":"ref_32","unstructured":"Sedgwick, K. (2020, January 15). Available online: https:\/\/news.bitcoin.com\/no-visa-doesnt-handle-24000-tps-and-neither-does-your-pet-blockchain\/."},{"key":"ref_33","unstructured":"(2020, January 15). Global General Purpose Cards\u2014Midyear 2018, The Nilsen Report. Available online: https:\/\/nilsonreport.com\/upload\/issues\/1140_0321.pdf."},{"key":"ref_34","unstructured":"Skene, J., Lamanna, D.D., and Emmerich, W. (2004, January 28). Precise Service Level Agreements ICSE \u201904. Proceedings of the 26th International Conference on Software Engineering, Edinburgh, UK."},{"key":"ref_35","unstructured":"Lamanna, D., Skene, J., and Emmerich, W. (2003, January 30). SLAng: A Language for Defining. Proceedings of the Ninth IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS), San Juan, PR, USA."},{"key":"ref_36","unstructured":"Fisher, I., and Gunnison Brown, H. (2010). The Purchasing Power of Money, its Determination and Relation to Credit, Interest and Crises, Nabu Press."},{"key":"ref_37","unstructured":"(2020, January 15). Federal Reserve Bank of St. Louis, Velocity of M1 Money Stock, Fred Economic Data, No.2019. Available online: https:\/\/fred.stlouisfed.org\/series\/M1V."},{"key":"ref_38","unstructured":"Bastiaan, M. (2020, January 15). Available online: https:\/\/www.hmbastiaan.nl\/martijn\/docs\/2015\/preventing-the-majority.pdf."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/11\/2\/90\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:55:50Z","timestamp":1760172950000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/11\/2\/90"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,7]]},"references-count":38,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,2]]}},"alternative-id":["info11020090"],"URL":"https:\/\/doi.org\/10.3390\/info11020090","relation":{"has-preprint":[{"id-type":"doi","id":"10.20944\/preprints202001.0059.v1","asserted-by":"object"}]},"ISSN":["2078-2489"],"issn-type":[{"value":"2078-2489","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,7]]}}}