# Profitable Double-Spending Attacks
## Appendix A  
**Proof of Lemma 1. ** For a given sample \(\omega\) and a given index \(i\), the event \(\omega\in\mathcal{D}^{(1)}_{j}\cap\mathcal{D}^{(2)}_{i,j}\) is equivalent to the event that there exists an intermediate state index \(j\) such that \(\omega\in\mathcal{D}^{(1)}_{j}\cap\mathcal{D}^{(2)}_{i,j}\). By the mutual exclusiveness of \(\mathcal{D}^{(1)}_{j}\cap\mathcal{D}^{(2)}_{i,j}\) for integers \(j\), such a state \(j\) is unique if it exists. Thus, we can write the probability \(p_{DSA,i}\) as follows,  
\[ \begin{array}{ll}p_{DSA,i}&=\Pr\left(\exists j\in\mathbb{N}:\omega\in \mathcal{D}^{(1)}_{j}\cap\mathcal{D}^{(2)}_{i,j}\right)\\ &=\sum\limits_{j=N_{BC}}^{\infty}\Pr\left(\omega\in\mathcal{D}^{(1)}_{j}\cap \mathcal{D}^{(2)}_{i,j}\right).\end{array}  \tag{1}\]Note that \(\mathcal{D}_{j}^{(1)}\cap\left(\mathcal{D}_{i,j}^{(2)}\right)=\phi\) for \(i\leq 2N_{BC}\), since the minimum number of states for an attack success is \(2N_{BC}+1\): \(N_{BC}\) number of \(+1\)'s state transitions for the block confirmation; and \(N_{BC}+1\) number of \(-1\)'s state transitions for the success of PoW competition. Thus, \(p_{DSA,i}=0\) for \(i\leq 2N_{BC}\). We further explore \(\mathcal{D}_{j}^{(1)}\) and \(\mathcal{D}_{i,j}^{(2)}\). We divide the domain of state index \(j\) in Equation (A1) into two exclusive domains; one is \(j\leq 2N_{BC}\); and the other is \(j>2N_{BC}\). First, for \(j\leq 2N_{BC}\), two sets \(\mathcal{D}_{j}^{(1)}\) and \(\mathcal{D}_{i,j}^{(2)}\) are independent, since their requirements on the state transitions are focusing on disjoint indices of state by their definitions. Formally, \(\Pr\left(\omega\in\mathcal{D}_{j}^{(1)}\cap\mathcal{D}_{i,j}^{(2)}\right)= \Pr\left(\omega\in\mathcal{D}_{j}^{(1)}\right)\Pr\left(\omega\in\mathcal{D}_{ i,j}^{(2)}\right)\). Second, we explore the domain \(j>2N_{BC}\). By the definition of \(\mathcal{D}_{j}^{(1)}\), all \(\omega\in\mathcal{D}_{j}^{(1)}\) satisfy \(S_{j}=\sum_{k=1}^{j}\pi_{\Delta_{k}}(\omega)=2N_{BC}-j\). Thus, for every \(j>2N_{BC}\), \(S_{j}\) is already negative, which implies all \(\omega\in\mathcal{D}_{j}^{(1)}\) satisfy both and at state \(j\). The set \(\mathcal{D}_{i,j}^{(2)}=\phi\) for \(j>2N_{BC}\) and \(j<i\), since the state \(S_{j}=2N_{BC}-j\) contradicts one requirement of \(\mathcal{D}_{i,j}^{(2)}\): the interim transitions between the states \(j\) and \(i\) should be non-negative. For \(j>2N_{BC}\) and \(j=i\), let us set \(\mathcal{D}_{i,j}^{(2)}=\Omega\), since there is no interim state to apply the requirement to. To sum up, \(\mathcal{D}_{j}^{(1)}\cap\mathcal{D}_{i,j}^{(2)}=\mathcal{D}_{i}^{(1)}\) for \(j>2N_{BC}\) and \(i=j\), and \(\mathcal{D}_{j}^{(1)}\cap\left(\mathcal{D}_{i,j}^{(2)}\right)=\phi\) for \(j>2N_{BC}\) and \(i>j\). Subsequently, Equation (A1) is computed as  
\[p_{DSA,i}=\sum_{j=N_{BC}}^{2N_{BC}}\Pr\left(\omega\in\mathcal{D}_{j}^{(1)} \right)\Pr\left(\omega\in\mathcal{D}_{i,j}^{(2)}\right)+\Pr\left(\omega\in \mathcal{D}_{i}^{(1)}\right).\] (A2)  
We now compute the ingredient probabilities \(\Pr\left(\omega\in\mathcal{D}_{j}^{(1)}\right)\) and \(\Pr\left(\omega\in\mathcal{D}_{i,j}^{(2)}\right)\) in Equation (A2). First, by the definition, all samples in \(\mathcal{D}_{j}^{(1)}\) must have \(N_{BC}-1\) number of \(+1\)'s state transitions among the first \(j-1\) transitions. And the rest of the \(j-1\) transitions must be valued by \(-1\). In addition, the \(j\)-th transition must be valued by \(+1\) so that the block confirmation is achieved exactly at the \(j\)-th state index. As the result, the probability \(\Pr\left(\omega\in\mathcal{D}_{j}^{(1)}\right)\) equals the point mass function of a negative binomial distribution:  
\[\Pr\left(\omega\in\mathcal{D}_{j}^{(1)}\right)=\left( \begin{array}{c}j-1\\ N_{BC}-1\end{array} \right)p_{H}{}^{N_{BC}}p_{A}{}^{j-N_{BC}}.\] (A3)  
Second, computing the probability \(\Pr\left(\omega\in\mathcal{D}_{i,j}^{(2)}\right)\) starts from counting the number of combinations of state transitions satisfying the requirements of set \(\mathcal{D}_{i,j}^{(2)}\).