CVarint serialization format 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.
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] &amp; 0x7F) + sum(i=1..len-1, 128^i*((a[len-i-1] &amp; 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&lt;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