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