p2pool/data.py

   1 from __future__ import division
   2
   3 import itertools
   4 import random
   5 import traceback
   6
   7 from p2pool.util import math
   8 from p2pool.bitcoin import data as bitcoin_data
   9
  10 class CompressedList(bitcoin_data.Type):
  11     def __init__(self, inner):
  12         self.inner = inner
  13
  14     def read(self, file):
  15         values, file = bitcoin_data.ListType(self.inner).read(file)
  16         if values != sorted(set(values)):
  17             raise ValueError("invalid values")
  18         references, file = bitcoin_data.ListType(bitcoin_data.VarIntType()).read(file)
  19         return [values[reference] for reference in references], file
  20
  21     def write(self, file, item):
  22         values = sorted(set(item))
  23         values_map = dict((value, i) for i, value in enumerate(values))
  24         file = bitcoin_data.ListType(self.inner).write(file, values)
  25         return bitcoin_data.ListType(bitcoin_data.VarIntType()).write(file, [values_map[subitem] for subitem in item])
  26
  27
  28 merkle_branch_type = bitcoin_data.ListType(bitcoin_data.ComposedType([
  29     ('side', bitcoin_data.StructType('<B')), # enum?
  30     ('hash', bitcoin_data.HashType()),
  31 ]))
  32
  33
  34 share_data_type = bitcoin_data.ComposedType([
  35     ('previous_share_hash', bitcoin_data.PossiblyNone(0, bitcoin_data.HashType())),
  36     ('previous_shares_hash', bitcoin_data.HashType()),
  37     ('target2', bitcoin_data.FloatingIntegerType()),
  38     ('nonce', bitcoin_data.VarStrType()),
  39 ])
  40
  41
  42 coinbase_type = bitcoin_data.ComposedType([
  43     ('identifier', bitcoin_data.FixedStrType(8)),
  44     ('share_data', share_data_type),
  45 ])
  46
  47 share_info_type = bitcoin_data.ComposedType([
  48     ('share_data', share_data_type),
  49     ('new_script', bitcoin_data.VarStrType()),
  50     ('subsidy', bitcoin_data.StructType('<Q')),
  51 ])
  52
  53
  54 share1a_type = bitcoin_data.ComposedType([
  55     ('header', bitcoin_data.block_header_type), # merkle_header not completely needed
  56     ('share_info', share_info_type),
  57     ('merkle_branch', merkle_branch_type),
  58 ])
  59
  60 share1b_type = bitcoin_data.ComposedType([
  61     ('header', bitcoin_data.block_header_type),
  62     ('share_info', share_info_type),
  63     ('other_txs', bitcoin_data.ListType(bitcoin_data.tx_type)),
  64 ])
  65
  66 shares_type = CompressedList(bitcoin_data.VarStrType())
  67
  68 def calculate_merkle_branch(txs, index):
  69     hash_list = [(bitcoin_data.tx_type.hash256(tx), i == index, []) for i, tx in enumerate(txs)]
  70
  71     while len(hash_list) > 1:
  72         hash_list = [
  73             (
  74                 bitcoin_data.merkle_record_type.hash256(dict(left=left, right=right)),
  75                 left_f or right_f,
  76                 (left_l if left_f else right_l) + [dict(side=1, hash=right) if left_f else dict(side=0, hash=left)],
  77             )
  78             for (left, left_f, left_l), (right, right_f, right_l) in
  79                 zip(hash_list[::2], hash_list[1::2] + [hash_list[::2][-1]])
  80         ]
  81
  82     assert hash_list[0][1]
  83     assert check_merkle_branch(txs[index], hash_list[0][2]) == hash_list[0][0]
  84
  85     return hash_list[0][2]
  86
  87 def check_merkle_branch(tx, branch):
  88     hash_ = bitcoin_data.tx_type.hash256(tx)
  89     for step in branch:
  90         if not step['side']:
  91             hash_ = bitcoin_data.merkle_record_type.hash256(dict(left=step['hash'], right=hash_))
  92         else:
  93             hash_ = bitcoin_data.merkle_record_type.hash256(dict(left=hash_, right=step['hash']))
  94     return hash_
  95
  96 def gentx_to_share_info(gentx):
  97     return dict(
  98         share_data=coinbase_type.unpack(gentx['tx_ins'][0]['script'])['share_data'],
  99         subsidy=sum(tx_out['value'] for tx_out in gentx['tx_outs']),
 100         new_script=gentx['tx_outs'][-1]['script'],
 101     )
 102
 103 def share_info_to_gentx(share_info, block_target, tracker, net):
 104     return generate_transaction(
 105         tracker=tracker,
 106         previous_share_hash=share_info['share_data']['previous_share_hash'],
 107         new_script=share_info['new_script'],
 108         subsidy=share_info['subsidy'],
 109         nonce=share_info['share_data']['nonce'],
 110         block_target=block_target,
 111         net=net,
 112     )
 113
 114 class Share(object):
 115     peer = None
 116     gentx = None
 117
 118     @classmethod
 119     def from_block(cls, block):
 120         return cls(block['header'], gentx_to_share_info(block['txs'][0]), other_txs=block['txs'][1:])
 121
 122     @classmethod
 123     def from_share1a(cls, share1a):
 124         return cls(**share1a)
 125
 126     @classmethod
 127     def from_share1b(cls, share1b):
 128         return cls(**share1b)
 129
 130     def __init__(self, header, share_info, merkle_branch=None, other_txs=None):
 131         if merkle_branch is None and other_txs is None:
 132             raise ValueError('need either merkle_branch or other_txs')
 133         if other_txs is not None:
 134             new_merkle_branch = calculate_merkle_branch([dict(version=0, tx_ins=[], tx_outs=[], lock_time=0)] + other_txs, 0)
 135             if merkle_branch is not None:
 136                 if merke_branch != new_merkle_branch:
 137                     raise ValueError('invalid merkle_branch and other_txs')
 138             merkle_branch = new_merkle_branch
 139
 140         self.header = header
 141         self.share_info = share_info
 142         self.merkle_branch = merkle_branch
 143         self.other_txs = other_txs
 144
 145         self.timestamp = self.header['timestamp']
 146
 147         self.share_data = self.share_info['share_data']
 148         self.new_script = self.share_info['new_script']
 149         self.subsidy = self.share_info['subsidy']
 150
 151         self.previous_hash = self.previous_share_hash = self.share_data['previous_share_hash']
 152         self.previous_shares_hash = self.share_data['previous_shares_hash']
 153         self.target2 = self.share_data['target2']
 154
 155         self.hash = bitcoin_data.block_header_type.hash256(header)
 156
 157         if self.hash > self.target2:
 158             print "hash", hex(self.hash)
 159             print "targ", hex(self.target2)
 160             raise ValueError('not enough work!')
 161
 162
 163         self.shared = False
 164
 165     def as_block(self):
 166         if self.other_txs is None:
 167             raise ValueError('share does not contain all txs')
 168
 169         return dict(header=self.header, txs=[self.gentx] + self.other_txs)
 170
 171     def as_share1a(self):
 172         return dict(header=self.header, share_info=self.share_info, merkle_branch=self.merkle_branch)
 173
 174     def as_share1b(self):
 175         return dict(header=self.header, share_info=self.share_info, other_txs=self.other_txs)
 176
 177     def check(self, tracker, net):
 178         import time
 179         if self.previous_share_hash is not None:
 180             if self.header['timestamp'] <= math.median((s.timestamp for s in itertools.islice(tracker.get_chain_to_root(self.previous_share_hash), 11)), use_float=False):
 181                 raise ValueError('share from too far in the past!')
 182
 183         if self.header['timestamp'] > time.time() + 2*60*60:
 184             raise ValueError('share from too far in the future!')
 185
 186         gentx = share_info_to_gentx(self.share_info, self.header['target'], tracker, net)
 187
 188         if self.merkle_branch is not None:
 189             if check_merkle_branch(gentx, self.merkle_branch) != self.header['merkle_root']:
 190                 raise ValueError("gentx doesn't match header via merkle_branch")
 191
 192         if self.other_txs is not None:
 193             if bitcoin_data.merkle_hash([gentx] + self.other_txs) != self.header['merkle_root']:
 194                 raise ValueError("gentx doesn't match header via other_txs")
 195
 196         self.gentx = gentx
 197
 198         return Share2(self)
 199
 200     def flag_shared(self):
 201         self.shared = True
 202
 203     def __repr__(self):
 204         return '<Share %s>' % (' '.join('%s=%r' % (k, v) for k, v in self.__dict__.iteritems()),)
 205
 206 class Share2(object):
 207     '''Share with associated data'''
 208
 209     def __init__(self, share):
 210         self.share = share
 211
 212         self.shared = False
 213
 214     def flag_shared(self):
 215         self.shared = True
 216
 217 def generate_transaction(tracker, previous_share_hash, new_script, subsidy, nonce, block_target, net):
 218     previous_share2 = tracker.shares[previous_share_hash] if previous_share_hash is not None else None
 219     #previous_share2 = chain.shares
 220     #previous_shares
 221     #shares =
 222     #shares = (previous_share2.shares if previous_share2 is not None else [net.SCRIPT]*net.SPREAD)[1:-1] + [new_script, new_script]
 223
 224     lookbehind = 200
 225     chain = list(itertools.islice(tracker.get_chain_to_root(previous_share_hash), lookbehind))
 226     if len(chain) < lookbehind:
 227         target2 = bitcoin_data.FloatingIntegerType().truncate_to(2**256//2**24 - 1)
 228     else:
 229         attempts = sum(bitcoin_data.target_to_average_attempts(share.target2) for share in chain[:-1])
 230         time = chain[0].timestamp - chain[-1].timestamp
 231         if time == 0:
 232             time = 1
 233         attempts_per_second = attempts//time
 234         pre_target = 2**256//(net.SHARE_PERIOD*attempts_per_second) - 1
 235         pre_target2 = math.clip(pre_target, (previous_share2.target2*9//10, previous_share2.target2*11//10))
 236         pre_target3 = math.clip(pre_target2, (0, 2**256//2**24 - 1))
 237         target2 = bitcoin_data.FloatingIntegerType().truncate_to(pre_target3)
 238         print attempts_per_second//1000, "KHASH"
 239         #print "TARGET", 2**256//target2, 2**256/pre_target
 240         #print "ATT", bitcoin_data.target_to_average_attempts(target2)//1000
 241
 242
 243     attempts_to_block = bitcoin_data.target_to_average_attempts(block_target)
 244     max_weight = net.SPREAD * attempts_to_block
 245     total_weight = 0
 246
 247     class fake_share(object):
 248         pass
 249     fake_share.new_script = new_script
 250     fake_share.target2 = target2
 251
 252     dest_weights = {}
 253     for i, share in enumerate(itertools.chain([fake_share], itertools.islice(tracker.get_chain_to_root(previous_share_hash), net.CHAIN_LENGTH))):
 254         weight = bitcoin_data.target_to_average_attempts(share.target2)
 255         if weight > max_weight - total_weight:
 256             weight = max_weight - total_weight
 257
 258         dest_weights[share.new_script] = dest_weights.get(share.new_script, 0) + weight
 259         total_weight += weight
 260
 261         if total_weight == max_weight:
 262             break
 263
 264     amounts = dict((script, subsidy*(199*weight)//(200*total_weight)) for (script, weight) in dest_weights.iteritems())
 265     amounts[net.SCRIPT] = amounts.get(net.SCRIPT, 0) + subsidy*1//200
 266     amounts[net.SCRIPT] = amounts.get(net.SCRIPT, 0) + subsidy - sum(amounts.itervalues()) # collect any extra
 267
 268     dests = sorted(amounts.iterkeys(), key=lambda script: (script == new_script, script))
 269     assert dests[-1] == new_script
 270
 271     previous_shares = [] # XXX
 272
 273     return dict(
 274         version=1,
 275         tx_ins=[dict(
 276             previous_output=None,
 277             sequence=None,
 278             script=coinbase_type.pack(dict(
 279                 identifier=net.IDENTIFIER,
 280                 share_data=dict(
 281                     previous_share_hash=previous_share_hash,
 282                     previous_shares_hash=shares_type.hash256(previous_shares),
 283                     nonce=nonce,
 284                     target2=target2,
 285                 ),
 286             )),
 287         )],
 288         tx_outs=[dict(value=amounts[script], script=script) for script in dests if amounts[script]],
 289         lock_time=0,
 290     )
 291
 292
 293
 294
 295 if __name__ == '__main__':
 296     class FakeShare(object):
 297         def __init__(self, hash, previous_share_hash):
 298             self.hash = hash
 299             self.previous_share_hash = previous_share_hash
 300
 301     t = Tracker()
 302
 303     t.add_share(FakeShare(1, 2))
 304     print t.heads, t.tails
 305     t.add_share(FakeShare(4, 0))
 306     print t.heads, t.tails
 307     t.add_share(FakeShare(3, 4))
 308     print t.heads, t.tails
 309     t.add_share(FakeShare(5, 0))
 310     print t.heads, t.tails
 311     t.add_share(FakeShare(0, 1))
 312     print t.heads, t.tails
 313
 314     for share_hash in t.shares:
 315         print share_hash, t.get_height_and_last(share_hash)
 316
 317 class OkayTracker(bitcoin_data.Tracker):
 318     def __init__(self, net):
 319         bitcoin_data.Tracker.__init__(self)
 320         self.net = net
 321         self.verified = bitcoin_data.Tracker()
 322     """
 323         self.okay_cache = {} # hash -> height
 324
 325     def is_okay(self, start, _height_after=0):
 326         '''
 327         Returns:
 328             {'result': 'okay', verified_height: ...} # if share has an okay parent or if share has CHAIN_LENGTH children and CHAIN_LENTH parents that it verified with
 329             {'result': 'needs_share', 'share_hash': ...} # if share doesn't have CHAIN_LENGTH parents
 330             #{'result': 'needs_share_shares', 'share_hash': ...} # if share has CHAIN_LENGTH children and needs its shares to
 331             {'result': 'not_okay'} # if the share has a not okay parent or if the share has an okay parent and failed validation
 332         '''
 333
 334         if start in self.okay_cache:
 335             return dict(result='okay', verified_height=self.okay_cache['start'])
 336
 337         share = self.shares[start]
 338         if start not in self.shares:
 339             return dict(result='needs_share', share_hash=start)
 340
 341         length = len
 342         to_end_rev = []
 343         for share in itertools.islice(self.get_chain(start), self.net.CHAIN_LENGTH):
 344             if share in self.okay_cache:
 345                 return validate(share, to_end_rev[::-1])
 346             to_end_rev.append(share)
 347         # picking up last share from for loop, ew
 348         self.okay_cache.add(share)
 349         return validate(share, to_end_rev[::-1])
 350     """
 351     def attempt_verify(self, share):
 352         if share.hash in self.verified.shares:
 353             return True
 354         try:
 355             share.check(self, self.net)
 356         except:
 357             print
 358             print "Share check failed:"
 359             traceback.print_exc()
 360             print
 361             return False
 362         else:
 363             self.verified.add(share)
 364             return True
 365     def think(self, ht):
 366         desired = set()
 367
 368         # for each overall head, attempt verification
 369         # if it fails, attempt on parent, and repeat
 370         # if no successful verification because of lack of parents, request parent
 371         for head in self.heads:
 372             head_height, last = self.get_height_and_last(head)
 373             if head_height < self.net.CHAIN_LENGTH and last is not None:
 374                 # request more
 375                 print 1, hex(last)
 376                 desired.add((self.shares[random.choice(list(self.reverse_shares[last]))].peer, last))
 377                 continue
 378
 379             for share in itertools.islice(self.get_chain_known(head), None if last is None else head_height - self.net.CHAIN_LENGTH):
 380                 if self.attempt_verify(share):
 381                     break
 382
 383         last = object
 384
 385         # try to get at least CHAIN_LENGTH height for each verified head, requesting parents if needed
 386         for head in self.verified.heads:
 387             head_height, last_hash = self.verified.get_height_and_last(head)
 388             last_height, last_last_hash = self.get_height_and_last(last_hash)
 389             # XXX review boundary conditions
 390             want = self.net.CHAIN_LENGTH - head_height
 391             can = max(last_height - 1 - self.net.CHAIN_LENGTH, 0) if last_last_hash is not None else last_height
 392             if want > can:
 393                 get = can
 394             else:
 395                 get = want
 396             #print "Z", head_height, last_hash is None, last_height, last_last_hash is None, want, can, get
 397             for share in itertools.islice(self.get_chain_known(last_hash), get):
 398                 if not self.attempt_verify(share):
 399                     break
 400             if head_height < self.net.CHAIN_LENGTH and last_last_hash is not None:
 401                 desired.add((self.verified.shares[random.choice(list(self.verified.reverse_shares[last_hash]))].peer, last_last_hash))
 402
 403         # decide best verified head
 404         def score(share_hash):
 405             head_height, last = self.verified.get_height_and_last(share_hash)
 406             score2 = 0
 407             attempts = 0
 408             max_height = 0
 409             for share in itertools.islice(self.verified.get_chain_known(share_hash), self.net.CHAIN_LENGTH):
 410                 max_height = max(max_height, ht.get_min_height(share.header['previous_block']))
 411                 attempts += bitcoin_data.target_to_average_attempts(share.target2)
 412                 this_score = attempts//(ht.get_highest_height() - max_height + 1)
 413                 if this_score > score2:
 414                     score2 = this_score
 415             res = (min(head_height, self.net.CHAIN_LENGTH), score2)
 416             print res
 417             return res
 418         best = max(self.verified.heads, key=score) if self.verified.heads else None
 419
 420         return best, desired
 421
 422
 423 class Mainnet(bitcoin_data.Mainnet):
 424     SHARE_PERIOD = 5 # seconds
 425     CHAIN_LENGTH = 24*60*60//5 # shares
 426     SPREAD = 3 # blocks
 427     SCRIPT = '4104ffd03de44a6e11b9917f3a29f9443283d9871c9d743ef30d5eddcd37094b64d1b3d8090496b53256786bf5c82932ec23c3b74d9f05a6f95a8b5529352656664bac'.decode('hex')
 428     IDENTIFIER = '7452839666e1f8f8'.decode('hex')
 429     PREFIX = '2d4224bf18c87b87'.decode('hex')
 430     ADDRS_TABLE = 'addrs'
 431     P2P_PORT = 9333
 432
 433 class Testnet(bitcoin_data.Testnet):
 434     SHARE_PERIOD = 5 # seconds
 435     CHAIN_LENGTH = 24*60*60//5 # shares
 436     SPREAD = 3 # blocks
 437     SCRIPT = '410403ad3dee8ab3d8a9ce5dd2abfbe7364ccd9413df1d279bf1a207849310465b0956e5904b1155ecd17574778f9949589ebfd4fb33ce837c241474a225cf08d85dac'.decode('hex')
 438     IDENTIFIER = '1ae3479e4eb6700a'.decode('hex')
 439     PREFIX = 'd19778c812754854'.decode('hex')
 440     ADDRS_TABLE = 'addrs_testnet'
 441     P2P_PORT = 19333