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_utxo = plyvel.DB(os.path.join(self.dbpath,'utxo'), create_if_missing=True, compression=None)
29 self.db_addr = plyvel.DB(os.path.join(self.dbpath,'addr'), create_if_missing=True, compression=None)
30 self.db_hist = plyvel.DB(os.path.join(self.dbpath,'hist'), create_if_missing=True, compression=None)
31 self.db_undo = plyvel.DB(os.path.join(self.dbpath,'undo'), create_if_missing=True, compression=None)
33 traceback.print_exc(file=sys.stdout)
36 self.db_version = 3 # increase this when database needs to be updated
38 self.last_hash, self.height, db_version = ast.literal_eval(self.db_undo.get('height'))
39 print_log("Database version", self.db_version)
40 print_log("Blockchain height", self.height)
42 #traceback.print_exc(file=sys.stdout)
43 print_log('initializing database')
45 self.last_hash = '000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f'
46 db_version = self.db_version
51 if self.db_version != db_version:
52 print_log("Your database '%s' is deprecated. Please create a new database"%self.dbpath)
59 self.root_hash, v = self.get_node_hash('',d,None)
60 print_log("UTXO tree root hash:", self.root_hash.encode('hex'))
61 print_log("Coins in database:", v)
63 # convert between bitcoin addresses and 20 bytes keys used for storage.
64 def address_to_key(self, addr):
65 return bc_address_to_hash_160(addr)
67 def key_to_address(self, addr):
68 return hash_160_to_bc_address(addr)
71 def get_proof(self, addr):
72 key = self.address_to_key(addr)
73 i = self.db_utxo.iterator(start=key)
81 v = self.db_utxo.get(item)
82 out.append((item.encode('hex'), v.encode('hex')))
87 def get_balance(self, addr):
88 key = self.address_to_key(addr)
89 i = self.db_utxo.iterator(start=key)
91 if not k.startswith(key):
93 p = self.get_parent(k)
99 def listunspent(self, addr):
100 key = self.address_to_key(addr)
103 for k, v in self.db_utxo.iterator(start=key):
104 if not k.startswith(key):
106 if len(k) == KEYLENGTH:
107 txid = k[20:52].encode('hex')
108 txpos = hex_to_int(k[52:56])
109 h = hex_to_int(v[8:12])
110 v = hex_to_int(v[0:8])
111 out.append({'tx_hash': txid, 'tx_pos':txpos, 'height': h, 'value':v})
113 out.sort(key=lambda x:x['height'])
117 def get_history(self, addr):
120 o = self.listunspent(addr)
122 out.append((item['tx_hash'], item['height']))
124 h = self.db_hist.get(addr)
129 txi = item[0:32].encode('hex')
130 hi = hex_to_int(item[36:40])
131 txo = item[40:72].encode('hex')
132 ho = hex_to_int(item[76:80])
133 out.append((txi, hi))
134 out.append((txo, ho))
137 out.sort(key=lambda x:x[1])
142 return map(lambda x: {'tx_hash':x[0], 'height':x[1]}, out)
146 def get_address(self, txi):
147 return self.db_addr.get(txi)
150 def get_undo_info(self, height):
151 s = self.db_undo.get("undo_info_%d" % (height % 100))
152 if s is None: print_log("no undo info for ", height)
156 def write_undo_info(self, height, bitcoind_height, undo_info):
157 if height > bitcoind_height - 100 or self.test_reorgs:
158 self.db_undo.put("undo_info_%d" % (height % 100), repr(undo_info))
161 def common_prefix(self, word1, word2):
162 max_len = min(len(word1),len(word2))
163 for i in range(max_len):
164 if word2[i] != word1[i]:
169 return word1[0:index]
172 def put_node(self, key, d, batch=None):
176 if chr(i) in d.keys():
179 if h is None: h = chr(0)*32
180 vv = int_to_hex(v, 8).decode('hex')
182 assert len(item) == 40
185 k = "0x%0.64X" % k # 32 bytes
186 k = k[2:].decode('hex')
192 self.db_utxo.put(key, out)
195 def get_node(self, key):
197 s = self.db_utxo.get(key)
201 #print "get node", key.encode('hex'), len(key), s.encode('hex')
203 k = int(s[0:32].encode('hex'), 16)
209 value = hex_to_int(s[32:40])
210 d[chr(i)] = (_hash, value)
218 def add_address(self, target, value, height):
219 assert len(target) == KEYLENGTH
224 i = self.db_utxo.iterator()
228 items = self.get_node(key)
230 if word[0] in items.keys():
232 i.seek(key + word[0])
233 new_key, _ = i.next()
235 if target.startswith(new_key):
236 # add value to the child node
238 word = target[len(key):]
242 assert key not in path
245 # prune current node and add new node
246 prefix = self.common_prefix(new_key, target)
249 ## get hash and value of new_key from parent (if it's a leaf)
250 if len(new_key) == KEYLENGTH:
251 parent_key = self.get_parent(new_key)
252 parent = self.get_node(parent_key)
253 z = parent[ new_key[len(parent_key)] ]
254 self.put_node(prefix, { target[index]:(None,0), new_key[index]:z } )
256 # if it is not a leaf, update the hash of new_key because skip_string changed
257 h, v = self.get_node_hash(new_key, self.get_node(new_key), prefix)
258 self.put_node(prefix, { target[index]:(None,0), new_key[index]:(h,v) } )
261 self.parents[new_key] = prefix
266 items[ word[0] ] = (None,0)
267 self.put_node(key,items)
271 s = (int_to_hex(value, 8) + int_to_hex(height,4)).decode('hex')
272 self.db_utxo.put(target, s)
273 # the hash of a node is the txid
274 _hash = target[20:52]
275 self.update_node_hash(target, path, _hash, value)
278 def update_node_hash(self, node, path, _hash, value):
284 self.hash_list[node] = (_hash, value)
287 def update_hashes(self):
289 nodes = {} # nodes to write
291 for i in range(KEYLENGTH, -1, -1):
293 for node in self.hash_list.keys():
294 if len(node) != i: continue
296 node_hash, node_value = self.hash_list.pop(node)
298 # for each node, compute its hash, send it to the parent
300 self.root_hash = node_hash
301 self.root_value = node_value
304 parent = self.parents[node]
306 # read parent.. do this in add_address
307 d = nodes.get(parent)
309 d = self.get_node(parent)
312 letter = node[len(parent)]
313 assert letter in d.keys()
315 if i != KEYLENGTH and node_hash is None:
316 d2 = self.get_node(node)
317 node_hash, node_value = self.get_node_hash(node, d2, parent)
319 assert node_hash is not None
321 d[letter] = (node_hash, node_value)
325 grandparent = self.parents[parent] if parent != '' else None
326 parent_hash, parent_value = self.get_node_hash(parent, d, grandparent)
327 self.hash_list[parent] = (parent_hash, parent_value)
330 # batch write modified nodes
331 batch = self.db_utxo.write_batch()
332 for k, v in nodes.items():
333 self.put_node(k, v, batch)
337 assert self.hash_list == {}
341 def get_node_hash(self, x, d, parent):
345 skip_string = x[len(parent)+1:]
349 d2 = sorted(d.items())
350 values = map(lambda x: x[1][1], d2)
351 hashes = map(lambda x: x[1][0], d2)
352 value = sum( values )
353 _hash = self.hash( skip_string + ''.join(hashes) )
357 def get_path(self, target):
361 i = self.db_utxo.iterator(start='')
365 i.seek(key + word[0])
367 new_key, _ = i.next()
368 is_child = new_key.startswith(key + word[0])
369 except StopIteration:
374 if target.startswith(new_key):
375 # add value to the child node
377 word = target[len(key):]
381 assert key not in path
384 print_log('not in tree', self.db_utxo.get(key+word[0]), new_key.encode('hex'))
393 def delete_address(self, leaf):
394 path = self.get_path(leaf)
396 print_log("addr not in tree", leaf.encode('hex'), self.key_to_address(leaf[0:20]), self.db_utxo.get(leaf))
399 s = self.db_utxo.get(leaf)
401 self.db_utxo.delete(leaf)
402 if leaf in self.hash_list:
403 self.hash_list.pop(leaf)
406 letter = leaf[len(parent)]
407 items = self.get_node(parent)
410 # remove key if it has a single child
412 letter, v = items.items()[0]
414 self.db_utxo.delete(parent)
415 if parent in self.hash_list:
416 self.hash_list.pop(parent)
418 # we need the exact length for the iteration
419 i = self.db_utxo.iterator()
420 i.seek(parent+letter)
423 # note: k is not necessarily a leaf
424 if len(k) == KEYLENGTH:
425 _hash, value = k[20:52], hex_to_int(v[0:8])
427 _hash, value = None, None
429 self.update_node_hash(k, path[:-1], _hash, value)
432 self.put_node(parent, items)
433 _hash, value = None, None
434 self.update_node_hash(parent, path[:-1], _hash, value)
439 def get_children(self, x):
440 i = self.db_utxo.iterator()
445 if k.startswith(x+chr(l)):
448 elif k.startswith(x):
450 l = ord(k[len(x)]) + 1
457 def get_parent(self, x):
458 """ return parent and skip string"""
459 i = self.db_utxo.iterator()
460 for j in range(len(x)):
464 if x.startswith(k) and x!=k:
471 if DEBUG: return "hash("+x+")"
475 def get_root_hash(self):
476 return self.root_hash
486 def add_to_history(self, addr, tx_hash, tx_pos, value, tx_height):
487 key = self.address_to_key(addr)
488 txo = (tx_hash + int_to_hex(tx_pos, 4)).decode('hex')
490 # write the new history
491 self.add_address(key + txo, value, tx_height)
494 self.db_addr.put(txo, addr)
498 def revert_add_to_history(self, addr, tx_hash, tx_pos, value, tx_height):
499 key = self.address_to_key(addr)
500 txo = (tx_hash + int_to_hex(tx_pos, 4)).decode('hex')
503 self.delete_address(key + txo)
506 self.db_addr.delete(txo)
509 def get_utxo_value(self, addr, txi):
510 key = self.address_to_key(addr)
512 s = self.db_utxo.get(leaf)
513 value = hex_to_int(s[0:8])
517 def set_spent(self, addr, txi, txid, index, height, undo):
518 key = self.address_to_key(addr)
521 s = self.delete_address(leaf)
522 value = hex_to_int(s[0:8])
523 in_height = hex_to_int(s[8:12])
524 undo[leaf] = value, in_height
526 # delete backlink txi-> addr
527 self.db_addr.delete(txi)
530 s = self.db_hist.get(addr)
532 txo = (txid + int_to_hex(index,4) + int_to_hex(height,4)).decode('hex')
533 s += txi + int_to_hex(in_height,4).decode('hex') + txo
534 s = s[ -80*self.pruning_limit:]
535 self.db_hist.put(addr, s)
539 def revert_set_spent(self, addr, txi, undo):
540 key = self.address_to_key(addr)
544 self.db_addr.put(txi, addr)
546 v, height = undo.pop(leaf)
547 self.add_address(leaf, v, height)
549 # revert add to history
550 s = self.db_hist.get(addr)
551 # s might be empty if pruning limit was reached
555 assert s[-80:-44] == txi
557 self.db_hist.put(addr, s)
564 def import_transaction(self, txid, tx, block_height, touched_addr):
566 undo = { 'prev_addr':[] } # contains the list of pruned items for each address in the tx; also, 'prev_addr' is a list of prev addresses
569 for i, x in enumerate(tx.get('inputs')):
570 txi = (x.get('prevout_hash') + int_to_hex(x.get('prevout_n'), 4)).decode('hex')
571 addr = self.get_address(txi)
573 self.set_spent(addr, txi, txid, i, block_height, undo)
574 touched_addr.add(addr)
575 prev_addr.append(addr)
577 undo['prev_addr'] = prev_addr
579 # here I add only the outputs to history; maybe I want to add inputs too (that's in the other loop)
580 for x in tx.get('outputs'):
581 addr = x.get('address')
582 if addr is None: continue
583 self.add_to_history(addr, txid, x.get('index'), x.get('value'), block_height)
584 touched_addr.add(addr)
589 def revert_transaction(self, txid, tx, block_height, touched_addr, undo):
590 #print_log("revert tx", txid)
591 for x in reversed(tx.get('outputs')):
592 addr = x.get('address')
593 if addr is None: continue
594 self.revert_add_to_history(addr, txid, x.get('index'), x.get('value'), block_height)
595 touched_addr.add(addr)
597 prev_addr = undo.pop('prev_addr')
598 for i, x in reversed(list(enumerate(tx.get('inputs')))):
601 txi = (x.get('prevout_hash') + int_to_hex(x.get('prevout_n'), 4)).decode('hex')
602 self.revert_set_spent(addr, txi, undo)
603 touched_addr.add(addr)