Bijou64: Solving the Canonicality Problem in Variable-Length Integer Encoding
In the world of binary protocols, encoding integers efficiently is a constant balancing act. Most developers reach for variable-length integer encodings (varints) to ensure that small numbers don't waste 8 bytes of space. However, a subtle but dangerous flaw exists in many of these designs: the lack of structural canonicality.
When a single value can be represented by multiple different byte sequences, security vulnerabilities emerge—particularly in signed protocols. If a system verifies a signature based on the bytes of a message, but the decoder treats different byte sequences as the same value, an attacker can alter the message bytes without changing the logical value, potentially bypassing security checks or causing malleability issues. This is the core problem that bijou64 was designed to solve.
The Flaw in LEB128
To understand bijou64, one must first look at the industry standard: LEB128. LEB128 encodes numbers in 7-bit segments, using the high bit of each byte as a "continuation bit" to signal that more bytes follow.
While practical, LEB128 is not canonical by construction. For example, the number 0 can be encoded as 0x00, but it can also be encoded as 0x80 0x00 or 0x80 0x80 0x00. Most decoders will happily accept any of these as zero. This non-canonicality has led to real-world vulnerabilities in critical systems, including ASN.1, X.509 certificates, and Bitcoin transactions.
Traditionally, the fix is to enforce a "canonical form" via runtime checks in the decoder. But as the authors of bijou64 point out, these checks are often omitted, optimized away, or forgotten during porting, leading to silent security degradation.
How Bijou64 Achieves Canonicality
Bijou64 eliminates the possibility of multiple encodings per integer by using two primary mechanisms: first-byte tagging and offsets.
1. First Byte Double Duty
In bijou64, the first byte serves two purposes. For values between 0 and 247, the first byte is the value. For values 248 and above, the first byte acts as a tag that specifies exactly how many subsequent bytes follow.
This provides an immediate performance win: the decoder knows the exact memory allocation required in $O(1)$ time, whereas LEB128 must scan continuation bits in $O(n)$ time.
2. The Offset Trick
To prevent a number like 0 from being represented as both a single byte (0x00) and a tagged sequence (e.g., 0xF8 0x00), bijou64 employs offsets. Instead of the tagged bytes representing the number starting from zero, they are offset by a value that ensures they never overlap with the range of the previous tier.
For example, if the tag indicates a 2-byte sequence, the value is offset by 248 (0xF8). This ensures that the smallest possible 2-byte encoding represents 248, not 0. This pattern continues predictably for larger integers, creating a lookup table of offsets based on the first byte.
Performance Benchmarks
Surprisingly, designing for security also yielded significant performance gains. Benchmarks on ARM (Apple M2 Pro) and x86 (AMD Zen 5) show that bijou64 is often substantially faster than LEB128.
- Decoding Speed: Bijou64 is roughly 2–10 times faster than LEB128. For large
u64distributions, it can process batches of 4096 values in ~3 $\mu$s, compared to LEB128's ~30 $\mu$s. - Consistency: Because bijou64 avoids the unpredictable branch patterns of continuation-bit scanning, its performance is highly consistent (represented by nearly vertical CDF curves in the benchmarks).
- Encoding Speed: While LEB128 is slightly faster for a specific "small" distribution (248 – 65,535), bijou64 generally outperforms it elsewhere.
These gains stem from the use of contiguous big-endian payloads, which allow modern CPUs to use a single load and a bswap instruction, rather than the masking and shifting required by LEB128's 7-bit layout.
Critical Perspectives and Trade-offs
While the benchmarks are impressive, the community has raised several important counterpoints:
SIMD and Parallelization
One contributor noted that while bijou64 is fast for scalar operations, it may struggle against LEB128 or sentinel-based encodings when using SIMD (Single Instruction, Multiple Data) instructions. Parallelization opportunities often favor formats that can be processed in bulk without the strict dependency on a leading tag byte.
Space Efficiency
LEB128 is more compact for certain ranges. For instance, LEB128 stays at 2 bytes for values up to $2^{14}$, whereas bijou64's 2-byte range is much smaller (up to 500). For protocols where every byte is critical and values frequently fall in this mid-range, LEB128 may be preferable.
The "Linking" Use Case
In some environments, such as DWARF or WASM, non-canonical encodings are actually a feature. Compilers often emit the widest possible varint (e.g., 5 bytes for LEB128) as a placeholder for symbols whose final address isn't known until linking. If the encoding were strictly canonical, the linker would have to shift all subsequent code every time a varint's width changed, triggering a cascade of re-computations.
Conclusion
Bijou64 represents a shift in philosophy: instead of adding checks to a flawed format, it changes the format to make the flaw impossible. For developers building new protocols where signatures, content-addressing, or strict agreement between implementations are required, bijou64 offers a structurally safer and generally faster alternative to LEB128.