p2pool/bitcoin/data.py

   1 import struct
   2 import StringIO
   3 import hashlib
   4
   5 class EarlyEnd(Exception):
   6     pass
   7
   8 class LateEnd(Exception):
   9     pass
  10
  11 class Type(object):
  12     # the same data can have only one unpacked representation, but multiple packed binary representations
  13
  14     def _unpack(self, data):
  15         f = StringIO.StringIO(data)
  16
  17         obj = self.read(f)
  18
  19         if f.tell() != len(data):
  20             raise LateEnd('underread ' + repr((self, data)))
  21
  22         return obj
  23
  24     def unpack(self, data):
  25         obj = self._unpack(data)
  26         assert self._unpack(self._pack(obj)) == obj
  27         return obj
  28
  29     def _pack(self, obj):
  30         f = StringIO.StringIO()
  31
  32         self.write(f, obj)
  33
  34         data = f.getvalue()
  35
  36         return data
  37
  38     def pack(self, obj):
  39         data = self._pack(obj)
  40         assert self._unpack(data) == obj
  41         return data
  42
  43 class VarIntType(Type):
  44     def read(self, file):
  45         data = file.read(1)
  46         if len(data) != 1:
  47             raise EarlyEnd()
  48         first, = struct.unpack('<B', data)
  49         if first == 0xff: desc = '<Q'
  50         elif first == 0xfe: desc = '<I'
  51         elif first == 0xfd: desc = '<H'
  52         else: return first
  53         length = struct.calcsize(desc)
  54         data = file.read(length)
  55         if len(data) != length:
  56             raise EarlyEnd()
  57         return struct.unpack(desc, data)[0]
  58
  59     def write(self, file, item):
  60         if item < 0xfd:
  61             file.write(struct.pack('<B', item))
  62         elif item <= 0xffff:
  63             file.write(struct.pack('<BH', 0xfd, item))
  64         elif item <= 0xffffffff:
  65             file.write(struct.pack('<BI', 0xfe, item))
  66         elif item <= 0xffffffffffffffff:
  67             file.write(struct.pack('<BQ', 0xff, item))
  68         else:
  69             raise ValueError('int too large for varint')
  70
  71 class VarStrType(Type):
  72     def read(self, file):
  73         length = VarIntType().read(file)
  74         res = file.read(length)
  75         if len(res) != length:
  76             raise EarlyEnd('var str not long enough %r' % ((length, len(res), res),))
  77         return res
  78
  79     def write(self, file, item):
  80         VarIntType().write(file, len(item))
  81         file.write(item)
  82
  83 class FixedStrType(Type):
  84     def __init__(self, length):
  85         self.length = length
  86
  87     def read(self, file):
  88         res = file.read(self.length)
  89         if len(res) != self.length:
  90             raise EarlyEnd('early EOF!')
  91         return res
  92
  93     def write(self, file, item):
  94         if len(item) != self.length:
  95             raise ValueError('incorrect length!')
  96         file.write(item)
  97
  98 class EnumType(Type):
  99     def __init__(self, inner, values):
 100         self.inner = inner
 101         self.values = values
 102
 103         self.keys = {}
 104         for k, v in values.iteritems():
 105             if v in self.keys:
 106                 raise ValueError('duplicate value in values')
 107             self.keys[v] = k
 108
 109     def read(self, file):
 110         return self.keys[self.inner.read(file)]
 111
 112     def write(self, file, item):
 113         self.inner.write(file, self.values[item])
 114
 115 class HashType(Type):
 116     def read(self, file):
 117         data = file.read(256//8)
 118         if len(data) != 256//8:
 119             raise EarlyEnd('incorrect length!')
 120         return int(data[::-1].encode('hex'), 16)
 121
 122     def write(self, file, item):
 123         file.write(('%064x' % (item,)).decode('hex')[::-1])
 124
 125 class ShortHashType(Type):
 126     def read(self, file):
 127         data = file.read(160//8)
 128         if len(data) != 160//8:
 129             raise EarlyEnd('incorrect length!')
 130         return int(data[::-1].encode('hex'), 16)
 131
 132     def write(self, file, item):
 133         file.write(('%020x' % (item,)).decode('hex')[::-1])
 134
 135 class ListType(Type):
 136     def __init__(self, type):
 137         self.type = type
 138
 139     def read(self, file):
 140         length = VarIntType().read(file)
 141         return [self.type.read(file) for i in xrange(length)]
 142
 143     def write(self, file, item):
 144         VarIntType().write(file, len(item))
 145         for subitem in item:
 146             self.type.write(file, subitem)
 147
 148 class StructType(Type):
 149     def __init__(self, desc):
 150         self.desc = desc
 151         self.length = struct.calcsize(self.desc)
 152
 153     def read(self, file):
 154         data = file.read(self.length)
 155         if len(data) != self.length:
 156             raise EarlyEnd()
 157         res, = struct.unpack(self.desc, data)
 158         return res
 159
 160     def write(self, file, item):
 161         data = struct.pack(self.desc, item)
 162         if struct.unpack(self.desc, data)[0] != item:
 163             # special test because struct doesn't error on some overflows
 164             raise ValueError("item didn't survive pack cycle (%r)" % (item,))
 165         file.write(data)
 166
 167 class IPV6AddressType(Type):
 168     def read(self, file):
 169         data = file.read(16)
 170         if len(data) != 16:
 171             raise EarlyEnd()
 172         if data[:12] != '00000000000000000000ffff'.decode('hex'):
 173             raise ValueError("ipv6 addresses not supported yet")
 174         return '::ffff:' + '.'.join(str(ord(x)) for x in data[12:])
 175
 176     def write(self, file, item):
 177         prefix = '::ffff:'
 178         if not item.startswith(prefix):
 179             raise ValueError("ipv6 addresses not supported yet")
 180         item = item[len(prefix):]
 181         bits = map(int, item.split('.'))
 182         if len(bits) != 4:
 183             raise ValueError("invalid address: %r" % (bits,))
 184         data = '00000000000000000000ffff'.decode('hex') + ''.join(chr(x) for x in bits)
 185         assert len(data) == 16, len(data)
 186         file.write(data)
 187
 188 class ComposedType(Type):
 189     def __init__(self, fields):
 190         self.fields = fields
 191
 192     def read(self, file):
 193         item = {}
 194         for key, type_ in self.fields:
 195             item[key] = type_.read(file)
 196         return item
 197
 198     def write(self, file, item):
 199         for key, type_ in self.fields:
 200             type_.write(file, item[key])
 201
 202 address_type = ComposedType([
 203     ('services', StructType('<Q')),
 204     ('address', IPV6AddressType()),
 205     ('port', StructType('>H')),
 206 ])
 207
 208 tx_type = ComposedType([
 209     ('version', StructType('<I')),
 210     ('tx_ins', ListType(ComposedType([
 211         ('previous_output', ComposedType([
 212             ('hash', HashType()),
 213             ('index', StructType('<I')),
 214         ])),
 215         ('script', VarStrType()),
 216         ('sequence', StructType('<I')),
 217     ]))),
 218     ('tx_outs', ListType(ComposedType([
 219         ('value', StructType('<Q')),
 220         ('script', VarStrType()),
 221     ]))),
 222     ('lock_time', StructType('<I')),
 223 ])
 224
 225 block_header_type = ComposedType([
 226     ('version', StructType('<I')),
 227     ('previous_block', HashType()),
 228     ('merkle_root', HashType()),
 229     ('timestamp', StructType('<I')),
 230     ('bits', StructType('<I')),
 231     ('nonce', StructType('<I')),
 232 ])
 233
 234 block_type = ComposedType([
 235     ('header', block_header_type),
 236     ('txs', ListType(tx_type)),
 237 ])
 238
 239 def doublesha(data):
 240     return HashType().unpack(hashlib.sha256(hashlib.sha256(data).digest()).digest())
 241
 242 def ripemdsha(data):
 243     return ShortHashType().unpack(hashlib.new('ripemd160', hashlib.sha256(data).digest()).digest())
 244
 245 merkle_record_type = ComposedType([
 246     ('left', HashType()),
 247     ('right', HashType()),
 248 ])
 249
 250 def merkle_hash(tx_list):
 251     hash_list = [doublesha(tx_type.pack(tx)) for tx in tx_list]
 252     while len(hash_list) > 1:
 253         hash_list = [doublesha(merkle_record_type.pack(dict(left=left, right=left if right is None else right)))
 254             for left, right in zip(hash_list[::2], hash_list[1::2] + [None])]
 255     return hash_list[0]
 256
 257 def tx_hash(tx):
 258     return doublesha(tx_type.pack(tx))
 259
 260 def block_hash(header):
 261     return doublesha(block_header_type.pack(header))
 262
 263 class EarlyEnd(Exception):
 264     pass
 265
 266 class LateEnd(Exception):
 267     pass
 268
 269 class Type(object):
 270     # the same data can have only one unpacked representation, but multiple packed binary representations
 271
 272     def _unpack(self, data):
 273         f = StringIO.StringIO(data)
 274
 275         obj = self.read(f)
 276
 277         if f.tell() != len(data):
 278             raise LateEnd('underread ' + repr((self, data)))
 279
 280         return obj
 281
 282     def unpack(self, data):
 283         obj = self._unpack(data)
 284         assert self._unpack(self._pack(obj)) == obj
 285         return obj
 286
 287     def _pack(self, obj):
 288         f = StringIO.StringIO()
 289
 290         self.write(f, obj)
 291
 292         data = f.getvalue()
 293
 294         return data
 295
 296     def pack(self, obj):
 297         data = self._pack(obj)
 298         assert self._unpack(data) == obj
 299         return data
 300
 301 class VarIntType(Type):
 302     def read(self, file):
 303         data = file.read(1)
 304         if len(data) != 1:
 305             raise EarlyEnd()
 306         first, = struct.unpack('<B', data)
 307         if first == 0xff: desc = '<Q'
 308         elif first == 0xfe: desc = '<I'
 309         elif first == 0xfd: desc = '<H'
 310         else: return first
 311         length = struct.calcsize(desc)
 312         data = file.read(length)
 313         if len(data) != length:
 314             raise EarlyEnd()
 315         return struct.unpack(desc, data)[0]
 316
 317     def write(self, file, item):
 318         if item < 0xfd:
 319             file.write(struct.pack('<B', item))
 320         elif item <= 0xffff:
 321             file.write(struct.pack('<BH', 0xfd, item))
 322         elif item <= 0xffffffff:
 323             file.write(struct.pack('<BI', 0xfe, item))
 324         elif item <= 0xffffffffffffffff:
 325             file.write(struct.pack('<BQ', 0xff, item))
 326         else:
 327             raise ValueError('int too large for varint')
 328
 329 class VarStrType(Type):
 330     def read(self, file):
 331         length = VarIntType().read(file)
 332         res = file.read(length)
 333         if len(res) != length:
 334             raise EarlyEnd('var str not long enough %r' % ((length, len(res), res),))
 335         return res
 336
 337     def write(self, file, item):
 338         VarIntType().write(file, len(item))
 339         file.write(item)
 340
 341 class FixedStrType(Type):
 342     def __init__(self, length):
 343         self.length = length
 344
 345     def read(self, file):
 346         res = file.read(self.length)
 347         if len(res) != self.length:
 348             raise EarlyEnd('early EOF!')
 349         return res
 350
 351     def write(self, file, item):
 352         if len(item) != self.length:
 353             raise ValueError('incorrect length!')
 354         file.write(item)
 355
 356 class EnumType(Type):
 357     def __init__(self, inner, values):
 358         self.inner = inner
 359         self.values = values
 360
 361         self.keys = {}
 362         for k, v in values.iteritems():
 363             if v in self.keys:
 364                 raise ValueError('duplicate value in values')
 365             self.keys[v] = k
 366
 367     def read(self, file):
 368         return self.keys[self.inner.read(file)]
 369
 370     def write(self, file, item):
 371         self.inner.write(file, self.values[item])
 372
 373 class HashType(Type):
 374     def read(self, file):
 375         data = file.read(256//8)
 376         if len(data) != 256//8:
 377             raise EarlyEnd('incorrect length!')
 378         return int(data[::-1].encode('hex'), 16)
 379
 380     def write(self, file, item):
 381         file.write(('%064x' % (item,)).decode('hex')[::-1])
 382
 383 class ShortHashType(Type):
 384     def read(self, file):
 385         data = file.read(160//8)
 386         if len(data) != 160//8:
 387             raise EarlyEnd('incorrect length!')
 388         return int(data[::-1].encode('hex'), 16)
 389
 390     def write(self, file, item):
 391         file.write(('%020x' % (item,)).decode('hex')[::-1])
 392
 393 class ListType(Type):
 394     def __init__(self, type):
 395         self.type = type
 396
 397     def read(self, file):
 398         length = VarIntType().read(file)
 399         return [self.type.read(file) for i in xrange(length)]
 400
 401     def write(self, file, item):
 402         VarIntType().write(file, len(item))
 403         for subitem in item:
 404             self.type.write(file, subitem)
 405
 406 class StructType(Type):
 407     def __init__(self, desc):
 408         self.desc = desc
 409         self.length = struct.calcsize(self.desc)
 410
 411     def read(self, file):
 412         data = file.read(self.length)
 413         if len(data) != self.length:
 414             raise EarlyEnd()
 415         res, = struct.unpack(self.desc, data)
 416         return res
 417
 418     def write(self, file, item):
 419         data = struct.pack(self.desc, item)
 420         if struct.unpack(self.desc, data)[0] != item:
 421             # special test because struct doesn't error on some overflows
 422             raise ValueError("item didn't survive pack cycle (%r)" % (item,))
 423         file.write(data)
 424
 425 class IPV6AddressType(Type):
 426     def read(self, file):
 427         data = file.read(16)
 428         if len(data) != 16:
 429             raise EarlyEnd()
 430         if data[:12] != '00000000000000000000ffff'.decode('hex'):
 431             raise ValueError("ipv6 addresses not supported yet")
 432         return '::ffff:' + '.'.join(str(ord(x)) for x in data[12:])
 433
 434     def write(self, file, item):
 435         prefix = '::ffff:'
 436         if not item.startswith(prefix):
 437             raise ValueError("ipv6 addresses not supported yet")
 438         item = item[len(prefix):]
 439         bits = map(int, item.split('.'))
 440         if len(bits) != 4:
 441             raise ValueError("invalid address: %r" % (bits,))
 442         data = '00000000000000000000ffff'.decode('hex') + ''.join(chr(x) for x in bits)
 443         assert len(data) == 16, len(data)
 444         file.write(data)
 445
 446 class ComposedType(Type):
 447     def __init__(self, fields):
 448         self.fields = fields
 449
 450     def read(self, file):
 451         item = {}
 452         for key, type_ in self.fields:
 453             item[key] = type_.read(file)
 454         return item
 455
 456     def write(self, file, item):
 457         for key, type_ in self.fields:
 458             type_.write(file, item[key])
 459
 460 address_type = ComposedType([
 461     ('services', StructType('<Q')),
 462     ('address', IPV6AddressType()),
 463     ('port', StructType('>H')),
 464 ])
 465
 466 tx_type = ComposedType([
 467     ('version', StructType('<I')),
 468     ('tx_ins', ListType(ComposedType([
 469         ('previous_output', ComposedType([
 470             ('hash', HashType()),
 471             ('index', StructType('<I')),
 472         ])),
 473         ('script', VarStrType()),
 474         ('sequence', StructType('<I')),
 475     ]))),
 476     ('tx_outs', ListType(ComposedType([
 477         ('value', StructType('<Q')),
 478         ('script', VarStrType()),
 479     ]))),
 480     ('lock_time', StructType('<I')),
 481 ])
 482
 483 block_header_type = ComposedType([
 484     ('version', StructType('<I')),
 485     ('previous_block', HashType()),
 486     ('merkle_root', HashType()),
 487     ('timestamp', StructType('<I')),
 488     ('bits', StructType('<I')),
 489     ('nonce', StructType('<I')),
 490 ])
 491
 492 block_type = ComposedType([
 493     ('header', block_header_type),
 494     ('txs', ListType(tx_type)),
 495 ])
 496
 497 def doublesha(data):
 498     return HashType().unpack(hashlib.sha256(hashlib.sha256(data).digest()).digest())
 499
 500 def ripemdsha(data):
 501     return ShortHashType().unpack(hashlib.new('ripemd160', hashlib.sha256(data).digest()).digest())
 502
 503 merkle_record_type = ComposedType([
 504     ('left', HashType()),
 505     ('right', HashType()),
 506 ])
 507
 508 def merkle_hash(tx_list):
 509     hash_list = [doublesha(tx_type.pack(tx)) for tx in tx_list]
 510     while len(hash_list) > 1:
 511         hash_list = [doublesha(merkle_record_type.pack(dict(left=left, right=left if right is None else right)))
 512             for left, right in zip(hash_list[::2], hash_list[1::2] + [None])]
 513     return hash_list[0]
 514
 515 def tx_hash(tx):
 516     return doublesha(tx_type.pack(tx))
 517
 518 def block_hash(header):
 519     return doublesha(block_header_type.pack(header))
 520
 521 def bits_to_target(bits):
 522     return (bits & 0x00ffffff) * 2 ** (8 * ((bits >> 24) - 3))
 523
 524 def target_to_average_attempts(target):
 525     return 2**256//(target + 1)