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)
- 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
-
CC BY