Research lab Ink & Switch published bijou64, a variable-length integer encoding where every number maps to exactly one byte representation. Designed to eliminate signature-malleability bugs in their Subduction sync protocol, the format avoids canonicality validation logic by construction while decoding up to ten times faster than LEB128.

Research lab Ink & Switch has released bijou64, a variable-length integer (varint) encoding designed so every integer maps to a single valid byte sequence. Developed by Brooklyn Zelenka, the design removes the class of canonicality bugs that frequently affect binary protocols while outperforming standard scalar LEB128 decoders in benchmarks.

Traditional varints like LEB128 divide integers into 7-bit chunks with a continuation bit on each byte. This allows multiple valid byte sequences for the same number (e.g., zero can be encoded as 0x00 or 0x80 0x00). In systems using cryptographic signatures, content addressing, or distributed consensus, these redundant encodings create an attack surface. While specifications mandate that decoders reject non-canonical inputs, Zelenka notes that developers frequently omit or optimize away these separate validation checks, leading to security flaws similar to historic vulnerabilities in PKCS#1 v1.5, GnuTLS, and Bitcoin transaction malleability.

Bijou64 addresses this by making alternative encodings impossible at the structural level. As Zelenka frames it in the post:

This is the bug class bijou64 is designed to make impossible. Not by adding more checks, but by removing the one that mattered, and making the format such that, with no canonicality check at all, the only encoding that exists for any given value is the canonical one.

The design relies on two main structural mechanics:

  • Direct Values (0–247): An initial byte in this range represents the integer value directly without extra metadata.
  • Tag Bytes and Offsets (248–255): Bytes in this range signal how many payload bytes follow. Each length tier adds a fixed constant offset so lower values cannot be padded into larger byte tiers.

Because the payload is a contiguous big-endian integer, compilers can turn decoding into a single load and byte swap. On x86 and ARM hardware, bijou64 decodes small numbers roughly twice as fast as LEB128 and larger numbers 8 to 10 times faster by avoiding LEB128's bit-masking and branch-thrashing continuation bit scans.

Community reaction on Hacker News raised several trade-offs regarding the format. One commenter, drawing on benchmarking from the BONJSON format, argued that comparing against scalar decoders misses where high-performance parsing has moved:

Testing proved that when you move to SIMD instructions, ULEB128 or sentinel values win every time because of the parallelization opportunities. The true irony is that even SIMD text parsing would outperform this! SIMD is that powerful.

Another commenter, dzaima, questioned the core security claim, pointing out that bijou64 narrows the checked boundary surface rather than eliminating runtime validation entirely:

Forgetting to do the range check on the first_byte==255 case and just letting it do 64-bit wraparound is exactly as much of a plausible bug as missing range checks on LEB128. In a sense, bijou64 could perhaps even be more problematic: it invites not doing any range checks for the smaller inputs because they obviously don't need it, and so you can just forget to special-case the max length case.

Additional feedback highlighted that non-canonical formats like LEB128 are intentionally used by linkers in WebAssembly and DWARF to pad unlinked references for in-place patching, showing that variable padding remains a deliberate requirement for specific toolchains.

The reference bijou64 implementation is available in Rust on crates.io under dual MIT/Apache 2.0 licenses, alongside JavaScript wrappers on npm and community ports in Elixir, Go, Perl, and Java. Width variants bijou32 and bijou128 are also covered in the specification.

About the Author

Steef-Jan Wiggers