Bijou64：可変長整数エンコーディングにおける正規性問題の解決

バイナリプロトコルの世界では、整数を効率的にエンコードすることは常にバランスを取る作業です。ほとんどの開発者は、varint（可変長整数エンコーディング）を利用して、小さな数が 8 バイトもの領域を無駄にしないようにしています。しかし、多くの設計には微妙ながら危険な欠陥があります。それは 構造的正規性の欠如 です。

単一の値が複数の異なるバイト列で表現できてしまうと、特に署名付きプロトコルにおいてセキュリティ脆弱性が生じます。システムがメッセージのバイト列に基づいて署名を検証し、デコーダが異なるバイト列を同一の値として扱う場合、攻撃者は論理的な値を変えずにメッセージバイトを改ざんでき、セキュリティチェックを回避したり可変性（malleability）問題を引き起こしたりします。これが bijou64 が解決しようとしている核心的な問題です。

LEB128 の欠陥

bijou64 を理解するには、まず業界標準である LEB128 を見る必要があります。LEB128 は 7 ビット単位で数値をエンコードし、各バイトの最上位ビットを「継続ビット」として使用し、続くバイトがあることを示します。

実用的ではありますが、LEB128 は構造的に正規ではありません。たとえば数値 0 は 0x00 とエンコードできますが、0x80 0x00 や 0x80 0x80 0x00 とエンコードすることも可能です。ほとんどのデコーダはこれらすべてをゼロとして受け入れます。この非正規性は、ASN.1、X.509 証明書、Bitcoin 取引など、重要なシステムに実際の脆弱性をもたらしました。

従来は、デコーダ側で「正規形」を強制するランタイムチェックを導入して対処してきました。しかし、bijou64 の作者が指摘するように、これらのチェックはしばしば省略されたり、最適化で除去されたり、移植時に忘れられたりして、静かにセキュリティが低下してしまいます。

Bijou64 が正規性を実現する方法

bijou64 は、整数ごとに複数のエンコードが存在する可能性を排除するために、先頭バイトのタグ付け と オフセット の二つの主要メカニズムを使用します。

1. 先頭バイトの二重役割

bijou64 では、先頭バイトが二つの目的を果たします。0 から 247 までの値に対しては、先頭バイト自体がその値になります。248 以上の値に対しては、先頭バイトがタグとして機能し、続くバイト数を正確に示します。

この設計により、デコーダは $O(1)$ 時間で必要なメモリ割り当て量を即座に把握でき、LEB128 が $O(n)$ 時間で継続ビットを走査しなければならない点と比べて、明らかな性能向上が得られます。

2. オフセット手法

0 のような数が単一バイト (0x00) とタグ付きシーケンス（例：0xF8 0x00）の両方で表現されることを防ぐため、bijou64 は オフセット を導入します。タグ付きバイト列は「ゼロから」数値を表すのではなく、前段階の範囲と重ならないようにオフセットされた値を表します。

たとえば、タグが 2 バイトシーケンスを示す場合、値は 248（0xF8）でオフセットされます。これにより、最小の 2 バイトエンコードは 0 ではなく 248 を表すことになります。このパターンはより大きな整数に対しても予測可能に続き、先頭バイトに基づくオフセットテーブルが形成されます。

パフォーマンスベンチマーク

驚くべきことに、セキュリティを重視した設計が 大幅な性能向上 ももたらしました。ARM（Apple M2 Pro）と x86（AMD Zen 5）でのベンチマークは、bijou64 が LEB128 よりもかなり高速であることを示しています。

デコード速度：bijou64 は LEB128 の約 2〜10 倍 の速度でデコードできます。大規模な u64 分布に対しては、4096 個の値を約 3 μs で処理でき、LEB128 の約 30 μs と比較して大幅に速いです。
一貫性：継続ビットの走査という予測不可能な分岐がないため、性能は非常に安定しています（ベンチマークの CDF 曲線がほぼ垂直になるほど）。
エンコード速度：特定の「小」分布（248〜65,535）では LEB128 がやや速いものの、他のケースでは bijou64 が全般的に優れています。

これらの利点は、ビッグエンディアンの連続ペイロード を使用できることに起因します。これにより、モダン CPU は単一のロードと bswap 命令だけで処理でき、LEB128 が必要とする 7 ビットレイアウトのマスクとシフトを回避できます。

批判的視点とトレードオフ

ベンチマークは印象的ですが、コミュニティからは以下のような重要な指摘が上がっています。

SIMD と並列化

あるコントリビュータは、bijou64 はスカラー演算では高速でも、SIMD（Single Instruction, Multiple Data）命令を用いた場合や、先行タグバイトへの依存が強い形式に比べて劣る可能性があると指摘しています。大量データを一括処理できるフォーマットは、タグバイトへの厳格な依存がない分、並列化の恩恵を受けやすいです。

空間効率

LEB128 は特定の範囲でよりコンパクトです。たとえば、LEB128 は $2^{14}$ までの値を 2 バイト で表現できますが、bijou64 の 2 バイト範囲ははるかに小さく（最大 500）です。バイト数が極めて重要で、値がこの中間範囲に頻繁に収まるプロトコルでは、LEB128 の方が適している場合があります。

「リンク」ユースケース

DWARF や WASM などの環境では、非正規エンコードが実際には機能 しています。コンパイラはシンボルの最終アドレスがリンク時まで不明であるため、最も広い varint（例：LEB128 の 5 バイト）をプレースホルダーとして出力します。エンコードが厳密に正規であると、リンク時に varint の幅が変わるたびに後続コード全体をシフトし直す必要が生じ、再計算の連鎖が発生します。

結論

bijou64 は哲学的な転換を示しています。欠陥のあるフォーマットにチェックを付加するのではなく、フォーマット自体を変更して欠陥を根本的に不可能にします。署名やコンテンツアドレッシング、実装間の厳格な合意が必要な新しいプロトコルを構築する開発者にとって、bijou64 は 構造的に安全で、一般的に LEB128 より高速 な代替手段を提供します。