3

Recently I started analyzing the UTXO set data that every full node stores in chainstate folder (a LevelDB database).

By looking into the code you can learn more or less how the data entries are formatted. However, to save as much space as possible, some of the data is compressed and encoded as a varint.

How data is compressed can be found and also analyzed in the code. However, I'm struggling with understanding how the varint encoding/decoding is performed. According to the developers guide, the class responsible to do so is CVarint, and I've been able to trace down the method that I think is doing so. However, since I don't know the format the data is encoded I'm not able to understand what it is doing.

Does someone have a clue about how the stored data is formatted?

Clarification: I'm referring to the CVarint format that is used in UTXOs along the Bitcoin Core, not to the varint format that is used to encode information in txs scripts.

2 Answers 2

3

The CVarInt format is implemented in serialize.h

As the comment is extensive, I'll just quote it here:

Variable-length integers: bytes are a MSB base-128 encoding of the number. The high bit in each byte signifies whether another digit follows. To make sure the encoding is one-to-one, one is subtracted from all but the last digit. Thus, the byte sequence a[] with length len, where all but the last byte has bit 128 set, encodes the number:

(a[len-1] & 0x7F) + sum(i=1..len-1, 128^i*((a[len-i-1] & 0x7F)+1))

Properties:

  • Very small (0-127: 1 byte, 128-16511: 2 bytes, 16512-2113663: 3 bytes)
  • Every integer has exactly one encoding
  • Encoding does not depend on size of original integer type
  • No redundancy: every (infinite) byte sequence corresponds to a list of encoded integers.

Examples:

  • 0: [0x00]
  • 1: [0x01]
  • 127: [0x7F]
  • 128: [0x80 0x00]
  • 255: [0x80 0x7F]
  • 256: [0x81 0x00]
  • 16383: [0xFE 0x7F]
  • 16384: [0xFF 0x00]
  • 16511: [0xFF 0x7F]
  • 65535: [0x82 0xFE 0x7F]
  • 2^32: [0x8E 0xFE 0xFE 0xFF 0x00]

To store CAmount values (integers representing numbers of satoshis), a transformation is applied beforehand that turns more common numbers (multiples of powers of 10) into smaller numbers first:

  • If the amount is 0, output 0.
  • Otherwise, divide the amount (in base units) by the largest power of 10 possible; call the exponent e (e is max 9)
  • If e<9, the last digit of the resulting number cannot be 0; store it as d, and drop it (divide by 10), calling the result n. Then, output 1 + 10*(9*n + d - 1) + e
  • If e==9, we only know the resulting number is not zero, so output 1 + 10*(n - 1) + 9
1
  • My bad, I didn't see the comment right above the method.
    – sr_gi
    Feb 25, 2017 at 9:04
0
MyByteArray& MyByteArray::putVarInt ( const unsigned value )
{
  return ( value < 0xFD )    ? putInt8 ( value ) :
         ( value <= 0xFFFF ) ? putInt8 ( 0xFD ).putInt16 ( value ) :
                               putInt8 ( 0xFE ).putInt32 ( value );
}

little-endian encoding

MyByteArray& MyByteArray::putPush ( const QByteArray& value )
{
  if ( value.size ( ) < OP_PUSHDATA1 )
    return putInt8 ( value.size ( ) ).putArray ( value );
  if ( value.size ( ) <= 0xFF )
    return putInt8 ( OP_PUSHDATA1 ).putInt8 ( value.size ( ) ).putArray ( value );
  return putInt8 ( OP_PUSHDATA2 ).putInt16 ( value.size ( ) ).putArray ( value );
}
5
  • But this is the one that is used in transactions, for example when encoding the number of inputs, or outputs. Is it the same that is used when storing the compacted satoshis amount of an UTXO into the LevelDB?
    – sr_gi
    Feb 24, 2017 at 16:23
  • answer updated with a method for serializing data in scripts. satoshis in utxo are atored as little-endian 64-bit value, not compacted
    – amaclin
    Feb 24, 2017 at 16:27
  • Still wrong. He's asking about the CVarInt used in UTXOs internally in Bitcoin Core. Not the variable-length push in scripts, or the CCompactLen used in the P2P protocol. Feb 24, 2017 at 17:31
  • Exactly, I'm familiar with the varint encoding used in serialized txs but not with the one used in the LevelDB.
    – sr_gi
    Feb 24, 2017 at 17:46
  • Oups, sorry. My bad English understanding. I am not familar with Bitcoin Core sources and its internal structures. Of course, my answer was about bitcoin protocol itself
    – amaclin
    Feb 24, 2017 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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