You are looking at a specific version 20190717:072106 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. MINOR revision.
Keywords
Blockchainbitcoindistributed ledger technologydouble spending
Contact author(s)
zvi @ zvi net
History
2020-02-06: last of 3 revisions
2019-07-17: received
See all versions
Short URL
https://ia.cr/2019/827
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.