I know that Bitcoin Core uses LevelDB since 0.8 version. However, I couldn't find detailed explanation about how Bitcoin stores and retrieves from LevelDB. E.g. If B transaction uses an output from previous transaction A as input, how does Bitcoin lookup this transaction and see if it's spent? After transaction B is spent, how does this transaction get updated?

up vote 9 down vote accepted

In the specific example you asked, it does so by querying the LevelDB located in ./bitcoin/chainstate (there is where the UTXO set is stored).

UTXOs are identified by its txid (Little Endian representation) leaded by a c.

Example

Transaction

246c5a81b6ad0dfc0dbc0b2ff5bde65ee1913f75a47d409b8ff8074a27ec1000

is identified in the LevelDB by:

c0010ec274a07f88f9b407da4753f91e15ee6bdf52f0bbc0dfc0dadb6815a6c24

or what is the same:

630010ec274a07f88f9b407da4753f91e15ee6bdf52f0bbc0dfc0dadb6815a6c24

since the hex representation of 'c' is 63. Notice that when you query the database you should not do it using the string representation of the value, but the byte array one.

Each entry in the LevelDB contains two values, the identifier (explained avobe and used to query the data), and the value.

The value of each entry (the UTXO) is encoded in the LevelDB following the structure that follows (extracted from this comment from the source code):

  • Serialized format
    • VARINT(nVersion)
    • VARINT(nCode)
    • unspentness bitvector, for vout[2] and further; least significant byte first
    • the non-spent CTxOuts (via CTxOutCompressor)
    • VARINT(nHeight)
    • The nCode value consists of:
      • bit 1: IsCoinBase()
      • bit 2: vout[0] is not spent
      • bit 4: vout[1] is not spent
      • The higher bits encode N, the number of non-zero bytes in the following bitvector.
      • In case both bit 2 and bit 4 are unset, they encode N-1, as there must be at least one non-spent output).

You can find a better formated explanation and examples in the source code from the provided link.

Notice that, since chainstate database used to trigger anti-virus software, as you can check in this issue and in this question, the first lines of the chainstate contains the obfuscation key, a 64-bit value identified by 0e00obfuscation_key that should be XORed with each data value from the database. To do so, the key is concatenated with itself until it reaches the length of the obfuscated value.

Example

Lets o_k = '27c78118b7316105' be our obfuscation key, and

{"key": "63000002f414665fb03389dd19776732bf90883bcb399d23323747596e98dd1801", "value": "26c326d7353661dc7005d274976f458691f24f0f05d141335f4ad5927e41"}

be one entry from the database. As you can see, value does not follow the above introduced format, since it is obfuscated. value is 60 characters long, so if we extend the obsfuscation key since it reaches the same length, we get:

27c78118b731610527c78118b731610527c78118b731610527c78118b731

Now, if we perform the XOR between the value and the key:

26c326d7353661dc7005d274976f458691f24f0f05d141335f4ad5927e41 XOR 27c78118b731610527c78118b731610527c78118b731610527c78118b731  

We obtain:

01028820010b2a00367244680f6da18acd861a08f0a89cb3b49ab50e

That matches with the previous stated format, and it's indeed the UTXO value identified by 63000002f414665fb03389dd19776732bf90883bcb399d23323747596e98dd1801.

  • Thanks. Finally I figured out that Bitcoin uses LevelDB to save the transaction index, which uses the transaction hash as key and file position as value. The actual binary transaction data are stored in the block files. – Yangrui Mar 17 '17 at 21:46
  • @Yangrui That used to be how Bitcoin Core worked up to version 0.7.x. As of 0.8.0, there is no transaction index at all anymore, and only a database with a copy of the unspent transaction outputs. This means no disk lookup for the actual transaction is needed anymore, and we're able to support pruning (deleting the actual block data from disk after validation). – Pieter Wuille Mar 27 '17 at 18:58
  • 1
    Thanks Pieter. So if a transaction is spent, is it just removed from the UTXO db right away? – Yangrui Mar 28 '17 at 20:03
  • For future travelers like me, the key for chainstate is not an ascii 0e00obfuscation_key, but a hex \x0e\x00obfuscate_key (as of v0.15.0.1) – num1 Apr 10 at 1:09
  • \x0e and \x00 indicate 0e and 00 hex respectively. – sr-gi Apr 10 at 2:04

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.