How far can possibly bitcoin blockchain height diverge from the ideal one- block-per-10-minutes measure?
MotivationDuring
a discussion with @gmaxwell about a hypothetical DoS vulnerability, in response to my suggestion for blacklisting peers that send block locators unreasonably large, he objected to my proposal by asserting that a loyal node may become maliciously bootstrapped and fooled to commit to a very long chain with trivial difficulty, so blocking it won't be helpful. I responded with a moderate version, ... but after further assessments, I realized that the whole situation is somewhat abnormal, the possibility of having honest nodes with an unreasonable perception of chain height.
In bitcoin, 10 minutes block time interval is not imposed synchronously nor integrally. Protocol adjusts the difficulty every 2016 blocks to keep the generation pace at 10 minutes target but a steady growth in network hash power makes it a possibility for chain height to exceed the ideal number based on 10 minutes generation rate. Actually maximum block height of the network as of this writing is #535461 while it is supposed to be ~504300 showing a +6% divergence.
Not satisfied with the situation, I asked myself:
Why should we accept a proposed chain with an unreasonable longitude like 10 times or 1000 times longer than normal in the first place?
Why shouldn't we simply reject such proposals and shut down the peers who made them? Putting difficulty requirements aside, is it possible to have a chain orders of magnitude longer than normal?
In the malicious block locator scenario, a peer node, very commonly a spv, sends us a
getheaders message with a payload of hundreds of thousands stupid hashes as block locator and instead of being rejected and banned we hopefully and exhaustively try to locate them one by one.
At first, @gmaxwell didn't believe it to be an attack vector because of the cpu bound nature of the processing involved but finally he
made a pull request out of that discussion and it was committed to the source. Bitcoin core now puts a MAX_LOCATOR_SZ hardcoded to be equal to 101. So, we have block locator problem fixed now.
A block locator in bitcoin is a special data structure that spontaneously represents (partially) a node's interpretation of block headers in the chain. The spontaneous nature of block locator generation algorithm guarantees its length to be of O(log(n)) where n is the maximum block height in the chain, it is exactly 10+(log
2(n)) . For current block height of 535461 a legitimate block locator should carry a maximum of 29 hashes and a node sending 30 hashes is claiming a chain with 1,073,741,824 height which is almost twice longer and it would be 2 million times
longer if block locator was holding 50 hashes. Yet we were worried about block locators holding thousands of hashes which represent chains with astronomical heights.
Although the issue is fixed now, the underlying theoretical base didn't get the attention it deserves: A boundary for the divergence of actual block chain's height from what we could trivially calculate by dividing the minutes elapsed from an accepted checkpoint block's timestamp by 10 (normal block interval).
At the time of this writing, the divergence is 6+% but we have no measure to consider 60%, 600% , 6,000,000,000% , ... divergence indexes infeasible, until now.
In this article I'm trying to establish a mathematical framework for further research on this problem, by introducing a relation between hash power increase requirements for a specific divergence within a relatively large window of time.
I also found it useful to include a background section for interested readers, if you are familiar with the subjects, just skip this section.
BackgroundDifficulty adjustment: How bitcoin keeps the paceTwo rules are applied in bitcoin protocol for regulating the rate by which blocks are generated:
1- Increase/decrease difficulty every 2016 blocks by comparing the actual time elapsed with an expected 2 week period.
2- Don't Increase/decrease difficulty with a factor greater than 4.
The latter constraint is commonly overlooked because such a large retargeting is very unlikely to happen with the huge inertia of the currently installed hash power but as we are studying extreme conditions, the 4 times increase factor is of much importance.
Longest Chain Rule: How Bitcoin chooses between forksIn bitcoin and its clones, LRU is not interpreted naively as selecting the chain with biggest height as the main, instead it is defined as the chain with most work needed to generate it.
To calculate accumulative work done on each chain:
1-work for each block is calculated as:
floor(2^256 / (target + 1)) This is done in chain.cpp of bitcoin source code via
GetBlockProof function:
arith_uint256 GetBlockProof(const CBlockIndex& block)
122 {
123 arith_uint256 bnTarget;
124 bool fNegative;
125 bool fOverflow;
126 bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow);
127 if (fNegative || fOverflow || bnTarget == 0)
128 return 0;
129 // We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256
130 // as it's too large for an arith_uint256. However, as 2**256 is at least as large
131 // as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1,
132 // or ~bnTarget / (bnTarget+1) + 1.
133 return (~bnTarget / (bnTarget + 1)) + 1;
134 }
2- During loading/adding a block to
block index in memory, not only the block work is computed by calling the above function but also an accumulated chain work is aggregated in
nChainWork with this ocde:
pindex->nChainWork = (pindex->pprev ? pindex->pprev->nChainWork : 0) + GetBlockProof(*pindex);
which is executed both in
LoadBlockIndex and
AddToBlockIndex.
The forks are compared based on
nChainWork of BlockIndex item of their respective last block and once a chain is found
heavier than current active chain a reorg will be performed mainly by updating UTXO and pointing to new chain as the active fork.
Between two difficulty adjustments, this the-most-difficult-chain-is-the-best-chain approach is identical to the-longest-chain-is-the-best-chain originally proposed by Satoshi but when we have to choose between two forks with at least one difficulty adjustment (typically in both forks) there is no guarantee for the results to be identical.
Block timestamp:How bitcoin keeps track of timeIn bitcoin few rules apply to block time and current time. This is an important topic for the purpose of this article, defining an upper bound for the height of forks, because to impose such a boundary a node should eventually have a measure of time and it is not simply its own system clock for obvious reasons.
1- Bitcoin defines a concept named network-adjusted time. It is defined to be the median of times reported by all the peers a node is connected to.
2- In any case network-adjusted time shouldn't offset node's local time more than 70 minutes.
3- Blocks should be marked with a timestamp greater than the median of previous 11 blocks and less than 2 hours after node's network-adjusted-time.
These constraints make it very hard for an adversary to manipulate block times and forging fake chains with fake difficulty and height which is our concern.
AbstractThe short-range difficulty adjustment policy of bitcoin causes a divergence of expected chain height (expected from ideal 10 minutes block time) because of increased hashpower during each epoch, we show that this divergence is exponentially difficult by proving a functional dependency between the ratios by which hash power and the divergence increase:
F = (n/N)^nTo prove this relation, we primarily show the maximum divergence caused by introducing any amount of new hashpower to the network in a specific period of time is achieved when its distribution in epochs, is representable by a
geometric progress.
The 4 times maximum threshold imposed by difficulty adjustment algorithm of network is deliberately ignored to to avoid complicating the discussion. It is a justifiable simplifying assumption in the context of this article because a 4+ times per epoch increase in hashpower is not feasible anyway, as we shortly discuss at the end of the article.
After proving the exponential dependency, we briefly illustrate and discuss its relevance to block locator size problem and other interesting potentials for dealing with similar problems generally.
Lemma:Suppose at the end of a difficulty adjusting epoch we have already chosen as a check point and has started at time t0 we have calculated an average hashpower C as current network hashpower and begun to introduce Q as a relatively large hashpower in a period of time t, greater than or equal to 1 ideal difficulty adjustment epoch time T0. The number of epochs n that occur in period [t0, t0+t], is at its maximum when Q is distributed in a way that the network hashrate would go through a geometrical progression With: Ci = C*qi
and we have Sum(Ci-Ci-1)=Q the increased hash power:
proof:For a network state at the end of a given epoch that is in equilibrium with hashpower C and an arbitrary distribution of new power Q in n epochs we have the sequence
C, C*k1, (C*k1)*k2, ..., (C*ki-1)*ki, ..., (C*kn-1)*kn
defined recursively as :
Ci=Ci-1*ki , C0 = C
Observing that for n+1>i>0:
Ci=C*K1*k2*...*ki=C*K1k2...*ki
and in the end of application of power Q, we have a total hashpower of C+Q that is equal to the last term of the sequence
We have to prove for n+1>i>0 we have k
1=k
2=...=k
n=q for the n epochs to occur in the least possible actual time. For this, we note that in the end of each epoch the difficulty adjustment algorithm of bitcoin (4 times limit temporarily being ignored) resets block generation pace to T
0 for future epochs, so in each epoch we have:
ti= Ci/Ci-1 = (C*K1k2...ki-1)/ (C*K1k2...ki) = 1/ki
For total elapsed time t during n epochs, we have:
T = T0+T0*1/k1+T0*1/k2+... +T0*1/kn
Then:
T/T
0 =1+1/k
1+1/k
2+...+ 1/k
n = 1+ f(k)/(k
1k
2...k
n-1k
n = 1+f(k)/ ((C+Q)/C) )
Where f(k) is the sum of the sequence:
ai = k1k2...kn/ki
, now we need to have this sum in its minimum. We first calculate the product of the terms as prod(a
i) = (k
1k
2...k
n)
n-1 = ((C+Q)/C)
n-1
where ((C+Q)/C) and n-1 are constants and the sum is minimum when a
1=a
2=...=a
n hence:
k1=k2=...=kn
Now we have proof because for the minimum time to be elapsed the power sequence definitively should be rewritten as:
Ci = Ci-1*q = C0*qi
where C
0 = C and n+1>i>1 which is a sequence with geometric progression.
Theorem Minimum hashpower growth factor F = (Q+C)/C needed for bitcoin blockchain
* to grow by an abnormal ratio n/N is determined by F=(n/N)^n
where C is current hashpower of the network and Q is the absolute increase during a period of N*T
0.
*Note: Bitcoin difficulty adjustment algorithm applies 4 times maximum threshold that is ignored deliberately for practical purposes
ProofFor a given F = (Q+C)/C Using the geometric progress lemma above we have:
t=T
0*n/q ==>
t/T0=N=n/q ==> n/N = qand
Q=C*(q
n-1) ==>
(Q+C)/C=F=qneliminating q:
F=(n/N)n
DiscussionThe exponential relationship with the ratio of power increase and the ratio by which blockchain height diverges from normal N=t/T
0 is an important key to understand how impractical would be for a network like bitcoin with tens of thousands penta hash inertia (C) to diverge from its normal behavior in terms of longitude (chain height).
Let's have a graphical illustration of this function. We replace n with N+d where d is the number of abnormally added epochs. So F=((N+d)/N)
(n+d)This form of the equation illustrates how F (relative hashpower) should grow to have N+d epochs instead of N, normal epochs.
figure 1: F/d diagram with various N values for F up to 30 times hashpower increase
Figure 1 illustrates how hard is achieving to 2-3 epochs divergence in 3,6,12,24 standard epoch times (two weeks long each) e.g for reaching to 3 epochs divergence within 24 weeks (12 epochs) even 40 times increase in network hashpower doesn't suffice.
Figure 2 (below) illustrates the same function in larger scale (1000 times hashpower increase). To diverge 6 epochs within 48 weeks we need 800 times increase in network hash power and within 24 weeks even with 1000 times increase divergence can't approach 6.
figure 2: F/d diagram with various N values for F up to 1000 times hashpower increase
This exponential behavior is very interesting and potentially can be used as a basis for confronting malicious bootstrap attacks and issues like what we mentioned in the beginning of this article: bogus block locator issue.
As of the 4 times maximum threshold bitcoin uses for difficulty adjustment, obviously having a 4 times or more increase in each epoch for the network is infeasible specially when it comes to large windows of time, like 1-2 years that cause exponential network hash power increase up to infeasible quantities. Hence, ignoring that threshold practically won't affect this analysis.
