Skip to content

Instantly share code, notes, and snippets.

@ajtowns
Last active April 6, 2021 02:44
Show Gist options
  • Save ajtowns/fbcf30ed9d0e1708fdc98a876a04ff69 to your computer and use it in GitHub Desktop.
Save ajtowns/fbcf30ed9d0e1708fdc98a876a04ff69 to your computer and use it in GitHub Desktop.
Estimate losses to miners with forced signalling
#!/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("----")
#!/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("")
#!/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)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment