Subduction Protocol Developers Introduce Bijou64 to Resolve Varint Security Flaws

Developers working on the Subduction CRDT sync protocol have introduced bijou64, a variable-length integer encoding designed to ensure canonical representation for security purposes. The format was created to resolve signature-verification bugs by ensuring each integer has only one unique byte representation, eliminating the ambiguity found in formats like LEB128. Benchmarks on Apple M2 Pro and AMD Zen 5 processors indicate that bijou64 decodes approximately two to ten times faster than the widely used LEB128 standard. This performance gain is attributed to bijou64’s structure, which allows decoders to determine byte length immediately without scanning for continuation bits, thereby improving branch prediction efficiency. The library is available on crates.io under dual MIT and Apache-2.0 licences.

The primary motivation for bijou64 was to address security vulnerabilities inherent in previous varint standards, particularly those arising from non-canonical encodings. In formats such as LEB128, numbers can be represented in multiple ways, leading to potential signature-verification failures where different byte strings decode to the same value. Bijou64 eliminates this risk by ensuring that every integer has a single, unique byte representation, similar to standard decimal notation. This design prevents adversarial inputs from exploiting encoding ambiguities, a pattern that has historically affected protocols relying on ASN.1 and other legacy standards.

Bijou64 utilises a first-byte tag system to achieve this structural safety. The first byte represents values from 0 to 247 directly, while bytes 248 to 255 act as tags indicating how many subsequent bytes follow. This approach allows the decoder to determine the total byte length immediately, enabling O(1) memory allocation. In contrast, LEB128 requires the decoder to scan each byte for continuation bits until a terminator is found, a process that forces the CPU to mask and shift data repeatedly. Bijou64 offsets subsequent bytes by 248 to guarantee canonicity, ensuring that values like 248 are not confused with zero.

Performance benchmarks conducted on Apple M2 Pro and AMD Zen 5 processors demonstrate significant efficiency gains for the new format. Bijou64 decodes approximately two to ten times faster than LEB128, with the disparity widening for larger numbers that require extensive continuation-bit scanning in the older standard. On a uniform full-u64 distribution, bijou64 processed a batch of 4096 values in approximately three microseconds, compared to thirty microseconds for LEB128. The encoding’s design allows modern CPUs to leverage byte-swap instructions and stable branch prediction, resulting in consistent performance with minimal variance.

The bijou64 library is now available on crates.io under dual MIT and Apache-2.0 licences, with a Wasm/JavaScript wrapper also existing. The specification is published under CC BY-SA 4.0, and the developers invite feedback on workloads where the format might underperform. While LEB128 remains a mature and widely adopted standard, bijou64 offers a structurally safer alternative for applications where canonicality is critical, such as in digital signatures and content-addressing systems. The authors note that while the format is new, its arithmetic design results in fewer instructions in the hot path on modern hardware, making it a compelling option for new protocol designs.