p2pool/bitcoin/data.py

   1 from __future__ import division
   2
   3 import struct
   4 import hashlib
   5 import itertools
   6 import warnings
   7
   8 from . import base58
   9 from p2pool.util import bases, math, skiplist
  10
  11 class EarlyEnd(Exception):
  12     pass
  13
  14 class LateEnd(Exception):
  15     pass
  16
  17 def read((data, pos), length):
  18     data2 = data[pos:pos + length]
  19     if len(data2) != length:
  20         raise EarlyEnd()
  21     return data2, (data, pos + length)
  22
  23 def size((data, pos)):
  24     return len(data) - pos
  25
  26 class Type(object):
  27     # the same data can have only one unpacked representation, but multiple packed binary representations
  28
  29     #def __hash__(self):
  30     #    return hash(tuple(self.__dict__.items()))
  31
  32     #def __eq__(self, other):
  33     #    if not isinstance(other, Type):
  34     #        raise NotImplementedError()
  35     #    return self.__dict__ == other.__dict__
  36
  37     def _unpack(self, data):
  38         obj, (data2, pos) = self.read((data, 0))
  39
  40         assert data2 is data
  41
  42         if pos != len(data):
  43             raise LateEnd()
  44
  45         return obj
  46
  47     def _pack(self, obj):
  48         f = self.write(None, obj)
  49
  50         res = []
  51         while f is not None:
  52             res.append(f[1])
  53             f = f[0]
  54         res.reverse()
  55         return ''.join(res)
  56
  57
  58     def unpack(self, data):
  59         obj = self._unpack(data)
  60
  61         if __debug__:
  62             data2 = self._pack(obj)
  63             if data2 != data:
  64                 assert self._unpack(data2) == obj
  65
  66         return obj
  67
  68     def pack(self, obj):
  69         data = self._pack(obj)
  70
  71         assert self._unpack(data) == obj
  72
  73         return data
  74
  75
  76     def pack_base58(self, obj):
  77         return base58.base58_encode(self.pack(obj))
  78
  79     def unpack_base58(self, base58_data):
  80         return self.unpack(base58.base58_decode(base58_data))
  81
  82
  83     def hash160(self, obj):
  84         return ShortHashType().unpack(hashlib.new('ripemd160', hashlib.sha256(self.pack(obj)).digest()).digest())
  85
  86     def hash256(self, obj):
  87         return HashType().unpack(hashlib.sha256(hashlib.sha256(self.pack(obj)).digest()).digest())
  88
  89 class VarIntType(Type):
  90     # redundancy doesn't matter here because bitcoin and p2pool both reencode before hashing
  91     def read(self, file):
  92         data, file = read(file, 1)
  93         first = ord(data)
  94         if first < 0xfd:
  95             return first, file
  96         elif first == 0xfd:
  97             desc, length = '<H', 2
  98         elif first == 0xfe:
  99             desc, length = '<I', 4
 100         elif first == 0xff:
 101             desc, length = '<Q', 8
 102         else:
 103             raise AssertionError()
 104         data, file = read(file, length)
 105         return struct.unpack(desc, data)[0], file
 106
 107     def write(self, file, item):
 108         if item < 0xfd:
 109             file = file, struct.pack('<B', item)
 110         elif item <= 0xffff:
 111             file = file, struct.pack('<BH', 0xfd, item)
 112         elif item <= 0xffffffff:
 113             file = file, struct.pack('<BI', 0xfe, item)
 114         elif item <= 0xffffffffffffffff:
 115             file = file, struct.pack('<BQ', 0xff, item)
 116         else:
 117             raise ValueError('int too large for varint')
 118         return file
 119
 120 class VarStrType(Type):
 121     _inner_size = VarIntType()
 122
 123     def read(self, file):
 124         length, file = self._inner_size.read(file)
 125         return read(file, length)
 126
 127     def write(self, file, item):
 128         return self._inner_size.write(file, len(item)), item
 129
 130 class FixedStrType(Type):
 131     def __init__(self, length):
 132         self.length = length
 133
 134     def read(self, file):
 135         return read(file, self.length)
 136
 137     def write(self, file, item):
 138         if len(item) != self.length:
 139             raise ValueError('incorrect length item!')
 140         return file, item
 141
 142 class EnumType(Type):
 143     def __init__(self, inner, values):
 144         self.inner = inner
 145         self.values = values
 146
 147         self.keys = {}
 148         for k, v in values.iteritems():
 149             if v in self.keys:
 150                 raise ValueError('duplicate value in values')
 151             self.keys[v] = k
 152
 153     def read(self, file):
 154         data, file = self.inner.read(file)
 155         return self.keys[data], file
 156
 157     def write(self, file, item):
 158         return self.inner.write(file, self.values[item])
 159
 160 class HashType(Type):
 161     def read(self, file):
 162         data, file = read(file, 256//8)
 163         return int(data[::-1].encode('hex'), 16), file
 164
 165     def write(self, file, item):
 166         if not 0 <= item < 2**256:
 167             raise ValueError('invalid hash value - %r' % (item,))
 168         if item != 0 and item < 2**160:
 169             warnings.warn('very low hash value - maybe you meant to use ShortHashType? %x' % (item,))
 170         return file, ('%064x' % (item,)).decode('hex')[::-1]
 171
 172 class ShortHashType(Type):
 173     def read(self, file):
 174         data, file = read(file, 160//8)
 175         return int(data[::-1].encode('hex'), 16), file
 176
 177     def write(self, file, item):
 178         if not 0 <= item < 2**160:
 179             raise ValueError('invalid hash value - %r' % (item,))
 180         return file, ('%040x' % (item,)).decode('hex')[::-1]
 181
 182 class ListType(Type):
 183     _inner_size = VarIntType()
 184
 185     def __init__(self, type):
 186         self.type = type
 187
 188     def read(self, file):
 189         length, file = self._inner_size.read(file)
 190         res = []
 191         for i in xrange(length):
 192             item, file = self.type.read(file)
 193             res.append(item)
 194         return res, file
 195
 196     def write(self, file, item):
 197         file = self._inner_size.write(file, len(item))
 198         for subitem in item:
 199             file = self.type.write(file, subitem)
 200         return file
 201
 202 class StructType(Type):
 203     def __init__(self, desc):
 204         self.desc = desc
 205         self.length = struct.calcsize(self.desc)
 206
 207     def read(self, file):
 208         data, file = read(file, self.length)
 209         res, = struct.unpack(self.desc, data)
 210         return res, file
 211
 212     def write(self, file, item):
 213         data = struct.pack(self.desc, item)
 214         if struct.unpack(self.desc, data)[0] != item:
 215             # special test because struct doesn't error on some overflows
 216             raise ValueError('''item didn't survive pack cycle (%r)''' % (item,))
 217         return file, data
 218
 219 class IPV6AddressType(Type):
 220     def read(self, file):
 221         data, file = read(file, 16)
 222         if data[:12] != '00000000000000000000ffff'.decode('hex'):
 223             raise ValueError('ipv6 addresses not supported yet')
 224         return '.'.join(str(ord(x)) for x in data[12:]), file
 225
 226     def write(self, file, item):
 227         bits = map(int, item.split('.'))
 228         if len(bits) != 4:
 229             raise ValueError('invalid address: %r' % (bits,))
 230         data = '00000000000000000000ffff'.decode('hex') + ''.join(chr(x) for x in bits)
 231         assert len(data) == 16, len(data)
 232         return file, data
 233
 234 class ComposedType(Type):
 235     def __init__(self, fields):
 236         self.fields = fields
 237
 238     def read(self, file):
 239         item = {}
 240         for key, type_ in self.fields:
 241             item[key], file = type_.read(file)
 242         return item, file
 243
 244     def write(self, file, item):
 245         for key, type_ in self.fields:
 246             file = type_.write(file, item[key])
 247         return file
 248
 249 class ChecksummedType(Type):
 250     def __init__(self, inner):
 251         self.inner = inner
 252
 253     def read(self, file):
 254         obj, file = self.inner.read(file)
 255         data = self.inner.pack(obj)
 256
 257         checksum, file = read(file, 4)
 258         if checksum != hashlib.sha256(hashlib.sha256(data).digest()).digest()[:4]:
 259             raise ValueError('invalid checksum')
 260
 261         return obj, file
 262
 263     def write(self, file, item):
 264         data = self.inner.pack(item)
 265         return (file, data), hashlib.sha256(hashlib.sha256(data).digest()).digest()[:4]
 266
 267 class FloatingIntegerType(Type):
 268     # redundancy doesn't matter here because bitcoin checks binary bits against its own computed bits
 269     # so it will always be encoded 'normally' in blocks (they way bitcoin does it)
 270     _inner = StructType('<I')
 271
 272     def read(self, file):
 273         bits, file = self._inner.read(file)
 274         target = self._bits_to_target(bits)
 275         if __debug__:
 276             if self._target_to_bits(target) != bits:
 277                 raise ValueError('bits in non-canonical form')
 278         return target, file
 279
 280     def write(self, file, item):
 281         return self._inner.write(file, self._target_to_bits(item))
 282
 283     def truncate_to(self, x):
 284         return self._bits_to_target(self._target_to_bits(x, _check=False))
 285
 286     def _bits_to_target(self, bits2):
 287         target = math.shift_left(bits2 & 0x00ffffff, 8 * ((bits2 >> 24) - 3))
 288         assert target == self._bits_to_target1(struct.pack('<I', bits2))
 289         assert self._target_to_bits(target, _check=False) == bits2
 290         return target
 291
 292     def _bits_to_target1(self, bits):
 293         bits = bits[::-1]
 294         length = ord(bits[0])
 295         return bases.string_to_natural((bits[1:] + '\0'*length)[:length])
 296
 297     def _target_to_bits(self, target, _check=True):
 298         n = bases.natural_to_string(target)
 299         if n and ord(n[0]) >= 128:
 300             n = '\x00' + n
 301         bits2 = (chr(len(n)) + (n + 3*chr(0))[:3])[::-1]
 302         bits = struct.unpack('<I', bits2)[0]
 303         if _check:
 304             if self._bits_to_target(bits) != target:
 305                 raise ValueError(repr((target, self._bits_to_target(bits, _check=False))))
 306         return bits
 307
 308 class PossiblyNone(Type):
 309     def __init__(self, none_value, inner):
 310         self.none_value = none_value
 311         self.inner = inner
 312
 313     def read(self, file):
 314         value, file = self.inner.read(file)
 315         return None if value == self.none_value else value, file
 316
 317     def write(self, file, item):
 318         if item == self.none_value:
 319             raise ValueError('none_value used')
 320         return self.inner.write(file, self.none_value if item is None else item)
 321
 322 address_type = ComposedType([
 323     ('services', StructType('<Q')),
 324     ('address', IPV6AddressType()),
 325     ('port', StructType('>H')),
 326 ])
 327
 328 tx_type = ComposedType([
 329     ('version', StructType('<I')),
 330     ('tx_ins', ListType(ComposedType([
 331         ('previous_output', PossiblyNone(dict(hash=0, index=2**32 - 1), ComposedType([
 332             ('hash', HashType()),
 333             ('index', StructType('<I')),
 334         ]))),
 335         ('script', VarStrType()),
 336         ('sequence', PossiblyNone(2**32 - 1, StructType('<I'))),
 337     ]))),
 338     ('tx_outs', ListType(ComposedType([
 339         ('value', StructType('<Q')),
 340         ('script', VarStrType()),
 341     ]))),
 342     ('lock_time', StructType('<I')),
 343 ])
 344
 345 block_header_type = ComposedType([
 346     ('version', StructType('<I')),
 347     ('previous_block', PossiblyNone(0, HashType())),
 348     ('merkle_root', HashType()),
 349     ('timestamp', StructType('<I')),
 350     ('target', FloatingIntegerType()),
 351     ('nonce', StructType('<I')),
 352 ])
 353
 354 block_type = ComposedType([
 355     ('header', block_header_type),
 356     ('txs', ListType(tx_type)),
 357 ])
 358
 359
 360 merkle_record_type = ComposedType([
 361     ('left', HashType()),
 362     ('right', HashType()),
 363 ])
 364
 365 def merkle_hash(tx_list):
 366     if not tx_list:
 367         return 0
 368     hash_list = map(tx_type.hash256, tx_list)
 369     while len(hash_list) > 1:
 370         hash_list = [merkle_record_type.hash256(dict(left=left, right=left if right is None else right))
 371             for left, right in zip(hash_list[::2], hash_list[1::2] + [None])]
 372     return hash_list[0]
 373
 374 def target_to_average_attempts(target):
 375     return 2**256//(target + 1)
 376
 377 # tx
 378
 379 def tx_get_sigop_count(tx):
 380     return sum(script.get_sigop_count(txin['script']) for txin in tx['tx_ins']) + sum(script.get_sigop_count(txout['script']) for txout in tx['tx_outs'])
 381
 382 # human addresses
 383
 384 human_address_type = ChecksummedType(ComposedType([
 385     ('version', StructType('<B')),
 386     ('pubkey_hash', ShortHashType()),
 387 ]))
 388
 389 pubkey_type = FixedStrType(65)
 390
 391 def pubkey_hash_to_address(pubkey_hash, net):
 392     return human_address_type.pack_base58(dict(version=net.BITCOIN_ADDRESS_VERSION, pubkey_hash=pubkey_hash))
 393
 394 def pubkey_to_address(pubkey, net):
 395     return pubkey_hash_to_address(pubkey_type.hash160(pubkey), net)
 396
 397 def address_to_pubkey_hash(address, net):
 398     x = human_address_type.unpack_base58(address)
 399     if x['version'] != net.BITCOIN_ADDRESS_VERSION:
 400         raise ValueError('address not for this net!')
 401     return x['pubkey_hash']
 402
 403 # transactions
 404
 405 def pubkey_to_script2(pubkey):
 406     return ('\x41' + pubkey_type.pack(pubkey)) + '\xac'
 407
 408 def pubkey_hash_to_script2(pubkey_hash):
 409     return '\x76\xa9' + ('\x14' + ShortHashType().pack(pubkey_hash)) + '\x88\xac'
 410
 411 # linked list tracker
 412
 413 class Tracker(object):
 414     def __init__(self):
 415         self.shares = {} # hash -> share
 416         self.ids = {} # hash -> (id, height)
 417         self.reverse_shares = {} # previous_hash -> set of share_hashes
 418
 419         self.heads = {} # head hash -> tail_hash
 420         self.tails = {} # tail hash -> set of head hashes
 421
 422         self.heights = {} # share_hash -> height_to, other_share_hash
 423
 424         self.id_generator = itertools.count()
 425         self.tails_by_id = {}
 426
 427         self.get_nth_parent_hash = skiplist.DistanceSkipList(self)
 428
 429     def add(self, share):
 430         assert not isinstance(share, (int, long, type(None)))
 431         if share.hash in self.shares:
 432             return # XXX raise exception?
 433
 434         parent_id = self.ids.get(share.previous_hash, None)
 435         children_ids = set(self.ids.get(share2_hash) for share2_hash in self.reverse_shares.get(share.hash, set()))
 436         infos = set()
 437         if parent_id is not None:
 438             infos.add((parent_id[0], parent_id[1] + 1))
 439         for child_id in children_ids:
 440             infos.add((child_id[0], child_id[1] - 1))
 441         if not infos:
 442             infos.add((self.id_generator.next(), 0))
 443         chosen = min(infos)
 444         self.ids[share.hash] = chosen
 445
 446         self.shares[share.hash] = share
 447         self.reverse_shares.setdefault(share.previous_hash, set()).add(share.hash)
 448
 449         if share.hash in self.tails:
 450             heads = self.tails.pop(share.hash)
 451         else:
 452             heads = set([share.hash])
 453
 454         if share.previous_hash in self.heads:
 455             tail = self.heads.pop(share.previous_hash)
 456         else:
 457             #dist, tail = self.get_height_and_last(share.previous_hash) # XXX this should be moved out of the critical area even though it shouldn't matter
 458             tail = share.previous_hash
 459             while tail in self.shares:
 460                 tail = self.shares[tail].previous_hash
 461
 462         self.tails.setdefault(tail, set()).update(heads)
 463         if share.previous_hash in self.tails[tail]:
 464             self.tails[tail].remove(share.previous_hash)
 465
 466         for head in heads:
 467             self.heads[head] = tail
 468
 469     def test(self):
 470         t = Tracker()
 471         for s in self.shares.itervalues():
 472             t.add(s)
 473
 474         assert self.shares == t.shares, (self.shares, t.shares)
 475         assert self.reverse_shares == t.reverse_shares, (self.reverse_shares, t.reverse_shares)
 476         assert self.heads == t.heads, (self.heads, t.heads)
 477         assert self.tails == t.tails, (self.tails, t.tails)
 478
 479     def remove(self, share_hash):
 480         assert isinstance(share_hash, (int, long, type(None)))
 481         if share_hash not in self.shares:
 482             raise KeyError()
 483         share = self.shares[share_hash]
 484         del share_hash
 485
 486         if share.hash in self.heads and share.previous_hash in self.tails:
 487             tail = self.heads.pop(share.hash)
 488             self.tails[tail].remove(share.hash)
 489             if not self.tails[share.previous_hash]:
 490                 self.tails.pop(share.previous_hash)
 491         elif share.hash in self.heads:
 492             tail = self.heads.pop(share.hash)
 493             self.tails[tail].remove(share.hash)
 494             if self.reverse_shares[share.previous_hash] != set([share.hash]):
 495                 pass # has sibling
 496             else:
 497                 self.tails[tail].add(share.previous_hash)
 498                 self.heads[share.previous_hash] = tail
 499         elif share.previous_hash in self.tails:
 500             raise NotImplementedError() # will break other things..
 501             heads = self.tails[share.previous_hash]
 502             if len(self.reverse_shares[share.previous_hash]) > 1:
 503                 raise NotImplementedError()
 504             else:
 505                 del self.tails[share.previous_hash]
 506                 for head in heads:
 507                     self.heads[head] = share.hash
 508                 self.tails[share.hash] = set(heads)
 509         else:
 510             raise NotImplementedError()
 511
 512         '''
 513         height, tail = self.get_height_and_last(share.hash)
 514
 515         if share.hash in self.heads:
 516             my_heads = set([share.hash])
 517         elif share.previous_hash in self.tails:
 518             my_heads = self.tails[share.previous_hash]
 519         else:
 520             some_heads = self.tails[tail]
 521             some_heads_heights = dict((that_head, self.get_height_and_last(that_head)[0]) for that_head in some_heads)
 522             my_heads = set(that_head for that_head in some_heads
 523                 if some_heads_heights[that_head] > height and
 524                 self.get_nth_parent_hash(that_head, some_heads_heights[that_head] - height) == share.hash)
 525
 526         if share.previous_hash != tail:
 527             self.heads[share.previous_hash] = tail
 528
 529         for head in my_heads:
 530             if head != share.hash:
 531                 self.heads[head] = share.hash
 532             else:
 533                 self.heads.pop(head)
 534
 535         if share.hash in self.heads:
 536             self.heads.pop(share.hash)
 537
 538
 539         self.tails[tail].difference_update(my_heads)
 540         if share.previous_hash != tail:
 541             self.tails[tail].add(share.previous_hash)
 542         if not self.tails[tail]:
 543             self.tails.pop(tail)
 544         if my_heads != set([share.hash]):
 545             self.tails[share.hash] = set(my_heads) - set([share.hash])
 546         '''
 547
 548         self.shares.pop(share.hash)
 549         self.reverse_shares[share.previous_hash].remove(share.hash)
 550         if not self.reverse_shares[share.previous_hash]:
 551             self.reverse_shares.pop(share.previous_hash)
 552
 553         assert self.test() is None
 554
 555     def get_height(self, share_hash):
 556         height, work, last = self.get_height_work_and_last(share_hash)
 557         return height
 558
 559     def get_work(self, share_hash):
 560         height, work, last = self.get_height_work_and_last(share_hash)
 561         return work
 562
 563     def get_height_and_last(self, share_hash):
 564         height, work, last = self.get_height_work_and_last(share_hash)
 565         return height, last
 566
 567     def get_height_work_and_last(self, share_hash):
 568         assert isinstance(share_hash, (int, long, type(None)))
 569         orig = share_hash
 570         height = 0
 571         work = 0
 572         updates = []
 573         while True:
 574             if share_hash is None or share_hash not in self.shares:
 575                 break
 576             updates.append((share_hash, height, work))
 577             if share_hash in self.heights:
 578                 height_inc, share_hash, work_inc = self.heights[share_hash]
 579             else:
 580                 height_inc, share_hash, work_inc = 1, self.shares[share_hash].previous_hash, target_to_average_attempts(self.shares[share_hash].target)
 581             height += height_inc
 582             work += work_inc
 583         for update_hash, height_then, work_then in updates:
 584             self.heights[update_hash] = height - height_then, share_hash, work - work_then
 585         return height, work, share_hash
 586
 587     def get_chain_known(self, start_hash):
 588         assert isinstance(start_hash, (int, long, type(None)))
 589         '''
 590         Chain starting with item of hash I{start_hash} of items that this Tracker contains
 591         '''
 592         item_hash_to_get = start_hash
 593         while True:
 594             if item_hash_to_get not in self.shares:
 595                 break
 596             share = self.shares[item_hash_to_get]
 597             assert not isinstance(share, long)
 598             yield share
 599             item_hash_to_get = share.previous_hash
 600
 601     def get_chain_to_root(self, start_hash, root=None):
 602         assert isinstance(start_hash, (int, long, type(None)))
 603         assert isinstance(root, (int, long, type(None)))
 604         '''
 605         Chain of hashes starting with share_hash of shares to the root (doesn't include root)
 606         Raises an error if one is missing
 607         '''
 608         share_hash_to_get = start_hash
 609         while share_hash_to_get != root:
 610             share = self.shares[share_hash_to_get]
 611             yield share
 612             share_hash_to_get = share.previous_hash
 613
 614     def get_best_hash(self):
 615         '''
 616         Returns hash of item with the most items in its chain
 617         '''
 618         if not self.heads:
 619             return None
 620         return max(self.heads, key=self.get_height_and_last)
 621
 622     def get_highest_height(self):
 623         return max(self.get_height_and_last(head)[0] for head in self.heads) if self.heads else 0
 624
 625 class FakeShare(object):
 626     def __init__(self, **kwargs):
 627         self.__dict__.update(kwargs)
 628
 629 if __name__ == '__main__':
 630
 631     t = Tracker()
 632
 633     for i in xrange(10000):
 634         t.add(FakeShare(hash=i, previous_hash=i - 1 if i > 0 else None))
 635
 636     #t.remove(99)
 637
 638     print "HEADS", t.heads
 639     print "TAILS", t.tails
 640
 641     import random
 642
 643     while False:
 644         print
 645         print '-'*30
 646         print
 647         t = Tracker()
 648         for i in xrange(random.randrange(100)):
 649             x = random.choice(list(t.shares) + [None])
 650             print i, '->', x
 651             t.add(FakeShare(i, x))
 652         while t.shares:
 653             x = random.choice(list(t.shares))
 654             print "DEL", x, t.__dict__
 655             try:
 656                 t.remove(x)
 657             except NotImplementedError:
 658                 print "aborted; not implemented"
 659         import time
 660         time.sleep(.1)
 661         print "HEADS", t.heads
 662         print "TAILS", t.tails
 663
 664     #for share_hash, share in sorted(t.shares.iteritems()):
 665     #    print share_hash, share.previous_hash, t.heads.get(share_hash), t.tails.get(share_hash)
 666
 667     #import sys;sys.exit()
 668
 669     print t.get_nth_parent_hash(9000, 5000)
 670     print t.get_nth_parent_hash(9001, 412)
 671     #print t.get_nth_parent_hash(90, 51)
 672
 673     for share_hash in sorted(t.shares):
 674         print str(share_hash).rjust(4),
 675         x = t.skips.get(share_hash, None)
 676         if x is not None:
 677             print str(x[0]).rjust(4),
 678             for a in x[1]:
 679                 print str(a).rjust(10),
 680         print
 681
 682 # network definitions
 683
 684 class Mainnet(object):
 685     BITCOIN_P2P_PREFIX = 'f9beb4d9'.decode('hex')
 686     BITCOIN_P2P_PORT = 8333
 687     BITCOIN_ADDRESS_VERSION = 0
 688
 689 class Testnet(object):
 690     BITCOIN_P2P_PREFIX = 'fabfb5da'.decode('hex')
 691     BITCOIN_P2P_PORT = 18333
 692     BITCOIN_ADDRESS_VERSION = 111