Cryptology ePrint Archive: Report 2019/827

k-root-n: An efficient O(√n) algorithm for avoiding short term double spending in Distributed Ledger Technologies such as Blockchain

Zvi Schreiber

Abstract: Blockchains such as bitcoin rely on reaching global consensus for the distributed ledger, and suffer from a well know scalability problem. We propose an algorithm which can avoid double spending in the short term with just $O(\sqrt{n})$ messages, relying on the fact that the velocity of money in the real world has coins generally circulating through at most a few wallets per day. The algorithm should be practical to avoid double spending with arbitrarily high probability, while feasibly coping with all the commerce in the world. This k-root-n algorithm is less effective in the long term once money circulates through a significant proportion of the world’s wallets, and should therefore be used as a complement to a global consensus. Thus, global consensus can be reached periodically and with a considerable lag, while money can be safely spent with quick transactions in-between.

Category / Keywords: applications / Blockchain, bitcoin, distributed ledger technology, double spending

Date: received 17 Jul 2019

Contact author: zvi at zvi net

Available format(s): PDF | BibTeX Citation

Version: 20190717:072106 (All versions of this report)

Short URL: ia.cr/2019/827


[ Cryptology ePrint archive ]