backends/bitcoind/storage.py

   1 import plyvel, ast, hashlib, traceback, os
   2 from processor import print_log
   3 from utils import *
   4
   5
   6 """
   7 Patricia tree for hashing unspents
   8
   9 """
  10
  11 DEBUG = 0
  12 KEYLENGTH = 20 + 32 + 4   #56
  13
  14 class Storage(object):
  15
  16     def __init__(self, config, shared, test_reorgs):
  17
  18         self.dbpath = config.get('leveldb', 'path_fulltree')
  19         if not os.path.exists(self.dbpath):
  20             os.mkdir(self.dbpath)
  21         self.pruning_limit = config.getint('leveldb', 'pruning_limit')
  22         self.shared = shared
  23         self.hash_list = {}
  24         self.parents = {}
  25
  26         self.test_reorgs = test_reorgs
  27         try:
  28             self.db_tree = 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_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)
  32         except:
  33             traceback.print_exc(file=sys.stdout)
  34             self.shared.stop()
  35
  36         self.db_version = 2 # increase this when database needs to be updated
  37         try:
  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)
  41         except:
  42             #traceback.print_exc(file=sys.stdout)
  43             print_log('initializing database')
  44             self.height = 0
  45             self.last_hash = '000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f'
  46             db_version = self.db_version
  47             # write root
  48             self.put_node('', {})
  49
  50         # check version
  51         if self.db_version != db_version:
  52             print_log("Your database '%s' is deprecated. Please create a new database"%self.dbpath)
  53             self.shared.stop()
  54             return
  55
  56
  57
  58     # convert between bitcoin addresses and 20 bytes keys used for storage.
  59     def address_to_key(self, addr):
  60         return bc_address_to_hash_160(addr)
  61
  62     def key_to_address(self, addr):
  63         return hash_160_to_bc_address(addr)
  64
  65
  66     def get_history(self, addr):
  67         addr = self.address_to_key(addr)
  68         x = self.db_tree.get(addr)
  69         if x is None:
  70             return ''
  71         try:
  72             _hash, v, h = x
  73             return h
  74         except:
  75             traceback.print_exc(file=sys.stdout)
  76             self.shared.stop()
  77             raise
  78
  79
  80     def get_address(self, txi):
  81         addr = self.db.get(txi)
  82         return self.key_to_address(addr) if addr else None
  83
  84
  85     def get_undo_info(self, height):
  86         s = self.db_undo.get("undo_info_%d" % (height % 100))
  87         if s is None: print_log("no undo info for ", height)
  88         return eval(s)
  89
  90
  91     def write_undo_info(self, height, bitcoind_height, undo_info):
  92         if height > bitcoind_height - 100 or self.test_reorgs:
  93             self.db_undo.put("undo_info_%d" % (height % 100), repr(undo_info))
  94
  95
  96     def common_prefix(self, word1, word2):
  97         max_len = min(len(word1),len(word2))
  98         for i in range(max_len):
  99             if word2[i] != word1[i]:
 100                 index = i
 101                 break
 102         else:
 103             index = max_len
 104         return word1[0:index]
 105
 106
 107     def put_node(self, key, d, batch=None):
 108         k = 0
 109         serialized = ''
 110         for i in range(256):
 111             if chr(i) in d.keys():
 112                 k += 1<<i
 113                 h, v = d[chr(i)]
 114                 if h is None: h = chr(0)*32
 115                 vv = int_to_hex(v, 8).decode('hex')
 116                 item = h + vv
 117                 assert len(item) == 40
 118                 serialized += item
 119
 120         k = "0x%0.64X" % k # 32 bytes
 121         k = k[2:].decode('hex')
 122         assert len(k) == 32
 123         out = k + serialized
 124         if batch:
 125             batch.put(key, out)
 126         else:
 127             self.db_tree.put(key, out)
 128
 129
 130     def get_node(self, key):
 131
 132         s = self.db_tree.get(key)
 133         if s is None:
 134             return
 135
 136         #print "get node", key.encode('hex'), len(key), s.encode('hex')
 137
 138         k = int(s[0:32].encode('hex'), 16)
 139         s = s[32:]
 140         d = {}
 141         for i in range(256):
 142             if k % 2 == 1:
 143                 _hash = s[0:32]
 144                 value = hex_to_int(s[32:40])
 145                 d[chr(i)] = (_hash, value)
 146                 s = s[40:]
 147             k = k/2
 148
 149         #cache
 150         return d
 151
 152
 153     def add_address(self, target, value, height):
 154         assert len(target) == KEYLENGTH
 155
 156         word = target
 157         key = ''
 158         path = [ '' ]
 159         i = self.db_tree.iterator()
 160
 161         while key != target:
 162
 163             items = self.get_node(key)
 164
 165             if word[0] in items.keys():
 166
 167                 i.seek(key + word[0])
 168                 new_key, _ = i.next()
 169
 170                 if target.startswith(new_key):
 171                     # add value to the child node
 172                     key = new_key
 173                     word = target[len(key):]
 174                     if key == target:
 175                         break
 176                     else:
 177                         assert key not in path
 178                         path.append(key)
 179                 else:
 180                     # prune current node and add new node
 181                     prefix = self.common_prefix(new_key, target)
 182                     index = len(prefix)
 183
 184                     ## get hash and value of new_key from parent (if it's a leaf)
 185                     if len(new_key) == KEYLENGTH:
 186                         parent_key = self.get_parent(new_key)
 187                         parent = self.get_node(parent_key)
 188                         z = parent[ new_key[len(parent_key)] ]
 189                         self.put_node(prefix, { target[index]:(None,0), new_key[index]:z } )
 190                     else:
 191                         # if it is not a leaf, update the hash of new_key because skip_string changed
 192                         h, v = self.get_node_hash(new_key, self.get_node(new_key), prefix)
 193                         self.put_node(prefix, { target[index]:(None,0), new_key[index]:(h,v) } )
 194
 195                     path.append(prefix)
 196                     self.parents[new_key] = prefix
 197                     break
 198
 199             else:
 200                 assert key in path
 201                 items[ word[0] ] = (None,0)
 202                 self.put_node(key,items)
 203                 break
 204
 205         # write
 206         s = (int_to_hex(value, 8) + int_to_hex(height,4)).decode('hex')
 207         self.db_tree.put(target, s)
 208         # the hash of a node is the txid
 209         _hash = target[20:52]
 210         self.update_node_hash(target, path, _hash, value)
 211
 212
 213     def update_node_hash(self, node, path, _hash, value):
 214         c = node
 215         for x in path[::-1]:
 216             self.parents[c] = x
 217             c = x
 218
 219         self.hash_list[node] = (_hash, value)
 220
 221
 222     def update_hashes(self):
 223
 224         nodes = {} # nodes to write
 225
 226         for i in range(KEYLENGTH, -1, -1):
 227
 228             for node in self.hash_list.keys():
 229                 if len(node) != i: continue
 230
 231                 node_hash, node_value = self.hash_list.pop(node)
 232
 233                 # for each node, compute its hash, send it to the parent
 234                 if node == '':
 235                     self.root_hash = node_hash
 236                     self.root_value = node_value
 237                     break
 238
 239                 parent = self.parents[node]
 240
 241                 # read parent.. do this in add_address
 242                 d = nodes.get(parent)
 243                 if d is None:
 244                     d = self.get_node(parent)
 245                     assert d is not None
 246
 247                 letter = node[len(parent)]
 248                 assert letter in d.keys()
 249
 250                 if i != KEYLENGTH and node_hash is None:
 251                     d2 = self.get_node(node)
 252                     node_hash, node_value = self.get_node_hash(node, d2, parent)
 253
 254                 assert node_hash is not None
 255                 # write new value
 256                 d[letter] = (node_hash, node_value)
 257                 nodes[parent] = d
 258
 259                 # iterate
 260                 grandparent = self.parents[parent] if parent != '' else None
 261                 parent_hash, parent_value = self.get_node_hash(parent, d, grandparent)
 262                 self.hash_list[parent] = (parent_hash, parent_value)
 263
 264
 265         # batch write modified nodes
 266         batch = self.db_tree.write_batch()
 267         for k, v in nodes.items():
 268             self.put_node(k, v, batch)
 269         batch.write()
 270
 271         # cleanup
 272         assert self.hash_list == {}
 273         self.parents = {}
 274
 275
 276     def get_node_hash(self, x, d, parent):
 277
 278         # final hash
 279         if x != '':
 280             skip_string = x[len(parent)+1:]
 281         else:
 282             skip_string = ''
 283
 284         d2 = sorted(d.items())
 285         values = map(lambda x: x[1][1], d2)
 286         hashes = map(lambda x: x[1][0], d2)
 287         value = sum( values )
 288         _hash = self.hash( skip_string + ''.join(hashes) )
 289         return _hash, value
 290
 291
 292     def get_path(self, target):
 293         word = target
 294         key = ''
 295         path = [ '' ]
 296         i = self.db_tree.iterator(start='')
 297
 298         while key != target:
 299
 300             i.seek(key + word[0])
 301             try:
 302                 new_key, _ = i.next()
 303                 is_child = new_key.startswith(key + word[0])
 304             except StopIteration:
 305                 is_child = False
 306
 307             if is_child:
 308
 309                 if target.startswith(new_key):
 310                     # add value to the child node
 311                     key = new_key
 312                     word = target[len(key):]
 313                     if key == target:
 314                         break
 315                     else:
 316                         assert key not in path
 317                         path.append(key)
 318                 else:
 319                     print_log('not in tree', self.db_tree.get(key+word[0]), new_key.encode('hex'))
 320                     return False
 321             else:
 322                 assert key in path
 323                 break
 324
 325         return path
 326
 327
 328     def delete_address(self, leaf):
 329         path = self.get_path(leaf)
 330         if path is False:
 331             print_log("addr not in tree", leaf.encode('hex'), self.key_to_address(leaf[0:20]), self.db_tree.get(leaf))
 332             raise
 333
 334         s = self.db_tree.get(leaf)
 335
 336         self.db_tree.delete(leaf)
 337         if leaf in self.hash_list:
 338             self.hash_list.pop(leaf)
 339
 340         parent = path[-1]
 341         letter = leaf[len(parent)]
 342         items = self.get_node(parent)
 343         items.pop(letter)
 344
 345         # remove key if it has a single child
 346         if len(items) == 1:
 347             letter, v = items.items()[0]
 348
 349             self.db_tree.delete(parent)
 350             if parent in self.hash_list:
 351                 self.hash_list.pop(parent)
 352
 353             # we need the exact length for the iteration
 354             i = self.db_tree.iterator()
 355             i.seek(parent+letter)
 356             k, v = i.next()
 357
 358             # note: k is not necessarily a leaf
 359             if len(k) == KEYLENGTH:
 360                  _hash, value = k[20:52], hex_to_int(v[0:8])
 361             else:
 362                 _hash, value = None, None
 363
 364             self.update_node_hash(k, path[:-1], _hash, value)
 365
 366         else:
 367             self.put_node(parent, items)
 368             _hash, value = None, None
 369             self.update_node_hash(parent, path[:-1], _hash, value)
 370
 371         return s
 372
 373
 374     def get_children(self, x):
 375         i = self.db_tree.iterator()
 376         l = 0
 377         while l <256:
 378             i.seek(x+chr(l))
 379             k, v = i.next()
 380             if k.startswith(x+chr(l)):
 381                 yield k, v
 382                 l += 1
 383             elif k.startswith(x):
 384                 yield k, v
 385                 l = ord(k[len(x)]) + 1
 386             else:
 387                 break
 388
 389
 390
 391
 392     def get_parent(self, x):
 393         """ return parent and skip string"""
 394         i = self.db_tree.iterator()
 395         for j in range(len(x)):
 396             p = x[0:-j-1]
 397             i.seek(p)
 398             k, v = i.next()
 399             if x.startswith(k) and x!=k:
 400                 break
 401         else: raise
 402         return k
 403
 404
 405     def hash(self, x):
 406         if DEBUG: return "hash("+x+")"
 407         return Hash(x)
 408
 409
 410     def get_root_hash(self):
 411         return self.root_hash
 412
 413
 414     def close(self):
 415         self.db_tree.close()
 416         self.db.close()
 417         self.db_hist.close()
 418         self.db_undo.close()
 419
 420
 421     def add_to_history(self, addr, tx_hash, tx_pos, value, tx_height):
 422         key = self.address_to_key(addr)
 423         txo = (tx_hash + int_to_hex(tx_pos, 4)).decode('hex')
 424
 425         # write the new history
 426         self.add_address(key + txo, value, tx_height)
 427
 428         # backlink
 429         self.db.put(txo, key)
 430
 431
 432
 433     def revert_add_to_history(self, addr, tx_hash, tx_pos, value, tx_height):
 434         key = self.address_to_key(addr)
 435         txo = (tx_hash + int_to_hex(tx_pos, 4)).decode('hex')
 436
 437         # delete
 438         self.delete_address(key + txo)
 439
 440         # backlink
 441         self.db.delete(txo)
 442
 443
 444
 445     def set_spent(self, addr, txi, txid, index, height, undo):
 446         key = self.address_to_key(addr)
 447         leaf = key + txi
 448
 449         s = self.delete_address(leaf)
 450         value = hex_to_int(s[0:8])
 451         in_height = hex_to_int(s[8:12])
 452         undo[leaf] = value, in_height
 453
 454         # delete backlink txi-> addr
 455         self.db.delete(txi)
 456
 457         # add to history
 458         s = self.db_hist.get(addr)
 459         if s is None: s = ''
 460         txo = (txid + int_to_hex(index,4) + int_to_hex(height,4)).decode('hex')
 461         s += txi + int_to_hex(in_height,4).decode('hex') + txo
 462         s = s[ -80*self.pruning_limit:]
 463         self.db_hist.put(addr, s)
 464
 465
 466
 467     def revert_set_spent(self, addr, txi, undo):
 468         key = self.address_to_key(addr)
 469         leaf = key + txi
 470
 471         # restore backlink
 472         self.db.put(txi, key)
 473
 474         v, height = undo.pop(leaf)
 475         self.add_address(leaf, v, height)
 476
 477         # revert add to history
 478         s = self.db_hist.get(addr)
 479         # s might be empty if pruning limit was reached
 480         if not s:
 481             return
 482
 483         assert s[-80:-44] == txi
 484         s = s[:-80]
 485         self.db_hist.put(addr, s)
 486
 487
 488
 489
 490
 491
 492     def import_transaction(self, txid, tx, block_height, touched_addr):
 493
 494         undo = { 'prev_addr':[] } # contains the list of pruned items for each address in the tx; also, 'prev_addr' is a list of prev addresses
 495
 496         prev_addr = []
 497         for i, x in enumerate(tx.get('inputs')):
 498             txi = (x.get('prevout_hash') + int_to_hex(x.get('prevout_n'), 4)).decode('hex')
 499             addr = self.get_address(txi)
 500             if addr is not None:
 501                 self.set_spent(addr, txi, txid, i, block_height, undo)
 502                 touched_addr.add(addr)
 503             prev_addr.append(addr)
 504
 505         undo['prev_addr'] = prev_addr
 506
 507         # here I add only the outputs to history; maybe I want to add inputs too (that's in the other loop)
 508         for x in tx.get('outputs'):
 509             addr = x.get('address')
 510             if addr is None: continue
 511             self.add_to_history(addr, txid, x.get('index'), x.get('value'), block_height)
 512             touched_addr.add(addr)
 513
 514         return undo
 515
 516
 517     def revert_transaction(self, txid, tx, block_height, touched_addr, undo):
 518         #print_log("revert tx", txid)
 519         for x in reversed(tx.get('outputs')):
 520             addr = x.get('address')
 521             if addr is None: continue
 522             self.revert_add_to_history(addr, txid, x.get('index'), x.get('value'), block_height)
 523             touched_addr.add(addr)
 524
 525         prev_addr = undo.pop('prev_addr')
 526         for i, x in reversed(list(enumerate(tx.get('inputs')))):
 527             addr = prev_addr[i]
 528             if addr is not None:
 529                 txi = (x.get('prevout_hash') + int_to_hex(x.get('prevout_n'), 4)).decode('hex')
 530                 self.revert_set_spent(addr, txi, undo)
 531                 touched_addr.add(addr)
 532
 533         assert undo == {}
 534