# Profitable Double-Spending Attacks
## 2 The Attack Model
### Stochastic Model  
We model the conditions in Definition 2 with a stochastic model. We fit the block generation process using the PCP [22] with a given block generation rate \(\lambda\) (blocks per second). Including [PERSON] [1] and [PERSON] [6], it has been most conventional to analyze the block generation process of a blockchain using PCP. A rationale why the block generation process is modeled as PCP is given in [PERSON] et al. [23], where experiments show the fitness of PCP model to real data samples from a live network.  
We denote the lengths of the honest chain and the fraudulent chain over time \(t\in(0,\infty]\) by two independent PCPs, \(H(t)\in\mathbb{N}_{0}\) with the block generation rate \(\lambda_{H}\) (blocks per second) and \(A(t)\in\mathbb{N}_{0}\) with the block generation rate \(\lambda_{A}\), respectively. Both processes start at the time origin \(t=0\) (at which the DS attack is launched) at which the both chains are at the zero states, i.e., \(H(0)=A(0)=0\). Each chain independently increases at most by \(1\) at a time point. An increment of \(1\) in the counting process occurs when the pertinent network adds a new block to its chain.  
We represent the difference between \(A(t)\) and \(H(t)\) in a discrete-time domain as a random walk \(S_{i}\in\mathbb{Z}\) for \(i\in\mathbb{N}\). For this purpose, we first define two continuous stochastic processes \(M(t)\) and \(S(t)\), which are respectively defined as  
\[M(t):=H(t)+A(t), \tag{1}\]  
and  
\[S(t):=H(t)-A(t). \tag{2}\]  
The first process \(M(t)\) is also a PCP [22] with the rate  
\[\lambda_{T}:=\lambda_{A}+\lambda_{H}. \tag{3}\]  
The second process \(S(t)\) is the continuous-time analog of the random walk \(S_{i}\in\mathbb{Z}\) for \(i\in\mathbb{N}\) such that  
\[S_{i}:=S(T_{i}), \tag{4}\]  
where \(T_{i}\) is the state progression time defined by  
\[T_{i}:=\inf\Bigl{\{}\,t\in\mathbb{R}^{+}:M(t)=i\,\Bigr{\}}, \tag{5}\]  
which increases as \(i\) increases. Random walk \(S_{i}\) is a stationary Markov chain starting from \(S_{0}=0\). The state transition probabilities [22] are given by  
\[p_{A}:=\Pr(S_{i}=n-1|S_{i-1}=n)=\frac{\lambda_{A}}{\lambda_{T}}, \tag{6}\]  
and  
\[p_{H}:=\Pr(S_{i}=n+1|S_{i-1}=n)=\frac{\lambda_{H}}{\lambda_{T}}, \tag{7}\]  
for all \(i\in\mathbb{N}\) and \(n\in\mathbb{Z}\). The state transition probabilities \(p_{H}\) and \(p_{A}\) are the proportions of computing power occupied by the normal miners and that by the attacker, respectively.  
We define independent and identically distributed (i.i.d.) state transition random variables \(\Delta_{i}\in\{\pm 1\}\sim\text{Bernoulli}(p_{H})\) as  
\[\Delta_{i}:=S_{i}-S_{i-1}, \tag{8}\]  
for \(i\in\mathbb{N}\). Note that \(S_{i}=\sum_{k=0}^{i}\Delta_{k}\).  
**Definition 3**.: _A DS attack \(\text{DS}(p_{A},t_{cut};N_{\text{BC}})\) is a random experiment that picks a sample \(\omega\in\Omega\). Each element \(\omega\) is an infinite-length sequence of pairs of \(T_{i}\) and \(\Delta_{i}\) in Equations (5) and (8) for all \(i\in\mathbb{N}\), i.e.,_  
\[\omega:=((T_{1},\Delta_{1}),(T_{2},\Delta_{2}),\cdots,(T_{\infty},\Delta_{ \infty})). \tag{9}\]  
The set \(\Omega\) is the universal set of all possible \(\omega\), i.e.,  
\[\Omega:=\Bigl{\{}\omega\in\Bigl{\{}\mathbb{R}^{+}\times\{\pm 1\}\Bigr{\}}^{ \infty}\Bigr{\}}. \tag{10}\]  
For given a DS sample \(\omega\in\Omega\) and a state index \(i\in\mathbb{N}\), we denote projections  
\[\pi_{T_{i}}(\omega):=T_{i} \tag{11}\]  
and  
\[\pi_{\Delta_{i}}(\omega):=\Delta_{i} \tag{12}\]  
that retrieve the progression time \(T_{i}\) and the transition \(\Delta_{i}\) of the \(i\)-th state, respectively.