1 from __future__ import division
8 from p2pool.util import bases, math
10 class EarlyEnd(Exception):
13 class LateEnd(Exception):
16 def read((data, pos), length):
17 data2 = data[pos:pos + length]
18 if len(data2) != length:
20 return data2, (data, pos + length)
23 # the same data can have only one unpacked representation, but multiple packed binary representations
26 # return hash(tuple(self.__dict__.items()))
28 #def __eq__(self, other):
29 # if not isinstance(other, Type):
30 # raise NotImplementedError()
31 # return self.__dict__ == other.__dict__
33 def _unpack(self, data):
34 obj, (data2, pos) = self.read((data, 0))
44 f = self.write(None, obj)
54 def unpack(self, data):
55 obj = self._unpack(data)
58 data2 = self._pack(obj)
60 assert self._unpack(data2) == obj
65 data = self._pack(obj)
67 assert self._unpack(data) == obj
72 def pack_base58(self, obj):
73 return base58.base58_encode(self.pack(obj))
75 def unpack_base58(self, base58_data):
76 return self.unpack(base58.base58_decode(base58_data))
79 def hash160(self, obj):
80 return ShortHashType().unpack(hashlib.new('ripemd160', hashlib.sha256(self.pack(obj)).digest()).digest())
82 def hash256(self, obj):
83 return HashType().unpack(hashlib.sha256(hashlib.sha256(self.pack(obj)).digest()).digest())
85 class VarIntType(Type):
86 # redundancy doesn't matter here because bitcoin and p2pool both reencode before hashing
88 data, file = read(file, 1)
93 desc, length = '<H', 2
95 desc, length = '<I', 4
97 desc, length = '<Q', 8
99 raise AssertionError()
100 data, file = read(file, length)
101 return struct.unpack(desc, data)[0], file
103 def write(self, file, item):
105 file = file, struct.pack('<B', item)
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)
113 raise ValueError('int too large for varint')
116 class VarStrType(Type):
117 _inner_size = VarIntType()
119 def read(self, file):
120 length, file = self._inner_size.read(file)
121 return read(file, length)
123 def write(self, file, item):
124 return self._inner_size.write(file, len(item)), item
126 class FixedStrType(Type):
127 def __init__(self, length):
130 def read(self, file):
131 return read(file, self.length)
133 def write(self, file, item):
134 if len(item) != self.length:
135 raise ValueError('incorrect length item!')
138 class EnumType(Type):
139 def __init__(self, inner, values):
144 for k, v in values.iteritems():
146 raise ValueError('duplicate value in values')
149 def read(self, file):
150 data, file = self.inner.read(file)
151 return self.keys[data], file
153 def write(self, file, item):
154 return self.inner.write(file, self.values[item])
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
161 def write(self, file, item):
162 if not 0 <= item < 2**256:
163 raise ValueError('invalid hash value - %r' % (item,))
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]
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
173 def write(self, file, item):
174 if not 0 <= item < 2**160:
175 raise ValueError('invalid hash value - %r' % (item,))
176 return file, ('%040x' % (item,)).decode('hex')[::-1]
178 class ListType(Type):
179 _inner_size = VarIntType()
181 def __init__(self, type):
184 def read(self, file):
185 length, file = self._inner_size.read(file)
187 for i in xrange(length):
188 item, file = self.type.read(file)
192 def write(self, file, item):
193 file = self._inner_size.write(file, len(item))
195 file = self.type.write(file, subitem)
198 class StructType(Type):
199 def __init__(self, desc):
201 self.length = struct.calcsize(self.desc)
203 def read(self, file):
204 data, file = read(file, self.length)
205 res, = struct.unpack(self.desc, data)
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,))
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
222 def write(self, file, item):
223 bits = map(int, item.split('.'))
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)
230 class ComposedType(Type):
231 def __init__(self, fields):
234 def read(self, file):
236 for key, type_ in self.fields:
237 item[key], file = type_.read(file)
240 def write(self, file, item):
241 for key, type_ in self.fields:
242 file = type_.write(file, item[key])
245 class ChecksummedType(Type):
246 def __init__(self, inner):
249 def read(self, file):
250 obj, file = self.inner.read(file)
251 data = self.inner.pack(obj)
253 if file.read(4) != hashlib.sha256(hashlib.sha256(data).digest()).digest()[:4]:
254 raise ValueError('invalid checksum')
258 def write(self, file, item):
259 data = self.inner.pack(item)
261 return file, hashlib.sha256(hashlib.sha256(data).digest()).digest()[:4]
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')
268 def read(self, file):
269 bits, file = self._inner.read(file)
270 target = self._bits_to_target(bits)
272 if self._target_to_bits(target) != bits:
273 raise ValueError('bits in non-canonical form')
276 def write(self, file, item):
277 return self._inner.write(file, self._target_to_bits(item))
279 def truncate_to(self, x):
280 return self._bits_to_target(self._target_to_bits(x, _check=False))
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
288 def _bits_to_target1(self, bits):
290 length = ord(bits[0])
291 return bases.string_to_natural((bits[1:] + '\0'*length)[:length])
293 def _target_to_bits(self, target, _check=True):
294 n = bases.natural_to_string(target)
295 if n and ord(n[0]) >= 128:
297 bits2 = (chr(len(n)) + (n + 3*chr(0))[:3])[::-1]
298 bits = struct.unpack('<I', bits2)[0]
300 if self._bits_to_target(bits) != target:
301 raise ValueError(repr((target, self._bits_to_target(bits, _check=False))))
304 class PossiblyNone(Type):
305 def __init__(self, none_value, inner):
306 self.none_value = none_value
309 def read(self, file):
310 value, file = self.inner.read(file)
311 return None if value == self.none_value else value, file
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)
318 address_type = ComposedType([
319 ('services', StructType('<Q')),
320 ('address', IPV6AddressType()),
321 ('port', StructType('>H')),
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')),
331 ('script', VarStrType()),
332 ('sequence', PossiblyNone(2**32 - 1, StructType('<I'))),
334 ('tx_outs', ListType(ComposedType([
335 ('value', StructType('<Q')),
336 ('script', VarStrType()),
338 ('lock_time', StructType('<I')),
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')),
350 block_type = ComposedType([
351 ('header', block_header_type),
352 ('txs', ListType(tx_type)),
356 merkle_record_type = ComposedType([
357 ('left', HashType()),
358 ('right', HashType()),
361 def merkle_hash(tx_list):
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])]
370 def target_to_average_attempts(target):
371 return 2**256//(target + 1)
375 human_address_type = ChecksummedType(ComposedType([
376 ('version', StructType('<B')),
377 ('pubkey_hash', ShortHashType()),
380 pubkey_type = FixedStrType(65)
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))
385 def pubkey_to_address(pubkey, net):
386 return pubkey_hash_to_address(pubkey_type.hash160(pubkey), net)
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']
394 # linked list tracker
396 class Tracker(object):
398 self.shares = {} # hash -> share
399 self.reverse_shares = {} # previous_hash -> set of share_hashes
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 self.skips = {} # share_hash -> skip list
406 def add(self, share):
407 assert not isinstance(share, (int, long, type(None)))
408 if share.hash in self.shares:
409 return # XXX raise exception?
411 self.shares[share.hash] = share
412 self.reverse_shares.setdefault(share.previous_hash, set()).add(share.hash)
414 if share.hash in self.tails:
415 heads = self.tails.pop(share.hash)
417 heads = set([share.hash])
419 if share.previous_hash in self.heads:
420 tail = self.heads.pop(share.previous_hash)
422 tail = share.previous_hash
424 self.tails.setdefault(tail, set()).update(heads)
425 if share.previous_hash in self.tails[tail]:
426 self.tails[tail].remove(share.previous_hash)
429 self.heads[head] = tail
431 def get_height_and_last(self, share_hash):
432 assert isinstance(share_hash, (int, long, type(None)))
437 if share_hash is None or share_hash not in self.shares:
439 updates.append((share_hash, height))
440 if share_hash in self.heights:
441 height_inc, share_hash = self.heights[share_hash]
443 height_inc, share_hash = 1, self.shares[share_hash].previous_hash
445 for update_hash, height_then in updates:
446 self.heights[update_hash] = height - height_then, share_hash
447 assert (height, share_hash) == self.get_height_and_last2(orig), ((height, share_hash), self.get_height_and_last2(orig))
448 return height, share_hash
450 def get_height_and_last2(self, share_hash):
451 assert isinstance(share_hash, (int, long, type(None)))
454 if share_hash not in self.shares:
456 share_hash = self.shares[share_hash].previous_hash
458 return height, share_hash
460 def get_chain_known(self, start_hash):
461 assert isinstance(start_hash, (int, long, type(None)))
463 Chain starting with item of hash I{start_hash} of items that this Tracker contains
465 item_hash_to_get = start_hash
467 if item_hash_to_get not in self.shares:
469 share = self.shares[item_hash_to_get]
470 assert not isinstance(share, long)
472 item_hash_to_get = share.previous_hash
474 def get_chain_to_root(self, start_hash, root=None):
475 assert isinstance(start_hash, (int, long, type(None)))
476 assert isinstance(root, (int, long, type(None)))
478 Chain of hashes starting with share_hash of shares to the root (doesn't include root)
479 Raises an error if one is missing
481 share_hash_to_get = start_hash
482 while share_hash_to_get != root:
483 share = self.shares[share_hash_to_get]
485 share_hash_to_get = share.previous_hash
487 def get_best_hash(self):
489 Returns hash of item with the most items in its chain
493 return max(self.heads, key=self.get_height_and_last)
495 def get_highest_height(self):
496 return max(self.get_height_and_last(head)[0] for head in self.heads) if self.heads else 0
498 def get_nth_parent_hash(self, item_hash, n):
500 raise ValueError('n must be >= 0')
504 if item_hash not in self.skips:
505 self.skips[item_hash] = math.geometric(.5), [(1, self.shares[item_hash].previous_hash)]
506 skip_length, skip = self.skips[item_hash]
508 for i in xrange(skip_length):
510 n_then, that_hash = updates.pop(i)
511 x, y = self.skips[that_hash]
513 y.append((n_then - n, item_hash))
515 for i in xrange(len(skip), skip_length):
516 updates[i] = n, item_hash
518 for i, (dist, then_hash) in enumerate(reversed(skip)):
522 raise AssertionError()
525 item_hash = then_hash
529 def get_nth_parent2(self, item_hash, n):
532 x = self.shares[item_hash].previous_hash
535 if __name__ == '__main__':
536 class FakeShare(object):
537 def __init__(self, hash, previous_hash):
539 self.previous_hash = previous_hash
543 for i in xrange(10000):
544 t.add(FakeShare(i, i - 1 if i > 0 else None))
546 #for share_hash in sorted(t.shares):
547 # print share_hash, t.get_height_and_last(share_hash)
549 print t.get_nth_parent_hash(9000, 5000)
550 print t.get_nth_parent_hash(9001, 412)
551 #print t.get_nth_parent_hash(90, 51)
553 for share_hash in sorted(t.shares):
554 print str(share_hash).rjust(4),
555 x = t.skips.get(share_hash, None)
557 print str(x[0]).rjust(4),
559 print str(a).rjust(10),
562 # network definitions
564 class Mainnet(object):
565 BITCOIN_P2P_PREFIX = 'f9beb4d9'.decode('hex')
566 BITCOIN_P2P_PORT = 8333
567 BITCOIN_ADDRESS_VERSION = 0
569 class Testnet(object):
570 BITCOIN_P2P_PREFIX = 'fabfb5da'.decode('hex')
571 BITCOIN_P2P_PORT = 18333
572 BITCOIN_ADDRESS_VERSION = 111