Extrapolation to Calculate the Probability of a Double Spending Attack

Abstract

One of the important aspects of the efficiency of modern distributed networks built using blockchain technologies is the study of the security of consensus protocols. In particular, the most common cryptocurrencies and blockchain systems with probabilistic consensus protocols are subjects to so-called double-spending attack. The basis of such an attack is the use of the attacker's computing capabilities to form alternative blockchains. If the generated sequence is longer than the public chain of blocks, the attacker can present it as the proof of work and thus disrupt the correct functioning of the network. In this article we explore the probability of a successful double-spending attack, derive formulas for evaluating the corresponding events, consisting of the formation by the attacker of an alternative sequence of blocks. These formulas are extremely cumbersome and difficult to calculate. The paper proposes simplified analytical expressions to quickly assess the probability of a successful doublespending attack. For this we use the extrapolation of intermediate calculations using the Lagrange interpolation formulas, as well as binomial approximation. The simulation results show that the use of simplified expressions allows us to provide acceptable accuracy of calculations.

Keywords

• blockchain technology
• consensus protocols
• proof-ofwork
• double-spending attack
• polynomial interpolation
• binomial approximation

-

Modern decentralized systems are a real alternative to the classical centralized approach in creating of complex information and telecommunication systems and networks [ 1-4 ]. For example, it is advisable to use decentralization in complex systems of corporate relations, in the provision of state and administrative functions, to build independent cryptocurrencies, as well as to create secure registers, cadastres, etc. [ 13 ]. These and many other aspects show the clear advantage of decentralized systems built on blockchain technology [ 5, 6 ].

At the same time, for the most developed and studied blockchain networks with probabilistic consensus protocols, there is a risk of a double-spending attack. The essence of the attack is to use the features of consensus building protocols. For example, in the proof-of-work protocols, each record in the protected registry (each block of records) can be made only by the participant who was the first to solve the exhaustive task of finding the preimage of the cryptographic hash function. The block chain stores all the important records, and each following record (block of records) is connected with the previous ones through a one-way hash function. This is a reliable and safe way to save critical data, protect it from falsification, alteration, intentional or accidental modification. At the same time, an attacker who has sufficient computing resources may try to form an alternative chain of blocks (with other records in previous blocks). This will give him the opportunity to disrupt the proper functioning of the blockchain network, for example, by spending the same assets twice (cryptocurrencies, tokens, etc.). The probability of such unauthorized interference is extremely small (with the small computing capabilities of an individual attacker it is almost impossible). However, when building a critical information infrastructure, an extremely important aspect is the assessment of various risks and threats to information security, including the probabilities of successful implementation of various attacks. Therefore, assessing the security of blockchain systems and, in particular, assessing the likelihood of a successful implementation of a double-spending attack in systems with probabilistic consensus protocols, is an urgent and practically important scientific task.

In this article, we consider consensus protocols with probabilistic completion (such as proof-of-work), and assess the probability of a successful double-spending attack. For this, we use the model of independent players (as in our previous works [ 4 ]). This model differs from the gambler's ruin model adopted in [ 2, 3 ] by both the number of elementary outcomes and general expressions for assessing the probability of a successful attack. To simplify computational calculations, we use polynomial interpolation, as well as binomial coefficients to extrapolate intermediate calculations. The results of numerical simulation show that simplified formulas can significantly reduce computational costs and obtain approximate estimates with acceptable accuracy of calculations. These results can be used to calculate the security indicators of blockchain networks with probabilistic consensus protocols. 2

The probabilities of forming a chain of blocks under the same initial conditions To obtain the formula for the probability of a successful double-spending attack, let us consider the following possible probabilities and combinations in which the attacker succeeds: 1. Success is not possible on the first attempt ( t  N  j  k  1  0  0  1 ). The attacker may form no more than one block in one attempt, and in order to succeed, he needs to wait for the generation of the block by the honest network and extend the chain of blocks to one more. Thus, the attacker needs to form at least two blocks. The probability of success of the attacker is defined as: PIN 1, j0,k 0  0 2. The attacker may succeed on the second attempt ( t  N  0 1  2 ) if he managed to form on both attempts per block, and the honest network will form only one block (no matter on the first or second attempt).The total probability of this event: PIN 1, j0,k1  p  1 p q  q  1 p  p q  q  2  p  1 p  q2 3. On the third attempt ( t  N  0  2  3 ). If the honest network forms a block on the first or second attempt, then the second block should be formed by the attacker only on the third attempt, otherwise (if the second block is formed on the second attempt) there is a previous case (as for PIN 1, j0,k 1 ). If the honest network forms the second block on the third attempt, there are no restrictions on the formation of blocks for the attacker. The total probability of the event will be calculated similarly to the events described above. Thus, the total probability will be: PIN 1, j0,k 2  2  p1  1  p2 2  q2  1 q1  

  p1  1  p 2 3 q2  1  q1  q3  .

 4. On the fourth attempt ( t  N  0  3  4 ) similar to the situation described in the previous paragraph, the total probability for the attacker to succeed will be equal to:

PIN 1, j0,k 3  3  p1  1  p3 3 q2  1  q 2  

   p1  1  p 3 6  q2  1 q2  4  q3  1  q 1  q4  . 5. On the t -th attempt ( t  N  0  k ) the probability of success of the attacker is equal to: PIN 1, j0,k k  p1  1  p k   k 2  q2  1 q k 1  1   k  1  q0  1 qk 1   k  1  q1  1 q k     0   1   Carrying out similar constructions and summing all the k  0,1, 2, , we find the probability of a successful double-spending attack, provided that the honest network is formed of no more than N  1 blocks:

  k  PIN 1, j0    p  1  p  k  q2  1  qk 1  k 1    1   k  1  q0  1 qk 1   k 1  q1  1 qk .

  0   1  

Let us consider the case when N  2, j  0 .

If k  0 , as well as in the previous case, success is impossible.

If k  1 and, therefore, t  N  0 1  3 , the probability of success of the attacker is equal to:

PIN 2, j0,k1  3 p2  1 p  q3.

If k  2 ( t  4 ), the probability of successful attack is equal to:

PIN 2, j0,k 2  3  p2  1  p 2  3 q3  1 q  3  p2  1  p2  4  q3  1  q   q4  .

If k  3 ( t  5 ), the probability of success of the attacker is equal to: PIN 2, j0,k 3  6  p2  1  p3  6  q3  1  q 2     4  p2  1  p 3  10  q3  1  q 2  5  q4  1 q1  1 q5  .

The above results allow us to obtain expressions for arbitrary values of N and k :  k  t 12 PIN N, j0   p N  1  p   N   qN 1  1  q k 1  k 1   N 1  1      qi  1  q ti   t 1   N  t    .

i0  i  

Let us consider the case for N  1, j  1 . If k  0 attacker's success is impossible If k  1 the probability of success of the attacker is equal to:

PIN 1, j1,k1  p  p  1 p q  q  q .

If k  2 ( t  4 ) the probability of the attacker's success is equal to: PIN 1, j1,k 2  p2  1  p2  q3  1 q 3  2  2 .

 If k  3 ( t  5 ) the probability for the attacer to succeed is equal to:

PIN 1, j1,k 3  pN  j  1  pk  qN  j1  1  q k 1   k   t 1  k 1  t  2   k  2   t  3               .

 1   2    1   2   1   2 

Thus, summarizing the results for arbitrary initial values, we obtain the probability of a successful double-spending attack ( PI ) on blockchain systems using the consensus algorithm Proof of Work based on a hash function (without the attacker's advantage in one pre-formed block):

where sumq 

 k  t 12 PI  p N   1  p      qN 1  1 qk 1 

k 1  N   N 1  1     qi  1 q ti   t 1   N  t     

i0  i      pN  j  qN  j1   sump  1  pk  1  q k 1 ,

 j1  k 1  

t  N  j  k ; sump  k  k 1      ip(N j) 1 ip(N j1) ip(N j) 1 t2  t1        sumq     ; ip2 ip3 1 ip1 ip2 1 (1)  k  k 1      iq(N j) 1 iq(N j1) iq(N j) 1 t j1  t j      iq( j1) iq( j2) 1 iq j maxiq( j1) 1,ip( j)   t2  t1    iq2 maxiq3 1,ip2   iq1maxiq2 1,ip1

     1     .

    

Although the expression (1) provides an accurate quantitative result on the probability of successful double-spending attacks, it also has limitations on its use, which is related to the polynomial complexity of computational calculations. In this paper, we propose using an approximate formula to calculate the probability of a successful attack. For this, simplified expressions based on polynomial interpolation can be used. In addition, we explore other approximation methods, including using binomial coefficients.

Extrapolation of the sum in the formula of calculation of the probability of success of the attacker The value of sums ( sump and sumq ) is increasing very fast and even at j  10 and k  15 the calculation becomes a very difficult task. For example, if j  20 and k  7 the sum sump  16 570 275 123 (this value was calculated by the computer for several hours). On the other hand, these sums for each value N could be calculated once and used for different probabilities. Tables 1, 2, as an example, provide calculated values of sump for N  1,5 and some values of j and k .

However, given the limited number of calculated coefficients of sump , the expression (1) gives a good match with the experimental data (setting up the computational experiment is given in [ 4 ]) when the probabilities q and p significantly (twice or more) differ from each other. However, there is no need to calculate the large number of values in the sum by j , that allows to be limited to some small pre-calculated set of values of sump . Also, at q, p  0, 2 the blocks will be formed with a relatively high probability, that makes it possible to significantly reduce the sum by k . In addition, for smaller values N , the sum sump grows more slowly, making it possible to calculate sump for more values j and k .

However, in order to improve the accuracy of the calculation (increasing the calculated coefficients j and k ), it is possible to extrapolate the values of sump using polynomial approximation. Thus, for j  1 the value sump is very well approximated (within known values of k ) and extrapolated (beyond calculated values of k ) by a polynomial:

sump (N  1, j  1, k)  0,125 k 4  0, 4167  k3  0,375 k 2  0, 0833 k , for j  2 : sump (N  1, j  2, k)  0, 0097  k 6  0, 0792  k 5  0, 2431 k 4  0, 3542  k 3 

Extrapolation is also well done by j , and the value of k is fixed. sume xi to be ki or ji ), where i  1, 2,, n , and n is the number of points by which the Lagrangian polynomial is constructed (in our case, for N  1 , n must be chosen as n  3  2  j for extrapolations by k and as n  2  k 1 for extrapolations by j ), then we can extrapolate sump by Lagrange interpolation polynomial: sump  n  sump (xi )  n x  xs  .

 i0  ssi0, xi  xs 

The results of the extrapolation of value of sump are illustrated in Figure 1, which shows a graph of the dependence of precisely calculated values of sump (solid line) by formula (1) and its approximation and extrapolation (dashed line).

Extrapolation using a polynomial gives a very good accuracy, but with increasing k ( j ) increases the number of first values of sump that must be known and whose values are taken into account in the Lagrangian interpolation polynomial. Given that we are aware of a rather limited number of sump (for example, in Table 2 for k  7 this is only for j  15 ) polynomial extrapolation will also have some limits.

The next extrapolation method we have applied is binomial extrapolation, that is, extrapolation using binomial coefficients of the form

 N  j  ki 12 sump  d   N  j  where d – some coefficient 0  d  1, which is selected experimentally.

Binomial extrapolation gives much less precision than polynomial, but better than neglecting additives in general. This is especially noticeable when q  p and a significant number of coefficients j and k must be considered.

Thus, the results obtained can significantly reduce the complexity of the calculations when calculating the probability of a successful double-spending attack. In particular, to calculate the probabilities by the formula (1), it is necessary to calculate an infinite number of sums sump , each of which in turn is formed by summing a large number of terms. We were able to simplify these intermediate sums by introducing interpolation polynomial equations. By extrapolating the sums to a larger data range, we can replace complex and cumbersome calculations with simple and convenient calculations based on interpolation polynomials. The simulation results show that the values calculated in this way almost 100% repeat the results obtained by exact expressions using formula (1). Fig. 1. Dependencies of values of sump (solid line) calculated by formula (1) and its approximation and extrapolation (dashed line) for N  1 a) extrapolation by k b) extrapolation by j

These results can be useful for assessing the security of blockchain networks with probabilistic consensus building [ 9-11 ]. In particular, practical recommendations for constructing asset transfer protocols in decentralized systems can be justified through restrictions on the probability of corresponding risks. For example, given the restrictions on the admissible probability of loss of an asset as a result of a double-spending attack, our formulas allow us to calculate the minimum number of confirmed transactions (length of a chain of blocks) and these calculations can be performed very quickly even in the conditions of a rapid change in the share of controlled computing resources. These and other studies are our promising areas of further work. 4

Conclusions This paper address in detail one of the main vulnerabilities of blockchain systems built by consensus with probabilistic completeness - the double-spending attack.

Basing on the model of "independent players", we have obtained the analytical expression of the probability of a successful double-spending attack on a blockchain system which uses the consensus algorithm Proof of Work (PoW) based on a hash function depending on the number of confirmations used and the number of attempts and hash rate of both the honest network and the attacker.

The adopted model of "independent players" and the resulting formula (1) eliminates the significant disadvantages inherent in other work in this field, namely:  the race between two participants of the network does not have to be endless, it is enough to be limited by some fixed number of attempts;  uses a more adequate, in the authors' view, model of "independent players", which includes a space of four elementary events, instead of two, used in the model of "gambler's ruin";  the probability of forming a block with the honest network and the attacker are independent quantities that are directly determined by the capacities possessed by the participants, and the mentionedprobabilities are independent on each other, that is, the requirement p  q  1 is optional;  it is calculated the probability for the attacker to be ahead of the honest network, and not only the probability of catching up with it, that is, when the attacker does not have an advantagein one pre-formed block.

The quantitative values obtained by the expression (1) of the probability of a successful attack for different opportunities of the attacker (the probability of forming a block), the different number of formed blocks after which the agreement is considered confirmed, the different duration of the race (the number of blocks during which the attacker continues to catch up the network) are given. To simplify the numerical calculations, it is proposed to use polynomial approximation. In particular, the intermediate sums in formula (1) were able to be approximated by Lagrange interpolation polynomials. In addition, we used binomial extrapolation. However, the simulation results show that polynomial interpolation provides greater accuracy. The formulas obtained make it possible to quickly assess the probability of a successful doublespending attack using these simplified formulas.

This study can be useful for modeling and evaluating the effectiveness of blockchain networks, as well as in other practically important applications [ 12-16 ].

References

1. Zaghloul , E. , Li , T. , Mutka , M.W. , Ren , J.: Bitcoin and Blockchain: Security and Privacy . ArXiv, abs/ 1904 .11435 ( 2019 )

2. Nakamoto , S. : Bitcoin: A Peer-to-Peer Electronic Cash System ( 2009 )

3. Rosenfeld , M.: Analysis of hashrate-based double-spending ( 2014 )

4. Poluyanenko , N.A. , Kuznetsov , A.A. : Simulation of double spend attack on the “Proof of Work” consensus protocol . Radiotekhnika . 3 , 146 - 161 ( 2019 ). doi: 10 .30837/rt. 2019 . 3 .198.11 (in Russian)

5. Zaghloul , E. , Li , T. , Mutka , M.W. , Ren , J.: Bitcoin and Blockchain: Security and Privacy ( 2019 )

6. Ozisik , A.P. , Levine , B.N.: An Explanation of Nakamoto's Analysis of Double- spend Attacks ( 2017 )

7. Turchak , L.I. , Plotnikov , P.V. : Fundamentals of numerical methods . Moscow, Fizmat-lit. 304 p. ( 2003 ) (in Russian)

8. Interpolating Polynomial , http://dx.doi.org/10.3840/001276, ( 2007 )

9. Pilkington , M. : Blockchain technology: principles and applications , http://dx.doi.org/10.4337/9781784717766.00019, ( 0 )

10. Salman , T. , Jain , R. , Gupta , L. : Probabilistic Blockchains: A Blockchain Paradigm for Collaborative Decision-Making . In: 2018 9th IEEE Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON) . IEEE ( 2018 ). doi: 10 .1109/UEMCON. 2018 .8796512

11. Bhat , M. , Vijayal , S.: A Probabilistic Analysis on Crypto-Currencies Based on Blockchain . In: 2017 International Conference on Next Generation Computing and Information Systems (ICNGCIS) . IEEE ( 2017 ). doi: 10 .1109/ICNGCIS. 2017 .37

12. Kuznetsov , A. , Shekhanin , K. , Kolhatin , A. , Kovalchuk , D. , Babenko , V. , Perevozova , I. : Performance of Hash Algorithms on GPUs for Use in Blockchain . In: 2019 IEEE International Conference on Advanced Trends in Information Theory (ATIT) . IEEE ( 2019 ). doi: 10.1109/ATIT49449 . 2019 .9030442

13. Bondarenko , S. , Liliya , B. , Oksana , K. , & Inna , G. : Modelling instruments in risk management . International Journal of Civil Engineering and Technology . 10 ( 1 ), 1561 - 1568 ( 2019 )

14. Runovski , K. , Schmeisser , H.: On the convergence of fourier means and interpolation means . Journal of Computational Analysis and Applications . 6 ( 3 ), 211 - 227 ( 2004 )

15. Tkach , B.P. , Urmancheva , L.B. : Numerical-analytic method for finding solutions of systems with distributed parameters and integral condition . Nonlinear Oscillations . 12 , 113 - 122 ( 2009 ). doi:10.1007/s11072-009-0064-6

16. Chornei , R.K. , Daduna V.M. , H. , Knopov , P.S. : Controlled Markov Fields with Finite State Space on Graphs . Stochastic Models . 21 , 847 - 874 ( 2005 ). doi:10.1080/15326340500294520