Bounds on chain length with BIP-54 timewarp fixes

Protocol Design
,
21

@zawy It’s a nice idea to write it as a lower bound on the time t in function of a lower bound on the chain length n and an upper bound on the amount of work w. It yields significantly simpler expressions.

For the approach with the simplified difficulty adjustment from Section 3.3, I get:

t \;\geq\; \frac{n-1}{N_\text{period}}\left(T_\text{period} - T_\text{grace}\right) \;-\; T_\text{period}\, \cdot\ln\frac{N_\text{period} + (R_\text{max}-1)\,\frac{w}{W_\text{unit}}} {N_\text{period} + R_\text{max} - 1}

For the approach without that simplification, i.e., the inverse of the formula with the Lambert W from Section 4, I get:

t \;\geq\; \frac{n-1}{N_\text{period}} \left[\,T_\text{period} \cdot\left(\frac{N_\text{period} + (R_\text{max}-1)\,\frac{w}{W_\text{unit}}} {N_\text{period} + R_\text{max} - 1}\right)^{\textstyle -\dfrac{N_\text{period}}{n-1}} \;-\; T_\text{grace}\right]

which looks similar in structure to your approximate one. I don’t have a Lean proof for these, but they’re created using the same approach that was proven correct already, so I believe they are proper lower bounds on t. Both of them come with some constraints on the constants (which are satisfied for us), and the second one requires n to be sufficiently large (to be past the alternating span regime, see Section 4).

Inspired by that, it may be even more interesting to have a lower bound on w given a lower bound on chain length n and an upper bound on time t, i.e., “how much work does an attacker need to do to create an attack chain with certain properties?”.

For that, without the simplification (which seems of little help in this case), I get:

w \;\geq\; \frac{W_\text{unit}}{R_\text{max}-1}\left[ \left(N_\text{period} + R_\text{max} - 1\right) \left(\frac{T_\text{period}} {\frac{N_\text{period}\,t}{n-1} + T_\text{grace}}\right)^{\textstyle \frac{n-1}{N_\text{period}}} \;-\; N_\text{period}\right]

For the Bitcoin + BIP-54 constants, that is:

w \;\geq\; \frac{4295032832}{10923} \left[7350955\left(\frac{4200\,(n-1)}{7t+25\,(n-1)}\right)^{\dfrac{n-1}{2016}} -\;7340032\right]
22

It had crossed my mind that a lower bound on w might be useful. Using 2 of 3 boundaries is interesting in creating a hard limit on the 3rd instead of it having a long statistical tail. The t comes down as the other two go up.

Mean hashrate per block = w / t / n. I guess that value describes a surface of possibilities. I believe that’s the scarce resource that creates our trilemma.

I was trying to conceptualize the new problem and found thinking about hashrate per block helps: He has more than w done in less than t, so it’s a > hashrate that must result in more than n blocks. Or maybe given more than n blocks, the minimal hashrate must have been…

23

Ok, proven now.

If:

  • The number of blocks n is at least 1.
  • No block has timestamp more than t + 7200 seconds after genesis, with t \geq 0.
  • The timestamps of the blocks satisfy both BIP-54 timewarp fix rules.
  • Difficulty adjustment follows existing consensus rules, including integer rounding and conversion to nbits.
  • The total chainwork w of the blocks (computed as \sum \lfloor 2^{256} / \text{target} \rfloor) is at most 2^{208}.

Then:

\begin{gathered} w \;\geq\; \frac{4295032832}{10923}\left[ 7350955\,{\alpha'}^{-\frac{n-1}{2016}} -\;7340032\right]\\[2.5ex] \alpha=\frac{t}{600\,(n-1)}+\frac{1}{168},\qquad \alpha'=\begin{cases} \alpha, & \alpha\ge\mathrm{e}/4\\[1ex] \mathrm{e}^{4\alpha/\mathrm{e}}/4, & \alpha\le\mathrm{e}/4 \end{cases} \end{gathered}

The factor \alpha here is the expected period span divided by 2 weeks, and can normally be used directly. When it is very low however (average period spans under ~9.5 days, or average difficulty adjustments over 1.47x), the corrected \alpha' needs to be used. This is the regime where it becomes profitable to mix/alternative span-0 periods and longer periods.

The exact proven statement is

work_ge_wlow : ∀ (n : ℕ) (x : ℕ → ℤ) (g : ℕ → ℕ) (t : ℕ),                                                                                                                                    
  1 ≤ n →
  x 0 = 0 →
  (∀ i < n, x i ≤ ↑t + 7200) →
  (∀ (j : ℕ), 0 < j → 2016 * j < n → x (2016 * j - 1) - 7200 ≤ x (2016 * j)) →
  (∀ (j : ℕ), 2016 * j + 2015 < n → x (2016 * j) ≤ x (2016 * j + 2015)) →
  g 0 = powLimit →
  (∀ (j : ℕ), 2016 * j + 2015 < n → g (j + 1) = nextTarget (g j) (x (2016 * j + 2015) - x (2016 * j))) →
  ∑ i ∈ Finset.range n, ↑(work (g (i / 2016))) ≤ 2 ^ 208 →
  wlow n t ≤ ∑ i ∈ Finset.range n, ↑(work (g (i / 2016)))

def BIP54.wlow : ℕ → ℕ → ℝ := fun n t => 4295032832 / 10923 * (7350955 * α' n t ^ (-((↑n - 1) / 2016)) - 7340032)
def BIP54.α' : ℕ → ℕ → ℝ := fun n t => if Real.exp 1 / 4 ≤ α n t then α n t else Real.exp (4 * α n t / Real.exp 1) / 4                                                                                                   
def BIP54.α : ℕ → ℕ → ℝ := fun n t => ↑t / (600 * (↑n - 1)) + 1 / 168                                                                                                                                                   
def BIP54.Wunit : ℝ := 2 ^ 32 + 2 ^ 16                                                                                                                                                                              
def BIP54.work : ℕ → ℕ := fun g => 2 ^ 256 / (g + 1)                                                                                                                                                                   
def BIP54.nextTarget : ℕ → ℤ → ℕ := fun g s => compactRound (min powLimit (g * clampSpan s / 1209600))
def BIP54.clampSpan : ℤ → ℕ := fun s => (max (1209600 / 4) (min (4 * 1209600) s)).toNat
def BIP54.compactRound : ℕ → ℕ := fun x => setCompact (getCompact x)
def BIP54.getCompact : ℕ → ℕ × ℕ := fun x => if 2 ^ 23 ≤ mant x then (mant x / 2 ^ 8, nSize x + 1) else (mant x, nSize x)                                                                                                        
def BIP54.setCompact : ℕ × ℕ → ℕ := fun p => if p.2 ≤ 3 then p.1 / 2 ^ (8 * (3 - p.2)) else p.1 * 2 ^ (8 * (p.2 - 3))
def BIP54.mant : ℕ → ℕ := fun x => if nSize x ≤ 3 then x * 2 ^ (8 * (3 - nSize x)) else x / 2 ^ (8 * (nSize x - 3))
def BIP54.nSize : ℕ → ℕ := fun x => (x.size + 7) / 8
def BIP54.powLimit : ℕ := 65535 * 2 ^ 208
24

I want to restate your equation without 7200 and R.

  • U = periods in the chain = (n-1) / 2016.
  • T = timespan of the entire chain in units of target time for 1 period = t /2016 / 600
  • W = work performed as a multiple of the work performed in 1st period = w/w_{0}

Your equation without 7200, R, and 2^(-15) becomes:

W > \left(\frac{U}{T}\right)^U - 1

[ edit: See PW’s more precise eq below. In particular, BTC’s R = 4x timespan limit has a much larger effect than I realized:

W >\approx 3 * \left(\frac{U}{T}\right)^U

/edit ]

This is my equation for T_{min} rearranged, minus a 1 I was missing. With BTC’s w / w_0 and U = 499, it gave a very accurate T = 463.3. Obviously W_{min} is very sensitive to error in U / T due to the ^U. At T = 462 instead of 463.3, W is > 4x BTC’s w/w_{0}. At T = 465, W is > 1/7.

The attacker has a mean hashrate per period of blocks:

H = W / T / U

Substituting:

H > \frac{1}{U T} * \left( \left(\frac{U}{T}\right)^U - 1 \right)

Spot-checking this, if hashrate matches the difficulty in the 1st period and it never changes, then U = T and plugging that in gives W and H > 0 which makes sense.

I guess the benefit for DoS is that if you see a block at U with timestamp T, you can see if the H or W in any block is too high. Maybe that’s something we shouldn’t advertise so that they can make the mistake. Maybe that’s making a bad assumption since refusing to check isn’t in accordance with strict PoW.

25

This can be combined with looking at the N lowest hashes to get upper and lower bounds on W. You plug in the T and U reported for the newest lowest-hash. The resulting W_{min} must be smaller than the following upper bound:

  • N = number of lowest hashes to look at
  • h = Nth lowest hash
  • x = number of standard deviations to be sure

w < 2^{256} * \frac{N-1}{h} * \left( 1 + \frac{X}{\sqrt{N-2}}\right)

on the condition that difficulty target was never < Nth_lowest_hash.

Example data point:

  • block 738031 was 10th lowest when I observed it at chain height 773150. Chain work at that time was
  • w = 1.929e28
  • The Nth lowest hash was 5.83e49
  • Block 768824 was the newest of the 10 lowest hashes with reported chain time of T = 440,941,829 / 2016 / 600 = 364.535. U = 768824 / 2016 = 381.37

Using X = 10 std devs, the upper bound is:

w < 2^{256} * \left(10-1\right) / 5.83e49 * \left( 1 + \frac{10}{\sqrt{8}}\right)

w < 8.21e28

Using the newest T and U out of the 10 lowest hashes in the lower bound equation:

W > (381.37 / 364.535) ^{381.37} -1 = 30,035,430

w > W * 2016 * 2^{32} = 2.60e20 [ x 3 ]

[ edit multiply by 3 for BTC’s 4x timespan limit. See PW’s accurate eq below ]

This confirms chain work at the time of observation of the between the limits.

2.60e20 < 1.929e28 < 8.21e 28

Also the w_{min} for each of the T and U reported by the 10 blocks could be checked.

26

If we define:

  • P = (n-1)/2016, periods in the chain
  • T = t / (3600 \cdot 24 \cdot 14), intended periods for amount of time
  • D = w / (2^{32} + 2^{16}), total summed difficulty

Then the following holds:

D \;\geq\; \begin{cases} A\left[\left(\dfrac{T}{P}+C\right)^{\!-P}-1\right]+1, & \dfrac{T}{P}\;\geq\;\dfrac{\mathrm{e}}{4}-C\\[4ex] A\left[\left(\dfrac{1}{4}\,\mathrm{e}^{\frac{4}{\mathrm{e}}\left(\frac{T}{P}+C\right)}\right)^{\!-P}-1\right]+1, & \dfrac{T}{P}\;<\;\dfrac{\mathrm{e}}{4}-C \end{cases}

where A=672.9794928 = 1+\dfrac{N_\text{period}}{R_\text{max}-1} and C = \dfrac{1}{168} = \dfrac{T_\text{grace}}{T_\text{period}}

If you ignore the C correction from the grace time, and the fast-increase regime \frac{T}{P} < \frac{\mathrm{e}}{4}, then that matches your formula very closely, though it has an additional factor A. You can set A=1 of course, and still get a correct but less tight bound. With the A factor, you account for not just the last block in the chain, but the amount of work in the blocks before it too.

28

I was puzzling over why w has to increase a lot to lower T_{min} if T is starting out close to it. It turns out that if hashrate increases 5% in every period, it decreases T_{min} by 5%. So it’s wrong to think that Bitcoin’s “consistent” 5% per period hashrate increase would have bumped up against T_{min} if it was a lot larger. It just lowers T_{min} at about the same rate. And that’s how much T itself move for whatever timestamp scheme they use.