-
Notifications
You must be signed in to change notification settings - Fork 1
/
reorgsim.py
executable file
·187 lines (162 loc) · 8.59 KB
/
reorgsim.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#!/usr/bin/pypy
import random, traceback, platform
from math import *
params = {'attacker_rate':2, # attacker hashrate, where 1.0 is 100% of the pre-fork hashrate
'defender_rate':1., # defender hashrate
'attacker_delay':60*60., # seconds that the attacker waits before publishing their chain
'duration':36000., # seconds before the attacker gives up if they're not ahead
'finalize':0, # allow finalization after this many blocks (0 to disable)
'exp':1.9, # exponent for decaying contributions of later blocks to the penalty factor
'tc':120.} # time constant for penalizing blocks. A delay of tc on the first block gives a penalty of +1 (2x)
debug=0
seed = random.randint(0, 2**32-1) # you can also set this to a specific integer for repeatability
print "Seed = %i" % seed
random.seed(seed)
class Block:
def __init__(self, parent, firstseen, tag=''):
self.parent = parent
self.firstseen = firstseen
self.height = parent.height + 1 if parent else 0
self.difficulty = 1. # not yet implemented
self.pow = parent.pow + self.difficulty if parent else self.difficulty
self.name = str(self.height) + tag
def __str__(self):
return self.name
def __repr__(self):
return "[%6s: parent=%6s, time=%6.0f, height=%3i, diff=%1.2f, PoW=%5.1f]" % (
self.name, str(self.parent), self.firstseen, self.height, self.difficulty,
self.pow)
def find_shared_ancestor(a, b):
known = set()
while a.parent or b.parent:
if a.parent:
a = a.parent
if a in known: return a
known.add(a)
if b.parent:
b = b.parent
if b in known: return b
known.add(b)
return None
def compare_blocks_simple_pow(a, b):
return a if a.pow > b.pow else b
def time_to_beat(enemytip, pow, mytime):
if enemytip.pow < pow:
return mytime
while enemytip.parent and pow < enemytip.parent.pow:
enemytip = enemytip.parent
if not enemytip.parent:
print "huh, couldn't find an equivalent PoW block"
raise
interp = (pow - enemytip.parent.pow) / (enemytip.pow - enemytip.parent.pow)
return enemytip.parent.firstseen + interp * (enemytip.firstseen - enemytip.parent.firstseen)
def compare_blocks_toomim_time(a, b, timeconstant, exponent, finalize=False, root=None, debug=debug):
if root==None: root = find_shared_ancestor(a, b)
if root == None: # this ain't no fork
if debug: print "Hey, you're forkless!"
return compare_blocks_simple_pow(a, b)
bestchain = None
for chaintip, opponent in ((a, b), (b,a)):
blk = chaintip
while blk.pow < opponent.pow:
blk = Block(blk, opponent.firstseen, tag='-TBD')
chainpenalty = 1.
blocks = []
while blk != root:
blocks.append(blk)
blk = blk.parent
for blk in reversed(blocks):
if not hasattr(blk, 'penalty'): # small optimization because python is slow
ts = time_to_beat(a if chaintip == b else b, blk.pow, blk.firstseen)
pseudoheight = (blk.pow - root.pow) / root.difficulty
blk.delay = max(0, blk.firstseen - ts)
blk.penalty = (blk.delay / timeconstant) / (pseudoheight)**exponent
#blk.chainpenalty = blk.parent.chainpenalty + blk.penalty if hasattr(blk.parent, 'chainpenalty') else 1.+blk.penalty
chainpenalty += blk.penalty
blk.chainpenalty = chainpenalty
if debug>2: print " Block %6s increased chain penalty by %4.2f to %5.2f from %4.0f sec delay" % (
str(blk), blk.penalty, chainpenalty, blk.delay)
score = (chaintip.pow - root.pow) / chainpenalty
chaintip.hyposcore = score
chaintip.hypochainpenalty = chainpenalty
if debug>1: print "Overall for %s: score=%f, pow=%f, penalty=%f, chaintip.chainpenalty=%f\n" % (
str(chaintip), score, chaintip.pow - root.pow, chainpenalty, chaintip.chainpenalty)
if bestchain and finalize:
winscore = max(score, bestchain[0])
losescore = min(score, bestchain[0])
winner = chaintip if score == winscore else bestchain[1]
loser = chaintip if score == losescore else bestchain[1]
return winscore / losescore > 2 and winner.height - root.height > finalize
if bestchain == None or score > bestchain[0]:
bestchain = [score, chaintip]
return bestchain[1]
def print_chains(chain_a, chain_b, labels=("Chain A", "Chain B")):
print labels[0] + " "*65 + labels[1]
for h in range(1+max(chain_a[-1].height, chain_b[-1].height)):
a, b = None, None
for blk in chain_a:
if blk.height == h:
a = blk
break
for blk in chain_b:
if blk.height == h:
b = blk
break
print `a` if a else " "*70, `b` if b else ""
def reorgattack(attacker_rate, defender_rate, attacker_delay, duration, tc, exp, finalize=10, debug=debug):
root = Block(None, 0, '')
chain_att = [root]
chain_def = [root]
finalized = 0
t=0.
while t < attacker_delay:
t += random.expovariate(1) * 600. / (attacker_rate + defender_rate)
if random.random() < attacker_rate / (attacker_rate + defender_rate):
chain_att.append(Block(chain_att[-1], attacker_delay, tag='-A'))
else:
chain_def.append(Block(chain_def[-1], t, tag='-D'))
blocks_per_step = 1
i=1
while i < blocks_per_step or compare_blocks_toomim_time(chain_def[-1], chain_att[-1], tc, exp, root=root, debug=0) == chain_def[-1] and t < duration and not finalized:
if i == blocks_per_step:
i = 1
if len(chain_def)/3 > blocks_per_step:
blocks_per_step += 1
else: i+=1
t += random.expovariate(1) * 600. / (attacker_rate + defender_rate)
if random.random() < attacker_rate / (attacker_rate + defender_rate):
chain_att.append(Block(chain_att[-1], t, tag='-A'))
else:
chain_def.append(Block(chain_def[-1], t, tag='-D'))
if finalize > 0 and compare_blocks_toomim_time(chain_def[-1], chain_att[-1], tc, exp, root=root, finalize=finalize, debug=0):
finalized = 1
if debug>1: print_chains(chain_def, chain_att, labels=("Defender", "Attacker"))
return compare_blocks_toomim_time(chain_def[-1], chain_att[-1], tc, exp, debug=debug) == chain_def[-1], len(chain_att), len(chain_def), finalized, chain_att[-1], chain_def[-1]
if __name__ == "__main__":
print "Defender won the sample round above\n" if reorgattack(**params)[0] else "Attacker won the sample round above\n"
if platform.python_implementation() == 'PyPy':
rounds = 10000
else:
rounds = 100
print "Note: PyPy is strongly recommended for running this code. Falling back to 100 rounds for performance."
print "Parameters: att_hashrate = %(attacker_rate)3.2f, def_hashrate = %(defender_rate)3.2f, attacker_delay = %(attacker_delay)4.0f, attack_endurance = %(duration)5.0f, maxreorgdepth = %(finalize)i" % params
results = [reorgattack(debug=0, **params) for i in range(rounds)]
wins = [1 if res[0] else 0 for res in results]
att_blocks = [res[1] for res in results]
def_blocks = [res[2] for res in results]
total_blocks = [res[1] + res[2] for res in results]
def_losses = [res[2] if not res[0] else 0 for res in results]
att_losses = [res[1] if res[0] else 0 for res in results]
net_blocks = [(res[1] - res[2]) * (-1 if res[0] else 1) for res in results]
def_finals = [res[3] for res in results if res[0]]
att_finals = [res[3] for res in results if not res[0]]
print "Defender won %i of %i rounds" % (sum(wins), len(wins))
print "Defender orphan rate: %3.1f%%" % (100.* sum(def_losses) / sum(def_blocks))
print "Attacker orphan rate: %3.1f%%" % (100.* sum(att_losses) / sum(att_blocks))
print "Defender finalizations: %3.1f%%" % (100.* sum(def_finals) / len(results))
print "Attacker finalizations: %3.1f%%" % (100.* sum(att_finals) / len(results))
print sum(total_blocks), sum(att_blocks), sum(def_blocks), sum(def_losses), sum(att_losses), sum(net_blocks)
reorgs = [(i, len([1 for res in results if res[2]==i and not res[0]])) for i in range(20)]
print "\nReorg_size\tProbability"
for org in reorgs: print "%i \t%3.1f%%" % (org[0], 100.*org[1]/len(results))
print "Chance of >=10 block reorg: %3.1f%%" % (100.* sum(org[1] for org in reorgs[10:])/len(results))