2. The PDF of the double-spending time

In this section, the length of the honest chain $\{z+N(t),\, t\geq0\}$ is governed by an OSPP. Its jump times, provided that $N(t)=n$ , have the same joint distribution as a vector of order statistics. Namely, it holds that

$$[T_1,\ldots,T_{n}\ \,\,|\, \ \, N(t)=n]\stackrel{\text{D}}{=} (V_{1\colon n},\ldots,V_{n\colon n}),$$

where ‘ $\stackrel{\text{D}}{=} $ ’ stands for equality in distribution and $V_{1\colon n},\ldots,V_{n\colon n}$ correspond to the order statistics of n i.i.d. random variables having a cumulative distribution function (CDF) $F_{t}(s)$ , for $0\leq s\leq t$ . The length of the malicious chain is a renewal process generated by a sequence of i.i.d. interarrival times $\{\Delta^{S}_{k}\text{ , }k\geq1\}$ having a PDF denoted by $f_{\Delta^{S}}$ . The sequence of arrival times $\{S_{n}\text{ , }n\in\mathbb{N}\}$ , with the convention $S_0=0$ , corresponds to the partial sums of the interarrival times sequence. The PDF of $S_{n}$ , for $n\in\mathbb{N}$ , is given by

$f_{S_{n}}(t)=f^{\ast n}_{\Delta^{S}}(t) \quad\text{for }t\geq0,$

where $f^{\ast n}$ denote the n-fold convolution of $f_{\Delta^{S}}$ with itself. Let $z\geq1$ be an integer, the following result gives a formula for the PDF of

$$ \tau_{z}=\inf\{t\geq0;\, M(t)=N(t)+z\}, $$

the time at which the double-spending attack is completed.

Theorem 1. If $\{N(t),\, t\geq0\}$ is an OSPP and $\{M(t),\, t\geq0\}$ is a renewal process, then the PDF of $\tau_z$ is given by

(1) \begin{equation} f_{\tau_z}(t)=\mathbb{E}[(\!-\!1)^{N(t)}h_{N(t)}(t,z) f_{\Delta^{S}}^{\ast[N(t)+z]}(t)], \qquad t\geq0, \label{eqn1} \end{equation}

where

(2) \begin{equation} h_n(t,z)=\mathbb{E}\{G_{n}[0\ \,\,|\, \ \, F_{t}(S_{z}),\ldots,F_{t}(S_{n+z-1})]\ \,\,|\, \ \, S_{n+z}=t \}, \label{eqn2} \end{equation}

and $G_n(0\ \,\,|\, \ \, .)$ is an A-G polynomial such as defined in Appendix A.

Proof. The event $\{\tau_z\in(t,t+\text{d}t)\}$ for $t\geq0$ corresponds to the exact time at which the double-spending attack is successful as the malicious chain takes over the honest chain. At time $t=0$ , the honest chain is ahead by $z\geq 1$ blocks. Assuming that later, at time $t>0$ , the honest miners manage to add $N(t)=n\in\mathbb{N}$ blocks to the chain, then the malicious chain must be of length $M(t^{-})=n+z-1$ at some time $t^{-}<t$ and jumps to the level $n+z$ exactly at t. Conditioning over the values of $\{N(t),\, t\geq0\}$ yields

$\{\tau_z\in(t,t+\text{d}t)\}=\bigcup_{n=0}^{+\infty}\{\tau_z\in(t,t +\text{d}t)\}\cap\{N(t)=n\}.$

In the case where $N(t)=0$ , the only requirement is that the zth jump of $\{M(t),\, t\geq0\}$ occurs at time t. It then follows that

$\{\tau_z\in(t,t+\text{d}t)\}\cap\{N(t)=0\}=\{S_{z}\in(t,t+\text{d}t)\} \cap\{N(t)=0\}$

and, consequently,

$f_{\tau_z\ \,\,|\, \ \, N(t)=0}(t)=f^{\ast z}_{\Delta^{S}}(t), \qquad t\geq0,$

where $\smash{f_{\tau_z\ \,\,|\, \ \, N(t)=0}(t)}$ denotes the conditional PDF of $\tau_z$ given that $N(t)=0$ . On the set $\{N(t)\geq1\}$ we need to make sure that $\{M(t),\, t\geq0\}$ behaves properly by constraining its jump times so that it does not reach $N(s)+z$ at any time $s<t$ and performs the $(n+z)$ th jump at t. Hence, it holds that

\begin{equation*} \{\tau_z\in(t,t+\text{d}t)\}\cap\{N(t)\geq1\}=\bigcup_{n=1}^{+\infty} \bigcap_{k=1}^{n}\{T_k\leq S_{z+k-1}\}\cap\{S_{z+n}\in(t,t+\text{d}t)\}\cap\{N(t)=n\}. \end{equation*}

Applying the law of total probability yields

(3) $$\mathbb{P}[\{\tau_z\in(t,t+\text{d}t)\}\cap\{N(t)\geq1\}] \nonumber\\ \qquad= \sum_{n=1}^{+\infty}\mathbb{P}\bigg[\bigcap_{k=1}^{n}\{T_k\leq S_{z+k-1}\}\cap\{S_{z+n}\in(t,t+\text{d}t)\}\biggm| N(t)=n\bigg]\mathbb{P}[N(t)=n].$$

By virtue of the order statistic property, the successive jump times $(T_1,\ldots,T_n)$ are distributed as the order statistics $(V_{1: n},\ldots,V_{n: n})$ of a sample of n i.i.d. random variables with CDF $F_t(s),\text{ }0\leq s\leq t$ . The conditional probability in (3) may be rewritten as

(4) \begin{align} &\mathbb{P}\biggl[\bigcap_{k=1}^{n}\{V_{k: n}\leq S_{z+k-1}\} \cap\{S_{z+n}\in(t,t+\text{d}t)\}\biggr]\nonumber \\ &\qquad=\mathbb{P}\biggl[\bigcap_{k=1}^{n}\{U_{k: n}\leq F_{t}(S_{z+k-1})\}\cap\{S_{z+n}\in(t,t+\text{d}t)\}\biggr]\nonumber \\ &\qquad=\mathbb{P}\biggl[\bigcap_{k=1}^{n}\{U_{k: n}\leq F_{t}(S_{z+k-1})\}\ \,\,|\, \ \, S_{z+n}\in(t,t+\text{d}t)\biggr]\mathbb{P}[S_{z+n}\in(t,t+\text{d}t)] \nonumber \\ &\qquad=\mathbb{E}\{(-1)^{n}G_{n}[0\ \,\,|\, \ \, F_{t}(S_{z}),\ldots,F_{t}(S_{z+n-1})] \ \,\,|\, \ \, S_{z+n}\in(t,t+\text{d}t)\}\mathbb{P}[S_{z+n}\in(t,t+\text{d}t)], \label{eqn4}\end{align}

where $U_{1: n},\ldots,U_{n: n}$ denote the order statistics of a sample of n i.i.d. uniform random variables on [0,1], and $G_n(.\ \,\,|\, \ \, .)$ correspond to the sequence of A-G polynomials as defined in the Appendix A. Inserting 4 into 3 and letting $\text{d}t$ be small enough yields

\begin{align*} f_{\tau_z\ \,\,|\, \ \, N(t)\geq1}(t)&=\sum_{n=1}^{+\infty}\mathbb{E} \{(\!-\!1)^{n}G_{n}[0\ \,\,|\, \ \, F_{t}(S_{z}),\ldots,F_{t}(S_{z+n-1})] \ \,\,|\, \ \, S_{z+n}=t\} \\ & \times f_{S_{z+n}}(t)\mathbb{P}[N(t)=n]. \end{align*}

The final step consists in noting that $G_0(x)=1$ for every $x\in\mathbb{R}$ , and writing

(5) \begin{equation} f_{\tau_z}(t)=\sum_{n=0}^{+\infty}\mathbb{E}\{(\!-\!1)^{n}G_{n} [0\vert F_{t}(S_{z}),\ldots,F_{t}(S_{z+n-1})] \vert S_{z+n}=t\}f_{\Delta^{S}}^{\ast (z+n)}(t)\mathbb{P}[N(t)=n], \label{eqn5} \end{equation}

which is equivalent to 1.

The stopping time $\tau_z$ may be interpreted as the first meeting time of the OSPP $\{N(t),\, t\geq0)\}$ and the lower randomized boundary defined by $\{M(t)-z,\, t\geq0\}$ . This remark explains why Theorem 1 is reminiscent of the results given in [Reference Goffard and Lefèvre17, Proposition 3.1] and [Reference Goffard and Lefèvre18, Theorem 3.1], where the first-meeting problem of an OSPP with a lower deterministic boundary was handled. The numerical evaluations of 1, to compute, for instance, the probability that the double-spending attack succeeds within a fixed time period, looks challenging. A method based on the truncation of the infinite series in 5 coupled with a numerical integration routine, in the same vein as proposed in [Reference Borovkov and Dickson4], can be put together. The next result shows how 1 may be simplified when $\{N(t),\,t\geq0\}$ is a mixed Poisson process.

Corollary 1. If $\{N(t),\, t\geq0\}$ is a mixed Poisson process then the PDF of $\tau_z$ is given by

(6) \begin{equation} f_{\tau_z}(t)=\mathbb{E}\bigg[\frac{z}{z+N(t)}f_{\Delta^{S}}^{\ast[N(t)+ z]}(t)\bigg] \quad\text{for }t\geq0. \label{eqn6} \end{equation}

Proof. As $\{N(t),\, t\geq0\}$ is a mixed Poisson process then we can apply Theorem 1 replacing $F_t(s)$ by $s/t$ for $s\leq t$ . The function $h_n(t,z)$ defined in 2 becomes

\begin{equation*} h_n(t,z)=\mathbb{E}\bigg\{\frac{1}{t^{n}}G_{n} (0\ \,\,|\, \ \, S_{z},\ldots,S_{n+z-1})\ \,\,|\, \ \, S_{n+z}=t \bigg\}, \end{equation*}

after applying identity 45. Conditioning upon the values of $S_z$ , and applying successively the identities 45 and 47 leads to

(7) \begin{align} &h_n(t,z)\nonumber \\ &\qquad=\frac{1}{t^{n}}\mathbb{E}\{\mathbb{E}[G_{n} (0\ \,\,|\, \ \, S_z,\ldots,S_{n+z-1})\ \,\,|\, \ \, S_z,S_{n+z}]\ \,\,|\, \ \, S_{n+z}=t \}\nonumber \\ &\qquad=\frac{1}{t^{n}}\mathbb{E}\biggl\{\mathbb{E}\biggl[G_{n} \biggl(-S_z\ \,\,|\, \ \, 0,\Delta^{S}_{z+1}\ldots,\sum_{k=1}^{n-1}\Delta^{S}_{z+k}\biggr) \Biggm| \sum_{k=1}^{n}\Delta^{S}_{z+k}=S_{n+z}-S_z\biggr]\ \,\,|\, \ \, S_{n+z}=t \biggr\}\nonumber \\ &\qquad=\frac{1}{t^{n}}\mathbb{E}\{(-S_z)[-S_z-(S_{n+z}-S_z)]^{n-1} \ \,\,|\, \ \, S_{n+z}=t \}\nonumber \\ &\qquad=\frac{(\!-\!1)^{n}}{t^{n}}\mathbb{E}[S_{z}(S_{z+n})^{n-1}\ \,\,|\, \ \, S_{n+z}=t ]\nonumber \\ &\qquad=(\!-\!1)^{n}\frac{z}{n+z}. \label{eqn7}\end{align}

Substituting (7) into (1) yields (6).

The formula given in Corollary 1 is reminiscent of the first-hitting time theorem and also the so-called Kendall identity (see, for instance, [Reference Borovkov and Burq3]), which gives the PDF of the first-meeting time of a spectrally negative Lévy process with a lower linear boundary. The following example leads to an expression for the PDF of $\tau_z$ that allows the evaluation of the probability of a successful double-spending attack $\mathbb{P}[\tau_z<\infty]$ .

Example 1 Assume that the length of the chains $\{z+N(t),\, t\geq0\}$ and $\{M(t),\, t\geq0\}$ are governed by two homogeneous Poisson processes of intensity $\lambda$ and $\mu,$ respectively. The interarrival times $\{\Delta^{S}_{k},\, k\geq1\}$ are i.i.d. exponential random variables with parameter $\mu$ and associated PDF

$$f_{\Delta^{S}}(x)=\mu \mathrm{e}^{-\mu x} \quad\text{for }x\geq0.$$

Applying Corollary 1 yields, after a couple of rearrangements, the following expression for the PDF of $\tau_z$ ,

(8) \begin{equation} f_{\tau_z}(t)=\sum_{n=0}^{+\infty}\bigg(\frac{z}{z+n}\bigg) \binom{2n+z-1}{n}\bigg(\frac{\mu}{\mu+\lambda}\bigg)^{n+z} \bigg(\frac{\lambda}{\mu+\lambda}\bigg)^{n}\frac{(\lambda+\mu)^{2n+z} t^{2n+z-1}\mathrm{e}^{-t(\mu+\lambda)}}{\Gamma(2n+z)} \label{eqn8} \end{equation}

for $t\geq0$ . Assuming that $\lambda> \mu$ and integrating 8 with respect to t yields the probability of successful double-spending attack with

(9) $$\mathbb{P}[\tau_z<\infty] =\sum_{n=0}^{+\infty}\bigg(\frac{z}{z+n}\bigg) \binom{2n+z-1}{n}\bigg(\frac{\mu}{\mu+\lambda}\bigg)^{n+z} \bigg(\frac{\lambda}{\mu+\lambda}\bigg)^{n} \nonumber \\ =\bigg(\frac{\lambda+\mu}{\lambda}\bigg)^{z}z\sum_{n=0}^{+\infty} \binom{2n+z-1}{n}\bigg(\frac{1}{z+n}\bigg)\bigg[\frac{\lambda\mu} {(\mu+\lambda)^{2}}\bigg]^{n+z}\nonumber \\ =\bigg(\frac{\lambda+\mu}{\lambda}\bigg)^{z}z\sum_{n=0}^{+\infty} \binom{2n+z-1}{n}\int_{0}^{{\lambda\mu}/{(\mu+\lambda)^{2}}}t^{n+z- 1}\text{d}t\nonumber \\ =\bigg(\frac{\lambda+\mu}{\lambda}\bigg)^{z}z\sum_{n=0}^{+\infty} \binom{2n+z-1}{n}\int_{0}^{{\lambda\mu}/{(\mu+\lambda)^{2}}}t^{n+z- 1}\text{d}t\nonumber \\ =\bigg(\frac{\lambda+\mu}{\lambda}\bigg)^{z}z\int_{0}^{{\lambda\mu}/ {(\mu+\lambda)^{2}}}t^{z-1}\sum_{n=0}^{+\infty}\binom{2n+z-1}{n}t^{n} \text{d}t\nonumber \\ =\bigg(\frac{\lambda+\mu}{\lambda}\bigg)^{z}z\int_{0}^{{\lambda\mu}/ {(\mu+\lambda)^{2}}}t^{z-1}\frac{C(t)^{z-1}}{\sqrt{1-4t}\,}\text{d}t,$$

where

(10) \begin{equation} C(t)=\frac{1-\sqrt{1-4t}}{2t}, \label{eqn10} \end{equation}

denotes the generating function of Catalan’s numbers; see, for instance, [Reference Aigner1, Chapter 3]. Note that the last equality follows from an exercise in the textbook of Aigner [1, Exercise 3.25]. Inserting 10 into 9 yields, after straightforward integration,

\begin{equation*} \mathbb{P}[\tau_z<+\infty]=\bigg(\frac{\mu}{\lambda}\bigg)^{z}. \end{equation*}

The result given above is consistent with Corollary 3; see Section 4.

3. The SF of the double-spending time

In this section, the length of the honest and the malicious chains are governed by two independent OSPPs. The order statistic property satisfied by $\{M(t),\, t\geq0\}$ implies that

\begin{equation*} [S_{1},\ldots,S_{m}\ \,\,|\, \ \, M(t)=m]\stackrel{\text{D}}{=} (V^{\ast}_{1: m},\ldots,V^{\ast}_{m: m}), \end{equation*}

where $V^{\ast}_{1: m},\ldots,V^{\ast}_{m: m}$ denote the order statistics of a sample $V^{\ast}_{1},\ldots,V^{\ast}_{m}$ of m i.i.d. random variables having a CDF $F_{t}^{\ast}(s)$ for $0\leq s\leq t$ . Note that, regarding $\{N(t),\, t\geq0\}$ , the notation of Section 2 is preserved. The following result gives a formula in terms of Appell polynomials for the SF of $\tau_z=\inf\{t\ge0,\, M(t)=N(t)+z\}.$

Theorem 2. If $\{N(t),\, t\geq0\}$ and $\{M(t),\, t\geq0\}$ are two OSPPs, then the SF of $\tau_z$ is given by

(11) \begin{equation} \mathbb{P}[\tau_z>t]=\mathbb{E}(A_{M(t)}\{1\ \,\,|\, \ \, 0,\ldots, 0,F_{t}^{\ast}[V_{1\colon N(t)}],\ldots,F_{t}^{\ast}[V_{M(t)+1-z: N(t)}]\} {\bf 1}_{M(t)\leq N(t)+z-1}\!) \label{eqn11} \end{equation}

for $t\geq0$ , where $A_{n}(1\ \,\,|\, \ \, .)$ is an Appell polynomial such as defined in Appendix A.

Proof. If $M(t)\geq N(t)+z$ , at time $t\geq0$ , then the double-spending attack already occured. Consider the event $\{\tau_z>t\}$ , conditioning upon the possible values of the counting processes leads to

$$\{\tau_z>t\}=\bigcup_{n=0}^{+\infty}\bigcup_{m=0}^{n+z-1}\{\tau_z>t\} \cap\{N(t)=n\}\cap\{M(t)=m\}.$$

The double-spending attack did not happen before time $t\geq0$ if M(t) is smaller or equal to $z-1$ , irrespective of the value of N(t). If M(t) falls between z and $N(t)+z$ then N(t) must have jumped, at least once, and an investigation over the jump times of both point processes must be conducted. The event $\{\tau_z>t\}$ is further rewritten as

$$\{\tau_z>t\}=\bigcup_{m=0}^{z-1}\{M(t)=m\} \cup\bigcup_{n=1}^{+\infty}\bigcup_{m=z}^{n+z-1}\bigcap_{k=z}^{m} \{S_k>T_{k+1-z}\}\cap\{N(t)=n\}\cap\{M(t)=m\}.$$

The law of total probability yields

(12) $$ \mathbb{P}[\tau_z>t]\nonumber \\ \qquad=\mathbb{P}[M(t)\leq z-1] +\sum_{n=1}^{+\infty}\sum_{m=z}^{n+z-1}\mathbb{P} \bigg[\bigcap_{k=z}^{m}\{S_k>T_{k+1-z}\}\biggm| N(t)=n,M(t)=m\bigg]\nonumber \\ \times\mathbb{P}[N(t)=n,M(t)=m].$$

Now, by the order statistic property, it holds that

\[ [(T_{1},\ldots,T_{m+1-z})\ \,\,|\, \ \, N(t)=n]\stackrel{\text{D}}{=} (V_{1\colon n},\ldots,V_{m+1-z\colon n}) \]

and

\[ [(S_{z},\ldots,S_{m})\ \,\,|\, \ \, M(t)=m]\stackrel{\text{D}}{=} (V^{\ast}_{z\colon m},\ldots,V^{\ast}_{m\colon m}). \]

Therefore, the conditional probability in 12 may be rewritten as

(13) \begin{align} \mathbb{P}\bigg[\bigcap_{k=z}^{m}\{V^{\ast}_{k: m}>V_{k+1-z: n}\}\bigg]&=\mathbb{P}\bigg[\bigcap_{k=z}^{m}\{U_{k\colon m}>F^{\ast}_{t}(V_{k+1-z: n})\}\bigg]\nonumber \\ &=A_m[1\ \,\,|\, \ \, 0,\ldots,0,F^{\ast}_{t}(V_{1: n}),\ldots,F^{\ast}_{t}(V_{m+1-z: n})], \label{eqn13}\end{align}

where $U_{1: m},\ldots,U_{m: m}$ are the order statistics of a sample of m i.i.d. uniform random variables on (0,1) and $A_m(.\ \,\,|\, \ \, .)$ denote the Appell polynomials defined in Appendix A. Inserting 13 into 12 yields

(14) \begin{align} \mathbb{P}[\tau_z>t] &=\mathbb{P}[M(t)\leq z] +\sum_{n=1}^{+\infty}\sum_{m=z}^{n+z-1}A_m[1\ \,\,|\, \ \, 0,\ldots, 0,F^{\ast}_{t}(V_{1: n}),\ldots,F_{t}^{\ast}(V_{m+1-z: n})]\nonumber \\ &\times \mathbb{P}[N(t)=n,M(t)=m], \label{eqn14}\end{align}

which is the same as 11 after noting that $A_{m}(1\ \,\,|\, \ \, 0,\ldots,0)=1$ for every $m\in\mathbb{N}$ .

In Subsection 5.2 a Monte Carlo evaluation of the expectation of (11) is performed. This type of estimator has been studied in [Reference Goffard and Lefèvre17, Section 6] and named Appell polynomial Monte Carlo (APMC). The procedure entails a variance reduction in comparison to a crude Monte Carlo evaluation. The following result shows how (11) may be simplified by setting $z=1$ , when the OSPPs are similar in a sense detailed below.

Corollary 2. Assume that $z=1$ . If $\{N(t),\, t\geq0\}$ and $\{M(t),\, t\geq0\}$ are two OSPPs such that $F_t(s)=F_{t}^{\ast}(s)$ for every $s\leq t,$ then the SF of $\tau_z$ is given by

(15) \begin{equation} \mathbb{P}[\tau_z>t]=\mathbb{E}\bigg(\frac{N(t)-M(t)+1}{N(t)+1} {\bf 1}_{M(t)\leq N(t)}\!\bigg) \quad\text{for }t\geq0. \label{eqn15} \end{equation}

Proof. Let $\{N(t),\, t\geq0\}$ and $\{M(t),\, t\geq0\}$ be two OSPPs such that $F_t(s)=F_{t}^{\ast}(s)$ for every $s\leq t$ . Applying Theorem 2, with $z=1$ , yields

\begin{equation*} \mathbb{P}[\tau_z>t]=\mathbb{E}(A_{M(t)}\{1\ \,\,|\, \ \, U_{1: N(t)},\ldots,U_{M(t): N(t)}\}{\bf 1}_{M(t)\leq N(t)}\!) \quad\text{for }t\geq0. \end{equation*}

Recall the probabilistic interpretation of the Appell polynomial in Proposition 1 with

\begin{equation*} \mathbb{P}[\tau_z>t]=\mathbb{E}(\mathbb{P}[U^{\ast}_{1: M(t)}> U_{1: N(t)},\ldots,U^{\ast}_{M(t): M(t)}>U_{M(t): N(t)}\}{\bf 1}_{M(t)\leq N(t)}\!) \end{equation*}

for $t\geq0$ . Applying Bertrand’s ballot theorem, allowing for ties, yields (15).

The case treated in the numerical illustrations considers that the length of the chains are governed by two nonhomogeneous Poisson processes, which is consistent with the empirical study conducted in [Reference Bowden, Keeler, Krzesinski and Taylor8], as explained in the following example.

Example 2. Bowden et al. [Reference Bowden, Keeler, Krzesinski and Taylor8] recommended modeling the arrival of blocks as a nonhomogeneous Poisson process with an intensity function designed to capture the evolution of the global hashrate on one hand and the difficulty adjustment of the cryptopuzzles on the other hand. The block number n is associated to a hash f(n), which is a number drawn randomly from the lattice $\{0,1,\ldots,2^{256}-1\}$ . Mining a block consists in computing the hash of the block until it is lower than a target L. The number of trials required is a geometric random variable $\text{Geom}(L\times2^{-256})$ with associated PMF $ (1-L\times2^{-256})^{k-1}L\times2^{-256} $ for $k\geq1$ . The difficulty is adjusted by tuning the target L. Denote by $\{T_k\text{ , }k\geq1\}$ the sequence of arrival times of the blocks. The difficulty is adjusted every 2016 blocks to maintain an average of 1 block mined every 10 minutes. Mining 2016 takes about 2 weeks. This leads to the definition of a piecewise constant target function L(t) as

$$ L(t)= \begin{cases} L_0 &\text{for }t\in (0,T_{2016}), \\ L_k &\text{for }t\in (T_{2016k},T_{2016(k+1)})\text{ and }k>0, \end{cases}$$

where the sequence of real numbers $\{L_k,\, k\geq0\}$ is defined recursively as

$$ L_k= \begin{cases} 2^{224} & \text{for }k=0, \\ \displaystyle{L_{k-1} \frac{T_{2016k}-T_{2016(k-1)}}{1209600}} & \text{for }k>0. \end{cases} $$

Note that the time unit is the second and $1\,209\,600$ seconds correspond to 2 weeks. The number of trials relates to the mining time through the (global) hashrate function H(t). The hashrate function corresponds to the number of hashes computed per second by the entire network of miners. Hence, the instantaneous average mining time is given by ${2^{256}}/{H(t)L(t)}$ and the intensity function of the underlying nonhomogeneous Poisson process is given by

(16) \begin{equation} \lambda(t)=\frac{H(t)L(t)}{2^{256}} \quad\text{for }t\geq0. \label{eqn16} \end{equation}

There are two main drivers of the hashrate. First, the improvement of the mining machines which enhances the computing power of the miners. Second, the number of miners in the network. The miners enter and exit the network according to how profitable mining BTCs is at the moment. This last factor depends on the price of the electricity and the value of the BTCs at a given point in time. Information regarding the target L(t) can be collected from the header of the block. The hashrate H(t) is retrieved from the knowledge of the difficulty and the timestamp data. Bowden et al. [Reference Bowden, Keeler, Krzesinski and Taylor8] proposed an exponential function of the form $H(t)=\mathrm{e}^{at+b}$ arguing that the log hashrate is piecewisely linear over time. The values of a and b follow from the linear interpolation within successive time periods. Once the hashrate function has been determined, the length of the blockchain $\{N(t),\, t\geq0\}$ is a nonhomogeneous Poisson process with intensity function $\lambda(t)$ defined in (16). Assuming that $N(t)=n$ , the arrival times $T_1,\ldots,T_n$ are distributed as the order statistics of n i.i.d. random variables with associated CDF

$$F_t(s)=\frac{\Lambda(s)}{\Lambda(t)} \quad\text{for }s\leq t,$$

where $\Lambda(t)=\int_{0}^{t}\lambda(s){\,\mathrm{d}}s$ . In the event of a double-spending attack, the difficulty of the puzzle is the same for the honest miners and the colluding miners. The difference between the two pools lies in their computing power and, thus, their hashrate function. We may assume that both the honest and dishonest miners contribute to the global hashrate of the network in an additive way. More specifically, let $H_1(t)=p\times H(t)$ be the hashrate of the honest miners and $H_2(t)=(1-p)\times H(t)$ , where $p\in (0,1)$ represents the repartition of the computing resources among the miners. Theorem 2 is applicable and (11) simplifies to

(17) \begin{equation} \mathbb{P}[\tau_z>t]=\mathbb{E}(A_{M(t)}\{1\ \,\,|\, \ \, 0,\ldots, 0,U_{1: N(t)},\ldots,U_{M(t)+1-z: N(t)}\}{\bf 1}_{M(t)\leq N(t)+z-1}\!), \label{eqn17} \end{equation}

because $F^{\ast}_{t}(s)=F_t(s)$ for every $s\leq t$ . An evaluation via Monte Carlo simulation is possible by generating values for M(t), N(t), and $U_{1: N(t)},\ldots,U_{M(t)+1-z: N(t)}$ . Appell polynomials do not usually admit a closed-form expression but can be computed recursively via the relations provided in Appendix A; see Proposition 2.

Note that the evaluation of (11) may be achieved through the truncation of the infinite series in (14) followed by numerical integration, in the same vein as performed in [Reference Dimitrova, Kaishev and Zhao11]. Another solution would be to resort to a fully recursive evaluation as in [Reference Lefèvre and Loisel22].

4. The probability of a successful double-spending attack

In this section we study the probability of a successful double-spending attack, $\mathbb{P}[\tau_z<+\infty]$ , when the length of the chains $\{z+N(t),\, t\geq0\}$ and $\{M(t),\, t\geq0\}$ are modeled by independent renewal processes generated by their respective sequence of i.i.d. interarival times denoted by $\{\Delta^{T}_k,\, k\geq1\}$ and $\{\Delta^{S}_k,\, k\geq1\}$ . Assume that

1. (A1) $\mathbb{E}(\Delta^{S})> \mathbb{E}(\Delta^{T})$ ;

2. (A2) the equation

   (18) \begin{equation} \log\mathbb{E}[\mathrm{e}^{\theta (\Delta^{T}-\Delta^{S})}]=0 \label{eqn18} \end{equation}
   has a unique nonnegative solution denoted by $\gamma$ , refered to as the adjustment coefficient.

The stopping time $\tau_z=\inf\{t\geq0; \,M(t)=z+N(t)\}$ coincides with the ruin time $\tau_z=\inf\{t\geq0; \,R(t)=0\}$ associated to the risk process

(19) \begin{equation} R(t)=z+N(t)-M(t), \qquad t\geq0. \label{eqn19} \end{equation}

Define the claim surplus process as

(20) \begin{equation} S(t)=M(t)-N(t), \qquad t\geq0. \label{eqn20} \end{equation}

In risk theory, processes such as (19) model the evolution of the net worth of an insurance company over time. Here, the insurance company holds an initial capital of amount z, its premium income is governed by $\{N(t),\, t\geq0\}$ while $\{M(t),\, t\geq0\}$ corresponds to its liability at time $t\geq0$ . Note that risk theory terminology is being used only to improve the presentation, I am not claiming that one should model the evolution of the financial reserves of any nonlife insurance company via (19). When studying the distribution of the ruin time is problematic, a simple trick consists in passing to a dual risk model. This approach is rather standard (see the references given in the introduction). For the sake of clarity, the idea is recalled hereafter and illustrated by Figure 2. In Figure 2(a) we display the ruin problem in model (19). The initial ruin problem is converted into another equivalent ruin problem. Increment the value of $\{M(t),\, t\geq0\}$ by one unit and consider the risk model

$$\tilde{R}(t)=z+N(t)-[M(t)+1],\qquad t\geq0.$$

Further define the ruin time

$$\tilde{\tau}_z=\inf\{t\geq0;\, z+N(t)<[M(t)+1]\},$$

which corresponds to the first-crossing time of $\{M(t)+1,\, t\geq0\}$ through the upper boundary $\{N(t)+z,\, t\geq0\}$ ; see Figure 2(b). It holds that

$$\tau_z\overset{\text{a.s.}}{=}\tilde{\tau}_z,$$

where ‘ $\overset{\text{a.s.}}{=}$ ’ stands for equality almost sure as it is true for every trajectory. Then rotate Figure 2(b) by $90^{\circ}$ anticlockwise to obtain Figure 2(c). Shifting the origin from (0, 0) to $(z-1,0)$ finally leads to Figure 2(d). The ruin problem displayed in Figure 2(d) concerns a discrete-time risk model denoted by $\{R^{\ast}(n),\, n\geq1\}$ and defined as

(21) \begin{equation} R^{\ast}(n)=S_{z-1}+\sum_{k=1}^{n}(\Delta^{S}_{k+z-1}- \Delta^{T}_{k}) \quad\text{for }n\in\mathbb{N}. \label{eqn21} \end{equation}

The initial capital is $S_{z-1}$ , the sequence $\{\Delta^{S}_{k+z-1},\, k\geq1\}$ models the premium collected at each time period, and the sequence $\{\Delta^{T}_{k},\, k\geq1\}$ represents the total claim amounts incurred during each time period. The conventions $S_0=0$ and $T_0=0$ are adopted. The claim surplus process $\{S^{\ast}(n),\, n\geq1\}$ is given by

(22) \begin{equation} S^{\ast}(n)=\sum_{k=1}^{n}(\Delta^{T}_{k}-\Delta^{S}_{k+z-1}). \label{eqn22} \end{equation}

The ruin time is defined as $\sigma_{S_{z-1}}= \inf\{n\in\mathbb{N};\, R^{\ast}(n)\leq0\}$ and relates to $\tau_z=\inf\{t\geq0;\, R(t)=0\}$ as

$$\tau_z\overset{\mathcal{\text{a.s.}}}{=}\tilde{\tau}_z\overset{\mathcal{\text{a.s.}}}{=} S_{\sigma_{S_{z-1}}+z-1},$$

which implies that

(23) \begin{equation} \mathbb{P}[\tau_z<\infty]=\mathbb{P}[\sigma_{S_{z-1}}<\infty]. \label{eqn23} \end{equation}

Again the one-to-one correpondence between the trajectories leading to ruin in the multiple risk models entail the equality almost surely. The following result provides, inter alia, an upper bound for the probability of a successful double-spending attack.

Figure 2.

Boundary crossing problems in the various risk models.

Theorem 3. If $\{N(t),\, t\geq0\}$ and $\{M(t),\, t\geq0\}$ are two independent renewal processes such that (A1) and (A2) hold then

(24) \begin{equation} \mathbb{P}[\tau_z<\infty]=\frac{[\mathbb{E}(\mathrm{e}^{-\gamma \Delta^S})]^{z-1}}{\mathbb{E}[\mathrm{e}^{\gamma\xi(S_{z-1})} \ \,\,|\, \ \, \tau_z<\infty]}, \label{eqn24} \end{equation}

where $\xi(S_{z-1})=S(\sigma_{S_{z-1}})-S_{z-1}$ denotes the overshoot, immediately after ruin, in model (21). The following Cramér–Lundberg upper bound holds:

(25) \begin{equation} \mathbb{P}[\tau_z<\infty]\leq[\mathbb{E}(\mathrm{e}^{-\gamma \Delta^S} )]^{z-1}. \label{eqn25} \end{equation}

Proof. The claim surplus process $\{S^{\ast}(n),\, n\geq1\}$ in (22) is a random walk. Assumption (A2) implies that the process $\{\mathrm{e}^{\gamma S^{\ast}(n)},\, n\geq1\}$ is a martingale as a consequence of [Reference Asmussen and Albrecher2, Theorem 1.1]. Note also that $S^{\ast}(n)\overset{\text{a.s}}{\rightarrow}-\infty$ , where ‘ $\overset{\text{a.s}}{\rightarrow}$ ’ stands for convergence almost surely, follows from assumption (A1) and the law of large numbers. Let the initial reserves $S_{z-1}=s\geq0$ be fixed in 21. The application of [Reference Asmussen and Albrecher2, Proposition 3.1] allows us to rewrite the ultimate ruin probability as

\begin{equation*} \mathbb{P}[\sigma_s<\infty]=\frac{\mathrm{e}^{-\gamma s}}{\mathbb{E} [\mathrm{e}^{\gamma \xi(s)} \ \,\,|\, \ \, \sigma_s<\infty]}, \end{equation*}

where $\xi(u)=S^{\ast}(\sigma_s)-s$ denotes the overshoot given that ruin occurred in model (21). Thanks to the connection (23), by conditioning on the values of $S_{z-1}$ , it holds that

$$\mathbb{P}[\tau_z<\infty]=\frac{\mathbb{E}[\mathrm{e}^{-\gamma S_{z-1}} ]}{\mathbb{E}[\mathrm{e}^{\gamma \xi(S_{z-1})}\ \,\,|\, \ \, \tau_z<\infty]}=\frac{\mathbb{E} [\mathrm{e}^{-\gamma \Delta^{S}}]^{z-1}}{\mathbb{E}[\mathrm{e}^{\gamma \xi(S_{z-1})}\ \,\,|\, \ \, \tau_z<\infty]}.$$

The upper bound (25) follows from noting that $$\mathbb{E}[\mathrm{e}^{\gamma \xi(S_{z-1})}\ \,\,|\, \ \, \sigma_s\lt\infty]>1.$$

The next result specifies the expression for the probability $\mathbb{P}[\tau_z<\infty]$ in the case where $\{N(t),\, t\geq0\}$ is a Poisson process.

Corollary 3. If $\{N(t),\, t\geq0\}$ is a homogeneous Poisson process of intensity $\lambda$ and $\{M(t),\, t\geq0\}$ is a renewal process, independent from $\{N(t),\, t\geq0\}$ , such that (A1) and (A2) holds then

(26) \begin{equation} \mathbb{P}[\tau_z\lt\infty]=\frac{\lambda-\gamma}{\lambda}\mathbb{E} [\mathrm{e}^{-\gamma \Delta^S}]^{z-1}. \label{eqn26} \end{equation}

If $\{M(t),\, t\geq0\}$ is also a homogeneous Poisson process of intensity $\mu\lt \lambda$ then

(27) \begin{equation} \mathbb{P}[\tau_z\lt \infty]=\bigg(\frac{\mu}{\lambda}\bigg)^{z}. \label{eqn27} \end{equation}

Proof. As $\{N(t),\, t\geq0\}$ is a homogenous Poisson process, it is a renewal process and 24 holds. The sequence of interarrival times $\{\Delta^{T}_k,\, k\geq1\}$ is formed by i.i.d. exponential random variables with parameter $\lambda,$ which implies that the overshoot $\xi(S_{z-1})$ is also exponentially distributed with parameter $\lambda$ by virtue of the lack of memory of the exponential distribution. It follows that

$$ \mathbb{E}[\mathrm{e}^{\gamma \xi(S_{z-1})}\ \,\,|\, \ \, \tau_z\lt\infty]=\frac{\lambda} {\lambda-\gamma}. $$

Substituting in 24 yields 26. Now, assume that $\{M(t),\, t\geq0\}$ is also a Poisson process with intensity $\mu<\lambda$ . The sequence of interarrival times $\{\Delta^{S}_k,\, k\geq1\}$ is made of i.i.d. exponential random variables with parameter $\mu$ . Equation 18 is equivalent to

$$\log ({{\lambda \mu } \over {(\lambda - \theta )(\mu + \theta )}}) = 0$$

and admits $\gamma=\lambda-\mu$ as only nonnegative solution. Substituting $\gamma=\lambda-\mu$ into (26) yields (27).

This result allows confirmation of Corollary 1; see Example 1. Note that the probability of a successful double-spending attack when the length of the chains are two independent Poisson processes may be retrieved without using the duality argument as shown in the following remark.

Remark 1 Assume that $\{N(t),\, t\geq0\}$ and $\{M(t),\, t\geq0\}$ are two independent homogeneous Poisson processes with respective intensity $\lambda$ and $\mu$ such that $\lambda\gt \mu$ . The claim surplus process, already defined in 20 as

\begin{equation*} S(t)=M(t)-N(t) \quad\text{for }t\geq0, \end{equation*}

is the difference between two independent Poisson processes and, thus, a Lévy process. Theorem 1.2 of [Reference Asmussen and Albrecher2] then implies that the process defined by

$${{\rm{e}}^{\theta S(t) - t\kappa (\theta )}}\quad {\rm{for }}t \ge 0,$$

where $\kappa(\theta)=\log\mathbb{E}[\theta S(1)]$ , is a martingale. The equation $\kappa(\theta)=0$ is equivalent to

$$\mu {{\rm{e}}^\theta } + \lambda {{\rm{e}}^{ - \theta }} - (\lambda + \mu ) = 0$$

and admits a unique nonnegative solution $\gamma=\log(\lambda/\mu)$ . Consequently, the process $\{\mathrm{e}^{\gamma S(t)}, t\geq0\}$ is a martingale. Moreover, the condition $\lambda>\mu$ entails $S(t)\overset{\text{a.s.}}{\rightarrow}-\infty$ . Applying [Reference Asmussen and Albrecher2, Proposition 3.1] yields

(28) \begin{equation} \mathbb{P}[\tau_z\lt \infty]=\frac{\mathrm{e}^{-\gamma z}}{\mathbb{E}[\mathrm{e}^{\gamma\xi(z)}\ \,\,|\, \ \, \tau_z\lt \infty]}, \label{eqn28} \end{equation}

where $\xi(z)=S(\tau_z)-z$ denotes the overshoot after ruin occurred in model 19. In the case considered here there is no overshoot as $S(\tau_z)=z$ . Substituting $\gamma=\log(\lambda/\mu)$ into (28) yields (26).

5. Numerical illustrations

The numerical results presented here are based on the data collected by Bowden [Reference Bowden7] and the analysis conducted in [Reference Bowden, Keeler, Krzesinski and Taylor8]. In Subsection 5.1 data is used to fit the interblock time distribution within the public chain. The lack of data regarding the growth of the malicious chain is circumvented by assuming that the interblock times in the malicious chain are defined as a transformation of the interblock times in the public chain. This allows us to illustrate the results given in Sections 2 and 4. Subsection 5.2 focuses on the case where the lengths of the chains are governed by nonhomogeneous Poisson processes which seems to be the most suitable model according to Bowden et al. [Reference Bowden, Keeler, Krzesinski and Taylor8]. It allows us to illustrate the results derived in Section 3.

5.1. Length of the chains as renewal process

In this subsection the length of the chains $\{N(t),\, t\geq0\}$ and $\{M(t),\, t\geq0\}$ are assumed to be governed by renewal processes. The first task consists in studying the fit of the interblock time distribution to the data provided in [Reference Bowden7]. In Figure 3 we display the interblock times chronologically. The distribution of the interblock times of the first few blocks presents a few spikes (to the magnitude of the day) before reaching stationarity around the $200\,000$ th block; see Figure 3(a). If we limit our analysis to the latest blocks, starting, for instance, from the $400\,000$ th, then the data admits fewer outliers, with a maximum of 2 hours; see Figure 3(b). The inference of the block arrival is therefore based on the interarrival times starting from the $400\,000$ th block onward which still represents $96\,628$ data points. The empirical mean is equal to $9.57$ minutes while the standard deviation is significantly lower than the overall one with $9.56$ minutes. In Figure 4 we show the histogram of the interblock times. The PDF of the exponential distribution $\text{Exp}(\widehat{\lambda})$ , where $\widehat{\lambda}=1/9.57$ corresponds to the method of the moment estimator, matches reasonably well the histogram. In Figure 4(b) the empirical quantiles are plotted against the quantiles of the exponential distribution $\text{Exp}(\widehat{\lambda})$ . The points overlap the diagonal $y=x$ , which indicates a superb fit. This analysis leads us to model the number of blocks in the honest chain $\{N(t)\text{ , }t\geq0\}$ by a homogeneous Poisson process of intensity $\widehat{\lambda}$ .

Figure 3.

Chronological series of the interblock times.

Figure 4.

Distribution of the interblock times.

Regarding the block arrival in the malicious chain, no data is available. The only a priori information is that the interblock time should be larger to account for the unbalanced repartition of the computing power in favour of the honest miners. The growth of $\{M(t),\, t\geq0\}$ should be slower than the growth of $\{N(t),\, t\geq0\}$ . In the sequel, two definitions of the interarrival times $\{\Delta^{S}_k,\, k\geq1\}$ that generate $\{M(t),\, t\geq0\}$ are compared in terms of the risk of a double-spending attack.

1. 1. Define

   $${\Delta ^S}\mathop = \limits^{\rm{D}} {{{\Delta ^T}} \over r},$$
   where $r>1$ . The interarrival times $\{\Delta^{S}_{k},\, k\geq1\}$ are i.i.d. exponential random variables and the process $\{M(t),\, t\geq0\}$ is a homogeneous Poisson process with intensity $\widehat{\lambda}/r$ . Corollary 3 applies and the probability of a successful double-spending attack is given by
   (29) \begin{equation} \mathbb{P}[\tau_z\lt \infty]=\bigg(\frac{1}{r}\bigg)^{z}. \label{eqn29} \end{equation}
   The PDF of the double-spending time $f_{\tau_z}$ follows from applying Corollary 1 and is given in 8 after substituting $\lambda=\widehat{\lambda}$ and $\mu=\widehat{\lambda}/r$ .

2. 2. Define

   $${\Delta ^S}\mathop = \limits^{\rm{D}} \Delta _1^T + \cdots + \Delta _r^T,$$
   where $r\gt 1$ is integer valued. The interarrival times $\{\Delta^{S}_{k},\, k\geq1\}$ are i.i.d. gamma random variables $\text{Gam}(r,\lambda)$ with associated PDF
   $${f_{{\Delta ^S}}}(t) = {{{{\rm{e}}^{ - \lambda t}}{t^{r - 1}}{\lambda ^t}} \over {\Gamma (r)}}\quad {\rm{for }}t \ge 0.$$
   The process $\{M(t),\, t\geq0\}$ is a renewal process and Corollary 3 applies. The probability of a successful double-spending attack is given by
   (30) \begin{equation} \mathbb{P}[\tau_z\lt \infty]=\frac{\lambda-\gamma}{\lambda} \bigg[\frac{\lambda}{\lambda+\gamma}\bigg]^{r(z-1)}, \label{eqn30} \end{equation}
   where $\gamma$ is the only nonnegative solution to
   (31) \begin{equation} \log\bigg[\frac{\lambda^{r}}{(\lambda-\theta)(\lambda+\theta)^{r-1}} \bigg]=0. \label{eqn31} \end{equation}
   Note that the root in 31 is derived numerically using the uniroot built-in function in R. The PDF $f_{\tau_z}$ of the double-spending time follows from the application of Corollary 1 and reduces, after a couple of rearrangements, to
   (32) \begin{equation} f_{\tau_z}(t)=\sum_{n=0}^{+\infty}\bigg(\frac{z}{z+n}\bigg) \frac{\Gamma[r(n+z)+n]}{\Gamma(n+1)\Gamma[r(n+z)]2^{r(n+z)+n}} \frac{(2\lambda)^{r(n+z)+n}t^{r(n+z)+n-1}\mathrm{e}^{-2\lambda t}}{\Gamma[r(n+z)+n]} \label{eqn32} \end{equation}
   for $t\geq0$ .

In Table 1 we report the values of 29 and 30 for $r=2,3,4,5$ and $z=1,2,3,4,5$ . Although definitions 1 and 2 both mean that the building of blocks is r times slower on average in the malicious chain, the probability of a successful double-spending attack is much smaller when $\{M(t),\, t\geq0\}$ is a renewal process with gamma-distributed interarrival times. It shows the influence of the shape of the distribution of the interarrival times on the likelihood of a double-spending attack. In Figure 5 we display the PDF and CDF of the double-spending time

$$ \tau_1=\inf\{t\geq0; N(t)+1=M(t)\} $$

for $r=2$ along with the reference horizontal lines $y=\mathbb{P}[\tau_1\lt \infty]$ . Note that the infinite series in 8 and 32 are truncated to the order $K=50$ . In both cases, the merchant who is waiting for two hours is not taking much risk as the CDF reaches the barrier $\mathbb{P}[\tau_1\lt \infty]$ . Namely, if $\mathbb{P}[\tau_1\lt \infty]-\mathbb{P}[\tau_1\lt t]=\varepsilon $ , for some $t\geq0$ and $\varepsilon \gt 0$ , then the probability of the double-spending ever being successful, conditionning upon $\{\tau_z\gt t\}$ , may be written as

$$ \mathbb{P}[\tau_z=+\infty\ \,\,|\, \ \, \tau_z\gt t]=\frac{\mathbb{P}[\tau_z=+\infty]} {\mathbb{P}[\tau_z=+\infty]+\varepsilon }. $$

This probability becomes close to 1 as we let $\varepsilon $ tend to 0. The R code is accessible online at [Reference Goffard16] for the sake of reproducibility.

Table 1.

Probability of a successful double-spending attempt

Figure 5.

PDF and CDF of the double-spending time $\tau_1$ : $\{M(t),\, t\geq0\}$ is a homogeneous Poisson process with intensity $\widehat{\lambda}/2$ (solid line), $\{M(t),\, t\geq0\}$ is a renewal process with gamma $\text{Gam}(r=2,\widehat{\lambda})$ distributed interarrival times (dash–dot line).

5.2. Length of the chains as a nonhomogeneous Poisson process

In this subsection the length of the chains $\{z+N(t),\, t\geq0\}$ and $\{M(t),\, t\geq0\}$ are assumed to be governed by two nonhomogeneous Poisson processes. The intensity function of $\{N(t),\, t\geq0\}$ is given by

\begin{equation*} \lambda(t)=\frac{pH(t)L(t)}{2^{256}}, \end{equation*}

where H(t) denotes the global hashrate function, L(t) is the target function, and $p\in (0,1)$ reflects the repartition of the computing power between honest and dishonest miners. We refer the reader to Example 2 for a definition of these quantities. The intensity function of $\{M(t),\, t\geq0\}$ is given by

\begin{equation*} \lambda^{\ast}(t)=\frac{(1-p)H(t)L^{\ast}(t)}{2^{256}}. \end{equation*}

The global hashrate is assumed to admit a parametric form with $H(t)=\mathrm{e}^{at+b}$ , where the values of a and b are selected from [8, Table 1]. The difficulty is assumed to be the same for all the miners so that $L^{\ast}(t)=L(t)$ . More specifically, let us consider a time span during which the difficulty is contant, equal to L say. This is true for time periods that are about two weeks long as it corresponds to the average time to discover 2016 blocks. The intensity function $\lambda(t)$ associated to $\{N(t),\, t\geq0\}$ becomes

\begin{equation*} \lambda(t)=\frac{p\mathrm{e}^{at+b}L}{2^{256}}, \end{equation*}

and may be integrated as

(33) \begin{equation} \Lambda(t)=\int_{0}^{t}\lambda(s){\,\mathrm{d}}s=\frac{p\mathrm{e}^{b}L}{2^{256}a} (\mathrm{e}^{at}-1). \label{eqn33} \end{equation}

Note that we equivalently have

\begin{equation*} \lambda^{\ast}(t)=\frac{(1-p)\mathrm{e}^{at+b}L}{2^{256}} \end{equation*}

and

(34) \begin{equation} \Lambda^{\ast}(t)=\int_{0}^{t}\lambda^{\ast}(s){\,\mathrm{d}}s=\frac{(1-p) \mathrm{e}^{b}L}{2^{256}a}(\mathrm{e}^{at}-1). \label{eqn34} \end{equation}

In view of these assumptions, the conditional distribution of the block arrival times given the length of the chain is the same in the honest and the malicious chains. Namely, it holds that $F_{t}(s)=F^{\ast}_{t}(s)$ and the probability $\mathbb{P}[\tau_z\gt t]$ of the double-spending attack being unsuccessful before t may be estimated via 17. The practical evaluation is handled via Monte Carlo simulations; note that the numerical value of Appell polynomials of any order may be computed recursively using the relations given in Appendix 7 (see Proposition 2). Let the time unit be one second, and consider a two week time period, which corresponds to $1\,209\,600$ seconds. Let us set the parameters of the hashrate function to $a=-9.44\times10^{-9}$ and $b=27.1$ according to the first row of Table 1 of [Reference Bowden, Keeler, Krzesinski and Taylor8]. The difficulty is assumed to be constant, equal to

$$ L=2016\times \frac{2^{256}a}{\mathrm{e}^b(\mathrm{e}^{a*1209600}-1)}, $$

in order to have on average 2016 blocks discovered by the end of the time horizon (i.e. two weeks). In Figure 6 we display the integrated intensity functions 33 and 34 over time. The parametrization entails a linear growth (on average) of the chains which makes our example close to the homogeneous Poisson arrival situation. Equation 11 is difficult to use for risk management purposes without the knowledge of the mass of probability associated to $\tau_z=\infty$ . This issue is addressed by assuming that an attacker gives up his double-spending attempt if not completed within three hours (10 800 seconds). It makes little sense in practice for an attacker to carry on an attack for two weeks. We then investigate the probability of a successful double-spending attack attempted every three hours over the course of two weeks. Namely, denote by

$$ t_k=k\times10800 \quad\text{for }0\leq k\lt 112, $$

the sequence of time steps and by

(35) \begin{equation} p_{z,k}=\mathbb{P}[\tau_{z,k}<10800] \label{eqn35} \end{equation}

the probabilities of interest, where

$$ \tau_{z,k}=\inf\{t\in(t_k,t_{k+1}); M(t)=z+N(t)\ \,\,|\, \ \, M(t_k)=N(t_k)=0\}. $$

Figure 6.

Integrated intensity functions over time: $\Lambda(t)$ associated to $\{N(t),\, t\geq0\}$ (solid line), $\Lambda^{\ast}(t)$ associated to $\{M(t),\, t\geq0\}$ (dash–dot line).

Let us assume that the honest chain is one block ahead, which in turn allows us to use 15 and alleviate the computational burden associated to the recursive evaluation of Appell polynomials. In Figure 7 we display the value of the probabilities 35 over the two weeks of operations for various repartition $p\in \{0.6,0.7,0.8,0.9\}$ of the hash power. Note that the evaluation is based on $10\,000$ trajectories of $\{N(t),\, t\geq0\}$ and $\{M(t),\, t\geq0\}$ . The probabilities $p_{z,k}$ are constant over time, which was expected as the arrival of blocks is almost time homogenous due to the parametrization of the global hashrate function. The source code is available online [Reference Goffard16] and the reader is invited to experiment the effect of modifying the parameters a and b on the double-spending probabilities.

Figure 7.

Evolution of the probability of performing a successful double-spending attack in the course of two weeks for various values of p: $p=0.6$ (solid line), $p=0.7$ (dashed line), $p=0.8$ (dotted line), $p=0.9$ (dash–dot line).

6. Concluding remarks

In this paper, the model, initially proposed by Nakamoto [Reference Nakamoto27], to comprehend the double-spending issue is refined. Assuming that the lengths of the competing blockchains are governed by counting processes leads to interesting boundary crossing problems. This refinement offers more flexibility to reflect accurately the block discovery frequency as well as the distribution of the computing power among honest and dishonest miners through the calibration of the arrival times that generate the aforementionned counting pocesses. Theorem 3 is useful to advise the merchant on how many subsequent blocks should be added to the chain before shipping the goods. Theorems 1 and 2 enable us to determine the time at which the double-spending attack is most likely to occur. This is helpful to provide merchants with guidelines on how long they should wait before shipping goods, which compliments the advice on the number of blocks.

Throughout this paper, the lag $z\gt 0$ between the honest and malicious chains is assumed to be deterministic. In practice, because the length of the dishonest chain is unknown to the vendor at the time of the shipping, the delay should be assumed to be stochastic. From a mathematical point of view, the question is when do we initialize the counting processes $\{N(t),\, t\geq0\}$ and $\{M(t),\, t\geq0\}$ ? If the starting time is the time at which the goods are shipped then Z and the counting processes are independent. Thus, we can apply the law of total probability together with the formulae derived above. We have an atom at 0 with probability mass $\mathbb{P}[Z\leq0]$ . If we initialize the counting processes at the time of issuance of the transactions then Z and the counting processes are linked. The vendor is asked to wait for say $k\in\mathbb{N}$ blocks to be added to the blockchain before shipping the goods. The honest chain is then ahead by $Z=k-M(T_k)$ , where $T_k$ is the arrival time of the kth block in the honest chain. The time interval $[0,T_k]$ is a burn-in period during which it does not matter which chain is leading. If $\{N(t),\, t\geq0\}$ and $\{M(t),\, t\geq0\}$ are Poisson processes then $T_k$ has a gamma distribution, the stopped processes at $T_k$ are again Poisson processes, and $M(T_k)$ is governed by a negative binomial distribution which is consistent with Rosenfeld’s findings [Reference Rosenfeld32]. The general case will be studied in upcoming research.

The success of the blockchain method has resulted in bitcoin becoming increasingly popular and inspiring other electronic payment methods. It is worth mentionning that the results derived in this paper may be relevant to understanding other systems where similar blockchain policies are used.

Selfish mining, described, for instance, in [Reference Eyal and Sirer12], [Reference Göbel, Keeler, Krzesinski and Taylor14], and [Reference Sapirshtein, Sompolinsky and Zohar33], is another type of miners’ misconduct. Nowadays, it is no longer feasible to mine BTCs in isolation. Empirical evidence shows that BTC miners behave strategically by gathering in pools. All members contribute to the solution of each cryptopuzzle, and share the rewards proportionally to their contribution. Selfish mining is a strategy that can be used by a minority pool to obtain more revenue. The key idea is for the pool of selfish miners to keep its discovered blocks private while honest nodes continue to mine on the public chain. Assuming that the private chain has the lead over the public chain, when the public branch approaches the selfish miners’ chain, the private chain is released publicly. It results in a waste of resources for all the miners but Eyal and Siren [Reference Eyal and Sirer12] showed that the revenue of the selfish miners goes beyond the revenue expected when following the usual protocol given their share of the total computing power. The results presented here may be relevant in the context of a selfish mining attack as it boils down again to the race between two counting processes.