bijou64：暗号プロトコル向けの可変長整数エンコーディング

Ink and Switchが開発した可変長整数エンコーディング「bijou64」は、LEB128より2～10倍高速に動作し、署名検証の脆弱性を防ぐため数値の正準表現を保証する。

Ink and Switchは、Subduction CRDTシンク プロトコル向けに開発した可変長整数エンコーディング「bijou64」を公開した。この設計は、数値が唯一の方法でのみ表現可能にすることで、署名検証の脆弱性を修正することを意図していた。ベンチマークの結果、より一般的なvarint形式であるLEB128より数倍から10倍高速に動作することが判明した。

正準表現による署名検証の保護

LEB128エンコーディングには、同じ数値を複数の方法で表現できる問題がある。例えば、数値0は0x00、0x80 0x00、0x80 0x80 0x00など複数の方法で符号化可能である。このような非正準エンコーディングは「正準性攻撃」と呼ばれ、PKCS#1 v1.5、Mozilla NSS、GnuTLS、JWT、ビットコイン トランザクションなど複数のプロトコルで実証されている。

bijou64は二つの設計手法により、この問題を根本的に解決する。第一に、最初のバイトは0～247を通常通り表現し、248～255はタグとして機能する二重の役割を担う。第二に、オフセット値を利用して複数のエンコーディング方法を排除する。例えば、数値1738は、タグとその後の2バイトを組み合わせて表現される。このアプローチにより、各数値は唯一の符号化方式のみが存在するようになる。

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

bijou64が高速である理由は、デコード時間の複雑さにある。LEB128はO(n)の走査を必要とするのに対し、bijou64は最初のバイトから読み込むべきバイト数を確定でき、O(1)のデコード時間を実現する。

単一バイト数値では約2倍の高速化を達成し、LEB128の継続ビットを要する大きな数値では8～10倍高速化する。一様なfull-u64分布ベンチマークでは、bijou64が4096個の値を約3マイクロ秒で処理する一方、LEB128は約30マイクロ秒を要する。これは値あたり0.75ナノ秒対7.3ナノ秒に相当する。

ただし、小規模分布（248～65,535）のエンコーディングではLEB128が約1.24倍優位に立つ。両者のワイヤバイト数は、現実的なワークロードで数パーセント以内の差に収まる。

実装と配布

bijou64はcrates.ioにMIT/Apache-2.0デュアルライセンスで公開されている。仕様はCC BY-SA 4.0の下で提供される。Wasm/JavaScriptラッパーも存在し、6864ビット最大値（u64）を対象としている。将来拡張として、bijou32やbijou128といった幅拡張ファミリーが仕様書に記載されている。

筆者の見立て

• bijou64は正準性の観点で重要なアプリケーション向けに「構造的により安全である」と評価している
• 新しいフォーマット設計時に正準性が重要な場合、bijou64は「検討する価値のある代替案である」と解釈している
• LEB128は「消え去るべきではなく、消え去らない」と述べている

この記事は元記事の事実のみに基づいて自動生成されました。

出典

Ink and Switch「bijou64」https://www.inkandswitch.com/tangents/bijou64/