# Analysis of Nakamoto's Private Chain Attack

[CS6231 Extension Exercise 6]

-- By Yangfan Jiang

------

Bounding the probability of successful attack (i.e., the event that adversary’s private chain is longer than longest honest chain).

## Preliminary

We begin with a brief introduction to the moment generating function, which is the key to derive the upper bound of the probability of the adversary's success. Then we formalize the problem using the language of probability theory.

### Moment Generating Function of Exponential Distribution

We will derive the results by bounding the moment generating function of the exponential distribution. The definition of the moment generating function is as follows.
> Let $X$ be a random variable. The moment generating function of $X$ is defeined as $$\mathbb{E}\left[e^{tX}\right],$$ where $t\in\mathbb{R}$ is a parameter of the moment generating function.

Consider the moment generating function of the exponential distribution. Let $X$ be a random variable with exponential distribution (with parameter $\lambda$). The probability density function of $X$ can be written as $$f(x)=\lambda e^{-\lambda x} \quad (x\geq0).$$ Then the moment generating function of $X$ (for $t<\lambda$) is
\begin{align}
\mathbb{E}\left[e^{tX}\right]=\int_{0}^{\infty} e^{tx} f(x) {\rm d}x=\int_{0}^{\infty} e^{tx} \lambda e^{-\lambda x} {\rm d}x = \lambda\int_{0}^{\infty} e^{(t-\lambda) x} {\rm d}x = \dots = \frac{\lambda}{\lambda-t}. \tag{1}
\end{align}

### Problem Statement

Let $\{T(\lambda_h)_i\}_{i=1}^{k}$ be the time intervals between the $i$th block and the $(i+1)$th block in the chains (maintained by honest nodes). Similarly, we define $\{T(\lambda_a)_i\}_{i=1}^{k}$ to be the time intervals between blocks that are mined by the adversary. Following the analysis presented in class, these time intervals can be viewed as i.i.d. random variables that follow the exponential distribution:
$$T(\lambda_h)_i\sim {\rm Exp}(\lambda_h), \quad {\rm and} \quad T(\lambda_a)_i\sim {\rm Exp}(\lambda_a).$$ In this way, the total time to mine $k$ blocks is $\sum_{i=1}^{k} T(\lambda_h)_i$ and $\sum_{i=1}^{k} T(\lambda_a)_i$ for honest parties and the adversary, respectively. To bound the probability of success of the adversary, our goal is to show that the total time to mine $k$ for the adversary is shorter than that of the honest parties with a small probability. In other words, we want to bound the following probability:
$$
\Pr\left[\sum_{i=1}^{k} T(\lambda_h)_i - \sum_{i=1}^{k} T(\lambda_a)_i>0\right].\tag{2}$$

In the remainder of this note, we assume that $\lambda_h>\lambda_a$. Otherwise, if the adversary controls the majority of the computation power, the honest longest path can hardly grow faster than the adversary's private chain.

## Security Analysis when $\Delta\to0$

We bound Eq. (2) as follows:
\begin{align}
&\Pr\left[\sum_{i=1}^{k} T(\lambda_h)_i - \sum_{i=1}^{k} T(\lambda_a)_i>0\right]\\
=&\Pr\left[e^{\sum_{i=1}^{k} \left(T(\lambda_h)_i - T(\lambda_a)_i\right)}>1\right]\\
=&\Pr\left[e^{t\cdot\sum_{i=1}^{k} \left(T(\lambda_h)_i - T(\lambda_a)_i\right)}>1\right]\quad (\forall t>0)\\
\leq & \mathbb{E}\left[e^{t\cdot\sum_{i=1}^{k} \left(T(\lambda_h)_i - T(\lambda_a)_i\right)}\right]\\
=&\mathbb{E}\left[\prod_{i=1}^{k} e^{t\cdot\left(T(\lambda_h)_i-T(\lambda_a)_i\right)}\right] \tag{3}
\end{align} where the inequality follows from Markov's inequality. Since all r.v. (i.e., $T(\lambda_h)_i$ and $T(\lambda_a)_i$) are independent, we have

\begin{align}
&\mathbb{E}\left[\prod_{i=1}^{k} e^{t\cdot\left(T(\lambda_h)_i-T(\lambda_a)_i\right)}\right]=\prod_{i=1}^{k} \mathbb{E}\left[e^{t\cdot\left(T(\lambda_h)_i-T(\lambda_a)_i\right)}\right] =\prod_{i=1}^{k} \left(\mathbb{E}\left[e^{tT(\lambda_h)_i}\right]\cdot\mathbb{E}\left[e^{-tT(\lambda_a)_i}\right]\right).\tag{4}
\end{align}

Note that $T(\lambda_h)_i$ and $T(\lambda_a)_i$ follow the exponential distribution. According to the analysis of moment generating function of exponential distribution (See Eq. (1)), we have (for $t<\lambda_h$ and $-t<\lambda_a$)
\begin{equation}
\mathbb{E}\left[e^{tT(\lambda_h)_i}\right]=\frac{\lambda_h}{\lambda_h-t} \quad {\rm and } \quad \mathbb{E}\left[e^{-tT(\lambda_a)_i}\right]=\frac{\lambda_a}{\lambda_a+t}.
\end{equation} Therefore, Eq. (4) can be written as
\begin{equation}
\mathbb{E}\left[\prod_{i=1}^{k} e^{t\cdot\left(T(\lambda_h)_i-T(\lambda_a)_i\right)}\right]=\left(\frac{\lambda_h}{\lambda_h-t}\cdot\frac{\lambda_a}{\lambda_a+t}\right)^k.\tag{5}
\end{equation}

In order to derive a 'good' upper bound, we need to choose $t$ to make Eq. (5) as small as possible. Note that the inequality $-t<\lambda_a$ holds for all $t>0$, thus we only need to consider $t\in (0,\lambda_h)$. It is easy to verify that choosing $t=\frac{\lambda_h-\lambda_a}{2}\in(0,\lambda_h)$ can minimize Eq. (5). Let $t=\frac{\lambda_h-\lambda_a}{2}$, we have:

\begin{align}
\left(\frac{\lambda_h}{\lambda_h-t}\cdot\frac{\lambda_a}{\lambda_a+t}\right)^k&=\left(\frac{4\lambda_h\lambda_a}{(\lambda_h+\lambda_a)^2}\right)^k\\
&=e^{\log\left[\left(\frac{4\lambda_h\lambda_a}{(\lambda_h+\lambda_a)^2}\right)^k\right]}\\
&=e^{-\log{\left[\frac{(\lambda_h+\lambda_a)^2}{4\lambda_h \lambda_a}\right]}\cdot k} = e^{-c k},
\end{align} where $c=\log{\left[\frac{(\lambda_h+\lambda_a)^2}{4\lambda_h \lambda_a}\right]}$. Because $\lambda_h>\lambda_a$, we have $(\lambda_h+\lambda_a)^2>4\lambda_h\lambda_a$, hence it holds that $c > \log{\left[\frac{4\lambda_h \lambda_a}{4\lambda_h \lambda_a}\right]}=0$. Putting the above analysis together, for some $c>0$, we have:

\begin{align}
\Pr\left[\sum_{i=1}^{k} T(\lambda_h)_i - \sum_{i=1}^{k} T(\lambda_a)_i>0\right]\leq\mathbb{E}\left[e^{\frac{\lambda_h-\lambda_a}{2}\cdot\sum_{i=1}^{k} \left(T(\lambda_h)_i - T(\lambda_a)_i\right)}\right]=e^{-ck}.\tag{6}
\end{align}

Note that our bound is slightly different (the exponential terms differ by a constant $c$) from the one shown in class, i.e., $e^{-c(k+1)}$. Nevertheless, they are of the same order of magnitude: $e^{-\Omega(k)}$.

## Security Analysis when $\Delta\neq 0$

The analysis is similar to the above case (i.e., $\Delta\to 0$). For the adversary, the broadcast latency $\Delta$ has no effect on the time intervals between blocks; for honest parties, when a new block is mined, it takes an additional $\Delta$ time (in the worst case) to send it to all honest parties. Therefore, the time taken to increase the longest honest chain by 1 is can be expressed as the random variable $T(\lambda_h)_i+\Delta$, where $T(\lambda_h)_i~\sim {\rm Exp}(\lambda_h)$.

In this case, the probability can be bounded as follows:
\begin{align}
&\Pr\left[\sum_{i=1}^{k} \left(T(\lambda_h)_i+\Delta\right) - \sum_{i=1}^{k} T(\lambda_a)_i>0\right]\\
=&\Pr\left[e^{\sum_{i=1}^{k} \left(T(\lambda_h)_i+\Delta - T(\lambda_a)_i\right)}>1\right]\\
=&\Pr\left[e^{t\cdot\sum_{i=1}^{k} \left(T(\lambda_h)_i+\Delta - T(\lambda_a)_i\right)}>1\right]\quad (\forall t>0)\\
\leq & \mathbb{E}\left[e^{t\cdot\sum_{i=1}^{k} \left(T(\lambda_h)_i+\Delta - T(\lambda_a)_i\right)}\right]\\
=&\mathbb{E}\left[\prod_{i=1}^{k} e^{t\cdot\left(T(\lambda_h)_i+\Delta-T(\lambda_a)_i\right)}\right] \\
=&\prod_{i=1}^{k} \left(\mathbb{E}\left[e^{tT(\lambda_h)_i}\right]\cdot\mathbb{E}\left[e^{-tT(\lambda_a)_i}\right]\right)\cdot e^{tk\Delta}\\
=&\left(\frac{\lambda_h}{\lambda_h-t}\cdot\frac{\lambda_a}{\lambda_a+t}\cdot e^{t\Delta}\right)^k .\tag{7}
\end{align}

Let $t=\frac{\lambda_h-\lambda_a}{2}$, we have
\begin{align}
\Pr\left[\sum_{i=1}^{k} \left(T(\lambda_h)_i+\Delta\right) - \sum_{i=1}^{k} T(\lambda_a)_i>0\right]&\leq \left(\frac{4\lambda_h\lambda_a}{(\lambda_h+\lambda_a)^2}\cdot e^{\frac{\lambda_h-\lambda_a}{2}\Delta}\right)^k\\
&=e^{-\left(\log\frac{(\lambda_h+\lambda_a)^2}{4\lambda_h\lambda_a}-\frac{\lambda_h-\lambda_a}{2}\Delta\right) k}.\tag{8}
\end{align}

Note that Eq. (8) is not tight, since in this case one may choose other $t$ to derive a tighter upper bound. Nevertheless, as we will show in the next Section, Eq. (8) is sufficient to show the effect of $\Delta$ on the probability of failure.

## Numerical Results

### Results of $\Delta\to0$

The following two figures show the numerical results when $\Delta\to0$. For each curve in the first figure, we fix the adversarial fraction $f$ and plot Eq. (6) *vs.* $k$, from which we can observe that as $k$ increases, the probability of the adversary's success decreases exponentially.

For each curve in the second figure, we fix $k$ and plot Eq. (6) *vs.* $f$. We can see that a larger $f$ leads to a larger probability of adversary's success, and the size of $k$ has a significant effect on the probability of failure.


### Results of $\Delta\neq0$

We fix $\lambda=\lambda_a+\lambda_h=1$, and plot the following figures based on Eq. (8). For the first figure, we further fix $f=0.3$ and vary $k$ from 1 to 50, from which we can observe that a larger $\Delta$ leads to a higher probability of adversary's success. Nevertheless, if we set $k$ to be large enough, the probability can still be sufficiently small (in fact, decreases exponentially *w.r.t.* $k$).

The curves of Eq. (8) *vs.* $f$ under different $\Delta$s are shown follows.

## Acknowledgements
We thank Jiamin Shen and Prateek Saxena for helpful discussions and feedback. The supplementary/review of this post by Jiamin can be found at https://www.dropbox.com/s/8mlc8lifcabj8pj/L6-review.pdf.