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