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_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)
  31         except:
  32             traceback.print_exc(file=sys.stdout)
  33             self.shared.stop()
  34
  35         self.db_version = 2 # increase this when database needs to be updated
  36         try:
  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)
  40         except:
  41             #traceback.print_exc(file=sys.stdout)
  42             print_log('initializing database')
  43             self.height = 0
  44             self.last_hash = '000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f'
  45             db_version = self.db_version
  46             # write root
  47             self.put_node('', {})
  48
  49         # check version
  50         if self.db_version != db_version:
  51             print_log("Your database '%s' is deprecated. Please create a new database"%self.dbpath)
  52             self.shared.stop()
  53             return
  54
  55
  56
  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)
  60
  61     def key_to_address(self, addr):
  62         return hash_160_to_bc_address(addr)
  63
  64
  65     def get_history(self, addr):
  66         addr = self.address_to_key(addr)
  67         x = self.db_addr.get(addr)
  68         if x is None:
  69             return ''
  70         try:
  71             _hash, v, h = x
  72             return h
  73         except:
  74             traceback.print_exc(file=sys.stdout)
  75             self.shared.stop()
  76             raise
  77
  78
  79     def get_address(self, txi):
  80         addr = self.db.get(txi)
  81         return self.key_to_address(addr) if addr else None
  82
  83
  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)
  87         return eval(s)
  88
  89
  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))
  93
  94
  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]:
  99                 index = i
 100                 break
 101         else:
 102             index = max_len
 103         return word1[0:index]
 104
 105
 106     def put_node(self, key, d, batch=None):
 107         k = 0
 108         serialized = ''
 109         for i in range(256):
 110             if chr(i) in d.keys():
 111                 k += 1<<i
 112                 h, v = d[chr(i)]
 113                 if h is None: h = chr(0)*32
 114                 vv = int_to_hex(v, 8).decode('hex')
 115                 item = h + vv
 116                 assert len(item) == 40
 117                 serialized += item
 118
 119         k = "0x%0.64X" % k # 32 bytes
 120         k = k[2:].decode('hex')
 121         assert len(k) == 32
 122         out = k + serialized
 123         if batch:
 124             batch.put(key, out)
 125         else:
 126             self.db_addr.put(key, out)
 127
 128
 129     def get_node(self, key):
 130
 131         s = self.db_addr.get(key)
 132         if s is None:
 133             return
 134
 135         #print "get node", key.encode('hex'), len(key), s.encode('hex')
 136
 137         k = int(s[0:32].encode('hex'), 16)
 138         s = s[32:]
 139         d = {}
 140         for i in range(256):
 141             if k % 2 == 1:
 142                 _hash = s[0:32]
 143                 value = hex_to_int(s[32:40])
 144                 d[chr(i)] = (_hash, value)
 145                 s = s[40:]
 146             k = k/2
 147
 148         #cache
 149         return d
 150
 151
 152     def add_address(self, target, value):
 153         assert len(target) == KEYLENGTH
 154
 155         word = target
 156         key = ''
 157         path = [ '' ]
 158         i = self.db_addr.iterator()
 159
 160         while key != target:
 161
 162             items = self.get_node(key)
 163
 164             if word[0] in items.keys():
 165
 166                 i.seek(key + word[0])
 167                 new_key, _ = i.next()
 168
 169                 if target.startswith(new_key):
 170                     # add value to the child node
 171                     key = new_key
 172                     word = target[len(key):]
 173                     if key == target:
 174                         break
 175                     else:
 176                         assert key not in path
 177                         path.append(key)
 178                 else:
 179                     # prune current node and add new node
 180                     prefix = self.common_prefix(new_key, target)
 181                     index = len(prefix)
 182
 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 } )
 189                     else:
 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) } )
 193
 194                     path.append(prefix)
 195                     self.parents[new_key] = prefix
 196                     break
 197
 198             else:
 199                 assert key in path
 200                 items[ word[0] ] = (None,0)
 201                 self.put_node(key,items)
 202                 break
 203
 204         # write
 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)
 210
 211
 212     def update_node_hash(self, node, path, _hash, value):
 213         c = node
 214         for x in path[::-1]:
 215             self.parents[c] = x
 216             c = x
 217
 218         self.hash_list[node] = (_hash, value)
 219
 220
 221     def update_hashes(self):
 222
 223         nodes = {} # nodes to write
 224
 225         for i in range(KEYLENGTH, -1, -1):
 226
 227             for node in self.hash_list.keys():
 228                 if len(node) != i: continue
 229
 230                 node_hash, node_value = self.hash_list.pop(node)
 231
 232                 # for each node, compute its hash, send it to the parent
 233                 if node == '':
 234                     self.root_hash = node_hash
 235                     self.root_value = node_value
 236                     break
 237
 238                 parent = self.parents[node]
 239
 240                 # read parent.. do this in add_address
 241                 d = nodes.get(parent)
 242                 if d is None:
 243                     d = self.get_node(parent)
 244                     assert d is not None
 245
 246                 letter = node[len(parent)]
 247                 assert letter in d.keys()
 248
 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)
 252
 253                 assert node_hash is not None
 254                 # write new value
 255                 d[letter] = (node_hash, node_value)
 256                 nodes[parent] = d
 257
 258                 # iterate
 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)
 262
 263
 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)
 268         batch.write()
 269
 270         # cleanup
 271         assert self.hash_list == {}
 272         self.parents = {}
 273
 274
 275     def get_node_hash(self, x, d, parent):
 276
 277         # final hash
 278         if x != '':
 279             skip_string = x[len(parent)+1:]
 280         else:
 281             skip_string = ''
 282
 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) )
 288         return _hash, value
 289
 290
 291     def get_path(self, target):
 292         word = target
 293         key = ''
 294         path = [ '' ]
 295         i = self.db_addr.iterator(start='')
 296
 297         while key != target:
 298
 299             i.seek(key + word[0])
 300             try:
 301                 new_key, _ = i.next()
 302                 is_child = new_key.startswith(key + word[0])
 303             except StopIteration:
 304                 is_child = False
 305
 306             if is_child:
 307
 308                 if target.startswith(new_key):
 309                     # add value to the child node
 310                     key = new_key
 311                     word = target[len(key):]
 312                     if key == target:
 313                         break
 314                     else:
 315                         assert key not in path
 316                         path.append(key)
 317                 else:
 318                     print_log('not in tree', self.db_addr.get(key+word[0]), new_key.encode('hex'))
 319                     return False
 320             else:
 321                 assert key in path
 322                 break
 323
 324         return path
 325
 326
 327     def delete_address(self, leaf):
 328         path = self.get_path(leaf)
 329         if path is False:
 330             print_log("addr not in tree", leaf.encode('hex'), self.key_to_address(leaf[0:20]), self.db_addr.get(leaf))
 331             raise
 332
 333         self.db_addr.delete(leaf)
 334         if leaf in self.hash_list:
 335             self.hash_list.pop(leaf)
 336
 337         parent = path[-1]
 338         letter = leaf[len(parent)]
 339         items = self.get_node(parent)
 340         vv = items.pop(letter)
 341
 342         # remove key if it has a single child
 343         if len(items) == 1:
 344             letter, v = items.items()[0]
 345
 346             self.db_addr.delete(parent)
 347             if parent in self.hash_list:
 348                 self.hash_list.pop(parent)
 349
 350             # we need the exact length for the iteration
 351             i = self.db_addr.iterator()
 352             i.seek(parent+letter)
 353             k, v = i.next()
 354
 355             # note: k is not necessarily a leaf
 356             if len(k) == KEYLENGTH:
 357                  _hash, value = k[20:52], hex_to_int(v)
 358             else:
 359                 _hash, value = None, None
 360
 361             self.update_node_hash(k, path[:-1], _hash, value)
 362
 363         else:
 364             self.put_node(parent, items)
 365             _hash, value = None, None
 366             self.update_node_hash(parent, path[:-1], _hash, value)
 367
 368         return vv
 369
 370
 371     def get_children(self, x):
 372         i = self.db_addr.iterator()
 373         l = 0
 374         while l <256:
 375             i.seek(x+chr(l))
 376             k, v = i.next()
 377             if k.startswith(x+chr(l)):
 378                 yield k, v
 379                 l += 1
 380             elif k.startswith(x):
 381                 yield k, v
 382                 l = ord(k[len(x)]) + 1
 383             else:
 384                 break
 385
 386
 387
 388
 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)):
 393             p = x[0:-j-1]
 394             i.seek(p)
 395             k, v = i.next()
 396             if x.startswith(k) and x!=k:
 397                 break
 398         else: raise
 399         return k
 400
 401
 402     def hash(self, x):
 403         if DEBUG: return "hash("+x+")"
 404         return Hash(x)
 405
 406
 407     def get_root_hash(self):
 408         return self.root_hash
 409
 410
 411     def close(self):
 412         self.db_addr.close()
 413         self.db.close()
 414         self.db_undo.close()
 415
 416
 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')
 420
 421         # write the new history
 422         self.add_address(key + txo, value)
 423
 424         # backlink
 425         self.db.put(txo, key)
 426
 427
 428
 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')
 432
 433         # delete
 434         self.delete_address(key + txo)
 435
 436         # backlink
 437         self.db.delete(txo)
 438
 439
 440
 441     def set_spent(self, addr, txi, txid, index, height, undo):
 442         key = self.address_to_key(addr)
 443         leaf = key + txi
 444
 445         _hash, value = self.delete_address(leaf)
 446         undo[leaf] = value
 447
 448         # delete backlink txi-> addr
 449         self.db.delete(txi)
 450
 451
 452
 453     def revert_set_spent(self, addr, txi, undo):
 454         key = self.address_to_key(addr)
 455         leaf = key + txi
 456
 457         # restore backlink
 458         self.db.put(txi, key)
 459
 460         v = undo.pop(leaf)
 461         self.add_address(leaf, v)
 462
 463
 464
 465
 466
 467
 468
 469     def import_transaction(self, txid, tx, block_height, touched_addr):
 470
 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
 472
 473         prev_addr = []
 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)
 477             if addr is not None:
 478                 self.set_spent(addr, txi, txid, i, block_height, undo)
 479                 touched_addr.add(addr)
 480             prev_addr.append(addr)
 481
 482         undo['prev_addr'] = prev_addr
 483
 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)
 490
 491         return undo
 492
 493
 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)
 501
 502         prev_addr = undo.pop('prev_addr')
 503         for i, x in enumerate(tx.get('inputs')):
 504             addr = prev_addr[i]
 505             if addr is not None:
 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)
 509
 510         assert undo == {}
 511