Estimate losses to miners with forced signalling

forced_signalling_chaos_cost_sim.py

#!/usr/bin/env python3

import math
import random

# twitter thread -- https://twitter.com/ajtowns/status/1321277134225043457

class Tester:
    good_chain = 0
    bad_chain = 0
    bad_time = 0
    max_reorg = 0
    this_reorg = 0

    lose_nover = 0
    lose_spy = 0
    mined_nover = 0
    mined_spy = 0

    def __init__(self, threshold, nover, spy, spy_time):
        self.leeway = 2016 - threshold
        assert nover >= 0 and spy >= 0 and (nover + spy) < 1
        self.nover_thresh = nover
        self.spy_thresh = nover + spy
        self.spy_time = spy_time

    def mine_enforce(self):
        self.good_chain += 1

    def mine_nover(self):
        self.mined_nover += 1
        if self.leeway > 0:
            self.good_chain += 1
            self.leeway -= 1
        else:
            self.lose_nover += 1
            if self.bad_chain == 0:
                self.bad_chain = self.good_chain + 1
                self.this_reorg = 1
            else:
                assert self.bad_chain >= self.good_chain
                self.bad_chain += 1
                self.this_reorg += 1

    def mine_spy(self, time):
        self.mined_spy += 1
        if self.bad_chain == 0 or time > self.bad_time + self.spy_time:
            self.good_chain += 1
        else:
            self.bad_chain += 1
            self.lose_spy += 1
            self.this_reorg += 1

    def mine_rand(self, t):
        if self.good_chain > self.bad_chain:
            # nodes that see the bad chain will be stuck on it until the good chain is longer
            self.bad_chain = 0
            if self.this_reorg > self.max_reorg:
                self.max_reorg = self.this_reorg
        x = random.random()
        if x < self.nover_thresh:
            self.mine_nover()
        elif x < self.spy_thresh:
            self.mine_spy(t)
        else:
            self.mine_enforce()

    def mine_period(self):
        t = 0
        while self.good_chain < 2016 or self.bad_chain >= self.good_chain:
            b = self.bad_chain
            t += math.log1p(-random.random()) * -600
            self.mine_rand(t)
            if b != self.bad_chain:
                self.bad_time = t
        return (self.lose_nover, self.lose_spy, self.mined_nover, self.mined_spy, self.max_reorg)

    @classmethod
    def stats(cls, n, reward, price, **kwargs):
        slv = sle = smv = sme = smx = 0
        for _ in range(n):
            (lv, le, mv, me, mx) = cls(**kwargs).mine_period()
            slv += lv
            sle += le
            smv += mv
            sme += me
            smx += mx
        k = reward*price/1e6
        print("Losses by miners not setting version: $%.1fM (%.1f%%); by spy miners: $%.1fM (%.1f%%); avg max reorg %.1f blocks" % (slv*k/n, slv*100./smv, sle*k/n, sle*100./sme, smx/n))


print("Block reward: $%dk" % (50*6.25))
for nover in [0.1, 0.15, 0.2, 0.3, 0.4]:
    print("Percent hashpower signalling: %d%%" % ((1-nover)*100))
    for tot_spy in [0.9, 0.6]:
        print("  Percent spy-mining: %d%%" % (tot_spy*100))
        for spytime in [5, 20, 90]:
            print("    spy for %ds: " % (spytime), end='')
            Tester.stats(1000, price=50000,reward=6.25,threshold=1815,nover=nover,spy=(tot_spy-nover),spy_time=spytime)
    print("----")

repeated_trials.py

#!/usr/bin/env python3

from math import exp, log

FACT = [1]
def factorial(n):
    assert n >= 0 and type(n) == int
    while n >= len(FACT):
        FACT.append(len(FACT) * FACT[-1])
    return FACT[n]

def logcombinations(n,k):
     assert 0 <= k <= n
     return log(factorial(n)) - log(factorial(k)) - log(factorial(n-k))

def prob(number, thresh, p):
    tot = []
    lp = log(p)
    lmp = log(1-p)
    for i in range(thresh, number+1):
        p = logcombinations(number, i) + i*lp + (number-i)*lmp
        tot.append(p)
    mt = max(tot)
    return exp(mt) * sum(exp(t-mt) for t in tot)

def probtrials(number, thresh, p, trials):
    return 1-(1-prob(number, thresh, p))**trials

def estimate(number, thresh, target, trials=1):
    assert 0 < target < 1
    l = 0,0
    h = 1,1
    diff = min(0.0001, target/2, (1-target)/2)
    while (h[1] - l[1]) >= diff:
        m = (h[0] + l[0])/2
        mp = probtrials(number, thresh, m, trials)
        if mp < target:
            l = m,mp
        elif mp > target:
            h = m,mp
        else: # ==
            return (m,mp)
    return (l[0]+h[0])/2,(l[1]+h[1])/2

def pretty(hp,p):
    print("%.2f%% hashpower gives %.5f%% chance of success" % (hp*100, p*100))


def needed_p(trials, target_p):
    # prob p of success per trial
    # (1-p) failure per trial
    # (1-p)^t failure in each of t trials
    # target_p = 1-(1-p)^t success in any of n trials
    # p = 1 - (1-target_p)^(1/t)
    return 1 - (1-target_p)**(1.0/trials)

def pretty2(hp, p, t):
    print("%.2f%% hashpower gives %.5f%% chance of success for %.5f%% chance over %d trials" % (hp*100, p*100, 1-(1-p)**t, t))

pretty(*estimate(2016, 1815, 0.00001, 26))
# 86.35% hashpower gives 0.00087% chance of success

pretty(*estimate(2016, 1815, 0.5, 26))
# 88.65% hashpower gives 50.00157% chance of success

pretty(*estimate(2016, 1815, 0.99999, 26))
# 89.76% hashpower gives 99.99908% chance of success

print("-----")
for p in [0.1, 0.5, 0.9]:
    for x in [5,7,51,55]:
        pretty2(*estimate(2016, 1815, needed_p(x, p), x), x)
    print("")

test_disaster.py

#!/usr/bin/env python3

import random
import math
from collections import defaultdict

class Chain:
    def __init__(self, other=None):
        if other is None:
            self.total = 0
            self.non_signal = 0
            self.mined_by = defaultdict(int)
        else:
            self.total = other.total
            self.non_signal = other.non_signal
            self.mined_by = other.mined_by.copy()

    def __repr__(self):
        return "Chain(%d,%d)" % (self.total, self.non_signal)

    def mine(self, signal, who):
        self.total += 1
        self.mined_by[who] += 1
        if not signal and self.total < 2016:
            self.non_signal += 1

class Sim:
    def __init__(self, p_lot_true, p_no_sig):
        self.ok_no_signal = 201
        self.p_lot_true = p_lot_true
        self.p_no_sig = p_no_sig
        self.best = Chain()
        self.lot_true = Chain(self.best)

    def __repr__(self):
        return "best:%r lot_true:%r" % (self.best, self.lot_true)

    def mine(self):
        p = random.random()
        if p < self.p_lot_true:
            self.lot_true.mine(True, "lot")
        elif p < self.p_lot_true + self.p_no_sig:
            self.best.mine(False, "nosig")
        else:
            self.best.mine(True, "other")

        # reorgs
        if self.best.total == self.lot_true.total:
            pass # everyone sticks with what they know
        elif self.best.total > self.lot_true.total:
            if self.best.non_signal <= self.ok_no_signal:
                self.lot_true = Chain(self.best)
        else: # self.best.total < self.lot_true.total:
            self.best = Chain(self.lot_true)

    def run_sim(self):
        while True:
            self.mine()
            if self.best.total >= 2016:
                if self.best.non_signal <= self.ok_no_signal:
                    return 1
                elif self.best.total > self.lot_true.total + 12:
                    return 0

x = [ Sim(0.40, 0.20).run_sim() for _ in range(10000) ]
print("%.2f%%" % (100.0 * sum(x) / len(x)))