What is the different between CompactSize and VarInt encoding?

Question

Pieter Wuille's definition of CompactSize encoding seems to match Greg Walker's definition of VarInt encoding, yet the BitcoinWiki claims that CompactSize is not to be confused with VarInt.

What, if any, are the differences between the two encodings? Or are they simply the same thing?

Answer 1

There are two distinct variable-length integer encodings implemented in Bitcoin Core's serialization framework:

1. The encoding used in the P2P protocol for the lengths of vectors (number of transactions in blocks, number of inputs/outputs in transactions, number of entries in inv/addr messages, ...) is known inside the Bitcoin Core codebase as the "CompactSize" encoding, though it has historically been referred to in external protocol documentation as "VarInt".
2. Another encoding which is only used internally in Bitcoin Core, in e.g. its UTXO database on disk, but isn't used anywhere in the P2P protocol. This is referred to inside the Bitcoin Core codebase as "VarInt".

For reference, the two encodings are:

1. The "CompactSize" encoding (also known as "VarInt" outside Bitcoin Core):

• 0..0xfc: 1 byte (the value itself)
• 0xfd..0xffff: 3 bytes (0xfd + 2 byte little endian encoding)
• 0x10000..0xffffffff: 5 bytes (0xfe + 4 byte little endian encoding)
• 0x100000000..0xffffffffffffffff: 9 bytes (0xff + 8 byte little endian encoding)

2. The "VarInt" encoding (not used outside Bitcoin Core) is described inside the codebase as follows:

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))

It results in the following sizes:

• 0..0x7f: 1 byte
• 0x80..0x407f: 2 bytes
• 0x4080..0x20407f: 3 bytes
• 0x204080..0x1020407f: 4 bytes
• 0x10204080..0x81020407f: 5 bytes
• ...