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