<p>The CVarInt format is implemented in <a href="https://github.com/bitcoin/bitcoin/blob/v0.13.2/src/serialize.h#L307L372" rel="nofollow noreferrer">serialize.h</a></p>

<p>As the comment is extensive, I'll just quote it here:</p>

<blockquote>
  <p>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:</p>
  
  <p>(a[len-1] &amp; 0x7F) + sum(i=1..len-1, 128^i*((a[len-i-1] &amp; 0x7F)+1))</p>
  
  <p>Properties:</p>
  
  <ul>
  <li>Very small (0-127: 1 byte, 128-16511: 2 bytes, 16512-2113663: 3 bytes)</li>
  <li>Every integer has exactly one encoding</li>
  <li>Encoding does not depend on size of original integer type</li>
  <li>No redundancy: every (infinite) byte sequence corresponds to a list of encoded integers.</li>
  </ul>
  
  <p>Examples:</p>
  
  <ul>
  <li>0: [0x00]</li>
  <li>1: [0x01]</li>
  <li>127: [0x7F]</li>
  <li>128: [0x80 0x00]</li>
  <li>255: [0x80 0x7F]</li>
  <li>256: [0x81 0x00]</li>
  <li>16383: [0xFE 0x7F]</li>
  <li>16384: [0xFF 0x00]</li>
  <li>16511: [0xFF 0x7F]</li>
  <li>65535: [0x82 0xFE 0x7F]</li>
  <li>2^32: [0x8E 0xFE 0xFE 0xFF 0x00]</li>
  </ul>
</blockquote>

<p>To store CAmount values (integers representing numbers of satoshis), a <a href="https://github.com/bitcoin/bitcoin/blob/v0.13.2/src/compressor.cpp#L133#L185" rel="nofollow noreferrer">transformation is applied</a> beforehand that turns more common numbers (multiples of powers of 10) into smaller numbers first:</p>

<ul>
<li>If the amount is 0, output 0.</li>
<li>Otherwise, divide the amount (in base units) by the largest power of 10 possible; call the exponent e (e is max 9)</li>
<li>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</li>
<li>If e==9, we only know the resulting number is not zero, so output 1 + 10*(n - 1) + 9</li>
</ul>

CC BY-SA 3.0
2017-02-25T09:04:24.183Z
My bad, I didn't see the comment right above the method.
sr_gi
CC BY-SA 3.0
2017-02-25T01:40:13.043Z
2017-02-25T01:40:13.043Z
Pieter Wuille
<pre><code>MyByteArray&amp; MyByteArray::putVarInt ( const unsigned value )
{
  return ( value &lt; 0xFD )    ? putInt8 ( value ) :
         ( value &lt;= 0xFFFF ) ? putInt8 ( 0xFD ).putInt16 ( value ) :
                               putInt8 ( 0xFE ).putInt32 ( value );
}
</code></pre>

<p>little-endian encoding</p>

<pre><code>MyByteArray&amp; MyByteArray::putPush ( const QByteArray&amp; value )
{
  if ( value.size ( ) &lt; OP_PUSHDATA1 )
    return putInt8 ( value.size ( ) ).putArray ( value );
  if ( value.size ( ) &lt;= 0xFF )
    return putInt8 ( OP_PUSHDATA1 ).putInt8 ( value.size ( ) ).putArray ( value );
  return putInt8 ( OP_PUSHDATA2 ).putInt16 ( value.size ( ) ).putArray ( value );
}
</code></pre>

CC BY-SA 3.0
2017-02-24T16:23:21.853Z
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
CC BY-SA 3.0
2017-02-24T16:27:01.500Z
answer updated with a method for serializing data in scripts. satoshis in utxo are atored as little-endian 64-bit value, not compacted
amaclin
CC BY-SA 3.0
2017-02-24T17:31:28.387Z
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.
Pieter Wuille
CC BY-SA 3.0
2017-02-24T17:46:51.387Z
Exactly, I'm familiar with the varint encoding used in serialized txs but not with the one used in the LevelDB.
sr_gi
CC BY-SA 3.0
2017-02-24T18:55:20.747Z
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
CC BY-SA 3.0
2017-02-24T16:14:51.603Z
2017-02-24T16:26:07.967Z
2017-02-24T16:26:07.967Z
amaclin
<p>Recently I started analyzing the UTXO set data that every full node stores in <code>chainstate</code> folder (a <code>LevelDB</code> database).</p>

<p>By looking into the <a href="https://github.com/bitcoin/bitcoin/blob/7dac1e5e9e887f5f6ff146e812a05bd3bf281eae/src/coins.h" rel="nofollow noreferrer">code</a> 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 <code>varint</code>.</p>

<p>How data is compressed can be found and also analyzed in the <a href="https://github.com/bitcoin/bitcoin/blob/7dac1e5e9e887f5f6ff146e812a05bd3bf281eae/src/coins.h#L23" rel="nofollow noreferrer">code</a>. However, I'm struggling with understanding how the varint encoding/decoding is performed. According to the <a href="https://bitcoin.org/en/developer-reference#raw-transaction-format" rel="nofollow noreferrer">developers guide</a>, the <a href="https://github.com/bitcoin/bitcoin/blob/c0ddd32bf629bb48426b0651def497ca1a78e6b1/src/serialize.h#L393" rel="nofollow noreferrer">class responsible</a> to do so is <code>CVarint</code>, and I've been able to trace down the <a href="https://github.com/bitcoin/bitcoin/blob/c0ddd32bf629bb48426b0651def497ca1a78e6b1/src/serialize.h" rel="nofollow noreferrer">method</a> 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.</p>

<p>Does someone have a clue about how the stored data is formatted?</p>

<p>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. </p>

<bitcoin-core-development><utxo><leveldb><encoding>
CVarint serialization format
sr_gi
# CVarint serialization format

(Asked by: username_0 on 2017-02-24)

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

By looking into the [code](https://github.com/bitcoin/bitcoin/blob/7dac1e5e9e887f5f6ff146e812a05bd3bf281eae/src/coins.h) 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](https://github.com/bitcoin/bitcoin/blob/7dac1e5e9e887f5f6ff146e812a05bd3bf281eae/src/coins.h#L23). However, I'm struggling with understanding how the varint encoding/decoding is performed. According to the [developers guide](https://bitcoin.org/en/developer-reference#raw-transaction-format), the [class responsible](https://github.com/bitcoin/bitcoin/blob/c0ddd32bf629bb48426b0651def497ca1a78e6b1/src/serialize.h#L393) to do so is `CVarint`, and I've been able to trace down the [method](https://github.com/bitcoin/bitcoin/blob/c0ddd32bf629bb48426b0651def497ca1a78e6b1/src/serialize.h) 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.

**Tags:** bitcoin-core-development, utxo, leveldb, encoding


---

## 2 answers

### Answer by username_1 on 2017-02-25. Score: 3 | Accepted answer

The CVarInt format is implemented in [serialize.h](https://github.com/bitcoin/bitcoin/blob/v0.13.2/src/serialize.h#L307L372)

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](https://github.com/bitcoin/bitcoin/blob/v0.13.2/src/compressor.cpp#L133#L185) 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

> **Comments:**
> **username_0**: My bad, I didn't see the comment right above the method.  

---

### Answer by username_2 on 2017-02-24. Score: 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 );
}

> **Comments:**
> **username_0**: 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?  
> **username_2**: answer updated with a method for serializing data in scripts. satoshis in utxo are atored as little-endian 64-bit value, not compacted  
> **username_1**: 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.  
> **username_0**: Exactly, I'm familiar with the varint encoding used in serialized txs but not with the one used in the LevelDB.  
> **username_2**: 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  

---

