p2pool/bitcoin/data.py

   1 from __future__ import division
   2
   3 import struct
   4 import hashlib
   5 import warnings
   6
   7 from . import base58
   8 from p2pool.util import bases, expiring_dict, math
   9
  10 class EarlyEnd(Exception):
  11     pass
  12
  13 class LateEnd(Exception):
  14     pass
  15
  16 def read((data, pos), length):
  17     data2 = data[pos:pos + length]
  18     if len(data2) != length:
  19         raise EarlyEnd()
  20     return data2, (data, pos + length)
  21
  22 class Type(object):
  23     # the same data can have only one unpacked representation, but multiple packed binary representations
  24
  25     #def __hash__(self):
  26     #    return hash(tuple(self.__dict__.items()))
  27
  28     #def __eq__(self, other):
  29     #    if not isinstance(other, Type):
  30     #        raise NotImplementedError()
  31     #    return self.__dict__ == other.__dict__
  32
  33     def _unpack(self, data):
  34         obj, (data2, pos) = self.read((data, 0))
  35
  36         assert data2 is data
  37
  38         if pos != len(data):
  39             raise LateEnd()
  40
  41         return obj
  42
  43     def _pack(self, obj):
  44         f = self.write(None, obj)
  45
  46         res = []
  47         while f is not None:
  48             res.append(f[1])
  49             f = f[0]
  50         res.reverse()
  51         return ''.join(res)
  52
  53
  54     def unpack(self, data):
  55         obj = self._unpack(data)
  56
  57         if __debug__:
  58             data2 = self._pack(obj)
  59             if data2 != data:
  60                 assert self._unpack(data2) == obj
  61
  62         return obj
  63
  64     def pack(self, obj):
  65         data = self._pack(obj)
  66
  67         assert self._unpack(data) == obj
  68
  69         return data
  70
  71
  72     def pack_base58(self, obj):
  73         return base58.base58_encode(self.pack(obj))
  74
  75     def unpack_base58(self, base58_data):
  76         return self.unpack(base58.base58_decode(base58_data))
  77
  78
  79     def hash160(self, obj):
  80         return ShortHashType().unpack(hashlib.new('ripemd160', hashlib.sha256(self.pack(obj)).digest()).digest())
  81
  82     def hash256(self, obj):
  83         return HashType().unpack(hashlib.sha256(hashlib.sha256(self.pack(obj)).digest()).digest())
  84
  85 class VarIntType(Type):
  86     # redundancy doesn't matter here because bitcoin and p2pool both reencode before hashing
  87     def read(self, file):
  88         data, file = read(file, 1)
  89         first = ord(data)
  90         if first < 0xfd:
  91             return first, file
  92         elif first == 0xfd:
  93             desc, length = '<H', 2
  94         elif first == 0xfe:
  95             desc, length = '<I', 4
  96         elif first == 0xff:
  97             desc, length = '<Q', 8
  98         else:
  99             raise AssertionError()
 100         data, file = read(file, length)
 101         return struct.unpack(desc, data)[0], file
 102
 103     def write(self, file, item):
 104         if item < 0xfd:
 105             file = file, struct.pack('<B', item)
 106         elif item <= 0xffff:
 107             file = file, struct.pack('<BH', 0xfd, item)
 108         elif item <= 0xffffffff:
 109             file = file, struct.pack('<BI', 0xfe, item)
 110         elif item <= 0xffffffffffffffff:
 111             file = file, struct.pack('<BQ', 0xff, item)
 112         else:
 113             raise ValueError('int too large for varint')
 114         return file
 115
 116 class VarStrType(Type):
 117     _inner_size = VarIntType()
 118
 119     def read(self, file):
 120         length, file = self._inner_size.read(file)
 121         return read(file, length)
 122
 123     def write(self, file, item):
 124         return self._inner_size.write(file, len(item)), item
 125
 126 class FixedStrType(Type):
 127     def __init__(self, length):
 128         self.length = length
 129
 130     def read(self, file):
 131         return read(file, self.length)
 132
 133     def write(self, file, item):
 134         if len(item) != self.length:
 135             raise ValueError('incorrect length item!')
 136         return file, item
 137
 138 class EnumType(Type):
 139     def __init__(self, inner, values):
 140         self.inner = inner
 141         self.values = values
 142
 143         self.keys = {}
 144         for k, v in values.iteritems():
 145             if v in self.keys:
 146                 raise ValueError('duplicate value in values')
 147             self.keys[v] = k
 148
 149     def read(self, file):
 150         data, file = self.inner.read(file)
 151         return self.keys[data], file
 152
 153     def write(self, file, item):
 154         return self.inner.write(file, self.values[item])
 155
 156 class HashType(Type):
 157     def read(self, file):
 158         data, file = read(file, 256//8)
 159         return int(data[::-1].encode('hex'), 16), file
 160
 161     def write(self, file, item):
 162         if not 0 <= item < 2**256:
 163             raise ValueError("invalid hash value")
 164         if item != 0 and item < 2**160:
 165             warnings.warn("very low hash value - maybe you meant to use ShortHashType? %x" % (item,))
 166         return file, ('%064x' % (item,)).decode('hex')[::-1]
 167
 168 class ShortHashType(Type):
 169     def read(self, file):
 170         data, file = read(file, 160//8)
 171         return int(data[::-1].encode('hex'), 16), file
 172
 173     def write(self, file, item):
 174         if not 0 <= item < 2**160:
 175             raise ValueError("invalid hash value")
 176         return file, ('%040x' % (item,)).decode('hex')[::-1]
 177
 178 class ListType(Type):
 179     _inner_size = VarIntType()
 180
 181     def __init__(self, type):
 182         self.type = type
 183
 184     def read(self, file):
 185         length, file = self._inner_size.read(file)
 186         res = []
 187         for i in xrange(length):
 188             item, file = self.type.read(file)
 189             res.append(item)
 190         return res, file
 191
 192     def write(self, file, item):
 193         file = self._inner_size.write(file, len(item))
 194         for subitem in item:
 195             file = self.type.write(file, subitem)
 196         return file
 197
 198 class StructType(Type):
 199     def __init__(self, desc):
 200         self.desc = desc
 201         self.length = struct.calcsize(self.desc)
 202
 203     def read(self, file):
 204         data, file = read(file, self.length)
 205         res, = struct.unpack(self.desc, data)
 206         return res, file
 207
 208     def write(self, file, item):
 209         data = struct.pack(self.desc, item)
 210         if struct.unpack(self.desc, data)[0] != item:
 211             # special test because struct doesn't error on some overflows
 212             raise ValueError("item didn't survive pack cycle (%r)" % (item,))
 213         return file, data
 214
 215 class IPV6AddressType(Type):
 216     def read(self, file):
 217         data, file = read(file, 16)
 218         if data[:12] != '00000000000000000000ffff'.decode('hex'):
 219             raise ValueError("ipv6 addresses not supported yet")
 220         return '.'.join(str(ord(x)) for x in data[12:]), file
 221
 222     def write(self, file, item):
 223         bits = map(int, item.split('.'))
 224         if len(bits) != 4:
 225             raise ValueError("invalid address: %r" % (bits,))
 226         data = '00000000000000000000ffff'.decode('hex') + ''.join(chr(x) for x in bits)
 227         assert len(data) == 16, len(data)
 228         return file, data
 229
 230 class ComposedType(Type):
 231     def __init__(self, fields):
 232         self.fields = fields
 233
 234     def read(self, file):
 235         item = {}
 236         for key, type_ in self.fields:
 237             item[key], file = type_.read(file)
 238         return item, file
 239
 240     def write(self, file, item):
 241         for key, type_ in self.fields:
 242             file = type_.write(file, item[key])
 243         return file
 244
 245 class ChecksummedType(Type):
 246     def __init__(self, inner):
 247         self.inner = inner
 248
 249     def read(self, file):
 250         obj, file = self.inner.read(file)
 251         data = self.inner.pack(obj)
 252
 253         if file.read(4) != hashlib.sha256(hashlib.sha256(data).digest()).digest()[:4]:
 254             raise ValueError("invalid checksum")
 255
 256         return obj, file
 257
 258     def write(self, file, item):
 259         data = self.inner.pack(item)
 260         file = file, data
 261         return file, hashlib.sha256(hashlib.sha256(data).digest()).digest()[:4]
 262
 263 class FloatingIntegerType(Type):
 264     # redundancy doesn't matter here because bitcoin checks binary bits against its own computed bits
 265     # so it will always be encoded 'normally' in blocks (they way bitcoin does it)
 266     _inner = StructType("<I")
 267
 268     def read(self, file):
 269         bits, file = self._inner.read(file)
 270         target = self._bits_to_target(bits)
 271         if __debug__:
 272             if self._target_to_bits(target) != bits:
 273                 raise ValueError("bits in non-canonical form")
 274         return target, file
 275
 276     def write(self, file, item):
 277         return self._inner.write(file, self._target_to_bits(item))
 278
 279     def truncate_to(self, x):
 280         return self._bits_to_target(self._target_to_bits(x, _check=False))
 281
 282     def _bits_to_target(self, bits2):
 283         target = math.shift_left(bits2 & 0x00ffffff, 8 * ((bits2 >> 24) - 3))
 284         assert target == self._bits_to_target1(struct.pack("<I", bits2))
 285         assert self._target_to_bits(target, _check=False) == bits2
 286         return target
 287
 288     def _bits_to_target1(self, bits):
 289         bits = bits[::-1]
 290         length = ord(bits[0])
 291         return bases.string_to_natural((bits[1:] + "\0"*length)[:length])
 292
 293     def _target_to_bits(self, target, _check=True):
 294         n = bases.natural_to_string(target)
 295         if n and ord(n[0]) >= 128:
 296             n = "\x00" + n
 297         bits2 = (chr(len(n)) + (n + 3*chr(0))[:3])[::-1]
 298         bits = struct.unpack("<I", bits2)[0]
 299         if _check:
 300             if self._bits_to_target(bits) != target:
 301                 raise ValueError(repr((target, self._bits_to_target(bits, _check=False))))
 302         return bits
 303
 304 class PossiblyNone(Type):
 305     def __init__(self, none_value, inner):
 306         self.none_value = none_value
 307         self.inner = inner
 308
 309     def read(self, file):
 310         value, file = self.inner.read(file)
 311         return None if value == self.none_value else value, file
 312
 313     def write(self, file, item):
 314         if item == self.none_value:
 315             raise ValueError("none_value used")
 316         return self.inner.write(file, self.none_value if item is None else item)
 317
 318 address_type = ComposedType([
 319     ('services', StructType('<Q')),
 320     ('address', IPV6AddressType()),
 321     ('port', StructType('>H')),
 322 ])
 323
 324 tx_type = ComposedType([
 325     ('version', StructType('<I')),
 326     ('tx_ins', ListType(ComposedType([
 327         ('previous_output', PossiblyNone(dict(hash=0, index=2**32 - 1), ComposedType([
 328             ('hash', HashType()),
 329             ('index', StructType('<I')),
 330         ]))),
 331         ('script', VarStrType()),
 332         ('sequence', PossiblyNone(2**32 - 1, StructType('<I'))),
 333     ]))),
 334     ('tx_outs', ListType(ComposedType([
 335         ('value', StructType('<Q')),
 336         ('script', VarStrType()),
 337     ]))),
 338     ('lock_time', StructType('<I')),
 339 ])
 340
 341 block_header_type = ComposedType([
 342     ('version', StructType('<I')),
 343     ('previous_block', PossiblyNone(0, HashType())),
 344     ('merkle_root', HashType()),
 345     ('timestamp', StructType('<I')),
 346     ('target', FloatingIntegerType()),
 347     ('nonce', StructType('<I')),
 348 ])
 349
 350 block_type = ComposedType([
 351     ('header', block_header_type),
 352     ('txs', ListType(tx_type)),
 353 ])
 354
 355
 356 merkle_record_type = ComposedType([
 357     ('left', HashType()),
 358     ('right', HashType()),
 359 ])
 360
 361 def merkle_hash(tx_list):
 362     if not tx_list:
 363         return 0
 364     hash_list = map(tx_type.hash256, tx_list)
 365     while len(hash_list) > 1:
 366         hash_list = [merkle_record_type.hash256(dict(left=left, right=left if right is None else right))
 367             for left, right in zip(hash_list[::2], hash_list[1::2] + [None])]
 368     return hash_list[0]
 369
 370 def target_to_average_attempts(target):
 371     return 2**256//(target + 1)
 372
 373 # human addresses
 374
 375 human_address_type = ChecksummedType(ComposedType([
 376     ('version', StructType("<B")),
 377     ('pubkey_hash', ShortHashType()),
 378 ]))
 379
 380 pubkey_type = FixedStrType(65)
 381
 382 def pubkey_hash_to_address(pubkey_hash, net):
 383     return human_address_type.pack_base58(dict(version=net.BITCOIN_ADDRESS_VERSION, pubkey_hash=pubkey_hash))
 384
 385 def pubkey_to_address(pubkey, net):
 386     return pubkey_hash_to_address(pubkey_type.hash160(pubkey), net)
 387
 388 def address_to_pubkey_hash(address, net):
 389     x = human_address_type.unpack_base58(address)
 390     if x['version'] != net.BITCOIN_ADDRESS_VERSION:
 391         raise ValueError('address not for this net!')
 392     return x['pubkey_hash']
 393
 394 # linked list tracker
 395
 396 class Tracker(object):
 397     def __init__(self):
 398         self.shares = {} # hash -> share
 399         self.reverse_shares = {} # previous_hash -> set of share_hashes
 400
 401         self.heads = {} # head hash -> tail_hash
 402         self.tails = {} # tail hash -> set of head hashes
 403         self.heights = {} # share_hash -> height_to, other_share_hash
 404
 405     def add(self, share):
 406         if share.hash in self.shares:
 407             return # XXX raise exception?
 408
 409         self.shares[share.hash] = share
 410         self.reverse_shares.setdefault(share.previous_hash, set()).add(share.hash)
 411
 412         if share.hash in self.tails:
 413             heads = self.tails.pop(share.hash)
 414         else:
 415             heads = set([share.hash])
 416
 417         if share.previous_hash in self.heads:
 418             tail = self.heads.pop(share.previous_hash)
 419         else:
 420             tail = share.previous_hash
 421
 422         self.tails.setdefault(tail, set()).update(heads)
 423         if share.previous_hash in self.tails[tail]:
 424             self.tails[tail].remove(share.previous_hash)
 425
 426         for head in heads:
 427             self.heads[head] = tail
 428
 429     def get_height_and_last(self, share_hash):
 430         orig = share_hash
 431         height = 0
 432         updates = []
 433         while True:
 434             if share_hash is None or share_hash not in self.shares:
 435                 break
 436             updates.append((share_hash, height))
 437             if share_hash in self.heights:
 438                 height_inc, share_hash = self.heights[share_hash]
 439             else:
 440                 height_inc, share_hash = 1, self.shares[share_hash].previous_hash
 441             height += height_inc
 442         for update_hash, height_then in updates:
 443             self.heights[update_hash] = height - height_then, share_hash
 444         assert (height, share_hash) == self.get_height_and_last2(orig), ((height, share_hash), self.get_height_and_last2(orig))
 445         return height, share_hash
 446
 447     def get_height_and_last2(self, share_hash):
 448         height = 0
 449         while True:
 450             if share_hash not in self.shares:
 451                 break
 452             share_hash = self.shares[share_hash].previous_hash
 453             height += 1
 454         return height, share_hash
 455
 456     def get_chain_known(self, start_hash):
 457         '''
 458         Chain starting with item of hash I{start_hash} of items that this Tracker contains
 459         '''
 460         item_hash_to_get = start_hash
 461         while True:
 462             if item_hash_to_get not in self.shares:
 463                 break
 464             share = self.shares[item_hash_to_get]
 465             assert not isinstance(share, long)
 466             yield share
 467             item_hash_to_get = share.previous_hash
 468
 469     def get_chain_to_root(self, start_hash, root=None):
 470         '''
 471         Chain of hashes starting with share_hash of shares to the root (doesn't include root)
 472         Raises an error if one is missing
 473         '''
 474         share_hash_to_get = start_hash
 475         while share_hash_to_get != root:
 476             share = self.shares[share_hash_to_get]
 477             yield share
 478             share_hash_to_get = share.previous_hash
 479
 480     def get_best_hash(self):
 481         '''
 482         Returns hash of item with the most items in its chain
 483         '''
 484         if not self.heads:
 485             return None
 486         return max(self.heads, key=self.get_height_and_last)
 487
 488 # network definitions
 489
 490 class Mainnet(object):
 491     BITCOIN_P2P_PREFIX = 'f9beb4d9'.decode('hex')
 492     BITCOIN_P2P_PORT = 8333
 493     BITCOIN_ADDRESS_VERSION = 0
 494
 495 class Testnet(object):
 496     BITCOIN_P2P_PREFIX = 'fabfb5da'.decode('hex')
 497     BITCOIN_P2P_PORT = 18333
 498     BITCOIN_ADDRESS_VERSION = 111