Alternative history attack success probability calculation in blockchain system
Abstract
This article systemizes the information on the subject of the alternative history attack of the blockchain registry. The review and generalization of the information presented in the most respected works in this direction is offered. The analysis of corresponding works on estimation of probability of double spending in the "Proof of Work" consensus protocol is carried out. The problems of the player's ruin are considered and an analogy with the attack of double spending on the blockchain is made. Poisson's experiment for the general case is considered. The models on the basis of which S. Nakamoto and M. Rosenfeld made attempts to get a quantitative estimation of probability of successful double spending attack on some algorithms of consensus having probability completeness are analyzed. Simplifications and assumptions that take place in the respective models with the help of which the final expression is obtained are given.
Downloads
References
Nakamoto S. Bitcoin: A Peer-to-Peer Electronic Cash System / Satoshi Nakamoto., 2009. – 9 с.
Hackernoon: Two Ways to Double-Spend https://medium.com/hackernoon/bitcoin-core-bug-cve-2018-17144-an-analysis-f80d9d373362 (дата звернення 28.12.19)
BitcoinCore: CVE-2018-17144 Full Disclosure https://web.archive.org/web/20191005023317/https://bitcoincore.org/en /2018/09/20/notice/ (дата звернення 28.12.19)
A. Pinar Ozisik., Brian Neil Levine. An Explanation of Nakamoto's Analysis of Double-spend Attacks https://arxiv.org/pdf/1701.03977.pdf (дата звернення 28.12.19)
W. Feller. An Introduction to Probability Theory and its Applications: Volume I, Volume 3. John Wiley & Sons London-New York-Sydney-Toronto, 1968.
Pinzón C., Rocha C. Double-spend Attack Models with Time Advantange for Bitcoin. Electronic Notes in Theoretical Computer Science. Volume 329, 9 December 2016, Pages 79-103 https://doi.org/10.1016/j.entcs.2016.12.006 (дата звернення 28.12.19)
Rosenfeld M. Analysis of hashrate-based double-spending / Meni Rosenfeld., 2014. – 13 с (arXiv preprint arXiv:1402.2009)
Ozisik A. P. and Levine B. N., “An explanation of Nakamoto’s analysis of double-spend attacks,” arXiv preprint arXiv:1701.03977, 2017 https://arxiv.org/pdf/1701.03977.pdf (дата звернення 30.12.19)
Zaghloul, E., Li, T., Mutka, M.W., & Ren, J. (2019). Bitcoin and Blockchain: Security and Privacy. ArXiv, abs/1904.11435
A.W.F. Edwards. Pascal's problem: The «gambler's ruin». Revue Internationale de Statistique, 51(1):73-79 (http://www.jstor.org/stable/1402732), Apr 1983
Ковальчук Л.В. Основні визначення у галузі блокчейну та детальний аналіз результатів Накамото-Розенфельда-Грунспана про ймовірність атаки подвійної витрати. Звіт про НДР (проміжний), Харків, АТ ІІТ, 36 с.
L. Rey-Bellet. Gambler's ruin and bold play. http://people.math.umass.edu/~lr7q/ps_files/teaching/math456/Week4.pdf, June 7 201651% Attack Explained: The Attack on a Blockchain https://www.fxempire.com/education/article/51-attack-explained-the-attack-on-a-blockchain-513887 (дата звернення 30.12.19)
Walpole R. E., Myers R. H., Myers S. L., Ye K. Probability & Statistics for Engineers & Scientists. Prentice Hall, (See pg. 161 for a discussion of Poisson experiments), 9-th edition, 2012.
Grunspan C., Pérez-Marco R. Double spend races. 2017. hal-01456773 https://hal.archives-ouvertes.fr/hal-01456773 (дата зве-рнення 11.01.20)
Rosenfeld M. Analysis of hashrate-based double-spending / Meni Rosenfeld., 2014. – 13 с (arXiv preprint arXiv:1402.2009)
Apostolaki M. Hijacking Bitcoin: Routing Attacks on Cryptocurrencies / M. Apostolaki, A. Zohar, L. Vanbever. – San Jose, CA, USA, 2017. – 18 р. https://btc-hijack.ethz.ch/files/btc_hijack.pdf
Apostolaki M., Marti G., Müller J., Vanbever L. SABRE: Protecting Bitcoin against Routing Attacks. –San Diego, CA, USA, 2019. pp. 1-15 https://dx.doi.org/10.14722/ndss.2019.23252
Kaidalov D.S., Kovalchuk L.V., Nastenko A.O., Rodinko M.Yu., Shevtsov O.V., Oliynykov R.V. Comparison of block expecta-tion time for various consensus algorithms. Radio Electronics, Computer Science, Control. 2018. № 4. рр. 159-171 DOI 10.15588/1607-3274-2018-4-15