# Resilience Analysis for Double Spending via Sequential Decision Optimization
## 3 The Double-Spending Problem  
Let us briefly discuss the classical results before we elaborate on our contribution. In the framework of the double-spending problem, it is assumed that a continuous-time Markov chain taking values in \(\mathbb{Z}\) describes the difference in blocks between official and secret branches. As in [3], we consider this process at time points at which new block in one of the branches is completed, which yields a discrete-time Markov chain \((Z_{t})_{t=0}^{\infty}\). Having started secret mining after the block including the attacker's payment (at block time \(t=0\), \(Z_{0}=0\)) the attacker considers the following situation: At each time \(t=1,2,3\dots\), a new block in one of the branches (official or secret) is found, the block difference changes  
\[\mathbb{P}(Z_{t}=z+1\,|Z_{t-1}=z) =1-q,\] \[\mathbb{P}(Z_{t}=z-1\,|Z_{t-1}=z) =q,\]  
where \(q\in]0,1[\) is the ratio of the computational power controlled by the attacker to the total mining capacity. Let us agree on the generic case where the attacker controls a smaller part of the mining power \(0<q<1/2\) than that controlled by honest miners. In this case, if at any block time \(t=0,1,2,\dots\) the block difference is \(z\in\mathbb{Z}\), then the probability \(a_{\infty}(z,q)\) that the secret branch overtakes the official branch within an unlimited time after \(t\) is given by  
\[a_{\infty}(z,q)=\mathbb{P}(\min_{u=0}^{\infty}Z_{u}<0\,|\,Z_{0}=z)=\left\{ \begin{array}{cl}1&\text{if }z<0,\\ (\frac{q}{1-q})^{z+1}&\text{otherwise.}\end{array} \right. \tag{1}\]Furthermore, at a time when the \(n\)-th block in the official branch is mined, the probability that the attacker has mined \(m=0,1,2,\dots\) blocks follows the _negative binomial distribution_ whose distribution function is given by  
\[F_{q,n}(m)=\sum_{j=0}^{m}\binom{n+j-1}{j}(1-q)^{n}q^{j},\qquad m=0,1,2,\dots. \tag{2}\]  
Both results (1) and (2) are combined in [3] to obtain the success probability of the double spending as follows: Consider the situation where the attack starts when the length difference between the official and the secret branches is \(k\in\mathbb{Z}\) with \(k\geq-n\). Consider first the situation that at the time the \(n\)-th block in the official chain is completed, the attacker has mined \(m\) blocks with \(m-k>n\) in which case the secret branch can be published immediately. The probability of this event is given by  
\[\sum_{m=n+k+1}^{\infty}\binom{n+m-1}{m}(1-q)^{n}q^{m}=1-F_{q,n}(n+k).\]  
Next, consider the opposite event, assuming that when the \(n\)-th official block is completed, the attacker has not overtaken the official chain in which case \(m-k\leq n\). In this case, the probability of winning the race is given by  
\[\sum_{m=0}^{n+k}\binom{n+m-1}{m}(1-q)^{n}q^{m}a_{\infty}(n+k-m,q)=\] \[= (\frac{q}{1-q})^{1+k}\sum_{m=0}^{n+k}\binom{n+m-1}{m}(1-q)^{m}q^ {n}\] \[= (\frac{q}{1-q})^{1+k}F_{1-q,n}(n+k).\]  
Clearly, the total success probability of the double spending is given by the sum of its probabilities in both cases and equals to  
\[ \begin{array}{l}r_{q,n}(k)=1-F_{q,n}(n+k)+(\frac{q}{1-q})^{1+k}F_{1-q,n}(n+k )\\ \text{for }n\in\mathbb{N},\,k\in\mathbb{Z},\,k\geq-n,\,\text{and}\,\,q\in]0, \frac{1}{2}[.\end{array}  \tag{3}\]  
For instance, consider the situation that the attacker starts the fork-off and launches the payment at the same time, then \(k=0\) and if the merchant waits for \(n=6\) confirming blocks, then the attacks succeeds with probabilities \(r_{q,n=6}(k=0)\) which are relatively small if the attacker controls a small part (six \(q=0.06\) or eight \(q=0.08\) percent) of the mining capacity:  
\[r_{0.06,6}(0)=0.00037,\qquad r_{0.08,6}(0)=0.0025\]  
As a result, waiting for six blocks after the payment has been considered to be secure in the sense that with realistic efforts, it is practically impossible to succeed with double spending. **Remark 2**.