bijou64: A Canonical and High-Performance Varint Encoding
AI Summary
bijou64 is a variable-length integer (varint) encoding designed to solve canonicality issues inherent in formats like LEB128. By ensuring each integer has exactly one unique byte representation, it eliminates the need for runtime canonicality checks, which are common sources of security vulnerabilities. The design uses a length-prefix in the first byte to allow O(1) memory allocation and utilizes contiguous big-endian payloads, enabling compilers to leverage hardware byte-swap instructions. Benchmarks show bijou64 is 2–10 times faster than LEB128 due to improved branch prediction and reduced bit-masking overhead.
Key Takeaways
- The first byte acts as a tag, indicating the total length of the integer, which allows for predictable memory allocation.
- Offsets are used to ensure that every integer value maps to a unique byte sequence, preventing multiple representations of the same number.
- Performance gains are largely attributed to the removal of continuation-bit scanning and the use of contiguous byte-swapping, which is highly optimized on modern CPUs.
Why it matters
For protocols involving signed data, content-addressing, or distributed consensus, non-canonical encodings allow adversarial inputs that can bypass security checks. bijou64 provides a 'secure-by-construction' alternative that improves performance by removing the need for explicit validation logic.
Conversation 0
Be the first to share your perspective.