Longest-chain Attacks: Difficulty Adjustment and Timestamp Verifiability

BY KEYHUNTER 05.03.2025
Longest-chain Attacks: Difficulty Adjustment and Timestamp Verifiability

We study an adversary who attacks a Proof-of-Work (POW) blockchain by selfishly constructing an alternative longest chain. We characterize optimal strategies employed by the adversary when a difficulty adjustment rule à la Bitcoin applies. As time (namely the timestamp specified in each block) in most permissionless POW blockchains is somewhat subjective, we focus on two extreme scenarios – when time is completely verifiable, and when it is completely unverifiable. We conclude that an adversary who faces a difficulty adjustment rule will find a longest-chain attack very challenging when timestamps are verifiable. POW blockchains with frequent difficulty adjustments relative to time reporting flexibility will be substantially more vulnerable to longest-chain attacks. Our main finding provides guidance on the design of difficulty adjustment rules and demonstrates the importance of timestamp verifiability.

Keywords: Bitcoin · blockchain · longest chain attack · difficulty adjustment · cryptocurrency · Proof-of-Work

1 Introduction

Permissionless Proof-of-Work (POW) consensus systems feature a network of peer-to-peer nodes that add blocks containing information to a blockchain. Since every node prefers blocks containing information specific to their own benefit, there will be no consensus unless a mechanism that grants nodes permission to add blocks is in place. Nakamoto [12] consensus is one such mechanism. Nodes earn the privilege to propose a block by reporting a suitable nonce to accompany a block containing specific information of their own choice. Receiving nodes accept the proposed block if it is valid. A nonce is a number embedded in the block so that the output of some cryptographic hash function of the block fulfills some condition. Typically, this condition takes the form of a difficulty threshold. An acceptable nonce is one which yields a block hash that falls within a specified distance from zero. Additionally, the information within the blocks must conform to a set of rules referred to as the blockchain’s protocol.

Due to the way that nonces are used, suitable ones can only be found by trial and error. The process of nonce finding is a race of who can test potential numbers most quickly and report their finding to the rest of the network. Nonce finding is literally work in the sense that the only practical way to do it is to pass electrical current through computer chips. A suitable nonce is quite simply, proof that work was done. Other nodes who receive this information then check if the newly received information contains the more cumulative and valid work than their own leading block as measured by the same metric.

If it is the case, the receiving node would accept the newly minted block and build on top of it. This process is referred to as mining and amounts to an arms race. Miners who control more (powerful) computer hardware and have access to cheap energy are able to test potential nonces more quickly. As a result, these miners add more blocks in their own favor.

Without additional safeguards, such a system would imply that an increase in the system mining capacity would result in a higher rate of token generation. To stabilize the token generation rate, blockchain protocols typically specify a difficulty adjustment protocol or rule. The difficulty is adjusted so that the token generation rate is steered towards some target rate as defined in the protocol. There are many different difficulty adjustment rules being used with this same overarching mandate. In this paper, we consider one that is modeled after the protocol used in Bitcoin [12].

Ideally, a difficulty adjustment rule would adjust the difficulty level according to the mining capacity of the network since that is the primary determinant of the block-finding rate. However, the mining capacity of the network is unobservable and particularly so in permissionless systems. Instead, the difficulty adjustment algorithms utilize the time taken for successive blocks to be created as an estimate of mining capacity and this is in turn “proxied” by the timestamps reported in each block. We emphasize the word “proxied” because the system time of a different node is itself unobservable due to the nature of asynchronous networks. Nodes can report any timestamp they please so long as the reported timestamp conforms to some protocol which in turn ensures its acceptance by other nodes. In addition, nodes can successfully mine a block and not report their success until a later time. Since there are various protocols for

4 Usually, the longest chain in a blockchain also requires the most amount of cumulative work to create. However, this is not always the case. For example, see Ethereum prior to its transition to Proof-of-Stake.

accepting/rejecting timestamps, there is substantial variation in the flexibility nodes have for timestamp reporting across different POW blockchains.

We investigate how this timestamp flexibility in relation to the difficulty ad- justment rule influences the optimal strategy that an adversary employs when mounting a longest-chain attack. To make key ideas clearer and more transpar- ent, we work with deterministic mining, which was also adopted in [9,11]. The strategies that apply in a deterministic setting continue to apply in the appro- priate probabilistic setting under the right assumptions about the adversary’s preferences. Other than benign analytical oddities such as integer constraints, none of our key points and findings depends on the deterministic mining as- sumption that we make.

In this paper, we characterize the optimal strategies in a simplified POW blockchain with deterministic mining [9,11] and comment on how the insights from our analysis would translate to real-world implications. Our main finding is that difficulty adjustment rules offer substantial protection against longest- chain attacks provided timestamps are accurate relative to the frequency of the difficulty adjustment.

2 Related Work

We discuss the closely related works that investigate the effect of varying mining difficulty and attacks on manipulating timestamps or mining difficulty. Garay et al. [6] formalize and analyze the core of the Bitcoin protocol, namely the Bitcoin backbone, in the static setting (with fixed number of nodes and fixed difficulty). Subsequently, Garay et al. [7] extend and analyze Bitcoin backbone protocol with mining difficulty adjustment by formulating the target (re)calculation function in Bitcoin. Kraft [10] and Noda et al. [14] study the effect of mining difficulty adjustment and block arrival rate.

The notion of selfish mining is first proposed in [4], which demonstrates disobedient mining could be more profitable than being honest, i.e., following the Bitcoin specification. Subsequently, Davidson and Diamond [3] and Alarcón Negy et al. [13] investigate the profitability of selfish mining [4] under different difficulty adjustment mechanism using simulation. In particular, it is shown that an intermittent selfish mining strategy [13] gives the attacker a higher profit by performing selfish mining intermittently. Per time-unit profitability of selfish mining under different difficulty adjustment mechanisms is also identified in [13].

Meshkove et al. [11] introduce the coin-hopping attack which allows attack- ers to gain profit compared to honest players by exploiting the mining difficulty adjustment. Boverman [2] describes an attack which forces honest players to accept a chain other than the canonical chain by tampering the “network time counter” at an honest player or even a majority of players. Fiat et al. [5] and Goren and Spiegelman [8] introduce the Energy Equilibria attack which min- imizes operational (energy) costs and manipulate mining difficulty to increase mining rewards per unit of time on average.

With the assumptions made, the canonical chain grows constantly a block per unit of time.

Attack starts at time $t_A$. Adversary must construct some chain $a_{N+1}$ that is at least a block longer than the honest miner’s chain. In this figure, we align both chains by block height. Note that $\tilde{t}_{N+1}$’s timestamp must be no more than $t_N$.

Yaish et al. [16] introduce an approach, called stretching and squeezing, which can create and exploit interest-rate arbitrage between decentralized finance platforms by manipulating the mining difficulty. They also find two timestamp weaknesses in Geth’s code. Later, Yaish et al. [15] identify an attack, called uncle maker, that allows attacker to gain higher profit by manipulating block timestamps at proper times.

To the best of our knowledge, we are the first to investigate the joint effect of difficulty adjustment and timestamp verifiability on the optimal strategy for mounting longest-chain attacks.

3 Simplified Proof-of-Work Blockchain

Honest miners. We model a vastly simplified Proof-of-Work (POW) blockchain with genesis block $c_0$ as shown in Figure 1. Honest miners control $M_h := 1$ mining capacity and do not behave strategically. They naively extend the longest chain known and ignore all others. In our notation, block $c_i$ is defined, but yet to be mined at time $t_i$, i.e., its header is fixed but a suitable nonce remains unknown.

The only active miners prior to $t_A$ are the honest miners. At that time, honest miners have mined $c_0$ to $c_{A-1}$, shaded grey, and are about to start mining block $c_A$. An adversary which we will later describe initiates an attack at time $t_A$.

Deterministic Mining. With deterministic mining [9,11], if $M_i$ mining power is dedicated to a block with difficulty $d_i$, then a suitable nonce will take

$$T_i = \frac{d_i}{M_i}$$

time units to be discovered.

The target block finding rate is 1 block per-unit time and each difficulty epoch contains one block. In the spirit of Bitcoin’s difficulty adjustment rule, the difficulty adjusts with every block/epoch following

[ d_{i+1} = \frac{d_i}{T_i} = \frac{d_i}{(\tilde{t}_{i+1} – \tilde{t}_i)} ]

[ d_0 = 1 ]

(2)

where ( \tilde{t} ) refers to the timestamps reported in the blocks.

Combining Equations (1) and (2) yields

[ d_{i+1} = \frac{d_i}{T_i} = \frac{d_{i-1}}{T_{i-1}} \frac{d_{i-1}}{T_{i-2}} \cdots \frac{d_0}{\prod_{j=0}^{i-1} T_{i-j}} ]

As in [12,11], we assume no propagation latency effects and no block transition delays. Honest miners propagate a block as soon as its nonce is discovered and immediately start mining on the next block. On the honest chain,

[ d_{i+1} = \frac{d_i}{T_i} = M_i ]

and consequently, in our setup, ( d_i = T_i = M_h = 1 ) and that ( t_i = i ) as shown in Figure 2.

Adversary. Our adversary seeks to replace ( c ) with a longer chain without any concern for the value of ( c ) or for the energy costs consumed. More concretely, the adversary could be a hostile government or sophisticated hacker, a large short financial position on ( c )’s tokens, or a competing blockchain. Given recent developments in quantum computing, it would not be a stretch to think of the adversary as a miner armed with quantum computing capabilities as described in Bard et al. [1].

The adversary initiates the longest-chain attack at time ( t_A ) which coincides with the time honest miners start mining block ( c_A ). The adversary controls mining capacity ( M_a > M_h ) and seeks to replace ( c ) by constructing an alternative chain starting at ( c_0 ). This analysis also applies if the adversary attacks a blockchain ( A ) blocks behind its most recent block. We name this adversarial chain ( a ). We use ( \tilde{t} ) to denote timestamps as reported by the adversary for chain ( a ).

While honest miners are extending ( c_A ), the adversary must construct ( a_1, a_2, \ldots, a_{N+1} ) where ( a_{N+1} ) is the first block higher than ( c_N ) which is the terminal block on the chain ( c ). Revealing ( a_{N+1} ) to the honest miners ends the game in favor of the adversary and invalidates all transactions between ( c_N ) and ( c_1 ) due to the longest-chain rule. The adversary also seeks to end the game as quickly as possible as measured by the time it spends on the attack. Since chain ( a ) is revealed at ( t_N ), ( \tilde{t}{a{N+1}} ) must be less than or equal to ( t_N ). The timestamp associated with ( a_1 ) is ( t_1 ) because ( c_1 ) and ( a_1 ) share a common ancestor and we assume no network propagation delay. Finally, we assume in this paper that the adversary does not We now align both chains by time. The adversary reports all timestamps truthfully (because it has to). Notice that $a_2$ is created after $t_A$ because the adversary started mining at time $t_A$. $a_{N+1}$ must be timestamped no later than $t_N$.

With all that we have described, what is the best that the adversary can do? As was suggested earlier in this paper, the answer will depend on how much flexibility the adversary has in reporting timestamps which is unobservable by honest miners.

4 What is the Time?

Time is a subjectively defined object in Bitcoin Core’s protocol. As of January 2023, a node accepts a block if the timestamp reported is within lower and upper bounds.\footnote{Block timestamp \url{https://en.bitcoin.it/wiki/Block_timestamp}} The lower bound is the median timestamp of the node’s previous 11 blocks. The upper bound is the median time reported by other connected nodes plus two hours. In other words, “time” specified in a block is valid so long it is not from the distant past or future.

This rather fluid notion of time directly affects the difficulty adjustment rule. Specifically, difficulty adjustment ensures that fluctuations in mining capacity changes will result in temporary deviations from the target token production schedule. Since this rule applies to all chains, an adversary who chooses to mount a longest-chain attack must also adhere to this rule while constructing chain $a$. In order to determine how the difficulty adjustment rule affects the adversary’s attack, we must now be precise about the nature of time.

We now consider two extremes of this flexible notion of time. In the first, time is verifiable and the adversarial miner must behave like an honest miner when it comes to reporting time. In the second, time is not verifiable and the adversary is able to report timestamps with a lot more flexibility.

Verifiable timestamps. When timestamps are \textbf{verifiable}, the timing of the adversary’s actions are observable by the honest miners which essentially forces the adversary to be honest as well. By this, we do not mean that honest miners can see everything the adversary does. We have in mind a situation where it is essentially impossible to falsify time due to the presence of a well-designed accept/reject protocol. It is also possible for a blockchain to feature some hardware technology like Intel SGX which provides trusted time. Figure 4 shows what these timestamps look like when the adversary is reporting honestly.

Unverifiable timestamps. When timestamps are unverifiable, and the honest miners are naive and do not use any additional safeguards, nothing prevents the adversary from choosing a timestamp for block $a_i$ that is different from the time he found the nonce for block $a_{i-1}$. We allow for any timestamp $\tilde{t}i$ so long it is after the timestamp $\tilde{t}{i-1}$. We also assume that blocks cannot contain a timestamp greater than the honest miner’s time when the alternative chain is revealed. Therefore, an adversarial and possibly dishonest miner is free to report any strictly increasing sequence of $\tilde{t}_i$ subject to those caveats. Of course, actual time taken to mine a block continue to obey Equation (1) and the difficulty level continues to evolve following Equation (2) for the chain the adversary is mining on. To highlight the flexibility that the adversary possesses, Figure 5 displays two possibilities for chain $a_i$.

5 Adversary’s Optimal Strategies

5.1 Verifiable Timestamps

In this situation, the adversary’s optimally chooses $M_i < M_a$ for $i \in {1, \ldots, N}$ to construct $a$.

The naive approach. It is easy to see why choosing $M_i = M_a$ for all $i$ will not work. $a_1$ has a difficulty level of 1 and is mined by the adversary in $1/M_a < 1$.

Therefore,

[ T_1 = t_A + \frac{1}{M_a} – t_1. ]

t_A is the time the adversary commences the attack. (1/M_A) is the time it took for a block with difficulty 1 to be mined, and (t_1) is the time block (c_0) was found and hence is the timestamp recorded in block (a_1). Consequently,

[ d_2 = \frac{d_1}{T_1} = \frac{M_a}{(1 + M_a(A – 1))} ]

[ T_2 = \frac{d_2}{M_a} = \frac{1}{(1 + M_a(A – 1))} ]

and

[ d_3 = M_a ]

In other words, the adversary will gain from applying (M_a > 1) to a single block with difficulty 1. In addition, the adversary will enjoy the delay of (A – 1) for one single block and thereafter, extend chain (a) at the target block growth rate of 1 just like (c). In total, (a_1) and (a_2) would have taken the adversary

[ \frac{1}{M_a} + \frac{1}{(1 + M_a(A – 1))} ]

which clearly approaches zero for large (M_a). However, the difficulty adjustment rule ensures that after two blocks the adversary will end up never catching up with (c) because both chain will grow at rate 1 per unit time. In a probabilistic setting, the best that the adversary can do is to reach a random walk with an initial deficit of (A – 2).

Optimal mining of (k) blocks. We now solve the adversary’s problem of optimally allocating mining power if it desires to construct (k) blocks as quickly as possible. Later, we will relate (k) to the problem of overtaking the canonical chain (c). Also, we ignore the fact that there is an added speed bonus from the delay (A – 1) since this is a one-time bonus that only serves to complicate the math with no additional insights.

The adversary’s optimization problem is to

[ \min_{M_i} \sum_{i=1}^{k} T_i \ \text{s.t. } M_i \leq M_a \ T_i = \frac{d_i}{M_i} \ d_{i+1} = \frac{d_i}{T_i} \ d_1 = 1 ]

This can be restated as

[ \min_{M_i} \frac{1}{M_1} + \frac{M_1}{M_2} + \ldots + \frac{M_{k-1}}{M_k} \ \text{s.t. } M_i \leq M_a ]

Clearly $M_k = M_a$ is optimal. Then by Arithmetic-Geometric mean inequality, the smallest value is $kM_a^{\frac{1}{k}}$, which is attained uniquely when all terms in the summation are equal. Hence the solution is

$$M_i = M_a^{\frac{1}{k}} \quad (3)$$

The adversary initiates the attack with $M_1 = M_a^{1/k}$ and increases the mining capacity by a factor of $M_1 > 1$ for $k$ blocks. Consequently, the adversarial chain adds a block every $1/M_1 < 1$ time units and is able to gain on the canonical chain. What we have left unanswered is the amount of mining capability $M_a$ required to overcome the adversary’s deficit of $A$ blocks which we address next.

Overtaking the canonical chain. While the adversary is constructing chain $a$, the canonical chain $c$ is still growing at rate 1. Therefore, the adversary must maintain this scaling up of mining capacity to construct as many blocks at it takes to gain $A$ blocks on the canonical chain so that the latest block it mines is ahead of $c_N$ by a single block.

$$k = A + \frac{k}{M_1} \quad (4)$$

Equation (4) relates number of blocks mined to conduct the attack $k$ and the duration of the attack $\frac{k}{M_1}$ to the initial deficit of $A$ blocks. The honest miners have a head-start of $A$ and continue to mine $\frac{k}{M_1}$ in the time it takes for the adversary to mine $k$ blocks. Combining Equation (4) with (3) yields

$$A = k \left(1 – \frac{1}{\sqrt[k]{M_a}}\right) \quad (5)$$

which links the three fundamental quantities of the initial deficit $A$ to the duration of the optimal attack $k$ and the adversary’s mining capacity $M_a$. For a fixed $A$, note that the mining capacity required grows the faster one intends to attack. As $M_a$ approaches infinity, $k$ approaches $A$. Indeed, instantaneously overcoming a deficit of $A$ would require an infinite amount of $M_a$.

For example with $M_a = 16$, dedicating $M_a = {2, 4, 8, 16}$ would allow for a gain of 4 blocks in 2 units of time since each block takes half a unit of time. Therefore, the adversary can overtake on $A = 2$ if it possessed at least $M_a = 16$ times more mining power than the honest miners. One quickly realizes that the mining power needed to overcome larger values of $A$ blows up the required $M_a$ due to the $k$-th root since $k > A$ for finite $M_a$.

$M_a$ also decreases in the number of blocks taken $k$. For $A = 2, k = 3; M_a = 27$. For $A = 2, k = 4; M_a = 16$ and for large $n$, $M_a$ is about 7.5. For $A = 3, k = 4; M_a = 256$. $M_a$ approaches about 20 for large $n$. In other words, to overtake the canonical chain from a deficit of two blocks over an arbitrarily long attack, the adversary would need at least 7.5 times more mining power than honest miners. This corresponds to an adversarial miner who controls about 90pct of the hash rate. To accomplish the same feat in 3 blocks which is the fastest possible, the adversarial miner would need to be in control of about 95pct of the mining power. In short, the difficulty adjustment protocol coupled with a protocol for validating timestamps provides vast amounts of protection against longest-chain attacks particularly those originating from a long range.

We illustrate this optimal strategy in Figure 6.

[ c_0 \rightarrow c_A \rightarrow \cdots \rightarrow c_N ]

[ t_0 \rightarrow t_A \rightarrow \cdots \rightarrow t_N ]

[ \tilde{t}_1 = t_A ]

[ \tilde{t}_{a_2} = \tilde{t}_1 + \frac{1}{M_1} ]

[ \tilde{t}_{a_3} = \tilde{t}_2 + \frac{1}{M_1} ]

[ \tilde{t}{a{N+1}} \leq t_N ]

Fig. 6. The adversary initiates the attack with ( M_1 = M_0^{1/N} ) and increases it by factor of ( M_1 ) each block so that ( M_i = M_{i-1} ). Therefore, every block takes ( 1/M_1 ) < 1 to mine.

We ignore the initial ( A – 1 ) delay bonus since that only helps the adversary, and only for two blocks.

5.2 Unverifiable Timestamps

While verifiable timestamps are useful, they are not easily attainable without reliance on more frequent communication (e.g., gossip, clock synchronization, etc.) and subjectivity. One may desire a blockchain design with more objectivity, or perhaps, reduce the bandwidth taken up by frequent communication to obtain a network time. We now study such a scenario to shed light on these questions.

While the adversary has flexibility in reporting ( \tilde{T}_i ), the following conditions must still be respected.

[ \tilde{T}_i > 0 ]

[ \sum_{i=1}^{N} \tilde{T}_i \leq N – 1 ]

[ \tilde{t}_{a_1} \geq t_1 = 1 ]

[ \tilde{t}_{N+1} \leq t_N = N ]

The first equation is equivalent to an assertion that the time reported in a block must be ahead of the time reported in its parent. Also, a block discovery time of zero implies infinite mining power which is impossible. The second condition simply states that the reported block times must occur in the past at the time of revelation to the honest miners which occurs when the honest miners are on block-height ( N ). The third condition states that both chains share a common ancestor at height 0. The final condition which follows from the previous two simply states that the adversary must be a block ahead of the honest miners at the time the alternative chain is revealed.

Useful information for enthusiasts:

Contact me via Telegram: @ExploitDarlenePRO