# Profitable Double-Spending Attacks
## 2 The Attack Model
### DS Attack Achieving Time  
**Definition 4**. : _For a DS sample \(\omega\) of \(\,\mathrm{DS}(p_{A},t_{cut};N_{BC})\), we define the DSA time \(T_{DSA}\) which measures the least one among the state progression times \(\pi_{T_{i}}(\omega)\) of state indices \(i\) at which \(\omega\) achieves the necessary conditions \(\mathcal{G}^{(1)}\) and \(\mathcal{G}^{(2)}\) in Definition 1._  
To express \(T_{DSA}\) as a random variable, we construct event sets \(\mathcal{D}^{(1)}_{j}\subset\Omega\) and \(\mathcal{D}^{(2)}_{i,j}\subset\Omega\). The sets \(\mathcal{D}^{(1)}_{j}\) for \(j\in\{N_{BC},N_{BC}+1,\cdots,\infty\}\) consist of DS samples \(\omega\) which achieves the block confirmation \(\mathcal{G}^{(1)}\) at state \(j\) for the first time. The sets \(\mathcal{D}^{(2)}_{i,j}\) for \(i\in\{j,j+1,\cdots,\infty\}\) and \(j\in\{N_{BC},N_{BC}+1,\cdots,\infty\}\) consists of \(\omega\) which achieves the success in the PoW competition \(\mathcal{G}^{(2)}\) at state \(i\) for the first time, given that \(\mathcal{G}^{(1)}\) has been already achieved at state \(j\). Subsequently, we aim for the samples \(\omega\in\mathcal{D}^{(1)}_{j}\cap\mathcal{D}^{(2)}_{i,j}\) to achieve the two conditions in Definition 1 at a state pair \((i,j)\) for the first time. Formally, we first construct a set \(\mathcal{D}^{(1)}_{j}\) focusing only on the first \(j\) transitions \(\Delta_{k}\) for \(k=1,\cdots,j\) of DS samples \(\omega\in\Omega\) with two requirements; one is that they must have \(N_{BC}\) number of \(+1\)'s and \(j-N_{BC}\) number of \(-1\)'s; and the other is that the \(j\)-th transition \(\Delta_{j}\) must be \(+1\) to guarantee that they have never been achieved in any states prior to the state \(j\). The former requirement implies that all \(\omega\in\mathcal{D}^{(1)}_{j}\) hold \(S_{j}=\sum_{k=1}^{j}\pi_{\Delta_{i}}(\omega)=2N_{BC}-j\). For example, when \(N_{BC}=2\) and \(j=5\), a sequence \((+1,-1,-1,-1,+1,\cdots)\) of state transitions satisfies the first requirement, and also satisfies \(S_{j}=2N_{BC}-j\). We next construct a set \(\mathcal{D}^{(2)}_{i,j}\subset\Omega\) which does not care about the first \(j\) transitions \(\Delta_{k}\) for \(k=1,\cdots,j\), but only focuses on the interim transitions \(\Delta_{m}\) for \(m=j+1,\cdots,i\). By the definition, all sequences \(\omega\in\mathcal{D}^{(2)}_{i,j}\) must achieve \(\mathcal{G}^{(1)}\) before the \(j\)-th state, which implies that they must hold \(S_{j}=2N_{BC}-j\). The rest requirement for each \(\omega\in\mathcal{D}^{(2)}_{i,j}\) is that the state changes from starting state \(S_{j}=2N_{BC}-j\) to state \(S_{i}=-1\), while any interim states \(S_{k}\) remain non-negative; i.e., \(S_{k}\geq 0\) for each \(k=j+1,\cdots,i-1\). The sets \(\mathcal{D}^{(1)}_{j}\) for all \(j\) are mutually exclusive as each of them represents the first satisfaction of the block confirmation condition exactly at the \(j\)-th state. For example, if \(\omega\in\mathcal{D}^{(1)}_{5}\) then \(\omega\
otin\mathcal{D}^{(1)}_{6}\) since \(\omega\) already has achieved the block confirmation at the \(5\)-th state for the first time before reaching the \(6\)-th state. The sets \(\mathcal{D}^{(2)}_{i,j}\) for all \((i,j)\) are also mutually exclusive for the same reason. Thus, their intersections \(\mathcal{D}^{(1)}_{j}\cap\mathcal{D}^{(2)}_{i,j}\) for all \((i,j)\) are also mutually exclusive. By Definition 4, the attack achieving time \(T_{DSA}\) can be measured if there exist index pairs \((i,j)\) such that \(\omega\in\mathcal{D}^{(1)}_{j}\cap\mathcal{D}^{(2)}_{i,j}\). By the mutual exclusivity of \(\mathcal{D}^{(1)}_{j}\cap\mathcal{D}^{(2)}_{i,j}\), if there exists such a pair \((i,j)\), it must be unique. In addition, if \(\omega\in\mathcal{D}^{(1)}_{j}\cap\mathcal{D}^{(2)}_{i,j}\), \(T_{DSA}\) equals \(\pi_{T_{i}}(\omega)\), since the state progression time \(T_{k}\) is non-decreasing as \(k\) increases. As the result, \(T_{DSA}\) can be rewritten as follows,  
\[T_{DSA}=