Analysis of Difficulty Control in Bitcoin and Proof-of-Work Blockchains
Daniel Fullmer A. S. Morse


[
    Fridolin Melong
    December 30, 2023
=====================

empty
empty


    This paper presents a stochastic model for block arrival times based on the difficulty retargeting rule used in Bitcoin, as well as other proof-of-work blockchains.
    Unlike some previous work, this paper explicitly models the difficulty target as a random variable which is a function of the previous block arrival times and affecting the block times in the next retargeting period.
    An explicit marginal distribution is derived for the time between successive blocks (the blocktime), while allowing for randomly changing difficulty.
    This paper also aims to serve as an introduction to Bitcoin and proof-of-work blockchains for the controls community, focusing on the difficulty retargeting procedure used in Bitcoin.




§ INTRODUCTION

Bitcoin is a decentralized digital currency (or cryptocurrency) operated by an ad-hoc network of computers.
It enables peer-to-peer payments without requiring a trusted third party.
Bitcoin's original “whitepaper” <cit.> was released late 2008, and the currency was launched in 2009.
There has been a significant amount of current interest in Bitcoin and alternative cryptocurrencies, as well as the technology underlying Bitcoin, the “blockchain.”

This paper focuses on one aspect of Bitcoin and blockchain-based systems, specifically difficulty retargeting, also called difficulty readjustment or difficulty control.
Some existing published analysis of difficulty control in Bitcoin may be found in <cit.> and <cit.>.
In <cit.>, the authors note that the block arrival times do not follow a Poisson distribution
and present a variety of modeling alternatives, testing them against real data from the Bitcoin blockchain.
In <cit.> the Bitcoin mining process is treated as a nonhomogeneous Poisson process with a deterministic intensity function λ(t).
Their analysis principally focuses on the design of a difficulty retargeting algorithm under the assumption of an exponentially increasing hashrate.
However, as noted in the paper, <cit.> does not account for the fact that λ(t) is itself a stochastic process depending on the time of the arrivals of the process.[
Poisson processes whose intensity functions are themselves stochastic processes are sometimes called “Cox processes” <cit.> or “doubly stochastic Poisson processes.”
The authors of this paper are not aware of the study of general Poisson processes whose intensity function depends on previous arrivals in the same way as considered in this paper.
]
This paper explicitly considers this case, and furthermore derives a marginal distribution for the time between successive blocks as well as their expected value and variance.
In order to derive these results, a stochastic model for block arrival times is developed as well.

While this paper specifically focuses on the difficulty retargeting rule used in Bitcoin,
the analysis applies to a number of related cryptocurrencies relying on proof-of-work which use a similar retargeting rule.

In <ref>, Bitcoin and blockchains are described and motivation is given for the difficulty adjustment mechanism.
In <ref>, the stochastic model for block arrival times is developed.
In <ref>, this model is analyzed and the main result of a marginal distribution, expected value, and variance for block times is presented.
Finally, in <ref>, simulations of the block arrival process are presented and compared with the analytical results given in the previous section.



§ BACKGROUND

The following description of Bitcoin and blockchains omits certain details which are not relevant to the specific problem considered in this paper.
With that said,
it is intended to describe and motivate the purpose of blockchains for cryptocurrencies,
the relevant property proof-of-work blockchains ensure (immutability),
and the purpose of difficulty retargeting.
Readers already familiar these concepts may skip to <ref>.
Readers desiring additional details are encouraged to read <cit.>.

Bitcoin is a cryptocurrency which relies on a public ledger of transactions.
All transactions are recorded on this public ledger, called the “blockchain”.
This ledger may be thought of as an ordered list of transactions.
Each transaction includes the address of the sender, the recipient, the amount, and a digital signature from the sender.
Senders of the currency can create, sign, and submit transactions to be included on the public ledger.
Recipients can check that transactions are valid and included on the ledger (confirmed).
A transaction is valid if it meets a number of criteria, including, if digital signature is valid and the payer has enough currency (as determined by the history of valid transactions on the ledger before that transaction.)
There also is a special type of transaction for creating new currency in the system.

Previous digital currency systems required a trusted third party intermediary to maintain and publish the ledger.
However, a third party maintainer of the public ledger must always be online and available.
It is a centralized, single point of failure.
Although such a potential maintainer is a trusted third party, it is not able to forge the digital signatures required for valid transactions.
As a result, it cannot arbitrarily transfer funds from one user to another.
It can, however, add, remove, or reorder previous transactions on the ledger, as well as censor transactions from particular users.
The ability to add, remove, or reorder transactions in the past may invalidate later transactions.
As a simple example, if one user transfers some amount of currency to another user to another exchange for some good,
and the maintainer later removes this transaction,
the original user then has both the good as well as his or her original currency,
and the other user has nothing.
So, recipients in the system would want to ensure that previous transactions are unchangeable (immutable).
The fundamental innovation of Bitcoin was to create a distributed public ledger which could ensure immutability for past transactions.
This distributed public ledger is the blockchain.

In a blockchain, transactions are grouped into blocks.
Each block contains a reference to the previous block, creating a chain.
Every user of the system keeps a copy of the blockchain[This is not strictly true, but is one of the details which is not relevant for our discussion.].
New blocks are created by users who decide to participate in mining.
These users are called miners.
They collect new transactions, attempt to create (mine) a new block including those transactions, and publish the newly created block to all other users.
However, mining a new block is intentionally difficult.
It requires a proof-of-work <cit.>.
This proof-of-work can be thought of as a solution to a difficult mathematical puzzle which depends on the data in the candidate block.
The purpose of the proof-of-work is to enable immutability of the blockchain, as described below.

For our purposes, a proof-of-work function is a function W : ℬ×ℤ→ [0,1],
where B is the set of valid blocks, and ℤ is the set of integers.
The goal is to find, given a block b ∈ℬ,  an integer “nonce” η satisfying the following:

    W(b, η) < 1/d

for some (large) difficulty target d > 0.
The function W is assumed to be a random oracle, which means that each unique evaluation of W produces a random number uniformly in [0,1].
Each miner repeatedly evaluates W with different nonces until they find one satisfying the difficulty target.
Attempts to find a solution are successful with some small probability as determined by d.
If they find one, their block with the included nonce is considered valid and will be accepted by others in the network,
and we say that the miner has successfully found a block, or that the miner has mined a block.
A block and nonce with a low W(·) value is proof that the miner has done a significant amount of work.
For Bitcoin, this proof-of-work function is based on the SHA-256 hash function <cit.>, but the details of this are not necessary for this paper, and the model in <ref> will suffice.

Successfully mining a block includes a block reward, which is a special transaction creating a predetermined amount of new currency which is allocated to the miner who successfully mined the block.
As a result, there is significant incentive for each miner to dedicate computational resources to the task of mining.



Since various miners may produce multiple blocks based on the same previous block,
multiple versions of the blockchain may exist simultaneously on the network,
but there is incentive for miners and users to come to a consensus on one version.
The rule which leads to consensus is this: the longest[More precisely, the canonical blockchain is the one with the most accumulated proof-of-work.] valid blockchain is the canonical one.
A block is valid if all transactions in the block are valid, the previous block is valid, and the proof-of-work is satisfied.
Because of this rule, miners are incentivized to mine new blocks which based on the existing longest blockchain, so that their rewards are accepted by all other users.

As previously mentioned, the proof-of-work system contributes to the immutability of the blockchain.
If, for instance, an adversarial miner wants to remove some transaction in the past,
he or she could create a new version of the blockchain based on the block immediately preceding the targeted transactions with that specific transaction omitted.
However, in order for this new blockchain to be accepted as canonical, it would have to become longer than the existing blockchain.
If the adversary controls less than half of the mining processing power, it will mine blocks less frequently (on average) than the miners mining on top of the existing blockchain.
It is unlikely the adversary's blockchain could surpass the existing blockchain, and for this reason, blocks far in the past are treated as immutable by the users in the system.
For more details, see <cit.>.

Recalling <ref>, if the difficulty target d is too high or too low, solutions will be found by miners too frequently or infrequently.
The desired goal is to have new solutions (and therefore new blocks) found every β = 10 minutes, on average.
This parameter β was chosen as a tradeoff between ensuring blocks have sufficient time to propagate to all users in the network,
and ensuring that transactions do not take too long to be confirmed (included on the blockchain).
Since miners continue to dedicate additional computational resources to the task of mining, absent any accommodating factor, blocks would be mined too frequently.
So, there is a difficulty retargeting algorithm as part of the Bitcoin consensus rules
which adjusts the difficulty upward if blocks are found too frequently,
or adjusts the difficulty downward if blocks are found too infrequently.
This may be thought of as a difficulty control problem integral to blockchains which rely on proof-of-work.




 §.§ Notation

For a random variable X, X ∼Dist(·) is denotes that X is distributed according to some distribution Dist(·).
For a continuous random variable X, f_X(x; θ) represent the probability density function of X parameterized by θ.
The families of probability distributions used in this paper are Exp(λ), Erlang(N, λ), and Lomax(N, λ)
which are the exponential, Erlang, and Lomax distributions with rate parameter λ and shape parameter N.



§ PROBLEM FORMULATION

Suppose blocks are found at the times given by the random variables 0 ≤ t_1 ≤ t_2 ≤… with the initial block time t_0 = 0.
The time between blocks is denoted by X_k = t_k - t_k-1 for k ≥ 1, and is called the blocktime for block k.

Recall that we treat the proof-of-work function W as a random oracle, meaning each unique evaluation samples uniformly a real value between 0 and 1.
As a result, the process of repeatedly evaluating W(·) until a nonce is found which satisfies the difficulty target may be thought of as Bernoulli trials.
As such, the number of evaluations needed until a success is found follows a geometric distribution.
The continuous analogue of a geometric distribution is the exponential distribution
The limiting behaviour of such a geometric distribution as the number of parallel evaluations and difficulty increases to infinity follows an exponential distribution.
See section 2.2.5 of <cit.>.













In as similar way as in <cit.>, for each k ≥ 1, the random variable X_k is assumed to be distributed according to an exponential distribution with a rate λ_k given by

    λ_k = r_k/d_k

where d_k and r_k are two positive real (random) variables, called the difficulty and the hashrate respectively.
The hashrate may be thought of as representing the sum of the computational resources dedicated toward mining at that time.
This is determined exogenously by the miners.
The difficulty, however, is updated automatically according to the Bitcoin consensus rules.
Recall that the expected value of an exponentially distributed random variable is equal to the inverse of its rate.
So, given a known λ_k, X_k | λ_k = 1/λ_k.

The design of Bitcoin includes a “difficulty retargeting” process which periodically updates the difficulty as the hashrate increases or decreases.
The goal is to have a new block found according to a desired blocktime β = 10 minutes (in expectation).
The difficulty is adjusted according to[The update rule used in Bitcoin additionally restricts d_k+1 to only change by a factor of 4 in either direction. Moreover, the Bitcoin code includes a well-known bug which excludes the final X_k in the sum.]

    d_k+1 = N β/∑_i=1^N X_k-N+i d_k   if  k  N = 0 
    
            d_k   otherwise

where N = 2016 is the number of blocks in each difficulty retargeting period
and d_1 is assumed to be initialized arbitrarily.
Note that the difficulty is constant between difficulty readjustments.
Intuitively, if the time to mine the previous N blocks took longer than N β, then the difficulty is decreased.
Likewise, if the time to mine the previous N blocks was shorter than N β, then the difficulty is increased.

In this paper, for simplicity, we additionally suppose that r_k remains constant during each retargeting period.

We concerned with computing the marginal distribution of the blocktimes X_k, k ≥ 1,
along with the expected value and variance of block times while accounting for randomly varying difficulty according to <ref>.
These results may be found in the sequel as <ref> and <ref>.



 §.§ Derivation of adjustment algorithm

Below is a description of how such a rule <ref> might be derived.
Specifically, it's designed so that λ_k^-1 (the expected time to mine the kth block) is approximately β,
assuming the hashrate is unchanging from the previous to the next period.
To derive this update rule, we first attempt to estimate the hashrate in the previous period, r_k, knowing only d_k and the previous X_k-N+i, 1 ≤ i ≤ N.
Toward this end, we estimate the λ_k, and call it λ̂_k, by setting the expected time to mine N blocks equal to the actual time to mine N blocks.


    N X_k | λ̂_k = N/λ̂_k  = ∑_i=1^n X_k-N+i

Let λ̂_k = r̂_k / d_k, where r̂_k is the estimate of the hashrate in the previous period.

    r̂_k = λ̂_k d_k = N d_k/∑_i=1^n X_k-N+i

With this estimate of the hashrate, the goal is to set d_k+1 such that the expected blocktime of the next block X_k+1 is equal to β, with r_k+1 assumed to be equal to r̂_k.

    β = X_k+1 | λ_k+1 = 1/λ_k+1 = d_k+1/r_k+1 = d_k+1/r̂_k

From this and <ref>,

    d_k+1 = N β/∑_i=1^n X_k-N+i d_k

which matches the update rule in <ref>.



§ ANALYSIS

Since d_k and r_k are assumed to be constant during each retargeting period,
it proves convenient to introduce the following notation.

    d̅_n = d_(n-1)N + 1 = d_(n-1)N + 2 = ⋯ = d_nN
    r̅_n = r_(n-1)N + 1 = r_(n-1)N + 2 = ⋯ = r_nN
    λ̅_n = λ_(n-1)N + 1 = λ_(n-1)N + 2 = ⋯ = λ_nN
    
        T_n = ∑_k=1^N X_(n-1)N+k

for each n ≥ 1.
From this and <ref> it follows that

    d̅_n+1 = N β/T_nd̅_n,    n ≥ 1

From this and <ref>, for each n ≥ 1

    λ̅_n+1
        = r̅_n+1/d̅_n+1
        = r̅_n+1 T_n/N βd̅_n
        = r̅_n+1r̅_n T_n/r̅_n N βd̅_n
        = δ_n+1T_n/N βλ̅_n

where δ_n = r̅_n / r̅_n-1 for n > 1.
It proves convenient to define θ_n = N β/δ_n for n ≥ 1.
So,

    λ̅_n+1 = T_n/θ_n+1λ̅_n

for each n ≥ 1.

So for each n ≥ 1 and 1 ≤ k ≤ N, the block time X_(n-1)N + k is exponentially distributed according to λ̅_n.
However, while λ̅_1 is a fixed value, each λ̅_n, n > 1 is a random variable.
In other words:

    X_k    ∼Exp(λ̅_1)     1 ≤ k ≤ N 
    
        X_(n-1)N + k | λ̅_n    ∼Exp(λ̅_n)     n > 1, 1 ≤ k ≤ N

So, the (conditional) probability density functions are as follows:

    f_X_k(x)    = λ̅_1 e^-λ̅_1 x    1 ≤ k ≤ N 
    
        f_X_(n-1)N + k | λ̅_n(x, λ)    = λ e^-λ x    n > 1, 1 ≤ k ≤ N

Here the distribution of each X_(n-1)N + k, n > 1, 1 ≤ k ≤ N is conditional on the value of λ̅_n.
Since each T_n is the sum of N i.i.d, exponentially distributed random variables whose parameter is λ̅_n,
T_n follows an Erlang distribution with parameters N and λ̅_n.
Similarly,

    T_1    ∼Erlang(N, λ̅_1) 
    
        T_n | λ̅_n    ∼Erlang(N, λ̅_n)     n > 1 
    
        f_T_1(t)    = λ̅_1^N t^N-1 e^-λ̅_1 t/(N-1)!
    
        f_T_n | λ̅_n(t, λ)    = λ^N t^N-1 e^-λ t/(N-1)!    n > 1


We next derive the conditional density function for λ̅_n+1 | λ̅_n, n ≥ 1.
Since λ̅_n+1 is monotonically increasing in T_n, we can perform a change of variables from λ̅_n+1 to T_n 
to determine the p.d.f. of λ̅_n+1 conditioned on λ̅_n.
From <ref>,

    f_λ̅_n+1 | λ̅_n(λ' | λ)
        
           = ( d/d λ'θ_n+1λ'/λ) f_T_n | λ̅_n(θ_n+1λ'/λ, λ)


From this and <ref>,

    f_λ̅_n+1 | λ̅_n(λ' | λ)
           = θ_n+1/λλ^N ( θ_n+1λ'/λ)^N-1 e^-θ_n+1λ'/(N-1)!
       = θ_n+1^N (λ')^N-1 e^-θ_n+1λ'/(N-1)!

Note two things:
First, this is an Erlang distribution with parameters N and θ_n.
Second, this expression is independent of λ.

Writing this more succinctly,

    λ̅_n ∼Erlang(N, θ_n)    where  θ_n = N β/δ_n,    n > 1.

Knowing this, the expected value can be easily calculated as

    λ̅_n = N/θ_n = δ_n/β

for n > 1.

Using this, it is possible to derive the p.d.f. for all X_k beyond the initial period.
These random variables have distributions whose parameters are themselves random variables,
which are referred to as compound distributions <cit.>.
Specifically, the distribution for X_(n-1)N + k, n > 1, 1 ≤ k ≤ N is a Lomax distribution,
which is the result of compounding an exponential distribution <ref> with its rate parameter λ̅_n set according to an Erlang distribution <ref>.
Computing the p.d.f. for X_(n-1)N + k, n > 1, 1 ≤ k ≤ N using <ref> and <ref> gives:

    f_X_(n-1)N+k(x)
        = ∫_λ=0^∞ f_X_(n-1)N+k | λ̅_n(x, λ) f_λ̅_n(λ) dλ
 

    = ∫_λ=0^∞λ e^-λ xθ_n^N λ^N-1 e^-λθ_n/(N-1)! dλ
       = N θ_n^N/(x+θ_n)^N+1∫_λ=0^∞(x + θ_n)^N+1λ^N e^-(x + θ_n) λ/N! dλ
       = N θ_n^N/(x+θ_n)^N+1∫_λ=0^∞Erlang(λ; N+1, x + θ_n) dλ
       = N θ_n^N/(x+θ_n)^N+1

This gives our main result:

Using the difficulty retargeting rule in <ref>,
for n > 1, 1 ≤ k ≤ N the marginal distribution of X_(n-1)N + k is the Lomax distribution with parameters N and θ_n.
i.e.

    X_(n-1)N + k∼Lomax(N, θ_n),    n > 1, 1 ≤ k ≤ N





The expected blocktime and variance are easily computed knowing this distribution.

Using the difficulty retargeting rule in <ref>,
for n > 1, 1 ≤ k ≤ N

    X_(n-1)N + k = θ_n/N-1 = N/(N-1) δ_nβ

assuming N > 1.
Additionally,

    X_(n-1)N + k   = θ_n^2 N/(N-1)^2 (N-2)
       = N^3/(N-1)^2(N-2) δ_n^2β^2

assuming N > 2.


If, instead, the difficulty d_k was assumed to be constant, each blocktime would indeed be distributed according to an exponential distribution with fixed rate parameter λ = 1/β,
whose expected value would be β and variance would be β^2.
It is clear that the difficulty retargeting procedure in <ref> leads to slightly higher expected value and variance.
So, even in the case of constant hashrate δ_n = 1, the Bitcoin blockchain runs too fast by a factor of N/(N-1).
However, for the value of N used in Bitcoin, 2016, N/(N-1) is very close to 1.



One modification to <ref> which would provide slightly better results would be to change N to (N-1).
With this modification, θ_n = (N-1) β / δ_n.
And, supposing δ_n = 1, the expected value of X_(n-1)N + k, n > 1, 1 ≤ k ≤ N is just β, as desired, and its variance is N/N-2β^2.




§ SIMULATIONS

In this section, we sample a realization of the random variables X_k and d_k for k ≥ 1 and different values of the parameter N.
<ref> and <ref> are two realizations of the stochastic process X_k, for N=2 and N=20 respectively.
The blue `x's represent individual block times X_k, and the red line represents the value of 1/λ_k, which is the expected value of X_k.
Note that the y-axes used in these figures are logarithmic.

In these simulations the parameter β is set to 10 and λ_1 set to 1/10, so the blocktimes in the initial period have an expected value of 10.
For <ref>, λ_k is adjusted every other unit of time based on the values of X_k for the previous two blocks, which leads to significantly more variation in the value of λ_k, as compared with <ref>.
The quality of the difficulty adjustment algorithm may be intuitively evaluated by how closely the red line stays to the value 10.
As can be seen by <ref>, the variance of these block times becomes particularly bad for small values of N.
In fact, for N=2, the blocktimes have infinite variance, as a result of them being Lomax-distributed.





§ CONCLUSION





Future work may consider additional difficulty retargeting rules used in other cryptocurrencies,
as well as studying the interaction between multiple blockchains which share a common proof-of-work scheme.




10

Nakamoto2008
S. Nakamoto, “Bitcoin: A Peer-to-Peer Electronic Cash System,” www.bitcoin.org, p. 9, 2008.

Kraft2016
D. Kraft, “Difficulty control for blockchain-based consensus systems,” Peer-to-Peer Networking and Applications, vol. 9, no. 2, pp. 397–413, 2016.

Bowden2018
R. Bowden, H. P. Keeler, A. E. Krzesinski, and P. G. Taylor, “Block arrivals
    in the Bitcoin blockchain,” arXiv:1801.07447, Jan.  2018.

Cox1955
A. Cox, “Some Statistical Methods Connected with Series of Events,” Journal of the Royal Statistical Society. Series B (Methodological),
  vol. 17, no. 2, pp. 129–164, 1955.

Tschorsch2016a
F. Tschorsch and B. Scheuermann, “Bitcoin and Beyond: A Technical Survey on
  Decentralized Digital Currencies,” IEEE Communications Surveys &
  Tutorials, vol. 18, no. 3, pp. 2084–2123, 2016.

Dwork
C. Dwork and M. Naor, “Pricing via Processing or Combatting Junk Mail,” in
  Advances in Cryptology - CRYPTO' 92, pp. 139–147, Berlin,
  Heidelberg: Springer Berlin Heidelberg, 1993.

Back2002
A. Back, “Hashcash - A Denial of Service Counter-Measure,” www.hashcash.org/papers/hashcash.pdf, no. August, pp. 1–10, 2002.

NIST2002
N. I. o. S. and Technology, “Specifications for the Secure Hash Standard -
  FIPS PUB 180-2,” Computing, vol. 2, pp. 1–71, 2002.

Gallager2013
R. Gallager, Stochastic processes: theory for applications.
2013.

Johnson1994
N. L. Johnson, S. Kotz, and N. Balakrishnan, Continuous Univariate
  Distributions, Vol. 1, vol. 2.
Wiley-Interscience, 2nd ed., 1994.



-12cm   
                                  
                                  
                                  
                                  
                                  

