Introduction

Modern decentralized systems are a real alternative to the classical centralized approach in creating of complex information and telecommunication systems and networks [1][2][3][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. [1][2][3]. 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.

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 (

1 0 0 1 t N j k       

). 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:

1, 0, 0 0 N j k PI     2.

The attacker may succeed on the second attempt ( 0 1 2 t N     ) 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:

          2 1, 0, 1 1 1 2 1 N j k PI p p qq p p qq p p q                   3. On the third attempt ( 0 2 3 t N     ).

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

1, 0, 1 N j k PI    ).

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:

        2 1 1 2 1, 0, 2 2 1 1 2 3 2 1 2 1 1 3 1 . N j k PI p p q q p p q q q                           4.

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

          3 2 1 2 1, 0, 3 3 2 1 1 2 3 4 3 1 3 1 1 6 1 4 1 . N j k PI p p q q p p q q q q q                               5.

On the t -th attempt ( 0 t N k    ) the probability of success of the attacker is equal to:

        1 1, 0, 1 1 2 2 0 1 1 1 1 1 1 1 1 0 1 k N j k k k k k PI p p k k k q q q q q q                                                    

Carrying out similar constructions and summing all the 0,1, 2, k   , we find the probability of a successful double-spending attack, provided that the honest network is formed of no more than 1 N  blocks:

        1 2 1, 0 1 1 0 1 1 1 1 1 1 1 1 . 0 1 k k N j k k k PI p p k q q k k q q q q                                                             Let us consider the case when 2, 0 N j   .

If 0 k  , as well as in the previous case, success is impossible. If 1 k  and, therefore, 0 1 3 t N     , the probability of success of the attacker is equal to:

  2 3 2, 0, 1 3 1 . N j k PI p p q         If 2 k  ( 4 t  ), the probability of successful attack is equal to:         2 2 3 2, 0, 2 2 2 3 4 3 1 3 1 3 1 4 1 . N j k PI p p q q p p q q q                              If 3 k  ( 5 t 

), the probability of success of the attacker is equal to:

          3 2 2 3 2, 0, 3 3 2 1 2 3 4 5 6 1 6 1 4 1 10 1 5 1 1 . N j k PI p p q q p p q q q q q                                  

The above results allow us to obtain expressions for arbitrary values of N and k :

      2 1 1 , 0 1 0 1 1 1 1 1 1 . 1 k k N N N N j k N t i i i t PI p p q q N t t q q N i                                                            Let us consider the case for 1, 1 N j   . If 0 k  attacker's success is impossible If 1 k  the probability of success of the attacker is equal to:     1, 1, 1 1 N j k PI p p p q q q           . If 2 k  ( 4 t  ) the probability of the attacker's success is equal to:       2 2 3 1, 1, 2 1 1 3 2 2 . N j k PI p p q q                 If 3 k  ( 5

t  ) the probability for the attacer to succeed is equal to:

    1 1 1, 1, 3 1 1 1 1 2 2 3 . 1 2 1 2 1 2 k k N j N j N j k PI p p q q k t k t k t                                                                       

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):

                      2 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 , k k N N k N t i i i k k N j N j p j k t PI p p q q N t t q q N i p q sum p q                                                                                     ( 1 )

where

t N j k    ;   ( ) ( 1 ) ( ) 2 3 1 2 1 2 1 1 1 1 1 N j N j N j k k t t p q ip ip ip ip ip ip ip sum sum                                           ;           ( )( 1 ) ( ) ( 1 )

( 2 )

2 3 2 1 2 1 ( 1) ( ) 1 1 2 1 1 1 1 m a x 1 , m a x 1 , max 1, 1 . N j N j N j j j j j j q t j t j k k t t iq iq iq iq iq iq iq ip iq iq ip iq iq ip sum                                                                          

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. However, given the limited number of calculated coefficients of p sum , the expres- sion (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 p sum . Also, at , 0,2 q p  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 p sum grows more slowly, making it possible to calculate p sum 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 p sum using polynomial approximation. Thus, for 1 j  the value p sum is very well approximated (within known values of k ) and extrapolated (beyond calculated values of k ) by a polynomial:

Extrapolation of the sum in the formula of calculation of the probability of success of the attacker4 3 2 0,125 0, 4167 0,375 0 ( 1, 1, ) ,0833 p sum k k k k k N j           ,p k k k k s m j k k k u N                

Extrapolation is also well done by j , and the value of k is fixed. As established experimentally, it is desirable to use the Lagrangian interpolation polynomial for computational methods (see, for example, [7] or [8]). The essence of which is as follows. We know some values of p sum at the first values of i x (we assume i

x to be i k or i j ), where 1, 2, , i n   , and n is the number of points by which the Lagrangian polynomial is constructed (in our case, for 1 N  , n must be chosen as 3 2 n j    for extrapolations by k and as 2 1 n k    for extrapolations by j ), then we can extrapolate p sum by Lagrange interpolation polynomial: 0 0, ( )

n n s p p i i s i s s i x x sum sum x x x                    .

The results of the extrapolation of value of p sum are illustrated in Figure 1, which shows a graph of the dependence of precisely calculated values of p sum (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 p sum 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 p sum (for example, in Table 2 for 7 k  this is only for 15 j  ) 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

2 1 i p N j k sum d N j            

where d -some coefficient 0 1 d   , 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 p sum , 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). These results can be useful for assessing the security of blockchain networks with probabilistic consensus building [9][10][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.

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 1 p q   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][13][14][15][16].