Profitable Double-Spending Attacks - The first knowledge sharing application in Vietnam

In Section 2 , we define DS attack scenario and sufficient and necessary conditions required for successful DS attacks. Also, we define random variables that are useful in analyzing the attack profits. Section 3 comprises the analytic results of stochastics of the time-finite attack success. In Section 4 , we define the profit function of DS attacks, followed by new theoretical results about the conditions for making them profitable. In Section 5 , an example analysis of DS attack profitability in sub-50% regime against BitcoinCash network is given. Section 6 compares our results with related works. Finally, Section 7 concludes the paper with a summary.

Second, we derive novel mathematical results that are useful for an analysis of the attack success time. Specifically, the probability distribution function and the first moment expectation of the attack success time have been derived. They enable us to estimate the expected profit of a DS attack for a given cut-time. All mathematical results are numerically-calculable. All numerical examples of the theoretical results given in this paper are reproducible in our web-site ( https://codeocean.com/capsule/2308305/tree ).

First, we theoretically show that DS attacks can be profitable not only in the regime of 51% attack but also in the sub-50% regime where the computing power invested by the attacker is smaller than that invested by the target network. Specifically, a sufficient and necessary condition is derived for profitable DS attacks on the minimum value of target transaction. In the sub-50% regime, we also show that profitable DS attacks necessitate setting a finite cut-time.

We study the profitability of DS attacks. The concept of cut-time is introduced. Cut-time is defined to be the duration of time, from the start time to the end time of an attack. For each DS attempt, the attacker needs to pay for the cost to run his mining rig. A rational attacker would not, therefore, continue an attack indefinitely especially when operating within the regime of less than 50% computing power. To reduce the cost, the attacker needs to figure out how his attack success probability rolls out to be as the time progresses. We define that a DS attack is profitable if and only if the expected profit, the difference between revenue and cost (see Equation (33)), is positive. Our contributions are summarized into two folds:

The analysis of attack profitability requires the ability to predict the time an attack will take, since the profit would be a function of time. Studies in [ 12 20 ] provided DS attack profitability analyses, but their time predictions were not accurate. Specifically, to make the time prediction easier, they either added impractical assumptions to the DS attack model defined by Nakamoto [ 1 ] and Rosenfeld [ 6 ] or oversimplified the time prediction formula (see Section 6 for details). Whereas, we follow the definition of DS attack in [ 1 6 ], and therefore we need to develop a new set of mathematical tools for precise analysis of attack profitability that we aim to report in this paper.

Success by making DS attacks is possible but is believed to be difficult for a public blockchain with a large pool of mining network support. By the results in [ 1 6 ], 51% attack has been considered as the requirement for a successful DS attack [ 11 ]. This conclusion however shall be reconsidered given our result in the sequel that there are significant chances of making a good profit from DS attacks regardless of the proportion of computing power. The problem to consider, therefore, is to analyze the profitability of such attacks.

In addition to the recentralization, the advent of rental services which lend the computing resources can be a concern as well [ 10 ]. Rental services such as nicehash.com which provide a brokerage service between the suppliers and the consumers have indeed become available. The rental service can be misused for making DS attacks easier. The presence of such computing resource rental services significantly reduce the cost of making a profit from double spending. This is because renting a required computing power for a few hours is much cheaper than building such a computing network. Indeed, nicehash.com attracts DS attackers to use their service by posting one-hour fees for renting 51% of the total computing power against dozens of blockchain networks on their website Crypto51.App (accessed on 26 November 2020).

In the last few years, unfortunately, blockchain networks have been recentralized [ 7 8 ], which make them vulnerable to DS attacks. To increase the chance of mining blocks, some nodes may form a pool of computing chips. The problem arises when a limited number of pools occupy a major proportion of the computing power in the network. For example, the pie chart (date accessed from BTC.com on November 24, 2020) shown in Figure 1 illustrates the proportion of computing power in the Bitcoin network as of January 2020. In the chart, five pools such as F2Pool, BTC.com , Poolin, and Huobi.pool occupy more than 50% of the total computing power of Bitcoin. In a recentralized network, since most computing resources are concentrated on a small number of pools, it could be not difficult for them to conspire to alter the block content for their own benefits, if aiming to double-spend. Indeed, there have been a number of reports in 2018 and 2019 in which cryptocurrencies such as Verge, BitcoinGold, Ethereum Classic, Feathercoin, and Vertcoin suffered from DS attacks and millions of US dollars have been lost [ 9 ].

A double-spending (DS) attack aims to double-spend a cryptocurrency for the worth of which a corresponding delivery of goods or services has already been completed. The records of payment are written in transactions and shared in a network via the status-quo chain. Thus, to double spend, attackers need to replace the status-quo chain in the network with their new one, after taking the goods or services. For example, under the longest chain consensus, this attack will be possible if an attacker builds a longer chain than the status-quo. Nakamoto [ 1 ] and Rosenfeld [ 6 ] have shown that the higher computing power is employed, the higher probability to make a DS attack successful is. In addition, if an attacker invests more computing power than that invested by a network, a success of DS attack is guaranteed. Such attacks are called the 51% attack.

A consensus mechanism is programmed for decentralized peers in a network to share a common chain. If a full-node succeeds in generating a new block, it has the latest version of the chain. All of the nodes in the network continuously communicate with each other to share the latest chain. A node may run into a situation in which it encounters mutually different chains more than one. In such a case, it utilizes a consensus rule with which it selects a single chain. Satoshi Nakamoto suggested the longest chain consensus for Bitcoin protocol in which the node selects the longest chain among all competing chains [ 1 ]. There are also other consensus rules [ 4 5 ], but a common goal of consensus rules is to select the single chain by which the most computation resources have been consumed based on the belief that it may have been verified by the largest number of miners.

A blockchain is a distributed ledger which has originated from the desire to find a novel alternative to centralized ledgers such as transactions through third parties [ 1 ]. Besides the role as a ledger, blockchains have been applied to many areas, e.g., managing the access authority to shared data in the cloud network [ 2 ] and averting collusion in e-Auction [ 3 ]. In a blockchain network based on the proof-of-work (PoW) mechanism, each miner verifies transactions and tries to put them into a block and mold the block to an existing chain by solving a cryptographic puzzle. This series of processes is called mining. However, the success of mining a block is given to only a single miner who solves the cryptographic puzzle for the first time. The reward of minting a certain amount of coins to the winner motivates more miners to join and remain in the network. As a result, blockchains have been designed so that the validity of transactions is confirmed by a lot of decentralized miners in the network.

By Definition 4, the attack achieving timecan be measured if there exist index pairssuch that. By the mutual exclusivity of, if there exists such a pair, it must be unique. In addition, ifequals, since the state progression timeis non-decreasing asincreases. As the result,can be rewritten as follows,

The sets D j 1 for all j are mutually exclusive as each of them represents the first satisfaction of the block confirmation condition exactly at the j -th state. For example, if ω ∈ D 5 1 then ω ∉ D 6 1 since ω already has achieved the block confirmation at the 5-th state for the first time before reaching the 6-th state. The sets D i , j 2 for all i , j are also mutually exclusive for the same reason. Thus, their intersections D j 1 ∩ D i , j 2 for all i , j are also mutually exclusive.

We next construct a set D i , j 2 ⊂ Ω which does not care about the first j transitions Δ k for k = 1 , ⋯ , j , but only focuses on the interim transitions Δ m for m = j + 1 , ⋯ , i . By the definition, all sequences ω ∈ D i , j 2 must achieve G 1 before the j -th state, which implies that they must hold S j = 2 N B C − j . The rest requirement for each ω ∈ D i , j 2 is that the state changes from starting state S j = 2 N B C − j to state S i = − 1 , while any interim states S k remain non-negative; i.e., S k ≥ 0 for each k = j + 1 , ⋯ , i − 1 .

Formally, we first construct a set D j 1 focusing only on the first j transitions Δ k for k = 1 , ⋯ , j of DS samples ω ∈ Ω with two requirements; one is that they must have N B C number of + 1 ’s and j − N B C number of − 1 ’s; and the other is that the j -th transition Δ j must be + 1 to guarantee that they have never been achieved in any states prior to the state j . The former requirement implies that all ω ∈ D j 1 hold S j = ∑ k = 1 j π Δ i ω = 2 N B C − j . For example, when N B C = 2 and j = 5 , a sequence + 1 , − 1 , − 1 , − 1 , + 1 , ⋯ of state transitions satisfies the first requirement, and also satisfies S j = 2 N B C − j .

To express T D S A as a random variable, we construct event sets D j 1 ⊂ Ω and D i , j 2 ⊂ Ω . The sets D j 1 for j ∈ N B C , N B C + 1 , ⋯ , ∞ consist of DS samples ω which achieves the block confirmation G 1 at state j for the first time. The sets D i , j 2 for i ∈ j , j + 1 , ⋯ , ∞ and j ∈ N B C , N B C + 1 , ⋯ , ∞ consists of ω which achieves the success in the PoW competition G 2 at state i for the first time, given that G 1 has been already achieved at state j . Subsequently, we aim for the samples ω ∈ D j 1 ∩ D i , j 2 to achieve the two conditions in Definition 1 at a state pair i , j for the first time.

For a DS sample ω of DS p A , t c u t ; N B C , we define the DSA time T D S A which measures the least one among the state progression times π T i ω of state indices i at which ω achieves the necessary conditions G 1 and G 2 in Definition 1.

The second processis the continuous-time analog of the random walkforsuch thatwhereis the state progression time defined bywhich increases asincreases. Random walkis a stationary Markov chain starting from. The state transition probabilities [ 22 ] are given byandfor alland. The state transition probabilitiesandare the proportions of computing power occupied by the normal miners and that by the attacker, respectively.

We denote the lengths of the honest chain and the fraudulent chain over time t ∈ 0 , ∞ by two independent PCPs, H t ∈ ℕ 0 with the block generation rate λ H (blocks per second) and A t ∈ ℕ 0 with the block generation rate λ A , respectively. Both processes start at the time origin t = 0 (at which the DS attack is launched) at which the both chains are at the zero states, i.e., H 0 = A 0 = 0 . Each chain independently increases at most by 1 at a time point. An increment of 1 in the counting process occurs when the pertinent network adds a new block to its chain.

We model the conditions in Definition 2 with a stochastic model. We fit the block generation process using the PCP [ 22 ] with a given block generation rate(blocks per second). Including Nakamoto [ 1 ] and Rosenfeld [ 6 ], it has been most conventional to analyze the block generation process of a blockchain using PCP. A rationale why the block generation process is modeled as PCP is given in Bowden et al. [ 23 ], where experiments show the fitness of PCP model to real data samples from a live network.

For a given cut-time t c u t ∈ ℝ + , the success of DS attack is declared if, and only if, there exists a DSA time T D S A ∈ 0 , t c u t at which G 1 and G 2 in Definition 1 have been achieved.

Rational attackers will not wait for his success indefinitely since growing the attacker’s chain incurs the expense per time spent for operating the computing power. The attack thus shall put a limit to the end time to cut loss. We refer to this end time as the cut-time t c u t ∈ ℝ + . A sufficient condition for the success of DS attack can be defined with applying the cut-time t c u t :

The attacker chooses to make the fraudulent chain public if his/her attack was successful. An attack is successful if the fraudulent chain is longer than the honest chain after the moment the block confirmation is satisfied. We define two necessary conditions G 1 , G 2 , for a success of DS attack:

Before shipping goods or providing services to the attacker, the victim will obviously choose to wait for a few more blocks on the honest chain in addition to the block on which the his/her transaction has been entered, i.e., so-called block confirmation. Karame et al. [ 21 ] showed the importance of block confirmation: attackers are able to double-spend against zero block-confirmation even without mining a single block on the fraudulent chain at all. The number of blocks the victim chooses to wait for is referred to as the block confirmation number, which includes the block on which the target transaction is entered.

When the attacker decides to launch a DS attack, he/she makes a target transaction for the payment of goods or services. In the target transaction, the transfer of cryptocurrency ownership from the attacker to a victim is written. We denote t = 0 as the time at which the last block of the honest chain has been generated. At time t = 0, the attacker announces the target transaction to normal group so that normal group starts to put it into the honest chain. At the same time t = 0, the attacker makes a fork of the honest chain which stems from the last block and builds it in secret. We refer to this secret fork as fraudulent chain. In the fraudulent chain, a fraudulent transaction is contained which alters the target transaction in a way that deceives the victim and benefits the attacker.

We extend a DS attack scenario which has been considered by Nakamoto [ 1 ] and Rosenfeld [ 6 ]. Specifically, we add a time-finite attack scenario. There are two groups of miners, the normal group of honest miners and a single attacker. The normal group tends the honest chain.

We define DS attack that we consider throughout this paper. We also define DS attack achieving (DSA) time, which is the least time spent for an occurrence of double-spending. The DSA time is a random variable derived from a random walk of Poisson counting processes (PCP).

A random variable fordoes not need to be defined since it is not useful. The PDFofis just a scaled version offor, which is given in Equation (20), with a scaling factor of. Formally, the PDFequals

From Equation (13), the PDF offollows the PDF ofat a given state index, if at which it holds that, with the probability of. If there does not exist such an index, with the probability of, then. Thus, we can write the PDFofas follows,whereis the Dirac delta function.

From Equation (13), the PDF ofrequires the probabilities of two random events: one is the state progression timein Equation (5); and the other is the event that a given state indexsatisfies. It has been well known thatfollows Erlang distribution [ 22 ] given as

We aim to calculate the probability distribution function (PDF) of the DSA time. Using this, the success probability of DS attack with a given cut-timecan be figured out as the probability that. Also, the expectation of attack success time can be calculated. The expected attack success time will be used in Section 4 to estimate the attack profits.

Theorem 2 shows that for, settingis expected to incur infinite deficit. On the contrary, for, what we have numerically checked out but omitted due to space limitation is the result thatis an increasing function of; i.e., settingis the optimal choice in the superior attack regime. Applyingandinto Equation (36) leads to, and thusturns intowhere a closed-form expression ofis given in Proposition 2. In this case, if; i.e.,, DS attacks are always profitable regardless of. According to nicehash.com, most networks maintainby the economic equilibrium. As the result, in addition to the results in [ 1 ] and [ 6 ] that DS attacks withguarantee probabilistic success, we show that such attacks guarantee economic gain as well.

For any p A ∈ 0 , 0.5 , it always holds that ℙ A S < 1 . In this case, if t c u t → ∞ then C Req . → ∞ from Equation (36); i.e., infinite value C of fraudulent transaction is required for a DS attack DS C , p A , t c u t ; N B C to be profitable. Thus, for a DS attack with p A ∈ 0 , 0.5 to be profitable, a finite cut-time t c u t < ∞ must be set. □

Theorem 1 shows that not only superior attackers with p A ∈ 0.5 , 1 but also inferior attackers with p A ∈ 0 , 0.5 are able to expect profitable DS attacks once a high enough value C greater than C Req . of the target transaction is designed. The condition C Req . in Equation (36) can be pre-computed before carrying out an attack, as it stochastically estimates the future expected cost, for a given position p A ∈ 0 , 1 and a cut-time t c u t of an attacker, and a given set of network environment parameters γ and β .

The key factor in determining the profitability of DS attacks is the valueof the fraudulent transaction. Thus, attackers would be interested in the minimum value required for profitable DS attacks [ 25 ]. Definition 5 implies that a DS attackis profitable if and only if, where the required value of target transactionis

With regards to, if an attack succeeds, the revenue comes from, as it is double-spent, added tofor the number of blocks mined during the time duration, i.e.,. In this case, the cost is the OPEX for the time duration, i.e.,. If the attack fails, the cost is the OPEXfor the time duration, and there is no revenue. Hence, for a DS attack, we defineas follows,

The OPEX(e.g., the rental fee for the computing power) and the block mining rewardtend to increase with respect toand the timeconsumed during the attack. Thus,andare expressed as functions ofand, and they can be any increasing function; e.g., linear, exponential, or logarithm. We defineand, respectively, as follows:for real constants, and, andfor real constants, and. We denote the ratio ofandby

We analyze the profitability of DS attacks and to this end, we define a profit function P of a DS attack DS C , p A , t c u t ; N B C , where C is the value of a fraudulent transaction, in terms of revenue and operating expense (OPEX) of the computing power.

As the results, we obtain ℙ A S ≈ 0.218 , 𝔼 T A S ≈ 5200 seconds, 𝔼 X ≈ 3.98 BTC, and C Req . ≈ 16.22 BTC. One can compute expected running time; i.e., the expected time spent for a single DS attack attempt as ℙ A S 𝔼 T A S + 1 − ℙ A S t c u t , which is around 2 h and 55 min. That is to say, attackers can repeatedly perform n number of attacks every 2 h and 55 min on the average. With the value C of target transaction, by the strong law of large numbers, the multiple attack attempts will return net profit n P A S t c u t ⋅ C − C Re q . as n → ∞ with probability 1.

In case of DS attacks with, the cut-timemust be determined as a finite value for profitable DS attacks by Theorem 2. We setseconds withand. We compute the resources required for profitable DS attacks against BitcoinCash when. Results are obtainable from the values in Table 1 and Table 2 by multiplying the scaling parametersandand by substitutingand

Note that it holds β > γ . From Equation (37), this relationship makes DS attack DS C , p A , t c u t ; N B C with p A > 0.5 and t c u t = ∞ always profitable regardless of the value C of target transaction.

The parameteris obtainable from nicehash.com. BitcoinCash uses the SHA-256 cryptographic puzzle for which the unit of computation is hash. As of 26th Feb. 2020, the rental fee for 1-peta (P) hashes per second for a day was around 0.017 BTC, which was aroundBTC per second. In other words, the rental fee was approximatelyBTC per the computing of a hash. Referring to BTC.com, the network’s computing speed is 3.57-exa (E) hashes per second; i.e.,hashes are needed to generate one block on the average. As the result, the parameteris obtained as

To this end, we first recall the parameters involved in block mining reward R and the OPEX X . The parameters used in Equation (29) and Equation (30) are assumed to x 1 = x 2 , x 3 = x 4 , r 1 = r 2 , and r 3 = r 4 which lead to linear functions X λ A , t and R λ A , t with respect to λ A and t . There are three more parameters: γ , β , and λ H − 1 . From Equation (29) and Equation (30), the parameter γ is the expected cost spent per generating a block; and the parameter β is the reward per generating a block. Parameter λ H − 1 is the average block generation time of the honest chain. All the parameters are different for each blockchain network.

Mục lục bài viết

6. Related Works

c
u
t

=
∞

. Both of them applied PCPs to model the growth of chains

and

. On one hand, the main difference between them was in probability calculations of the block confirmation process in Definition 1. Rosenfeld applied the PCPs to both

and

, whereas Nakamoto assumed the time spent for

≥

B
C

deterministic to simplify the calculation. On the other hand, they both used the gambler’s ruin approach to obtain the asymptotical behavior of

S
i

i
→
∞

by manipulating the recurrence relationship between two adjacent states. Namely, their results are based on an assumption that an indefinite number of attack chances are given [

By Nakamoto [ 1 ] and Rosenfeld [ 6 ], the probabilities have been studied that a DS attack will ever succeed when there is no time limit, i.e., the cut-time is set to. Both of them applied PCPs to model the growth of chainsand. On one hand, the main difference between them was in probability calculations of the block confirmation process in Definition 1. Rosenfeld applied the PCPs to bothand, whereas Nakamoto assumed the time spent fordeterministic to simplify the calculation. On the other hand, they both used the gambler’s ruin approach to obtain the asymptotical behavior ofasby manipulating the recurrence relationship between two adjacent states. Namely, their results are based on an assumption that an indefinite number of attack chances are given [ 12 ].

c
u
t

which generalizes analytical framework to the more interesting finite attack time and inferior attacker regime. By setting

c
u
t

infinite, the same result

ℙ

D
S
A

was obtained in [

c
u
t

, our results shall be useful when attack chances are limited due to limited amount of resources such as time and cost. In addition, we show in Theorem 2 that DS attacks with

p
A

<
0.5

must set a finite

c
u
t

in order to expect a non-negative profit. It shall be noted that there has been no intermediate result like

D
S
A
,
i

in Lemma 1. We use Lemma 1 to derive the novel results.

On the contrary, we introduce the cut-timewhich generalizes analytical framework to the more interesting finite attack time and inferior attacker regime. By settinginfinite, the same resultwas obtained in [ 6 ] as well. By setting a finite, our results shall be useful when attack chances are limited due to limited amount of resources such as time and cost. In addition, we show in Theorem 2 that DS attacks withmust set a finitein order to expect a non-negative profit. It shall be noted that there has been no intermediate result likein Lemma 1. We use Lemma 1 to derive the novel results.

Rosenfeld [ 6 ] and Bissias et al. [ 13 ] have analyzed the profitability of DS attacks. However, they put additional assumptions on the attack scenario to simplify the calculation of the attack time. Specifically, Rosenfeld assumed the attack time to be a constant. Bissias et al. assumed that the attack stops if either the normal peers or the attacker achieves the block confirmation first. On the contrary, in our model, an attack can be continued for a random attack time as long as it brings profit, even if the normal peers achieve the block confirmation before the attacker does.

p
A

<
0.5

, which is theoretically proven in this paper in Theorem 2. They also calculated the profit of DS attacks with a finite time-limit (see Section IV-C in [

In Zaghloul et al. [ 14 ], the profit of DS attack has been analyzed. Interestingly, they have discussed the need of cut-time for DS attacks with, which is theoretically proven in this paper in Theorem 2. They also calculated the profit of DS attacks with a finite time-limit (see Section IV-C in [ 14 ]), but their calculation was not as precise as ours in three points:

ℙ

A
S

c
u
t

in Equation (23) was never considered, which requires the distribution of the DS achieving time, i.e.,

TDSA

given in Proposition 1. Instead, their calculation used

ℙ

D
S
A

referring to the result in Rosenfeld [

ℙ

D
S
A

in [

First, the probability of attack success within a finite time-limit, i.e.,in Equation (23) was never considered, which requires the distribution of the DS achieving time, i.e.,given in Proposition 1. Instead, their calculation usedreferring to the result in Rosenfeld [ 6 ]. This contradicts their time-limited attack scenario, sincein [ 6 ] was resulted from the assumption of infinite time-limit.

Second, they approximated costs and revenues of DS attack spent within a time-limit. Estimation of the costs and revenues requires estimations of the numbers of blocks respectively mined by honest nodes and attackers within a time-limit, but those were assumed to be constant. This was due to the absence of the time analysis we provide in Proposition 1.

Third, they assumed the average block generation rates

λ
H

λ
A

respectively by honest miners and by attackers are always the same. Since, the proportions

p
H

p
A

of computing power occupied by the two groups can be quite different in general, such a result is not very useful. We agree to their assumption that most blockchains control the difficulty of block mining puzzle to keep the average speed of block generation constant, and thus

λ
H

can be considered as a constant. However,

λ
A

should be left as a varying quantity by

p
A

. The fact is that the computing power invested by the attacker cannot be monitored by the honest network and thus it cannot be reflected in the difficulty control routine.

p
A

>
0.5

. Under the cases, a condition on the value of the target transaction that makes DS attacks not profitable has been given based on the simulations. We give theoretical and numerically-calculable results for any

p
A

∈

0
,
1

, which do not require massive simulations.

Budish [ 15 ] conducted simulations on the profitability of DS attacks only in the cases of. Under the cases, a condition on the value of the target transaction that makes DS attacks not profitable has been given based on the simulations. We give theoretical and numerically-calculable results for any, which do not require massive simulations.

Gervais et al. [ 16 ] and Sompolinsky et al. [ 12 ] have used a Markov decision process (MDP) to analyze profits from DS attacks. These works differ from our contributions in the following regards:

B
C

blocks, while under their condition it was fraudulent for the chain to do so (see Section 3 of [

First, they did not follow the DS attacks scenario considered by Nakamoto [ 1 ] and Rosenfeld [ 6 ]. Instead, the scenario in [ 12 ] was a special case of the pre-mining strategy which was introduced in [ 17 18 ]. We show that the success of DS attack under this scenario is even more difficult to occur than the success of the DS attack under the scenario of Nakamoto and Rosenfeld (see Appendix D for details). Also, the attack scenario in [ 16 ] went even further by modifying the condition for block confirmation in Definition 1. Specifically, under our definition, it is required for the honest chain to have addedblocks, while under their condition it was fraudulent for the chain to do so (see Section 3 of [ 16 ]). Thus, it was not ensured that the potential victim has shipped the goods or service, and an attack success did not guarantee for the attacker to obtain the benefit of attacking.

Second, one important new advance in this paper is the derivation of the time analysis

A
S

given in Proposition 1. When one uses the MDP framework, one can obtain similar information such as the estimations for the attack success time

A
S

, the future profit

that an attacker will earn in the end, and the minimum value of target transaction

Req
.

. However, using MDP to make such estimations would have required extensive Monte Carlo simulations. Using our mathematical results, such estimations can be obtained without Monte Carlo simulations.

A
S

in Proposition 1 can be used at any intermediate Markov state to estimate the future profits. Specifically, the conditional expectation of the time left for an attack success

A
S

given

A
S

>
τ

can be calculated using

A
S

, where

is the observable time elapsed for reaching the current state. Once the time left is estimated, the estimation of future profits can be updated by substituting it into Equation (33). That is to say, at each state, the estimation of profits can be updated and used as the rewards resulting from the continue action.

In addition, we believe that our mathematical results can be utilized in the MDP frameworks to improve the reliability of analyses. Conventionally, a rational user of an MDP will make a decision at every state whether to stop or to continue the process by comparing the rewards that will be incurred in the future by his/her decision. The rewards for stop actions are clear because such actions are either an attack success or a give-up. The reward for the continue action is complex because it needs to consider all the actions in all future possible states as well. In [ 12 16 ], the rewards for the continue action were over-simplified as they were evaluated only for the very next state and did not include the estimation of the profits in further future actions. To improve the reliability, the PDFin Proposition 1 can be used at any intermediate Markov state to estimate the future profits. Specifically, the conditional expectation of the time left for an attack successgivencan be calculated using, whereis the observable time elapsed for reaching the current state. Once the time left is estimated, the estimation of future profits can be updated by substituting it into Equation (33). That is to say, at each state, the estimation of profits can be updated and used as the rewards resulting from the continue action.

B
C

=
0

. To sum up, the attack success time in neither analysis included the time spent for achieving the first condition: the block confirmation should be realized.

Goffard [ 19 ] and Karame et al. [ 20 ] have derived the PDFs of attack success time, but none of their DS attack scenarios matched with ours in Definition 1. In [ 19 ], Goffard derived the PDF of catch-up time spent for the fraudulent chain to catch up with the honest chain given that the length of honest chain is initially ahead by several blocks. The author used counting processes such as order statistic point process and renewal process which are more general than PCP, but there was no analytic result similar to what is given in Proposition 1. In [ 20 ], Karame et al. derived the PDF of the first attack success time under a fast-payment model which fixed. To sum up, the attack success time in neither analysis included the time spent for achieving the first condition: the block confirmation should be realized.