 |
January 21, 2019, 01:06:37 PM |
|
Bitcoin Study Supplement
Here is the article I co-authored with Ricardo Perez-Marco on the study of the probabilities of double spending in the Bitcoin network. This includes a correction to the founding article of the Bitcoin, Bitcoin: A Peer-to-Peer Electronic Cash System. We give a closed formula for the probability of success of double-expenditure and we prove the fact that this probability tends exponentially towards zero as a function of the number z of confirmations required, a result often cited but never demonstrated. Finally, we conduct a more detailed analysis of this attempt at double spending by taking into account the time taken by honest miners to undermine blocks, information available by the merchant who is about to send his consumer good to the possible attacker.
I wrote "correction". It's a strong word, but no matter how you turn it around, the mathematical part of the article (section 11 "Calculations") is slightly incorrect.
Satoshi's reasoning
Its approximation
Satoshi estimates that honest miners with a relative computing power equal to p put exactly \frac{z. \tau_0}{p} to mine z blocks with \tau_0 = 10 minutes. This is obviously a rough approximation. In reality, honest miners put on average \frac{\tau_0}{p} to mine a block and \frac{z.\tau_0}{p} to mine z blocks. This approximation is then used by Satoshi to say that during this time, the attacker who is trying to achieve a double-expenditure has managed to undermine {\bf N }(\frac{z\tau_0}{p}) where {\bf N'} is a Fish process of intensity q where q = 1-p is the relative computing power available to the attacker. The fact that there is a Fish process here is quite natural. This is because the hash function SHA256 is assumed to be perfect. The consequence of this hypothesis is that the inter-block mining time follows an exponential law and that the counting process that counts the number of mined blocks is a Fish process. As a result, the number of blocks mined by the attacker follows a Fish law of intensity \frac{q.z\tau_0}{p}. That's what Satoshi wrote.
The final calculation
The probability of success of double spending is then obtained simply by using the formula of total probabilities: P(A) = \sum_{k} P(A | B_k).P(B_k). Here, A denotes the event "the attacker succeeds in his attack" and B_k denotes the event "the attacker has succeeded in mined k blocks at a time when the honest minors have just mined z blocks". The probability P(B_k) has been seen above. Here z is fixed.
When k>z, of course we have P(A | B_k) = 1 and when k<z, the attacker is as lucky as a player who plays against the flipped bank with a delay of z-k: with each throw of a faked coin in favour of the bank (the bank has a probability p of winning) the player advances or retreats by 1. If he ends up catching the bank, he has won. This is a classic calculation. Satoshi refers to Feller's famous book An introduction to probability theory and its applications. This is a basic example of random walking. We have P(A | B_k) = (\frac{q}{p})^{z-k}. Hence Satoshi's final formula by rearranging the terms of his sum a little: P(A) = 1-\sum_{k=0}^{z}\frac{\lambda^k e^{-\lambda}}{k!}(1-(\frac{q}{p})^{z-k}) following which Satoshi presents a small C code to calculate this sum digitally.
The real calculation
A negative binomial law
But the time taken by honest minors is random and has no reason to be equal to its average \frac{z. \tau_0}{p}. The formula given above for P(A) is wrong. In fact, if we refer to {\bf S}_z as the time taken by honest miners to mine z blocks, the law of {\bf S}_z is a Gamma law of parameter (z,\tau_0) and the number of blocks mined by the attacker at the time the honest miners discover their zth block is {\bf N' }({\bf S}_z). A small calculation shows that the law of {\bf N'}({\bf S}_z) is a negative binomial law of parameter (z,p). That's normal. Everything happens as if the race to the mine was a multiple draw with the delivery of an urn filled with black and white balls until the Z white balls are obtained. Shooting a black ball means: "the attacker discovers a new block" and shooting a white ball means "honest miners discover a new block". In total, the number of black balls fired represents the number of blocks mined by the attacker at the moment the honest miners discover their zth block...
Meni Rosenfeld's formula
The true probability of success P(z) of double expenditure is P(z) = P[{\bf N'}({\bf S}_z) >z]+\sum_{k=0}^{z} P[{\bf N'}({\bf S}_z) = k] (\frac{q}{p})^{z-k}. Using the fact that {\bf N'}({\bf S}_z) is a negative binomial law of parameter (z,p) as explained above, we deduce that P(z) = 1-\sum_{k=0}^{z-1}(p^z.q^k-q^z.p^k)\dbinom{
However, with a questioning of all these calculations, I managed to spend 3 times 0.001 btc
-the first one went through
-the second one was refused
-the third one has passed.
And all of them once out of 4 times
I will continue my research and put the first version of triple spend online.
|
