Probability.tex

We will focus our analysis on the attack that is the most interesting for the adversary, that is creating coins in an invalid block and then transferring them to another address. The adversary has two strategy choices: they can use either the direct setup depicted in \autoref{figure:withfakecreating} or the valid-between one depicted in \autoref{figure:withfakedoublecreating}. Furthermore, if they choose the direct setup, they can either add fake blocks until they manage to be in the setup they chose or retry every time until the have an acceptable number of fake blocks in their fork. We will capture the latter by adding a new parameter \(\overline{F}\) which indicates the number of fake blocks in the adversary's fork above which they retry the attack. \(\overline{F}\) directly impacts both the probability of success of the attack and the time \(t_{\text{setup}}\) taken to setup the attack. We also introduce \(N\) which is the number of times the adversary has to retry the attack until the manage to have a number of fake blocks smaller than \(\overline{F}\).

In the first section, we will introduce more formally the parameters used for our analysis. We will then compute the probability for a block to be mined assuming a \FC\ protocol with constant difficulty in \autoref{section:probasampled}. We then evaluate which strategies the adversary has when trying to mine a block in \autoref{section:miningstrategies} and determine the most optimal one. Knowing this strategy, we compute the time taken and the number of fake blocks necessary to mine a block in \autoref{section:blockmined}. Using these, we evaluate in \autoref{section:firstsetup} the first possible setup, that is the direct one depicted in \autoref{figure:withfakecreating} and analyse it in \autoref{section:firstsetupanalysis}. We will continue in \autoref{section:secondsetup} by evaluating the valid-between setup, depicted in \autoref{figure:withfakedoublecreating}, and will compare it to the direct setup in \autoref{section:comparesetups}. Finally, we will end our analysis by evaluating the error made by considering a constant difficulty protocol in \autoref{section:variabledifficulty}.

\section{Parameters}

We take into account the following parameters on which the adversary has no control:

\begin{itemize}
    \item \textbf{the adversary's computational power} \(\mu\);
    \item \textbf{\FC's security parameter} \(\delta\). \(\delta\) controls how succinct the \FC\ proof will be: the lower \(\delta\), the more efficient the proof is, but the less secure the protocol is.
\end{itemize}

Concerning what the adversary can choose, there is only two parameters:

\begin{itemize}
    \item \textbf{the fake blocks threshold} \(\overline{F}\) and, in a way, \textbf{the number of fake blocks in the fork} \(F\). The greater \(\overline{F}\), the faster the adversary is able to setup the attack, but the more likely they are to be caught by the client. Indeed, putting \(\overline{F}=0\) implies that the adversary retries the attack \(N\) times until they manage to place 0 fake blocks in their fork, hence ensuring the largest probability of success that is possible. Putting \(\overline{F}=+\infty\) on the other side ensures that the adversary minimises their cost: whatever the number of fake blocks they have to place within their fork, they will not retry the attack. As a consequence, if \(\overline{F}=+\infty\), then \(N=0\), since the adversary won't retry the attack;
    \item \textbf{the depth of the merging block} \(n-m\). This directly impacts both the \(\overline{F}\) necessary to setup the attack and its probability of success \(p_{\text{success}}\), since \FC\ is more likely to sample recent blocks than old ones.
\end{itemize}

The two parameters that are coins-related that we consider are:

\begin{itemize}
    \item \textbf{the cost} \(C\). While mining on their fork rather than on the main chain, the adversary loses coins, since they do not receive the coins they would have obtained by mining blocks on the main chain. Plus, the adversary still spends computational power trying to mine on their fork. Adding those two defines a cost per block for the adversary: the longer they have to mine on their fork, the more coins they lose. We denote this by a cost \(C\) that the adversary wants to minimise;
    \item \textbf{the maximal gain} \(\overline{G}\). On the other hand, the adversary has a limited maximum gain \(\overline{G}\) when running the attack. Indeed, it is very likely that a client won't accept a transaction involving too much coins. Hence, a simple but efficient defence against the \cs\ attack is to ensure that the minimum cost \(C\) that an adversary has to pay to run the attack is higher than the maximum adversarial gain \(\overline{G}\).
\end{itemize}

\begin{table}[ht]
        \centering
        \begin{tabular}{|c|c|}
          \hline
          Object & Representation\\
          \hline
          Blockchain & \(\mathsf{C}\)\\
          \hline
          Blockchain length &  \(n\)\\
          \hline
          Adversary's computational power &  \(\mu\)\\
          \hline
          Block  \(i\) of the chain &  \(\mathsf{C[}i\mathsf{]}\)\\
          \hline
          Block \(i\) of the chain in the adversary's fork & \(\mathsf{C[}i\mathsf{]}'\)\\
          \hline
          Blocks \(i\) (inclusive) to  \(j\) (exclusive) of the chain &  \(\mathsf{C[}i\mathsf{:}j\mathsf{]}\)\\
          \hline
          Position of the forking block & \(f\)\\
          \hline
          Position of the merging block & \(m\)\\
          \hline
          Fraction of block sampled with probability 1 at the end of the chain & \(\delta\)\\
          \hline
          Number of fake blocks in the fork & \(F\)\\
          \hline
          Maximum number of blocks that the adversary accepts in their fork & \(\overline{F}\)\\
          \hline
          Depth of the merging block & \(n - m\)\\
          \hline
          Adversary's cost & \(C\)\\
          \hline
          Adversary's maximal gain & \(\overline{G}\)\\
          \hline
          Time to set up the attack & \(t_{\text{setup}}\)\\
          \hline
          Total time to run the attack & \(t\)\\
          \hline
        \end{tabular}
        \caption{Notations used throughout the computation of the probability of success of the \cs\ attack.}
        \label{table:notationsProba}
      \end{table} 

Finally, two measures of time has to be differentiated:

\begin{itemize}
    \item \textbf{the time taken to set up the attack} \(t_{\text{setup}}\). This is the number of blocks during which the adversary would be mining on their fork rather than on the main chain, which is directly related to their cost \(C\);
    \item \textbf{the total time taken to run the attack} \(t\), which is the number of blocks mined on the main chain between the moment where the adversary began to mine on their fork and the moment the client launches the protocol.
\end{itemize}

Hence, a simple relation between these last two parameters can be found:
\[t=t_{\text{setup}} + n - m.\]

All these parameters are summarised in \autoref{table:notationsProba}.



The goal of the next sections is to compute the time \(t_{\text{setup}}\) taken to setup a given strategy and the probability of success \(p_{\text{success}}\) of this strategy as functions of \(\overline{F}\), \(\mu\), \(n - m\) and \(\delta\).

\section{Probability for some blocks to be sampled under a constant difficulty}
\label{section:probasampled}
The probability that a block is sampled is described in \cite{\FCCite}. The probability that a block at position \(x\geqslant n\,(1-\delta)\) is sampled is 1, while \textbf{the probability that a block at position \(x<n\,(1-\delta)\) is sampled} is given by:
\begin{align*}
  p_x &= \frac{1}{\ln(\delta)}\int_{\frac{x}{n}}^{\frac{x+1}{n}}\frac{\mathrm{d}t}{t-1}\\
      &= \frac{\ln\left(\left|\frac{x+1}{n}-1\right|\right)-\ln\left(\left|\frac{x}{n}-1\right|\right)}{\ln(\delta)}\\
      &= \frac{\ln\left(1-\frac{1}{n-x}\right)}{\ln(\delta)}.
\end{align*}
More generally, \textbf{the probability that at least one block in the range \(\Crange{a}{b}\) is sampled} is given by:
\begin{align*}
    p_{a,b} &= \frac{1}{\ln(\delta)}\,\int^{\frac{b}{n}}_{\frac{a}{n}}\frac{\mathrm{d}t}{t-1}\\
    &= \frac{\ln\left(\left|\frac{b}{n}-1\right|\right)-\ln\left(\left|\frac{a}{n}-1\right|\right)}{\ln(\delta)}\\
    &= \frac{\ln\left(\frac{n-b}{n-a}\right)}{\ln(\delta)}.
\end{align*}

\section{Adversarial strategies for mining a block}
\label{section:miningstrategies}
    When the adversary tries to mine a block in its fork (or the merging block), they have two strategies when they don't manage to mine it before the main chain mines the equivalent honest block:
    \begin{itemize}
        \item continue to try to mine the same block and when they manage to do it add a number of fake blocks equivalent to the number of blocks mined by the main chain meanwhile;
        \item give up on mining this block, add a fake block in lieu and try to mine the new block.
    \end{itemize}
    The only advantage of the first solution is that the adversary does not waste the computational power spent on trying to mine this block. However, according to the Bitcoin backbone protocol \cite{Backbone}, mining a block can be represented as a random variable following a geometric distribution, the one mining the block being the one that had the first success. Since the geometric distribution is memoryless, the adversary doesn't gain anything by continuing to try to mine the same block. Furthermore, the second solution allows the adversary to obfuscate the fake UTXOs they intend to use. Indeed, to know that a UTXO is fake, the client has no choice but to recursively follow a transaction until one is proven fake.
    
    Hence, we will in the following assume that the adversary follows the second strategy for mining a block, that is adding a fake block as soon as they know they have failed to mine the corresponding block.

\section{Time and number of fake blocks necessary for mining a block on the Bitcoin blockchain}
\label{section:blockmined}

\paragraph{Number of fake blocks to include in the chain to mine one block.} Since we know from \autoref{section:miningstrategies} that the best strategy for mining a block is giving up as soon as one knows that they failed to mine the block before the main chain, it follows that mining the forking block \(\Cindex{f+1}'\) does not add any fake blocks to the adversary's fork, since the forking block is supposed to be the first. Hence, the only thing to compute is the number of blocks it will take the adversary before they manage to mine \(\Cindex{f+1}'\) before the main chain mines \(\Cindex{f+2}\). Let us denote this time \(t_f\). \(t_f\) is a random variable that follows a geometric distribution with parameter \(\mu\) and with support \(\mathbf{N}^*\). Thus, \textbf{the expected number of blocks mined on the main chain while the adversary tries to mine \(\Cindex{f+1}'\)} is given by:
\[\E{t_f}=\frac{1}{\mu}.\]
Hence, in average, \(\frac{1}{\mu}\) blocks will be mined before the adversary manages to mine the forking block before the main chain manages to mine \(\Cindex{f+1}\).

Using a similar reasoning, mining a block \(x\) that is not the forking block will take \(t_x\) blocks, where \(t_x\) follows a geometric distribution with parameter \(\mu\) and with support \(\mathbf{N}^*\). The adversary would then have to include \(t_x-1\) fake blocks in their fork.

\paragraph{Computing the parameters  of the geometric distributions  involved in the mining process.} We have to define what it means for the adversary to have a portion \(\mu\) of the total computational power. This will be used in the second setup, since the adversary has to mine two blocks faster than the main chain does. Since we know that we can model the number of tries necessary to mine a block follows a geometric distribution with support \(\mathbf{N}^*\) and whose parameter is a function of the total computational power, we can define two random variables \(H\) and \(A\) which represent the number of times the honest miners (respectively the adversary) have to query the random oracle defined in \cite{Backbone} to manage to mine the block. These two random variables are independent and have respectively one unknown parameter, \(a\) or \(h\). What we know is that a \(\mu\) portion of the blocks are going to be mined by the adversary. Hence, we have:
\[\P{A<H}+\beta\,\P{A=H}=\mu.\]
Here, \(\beta\) is a network parameter that captures how often an adversary is designed as the miner of a block when them and a honest miner simultaneously sent a PoW to the remaining of the network. For instance, if the adversary is able to completely reorder every message sent during a round, then \(\beta\) would be nil. This means that the adversary mines more than a \(\mu\) portion of the blocks: they would mine a \(\mu\) portion of the blocks plus those for which they queried the random oracle as much as another miner. For a balanced system, \(\beta\) would be equal to \(\frac12\): both the adversary, that has a \(\mu\) portion of the total computational power, and the remaining of the network, that has a \(1-\mu\) portion of the computational power would mine the same number of blocks for which they queried the random oracle as much as the other. Hence, the adversary would mine a \(\mu\) portion of the blocks, while the remaining of the miners would mine a \(1-\mu\) portion of the blocks.
Thus:
\begin{align*}
    \mu &= \sum_{i=1}^{+\infty}\P{(A\leqslant i)\cap(H=i+1)} + \beta\,\sum_{i=1}^{+\infty}\P{(A=i)\cap(H=i)}\\
    &= \sum_{i=1}^{+\infty}\P{A\leqslant i}\,\P{H=i+1} + \beta\,\sum_{i=1}^{+\infty}\P{A=i}\,\P{H=i}\\
    &= h\,\sum_{i=1}^{+\infty}\left[1-(1-a)^i\right]\,(1-h)^i + a\,h\,\beta\,\sum_{i=1}^{+\infty}\left[(1-a)\,(1-h)\right]^{i-1}\\
    &= h\,\left[\sum_{i=1}^{+\infty}(1-h)^i-\sum_{i=1}^{+\infty}\left[(1-a)\,(1-h)\right]^i\right] + \frac{a\,h\,\beta}{1-(1-a)\,(1-h)}\\
    &= 1 - h - \frac{h\,(1-a)\,(1-h)}{1-(1-a)\,(1-h)} + \frac{a\,h\,\beta}{1-(1-a)\,(1-h)}\\
    &= \frac{1-(1-a)\,(1-h)-h+h\,(1-a)\,(1-h)-h\,(1-a)\,(1-h)+a\,h\,\beta}{1-(1-a)\,(1-h)}\\
    &= a\,\frac{1-h\,(1-\beta)}{1-(1-a)\,(1-h)}\\
    &= a\,\frac{1-h\,(1-\beta)}{a+h-a\,h}.
\end{align*}
Note that the choice of \(a\) does not matter in this case. Hence, if we define \(h\) to be 1, we would have \(a=\frac{\mu}{\beta}\). Thus, as long as \(\mu\leqslant\beta\), we can define \(a\) to be equal to \(\frac{\mu}{\beta}\). In our analysis, we will assume that, contrarily to the original \FC\ paper, the adversary cannot reorder the messages during a round. Hence, we set \(\beta=\frac12\), and thus \(a=2\,\mu\).

\section{Probability for the \cs\ attack to succeed using the direct setup}
\label{section:firstsetup}
    As a recall, the adversary wants to have a similar setup to the one depicted on \autoref{figure:withfakecreating}. This is essentially a two-steps process: the adversary firstly mines \(\Cindex{f+1}'\), then mines the merging block \(\Cindex{m}\). 
    
    \subsection{Computing how many times has the adversary to retry the attack}
    
    According to \autoref{section:blockmined}, mining the forking block takes in average \(t_f=\frac{1}{\mu}\) blocks. Once the forking block has been mined, the only thing left to do is mining the merging block. Remember however that if the adversary has to include more than \(\overline{F}\) fake blocks in their fork, then they redo everything from the beginning. We are thus interested in the probability that \(F=t_m-1\leqslant\overline{F}\). Since \(F=t_m-1\) follows a geometric distribution with parameter \(\mu\) and with support \(\mathbf{N}\), we know that \textbf{the probability that the adversary doesn't have to redo the attack} is given by:
    \[\P{F\leqslant\overline{F}} = 1 - (1-\mu)^{\overline{F}+1}.\]
    Each time the adversary fails to have \(F\leqslant\overline{F}\), \(t_f+\overline{F}+1\) blocks have been mined on the main chain. The number \(N\) of times the adversary has to retry follows a geometric distribution with parameter \(\P{F\leqslant\overline{F}}\) and with support \(\mathbf{N}\). Hence, \textbf{the number of attempts that the adversary will make in average before managing to have \(F\leqslant\overline{F}\)} is given by:
    \[\E{N}=\frac{1-\P{F\leqslant\overline{F}}}{\P{F\leqslant\overline{F}}}.\]
    
    \subsection{Average number of fake blocks included in the fork}
    
    Finally, we are interested in \(\ES{F}{F\leqslant\overline{F}}\), which is \textbf{the average number of fake blocks the adversary has included in their fork knowing they succeeded to put the attack in place}. We have:
    \[\ES{F}{F\leqslant\overline{F}} = \sum_{k=0}^{\overline{F}}k\,\PS{F=k}{F\leqslant\overline{F}}.\]
    Hence:
    \begin{align*}
        \ES{F}{F=\leqslant\overline{F}} &= \sum_{k=0}^{\overline{F}}k\,\frac{\P{(F=k)\cap(F\leqslant\overline{F})}}{\P{F\leqslant\overline{F}}}\\
        &= \frac{1}{\P{F\leqslant\overline{F}}}\,\sum_{k=0}^{\overline{F}}k\,\mu\,(1-\mu)^k\\
        &= \frac{\mu\,(1-\mu)}{1 - (1-\mu)^{\overline{F}+1}}\,\sum_{k=0}^{\overline{F}}k\,(1-\mu)^{k-1}\\
        &= \frac{\mu\,(1-\mu)\,\left[1-(1-\mu)^{\overline{F}}\,(\overline{F}\,\mu+1)\right]}{\left[1 - (1-\mu)^{\overline{F}+1}\right]\,\mu^2}\\
        &= \frac{(1-\mu)\,\left[1-(1-\mu)^{\overline{F}}\,(\overline{F}\,\mu+1)\right]}{\mu\,\left[1 - (1-\mu)^{\overline{F}+1}\right]}.
    \end{align*}
    
    \subsection{Time taken to set up the attack}
    
    We have to add 1 to the previous formula since the adversary mines the merging block itself. Hence, \textbf{the number of blocks that will be mined while the adversary tries to have this setup} is given by:
    \[t_{\text{setup}} = \sum_{k=1}^N\,\left(t_{m, k} + \overline{F} + 1\right) + t_m + F + 1\,.\]
    Hence, in average, we have \(\ES{t_{\text{setup}}}{\mu,\overline{F}}\) being equal to:
    \begin{align*}
         &\phantom{=}\ES{\sum_{k=1}^N\,\left(t_{m, k} + \overline{F} + 1\right)}{\mu,\overline{F}}+\frac{1}{\mu}+\frac{(1-\mu)\,\left[1-(1-\mu)^{\overline{F}}\,(\overline{F}\,\mu+1)\right]}{\mu\,\left[1 - (1-\mu)^{\overline{F}+1}\right]} + 1\\
        &=\ES{N}{\mu,\overline{F}}\,\ES{t_{m, k} + \overline{F} + 1}{\mu,\overline{F}}+\frac{1}{\mu}+\frac{(1-\mu)\,\left[1-(1-\mu)^{\overline{F}}\,(\overline{F}\,\mu+1)\right]}{\mu\,\left[1 - (1-\mu)^{\overline{F}+1}\right]} + 1\\
        &=\frac{(1-\mu)^{\overline{F}+1}}{1 - (1-\mu)^{\overline{F}+1}}\,\left[\frac{1}{\mu}+\overline{F} + 1\right] + \frac{1}{\mu} + \frac{(1-\mu)\,\left[1-(1-\mu)^{\overline{F}}\,(\overline{F}\,\mu+1)\right]}{\mu\,\left[1 - (1-\mu)^{\overline{F}+1}\right]} + 1.
    \end{align*}
    This formula probably deserves some explanation. It is basically the sum of the different parts in the setup we discussed. The first term is:
    \[\underbrace{\frac{(1-\mu)^{\overline{F}+1}}{1 - (1-\mu)^{\overline{F}+1}}}_{\text{Number of failures}}\,\underbrace{\left[\frac{1}{\mu}+\overline{F} + 1\right]}_{\text{Blocks per failure}}\]
    which catches the expected number of blocks mined before the adversary manages to put the setup in place. It's the product between the expected number of failures and the expected number of blocks mined by the main chain meanwhile. While the first is given by \(\P{F\leqslant\overline{F}}\), the second is given by the sum of the expected number of blocks to be mined to mine the forking block, that is \(\frac{1}{\mu}\), plus \(\overline{F}+1\) blocks during which the adversary tried to mine the merging block.
    
    Then, the second term is \(\frac{1}{\mu}\), which is the expected number of blocks mined by the main chain while the adversary was trying to mine the merging block, on the attempt where they managed to place less than \(\overline{F}\) fake blocks in their fork. Finally, the final term is:
    \[\frac{(1-\mu)\,\left[1-(1-\mu)^{\overline{F}}\,(\overline{F}\,\mu+1)\right]}{\mu\,\left[1 - (1-\mu)^{\overline{F}+1}\right]} + 1\]
    which is the expected number of fake blocks that the adversary had to add to their fork plus the merging block. It is now possible to get a much simpler formula for \(\ES{t_{\text{setup}}}{\mu,\overline{F}}\) using these terms:
    \begin{align*}
         &\phantom{=}\frac{(1-\mu)^{\overline{F}+1}}{1 - (1-\mu)^{\overline{F}+1}}\,\left[\frac{1}{\mu}+\overline{F} + 1\right] + \frac{1}{\mu} + \frac{(1-\mu)\,\left[1-(1-\mu)^{\overline{F}}\,(\overline{F}\,\mu+1)\right]}{\mu\,\left[1 - (1-\mu)^{\overline{F}+1}\right]} + 1\\
        &= \left[\frac{1}{1-(1-\mu)^{\overline{F}+1}}-1\right]\,\left[\frac{1}{\mu}+\overline{F} + 1\right] + \frac{(1-\mu)\,\left[1-(1-\mu)^{\overline{F}}\,(\overline{F}\,\mu+1)\right]}{\mu\,\left[1 - (1-\mu)^{\overline{F}+1}\right]} + 1 + \frac{1}{\mu}\\
        &= \frac{1}{\mu\,\left[1-(1-\mu)^{\overline{F}+1}\right]}\,\left[2+\overline{F}\,\mu\,\left(1-(1-\mu)^{\overline{F}+1}\right)-(1-\mu)^{\overline{F}+1}\right] - \overline{F}\\
        &= \frac{1}{\mu\,\left[1-(1-\mu)^{\overline{F}+1}\right]}\,\left[2-(1-\mu)^{\overline{F}+1}\right]\\
        &= \frac{1}{\mu\,\left[1-(1-\mu)^{\overline{F}+1}\right]} + \frac{1}{\mu}\\
        &= \frac{1}{\mu}\,\left[1 + \frac{1}{1 - (1-\mu)^{T+1}}\right].
    \end{align*}
    
    \subsection{Probability of success of the \cs\ attack using the direct setup}
    
    Since we know the distribution of the number \(F\) of fake blocks that the adversary will include in their fork given \(\overline{F}\), we can also compute the probability that at least one of these blocks is sampled. Plus, it is important to note that the client must not sample the merging block if no fake block is present in the fork, that is if \(F=0\). This leads to the following \textbf{probability of success \(p_{\text{success}}\)}:
    \begin{align*}
        &\phantom{=}\left(1 - p_m\right)\,\PS{F=0}{F\leqslant\overline{F}} + \left(1 - p_{m-F,m}\right)\,\left(1-\PS{F=0}{F\leqslant\overline{F}}\right)\\
        &= \left[1-\frac{\ln\left(1-\frac{1}{n - m}\right)}{\ln(\delta)}\right]\,\frac{\mu}{1-(1-\mu)^{\overline{F}+1}}+\left[1-\frac{\ln\left(\frac{n-m}{n-m+F}\right)}{\ln(\delta)}\right]\,\left[1-\frac{\mu}{1-(1-\mu)^{\overline{F}+1}}\right]\\
        &= 1 - \frac{\mu\,\ln\left(1-\frac{1}{n - m}\right)}{\ln(\delta)\,\left[1-(1-\mu)^{\overline{F}+1}\right]}-\left[1-\frac{\mu}{1-(1-\mu)^{\overline{F}+1}}\right]\,\frac{\ln\left(1-\frac{F}{n-m+F}\right)}{\ln(\delta)}.
    \end{align*}
    Hence, \textbf{the average probability of success} \(\ES{p_{\text{success}}}{\mu,F\leqslant\overline{F}}\) is given by:
    \[1 - \frac{\mu\,\ln\left(1-\frac{1}{n - m}\right)}{\ln(\delta)\,\left[1-(1-\mu)^{\overline{F}+1}\right]}-\left[1-\frac{\mu}{1-(1-\mu)^{\overline{F}+1}}\right]\,\frac{\mu}{\ln(\delta)\,\left[1-(1-\mu)^{\overline{F}+1}\right]}\,g\left(\mu, \overline{F}, n - m\right)\]
    where:
    \[g\left(\mu, \overline{F}, n - m\right) = \sum_{k=1}^{\overline{F}}\ln\left(1-\frac{k}{k+n-m}\right)\,(1-\mu)^k.\]
    This can be written in a slightly more condensed form:
    \[1-\frac{\mu}{\ln(\delta)\,\left[1-(1-\mu)^{\overline{F}+1}\right]}\,\left[\ln\left(1-\frac{1}{n - m}\right) + g\left(\mu, \overline{F}, n - m\right)\,\left(1+\frac{\mu}{1-(1-\mu)^{\overline{F}+1}}\right)\right].\]
    It is now possible to visualise how the parameters influence the probability of success of the attack, which is the goal of the next section.
    
\section{Analysis of the \cs\ attack on the \FC\ protocol using the direct setup}
\label{section:firstsetupanalysis}
During this section, we will assume that \(\delta=2^{-10}\), since this is the value taken as example in \cite{\FCCite}.

\subsection{Impact of the depth of the merging block on the probability of success}

As a recall, the goal of the adversary is to minimise their cost \(C\) so that it is lower than their potential maximal gain \(\overline{G}\). Plus, once they have setup the attack, they want it to succeed with high probability. The only parameter that affects their cost is \(\overline{F}\): the higher \(\overline{F}\), the less they would have to mine on their fork rather than on the main chain, this the less they lose coins. However, increasing \(\overline{F}\) leads to decreasing the probability of success of the attack, what can be counterbalanced by increasing \(n-m\). Hence, what can be interesting to look at is the evolution of the probability of success of the attack, given that the adversary set \(\overline{F}=+\infty\) and has a portion \(\mu\) of the total computational power. This is shown on \autoref{figure:nmmimpact}.

\begin{figure}[ht]
    \centering
    \begin{tikzpicture}
        \begin{axis}[grid=major,
            xlabel={\(n - m\)},
            ylabel={\(\ES{p_{\text{success}}}{\overline{F}=+\infty}\)},
            legend entries={\(\mu=50\%\), \(\mu=33\%\), \(\mu=25\%\), \(\mu=10\%\)},
            no marks,
            legend style={at={(1,0)},anchor=south east},
            width=\figurewidth\textwidth,
            xmode=log
        ]
            \addplot table[x index=0, y index=1]{data/first_setup_analysis/nmmimpact.txt};
            \addplot table[x index=0, y index=2]{data/first_setup_analysis/nmmimpact.txt};
            \addplot table[x index=0, y index=3]{data/first_setup_analysis/nmmimpact.txt};
            \addplot table[x index=0, y index=4]{data/first_setup_analysis/nmmimpact.txt};
        \end{axis}
    \end{tikzpicture}
    \caption{The convergence of \(p_{\text{success}}\) to 1 as \(n - m\) goes to infinity implies that an adversary can have a probability of success as high as they want, no matter how much fake blocks they include in their forks, as long as they wait long enough.}
    \label{figure:nmmimpact}
\end{figure}

The fact that \(\ES{p_{\text{success}}}{\overline{F}=+\infty}\) converges to 1 as \(n - m\) goes to infinity indicates that no matter what \(\overline{F}\) is, the adversary can manage to have a very high probability of success as long as they wait long enough for \(n - m\) to be high. Hence, we introduce a final parameter \(\overline{t}\) which designates the maximum average time that an adversary is willing to wait before the moment they setup the attack and the moment they send the proof of inclusion to the verifier. As a consequence, this leads to a largest \(n - m\) possible, since:
\[n - m\leqslant\overline{t}-\ES{t_{\text{setup}}}{\mu, \overline{F}}.\]
Hence, the expected strategy for the adversary is the following: using \(\overline{t}\) they can compute the largest \(n - m\) possible according to what they chose for \(\overline{F}\). Since there is now a largest possible \(n - m\), the adversary cannot always set \(\overline{F}=+\infty\), especially when either \(\mu\) is low or when the desired \(p_{\text{success}}\) is high. This phenomenon is shown on \autoref{figure:setuptimewithpsuccess}. Note that the adversary's cost is equal to \(\ES{t_{\text{setup}}}{\mu,\overline{F}} - 1\), since the merging block is mined on the main chain.

\begin{figure}[ht]
    \centering
    \begin{subfigure}[b]{0.45\textwidth}
        \centering 
        \begin{tikzpicture}
            \begin{axis}[grid=major,
                xlabel={\(\ES{p_{\text{success}}}{F\leqslant\overline{F}}\)},
                ylabel={\(\ES{t_{\text{setup}}}{\mu,\overline{F}} - 1\)},
                legend entries={\(\mu=50\%\), \(\mu=33\%\), \(\mu=25\%\), \(\mu=10\%\)},
                no marks,
                legend style={at={(0,1)}, anchor=north west, nodes={scale=0.57857, transform shape}},
                width=.9\textwidth,
            ]
                \addplot table[x index=0, y index=1]{data/first_setup_analysis/setuptimewithpsuccess5050.txt};
                \addplot table[x index=0, y index=1]{data/first_setup_analysis/setuptimewithpsuccess3350.txt};
                \addplot table[x index=0, y index=1]{data/first_setup_analysis/setuptimewithpsuccess2550.txt};
                \addplot table[x index=0, y index=1]{data/first_setup_analysis/setuptimewithpsuccess1050.txt};
            \end{axis}
        \end{tikzpicture}
        \caption{Adversary's cost for \(\overline{t}=50\)}
        \label{figure:setuptimewithpsuccess144}
    \end{subfigure}
    ~
    \begin{subfigure}[b]{0.45\textwidth}
        \centering
        \begin{tikzpicture}
            \begin{axis}[grid=major,
                xlabel={\(\ES{p_{\text{success}}}{F\leqslant\overline{F}}\)},
                ylabel={\(\ES{t_{\text{setup}}}{\mu,\overline{F}} - 1\)},
                legend entries={\(\mu=50\%\), \(\mu=33\%\), \(\mu=25\%\), \(\mu=10\%\)},
                no marks,
                legend style={at={(0,1)}, anchor=north west, nodes={scale=0.57857, transform shape}},
                width=.9\textwidth,
            ]
                \addplot table[x index=0, y index=1]{data/first_setup_analysis/setuptimewithpsuccess50200.txt};
                \addplot table[x index=0, y index=1]{data/first_setup_analysis/setuptimewithpsuccess33200.txt};
                \addplot table[x index=0, y index=1]{data/first_setup_analysis/setuptimewithpsuccess25200.txt};
                \addplot table[x index=0, y index=1]{data/first_setup_analysis/setuptimewithpsuccess10200.txt};
            \end{axis}
        \end{tikzpicture}
        \caption{Adversary's cost for \(\overline{t}=200\)}
        \label{figure:setuptimewithpsuccess288}
    \end{subfigure}
    \caption{Evolution of the adversary's cost as \(\overline{t}\) grows. For a smaller \(\overline{t}\), the adversary is forced to decrease \(\overline{F}\), thus increasing its cost, in order to get a high probability of success. Increasing it however allows the adversary to consider higher \(n-m\) for the same \(\overline{F}\), hence increasing their probability of success, which is shown by the curves being sharper for high probability of success.}
    \label{figure:setuptimewithpsuccess}
\end{figure}

\subsection{Choosing the optimal \(\overline{F}\)}

What these figures show is that as expected, \(\overline{t}\) impacts the adversary's choice concerning \(\overline{F}\). As seen on \autoref{figure:setuptimewithpsuccess144}, it is easier for high computational powers to set \(\overline{F}=+\infty\), which is represented by a constant time in order to setup the attack. On the other hand, a smaller computational power is forced to decrease \(\overline{F}\) in order to obtain the probability they want. Using the same logic, even with a high computational power, the adversary is forced to decrease \(\overline{F}\) in order to obtain a very high \(p_{\text{success}}\), since \(n - m\) is upper bound because of \(\overline{t}\). This is shown on \autoref{figure:setuptimewithpsuccesszoom}.

\begin{figure}[ht]
    \centering
    \begin{tikzpicture}
        \begin{axis}[axis x line=none,
            axis y line*=right,
            grid=major,
            grid style=dashed,
            ylabel={Corresponding optimal \(\overline{F}\)},
            width=\figurewidth\textwidth,
        ]
            \addplot[dashed, blue] table[x index=0, y index=2]{data/first_setup_analysis/setuptimewithpsuccesszoom50.txt};
            \addplot[dashed, red] table[x index=0, y index=2]{data/first_setup_analysis/setuptimewithpsuccesszoom33.txt};
            \addplot[dashed, brown] table[x index=0, y index=2]{data/first_setup_analysis/setuptimewithpsuccesszoom25.txt};
        \end{axis}
        
        \begin{axis}[grid=major,
            xlabel={\(\ES{p_{\text{success}}}{F\leqslant\overline{F}}\)},
            ylabel={\(\ES{t_{\text{setup}}}{\mu,\overline{F}} - 1\)},
            legend entries={\(\mu=50\%\), \(\mu=33\%\), \(\mu=25\%\)},
            no marks,
            legend style={at={(0,1)},anchor=north west},
            width=\figurewidth\textwidth,
            scaled x ticks=base 10:2
        ]
            \addplot table[x index=0, y index=1]{data/first_setup_analysis/setuptimewithpsuccesszoom50.txt};
            \addplot table[x index=0, y index=1]{data/first_setup_analysis/setuptimewithpsuccesszoom33.txt};
            \addplot table[x index=0, y index=1]{data/first_setup_analysis/setuptimewithpsuccesszoom25.txt};
        \end{axis}
    \end{tikzpicture}
    \caption{Adversary's cost for \(\overline{t}=50\) for a high \(\ES{p_{\text{success}}}{F\leqslant\overline{F}}\) along with corresponding \(\overline{F}\). Dashed lines correspond to \(\overline{F}\). The structure in steps of these curves indicates that the adversary uses the largest \(n-m\) they can to have the desired probability of success. Once this is no more possible to obtain the desired probability with the largest \(n-m\) possible, it decreases \(\overline{F}\) in order to increase the largest \(n-m\) possible.}
    \label{figure:setuptimewithpsuccesszoom}
\end{figure}

The structure of the curves is also consistent with what we were expecting. Indeed, the adversary can use the biggest \(n - m\) at their disposal to have a given \(p_{\text{success}}\) with \(\overline{F}=+\infty\). Once this is not enough to get the desired probability, the adversary decreases \(\overline{F}\) and uses the next largest possible \(n - m\). This eventually leads to representing \(\ES{p_{\text{success}}}{\mu,\overline{F}}\) as a step function of \(p_{\text{success}}\). Furthermore, since that we know that for \(\overline{t}\) being not too small and \(p_{\text{success}}\) not being too close to 1 the adversary will set \(\overline{F}=+\infty\), then its cost will be equal to \(\frac{2}{\mu}-1\). This asymptote is shown on \autoref{figure:costwithmu}.

\begin{figure}[ht]
    \centering
    \begin{subfigure}[b]{0.45\textwidth}
        \centering 
        \begin{tikzpicture}
            \begin{axis}[grid=major,
                xlabel={\(\mu\)},
                ylabel={Number of blocks},
                legend entries={\(\ES{t_{\text{setup}}}{\mu,\overline{F}} - 1\), \(\frac{2}{\mu} - 1\)},
                no marks,
                legend style={at={(1,1)}, anchor=north east, nodes={scale=0.57857, transform shape}},
                width=.9\textwidth,
                xmin=0
            ]
                \addplot table[x index=0, y index=1]{data/first_setup_analysis/costwithmu50.txt};
                \addplot[dashed, red] table[x index=0, y index=2]{data/first_setup_analysis/costwithmu50.txt};
            \end{axis}
        \end{tikzpicture}
        \caption{Adversary's cost for \(\overline{t}=50\)}
        \label{figure:costwithmu144}
    \end{subfigure}
    ~
    \begin{subfigure}[b]{0.45\textwidth}
        \centering
        \begin{tikzpicture}
            \begin{axis}[grid=major,
                xlabel={\(\mu\)},
                ylabel={Number of blocks},
                legend entries={\(\ES{t_{\text{setup}}}{\mu,\overline{F}} - 1\), \(\frac{2}{\mu} - 1\)},
                no marks,
                legend style={at={(1,1)}, anchor=north east, nodes={scale=0.57857, transform shape}},
                width=.9\textwidth,
                xmin=0
            ]
                \addplot table[x index=0, y index=1]{data/first_setup_analysis/costwithmu200.txt};
                \addplot[dashed, red] table[x index=0, y index=2]{data/first_setup_analysis/costwithmu200.txt};
            \end{axis}
        \end{tikzpicture}
        \caption{Adversary's cost for \(\overline{t}=200\)}
        \label{figure:costwithmu288}
    \end{subfigure}
    \caption{Adversary's cost in order to have an average probability of success of \SI{99}{\percent}. It shows that if an adversary is willing to wait as long as it takes to have the desired probability of success, then their cost, which is the minimal one, is given by \(\frac{2}{\mu}-1\).}
    \label{figure:costwithmu}
\end{figure}

\subsection{Minimal cost of the \cs\ attack using the direct setup}

Hence, it is possible using this asymptote to derive the actual cost for an attacker which sets \(\overline{t}=+\infty\). We will not include the cost that the adversary has to pay to run physical devices that mine blocks, since this is a cost they will pay whatever they do. However, we must take into account the coins that the adversary loses by not mining on the main chain. According to \cite{BlockReward}, mining a block is currently worth \SI{6.25}{\bitcoin}. Plus, according to \cite{BitcoinValue}, a Bitcoin coin is currently worth \SI{11826.90}[\$]{}. Hence, if the adversary owns a portion \(\mu\) of the total computational power, then they lose \(\num{73918.125}\,\mu\) USD in average per block mined on the main chain while they are mining on their fork. Since they will in average spend \(\frac{2}{\mu}-1\) blocks mining on their fork, it follows that \textbf{the cost of the \cs\ attack on \FC} is given by:
\[C=\num{73918.125}\,(2-\mu).\]
This is not exactly true however. Indeed, the attack requires that the adversary mines the merging block on the honest chain. Hence, the attack requires that the adversary gets the award for having mined this block. While mining a block, in average, is worth \(\num{73918.125}\,\mu\) USD, this block will, in average, makes him win \(\num{73918.125}\,(1-\mu)\) USD. Hence, \textbf{the total cost of the attack} is given by  \(C=\num{73918.125}\,(2-\mu) - \num{73918.125}\,(1-\mu)\), that is:
\[C=\SI{73918.125}[\$]{}.\]
Interestingly enough, this cost does not depend on \(\mu\). This is due to the fact that an adversary with less computational power loses less per block they don't mine, but mine more blocks.
    
\section{Probability for the \cs\ attack on \FC to succeed using the valid-between setup}
\label{section:secondsetup}
We now want to compute the cost that the adversary has to pay to put the setup depicted on \autoref{figure:withfakedoublecreating} in place. This setup only makes sense when the adversary includes no other fake block than the one used to create coins. Indeed, the goal is to lower the probability that the attack fails because of the merging block being sampled. Thus, adding a fake block for this purpose makes no sense.

\subsection{Time to set up the \cs\ attack using the valid-between setup}

We can use a similar reasoning to the one in \autoref{section:firstsetup}. First of all, the adversary has to mine \(\Cindex{f+1}'\), in which they will include the fake UTXOs. They don't gain anything in continuing to try to mine \(\Cindex{f+1}'\) if they hear about \(\Cindex{f+1}\) before they manage to mine it. Hence, they will in average wait \(\frac{1}{\mu}\) blocks before they manage to mine \(\Cindex{f+1}'\) before the main chain mines the equivalent honest block, according to \autoref{section:blockmined}.

Starting from here, the adversary has to mine both \(\Cindex{f+2}'\) and \Cindex{m} before the main chain mines the corresponding honest blocks. However, even if they manage to mine \(\Cindex{f+2}'\) before the main chain mines \Cindex{f+2}, they still have to wait to hear about \Cindex{f+2} so that they can begin to mine the merging block.

According to \autoref{section:blockmined}, let us call \(A_x\) the random variable that counts the number of queries the adversary has to make to the random oracle described in \cite{Backbone} to mine the block at position \(x\). This random variable follows a geometric distribution with parameter \(2\,\mu\) and support \(\mathbf{N}^*\). Furthermore, let us denote \(H_x\) the number of queries that the honest miners have to make. \(H_x\) follows a geometric distribution with support \(\mathbf{N}^*\) and parameter 1. Hence, \(H_x\) is a constant random variable of value \(1\). \textbf{The probability that the adversary manages to put the attack in place} is then:
\[\P{\max\left(A_{f+2},H_{f+2}\right)+A_{m} < H_{f+2}+H_{m}} + \frac12\,\P{\max\left(A_{f+2},H_{f+2}\right)+A_{m} = H_{f+2}+H_{m}}\]
or more simply:
\[\frac12\,\P{A_{f+2}+A_{m} = 2}.\]
Hence, this probability is equal to:
\begin{align*}
    \frac12\,\P{A_{f+2}+A_{m} = 2} &= \frac12\P{\left(A_{f+2}=1\right)\cap\left(A_{m}=1\right)}\\
    &= \frac12\P{A_{f+2}=1}\,\P{A_{m}=1}\\
    &= 2\,\mu^2.
\end{align*}
Thus, the adversary has in average to make \(\frac{1-2\mu^2}{2\,\mu^2}\) tries before they manage to setup the attack. At each attempt, the adversary will wait the time necessary to mine the forking block, that is \(\frac{1}{\mu}\) in average, plus the two other blocks they tried to mine. Hence, \textbf{the average time in blocks the adversary has to wait} is given by:
\[\ES{t_{\text{setup}}}{\mu} = \frac{1-2\,\mu^2}{2\,\mu^2}\,\left(2+\frac{1}{\mu}\right)+3.\]

\subsection{Probability of success of the \cs\ attack using the valid-between setup}

It is then possible to compute \(p_{\text{success}}\) using the previous formula. The attack fails if \Cindex{m} and \(\Cindex{f+2}'\) are both sampled or if \(\Cindex{m}\) is sampled and \(m\) is even. Let us call \(E_x\) the event \enquote{the block \(\Cindex{x}\) is sampled}. Then, \textbf{the probability of success of the attack} is given by:
\begin{align*}
    p_{\text{success}} &= \PS{\text{Success}}{E_{m}}\,\P{E_{m}} + \PS{\text{Success}}{\overline{E_{m}}}\,\P{\overline{E_{m}}}\\
    &= \P{\overline{E_{m}}} + \P{E_{m}}\,\P{\overline{E_{m-1}}\cap\left(m\ \mathrm{mod}\ 2=0\right)}\\
    &= 1 - p_{m} + \frac12\,p_{m}\,\left(1-p_{m-1}\right)\\
    &= 1 - \frac12\,p_{m} - \frac12\,p_{m}\,p_{m-1}\\
    &= 1 - \frac12\,p_{m} - \frac12\,p_{m-1,m+1}\\
    &= 1 - \frac{\ln\left(1 - \frac{1}{n - m}\right) + \ln\left(\frac{n - m-1}{n - m+1}\right)}{2\,\ln(\delta)}\\
    &= 1 - \frac{\ln\left(1 - \frac{1}{n - m}\right) + \ln\left(1-\frac{2}{n - m+1}\right)}{2\,\ln(\delta)}.
\end{align*}
The next section will analyse this method and compare it to the first one.

\section{Analysis of the \cs\ attack on \FC\ using the valid-between setup}
We will use the same reasoning as the one made in \autoref{section:firstsetupanalysis}. Since we assume that the adversary can wait as long as they want, then they can have \(p_{\text{success}}\) as close to 1 as they desire. However, \textbf{the cost of the attack} is now given by:
\begin{align*}
    C &= \num{73918.125}\,\mu\,\left[\frac{1-2\,\mu^2}{2\,\mu^2}\,\left(2+\frac{1}{\mu}\right)+2\right] - \num{73918.125}\,(1-\mu) \\
    &= \num{73918.125}\,\left[\frac{1-2\,\mu^2}{2\,\mu^3}\,\left(2\,\mu+1\right)+1+\mu\right]\\
    &= \num{73918.125} + \num{73918.128}\,\frac{1+2\,\mu-2\,\mu^2-2\,\mu^3}{2\,\mu}
\end{align*}
which is clearly higher than the one induced by the first setup, since \SI{73918.125}[\$]{} was already the average cost.

\section{Comparison between the direct setup and the valid-between setup for a \cs\ attack}
\label{section:comparesetups}

Even though the direct setup is clearly cheaper if the adversary waits as long as they have to, what may be interesting is to compare these methods in terms of time. Experimentally, we found that for \(n - m = 22\), the probability of success of the valid-between setup is above \SI{99}{\percent}. Hence, we can compute the cost of the first setup if the adversary wants a \SI{99}{\percent} chance probability of success while waiting less than \(22+\ES{t_{\text{setup}}}{\mu}\) blocks, where \(t_{\text{setup}}\) here refers to the second setup. This is shown on \autoref{figure:comparecost}.

\begin{figure}[ht]
    \centering
    \begin{tikzpicture}
        \begin{axis}[grid=major,
            xlabel={\(\mu\)},
            ylabel={Cost \(C\) (\$)},
            legend entries={First setup with \(\overline{t}=22+\ES{t_{\text{setup}}}{\mu}\), Second setup},
            no marks,
            legend style={at={(1,1)},anchor=north east},
            width=\figurewidth\textwidth
        ]
            \addplot table[x index=0, y index=1]{data/first_setup_analysis/comparecost1.txt};
            \addplot table[x index=0, y index=1]{data/first_setup_analysis/comparecost2.txt};
        \end{axis}
    \end{tikzpicture}
    \caption{Comparison of the two setups. Even for high hashrates, the cost associated with the valid-between setup is much higher than the one associated with the direct setup. Hence, the direct setup should always be preferred to the valid-between one.}
    \label{figure:comparecost}
\end{figure}

What this figure shows is that it is always in the adversary's interest to choose the first setup. Indeed, given that the adversary owns less than half of the network hashrate, their average cost is always smaller than the one they would have got by choosing the second setup. This is largely due to the fact that \(\ES{t_{\text{setup}}}{\mu}\) is quite large for the second setup. Hence, there is no big differences between setting \(\overline{t}=22+\ES{t_{\text{setup}}}{\mu}\) and \(\overline{t}=+\infty\).

\section{Probability of sampling the merging block or fake blocks on the example of Bitcoin}
\label{section:variabledifficulty}
\FC\ can be implemented to work on a blockchain with a variable difficulty, like the Bitcoin one. The velvet fork attack works just the same as in the constant difficulty case. The goal of this section is to show that the computations made in the previous sections are still close to reality when the underlying protocol uses variable difficulty.

Indeed, the previous analysis considers the input space \([0\,;\,1]\) of the distribution function as a variable that ranges over blocks. For instance, \(x=\frac12\) roughly corresponds to the block at position \(\frac{n}{2}\) in the blockchain. However, as described in \cite{\FCCite}, one can adapt \FC\ to work with variable difficulty by considering \([0\,;\,1]\) as a variable that ranges over the difficulty. For instance, \(x=\frac{1}{2}\) roughly corresponds to the block where \(\frac12\) of the total computational power has been mined. This is actually a generalisation of the previous process: under a constant difficulty, half of the total computational power has been spent roughly at block \(\frac{n}{2}\).

Since what we essentially want is to translate a variable that ranges over the block space to a variable that ranges over the difficulty space, we denote \(d\) such a function. Hence, \textbf{the resulting sampling distribution \(s\)} is:
\[\forall x\in[0\,;\,1-\delta],s(x)=\frac{d'(x)}{[d(x)-1]\,\ln(\delta)}.\]
Using data from \cite{BTCDifficulty}, we can plot the graph of the cumulative Bitcoin difficulty \(d\) over the block space, using \([0\,;\,1]\) as an space that ranges over blocks, which is shown on \autoref{figure:graphofd}.

\begin{figure}[ht]
  \centering
  \begin{tikzpicture}
    \begin{axis}[ylabel={Block position},xlabel={Cumulative difficulty}, no marks, width=\figurewidth\textwidth, grid=major]
      \addplot table[x index=0, y index=1] {data/cumulated_difficulty.txt};
    \end{axis}
  \end{tikzpicture}
  \caption{Cumulative difficulty of the Bitcoin protocol.}
  \label{figure:graphofd}
\end{figure}

Using this function, it is possible to compute for each position \(x\) in the chain the difference between the probability that \(x\) is sampled in the variable difficulty case and the one that it is sampled in the constant difficulty case. This is shown on \autoref{figure:difference}.

\begin{figure}[ht]
  \centering
  \begin{tikzpicture}
    \begin{axis}[xlabel={Block position}, no marks,grid=major, width=\figurewidth\textwidth, grid=major, ylabel={Difference between the probabilities}]
      \addplot table[x index=0, y index=1] {data/difference.txt};
    \end{axis}
  \end{tikzpicture}
  \caption{Difference between the probability for a block to be sampled in the variable difficulty case and the one in the constant difficulty case for \(\delta=2^{-10}\) as a function of its position. Since in this case \FC\ samples even more recent blocks, the adversary is even more incentivised to wait, since their blocks will be sampled with lower probability than in the constant difficulty case.}
  \label{figure:difference}
\end{figure}

We can see on this graph that \FC\ samples even more aggressively the most recent blocks when the variable difficulty is taken into account. However, this helps the attacker in the case of a \cs\ attack: as soon as they have waited enough, that is, long enough for the merging block to be at position \(x=\num{0.95}\), then the probability of their blocks being sampled is lower than it used to be in the constant difficulty case. This proves our analysis is still valid when considering the variable difficulty case, which is the way \FC\ is supposed to be implemented.