Cyril Grunspan

Ricardo P Érez-Marco

BLOCK WITHHOLDING RESILIENCE

Keywords: 2010 Mathematics Subject Classification. 68M01, 60G40, 91A60 Bitcoin, blockchain, proof-of-work, selfish mining, martingale

It has been known for some time that the Nakamoto consensus as implemented in the Bitcoin protocol is not totally aligned with the individual interests of the participants. More precisely, it has been shown that block withholding mining strategies can exploit the difficulty adjustment algorithm of the protocol and obtain an unfair advantage. However, we show that a modification of the difficulty adjustment formula taking into account orphan blocks makes honest mining the only optimal strategy. Surprinsingly, this is still true when orphan blocks are rewarded with an amount smaller to the official block reward. This gives an incentive to signal orphan blocks. The results are independent of the connectivity of the attacker.

Introduction

Satoshi Nakamoto's foundational article [START_REF] Nakamoto | Bitcoin: a peer-to-peer electronic cash system[END_REF] describes Bitcoin protocol. Bitcoin is an electronic currency and bitcoin transactions operate through a computer network. This network is permissionless: anyone can freely enter or leave the network. Moreover, there is no central authority acting as a referee. The minting algorithm is implemented in the protocol. Transactions are packed in chronologically ordered blocks that form an unforgeable public ledger: the blockchain. Certain nodes of the network, called miners, play a special role. They secure the blockchain through intensive computation by a "proof of work", a technique originally invented to fight email spam and denial of service attacks. A miner creates a new block of transactions to add to the blockchain by solving a cryptographic puzzle by brute force iterating a simple algorithm. For this computational work he is rewarded by a coinbase reward of newly minted bitcoins. This mechanism generates the Bitcoin monetary mass.

How Bitcoin works

2.1. Nodes. The Bitcoin network is a peer-to-peer network made up of thousands of "nodes" connected around the world, forming an irreducible and highly connected graph. All nodes play or can play the same role and perform the same operations.

The nodes exchange information that consists of more or less complicated transactions and blocks of validated transactions. The blockchain is a database that defines the ledger of all confirmed transactions. The mempool is the set of all transactions in waiting for a confirmation in a block. Each time a node receives a transaction, it examines whether the transaction is legal, in the proper format, and checks that it does not conflict with other transactions already in its mempool. When this is the case, the transaction is added to its mempool and broadcasted to neighboring nodes.

2.2. Mining. Some of the nodes of the network perform a mining activity. A miner is a particular node that seeks to build up a new block. By definition, a B block is a set of data whose maximum size is about 2 Mega Bytes. It is formed by a reference to an old block, a set of transactions drawn from the miner's mempool, a creation date, the mining difficulty ∆ and a parameter called "nonce". The goal is to obtain a block B such the hash of its header is below some threshold:

(1) h(B) < 1 ∆ where h is the SHA 256•SHA 256 function where SHA 256 is the cryptographical hash function, and ∆ is called the difficulty. If successful, the miner receives a reward as a coinbase transaction. The reward decreases by half every four years (the "halving"). The difficulty parameter ∆ is adjusted regularly. The current difficulty adjustment algorithm allows blockwithholding attacks, i.e. the miner can obtain an advantage by withholding blocks and releasing them at the appropiate timing. This type of attack exploits the difficulty adjustment algorithm that evaluates the total hashrate in an erroneous way, only considering validated blocks and forgetting about orphan blocks (that fulfill the proof of work but are displaced from the blockchain by other competing blocks). The purpose of this article is to show that this problem can be corrected using an improved difficulty adjustment mechanism that evaluates properly the total hashrate by taking into account orphan blocks.

Mining strategies.

Why should miners immediately release a newly discovered block? This is implicitely assumed in the Bitcoin founding article, but in fact it is not properly incentivized. Could a miner validating a block try to widen the gap even further by secretly mining on top of that block? Could he devise a block withholding strategy giving him an advantage compared to the honest strategy? Definition 2.1. The official blockchain is the chain of blocks with the most of proofof-work.

In other words, the official blockchain is the chain of blocks which maximizes the quantity ∆ i where ∆ i is the difficulty parameter included in the i-th block. Most ot the time it is the longest blockchain because the difficulty parameter is locally constant (updated every 2016 block period).

Definition 2.2. The honest strategy consists in always mining on top of the last block of the official blockchain.

2.4. Performance of a mining strategy. A mining strategy is repetitive in the sense that the miner will return, to its starting point after a finite time. The miner has performed a strategy cycle during this period. We call such a strategy with finite expected return time, a finite strategy (also integrable strategy as been used).

We note τ the random duration of this cycle and G the miner's gain accumulated during this cycle. We use as a unit of wealth the average value contained in a block (i.e., average value of transaction fees contained in a block plus value of a coinbase). Mathematically speaking τ is a stopping time. We consider only cycles with expected finite duration: E[τ ] < ∞. If a miner repeats his strategy n times, he will gain per unit time

G 1 + . . . + G n τ 1 + . . . + τ n = G 1 +...+Gn n τ 1 +...+τn n which converges to E[G] E[τ ] (the assumption E[τ ] < ∞ implies that E[G] < ∞).
Similarly, the cost per unit time of the miner over the long term is

E[C] E[τ ]
where C is the cost per cycle of his mining activity and the miner's net income per unit time is therefore

E[G] E[τ ] -E[C] E[τ ]
. However, the cost of his mining activity per unit of time does not depend on whether or not the miner keeps blocks secret (it depends on the cost of electricity, the price of his equipment, the salaries paid to employees for a mining company, etc). Whether he makes blocks public or not has no impact on his cost per unit of time. Therefore, comparing two mining strategies with the same average operating cost per unit of time, a rational miner will choose the strategy that maximizes his income per unit of time in the long run Γ

= E[G] E[τ ] . Definition 2.

The proftability ratio of an integrable mining activity is

Γ = E[G] E[τ ]
where G is the gain per cycle and τ the duration of a cycle.

Mining model and notations

We use the widely adopted model and notations that Satoshi Nakamoto proposed in his Bitcoin founding article (see [START_REF] Nakamoto | Bitcoin: a peer-to-peer electronic cash system[END_REF] and [START_REF] Grunspan | Double spend races[END_REF]). We consider a miner who is a possible attacker (or a group of miners) against the rest of the network consisting of honest miners all following the rules of the Bitcoin protocol. Since the hash function used in Bitcoin mining operations is pseudorandom, the time T (resp. T ) taken by the honest miners (resp. attacker) to discover a block is a random variable following an exponential law (see [START_REF] Grunspan | Double spend races[END_REF]). We denote by α (resp. α ) the parameter of the exponential law. We have

E[T] = 1 α (resp. E[T ] = 1 α ).
In other words, α (resp. α ) is the average speed taken by honest miners (resp. attacker) to discover a block. Definition 3.1. For t ∈ R + , we denote N (t) (resp. N (t)) the number of blocks mined by honest miners (resp. attacker) between 0 and t.

The counting processes N (t) and N (t) are Poisson processes of parameters α and α (see [START_REF] Grunspan | Double spend races[END_REF]). Let h (resp. h ) be the number of hashes per second computed by the honest miners (resp. attacker). This is the absolute hash power of the honest miners (resp. attacker). The mining difficulty ∆ represents the number of hashes that one has to compute on average before finding a proof of work. It is related to the average time taken to discover a block. We have h

• E[T] = h • E[T ] = ∆. It follows that α = h ∆ (2) α = h ∆ (3)
Since the two variables T and T are independent, we also have

P[T < T] = α α+α = h h+h .
Therefore, the probability that the attacker discovers a block before the other miners is equal to its relative hash power. We make the assumption that this remains constant over time.

Definition 3.2. We denote by p (resp. q) be the relative hashing power of the honest miners (resp. attacker).

In other words, q = α α+α and p = 1 -q. Note that the network (the honest miners and the attacker) finds a block in inf(T, T ). This is again an exponential law of parameter α + α because T and T are independent [START_REF] Ross | Introduction to Probability Models[END_REF]. Therefore, E[inf(T, T )] =

1 α+α and α = p E[inf(T,T )] and α = q E[inf(T,T )] .
3.1. First stability theorem. In this section only, we consider a simplified Bitcoin network without difficulty adjustment (that is, the difficulty parameter is assumed to be constant). Let τ 0 = E[inf(T, T )] be the average time taken by the network to discover a block. Note that a priori here, τ 0 = 10 minutes because there is no particular difficulty adjustment. It follows easily from the previous section that N (resp. N ) is a Poisson process with parameter α = p τ 0 (resp. α = q τ 0 ) [START_REF] Ross | Introduction to Probability Models[END_REF]. Theorem 3.3. If Γ is the profitability ratio for a finite mining strategy, we have Γ q τ 0 .

Proof. Since the mining strategy is finite we have by definition E[τ ] < ∞ where τ the stopping time of the duration a cycle. Let G be the number of official blocks mined by the attacker between 0 and τ . We have G N (τ ). Let n ≥ 1 and the truncated stopping time τ n = inf(τ, n). The random variable N (t) -α t is a martingale. Therefore, by Doob's Stopping Time Theorem, we have

E[N (τ n ) - α τ n ] = 0, and E[N (τ n )] = α E[τ n ]
. By making n → +∞ and using the Monotone Convergence Theorem, we obtain

E[N (τ )] = α E[τ ], which finally gives Γ = E[G] E[τ ] α = q τ 0 . Corollary 3.4.
Without difficulty adjustment, the optimal strategy is the honest one.

Proof. If the attacker mines honestly, he earns on average q during a lapse τ 0 . Thus, the return on the honest strategy is q τ 0 which is also the maximum return in the previous Theorem. This result was already proved in [START_REF] Grunspan | On profitability of Selfish Mining[END_REF].

3.2.

Effect of the difficulty adjustment on the profit per unit time. The difficulty adjustment ensures a lower bound for expected interblock time that allows the network to synchronize, and also an upper bound for transaction confirmation waiting time (i.e.inclusion in the blockchain). The goal of a regular difficulty adjustment is to have, on average, a lapse of 10 minutes to validate a block. More precisely, the difficulty parameter ∆ is adjusted every n 0 blocks with n 0 = 2016. At each difficulty adjustment, the network calculates the time T taken to validate the last series of n 0 blocks. This work is done thanks to the timestamps of the blocks in the blockchain. If this time T is greater than 14 days = n 0 × 10 minutes, the difficulty decreases. Otherwise, it increases. The new difficulty parameter ∆ is given by: (4) ∆ = ∆ × n 0 × 10 T where T is calculated here in minutes. When the mining difficulty ∆ is changed, so are the parameters α and α of the Poisson processes N and N . The counting processes N and N are piecewise Poisson processes whose parameters α and α change each time the official blockchain progresses by n 0 blocks. If ∆ varies and becomes equal to ∆ λ , then α and α are each multiplied by λ according to the previous formulas (2) and (3).

We consider the previous situation where a miner repeats some block withholding strategy (deviant or not) and the rest of the network is composed by honest miners. We assume that the total hash power remains constant. The first observation is that this miner can have a significant impact on the first difficulty adjustment if he conceals his blocks. For example, after a period of mining n 0 official blocks, if a miner adopts a block withholding strategy, this slows down the natural progression of the official blockchain. The network will generally take longer than the expected two weeks to mine 2016 blocks. This triggers a downward difficulty adjustment, making the mining activity more profitable afterwards. If in the long run the miner continues with the same strategy, the difficulty parameter will stabilize assuming that the total hashrate remains constant. Then, in such a period of constant difficulty, since the interblock time is 10 minutes, the duration τ of an attack cycle is proportional on average to the height progression H of the official blockchain during that cycle, i.e.

E[τ ] = E[H]

× 10 where H. Although it is intuitively clear, this is proved by direct application of Wald's Theorem.

Thus we have the following Proposition: Proposition 3.5. Consider a finite mining strategy, i.e. E[τ ] < ∞. Let G be the number of blocks per cycle mined by the miner added to the official blockchain and H denote the height progression of the official blockchain over a cycle. Then the profitability ratio of the strategy is

Γ = E[G] E[H] .
Note that the honest strategy corresponds to a simple cycle that ends each time that a block is discovered. In this case, we have E[G] = q and E[H] = 1 where q is the relative hash power of the miner. Thus, Γ = q for the honest strategy and a rational miner has an incentive to adopt a deviant strategy if and only if Γ > q.

Block withholding attacks

It has been known since late 2013 that the rules of the Bitcoin protocol are not in sync with the interests of miners (see [START_REF] Grunspan | The Mathematics of Bitcoin[END_REF] for an overview). In particular, when the miner has enough computing power, the miner may have an interest in adopting a deviant strategy. We present below a simple example of deviant strategy, the "1+2 strategy", showing that the honest strategy is not the most profitable one.

The "1+2 strategy".

Suppose that the network is composed of an attacker and a set of honest miners. The attack is defined as follows. The attacker starts mining. If the honest miners are first to find a block then the attack ends and the attacker returns to mine on top of the last discovered block. If, on the other hand, the attacker manages to mine a block before the honest miners, then he keeps it secret and continues to mine on top of that block, seeking to widen the gap with the official blockchain. Then, regardless of the identity of the miners who validated the following blocks, as soon as two blocks have been discovered, the attack ends. If he is successful, i.e. if it has mined more blocks than the honest miners, the attacker reveals his secret blocks and imposes its "fork" (his block sequence) on the official blockchain, which then goes through a small reorganization. If this is not the case, it is useless for the attacker to broadcast anything since none of his blocks will be included in the official blockchain.

If we denote by A a block discovered by the attacker and by B a block discovered by the honest miners, the outcome of the attack can be encoded as a word formed with the letters A and B. The universe Ω of all possible cycles is :

Ω = {B, AAA, AAB, ABA, ABB}
The name "1+2 strategy" reflects the fact that the attacker is waiting to discover a block (hence the "1"). Then, when he does, he waits for two blocks to be discovered, hence the "+2".

Example 4.1. We describe the cycle ABA. The attacker discovers a block, then the honest miners mine one too and finally the attacker mines the next one. In this case, tha attack has succeeded and the attacker propagates his two secret blocks (the two A's). The official blockchain goes through a small reorganization: its now penultimate block (block "B") is replaced (it becomes an orphan block) and the height of the blockchain has increased by one block. The attacker earns the reward contained from his two blocks.

We can now compute the expected profitability of the "1+2" strategy. As before, we denote by q the relative hash power of the attacker and p = 1 -q the one of the honest miners. Let G the number of blocks mined by the attacker and added to the official blockchain. Let also H be the progression of the height of the official blockchain during an attack cycle. We have the probability distribution

P[B] = p, P[AAA] = q 3 , P[AAB] = P[ABA] = pq 2 , P[ABB] = p 2 q
From this we can compute:

G(B) = G(ABB) = 0, G(AAA) = 3, G(AAB) = G(ABA) = 2 and H(B) = 1, H(ABB) = H(AAB) = H(ABA) = 2, H(AAA) = 3 Therefore we can compute the expected values E[G] = p • 0 + q 3 •3 + pq 2 • 2 + pq 2 • 2 + p 2 q • 0 = q 2 (4 -q) and E[H] = p • 1 + q 3 •3 + pq 2 •2 + pq 2 • 2 + p 2 q • 2 = 1 + q + q 2
From these computations it follows:

Proposition 4.2. The profitability ratio of the "1+2" strategy is

Γ = E[G] E[H] = q 2 • (4 -q) 1 + q + q 3
This proves that the "1+2 strategy" is more profitable than the honest strategy if and only if q 2 •(4-q) 1+q+q 3 > q. This happens only when

(5) q > √ 2 -1
Thus, if a miner has a more than √ 2 -1 ≈ 41, 4% of hashpower, then he has no incentive to follow the protocol. From this simple example we reach the conclusion: Proposition 4.3. The rules of the Bitcoin protocol are not aligned with the selfinterests of miners.

One can shown that the "1+2" strategy is the best possible when the miner's attack cycle ends after the discovery of three blocks.

Modified Bitcoin protocol

From Corollary 3.4 and Proposition 4.3 it appears that the origin of the problem comes from the difficulty adjustment formula that can be exploited by blockwithholding strategies. We can prevent these attacks using a different formula for the difficulty adjustment taking into account orphan blocks.

5.1.

A more general difficulty adjustment formula. We consider a more general difficulty adjustment formula on the Bitcoin network of the form :

(6) ∆ = ∆ • D × 10 T
where D denotes the progression of a certain quantity, called difficulty function, over a validation period of n 0 official blocks. In the case of current Bitcoin protocol we simply have that D grows linearly and at the end of the period D = n 0 = 2016. That is, the difficulty function for Bitcoin increases one by one with each new block on the official blockchain.

We can consider more general difficulty functions D. With the new formula, the mining time of a cycle is now proportional to the progression of the difficulty function. The same argument as before shows the following result: Proposition 5.1. In the context of a modified Bitcoin protocol with a difficulty adjustment mechanism following relation (6), the rate of return of a mining strategy is

Γ = E[G] E[D]
where G is the number of blocks per cycle mined by the miner and added to the official blockchain and D denotes the progression of the difficulty function over that cycle.

Then we can consider a modification of the Bitcoin protocol, where miners, in addition to their mining activity, will report the presence of orphan blocks by recording their proof of existence. It is possible to encourage miners to record the existence of orphan blocks by modifying the rule that defines the official blockchain and, as we will see later, even by rewarding the reporting of orphan blocks. The blockchain that maximizes the difficulty is the one reporting the most number of orphan blocks weighted by their difficulty (during a difficulty adjustment period it will be the longest). At the end of a validation period of n 0 official blocks, the adjustment of difficulty will be given by a similar formula as the standard one but of the form:

∆ = ∆ • (n 0 + n 1 ) × 10
T where n 1 is the number of orphaned blocks reported during the last mining period of 2016 blocks. That means that we consider a difficulty function D that is not given by the height function of the blockchain but that increases by 1 at each time that a new block is registered in the official blockchain (whether this is an official block or just an orphan block detected by the network). The honest mining strategy corresponds to a cycle that ends as soon as a block is discovered, which still gives a profitability ratio equal to q. Hence, we have the following Proposition: Corollary 5.2. Consider a finite mining strategy with a length cycle τ and E[τ ] < ∞. The number of blocks added to the official blockchain by the miner (resp. the progression of the difficulty function) between 0 and τ is G(τ ) (resp. D(τ )). This strategy is more profitable than the honest strategy if and only if

E[G(τ )] > qE[D(τ )]
5.2. Stability of the Nakamoto consensus with general difficulty adjustment formula. Now assume that we are running the modified Bitcoin protocol with a difficulty adjustment formula as in (5.1) that takes into account orphan blocks. Theorem 5.3. For any finite mining strategy with E[τ ] < ∞, we have

E[G(τ )] qE[D(τ )]
Proof. During an attack cycle, among the N (τ ) blocks that are mined by the attacker we consdider Orph A , resp. Off A , the number of official, resp. orphan, blocks. Also, we denote N (τ ) blocks mined by honest miners and among them Off H , resp. Orph H , the numbers of officialm resp. orphan, blocks mined by honest miners. We have

N (τ ) = Off H + Orph H N (τ ) = Off A + Orph A and G(τ ) = Off A .
Orphan blocks by honest miners are public and will be registered sooner or later in the official blockchain. Only the orphan blocks of the attacker can remain secret. Therefore we have,

Off A + Off H + Orph H D(τ )
The two processes N and N are Poisson processes of parameters λ • p and λ • q where λ depends on the difficulty adjustment. If all miners are honest, then λ = 1 τ 0 with τ 0 = 10 minutes. The condition

E[τ ] < ∞ gives that E[N (τ )] = λpE[τ ] and E[N (τ )] = λqE[τ ]
. This follows from the fact that if M is a Poisson process of parameter α then the compensated process M (t) -αt is a martingale. Therefore,

pE[Off A ] pE[N (τ )] = pλqE[τ ] = qλpE[τ ] = qE[N (τ )] = qE[Off H ] + qE[Orph H ] which gives, E[G(τ )] = E[Off A ] = pE[Off A ] + qE[Off A ] qE[Off H ] + qE[Orph H ] + qE[Off A ] q • E[D(τ )]
which proves the Proposition.

Corollary 5.4. In the modified Bitcoin protocol, the most profitable strategy is always the honest one, and this does not depend on the connectivity of the miner.

We can indeed be more precise. We have :

pE[Off A ] + pE[Orph A ] = pE[N (τ )] = pλqE[τ ] = qλpE[τ ] = qE[N (τ )] = qE[Off H ] + qE[Orph H ] (7)
Among the Orph A orphan blocks of the attacker, we note Orph A the orphan blocks made public by the attacker and thus detected by the network at a given moment (the others remain secret).

We have, on the one hand

E[D(τ )] = E[Off H ] + E[Orph H ] + E[Off A ] + E[Orph A ]
and on the other hand according to (7),

E[Off A ] + E[Orph A ] = pE[Off A ] + pE[Orph A ] + qE[Off A ] + qE[Orph A ] pE[Off A ] + pE[Orph A ] + qE[Off A ] + qE[Orph A ] qE[Off H ] + qE[Orph H ] + qE[Off A ] + qE[Orph A ] q • E[D(τ )]
Now assume that the protocol grants a reward x to any orphan block creator with x ≤ 1. Then,

G(τ ) = Off A +x • Orph A Off A + Orph A
So, from the above,

E[G(τ )] E[Off A ] + E[Orph A ] q • E[D(τ )]
And we have proved the more general result:

Theorem 5.5. Consider a modified Bitcoin protocol that grants a coinbase fraction reward 0 ≤ x ≤ 1 for each block to orphan block creators. We assume that the difficulty adjustment mechanism is given by (5.1). Then the honest mining strategy is optimal. If x < 1 it is the only optimal strategy.

To illustrate this theorem, we can revisit the example of the "1+2" strategy.

Example 5.6. In the case of the "1+2" strategy, we have Email address: ricardo.perez.marco@gmail.com

Author's Bitcoin Beer Address (ABBA) 1 : 1KrqVxqQFyUY9WuWcR5EHGVvhCS841LPLn

1 You can send some anonymous satoshis to support our research at the pub.

D(B) = 1 ,

 1 D(ABB) = 2, D(AAA) = D(AAB) = D(ABA) = 3 and we check that E[G] -qE[D] = -p 3 q < 0. Léonard de Vinci, Pôle Univ., Research Center, Paris-La Défense, France Email address: cyril.grunspan@devinci.fr CNRS, IMJ-PRG, Paris, France