/ timing_strats.py
timing_strats.py
1 import random 2 import hashlib 3 import sys 4 # Clock offset 5 CLOCKOFFSET = 1 6 # Block time 7 BLKTIME = 40 8 # Round run time 9 ROUND_RUNTIME = 500000 10 # Number of rounds 11 ROUNDS = 2000 12 # Block reward 13 BLKREWARD = 1 14 # Reward for including x ticks' worth of transactions 15 # Linear by default, but sublinear formulas are 16 # probably most accurate 17 get_txreward = lambda ticks: 0.0001 * ticks 18 # Latency function 19 latency_sample = lambda L: int((random.expovariate(1) * ((L/1.33)**0.75))**1.33) 20 # latency = lambda: random.randrange(15) if random.randrange(10) else 47 21 # Offline rate 22 OFFLINE_RATE = 0.03 23 24 BLANK_STATE = {'transactions': 0} 25 26 class Simulation(): 27 def __init__(self, validators): 28 for i, v in enumerate(validators): 29 v.id = i 30 v.simulation = self 31 self.validators = validators 32 self.time = 0 33 self.next_id = 0 34 self.gvcache = {} 35 36 def run(self, rounds): 37 # Run the simulation 38 for i in range(rounds): 39 for m in self.validators: 40 m.mine() 41 m.listen() 42 self.time += 1 43 if i % (rounds // 100) == 0: 44 print 'Completed %d rounds out of %d' % (i, rounds) 45 46 def get_validator(self, randao, skips): 47 key = (randao << 32) + skips 48 if key not in self.gvcache: 49 self.gvcache[key] = sha256_as_int(key) % len(self.validators) 50 return self.gvcache[key] 51 52 53 class Block(): 54 def __init__(self, parent, state, maker, number=0, skips=0): 55 self.prevhash = parent.hash if parent else 0 56 self.state = state 57 self.number = number 58 self.height = parent.height + 1 if parent else 0 59 self.hash = random.randrange(10**20) + 10**23 * self.height 60 self.randao = sha256_as_int((parent.randao if parent else 0) + maker) 61 self.totskips = (parent.totskips if parent else 0) + skips 62 63 def sha256_as_int(v): 64 hashbytes = hashlib.sha256(str(v)).digest()[:4] 65 o = 0 66 for b in hashbytes: 67 o = (o << 8) + ord(b) 68 return o 69 70 GENESIS = Block(None, BLANK_STATE, 0) 71 72 # Insert a key/value pair into a state 73 # This is abstracted away into a method to make it easier to 74 # swap the state out with an immutable dict library or whatever 75 # else to increase efficiency 76 def update_state(s, k, v): 77 s2 = {_k: _v for _k, _v in s.items()} 78 s2[k] = v 79 return s2 80 81 # Get a key from a state, default zero 82 def get_state(s, k): 83 return s.get(k, 0) 84 85 86 class Validator(): 87 def __init__(self, strategy, latency=5): 88 # The block that the validator considers to be the head 89 self.head = GENESIS 90 # A map of tick -> blocks that the validator will receive 91 # during that tick 92 self.listen_queue = {} 93 # Blocks that the validator knows about 94 self.blocks = {GENESIS.hash: GENESIS} 95 # Scores (~= total subtree weight) for those blocks 96 self.scores = {GENESIS.hash: 0} 97 # When the validator received each block 98 self.time_received = {GENESIS.hash: 0} 99 # Received too early? 100 self.received_too_early = {} 101 # Blocks with missing parents, mapping parent hash -> list 102 self.orphans_by_parent = {} 103 # ... mapping hash -> list 104 self.orphans = {} 105 # This validator's clock is off by this number of ticks 106 self.time_offset = random.randrange(CLOCKOFFSET) - CLOCKOFFSET // 2 107 # Set the validator's strategy 108 self.set_strategy(strategy) 109 # Keeps track of the highest block number a validator has already 110 # produced a block at 111 self.min_number = 0 112 # The validator's ID 113 self.id = None 114 # Blocks created 115 self.created = 0 116 # Number of blocks to backtrack for GHOST 117 self.backtrack = 40 118 # The simulation that this validator is in 119 self.simulation = None 120 # Maximum number of skips to try 121 self.max_skips = 8 122 # Network latency 123 self.latency = latency 124 125 def set_strategy(self, strategy): 126 # The number of ticks a validator waits before producing a block 127 self.produce_delay = strategy[0] 128 # The number of extra ticks a validator waits per skip (ie. 129 # if you skip two validator slots then wait this number of ticks 130 # times two) before producing a block 131 self.per_block_produce_delay = strategy[1] 132 # The number of extra ticks a validator waits per skip before 133 # accpeint a block 134 self.per_block_accept_delay = strategy[2] 135 136 137 # Get the time from the validator's point of view 138 def get_time(self): 139 return max(self.simulation.time + self.time_offset, 0) 140 141 # Add a block to the listen queue at the given time 142 def add_to_listen_queue(self, time, obj): 143 if time not in self.listen_queue: 144 self.listen_queue[time] = [] 145 self.listen_queue[time].append(obj) 146 147 def earliest_block_time(self, parent, skips): 148 return 20 + parent.number * 20 + skips * 40 149 150 def mine(self): 151 # Is it time to produce a block? 152 t = self.get_time() 153 skips = 0 154 head = self.head 155 while self.simulation.get_validator(head.randao, skips) != self.id and skips < self.max_skips: 156 skips += 1 157 if skips == self.max_skips: 158 return 159 # If it is... 160 if t >= self.time_received[head.hash] + self.produce_delay + self.per_block_produce_delay * skips \ 161 and head.number >= self.min_number: 162 # Can't produce a block at this height anymore 163 self.min_number = head.number + 1 + skips 164 # Small chance to be offline 165 if random.random() < OFFLINE_RATE: 166 return 167 # Compute my block reward 168 my_reward = BLKREWARD + get_txreward(self.simulation.time - head.state['transactions']) 169 # Claim the reward from the transactions since the parent 170 new_state = update_state(head.state, 'transactions', self.simulation.time) 171 # Apply the block reward 172 new_state = update_state(new_state, self.id, get_state(new_state, self.id) + my_reward) 173 # Create the block 174 b = Block(head, new_state, self.id, number=head.number + 1 + skips, skips=skips) 175 self.created += 1 176 # print '---------> Validator %d makes block with hash %d and parent %d (%d skips) at time %d' % (self.id, b.hash, b.prevhash, skips, self.simulation.time) 177 # Broadcast it 178 for validator in self.simulation.validators: 179 recv_time = self.simulation.time + 1 + latency_sample(self.latency + validator.latency) 180 # print 'broadcasting, delay %d' % (recv_time - t) 181 validator.add_to_listen_queue(recv_time, b) 182 183 # If a validator realizes that it "should" have a block but doesn't, 184 # it can use this method to request it from the network 185 def request_block(self, hash): 186 for validator in self.simulation.validators: 187 if hash in validator.blocks: 188 recv_time = self.simulation.time + 1 + latency_sample(self.latency + validator.latency) 189 self.add_to_listen_queue(recv_time, validator.blocks[hash]) 190 191 # Process all blocks that it should receive during the current tick 192 def listen(self): 193 head = self.blocks[self.main_chain[-1]] 194 if self.simulation.time in self.listen_queue: 195 for blk in self.listen_queue[self.simulation.time]: 196 self.accept_block(blk) 197 if self.simulation.time in self.listen_queue: 198 del self.listen_queue[self.simulation.time] 199 200 def get_score_addition(self, blk): 201 parent = self.blocks[blk.prevhash] 202 skips = blk.number - parent.number - 1 203 return (0 if blk.hash in self.received_too_early else 10**20) + random.randrange(100) - 50 204 205 def accept_block(self, blk): 206 t = self.get_time() 207 # Parent not found or at least not yet processed 208 if blk.prevhash not in self.blocks and blk.hash not in self.orphans: 209 self.request_block(blk.prevhash) 210 if blk.prevhash not in self.orphans_by_parent: 211 self.orphans_by_parent[blk.prevhash] = [] 212 self.orphans_by_parent[blk.prevhash].append(blk.hash) 213 self.orphans[blk.hash] = blk 214 # print 'validator %d skipping block %d: parent %d not found' % (self.id, blk.hash, blk.prevhash) 215 return 216 # Already processed? 217 if blk.hash in self.blocks or blk.hash in self.orphans: 218 # print 'validator %d skipping block %d: already processed' % (self.id, blk.hash) 219 return 220 # Too early? Re-append at earliest allowed time 221 parent = self.blocks[blk.prevhash] 222 skips = blk.number - parent.number - 1 223 alotted_recv_time = self.time_received[parent.hash] + skips * self.per_block_accept_delay 224 if t < alotted_recv_time: 225 self.received_too_early[blk.hash] = alotted_recv_time - t 226 self.add_to_listen_queue((alotted_recv_time - t) * 2 + self.simulation.time, blk) 227 # print 'too early, validator %d delaying %d (%d vs %d)' % (self.id, blk.hash, t, alotted_recv_time) 228 return 229 # Add the block and compute the score 230 # print 'Validator %d receives block, hash %d, time %d' % (self.id, blk.hash, self.simulation.time) 231 self.blocks[blk.hash] = blk 232 self.time_received[blk.hash] = t 233 if blk.hash in self.orphans: 234 del self.orphans[blk.hash] 235 # Process the scoring rule 236 self.head 237 # print 'post', self.main_chain 238 # self.scores[blk.hash] = self.scores[blk.prevhash] + get_score_addition(skips) 239 if self.orphans_by_parent.get(blk.hash, []): 240 for c in self.orphans_by_parent[blk.hash]: 241 # print 'including previously rejected child of %d: %d' % (blk.hash, c) 242 b = self.orphans[c] 243 del self.orphans[c] 244 self.accept_block(b) 245 del self.orphans_by_parent[blk.hash] 246 247 248 def simple_test(baseline=[10, 40, 31]): 249 # Define the strategies of the validators 250 strategy_groups = [ 251 #((time before publishing a block, time per skip to wait before producing a block, time per skip to wait before accepting), latency, number of validators with this strategy) 252 # ((baseline[0], baseline[1], baseline[2]), 12, 4), 253 # ((baseline[0], baseline[1], baseline[2]), 11, 4), 254 # ((baseline[0], baseline[1], baseline[2]), 10, 4), 255 # ((baseline[0], baseline[1], baseline[2]), 9, 4), 256 # ((baseline[0], baseline[1], baseline[2]), 8, 4), 257 # ((baseline[0], baseline[1], baseline[2]), 7, 4), 258 ((baseline[0], baseline[1], baseline[2]), 6, 5), 259 ((baseline[0], baseline[1], baseline[2]), 5, 5), 260 ((baseline[0], baseline[1], baseline[2]), 4, 5), 261 ((baseline[0], baseline[1], baseline[2]), 3, 5), 262 ((baseline[0], baseline[1], baseline[2]), 2, 5), 263 ((baseline[0], baseline[1], baseline[2]), 1, 5), 264 # ((baseline[0], int(baseline[1] * 0.33), baseline[2]), 3, 2), 265 # ((baseline[0], int(baseline[1] * 0.67), baseline[2]), 3, 2), 266 # ((baseline[0], int(baseline[1] * 1.5), baseline[2]), 3, 2), 267 # ((baseline[0], int(baseline[1] * 2), baseline[2]), 3, 2), 268 # ((baseline[0], baseline[1], int(baseline[2] * 0.33)), 3, 2), 269 # ((baseline[0], baseline[1], int(baseline[2] * 0.67)), 3, 2), 270 # ((baseline[0], baseline[1], int(baseline[2] * 1.5)), 3, 2), 271 # ((baseline[0], baseline[1], int(baseline[2] * 2)), 3, 2), 272 ] 273 sgstarts = [0] 274 275 validators = [] 276 for s, l, c in strategy_groups: 277 sgstarts.append(sgstarts[-1] + c) 278 for i in range(c): 279 validators.append(Validator(s, l)) 280 281 Simulation(validators).run(ROUND_RUNTIME) 282 283 def report(validators): 284 head = validators[0].blocks[validators[0].main_chain[-1]] 285 286 print 'Head block number:', head.number 287 print 'Head block height:', head.height 288 print head.state 289 # print validators[0].scores 290 291 for i, ((s, l, c), pos) in enumerate(zip(strategy_groups, sgstarts)): 292 totrev = 0 293 totcre = 0 294 for j in range(pos, pos + c): 295 totrev += head.state.get(j, 0) 296 totcre += validators[j].created 297 print 'Strategy group %d: average %d / %d / %d' % (i, totrev * 1.0 / c, totcre * 1.0 / c, (totrev * 2.0 - totcre) / c) 298 299 report(validators) 300 301 def evo_test(initial_s=[1, 40, 27]): 302 s0 = [20, 40, 40] 303 s = initial_s 304 INITIAL_GROUP = 20 305 DEVIATION_GROUP = 2 306 LATENCY = 3 307 for i in range(ROUNDS): 308 print 's:', s, ', starting round', i 309 strategy_groups = [ 310 (s0, LATENCY, 1), 311 (s, LATENCY, INITIAL_GROUP - 1), 312 ] 313 for j in range(len(s)): 314 t = [x for x in s] 315 t[j] = int(t[j] * 1.3) 316 strategy_groups.append((t, LATENCY, DEVIATION_GROUP)) 317 u = [x for x in s] 318 u[j] = int(u[j] * 0.7) 319 strategy_groups.append((u, LATENCY, DEVIATION_GROUP)) 320 321 sgstarts = [0] 322 323 validators = [] 324 for _s, _l, c in strategy_groups: 325 sgstarts.append(sgstarts[-1] + c) 326 for i in range(c): 327 validators.append(Validator(_s, _l)) 328 329 Simulation(validators).run(ROUND_RUNTIME) 330 head = validators[0].blocks[validators[0].main_chain[-1]] 331 base_instate = sum([head.state.get(j, 0) for j in range(1, INITIAL_GROUP)]) * 1.0 / (INITIAL_GROUP - 1) 332 base_totcreated = sum([validators[j].created for j in range(1, INITIAL_GROUP)]) * 1.0 / (INITIAL_GROUP - 1) 333 base_reward = base_instate * 2 - base_totcreated 334 print 'old s:', s 335 for j in range(len(s)): 336 L = INITIAL_GROUP + DEVIATION_GROUP * 2 * j 337 M = INITIAL_GROUP + DEVIATION_GROUP * (2 * j + 1) 338 R = INITIAL_GROUP + DEVIATION_GROUP * (2 * j + 2) 339 up_instate = sum([head.state.get(k, 0) for k in range(L, M)]) * 1.0 / (M - L) 340 up_totcreated = sum([validators[k].created for k in range(L, M)]) * 1.0 / (M - L) 341 up_reward = up_instate * 2 - up_totcreated 342 down_instate = sum([head.state.get(k, 0) for k in range(M, R)]) * 1.0 / (R - M) 343 down_totcreated = sum([validators[k].created for k in range(M, R)]) * 1.0 / (R - M) 344 down_reward = down_instate * 2 - down_totcreated 345 print 'Adjusting variable %d: %.3f %.3f %.3f' % (j, down_reward, base_reward, up_reward) 346 if up_reward > base_reward > down_reward: 347 print 'increasing', j, s 348 s[j] = int(s[j] * min(1 + (up_reward - base_reward) * 2. / base_reward, 1.2) + 0.49) 349 elif down_reward > base_reward > up_reward: 350 print 'decreasing', j, s 351 s[j] = int(s[j] * max(1 - (down_reward - base_reward) * 2. / base_reward, 0.8) + 0.49) 352 print 'new s:', s 353 354 if len(sys.argv) >= 2 and sys.argv[1] == "evo": 355 if len(sys.argv) > 4: 356 evo_test([int(sys.argv[2]), int(sys.argv[3]), int(sys.argv[4])]) 357 else: 358 evo_test() 359 elif len(sys.argv) >= 2 and sys.argv[1] == "onetime": 360 if len(sys.argv) > 4: 361 simple_test([int(sys.argv[2]), int(sys.argv[3]), int(sys.argv[4])]) 362 else: 363 simple_test() 364 else: 365 print 'Use evo or onetime'