Разработчики протокола синхронизации Subduction CRDT столкнулись с неприятной проблемой: стандартное кодирование чисел переменной длины LEB128 позволяло представить одно и то же число несколькими способами. Это создавало брешь для атак на цифровые подписи — подсунув «лишний» байт, можно было изменить хэш подписанных данных, не меняя само значение. Такие уязвимости (канонизационные атаки) известны по PKCS#1, Mozilla NSS, JWT и Bitcoin. Обычно их закрывают отдельной проверкой в декодере, но разработчики часто забывают её добавить или оптимизируют в прогоне.
Чтобы решить проблему раз и навсегда, команда написала собственный варинт — bijou64. Идея в том, что каноничность встроена прямо в формат: у каждого числа есть ровно одно представление. Первый байт кодирует значения от 0 до 247 напрямую, а значения 248–255 служат тегом, указывающим, сколько ещё байт данных последует. Дополнительно используется смещение: например, двухбайтовая комбинация начинается не с нуля, а с числа 248, так что дублировать однобайтовые коды невозможно. Исключение — самый длинный 9-байтовый тег, где проверка границ u64 всё же нужна, но это не нарушает уникальность кодировок.
При тестировании на ARM M2 Pro и AMD Zen 5 обнаружился неожиданный бонус: bijou64 оказался в 2–10 раз быстрее LEB128 при декодировании. Для больших чисел (полный u64) разрыв достигает 10 раз — ~0.75 наносекунды на значение против 7.3 нс у LEB128. Причина в том, что декодеру не нужно сканировать каждый байт в поисках стоп-бита: длина известна сразу с первого байта. А непрерывные big-endian данные отлично ловятся одной инструкцией загрузки с перестановкой байт (bswap). Ветвления предсказываются идеально, о чём говорят почти вертикальные CDF-графики времени. Кодирование тоже быстрее, хотя на очень маленьких числах (248–65535) LEB128 выигрывает примерно в 1.24 раза. Размер на проводе отличается в пределах пары процентов.
Авторы честно предупреждают: формат новый, обкатан на трёх CPU, и LEB128 с его зрелой инфраструктурой никуда не денется. Но если проекту критична каноничность — для подписей, адресации по содержимому или консенсуса между разными реализациями — bijou64 даёт её бесплатно и с приростом скорости. Библиотека опубликована на crates.io под двойной лицензией MIT/Apache-2.0, спецификация под CC BY-SA 4.0, есть обёртка для Wasm/JavaScript и черновики для bijou32 и bijou128.