
2026/05/30 0:03
Bijou64:可変長整数符号化方式
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
Bijou64 は、Subduction CRDT サイシンクプロトコルに特化して開発された革新的な可変長整数符号化方式であり、数学的に正規化された数値表現を強制することで署名検証の脆弱性を排除することを目的としています。LEB128 といった従来の形式ではあいまいな符号化が可能となりセキュリティ上の欠陥を引き起こす可能性があるのに対し、Bijou64 はユニークな「第 1 バイトの二重利用」メカニズムとオフセットベースの構造(例:2 バイト数の表現には重複した低長表現を使用せず 0xF8 を使用)によって無効な形式を不可能にします。この「設計段階での正規化」により、別途の実行時のセキュリティチェックの必要がなくなり、Bitcoin や JWT、ASN.1 などのプロトコルに対する歴史的攻撃を防止すると同時に、オーバーヘッドを加えずまたは通信バイト数を増やすこともなく、ゼロコストで実現できます。この形式は、第 1 バイトを読み取る際に O(1) のメモリ配分が可能となることや、タグ(0x42–0xFF)を使用することで後続のバイト数をあいまいさなしに示せることを通じて達成しています。ARM および x86 アーキテクチャにおけるベンチマークでは、Bijou64 が既存の方法と比べて大部分のデータ分布で 2 倍から 10 倍高速にデコードすることが実証されており、固有の安全性と即時の効率化利得を提供します。小規模な数値(248–65,535)に対する符号化速度は LEB128 に比べてやや遅い(約 1.24 倍)ものの、この形式には他の安全な形式に見られる実行時のチェックオーバーヘッドがなく、統合された正規化特性により全体として優れています。本ソリューションは、双極の MIT/Apache-2.0 ライセンスおよび CC BY-SA 4.0 仕様に従って crates.io に
bijou64 として公開されており、様々な整数サイズ(bijou32, bijou128)および WebAssembly 向けの実装ライブラリが開発中です。本文
Bijou64: 構造上正規化された高速 Varint 暗号化方式
Bijou64(バイジュ 64)とは、Subduction CRDT サインクプロトコル開発のために設計された変長整数(Varint)の暗号化方式です。 当初は「記号検証における微妙なバグ解消」のみを目的としていましたが、意図していなかった制約から一般的な LEB128 よりも数倍高速に動作する驚異的なパフォーマンスが発見されました。
問題的背景:正規形化(Canonicalisation)の欠如
多くの二進法プロトコルでは、小型・大型の数値を問わずコンパクトな暗号化が求められます。しかし、既存の標準である LEB128 は以下の根本的な弱点を持っています。
LEB128 の構造と問題点
- 非一意な表現: 数値
は0
、0x00
、0x80 0x00
など、末尾にゼロバイトが続く限り無数の表し方があります。0x80 0x80 0x00 - ランタイムチェック依存: デコーダー側が「どの形式でも受け入れる」ため、正当性を保つのはランタイムチェックのみです。
- 署名処理への影響: 余分な
が存在すると署名が変わるため、正確なバイト列(一意性)を知る必要がある場合に致命的になります。0x80
正規形化攻撃のリスク
「異なるバイト列同士が同一値だと誤認させる」悪意のある入力に対し、システムは以下のような脆弱性を抱えています。
- 仕様の理想 vs 実装の隙: 仕様では「正規暗号化のみ許可」とされていますが、実装では条件分岐(
)によるチェックです。if - テストスイートの欠如: 悪意のある入力に対する耐性は稀にしかテストされません。
- パフォーマンス劣化: チェックが忘れられたり、最適化されなかったりで、セキュリティ特性が無音で低下します。
bijou64 の解決策:(ほぼ) 構造上の正規性
bijou64 は追加のチェックを追加するのではなく、フォーマット自体を「一意な暗号化形式」に設計することで問題を解決しました。これにより、正規形チェックはデコーディングの一部となり、処理負荷がゼロになります。
2 つの核心手法
-
最初のバイトの二重利用(First Byte Double Duty)
- 0–247: データそのものとして扱われます(例:
→ 値 66)。0x42 - 248–255: 「タグ」として機能し、後のバイト数(データ長)を示します。
- メリット: 最初のバイトでメモリ確保(O(1))が可能。LEB128 のように終端ビットをスキャンする必要がありません。
- 0–247: データそのものとして扱われます(例:
-
オフセット(Offsets)
- タグ単体では不十分なので、方向性を示すオフセットを使用します。
- 例:
は単に0xF8 0x00
ではなく、値0
を意味します(第二バイトをオフセットして計算するため)。0xF8 (248)
デコード計算の具体例
タグとデータ長に基づき、固定的なオフセットテーブルを使用することで高速化を図ります。
| 総長 (バイト数) | オフセット (Hex) | 説明 |
|---|---|---|
| 1 | | 単一バイト値 |
| 2 | | タグ +1 データバイト |
| 3 | | タグ +2 データバイト |
| 4 | | タグ +3 データバイト |
| ... | ... | オフセットパターンは予測可能 |
| 9 | | 最大タグ (タグ +8 データバイト) |
例外処理:
- 9 バイト(最大)のケースのみ、値が範囲内かを手動チェックします(u64 の上限のため)。
- その他の長さはオフセットテーブルで正確に扱えます。
ベンチマーク結果
固定長の 64 ビット整数と比較しても高く見えるコストは、bijou64 の構造上の恩恵によって相殺されています。
デコーディングパフォーマンス
**ARM (Apple M2 Pro) と x86 (AMD Zen 5)**での測定結果です。
- 全体: LEB128 の正規形チェックオーバーヘッドを含めずとも、約 2–10 倍高速。
- 小型数値 (単一バイト): LEB128 よりも約 2 倍速い。
- 大型数値 (継続ビット多数): LEB128 の約8–10 倍高速。
- LEB128: バッチ 4096 値あたり ≈30 マイクロ秒 (7.3 ns/値)
- Bijou64: バッチ 4096 値あたり ≈3 マイクロ秒 (0.75 ns/値)
なぜこれほど高速か?(技術的理由)
- 継続ビットスキャンなし: デコーダーは直ちに読み取るバイト数を把握できるため、ブランチ予測器(Branch Predictor)に負担をかけません。
- ビッグエンディアン・連続ペイロード: 7 ビット単位のレイアウトではなく、連続した整数として処理できるため、
等の最適化が適用されやすく、マスク/シフト指令が減ります。bswap - 予測可能な分岐: ターゲット選択が固定マッチで、ブランチ予測がすぐに安定します(急峻な CDF 曲線の原因)。
- 安価な算術:
の加算のみであり、複雑な分岐処理不要です。OFFSET[tier]
正規デコーディングの場合: LEB128 は「チェック」を追加のオーバーヘッドとして必要ですが、bijou64 では正規性チェックがデコーディングの一部となるため、実質的なコスト増はありません。
エンコードサイズと採用判断
圧縮率
- bijou64 は最もコンパクトではありませんが、LEB128 と比較してワイヤーバイト数は数%以内です。
- 大部分の数字において長さ(バイト数)は同一です。
採用すべきか?
**「はい、特に重要なケースでは」**という回答です。
- 推奨シナリオ:
- 署名(Signature)、コンテンツアドレス指定などの機能で「正確なバイト列」が必要である場合。
- プロトコルのセキュリティ特性を維持しつつ、最大のパフォーマンスを求める場合。
- 注意点:
- LEB128 はまだ主流であり、完全な置き換えにはタイミングが必要です。
- 特定の負荷分布で性能が劣化する可能性は理論上残るため、ベンチマークでの確認をお勧めします。
利用情報
- リポジトリ:
のcrates.iobijou64 - ライセンス: MIT / Apache-2.0 (実装コード)
- 仕様書: CC BY-SA 4.0 (自由に移植可能)
- 拡張性: Wasm/Javascript ラッパーあり、将来
/bijou32
が計画されている。bijou128