double-spend-z-stopping-rule.md

Required possession duration of malicious hashpower for successful double-spend attack with a $z$ stopping rule.

An attacker possesses $q$ share of Monero's hashpower for a duration of $d$ blocks. Honest miners possess $p=1-q$ hashpower share.

Let $z$ be the number of blocks that the potential victim waits for "full confirmation" of a transaction. When a transaction is mined in a block on the honest chain, that means that the transaction has one confirmation, i.e. $z=1$. When another block is mined on the honest chain, $z=2$.

The attacker attempts as many double-spend attacks as possible during the specified duration. Let us label this series of attacks as the "meta attack". The objective of the meta attack is for one of the double-spend attacks to succeed. Once the attacker has mined its initial block, it mines on its attacking sub-chain until the honest sub-chain has added $z$ more blocks. Then the attacker stops mining and broadcasts the attacking sub-chain if the attack is successful or starts mining a new attacking chain if unsuccessful. This attack with the $z$ stopping rule is not the same as the classic double-spend attack described in the bitcoin white paper, which assumed the attacker would continue mining the initial attacking sub-chain for an indefinite length of time.

The simple $z$ stopping rule does not necessarily maximize the probability of one of the attacks being successful. To evaluate the best strategy, the future probability of being successful while continuing to mine on the initial attacking sub-chain would have to be compared with the probability of re-starting the chain at every state change, i.e. each time the attacker or honest miners added a new block to their sub-chains. This kind of analysis would likely require more complicated techniques like Stochastic Dynamic Programming. Below, the simple $z$ stopping rule is analyzed.

Meta attack algorithm

(1) Attempt to secretly mine a block containing a self-send transaction.

(2a) If the attacker successfully mines a block before a new block is mined by honest miners, send a transaction that is incompatible with the self-send transaction to the potential victim and go to step (3). This transaction will go into the transaction pool of honest miners, waiting to be mined into the next block.

(2b) If the honest miners mine a block before the attacker, then go to step (1).

(3) Attempt to mine $z$ additional blocks in the attacking sub-chain before the honest miners mine $z$ blocks. (The total length of the attacking sub-chain will be $z+1$ blocks because the first block was mined in step (2a).

(4a) If the attempt in step (3) is successful, broadcast the attacking chain when the length of the honest sub-chain reaches $z$ and the victim considers the transaction to be fully confirmed. The attack is a success.

(4b) If the attempt in step (3) is unsuccessful, request a refund from the potential victim (e.g. request to withdraw the deposited coins from a cryptocurrency exchange) and go back to step (1).

Attack duration analysis

Let $w$ be the number of times that the attacker can run the (1)-(4) algorithm while possessing the $q$ share of hashpower for a duration of $d$ blocks. $w$ is determined by $z$ and the waiting time until the attacker produces a new first block in the attacking chain in step (2a). The waiting time is the number of times that the attacker has to re-start the algorithm when it fails at step (2b) because the honest miners have mined a block before the attacker.

Let $v$ be the random number of blocks that the honest miners produce while the attacker is trying to mine its first attacking block. $v$ has a negative binomial distribution where the number of successes is 1 and the probability of success is $q$ (Proposition 5.1 of Grunspan & Perez-Marco 2018). We will make the simplifying assumption that the attacker always has to wait for the mean of $v$ to produce its first attacking block. The mean of $v$ is $(1-q)/q$.

$w$ is the number of attempts that the attacker can make while possessing $q$ hashpower share for a $d$ duration of blocks. The attacker can only attack if he or she possesses the hashpower share for at least a full "cycle", so we use the floor function, $\lfloor x\rfloor$. $w$ is $d$ divided by the sum of the full confirmation waiting time $z$ and the expected waiting time until the attacker produces the first attacking block, $(1-q)/q$:

$$w=\lfloor d/(z+(1-q)/q)\rfloor$$

Again, use Proposition 5.1 of Grunspan & Perez-Marco (2018), but this time we will compute the probability that the attacking sub-chain is longer than the honest sub-chain when the length of the honest sub-chain reaches $z$. Let $x$ be the random number of blocks added to the attacking sub-chain in step (3). Therefore, the total length of the attacking sub-chain is $x+1$ because one block was mined in step (2a). Let $Pr(x\geq z)$ be the probability that step (4a) is achieved by the attacker, i.e. the length of the attacking sub-chain is longer than the length of the honest sub-chain when the honest sub-chain reaches $z$ blocks in length. We will start with the cumulative distribution function (CDF) of $x$, which is distributed as a negative binomial distribution:

$$Pr(x\leq k)=I_{p}(z,k+1)$$

where $I_{y}(a,b)$ is the regularized incomplete beta function.

Let $k+1=z$, so $k=z-1$. Therefore,

$$Pr(x\leq z-1)=I_{p}(z,z)$$

Get the complement of the probability (i.e. get the upper tail of the CDF):

$$Pr(x>z-1)=1-I_{p}(z,z)$$

$x$ and $z$ are discrete. Therefore, $x>z-1\Longleftrightarrow x\geq z$. So:

$$Pr(x\geq z)=1-I_{p}(z,z)$$

Which was the desired probability expression. We can simplify further by using an identity of the regularized incomplete beta function: $I_{1-y}(a,b)=1-I_{y}(b,a)$ and the fact that $q=1-p$:

$$Pr(x\geq z)=I_{q}(z,z)$$

It is interesting that the $Pr(x\geq z)$ success probability of a double spend with this $z$ block stopping rule is exactly half as large as the success probability of a single attack where the attacker continues adding blocks to the initial attacking sub-chain for an infinite amount of time, which is $2I_{q}(z,z)$. The indefinite-time attack is the classic form of the double spend attack described in the bitcoin white paper. The attacker's cost of an indefinite-time attack is potentially infinitely larger than the cost of the attack with the $z$ block stopping rule. (The proof of Theorem 6.1 in Grunspan & Perez-Marco (2018) shows that $2I_{q}(z,z)$ is the attack success probability for the indefinite-time attack.)

We want to know the probability that at least one of the double-spend attacks attempted during the meta attack is successful. We have $w$ attempts. Since the attack success probability are statistically independent and identical on each attempt, we can use $w$ as an exponent. The probability of attack failure is $1-I_{q}(z,z)$. Compute the probability that all of the attacks fail: $\left(1-I_{q}(z,z)\right)^{w}$. The probability that at least one double-spend attack succeeds during the meta attack is:

$$Pr_{meta}=1-\left(1-I_{q}(z,z)\right)^{w}$$

We want to find the minimum duration $d$ of the meta attack that would allow an attacker to achieve a specified probability of being successful in their meta attack, for several values of the attacker's hashpower share $q$ and the number of blocks for a transaction to be considered "fully confirmed", $z$. We must solve for $d$. Recall that the expression for $w$ contains the floor function. We will ignore that for the moment and use $w^{*}=d^{*}/(z+(1-q)/q)$. Now we need to find the minimum $d$ such that $Pr_{meta}\geq1-\left(1-I_{q}(z,z)\right)^{d^{*}/(z+(1-q)/q)}$. Solving for $d^{*}$:

$$(z+(1-q)/q)\cdot\log\left(1-Pr_{meta}\right)/\log\left(1-I_{q}(z,z)\right)\leq d^{*}$$

To find the minimum $d$ that satisfies this inequality, we need to "round up" $d^{*}$ to the next multiple of $z+(1-q)/q$, then round up again to the next integer (recall the definition of $w$). We use the ceiling function, $\lceil x\rceil$. The $d$ that satisfies the requirement is $d=\lceil\lceil d^{*}/(z+(1-q)/q)\rceil\cdot(z+(1-q)/q)\rceil$. Simplifying terms, we get:

$$d=\left\lceil \left\lceil \dfrac{\log\left(1-Pr_{meta}\right)}{\log\left(1-I_{q}(z,z)\right)}\right\rceil \cdot(z+(1-q)/q)\right\rceil $$

Table: Duration of meta attack to achieve attack success probability of 50 percent

Below is a table of the duration of a meta attack that would allow an attacker to achieve a 50 percent probability of being successful in their meta attack. The rows are different values for $z$, the number of blocks a potential victim would wait until considering a transaction "fully confirmed". The columns are different values for $q$, the share of hashpower the attacker possesses. The cells are the number of days that the attacker would have to possess the hashpower to achieve at least 50 percent probability (i.e. $Pr_{meta}=0.5$) of at least one successful double spend attack. For example, if a potential victim considered a transaction fully confirmed after 5 blocks, an attacker possessing 10 percent of hashpower for 15 days would have 50 percent probability of at least one successful execution of a double spend attack.

	0.05	0.1	0.2	0.3	0.4	0.45
1	0.389	0.097	0.028	0.010	0.007	0.007
2	2.800	0.382	0.058	0.019	0.010	0.010
3	18.303	1.350	0.117	0.031	0.013	0.013
4	114.393	4.586	0.233	0.053	0.024	0.015
5	695.467	15.128	0.450	0.072	0.028	0.018
6	4148.646	48.833	0.833	0.104	0.032	0.021
7	24406.850	155.156	1.512	0.143	0.036	0.024
8	> 100 yrs	486.719	2.733	0.201	0.040	0.026
9	> 100 yrs	1511.525	4.857	0.268	0.058	0.029
10	> 100 yrs	4654.446	8.536	0.360	0.064	0.032
11	> 100 yrs	14229.972	14.896	0.482	0.069	0.035
12	> 100 yrs	> 100 yrs	25.778	0.637	0.075	0.038
13	> 100 yrs	> 100 yrs	44.342	0.853	0.101	0.040
14	> 100 yrs	> 100 yrs	75.825	1.112	0.108	0.043
15	> 100 yrs	> 100 yrs	128.989	1.444	0.115	0.046
16	> 100 yrs	> 100 yrs	218.417	1.860	0.146	0.072
17	> 100 yrs	> 100 yrs	368.317	2.390	0.154	0.076
18	> 100 yrs	> 100 yrs	618.781	3.050	0.162	0.081
19	> 100 yrs	> 100 yrs	1036.086	3.911	0.200	0.085
20	> 100 yrs	> 100 yrs	1729.467	4.964	0.210	0.089
21	> 100 yrs	> 100 yrs	2878.854	6.287	0.219	0.093
22	> 100 yrs	> 100 yrs	4779.739	7.976	0.261	0.097
23	> 100 yrs	> 100 yrs	7916.962	10.064	0.272	0.101
24	> 100 yrs	> 100 yrs	13084.633	12.692	0.319	0.106
25	> 100 yrs	> 100 yrs	21581.438	15.944	0.332	0.110
26	> 100 yrs	> 100 yrs	35528.583	19.992	0.382	0.114
27	> 100 yrs	> 100 yrs	> 100 yrs	25.056	0.396	0.118
28	> 100 yrs	> 100 yrs	> 100 yrs	31.344	0.451	0.122
29	> 100 yrs	> 100 yrs	> 100 yrs	39.124	0.467	0.126
30	> 100 yrs	> 100 yrs	> 100 yrs	48.769	0.525	0.131

R code to reproduce the table above is:

# install.packages("zipfR")
# install.packages("knitr")

Pr_meta <- 0.5
n.blocks <- 30
hashpower.share <- c(0.05, 0.10, 0.20, 0.30, 0.40, 0.45)

z <- 1:n.blocks
results <- matrix(0, nrow = n.blocks, ncol = length(hashpower.share))

for (i in seq_along(hashpower.share)) {
  q <- hashpower.share[i]
  Iq <- zipfR::Rbeta(x = q, a = z, b = z)
  results[, i] <-  ceiling(ceiling(log(1 - Pr_meta)/(log(1-Iq))) * (z + (1-q)/q))
}

results <- results / (30*24)  # Convert to days
rownames(results) <- as.character(blocks)

results[ (! is.finite(results)) | results >= 365.25 * 100] <- NA

options(knitr.kable.NA = paste0("> 100 yrs"))

knitr::kable(results, format = "pipe", row.names = TRUE,
  col.names = hashpower.share, digits = 3)

References

Grunspan, C., & Perez-Marco, R. (2018). "Double spend races." Int. J. Theor. Appl. Finance, 21(8).