1 from __future__ import division
5 from bitcoin import data as bitcoin_data
7 class CompressedList(bitcoin_data.Type):
8 def __init__(self, inner):
12 values = bitcoin_data.ListType(self.inner).read(file)
13 if values != sorted(set(values)):
14 raise ValueError("invalid values")
15 references = bitcoin_data.ListType(bitcoin_data.VarIntType()).read(file)
16 return [values[reference] for reference in references]
18 def write(self, file, item):
19 values = sorted(set(item))
20 values_map = dict((value, i) for i, value in enumerate(values))
21 bitcoin_data.ListType(self.inner).write(file, values)
22 bitcoin_data.ListType(bitcoin_data.VarIntType()).write(file, [values_map[subitem] for subitem in item])
25 merkle_branch_type = bitcoin_data.ListType(bitcoin_data.ComposedType([
26 ('side', bitcoin_data.StructType('<B')), # enum?
27 ('hash', bitcoin_data.HashType()),
31 share_data_type = bitcoin_data.ComposedType([
32 ('previous_share_hash', bitcoin_data.PossiblyNone(0, bitcoin_data.HashType())),
33 ('previous_shares_hash', bitcoin_data.HashType()),
34 ('target2', bitcoin_data.FloatingIntegerType()),
35 ('nonce', bitcoin_data.VarStrType()),
39 coinbase_type = bitcoin_data.ComposedType([
40 ('identifier', bitcoin_data.StructType('<Q')),
41 ('share_data', share_data_type),
44 share_info_type = bitcoin_data.ComposedType([
45 ('share_data', share_data_type),
46 ('new_script', bitcoin_data.VarStrType()),
47 ('subsidy', bitcoin_data.StructType('<Q')),
51 share1a_type = bitcoin_data.ComposedType([
52 ('header', bitcoin_data.block_header_type), # merkle_header not completely needed
53 ('share_info', share_info_type),
54 ('merkle_branch', merkle_branch_type),
57 share1b_type = bitcoin_data.ComposedType([
58 ('header', bitcoin_data.block_header_type),
59 ('share_info', share_info_type),
60 ('other_txs', bitcoin_data.ListType(bitcoin_data.tx_type)),
63 shares_type = CompressedList(bitcoin_data.VarStrType())
65 def calculate_merkle_branch(txs, index):
66 hash_list = [(bitcoin_data.tx_type.hash256(tx), i == index, []) for i, tx in enumerate(txs)]
68 while len(hash_list) > 1:
71 bitcoin_data.merkle_record_type.hash256(dict(left=left, right=right)),
73 (left_l if left_f else right_l) + [dict(side=1, hash=right) if left_f else dict(side=0, hash=left)],
75 for (left, left_f, left_l), (right, right_f, right_l) in
76 zip(hash_list[::2], hash_list[1::2] + [hash_list[::2][-1]])
79 assert hash_list[0][1]
80 assert check_merkle_branch(txs[index], hash_list[0][2]) == hash_list[0][0]
82 return hash_list[0][2]
84 def check_merkle_branch(tx, branch):
85 hash_ = bitcoin_data.tx_type.hash256(tx)
88 hash_ = bitcoin_data.merkle_record_type.hash256(dict(left=step['hash'], right=hash_))
90 hash_ = bitcoin_data.merkle_record_type.hash256(dict(left=hash_, right=step['hash']))
93 def gentx_to_share_info(gentx):
95 share_data=coinbase_type.unpack(gentx['tx_ins'][0]['script'])['share_data'],
96 subsidy=sum(tx_out['value'] for tx_out in gentx['tx_outs']),
97 new_script=gentx['tx_outs'][-1]['script'],
100 def share_info_to_gentx(share_info, chain, net):
101 return generate_transaction(
102 previous_share2=chain.share2s[share_info['share_data']['previous_share_hash']],
103 nonce=share_info['share_data']['nonce'],
104 new_script=share_info['new_script'],
105 subsidy=share_info['subsidy'],
110 def __init__(self, header, share_info, merkle_branch=None, other_txs=None):
111 if merkle_branch is None and other_txs is None:
112 raise ValueError('need either merkle_branch or other_txs')
114 self.share_info = share_info
115 self.merkle_branch = merkle_branch
116 self.other_txs = other_txs
118 self.share_data = self.share_info['share_data']
119 self.new_script = self.share_info['new_script']
120 self.subsidy = self.share_info['subsidy']
122 self.previous_share_hash = self.share_data['previous_share_hash']
123 self.previous_shares_hash = self.share_data['previous_shares_hash']
124 self.target2 = self.share_data['target2']
126 self.hash = bitcoin_data.block_header_type.hash256(header)
129 def from_block(cls, block):
130 return cls(block['header'], gentx_to_share_info(block['txs'][0]), other_txs=block['txs'][1:])
133 def from_share1a(cls, share1a):
134 return cls(**share1a)
137 def from_share1b(cls, share1b):
138 return cls(**share1b)
142 raise ValueError('share does not contain all txs')
144 return dict(header=self.header, txs=self.txs)
147 return dict(header=self.header, gentx_info=self.gentx_info)
149 def check(self, chain, height, previous_share2, net):
150 if self.chain_id_data != chain.chain_id_data:
151 raise ValueError('wrong chain')
153 if self.hash > net.TARGET_MULTIPLIER*bitcoin_data.bits_to_target(self.header['bits']):
154 raise ValueError('not enough work!')
156 gentx, shares, merkle_root = gentx_info_to_gentx_shares_and_merkle_root(self.gentx_info, chain, net)
158 if merkle_root != self.header['merkle_root']:
159 raise ValueError("gentx doesn't match header")
161 return Share2(self, shares, height)
163 class Share2(object):
164 '''Share with associated data'''
166 def __init__(self, share, shares, height):
173 def flag_shared(self):
176 def generate_transaction(tracker, previous_share_hash, new_script, subsidy, nonce, block_target, net):
177 previous_share2 = tracker.shares[previous_share_hash] if previous_share_hash is not None else None
178 #previous_share2 = chain.shares
181 #shares = (previous_share2.shares if previous_share2 is not None else [net.SCRIPT]*net.SPREAD)[1:-1] + [new_script, new_script]
183 chain = list(itertools.islice(tracker.get_chain(previous_share_hash), net.CHAIN_LENGTH))
185 target2 = bitcoin_data.FloatingIntegerType().truncate_to(2**256//2**32 - 1)
187 attempts_per_second = sum(bitcoin_data.target_to_average_attempts(share.target) for share in itertools.islice(chain, 0, max(0, len(chain) - 1)))//(chain[0].timestamp - chain[-1].timestamp)
188 pre_target = 2**256*net.SHARE_PERIOD//attempts_per_second
189 pre_target2 = math.clip(pre_target, (previous_share2.target*9//10, previous_share2.target*11//10))
190 pre_target3 = math.clip(pre_target2, (0, 2**256//2**32 - 1))
191 target2 = bitcoin_data.FloatingIntegerType().truncate_to(pre_target3)
194 attempts_to_block = bitcoin_data.target_to_average_attempts(block_target)
197 class fake_share(object):
199 share = dict(target=target2)
202 for share in itertools.chain([fake_share], itertools.islice(tracker.get_chain(previous_share_hash), net.CHAIN_LENGTH)):
203 weight = bitcoin_data.target_to_average_attempts(share.share['target'])
204 weight = max(weight, attempts_to_block - total_weight)
206 dest_weights[share.script] = dest_weights.get(share.script, 0) + weight
207 total_weight += weight
209 if total_weight == attempts_to_block:
212 amounts = dict((script, subsidy*(199*weight)//(200*total_weight)) for (script, weight) in dest_weights.iteritems())
213 amounts[net.SCRIPT] = amounts.get(net.SCRIPT, 0) + subsidy*1//200 # prevent fake previous p2pool blocks
214 amounts[net.SCRIPT] = amounts.get(net.SCRIPT, 0) + subsidy - sum(amounts.itervalues()) # collect any extra
216 dests = sorted(amounts.iterkeys(), key=lambda script: (script == new_script, script))
217 assert dests[-1] == new_script, dests
219 previous_shares = [] # XXX
224 previous_output=None,
226 script=coinbase_type.pack(dict(
227 identifier=net.IDENTIFIER,
229 previous_share_hash=previous_share_hash,
230 previous_shares_hash=shares_type.hash256(previous_shares),
236 tx_outs=[dict(value=amounts[script], script=script) for script in dests if amounts[script]],
241 class Tracker(object):
243 self.shares = {} # hash -> share
244 self.reverse_shares = {} # previous_share_hash -> share_hash
245 self.heads = {} # hash -> (height, tail hash)
248 def add_share(self, share):
249 if share.hash in self.shares:
250 return # XXX raise exception?
252 self.shares[share.hash] = share
253 self.reverse_shares.setdefault(share.previous_share_hash, set()).add(share.hash)
255 if self.reverse_shares.get(share.hash, set()):
258 self.heads.add(share.hash)
259 if share.previous_share_hash in self.heads:
260 self.heads.remove(share.previous_share_hash)
262 def get_chain(self, start):
263 share_hash_to_get = start
264 while share_hash_to_get in self.shares:
265 share = self.shares[share_hash_to_get]
267 share_hash_to_get = share.previous_share_hash
269 def get_best_share_hash(self):
272 return max(self.heads, key=self.score_chain)
274 def score_chain(self, start):
275 length = len(self.get_chain(start))
278 for share in itertools.islice(self.get_chain(start), self.net.CHAIN_LENGTH):
281 return (min(length, 1000), score)
283 class OkayTracker(Tracker):
285 Tracker.__init__(self)
286 self.okay_cache = set()
287 def is_okay(self, start):
290 {'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
291 {'result': 'needs_parent', 'parent_hash': ...} # if share doesn't have CHAIN_LENGTH parents
292 {'result': 'needs_share_shares', 'share_hash': ...} # if share has CHAIN_LENGTH children and needs its shares to
293 {'result': 'not_okay'} # if the share has a not okay parent or if the share has an okay parent and failed validation
298 for share in itertools.islice(self.get_chain(start), self.net.CHAIN_LENGTH):
299 if share in self.okay_cache:
300 return validate(share, to_end_rev[::-1])
301 to_end_rev.append(share)
302 # picking up last share from for loop, ew
303 self.okay_cache.add(share)
304 return validate(share, to_end_rev[::-1])
309 def get_chain_descriptor(tracker, start):
310 for item in tracker.get_chain(self.net.CHAIN_LENGTH):
314 if __name__ == '__main__':
315 class FakeShare(object):
316 def __init__(self, hash, previous_share_hash):
318 self.previous_share_hash = previous_share_hash
322 t.add_share(FakeShare(1, 2))
324 t.add_share(FakeShare(4, 0))
326 t.add_share(FakeShare(3, 4))
329 class Mainnet(bitcoin_data.Mainnet):
330 SHARE_PERIOD = 5 # seconds
331 CHAIN_LENGTH = 1000 # shares
333 ROOT_BLOCK = 0x6c9cb0589a44808d9a9361266a4ffb9fea2e2cf4d70bb2118b5
334 SCRIPT = '4104ffd03de44a6e11b9917f3a29f9443283d9871c9d743ef30d5eddcd37094b64d1b3d8090496b53256786bf5c82932ec23c3b74d9f05a6f95a8b5529352656664bac'.decode('hex')
335 IDENTIFIER = 0x7452839666e1f8f8
336 PREFIX = '2d4224bf18c87b87'.decode('hex')
337 ADDRS_TABLE = 'addrs'
340 class Testnet(bitcoin_data.Testnet):
341 SHARE_PERIOD = 5 # seconds
342 CHAIN_LENGTH = 1000 # shares
344 ROOT_BLOCK = 0xd5070cd4f2987ad2191af71393731a2b143f094f7b84c9e6aa9a6a
345 SCRIPT = '410403ad3dee8ab3d8a9ce5dd2abfbe7364ccd9413df1d279bf1a207849310465b0956e5904b1155ecd17574778f9949589ebfd4fb33ce837c241474a225cf08d85dac'.decode('hex')
346 IDENTIFIER = 0x1ae3479e4eb6700a
347 PREFIX = 'd19778c812754854'.decode('hex')
348 ADDRS_TABLE = 'addrs_testnet'