Bijou64: A variable-length integer encoding that's both correct and accidentally fast

Summary

This article describes the development of bijou64, a variable-length integer (varint) encoding created for the Subduction CRDT sync protocol. The encoding was designed to fix a signature-verification bug by ensuring each number has only one possible representation (canonical encoding). An unexpected side benefit was that bijou64 runs several times faster than the more common LEB128 varint encoding. The author explains how the design constraints for correctness inadvertently led to performance improvements by requiring less computational work during encoding and decoding.