Ink & Switch Releases Bijou64, a Canonical Variable-Length Integer Encoding

Introduction of Bijou64

Research lab Ink & Switch has released bijou64, a new variable-length integer (varint) encoding. This format is designed to ensure that every integer maps to exactly one byte representation, which helps to eliminate a class of security bugs known as signature-malleability.

Addressing Canonicality Bugs

Traditional varint encodings, such as LEB128, can represent the same number with multiple valid byte sequences. For example, zero can be encoded as 0x00 or 0x80 0x00. In systems relying on cryptographic signatures, content addressing, or distributed consensus, these redundant encodings create an attack surface. While specifications often require decoders to reject non-canonical inputs, developers frequently omit or optimize these validation checks, leading to vulnerabilities similar to those seen in PKCS#1 v1.5, GnuTLS, and Bitcoin transaction malleability.

Bijou64's Design Solution

Bijou64 prevents alternative encodings at a structural level, making it impossible for a value to have more than one valid byte sequence. This design removes the need for explicit canonicality validation checks, as the format inherently ensures canonicality. The encoding uses direct values for numbers 0-247 and tag bytes (248-255) to indicate the number of subsequent payload bytes, with fixed constant offsets to prevent padding into larger byte tiers.

Performance Improvements

The design of bijou64 also offers significant performance benefits. Compilers can optimize decoding into a single load and byte swap due to the contiguous big-endian integer payload. Benchmarks show that bijou64 decodes small numbers approximately twice as fast as LEB128 and larger numbers 8 to 10 times faster on x86 and ARM hardware, by avoiding LEB128's bit-masking and branch-heavy continuation bit scans.