Skip to content

Instantly share code, notes, and snippets.

@impredicative

impredicative/analogy.md

Last active September 2, 2025 00:13
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save impredicative/0907e1699f5ff97a9fed5dee20393266 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save impredicative/0907e1699f5ff97a9fed5dee20393266 to your computer and use it in GitHub Desktop.
Download ZIP
Required number of confirmations
Raw
analogy.md

If it helps, think of proof-of-work as a game of tug-of-war. The strength of each side comes from their combined body weight as an analogy for hashrate.

On one side you have Team Honest, and on the other you have Team Attacker. Every new block is like one pull on the rope. If Team Honest has 60% of the total body weight and Team Attacker has 40%, then on average 60% of the pulls go to Honest and 40% to the Attacker. If the attacker has 49% of the body weight, it’s nearly even. At 50% or more, the attacker is guaranteed to eventually drag the rope to their side.

Your transaction becomes safer the more Team Honest has pulled the rope toward their side before you consider it final. This is what waiting for z confirmations really means. With each confirmation, the attacker falls further behind, and the chance they will ever drag the rope back drops.

But as the attacker’s body weight approaches half of the total, the advantage of extra pulls for Team Honest shrinks dramatically. At 40% weight, a lead of ~200 pulls (blocks) is enough to make their chance of catching up negligible. At 45%, it takes ~700 pulls. At 49%, it takes ~16k pulls. At exactly 50%, no lead is enough: the attacker will always catch up eventually.

Te statistical reality is that with nearly equal body weight, the weaker side still has a non-trivial chance of reversing the rope over thousands of pulls. The attacker’s blocks are valid pulls, made under the same rules. The risk is not block rejection; it is that, given enough time, the attacker can still use their near-equal weight to haul the rope back across and overtake the chain.

Raw
confirmations.md
Pool Share % Required Confirmations (ε=1e-6) Required Confirmations (ε=1e-3)
0 0 0
1 4 2
2 5 3
3 6 3
4 7 3
5 7 4
6 8 4
7 9 4
8 9 5
9 10 5
10 11 5
11 11 6
12 12 6
13 13 7
14 14 7
15 15 8
16 16 8
17 17 9
18 19 9
19 20 10
20 21 11
21 23 11
22 25 12
23 27 13
24 29 14
25 31 15
26 34 17
27 37 18
28 40 20
29 44 22
30 49 24
31 54 26
32 60 29
33 67 32
34 75 36
35 85 41
36 97 47
37 111 54
38 130 63
39 154 74
40 184 89
41 226 109
42 283 137
43 366 177
44 494 239
45 704 340
46 1088 526
47 1912 924
48 4252 2053
49 16795 8111
50 ∞ ∞
Raw
evaluation.md

Your method is mathematically sound and operationally conservative under the usual Nakamoto-model assumptions. It is also appropriately strict when the largest pool share reaches or exceeds 50% (returning inf), because no finite confirmation depth can bound the double-spend risk in that regime.

Why the logic is correct

  1. Correct risk model. You map a largest observed attacker share $q$ to the success probability that this attacker can reorganize a payment $z$ blocks deep using the standard Poisson race model from Nakamoto’s analysis. With $p=1-q$ and $\lambda=z,q/p$,

    $$ P(q,z)=1-\sum_{k=0}^{z}\frac{e^{-\lambda}\lambda^{k}}{k!}\Bigl(1-\bigl(\tfrac{q}{p}\bigr)^{,z-k}\Bigr). $$

    This is the canonical formulation used to set confirmation targets as a function of attacker hash power and risk tolerance $\varepsilon$.

  2. Correct treatment at and above 50%. If $q\ge 0.5$, then $P(q,z)=1$ for any finite $z$ in a longest-chain protocol, so returning math.inf is the only rational output.

  3. Sound decision rule. For $q<0.5$, you choose the minimum integer $z$ such that $P(q,z)\le \varepsilon$. This is the right optimization: it minimizes latency while meeting a chosen risk budget.

  4. Monotonicity and sanity checks (empirical).

    • For fixed $\varepsilon$, the computed $z$ is monotone increasing in $q$, and it grows very rapidly as $q\to 0.5^{-}$.
    • With $\varepsilon=10^{-6}$, your outputs (e.g., $z\approx 11$ at $q=10%$, $z\approx 184$ at $q=40%$, $z\approx 704$ at $q=45%$) are in the expected ballpark for this stringent risk level.
    • The explosion of $z$ near $50%$ is expected and desirable.

  5. Numerical method.

    • Forward direction: an exponential search to bracket the solution followed by integer binary search is efficient and returns the minimal $z$.
    • Reverse direction: solving $P(q,z)=\varepsilon$ for $q\in(0,0.5)$ with a bracketing root finder (Brent) is standard and robust.

Assumptions and limitations (what “safe” means here)

Your guarantees are conditional on the Nakamoto/Poisson model assumptions:

  • Constant attacker share: $q$ remains below 50% throughout the confirmation window. If short spikes take $q\ge 50%$, finite $z$ no longer protects you.
  • Independent block races / no network partitions: The Poisson model abstracts away propagation delays and strategic timing; extreme network conditions could increase effective reorg risk.
  • Single coordinated adversary: Using the largest pool share as $q$ is a conservative proxy; multiple colluding pools could make true $q$ higher than any single observed pool.
  • No advanced strategies beyond catch-up: Selfish mining and other tactics can alter risk slightly, though the dominant threshold behavior near 50% remains the critical factor.

Given these caveats, your method is rational and defensible for setting policy, and errs on the side of caution.

Practical recommendations

  • Operate with headroom: If you observe a largest pool at, say, 45%, consider computing $z$ for a slightly higher $q$ (e.g., 46–47%) as a safety margin.
  • Use a time window and smoothing: Base $q$ on a rolling window (e.g., last 3–6 hours) to avoid reacting to transient noise, but pause acceptance if the windowed or instantaneous share touches 50%.
  • Cap acceptance by value: For very large transactions, lower $\varepsilon$ (e.g., $10^{-9}$) or use additional operational controls (delayed withdrawals, out-of-band KYC checks, etc.).
  • Monitor continuously: Recompute targets if pool shares shift materially.

Optional implementation hardening

Your implementation is already concise and clear. If you expect to work very close to $50%$ with very large $z$, consider:

  • Using log-space (via scipy.special.gammaln and stable summation) to improve numerical stability for large $z$ and $\lambda$.
  • Replacing the explicit PMF loop with combinations of the Poisson CDF and geometric terms to reduce memory pressure when $z$ runs into the tens of thousands.

Conclusion

Your approach—returning inf at $\ge 50%$ and otherwise choosing the minimal $z$ meeting $P(q,z)\le \varepsilon$ using the standard Poisson model—is mathematically justified and operationally prudent. It provides a clear, tunable mapping from observed largest pool share to a warranted confirmation depth with an explicit risk budget.

Raw
nakamoto.py
from __future__ import annotations
import math
from typing import Union
import numpy as np
import pandas as pd
from scipy.optimize import brentq
from scipy.stats import poisson
def _attack_success_prob(q: float, z: int) -> float:
"""
Nakamoto-style probability that an attacker with hashrate fraction q
(0 < q < 1) eventually catches up and can reverse a transaction that is z
blocks deep (z >= 0). For q >= 0.5, the probability is 1 by majority control.
Uses the standard Poisson approximation (Bitcoin whitepaper):
P(q, z) = 1 - sum_{k=0}^{z} [ e^{-λ} λ^k / k! * (1 - (q/p)^{z-k}) ]
where p = 1 - q and λ = z * q / p.
Parameters
----------
q : float
Attacker/pool hashrate share as a fraction in (0, 1).
z : int
Confirmation depth (non-negative integer).
Returns
-------
float
Attack success probability P(q, z).
"""
if q >= 0.5:
return 1.0
if z <= 0:
# With 0 confirmations, success probability is trivially 1
# in the settlement sense (no finality yet).
return 1.0
p = 1.0 - q
lam = z * q / p
# Vectorized evaluation of the Poisson PMF for k = 0..z
ks = np.arange(z + 1)
pmf = poisson.pmf(ks, lam)
# Factor (1 - (q/p)^{z-k}); handle numerical stability when q/p ~ 1
ratio = q / p
# pow_term[j] = ratio**(z - k_j)
pow_term = np.power(ratio, z - ks, dtype=float)
terms = pmf * (1.0 - pow_term)
s = float(np.sum(terms))
return max(0.0, min(1.0, 1.0 - s))
def required_confirmations(
pool_share_pct: float,
epsilon: float = 1e-6,
z_max: int = 1_000_000
) -> Union[int, float]:
"""
Given the largest observed pool share (in percent), return the warranted
number of confirmations z such that the double-spend success probability
P(q, z) <= epsilon under the Poisson model.
If the input percentage is >= 50%, majority control is possible; no finite z
can guarantee safety, so the function returns math.inf.
Parameters
----------
pool_share_pct : float
Largest pool share as a percentage, e.g. 55.0 for 55%.
epsilon : float, optional
Target upper bound on attack success probability, default 1e-6.
z_max : int, optional
Hard cap to prevent runaway search in extreme edge cases.
Returns
-------
int | float
Minimal integer confirmations z meeting the risk target, or math.inf if
pool_share_pct >= 50.
"""
q = pool_share_pct / 100.0
if q >= 0.5:
return math.inf
if q <= 0.0:
return 0
# Exponential search to find an upper bound z_hi with P(q, z_hi) <= epsilon
z_lo = 0
z_hi = 1
while z_hi <= z_max and _attack_success_prob(q, z_hi) > epsilon:
z_lo = z_hi
z_hi <<= 1 # double
if z_hi > z_max:
# Could not meet epsilon within bound; return the cap (conservative).
return z_max
# Binary search for the minimal z in (z_lo, z_hi] with P(q, z) <= epsilon
while z_lo + 1 < z_hi:
z_mid = (z_lo + z_hi) // 2
if _attack_success_prob(q, z_mid) <= epsilon:
z_hi = z_mid
else:
z_lo = z_mid
return z_hi
def max_pool_share_for_confirmations(
z: int,
epsilon: float = 1e-6
) -> float:
"""
Given a proposed confirmation count z, return the largest pool share
(as a percentage) such that P(q, z) <= epsilon. This is found by solving
P(q, z) = epsilon for q in (0, 0.5) using Brent's method.
Parameters
----------
z : int
Proposed confirmation depth (non-negative integer).
epsilon : float, optional
Target upper bound on attack success probability, default 1e-6.
Returns
-------
float
Largest pool share in percent (0 <= result < 50) satisfying the risk
target. If even an infinitesimal attacker exceeds epsilon at this z,
returns 0.0. If epsilon is met arbitrary close to 50%, returns a value
extremely close to but below 50.0.
"""
if z <= 0:
return 0.0 # With z=0, only q≈0 would satisfy small epsilon.
# Define f(q) = P(q, z) - epsilon; we seek the largest q with f(q) <= 0.
def f(q: float) -> float:
return _attack_success_prob(q, z) - epsilon
q_low = 1e-12
q_high = 0.5 - 1e-12
# If even q_low violates the risk target, the answer is effectively 0%
if f(q_low) > 0.0:
return 0.0
# If the target is still satisfied arbitrarily close to 50%, return ~50%
if f(q_high) <= 0.0:
return 50.0 - 1e-10
# Root where P(q, z) = epsilon. This gives the *threshold* q*;
# any q <= q* satisfies the target.
q_star = brentq(f, q_low, q_high, maxiter=200, xtol=1e-12, rtol=1e-10)
return 100.0 * q_star
def generate_confirmations_table() -> str:
"""
Generate a raw markdown table of required confirmations
for pool shares from 0% to 50%, with ε=1e-6 and ε=1e-3.
Returns
-------
str
A markdown-formatted table as a string.
"""
pool_shares = list(range(0, 51))
epsilon1 = 1e-6
epsilon2 = 1e-3
results = []
for ps in pool_shares:
z1 = required_confirmations(ps, epsilon=epsilon1)
z2 = required_confirmations(ps, epsilon=epsilon2)
results.append((ps, z1, z2))
df = pd.DataFrame(results, columns=[
"Pool Share %",
"Required Confirmations (ε=1e-6)",
"Required Confirmations (ε=1e-3)"
])
return df.to_markdown(index=False)
if __name__ == "__main__":
print(generate_confirmations_table())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment