51 Attack: the math behind


The so-called $\textit{double-spending attack}$ acts as follows:

  1. A vendor generates new key pair $\textit{public key}+\textit{private key}$, then reveals the obtained payment address (i.e. hash of the public key) to an interested buyer.

  2. An attacker sends $N$ coins to the vendor for a good (e.g. instant-delivery digital good).

  3. Secretly, he starts mining alternative branch of blockchain: the branch in which the receiver of the buying transaction is one of wallets controlled by the attacker.

  4. Vendor waits for $z$ confirmations (block with transaction to vendor and $(z-1)$ more blocks of "honest" chain) and sends a good. The attacker receives the good.

  5. If the moment when attacker's branch is longer than honest miners' branch ever comes (to be precise — if combined difficulty of his branch becomes bigger), the attacker sends his branch to the network. According to protocol, this convinces users that attacker's branch is the correct one. Since his chain spends UTXOs that should've been delivered to vendor, rebroadcasting transaction to vendor will lead to rejection — these coins are already spent. This is the way how attacker preserves his money when buying a good or a service.


Let $s$ be probability of next hash be winning one (w.r.t. current difficulty). This probability is extremely low for any currency; e.g. for Bitcoin by the end of October $s$ is equal to $$0.0000000000000000000009006195589798516\nonumber$$
This number can be obtained by direct calculation. The probability that a hash is a winning one depends only on difficulty; let's elaborate on this dependence:
$$s = \frac{\text{current target}}{2^{256}} =\frac{2^{224}/\text{current difficulty}}{2^{256}} = \frac{1}{2^{32} \cdot \text{current difficulty}}\nonumber$$
For simplicity, we assume that difficulty doesn't change during attack, and that attacker and honest parts mine with the same difficulty. According to any PoW protocol, $\textit{true}$ transaction history resides in the branch that has biggest combined difficulty — the condition of biggest combined difficulty turns to condition of longest branch under out assumption.

Deriving the formula for attack success probability

According to Bernoulli distribution, the probability of attacker finding $k$ blocks after calculating $n$ hashes is $$P_n(k)=C^k_n s^k \left(1-s\right)^{n - k}\label{ref1}$$

Probability theory has two approximations for this expression (that is largely inappropriate for real calculation). Namely, for $n \to \infty, s \to 0, ns \to \lambda = \text{const}$ \ref{ref1} becomes Poisson distribution, and for $n \gg 1, k\gg 1, n \gg k, (k-ns) \ll ns$ \ref{ref1} turns to Gauss distribution. (One can check e.g. this proof.)

In our case $k \gg 1$ isn't quite true (attacker wouldn't find many blocks for the time honest miners' find $z$ blocks), and $k \ll 2ns$ is untrue as well. Thus, Gauss distribution is not appropriate approximation in case of our problem. But Poisson distribution fortunately is.

To prove that, we need to prove three facts: $n \to \infty, s \to 0, ns \to \lambda = \text{const}$. Indeed, $n$ is extremely large and $s$ is very close to zero, so the only thing left is to prove that $ns = \text{const}$ holds. Actually, both $n$ and $s$ are constants. Calculate them.

Let average block time be equal to $t$ minutes. According to our proposal, it takes $zt$ minutes from honest miners' to compute $z$ blocks. With hashrate of $p$ hashes per second, honest miners' will have $60p$ hashes per minute, and needed $z$ confirmations will be obtained as the result of calculating $60pzt$ hashes. Attacker has hashrate of $q$ hashes per second; this is quite clear that, by the same time, he or she calculates $n = 60qzt$ hashes.

Now to evaluating $s$. Honest miners' network hashrate is $60p$ hashes per minute, with $t$ minutes for average block time. To find a block, thus, they calculate, in average, $60pt$ hashes; in other words, taken $60pt$ hashes, in average, one is winning hash. Since $s$ is the probability to solve a block, $s = 1/(60pt)$ holds.
That is why $$ns = 60qzt \cdot \frac{1}{60pt} = z \cdot \frac{q}{p}\nonumber$$
Thus, $ns = \text{const}$ and this is every property for it to be Poisson distribution is satisfied; denote this constant by $\lambda$, $$\lambda = z \cdot \frac{q}{p}\label{ref2}$$ Thus, attacker will find $k$ blocks by the time honest miners' find $z$ blocks with probability as follows: $$P(k) = \frac{\lambda^k}{k!} e^{-\lambda}\label{ref3}$$ When $k > z$, attacked has already won. Once vendor waits for $z$ blocks and sends him a good, the attacker broadcasts the branch he was mining on, and network will accept his version of blockchain and honest miners' one.
Even if $k \leqslant z$, attacker can win if his or her ever becomes longest one. For that, he or she has to win $(z-k)$ blocks back, and then win another block to take a lead. We denote the probability to win $t$ blocks back and win another one by $\varphi(t+1)$; then for total attack success probability $$p_{\text{success}} = P(0) \varphi(z+1) + P(1) \varphi(z) + \dots + P(z) \varphi(1) + P(z+1) + P(z+2) + \dots\nonumber$$
Since we know $P(k)$, we simply substitute it, obtaining
$$p_{\text{success}} = \frac{\lambda^0}{0!} e^{-\lambda} \varphi(z+1) + \frac{\lambda^1}{1!} e^{-\lambda} \varphi(z) + \dots + \frac{\lambda^z}{z!} e^{-\lambda} \varphi(1) + \frac{\lambda^{z+1}}{(z+1)!} e^{-\lambda} + \frac{\lambda^{z+2}}{(z+2)!} e^{-\lambda} + \dots =\nonumber $$ $$ = 1 - \left( \frac{\lambda^0}{0!} e^{-\lambda} + \frac{\lambda^1}{1!} e^{-\lambda} + \dots + \frac{\lambda^z}{z!} e^{-\lambda} \right) + \left( \frac{\lambda^0}{0!} e^{-\lambda} \varphi(z+1) + \frac{\lambda^1}{1!} e^{-\lambda} \varphi(z) + \dots + \frac{\lambda^z}{z!} e^{-\lambda} \varphi(1) \right) =\nonumber $$ $$= 1 - e^{-\lambda} \left( \frac{\lambda^0}{0!} (1 - \varphi(z+1)) + \frac{\lambda^1}{1!} (1 - \varphi(z)) + \dots + \frac{\lambda^z}{z!} (1 - \varphi(1)) \right)\label{ref4}$$
This could be an answer if one knew what $\varphi(k)$ is. In Bitcoin whitepaper Satoshi provides the correct expression, referring to "gambler's ruin" problem. We provide entire derivation of this correct expression.

Deriving $\varphi(k)$

When honest miners' pullaway diminishes by $1$? It happens when attacker finds winning hash, and honest miners' have found zero winning hashes by the time attacker computed his one. Clearly, for the time attacker calculates $1$ hash, honest network calculates $p/q$ hashes. The probability is: $$p_{-1} = s \cdot C^0_{p/q} s^0 \left( 1-s \right)^{\frac{p}{q} - 0} = s \left( 1-s \right)^{\frac{p}{q}}\nonumber$$ (Non-integer arguments of binomial coefficients are not an issue — for non-integer $p/q$ quantity $C^i_{p/q}$ still can be defined, since factorial can be generalized to non-zero arguments thanks to Gamma function).
Which situations lead to non-changing pullaway? Two situations are there: 1) attacker has calculated a hash that appeared to be winning one, but honest miners' have found another winning hash by the same time 2) $\textit{(most common case)}$ attacker has calculated a hash that appeared to be not winning one, and honest miners' didn't succeed as well. For probability of any of these two outcomes one has $$p_0 = C^1_{p/q} s^{1+1} \left( 1-s \right)^{\frac{p}{q} - 1} + C^0_{p/q} s^{0} \left( 1-s \right)^{\frac{p}{q} - 0 + 1} = \frac{p}{q} s^2 \left( 1-s \right)^{\frac{p}{q} - 1} +\left( 1-s \right)^{\frac{p}{q} + 1}\nonumber $$ Since $s$ is very small, $$p_0 \approx \left( 1-s \right)^{\frac{p}{q} + 1} \nonumber$$ When honest miners' pullaway rises by $1$? Two situations again: 1) attacker has calculated a hash that appeared to be winning one, but honest miners' have found even 2 winning hashes by the same time 2) attacker has calculated a hash that appeared to be not winning one, and honest miners' found 1 winning hash by that time. For probability of this one has $$p_1 = C^2_{p/q} s^{2+1} \left( 1-s \right)^{\frac{p}{q} - 2} + C^1_{p/q} s^{1} \left( 1-s \right)^{\frac{p}{q} - 1 + 1} = C^2_{p/q} s^3 \left( 1-s \right)^{\frac{p}{q} - 2} + \frac{p}{q} s \left( 1-s \right)^{\frac{p}{q}} \approx \frac{p}{q} s \left( 1-s \right)^{\frac{p}{q}}\nonumber $$ When honest miners' pullaway rises by $2$? Two situations again: 1) attacker has calculated a hash that appeared to be winning one, but honest miners' have found 3 winning hashes by the same time 2) attacker has calculated a hash that appeared to be not winning one, and honest miners' found 2 winning hash by that time. For probability of this $$p_2 = C^3_{p/q} s^4 \left( 1-s \right)^{\frac{p}{q} - 3} + C^2_{p/q} s^{2} \left( 1-s \right)^{\frac{p}{q} - 1} \approx C^2_{p/q} s^{2} \left( 1-s \right)^{\frac{p}{q} - 1} \nonumber$$ This is proportional to $s^2$, thus being negligible in comparison to $p_{-1}$, $p_0$ and $p_1$. Probabilities $p_3$, $p_4$ and other are even less. Thus, every probability except $p_{-1}$, $p_0$ and $p_1$, is negligible.

Recall that in our notation $\varphi(1)$ is the probability that attacker ever shortens the distance by 1 block, $\varphi(2)$ — the probability that the distance will ever be shortened by 2 blocks, and so on.

After attacker takes one hash, with probability $p_{-1}$ the distance is shortened by $1$, with probability $p_0$ status quo is preserved, and with probability $p_1$ there will be two blocks to win back in the future: $$\varphi(1) = p_{-1} + p_0 \varphi(1) + p_1 \varphi(2)\label{ref5}$$ This is random walk that can be depicted on a plane. Now we want to solve \ref{ref5}. How?
The thing is, $\varphi(2)$ is in very simple connection with $\varphi(1)$. And that's why: $(m+1)$ blocks will ever be won back if and only if
  • $m$ blocks will be ever won back
  • $1$ blocks will be ever won back.
For probability of these two elementary outcomes happen, we have to multiply two probabilities (since these outcomes are independent): $\Rightarrow \varphi(m+1) = \varphi(m) \varphi(1)$. By induction immediately \[\varphi(m+1) = \varphi(1)^{m+1}\nonumber\] From $m+1$ we derive $\varphi(2) = \varphi(1)^2$, and equation can be rewritten in the form $$\varphi(1) = p_{-1} + p_0 \varphi(1) + p_1 \varphi(1)^2\nonumber$$ $$ p_1 \varphi(1)^2 + \left( p_0 - 1 \right) \varphi(1) + p_{-1} = 0\nonumber$$ This is quadratic equation. Solving it, one obtains: $$\varphi(1) = \frac{(1-p_0) \pm \sqrt{D}}{2p_1}\nonumber$$ $$D = (1 - p_0)^2 - 4 p_1 p_{-1} = \left( 1 - (1-s)^{\frac{p}{q} + 1} \right)^2 - 4 \frac{p}{q} s^2 (1-s)^{\frac{2p}{q}}\nonumber$$ $$1-p_0 = 1 - \left( 1-s \right)^{\frac{p}{q}+1}\nonumber$$ $$2p_1 = 2 \frac{p}{q} s \left( 1-s \right)^{\frac{p}{q}}\nonumber$$ At this moment, we cannot take limit $s \to 0$: this will lead to <> uncertainty. So there is something to elaborate on. Using well-known Taylor series ($\left(1 + s \right)^{\alpha} = 1 + \alpha s + O(s^2)$), one obtains $$D = \left(1 - 1 + \left(\frac{p}{q} + 1 \right) s - \dots \right)^2 - 4 \frac{p}{q} s^2 = s^2 \left( \left( \frac{p}{q} + 1 \right)^2 - 4 \frac{p}{q} \right) = s^2 \left( \frac{p}{q} - 1 \right)^2 + O(s^3)\nonumber$$ This is the square, so $$\sqrt{D} = s \left| \frac{p}{q} - 1 \right| + o(s)\nonumber$$ Going further, one obtains $$1 - p_0 = 1 - \left( 1-s \right)^{\frac{p}{q} + 1} = \left( \frac{p}{q} + 1 \right) s + O(s^2)\nonumber$$ Abandoning terms of $o(s)$ order, we rewrite the answer as follows: $$\varphi(1) = \frac{ \left(\frac{p}{q} + 1\right) s \pm \left|\frac{p}{q} - 1\right| s }{2\frac{p}{q}s} = \frac{ \left(\frac{p}{q} + 1\right) \pm \left|\frac{p}{q} - 1\right| }{2\frac{p}{q}} = 1; \frac{2}{2\frac{p}{q}} = 1; \frac{q}{p}\nonumber$$
We have received two solutions, which is common situation when you solve a quadratic equation. This is the time of thinking . For problems related to physics, one of mathematically derived solutions appears to be absurd (negative time, or distance for stone fly that is equal to zero), and the rest makes sense and gives true solution for the problem. Let's figure out what happens in our case.
Let $q \ll p$. Then attacker's chances are very little, and "$1$" is clearly incorrect answer, thus $q/p$ is correct. Clearly, $\varphi(1)$ should be smooth continuous function of $q$ and $p$, so no "jumps" allowed. Thus, increasing $q$, for $q$ < $p$ the correct answer will still be $q/p$. When $q$ becomes equal to $p$, same smoothness concept makes answer to be equal to $p/p = 1$. Increasing $q$ even more (case $q>p$), we find out that $q/p$ cannot be the correct answer anymore, since $\varphi(1)$ is the probability, and probability cannot exceed $1$. Thus, for $q>p$ the answer is $1$. (This is clear enough after having a glance at $p_{-1}$, $p_0$, $p_1$ values: when $q>p$, inequality $p_{-1} > p_1$ holds, and value $-1$ will be reached with probability $1$.)

We have calculated the probability $\varphi(1)$ of attacker becoming closer to his goal by one block. Earlier we proved that $\varphi(m+1) = \varphi(1)^{m+1}$, or $\varphi(k) = \varphi(1)^k$. Thus finally $$\varphi(k) = \left\{ \begin{array}{ll} \left(\frac{q}{p}\right)^k, \hskip 20 pt & \text{if} \: q \le p \\ 1, \hskip 20 pt & \text{if} \: q\geqslant p. \end{array} \right.\nonumber$$

Substituting $\varphi(k)$, solution and final analysis

Now when we have found the expression for $\varphi(k)$, substitute it to \ref{ref4} — to the formula for probability of attacker's success. Recall it: $$p_{\text{success}} = 1 - e^{-\lambda} \left( \frac{\lambda^0}{0!} (1 - \varphi(z+1)) + \frac{\lambda^1}{1!} (1 - \varphi(z)) + \dots + \frac{\lambda^z}{z!} (1 - \varphi(1)) \right)\nonumber $$ In situation when $q \geqslant p$, $\varphi(k) = 1$, so $p_{\text{success}} = 1$.
In case $q < p$, as we researched, $\varphi(k) = (q/p)^k$ holds, so $$p_{\text{success}} = 1 - e^{-\lambda} \left( \frac{\lambda^0}{0!} \left(1 - \left(\frac{q}{p}\right)^{z+1} \right) + \frac{\lambda^1}{1!} \left(1 - \left(\frac{q}{p}\right)^{z} \right) + \dots + \frac{\lambda^z}{z!} \left(1 - \frac{q}{p} \right) \right)\nonumber $$ Time to get rid of $\lambda$: $$\begin{eqnarray}p_{\text{success}} = 1 - e^{-z\frac{q}{p}} \left( \left(1 - \left(\frac{q}{p}\right)^{z+1} \right) + z \frac{q}{p} \left(1 - \left(\frac{q}{p}\right)^{z}\right) + \frac{(z \frac{q}{p})^2}{2!} \left(1 - \left(\frac{q}{p}\right)^{z-1} \right) + \dots\nonumber \\ + \frac{(z \frac{q}{p})^z}{z!} \left(1 - \frac{q}{p} \right) \right)\end{eqnarray}\nonumber$$ Grading by powers of $q/p$, $$p_{\text{success}} = 1 - e^{-z\frac{q}{p}} \left( \left(1 - \left(\frac{q}{p}\right)^{z+1} \right) + z \frac{q}{p} \left(1 - \left(\frac{q}{p}\right)^{z} \right) + \frac{(z \frac{q}{p})^2}{2!} \left(1 - \left(\frac{q}{p}\right)^{z-1}\right) + \dots \\ + \frac{(z \frac{q}{p})^z}{z!} \left(1 - \frac{q}{p}\right) \right) = \nonumber $$ $$= 1 - e^{-z\frac{q}{p}} \left( 1 - \left(\frac{q}{p}\right)^{z+1} + z \frac{q}{p} - z\left(\frac{q}{p}\right)^{z+1} + \frac{z^2}{2!} \left(\frac{q}{p}\right)^2 - \frac{z^2}{2!} \left(\frac{q}{p}\right)^{z+1} + \dots \\ + \frac{z^z}{z!} \left(\frac{q}{p}\right)^z - \frac{z^z }{z!} \left(\frac{q}{p}\right)^{z+1} \right) = \nonumber $$ $$= \boxed{ 1 - e^{-z\frac{q}{p}} \left( 1 + z \frac{q}{p} + \frac{z^2}{2!} \left(\frac{q}{p}\right)^2 + \dots + \frac{z^z}{z!} \left(\frac{q}{p}\right)^z - \left(\frac{q}{p}\right)^{z+1} - z \left(\frac{q}{p}\right)^{z+1} - \frac{z^2}{2!} \left(\frac{q}{p}\right)^{z+1} - \dots \\ - \frac{z^z }{z!} \left(\frac{q}{p}\right)^{z+1} \right) } \nonumber$$ Thus, the probability of attack success depends on two parameters: on attacker computational power divided by honest miners' computational power ($q/p$), and on number of confirmations ($z$) — the quantity of blocks vendor waits after incoming transaction has fallen into a block before sending a good.
We'd like to emphasize that this probability is derived only for case when vendor reveals their address right before the payment\que{fortunately, address generation costs nothing, the process can surely be automated, and arbitrary amount of addresses can be generated every second}. If vendor does not regularly change his payment addresses, the following attack is possible: 1) an attacker tries to outrun honest miners' chain by significant amount of blocks; repeat if current try looks unsuccessful 2) attacker sends his buying transaction to the vendor 3) when good is received, broadcast attacker's chain. This attack is successful with probability $1$, i.e. with guarantee.

Let us draw a graph depicting attacker's success probability for different $z$. In Bitcoin, standard recommendation for vendors is $6$ confirmations (some exchanges add coins sent to them to your balance after $3$ confirmations). This $z=6$ curve is dashed. Value $z=120$ is also special: according to current Bitcoin protocol, bitcoins earned as block reward can be spent only after $120$ confirmations. Makes some reason: if you were lucky enough to mine a block, then most probably you have significant share $q/p$, which may make your attempts to attack the network feasible.

This graph passes our sanity check: for $q/p \to 1$ attack success probability tends to one, and for $q/p \to 0$ — tends to zero. Let us make another plot, e.g. for $q/p \approx 0.4$:
This graph shows that sending a good after $z=6$ confirmations makes vendor feel much safer (probability of attack success $\approx$4$\%$) than in cases $z=2$ or $z=3$. These 4$\%$ can be rephrased the following way: in average, in $24$ out of $25$ cases attacker won't succeed, ultimately buying the good, and only in one case out of $25$ he or she will be able to receive it for free.


Popular posts from this blog

Crowdfunding vs ICO: major differences

Marketing ICO case

ICO regulation: Global trends