1 import plyvel, ast, hashlib, traceback, os
2 from processor import print_log
7 Patricia tree for hashing unspents
12 KEYLENGTH = 20 + 32 + 4 #56
14 class Storage(object):
16 def __init__(self, config, shared, test_reorgs):
18 self.dbpath = config.get('leveldb', 'path_fulltree')
19 if not os.path.exists(self.dbpath):
21 self.pruning_limit = config.getint('leveldb', 'pruning_limit')
26 self.test_reorgs = test_reorgs
28 self.db_addr = plyvel.DB(os.path.join(self.dbpath,'addr'), create_if_missing=True, compression=None)
29 self.db = plyvel.DB(os.path.join(self.dbpath,'utxo'), create_if_missing=True, compression=None)
30 self.db_undo = plyvel.DB(os.path.join(self.dbpath,'undo'), create_if_missing=True, compression=None)
32 traceback.print_exc(file=sys.stdout)
35 self.db_version = 2 # increase this when database needs to be updated
37 self.last_hash, self.height, db_version = ast.literal_eval(self.db_undo.get('height'))
38 print_log("Database version", self.db_version)
39 print_log("Blockchain height", self.height)
41 #traceback.print_exc(file=sys.stdout)
42 print_log('initializing database')
44 self.last_hash = '000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f'
45 db_version = self.db_version
50 if self.db_version != db_version:
51 print_log("Your database '%s' is deprecated. Please create a new database"%self.dbpath)
57 # convert between bitcoin addresses and 20 bytes keys used for storage.
58 def address_to_key(self, addr):
59 return bc_address_to_hash_160(addr)
61 def key_to_address(self, addr):
62 return hash_160_to_bc_address(addr)
65 def get_history(self, addr):
66 addr = self.address_to_key(addr)
67 x = self.db_addr.get(addr)
74 traceback.print_exc(file=sys.stdout)
79 def get_address(self, txi):
80 addr = self.db.get(txi)
81 return self.key_to_address(addr) if addr else None
84 def get_undo_info(self, height):
85 s = self.db_undo.get("undo_info_%d" % (height % 100))
86 if s is None: print_log("no undo info for ", height)
90 def write_undo_info(self, height, bitcoind_height, undo_info):
91 if height > bitcoind_height - 100 or self.test_reorgs:
92 self.db_undo.put("undo_info_%d" % (height % 100), repr(undo_info))
95 def common_prefix(self, word1, word2):
96 max_len = min(len(word1),len(word2))
97 for i in range(max_len):
98 if word2[i] != word1[i]:
103 return word1[0:index]
106 def put_node(self, key, d, batch=None):
110 if chr(i) in d.keys():
113 if h is None: h = chr(0)*32
114 vv = int_to_hex(v, 8).decode('hex')
116 assert len(item) == 40
119 k = "0x%0.64X" % k # 32 bytes
120 k = k[2:].decode('hex')
126 self.db_addr.put(key, out)
129 def get_node(self, key):
131 s = self.db_addr.get(key)
135 #print "get node", key.encode('hex'), len(key), s.encode('hex')
137 k = int(s[0:32].encode('hex'), 16)
143 value = hex_to_int(s[32:40])
144 d[chr(i)] = (_hash, value)
152 def add_address(self, target, value):
153 assert len(target) == KEYLENGTH
158 i = self.db_addr.iterator()
162 items = self.get_node(key)
164 if word[0] in items.keys():
166 i.seek(key + word[0])
167 new_key, _ = i.next()
169 if target.startswith(new_key):
170 # add value to the child node
172 word = target[len(key):]
176 assert key not in path
179 # prune current node and add new node
180 prefix = self.common_prefix(new_key, target)
183 ## get hash and value of new_key from parent (if it's a leaf)
184 if len(new_key) == KEYLENGTH:
185 parent_key = self.get_parent(new_key)
186 parent = self.get_node(parent_key)
187 z = parent[ new_key[len(parent_key)] ]
188 self.put_node(prefix, { target[index]:(None,0), new_key[index]:z } )
190 # if it is not a leaf, update the hash of new_key because skip_string changed
191 h, v = self.get_node_hash(new_key, self.get_node(new_key), prefix)
192 self.put_node(prefix, { target[index]:(None,0), new_key[index]:(h,v) } )
195 self.parents[new_key] = prefix
200 items[ word[0] ] = (None,0)
201 self.put_node(key,items)
205 s = int_to_hex(value, 8).decode('hex')
206 self.db_addr.put(target, s)
207 # the hash of a node is the txid
208 _hash = target[20:52]
209 self.update_node_hash(target, path, _hash, value)
212 def update_node_hash(self, node, path, _hash, value):
218 self.hash_list[node] = (_hash, value)
221 def update_hashes(self):
223 nodes = {} # nodes to write
225 for i in range(KEYLENGTH, -1, -1):
227 for node in self.hash_list.keys():
228 if len(node) != i: continue
230 node_hash, node_value = self.hash_list.pop(node)
232 # for each node, compute its hash, send it to the parent
234 self.root_hash = node_hash
235 self.root_value = node_value
238 parent = self.parents[node]
240 # read parent.. do this in add_address
241 d = nodes.get(parent)
243 d = self.get_node(parent)
246 letter = node[len(parent)]
247 assert letter in d.keys()
249 if i != KEYLENGTH and node_hash is None:
250 d2 = self.get_node(node)
251 node_hash, node_value = self.get_node_hash(node, d2, parent)
253 assert node_hash is not None
255 d[letter] = (node_hash, node_value)
259 grandparent = self.parents[parent] if parent != '' else None
260 parent_hash, parent_value = self.get_node_hash(parent, d, grandparent)
261 self.hash_list[parent] = (parent_hash, parent_value)
264 # batch write modified nodes
265 batch = self.db_addr.write_batch()
266 for k, v in nodes.items():
267 self.put_node(k, v, batch)
271 assert self.hash_list == {}
275 def get_node_hash(self, x, d, parent):
279 skip_string = x[len(parent)+1:]
283 d2 = sorted(d.items())
284 values = map(lambda x: x[1][1], d2)
285 hashes = map(lambda x: x[1][0], d2)
286 value = sum( values )
287 _hash = self.hash( skip_string + ''.join(hashes) )
291 def get_path(self, target):
295 i = self.db_addr.iterator(start='')
299 i.seek(key + word[0])
301 new_key, _ = i.next()
302 is_child = new_key.startswith(key + word[0])
303 except StopIteration:
308 if target.startswith(new_key):
309 # add value to the child node
311 word = target[len(key):]
315 assert key not in path
318 print_log('not in tree', self.db_addr.get(key+word[0]), new_key.encode('hex'))
327 def delete_address(self, leaf):
328 path = self.get_path(leaf)
330 print_log("addr not in tree", leaf.encode('hex'), self.key_to_address(leaf[0:20]), self.db_addr.get(leaf))
333 self.db_addr.delete(leaf)
334 if leaf in self.hash_list:
335 self.hash_list.pop(leaf)
338 letter = leaf[len(parent)]
339 items = self.get_node(parent)
340 vv = items.pop(letter)
342 # remove key if it has a single child
344 letter, v = items.items()[0]
346 self.db_addr.delete(parent)
347 if parent in self.hash_list:
348 self.hash_list.pop(parent)
350 # we need the exact length for the iteration
351 i = self.db_addr.iterator()
352 i.seek(parent+letter)
355 # note: k is not necessarily a leaf
356 if len(k) == KEYLENGTH:
357 _hash, value = k[20:52], hex_to_int(v)
359 _hash, value = None, None
361 self.update_node_hash(k, path[:-1], _hash, value)
364 self.put_node(parent, items)
365 _hash, value = None, None
366 self.update_node_hash(parent, path[:-1], _hash, value)
371 def get_children(self, x):
372 i = self.db_addr.iterator()
377 if k.startswith(x+chr(l)):
380 elif k.startswith(x):
382 l = ord(k[len(x)]) + 1
389 def get_parent(self, x):
390 """ return parent and skip string"""
391 i = self.db_addr.iterator()
392 for j in range(len(x)):
396 if x.startswith(k) and x!=k:
403 if DEBUG: return "hash("+x+")"
407 def get_root_hash(self):
408 return self.root_hash
417 def add_to_history(self, addr, tx_hash, tx_pos, value, tx_height):
418 key = self.address_to_key(addr)
419 txo = (tx_hash + int_to_hex(tx_pos, 4)).decode('hex')
421 # write the new history
422 self.add_address(key + txo, value)
425 self.db.put(txo, key)
429 def revert_add_to_history(self, addr, tx_hash, tx_pos, value, tx_height):
430 key = self.address_to_key(addr)
431 txo = (tx_hash + int_to_hex(tx_pos, 4)).decode('hex')
434 self.delete_address(key + txo)
441 def set_spent(self, addr, txi, txid, index, height, undo):
442 key = self.address_to_key(addr)
445 _hash, value = self.delete_address(leaf)
448 # delete backlink txi-> addr
453 def revert_set_spent(self, addr, txi, undo):
454 key = self.address_to_key(addr)
458 self.db.put(txi, key)
461 self.add_address(leaf, v)
469 def import_transaction(self, txid, tx, block_height, touched_addr):
471 undo = { 'prev_addr':[] } # contains the list of pruned items for each address in the tx; also, 'prev_addr' is a list of prev addresses
474 for i, x in enumerate(tx.get('inputs')):
475 txi = (x.get('prevout_hash') + int_to_hex(x.get('prevout_n'), 4)).decode('hex')
476 addr = self.get_address(txi)
478 self.set_spent(addr, txi, txid, i, block_height, undo)
479 touched_addr.add(addr)
480 prev_addr.append(addr)
482 undo['prev_addr'] = prev_addr
484 # here I add only the outputs to history; maybe I want to add inputs too (that's in the other loop)
485 for x in tx.get('outputs'):
486 addr = x.get('address')
487 if addr is None: continue
488 self.add_to_history(addr, txid, x.get('index'), x.get('value'), block_height)
489 touched_addr.add(addr)
494 def revert_transaction(self, txid, tx, block_height, touched_addr, undo):
495 #print_log("revert tx", txid)
496 for x in tx.get('outputs'):
497 addr = x.get('address')
498 if addr is None: continue
499 self.revert_add_to_history(addr, txid, x.get('index'), x.get('value'), block_height)
500 touched_addr.add(addr)
502 prev_addr = undo.pop('prev_addr')
503 for i, x in enumerate(tx.get('inputs')):
506 txi = (x.get('prevout_hash') + int_to_hex(x.get('prevout_n'), 4)).decode('hex')
507 self.revert_set_spent(addr, txi, undo)
508 touched_addr.add(addr)