DOI: https://doi.org/10.15588/1607-3274-2018-4-15

COMPARISON OF BLOCK EXPECTATION TIME FOR VARIOUS CONSENSUS ALGORITHMS

D. S. Kaidalov, L. V. Kovalchuk, A. O. Nastenko, M. Yu. Rodinko, O. V. Shevtsov, R. V. Oliynykov

Abstract


Context. We consider security properties of decentralized blockchain-based consensus protocols. The object of research is block
confirmation time for users to get assurance that their transaction will not be reverted.
Objective. The goal of the paper is to analyze double-spend attacks on the different blockchain-based systems and compare
resulting probabilities of attacker’s success.
Method. We presented two models for two types of attacks on the Ouroboros protocol (for the general and covert adversaries).
The models allow calculating the exact number of slots needed to achieve the required level of security. It was shown that the
Ouroboros protocol allows achieving the required security level with significantly shorter confirmation period in comparison with
Bitcoin. We estimated minimal number of confirmation blocks and compare estimation time for Bitcoin, GHOST and Ouroboros
protocols. As a measure of comparison, we considered transaction confirmation time for which the probability of a double-spend
attack is less than 0.1%. We use different standard probability distribution and different properties of Markov chains and Random
Walks to get comparison of estimated security properties of Bitcoin blockchain against three different models of Bitcoin double
spend attack. The splitting attack based on the model where resources of honest participants are divided to compete different chains
is applied to Bitcoin and GHOST consensus protocols. Properties of Markov chains and Random Walks are also applied to obtain
security estimations for the Ouroboros protocol.
Results. We developed methods to get specific numbers for average block confirmation time for Ouroboros protocol. We
compared minimal number of confirmation blocks needed to ensure a high security for considered protocols: Bitcoin, GHOST and
Ouroboros.
Conclusions. The obtained results allow determination of security bounds for the Bitcoin, GHOST and Ouroboros consensus
protocols. Users of the practically deployed blockchain systems may get specific parameters for a given assurance level.

Keywords


blockchain; Bitcoin; proof-of-work; GHOST; proof-of-stake; Ouroboros

References


Kiayias A. Ouroboros: A provably secure proof-of-stake blockchain protocol [Electronic resource], Cryptology ePrint Archive. Electronic data. [International Association for Cryptologic Research, 2016]. Mode of access:

http://eprint.iacr.org/2016/889 (viewed on May 13, 2018). Title from the screen.

Nakamoto S. A. peer-to-peer electronic cash system”

[Electronic resource], Bitcoin. Electronic data, 2008. Mode

of access: https: //bitcoin.org/bitcoin.pdf (viewed on May

, 2018). Title from the screen.

Sompolinsky Y., Zohar Aviv Accelerating bitcoin as

transaction processing. Fast money grows on trees, not

chains [Electronic resource], Cryptology ePrint Archive.

Electronic data. [International Association for Cryptologic

Research, 2013]. Mode of access:

http://eprint.iacr.org/2013/881 (viewed on May 13, 2018). Title from the screen.

Pinzon C., Rocha C. Double-Spend Attack Models with

Time Advantage for Bitcoin, Electronic Notes in Theoretical Computer Science, 2016, Vol. 329, pp. 79–103.

Rosenfeld M. Analysis of hashrate-based double-spending races [Electronic resource], Preprint arXiv. Electronic data, [Cornell: Cornell University, 2017], Mode of access:

https://arxiv.org/abs/1402.2009 (viewed on May 13, 2018). Title from the screen.

Grunspan C., Pérez-Marco R. Double spend races

[Electronic resource], Preprint arXiv. Electronic data,

[Cornell: Cornell University, 2017]. Mode of access:

https://arxiv.org/abs/1702.02867.pdf (viewed on May 13, 2018). Title from the screen.

Kiayias A., Panagiotakos G. Speed-security tradeoffs in blockchain protocols [Electronic resource] / A. Kiayias, // Electronic data. – [International Association for Cryptologic Research, Cryptology ePrint Archive, 2015]. – Mode of access: http://eprint.iacr.org/2015/1019 (viewed on May 13,

. Title from the screen.

Double-spending [Electronic resource], BitcoinWiki. Mode of access: https://en.bitcoin.it/wiki/Double-spending (viewed on May 13, 2018). Title from the screen.

Garay J. A. Kiayias Aggelos, and Leonardos Nikos The

Bitcoin Backbone Protocol: Analysis and Applications”,

Advances in Cryptology, EUROCRYPT 2015, 34th Annual

International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26–30, 2015: proceedings. Berlin, Springer, 2017. Part II, pp. 281– 310. DOI: 10.1007/978-3-662-46803-6_10.

Decker C., Wattenhofer R. Information Propagation in the Bitcoin Net-work, Peer-to-Peer Computing: IEEE

International Conference on Peer-to-Peer Computing (P2P), Trento, Italy, September 9–11, 2013, proceedings. Trento, IEEE Xplore, 2013, pp. 1–10. DOI:

1109/P2P.2013.6688704.

Sompolinsky Y., Zohar A. Secure high-rate transaction processing in Bitcoin, Financial Cryptography and Data Security – 19th International Conference, FC 2015, San Juan, Puerto Rico, January 26–30, 2015: proceedings. Berlin, Springer, Lecture Notes in Computer Science, 2004, Vol. 8975, pp. 507–527. DOI: 0.1007/978-3-662-47854-7_32.

Schoenmakers B. A simple publicly verifiable secret sharing scheme and its application to electronic voting, Advances in Cryptology – CRYPTO 99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15–19, 1999: proceedings. – Berlin: Springer, 1999,

Volume 1666 of Lecture Notes in Computer Science,

pp. 148–164.

Russel A. Forkable Strings are Rare [Electronic resource], Cryptology ePrint Archive. Electronic data. [International Association for Cryptologic Research, 2017]. Mode of access: http://eprint.iacr.org/2017/241 (viewed on May 13, 2018). Title from the screen.

Feller W. An Introduction to Probability Theory and its Applications. New York: John Wiley & Sons, 1970, 700 p. DOI: 10.1137/1014119


GOST Style Citations








Copyright (c) 2019 D. S. Kaidalov, L. V. Kovalchuk, A. O. Nastenko, M. Yu. Rodinko, O. V. Shevtsov, R. V. Oliynykov

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
Zaporizhzhya National Technical University, 
Zhukovskiy street, 64, Zaporizhzhya, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.