Zenn
Open4

CRLiteの仕様について

catatsuycatatsuy

Clubcard/Ribbon(Clubcard)アルゴリズム解説 — Mozilla実装コードをベースに

本資料は提示コード（公式実装）に即して、Clubcard = partitioned two‑level cascade of Ribbon filters のアルゴリズムを、実装の意図・数式・データ構造・処理フローの順で整理したものです。

0. 目的と全体像

  • 課題: 大規模な宇宙集合 U とその部分集合 R\subseteq U に対して、正確なメンバーシップ判定 f(u)=\mathbf{1}[u\in R] を、低帯域・低メモリ・高スループットで実現する。

  • アプローチ: 2段カスケード

    • 近似段 (X): まず確率的に候補をふるい落とす（偽陽性は残るが偽陰性なし）。
    • 確定段 (Y): 近似段を通過した要素だけを1ビットで厳密判定。

  • ブロック化 (Partitioning): U をブロック（パーティション）に分割し、各ブロックごとに Ribbon を構築・連結することで差分配布とスケールに対応する。

直感：Bloomの「ビット塗りつぶし」ではなく、Ribbon = GF(2)線形方程式の疎系を組み立て、**“解ベクトル”**を配ってローカルで判定する方式。

1. 数学モデル（lib.rsの仕様に準拠）

ClubcardはGF(2)上の行列 X, Y とハッシュ関数 h, g を用いる：

  • 近似段：H\cdot X = 0 を満たす X を構築する。

    • H の各行は h(u)（u\in R をハッシュしたベクトル）。
    • 列数：\operatorname{rank}(X) = \left\lfloor\log_2 \frac{|U\setminus R|}{|R|}\right\rfloor.

  • 確定段：G\cdot Y = C を満たす Y を構築する（列数は1）。

    • G の各行は、h(u)\cdot X=0 を満たす u に対する g(u)。
    • C は u\in R なら0、そうでなければ1を返す列ベクトル（GF(2)）。

  • 照会（判定）：u\in R\iff h(u)\cdot X=0\ \land\ g(u)\cdot Y=0.

実装では、この「h,g が返す行ベクトル」を Equation<W> として表現し、Ribbon解法の結果（X,Y の列ベクトル）に内積を取って 0/1 を判定します。

2. データ構造：Equation と Ribbon

2.1 Equation<W>

  • 形式： a(x) = b ⊕ Σ a_i x_i （GF(2)）

  • フィールド：

    • s：先頭の有効ビット位置（行番号起点）
    • a: [u64; W]：連続する 64\times W ビットの係数（疎な連続帯域）
    • b: u8：定数項（0/1）

  • 整列 (aligned)：a[0] & 1 == 1 を invariant とする。add 時に回転/シフトして pivot を必ずLSBへ寄せ、対応して s を増やす。

  • eval(z)：a\cdot z のGF(2)内積。

2.2 Ribbon（線形方程式系）

  • 役割：アイテムを Equation に写像して行列（疎）に積み上げ、後退代入で解ベクトルを得る。

  • insert(item)：

    1. eq = item.as_query(m) で方程式化（m はブロック全体の行数の目安）。
    2. eq.b = 0 if included()（R側）/ 1 otherwise（U\R側）。
    3. insert_equation(eq)：pivot衝突なら add で整列しつつ右へ流し、空行に挿入（arXiv:2103.02515 Algorithm 1 相当）。

  • solve(tail)：

    • 右隣ブロックの解（tail）をビット連結してから、行末から0へ後退代入。
    • 自由変数（ゼロ行）は乱数で埋める（非決定）。

これにより、ブロック列全体の列ベクトル（近似段は rank 本、確定段は1本）を構築します。

記号と演算（GF(2)）の意味と“どう計算しているか”

この節では、資料中の数式や記号と、実装で行っているビット演算の対応を明示します。

1) 係数体：GF(2)（2元体）

  • 扱う値は 0 と 1 のみ。

  • 和 ⊕ は XOR（排他的論理和）。

    • 0⊕0=0, 0⊕1=1, 1⊕0=1, 1⊕1=0。

  • 積 · は AND に相当（0·x=0, 1·x=x）。

  • すべて mod 2 の世界。重要なのは 1 ビットの個数が偶数か奇数か（パリティ）。

コード対応： ^ がXOR、& がAND、| がOR、>>/<< がシフト。count_ones() & 1 は「1 の個数の偶奇＝GF(2)の和」。

2) ベクトル/行列と内積

  • ベクトル a と z の内積は a·z = (Σ a_i z_i) mod 2。
  • 実装では (a & z) の 1 ビット総数の偶奇で求める（偶数→0、奇数→1）。
  • Equation::eval(z) はこの GF(2) 内積を返す（定数項 b は別扱い）。

3) 線形方程式 a(x) = b ⊕ Σ a_i x_i

  • 各 Equation は 1 本の「行」を表す。a が係数ベクトル、b が定数（0/1）。
  • Ribbon::solve() の後退代入は、各行 i について z_i = row_i(z) ⊕ b（実装では rows[i].eval(z) ^ rows[i].b）で解ベクトル z のそのビットを決める。
  • こうして全行に対して a(z)=b を満たす解 z を作る。

4) アライン（整列）と s の意味

  • Equation は連続 64×W ビット幅だけが非ゼロの疎構造。
  • s はその帯域の開始ビット位置（行番号）。add() 内で回転/シフトして a の最下位ビットを必ず 1 にし（pivot 揃え）、対応して s を進める。
  • eval(z) は s から 64×W ビット分だけ z を切り出し内積を取る。

5) 近似段 X と確定段 Y の判定

  • 近似段：列ベクトル X が rank 本あるとき、すべての列 j について h(u)·X_j = 0 なら通過。
  • 確定段：1 本の列ベクトル Y に対して g(u)·Y = 0 なら R、=1 なら U∖R。
  • 例外（exceptions）：一致したら常に非会員として落とす（誤包含の補正）。
  • 反転（inverted）：最後に結果を反転。U∖R を表現するブロックや R=U（m=0 かつ inverted=true）を簡潔に扱える。

6) ランク rank の意味

  • 近似段の列数。 rank = ⌊ log2( |U∖R| / |R| ) ⌋。
  • 直感：R が疎なら列を多くして偽陽性を強く削る。R が密（2|R|≥|U|）なら rank=0（全通過）として確定段に任せる。

7) 具体計算ミニ例（W=1）

  • 例1: 内積。 s=0, a=1011₂, z=1101₂ → a & z = 1001₂（1 が 2 個＝偶数）→ eval=0。
  • 例2: シフト。 s=2, a=0011₂, z=101100₂ → z を s=2 だけ右寄せで見て AND → 0011₂ → 1 が 2 個 → eval=0。
  • 例3: 確定段。 Exact 構築では R 要素は b=0、U∖R 要素は b=1 として式を挿入し、solve で a(z)=b を満たす Y を得る。クエリでは g(u)·Y を 0/1 判定するだけ（例外で補正あり）。

3. 近似段（ApproximateRibbon）

3.1 構築

  • ApproximateRibbon::new(id, |R|, |U|, inverted)：

    • m = ⌊(1+ε)|R|⌋（ε=0.02固定、実験で最適化余地あり）
    • rank = 0 if |R|=0 or 2|R| ≥ |U|、else ⌊log2((|U|-|R|)/|R|)⌋

  • From<RibbonBuilder>：

    • |R| ≤ |U| を assert。
    • 特例（R=U）：m=0 かつ inverted = !inverted として「空フィルタ＋反転」で表現（全包含）。
    • それ以外は要素を順次 insert。同次系なので exceptions は基本空。

3.2 近似段の意味（コードコメントに基づく）

  • 返す関数は f:U→{0,1} で、f(x)=0 iff x\in R\cup S。
  • S\subseteq U\setminus R はランダム部分集合で |S|\approx |R|。
  • よって偽陽性率は概ね |R|/(|U|-|R|)。この曖昧さを 次段Y で解消します。

4. 確定段（ExactRibbon）

4.1 構築

  • ExactRibbon::new(id, size, inverted)：m = ⌊(1+ε)·size⌋、rank=1 固定。

  • From<RibbonBuilder>：

    • 入力 items は、近似段で通過した宇宙（ブロック）と一致することを前提に universe_size をチェック（0 または items.len()）。

    • 近似ブロックが空（=論理全包含）なら m=0 の空確定リボンを返す（inverted継承）。

    • それ以外は、まず included()（b=0）を挿入→次に excluded（b=1）を挿入：

      • こうすることで、矛盾が出ても例外（exceptions）は原則U\R側になる（論理が分かりやすい）。

4.2 例外（exceptions）

  • 例外は「このブロックの線形系で誤って含まれてしまう非会員」を 明示的に除外 するための個別キー（discriminant()）。
  • 最後の判定で、例外一致なら非会員（0→1に反転）にする。

5. ブロック化と列ベクトルの連結

5.1 PartitionedRibbonFilter の構築

  • 入力：Vec<Ribbon> を rank降順でソート。

  • 列ベクトルを生成：

    • max_rank 回のループで列ごとの後退代入を行い、
    • 右端ブロックから左へ tail を渡しながら solve、末尾のゼロをトリム。
    • これで 近似段は rank 本の列ベクトル、確定段は 1本の列ベクトルを得る。

  • index：ブロックID→{offset, m, rank, exceptions, inverted} を格納。

    • offset はこのブロックが全体解ベクトルのどこから始まるかを示すビット位置。

5.2 ブロックの意味

  • 実運用でのパーティション（例：証明書のハッシュプレフィックス等）を “block id” で表現。
  • これによりスナップショット/デルタ更新をブロック単位で行え、大量失効イベント時も該当ブロックのみの更新で済む。

6. Clubcardのビルドとクエリ

6.1 ビルド（ClubcardBuilder）

  1. 近似リボン群を collect_approx_ribbons に渡し、approx_filter（Xの列群）を得る。

  2. 確定リボン群を collect_exact_ribbons に渡し、exact_filter（Yの列＝1本）を得る。

  3. 2つのインデックスを 結合：

    • ブロックごとの approx_filter_{m,rank,offset} と
    • exact_filter_{m,offset} を合体。
    • inverted は一致をassert、exceptions は結合。

  4. Clubcard として {universe, partition, index, approx_filter(cols), exact_filter(col)} を構築。

6.2 クエリ（Clubcard::contains / unchecked_contains）

  1. Universeチェック（in_universe）→不一致なら NotInUniverse。

  2. ブロックがなければ NoData。

  3. 近似段：

    • ブロックが空(m=0) なら論理的には何も含まない扱い（ただし最後に ^ inverted）。
    • meta.approx_filter_rank 本の列それぞれに対し h(u) を式化して内積を評価。全て0なら通過。

  4. 確定段：

    • g(u) を式化して内積を評価。0なら通過。

  5. 例外：discriminant() が exceptions に存在すれば不通過。

  6. 反転：結果を ^ meta.inverted で反転して返す。

戻り値は Membership::{Member,Nonmember,NotInUniverse,NoData}。

7. 実装に現れる重要な数式・パラメータ

  • rank（近似段の列数）：\left\lfloor\log_2 (|U\setminus R|/|R|)\right\rfloor。
  • m（行数目安）：m=\lfloor (1+\varepsilon)|R|\rfloor（\varepsilon=0.02）。
  • R=Uの特例：m=0 ＆ inverted=true の空フィルタで全包含を表現（メタデータで解釈）。
  • 偽陽性率（近似段）：概ね |R|/(|U|-|R|)。確定段で打ち消す設計。

8. テストが示す性質（抜粋）

  • identity解の検証（test_solve_identity）：x_i をそのまま解けることを確認。
  • 空近似の挙動（test_solve_empty）：空ブロックは論理的に何も含まない。
  • ランダム系の整合性（test_solve_random）：構築→解→評価で常に等式が成り立つ。
  • R=Uケース（test_total_approx_filter）：近似は m=0, rank=0, inverted=true、確定は m=0, rank=1, inverted=true、両段とも全包含（invertedで表現）。
  • rank=0近似（test_rank_0_approx_filter）：2|R|≥|U| で rank=0、全て通過（確定段へ）。

9. 実装者向けポイント（CRLite適用の観点）

  • AsQueryの品質が要：as_query(m) は

    • s を [0,m-1] の一様、
    • a[0]&1==1 を満たす一様乱数、
    • ブロックID（partitionの定義）と discriminant()（例外キー）を安定生成すること。

  • εのチューニング：対象分布（|R|/|U|、スパース度）で exceptions とサイズのトレードオフがある。経験的に最適化可能。

  • 決定性の要件：solve 自由変数に乱数を使うため、再現性が必要なら乱数源の固定化やdeterministicモードの追加を検討。

  • 例外ストア：巨大化抑制のための圧縮（prefix圧縮、集合ハッシュ）や分割配置（ブロック内辞書）が有効。

10. 簡易フローチャート（文章）

ビルド時

  1. 各ブロックで近似リボン ApproximateRibbon を構築（R=Uは空+inverted）。
  2. 近似で通過した宇宙に対して確定リボン ExactRibbon（rank=1）を構築。
  3. 両者を PartitionedRibbonFilter にして列ベクトル群（Xの複数列、Yの1列）を得る。
  4. Clubcard に index（offset/rank/m/exceptions/inverted）と列ベクトルを格納。

クエリ時

  1. ブロック特定→近似Xの全列で0判定→確定Yで0判定→例外照合→inverted反転→結果。

ブログ（2025-08-19）で公表された運用実態と計画（CRLite in Firefox）

出典: Mozilla公式ブログの発表要旨（提示文面に基づく整理）

  • 展開状況

    • Firefox 137 で デスクトップ全ユーザー（Windows/Linux/macOS）に有効化。
    • 失効照会は CTログに現れる全失効証明書 を対象。
    • ブラウザ外に照会を出さず（Mozillaにも送らない）ローカルで判定。

  • OCSPからの移行

    • 137以前はOCSPが主（プライバシー漏洩・HTTP素通し・遅延の問題）。
    • Firefox 142 で ドメイン認証(DV)証明書に対するOCSPを無効化予定。
    • HTTPS‑First・DNS over HTTPS・ECH(Encrypted ClientHello) の方針を補完。

  • 帯域プロファイル（配布形態）

    • 12時間ごとに差分（delta updates） を取得。
    • 45日ごとに約4MBのスナップショット を取得。
    • 平均 ~300KB/日（日々のdelta＋45日スナップショットの平準化）。

  • 性能（TLS接続の体感）

    • OCSPはTLSハンドシェイクを 中央値で≈100msブロック。
    • CRLite展開に伴い、ハンドシェイク中央値は 56.4ms→39.9ms に改善（ブログ掲載グラフ）。

  • 従来方式との比較

    • CRL（約3,000リスト、総量≈300MB）: 全更新は非現実的。
    • Chrome CRLSet（~600KB/日）: **全失効の約1%（35k/総400万）**のみ手選別で配信。
    • CRLite: 半分の帯域（~300KB/日）, 更新頻度2倍, “全失効”をカバー。

  • データ構造の進化

    • 初期実験は Bloomカスケード→帯域過大で実運用に不向き。
    • 現行は Clubcard（partitioned two-level cascade of Ribbon filters） を採用。
    • two‑level cascade は Mike Hamburg (RWC 2022) の発表に基づく。
    • partitioning はMozillaの独自拡張で、IEEE S&P 2025 / RWC 2025 で発表。

  • 今後の改善（ロードマップ）

    • Clubcardのpartition戦略の最適化（大量失効イベントの圧縮効率を強化）。
    • HTTP圧縮辞書の導入（delta更新をさらに縮小）。
    • 証明書有効期間の短期化を推進（同一失効を符号化対象とする期間を縮小）。
    • トータルとして 帯域は今後も逓減傾向 を見込む。

  • 公開実装

    • Clubcardブロックリストライブラリ、
    • CRLite向けClubcardのインスタンス化、
    • CRLiteバックエンド を公開。
    • 他ベンダへの採用を期待。

Bloomカスケード方式との明確な比較

結論: Clubcardは「データ構造（GF(2)線形系の解）×二段化×パーティション化」により、帯域・更新・網羅性でBloomカスケードを実運用可能な水準まで押し上げる。

1) データ構造の違い

  • Bloomカスケード: 濃いビット列に複数レベルのBloomを重ね、偽陽性を段階的に低減。
  • Clubcard: Equationで表す疎なGF(2)線形系を構築し、**解ベクトル（列）**を配布。近似段X（rank列）＋確定段Y（1列）。

2) 圧縮性とデルタ更新

  • Bloom: ビット分布がほぼランダムで高密度→一般圧縮が効きにくい。日々のビット反転が広域に散り、差分が大きくなりがち。
  • Clubcard: 解ベクトルは疎かつ構造化され、HTTP圧縮や辞書圧縮と相性が良い。さらにパーティション単位での更新が可能→大量失効でも該当ブロックのみ更新でき、deltaが小さい。

3) 偽陽性/偽陰性と“確定”の扱い

  • Bloom: 偽陽性はレベル数やビット密度で調整。確定（exact）段を別に持たないのが通常。
  • Clubcard: 近似段の偽陽性は確定段Yで必ず潰す（設計上、偽陰性なし）。例外はexceptionsで明示補正。

4) 帯域とサイズ（実測の一例）

  • Bloom（CRLite初期実験）: 12.2M失効/789.2M非失効の実データで 19.8MB フィルタ構築に 293s。
  • Clubcard: 8.5MB に 200s（lib.rsコメント記載の同条件）。さらに運用では平均 ~300KB/日 配布（ブログ）。

5) クエリコスト

  • Bloom: レベル×k個のハッシュ＆ビット検査。
  • Clubcard: rank本のX内積＋Y内積（いずれもビット演算）＋例外照合。ハッシュ生成はas_queryで一度。

6) エッジケースの表現力

  • Bloom: R=U などの退化ケースは構成上の特別扱いが増える。
  • Clubcard: R=U を m=0＋inverted=true で簡潔に表現。rank=0 になる高密度ケースも自然に処理。

7) 運用

  • Bloom: スナップショット再配布が重く、大規模イベント（鍵事故など）で破綻しやすい。
  • Clubcard: パーティション更新、HTTP辞書圧縮、短期有効期限との相乗で安定運用。

8) まとめ表

観点 Bloomカスケード Clubcard (Ribbon二段+Partition)
基本構造 多層Bloomビット列 GF(2)線形系の解（X:rank列, Y:1列）
圧縮性 低（高密度） 高（疎/構造化、辞書圧縮適合）
デルタ更新 不利（ビット反転が散在） 有利（パーティション局所化）
偽陽性 レベル増で低減 近似段のみ→確定段で除去
偽陰性 なし なし（例外で整合）
帯域/サイズ 大になりがち 実運用で~300KB/日、例: 8.5MB vs 19.8MB
構築時間 速い/単純 解法が必要だが実測で有利なケースあり
エッジケース 表現が煩雑 m=0+inverted/rank=0で自然に表現

実務TL;DR: 配るなら“解”を配る。Clubcardは配布/更新/圧縮で勝ち、さらに二段で“完全”を担保。

何がうれしいのか（導入メリットと現場で効くポイント）

出典: Mozilla公式ブログの発表要旨（提示文面に基づく整理）

  • 展開状況

    • Firefox 137 で デスクトップ全ユーザー（Windows/Linux/macOS）に有効化。
    • 失効照会は CTログに現れる全失効証明書 を対象。
    • ブラウザ外に照会を出さず（Mozillaにも送らない）ローカルで判定。

  • OCSPからの移行

    • 137以前はOCSPが主（プライバシー漏洩・HTTP素通し・遅延の問題）。
    • Firefox 142 で ドメイン認証(DV)証明書に対するOCSPを無効化予定。
    • HTTPS‑First・DNS over HTTPS・ECH(Encrypted ClientHello) の方針を補完。

  • 帯域プロファイル（配布形態）

    • 12時間ごとに差分（delta updates） を取得。
    • 45日ごとに約4MBのスナップショット を取得。
    • 平均 ~300KB/日（日々のdelta＋45日スナップショットの平準化）。

  • 性能（TLS接続の体感）

    • OCSPはTLSハンドシェイクを 中央値で≈100msブロック。
    • CRLite展開に伴い、ハンドシェイク中央値は 56.4ms→39.9ms に改善（ブログ掲載グラフ）。

  • 従来方式との比較

    • CRL（約3,000リスト、総量≈300MB）: 全更新は非現実的。
    • Chrome CRLSet（~600KB/日）: **全失効の約1%（35k/総400万）**のみ手選別で配信。
    • CRLite: 半分の帯域（~300KB/日）, 更新頻度2倍, “全失効”をカバー。

  • データ構造の進化

    • 初期実験は Bloomカスケード→帯域過大で実運用に不向き。
    • 現行は Clubcard（partitioned two-level cascade of Ribbon filters） を採用。
    • two‑level cascade は Mike Hamburg (RWC 2022) の発表に基づく。
    • partitioning はMozillaの独自拡張で、IEEE S&P 2025 / RWC 2025 で発表。

  • 今後の改善（ロードマップ）

    • Clubcardのpartition戦略の最適化（大量失効イベントの圧縮効率を強化）。
    • HTTP圧縮辞書の導入（delta更新をさらに縮小）。
    • 証明書有効期間の短期化を推進（同一失効を符号化対象とする期間を縮小）。
    • トータルとして 帯域は今後も逓減傾向 を見込む。

  • 公開実装

    • Clubcardブロックリストライブラリ、
    • CRLite向けClubcardのインスタンス化、
    • CRLiteバックエンド を公開。
    • 他ベンダへの採用を期待。

何がうれしいのか（導入メリットと現場で効くポイント）

使うと何が嬉しい？ 数字と運用で具体化します（元記事に基づく値）。

  • プライバシーが守れる: 失効照会をローカルで完結。OCSPのようにCAや経路に閲覧先が漏れません。FirefoxはDV証明書に対するOCSPをv142で無効化予定。HTTPS‑First/DoH/ECHの方針とも整合。
  • 速い: OCSPの待ち（中央値≈100ms）が消える。CRLite展開に伴い、TLSハンドシェイクの中央値は約56.4→39.9msに改善（約30%高速化）。タイムアウト/ソフトフェイル起因のブレも抑制。
  • 完全: CTログに出る“全失効”を網羅。CRLSetのような一部配信（~1%）ではなく、理由コードの曖昧さにも依存しない“全件チェック”。
  • 軽い: 平均**~300KB/日**（45日ごとに約4MBスナップショット＋差分）。全CRL（約300MB/日再取得想定）対比で**~1000×小さい**。CRLSet（~600KB/日）より小さく、頻度は2倍かつ網羅。
  • 堅牢: CA側のOCSP障害/ネットワーク障害に非依存。オフラインでも検証可能（最新スナップショット＋差分があれば可）。
  • 運用しやすい: パーティションで差分配布・負荷分散。大量失効イベントでも該当ブロックだけ更新。例外リストで稀な挿入失敗も論理整合。
  • 説明しやすい: 「2段ゲート（Xで粗く弾き、Yで確定）」のメンタルモデルで、偽陽性=Yが吸収、偽陰性=設計上なし、と端的に伝えられる。

現場で“教える”ための具体トピック

  1. エレベーターピッチ: 「OCSPをやめ、二段の線形代数フィルタをローカルに持つ。プライバシーは守れ、回線も軽く、遅延も減る」。

  2. ホワイトボード・ストーリー:

    • 左から右にブロックを描き、上段をX（rank列ぶんの縦ベクトル群）、下段をY（1列）。
    • ユーザーのuをh(u)→Xで0判定、次にg(u)→Yで0判定、最後に例外テーブル照合→結果反転(inverted)。

  3. 覚えておく数値: 「300KB/日 / 4MB/45日 / 56.4→39.9ms」。

  4. FAQ

    • 偽陰性は？ → 設計上なし（行列解と例外で担保）。
    • 偽陽性は？ → 近似段のみ発生。確定段Yで潰す。
    • R=Uのとき？ → m=0＋inverted=true（空行列＋反転）で“全包含”を表現。
    • 大規模イベント時？ → 該当パーティションのみを差分更新。

  5. ロールアウト時の計測: ハンドシェイク分位点(P50/P95)、OCSPエラー率→0推移、スナップショット/差分のDL量、例外ヒット率。

  6. デバッグの勘所: ブロックIDミスマッチ、as_query(m)の整列不変違反（a[0]&1==1）、rank/offsetの食い違い、例外キーの正規化漏れ。

  7. 実装チェックリスト

    • AsQueryの一様性（s∈[0,m-1]）と整列（a[0]&1==1）。
    • ブロック分割規則の固定（安定したpartition）。
    • 例外テーブルの圧縮（prefix/ハッシュ）とサイズ監視。
    • solveの決定性要件（再現性が必要ならRNGを固定）。
    • ε(0.02)のチューニング計画（データ分布で検証）。

11. まとめ

  • Clubcardは、Ribbon（GF(2)線形系）の解を配布する設計で、Bloom系の密ビット列に比べて圧縮・差分配布・偽陽性制御に優れる。

  • partitioned two‑level cascade により、Web全体規模の完全な失効網羅を、現実的なサイズと更新頻度で運用可能にする。

  • 実装は、

    • Equationの整列不変条件、
    • Ribbon挿入（Algorithm 1）と後退代入、
    • rank/offset付きの多ブロック連結、
    • 例外とinvertedロジック、
      を厳密にコード化しており、数式仕様と高い整合性を保っている。

付録：用語対応

  • 近似段X = approx_filter（列ベクトル群） / approx_filter_rank
  • 確定段Y = exact_filter（1列）
  • ブロックID = id / block()
  • offset = 当該ブロック行の解ベクトルにおける開始ビット位置
  • 例外 = exceptions（discriminant()で照合）
  • 反転 = inverted（^で最終結果反転）
catatsuycatatsuy

Clubcard / CRLite のロジック（かんたん解説）

要するに何？

「このアイテム u は集合 R（失効証明書の集合）に入っているか？」を、ブラウザ単体で・高速に・少ないデータ量で判定する仕組み。サーバには聞きに行かない。

コアの考え方（2段ゲート）

  1. 近似ゲート（X）: 粗いふるい。だいたい正しいが、ときどき“入ってないのに入ってるっぽい（偽陽性）”が残る。
  2. 確定ゲート（Y）: 近似を通った候補だけを最終チェック。ここで完全一致にする（偽陽性をゼロにする）。

2つの鍵束 X と Y を使う二段チェック、と覚える。

どう作る？（ビルド時のロジック）

  1. パーティション: 全体（U）をブロックに分ける（例：ハッシュのプレフィックス）。

  2. 式にする（ハッシュ）: それぞれの要素を、短いビット式 Equation（行）に変換する。

  3. Ribbon を組む:

    • 各ブロックで、行（式）を“縦に積んで”疎な線形方程式系を作る。

    • これを解く（後退代入）と、列ベクトルが得られる。これが鍵束：

      • 近似段の列＝X（rank 本）
      • 確定段の列＝Y（1 本）

  4. 例外リスト: まれに線形系に入らない個別要素は、**例外（exceptions）**としてキーで控える。

  5. 索引（index）: ブロックごとの オフセット（どこから読むか）/サイズ/列数(rank)/反転フラグ(inverted) を保存。差分更新しやすい形で配る。

どう使う？（クエリ時のロジック）

  1. ブロック決定: アイテム u のブロックIDを決める。
  2. 近似チェック（X）: ハッシュ式 h(u) を作り、X の各列に対して “内積が 0 か？” を全部チェック。1つでも 1 なら不合格。
  3. 確定チェック（Y）: ハッシュ式 g(u) を作り、Y と“内積が 0 か？”をチェック。0 なら合格、1 なら不合格。
  4. 例外照合: 例外リストに当たれば不合格。
  5. 反転フラグ: ブロックが「逆表現」（U\R を表す等）のときは、最終結果を反転して解釈。

“内積が 0 か？”って何をしてる？（超要約）

  • 0/1 の世界（GF(2)）で、ビット同士を重ね合わせて 1 の個数の偶奇を見るだけ。
  • コード的には「AND → 1 の数を数える → 偶奇」で 0/1 を出している。
  • これを X と Y の列ベクトルに対して行う。

どこが賢い？（Bloom カスケードと比べて）

  • 圧縮しやすい: 密なビット列ではなく、線形代数の“解”を配るので、圧縮・差分（デルタ）が効く。
  • 更新が軽い: ブロック（パーティション）単位で更新できる。大量失効でも局所的に差し替え。
  • 完全性: 二段目（Y）で偽陽性を必ず潰す＝偽陰性なし・最終判定は正確。
  • R=U みたいな極端なケースも、空フィルタ＋反転で自然に表現。

超ミニ擬似コード

# ビルド（ブロックごと）
H = {h(u) | u ∈ R}  # 近似用の式集合
X = solve(H · X = 0) # rank 本の列
G = {g(u) | u ∈ U s.t. h(u)·X==0}
Y = solve(G · Y = C) # 1 本の列, C=会員(0)/非会員(1)
index = {offset, m, rank, inverted, exceptions}

# クエリ
block = block_id(u)
if not index[block]: return NoData
if any(h(u)·X_col != 0): return Nonmember
if g(u)·Y != 0: return Nonmember
if discriminant(u) in exceptions: return Nonmember
return Member ^ inverted

まとめ（ひとことで）

「X で速くふるい、Y で確実に決める」。鍵束（列ベクトル）を配って、あとはビット演算だけで判定するから、速く・軽く・漏らさない。

catatsuycatatsuy

0) TL;DR

  • やりたいこと：ブラウザだけで「この証明書は失効しているか？」を正確に、少ない帯域で、速く判定。

  • 仕組みの芯：0/1 の世界（GF(2)）で

    • 近似段：失効集合 R の行列 H に対して H\cdot X=0 を解き、候補だけ通す。
    • 確定段：通過者の行列 G に対して G\cdot Y=C を解き、0/1 を厳密に返す。

  • Bloom との違い：ビット配列を配るのでなく、方程式の“解ベクトル” X,Y を配るから、圧縮・差分が効く。しかも2段目で厳密。

1) 問題設定

  • 宇宙集合 U：CTログに載る（失効していないことも含む）証明書たち
  • 失効集合 R\subseteq U：いま失効している証明書
  • 目標：関数 f:U\to\{0,1\}、f(u)=1\iff u\in R を小さな配布物（スナップショット＋差分）で届け、端末ローカルで判定

2) 演算の土台：GF(2)

  • 値は 0/1。
  • 加法 a\oplus b は XOR（偶奇）：1 の個数が偶数→0、奇数→1。
  • 乗法 a\cdot b は AND。
  • ベクトルの内積 a\cdot z=\big(\sum_i a_i z_i\big)\bmod 2 は「AND→1の数の偶奇」。

3) 2段ロジック（行列ビュー）

3.1 近似段（“ふるい”）

  • ハッシュ h:U\to\{0,1\}^m を用意し、失効要素だけ並べた行列を

    H=\begin{bmatrix}h(u_1)\\ h(u_2)\\ \vdots\end{bmatrix}\ \ (u_i\in R)

  • **零空間（null space）**の列ベクトル X を選ぶ：

    H\cdot X=0

  • すると u\in R は必ず h(u)\cdot X=0 になり通過。
    u\notin R が たまたま0 になる偽陽性は残る（設計どおり）。

列数（何本の X を持つか）は

> \mathrm{rank}=\left\lfloor\log_2\frac{|U\setminus R|}{|R|}\right\rfloor >

目安：Rが疎なら列を増やして偽陽性を下げ、Rが密なら \mathrm{rank}=0（全通過）にして次段で決める。

3.2 確定段（“厳密判定”）

  • 近似段を通った集合 S=\{u\mid h(u)\cdot X=0\} について、別ハッシュ g で

    G=\begin{bmatrix}g(u_1)\\ g(u_2)\\ \vdots\end{bmatrix}\ (u_i\in S),\quad C=\big(\mathbf{1}[u\notin R]\big)_{u\in S}

  • 1列の解ベクトル Y を $\ G\cdot Y=C\ $ で求める。
    すると照会は g(u)\cdot Y=C(u) を返すだけ（Rなら 0、偽陽性は 1）。

ここで矛盾（0=1）が起きる少数は exceptions に入れて「個別に非会員扱い」して整合させる（安全弁）。

4) ミニ行列例（手計算で腑に落とす）

  • U=\{a,b,c,d\},\ R=\{a,c\}
  • h(a)=[1,0,1],\ h(c)=[0,1,1]\Rightarrow H=\begin{bmatrix}1&0&1\\0&1&1\end{bmatrix}
    \Rightarrow X=[1,1,1]^T は H\cdot X=0。
  • 照会：h(a)\cdot X=0、h(c)\cdot X=0 は通過。
    h(b)=[1,1,0]\Rightarrow 0（偽陽性）、h(d)=[1,0,0]\Rightarrow 1（落ちる）。
  • 通過者 S=\{a,b,c\} に対し、
    g(a)=[1,0,0], g(c)=[0,1,0], g(b)=[0,0,1]、
    C=[0,0,1]^T（Rは0、偽陽性bは1）。
    \Rightarrow Y=C。照会で g(a)\cdot Y=0,\ g(c)\cdot Y=0,\ g(b)\cdot Y=1 と厳密に分かれる。

「たまたま合うのでは？」→ 近似段は“たまたま”OKがあり得るが、確定段はCを満たすYを作っているので必然的に一致。解けない分は exceptions で落とす。

5) 実装の肝（Ribbon と Equation）

  • 1 件の要素を Equation（行）に：
    a(x)=b\oplus\sum a_i x_i（GF(2)）
    連続 64\times W ビットだけ非ゼロの疎な帯域を持ち、pivot（先頭の1）を必ず最下位にそろえる。
  • 挿入：同じ列（pivot位置）に既存行があれば XOR して右へ流す（GF(2)ガウス消去）。
    ゼロ行になったとき b=0 なら冗長 OK、b=1 なら矛盾 → exceptions。
    近似段は同次（b=0）なので例外は原則ゼロ。確定段は非同次で稀に発生。
  • 解く：後退代入で解ベクトル（列）を得る。ブロックを横に並べ、右から左へ“tail”を渡しながら解を連結（partitioned two-level cascade）。

6) Clubcard（配るもの）

  • 近似段の列群 X（本数＝rank）、確定段の 1 列 Y。

  • ブロックごとの index（offset, m, rank, inverted, exceptions）。

  • 照会：

    1. h(u)\cdot X_j=0 を全列で満たすか
    2. g(u)\cdot Y=0 か
    3. exceptions に当たらないか
    4. inverted なら結果反転（例：R=U を m=0,\ inverted=true で表現）

7) Bloom カスケードとの違い（要点だけ）

観点 Bloomカスケード Clubcard（Ribbon 二段＋Partition）
配るもの ビット配列 解ベクトル X,Y
2段の意味 どちらも近似 1段目=近似、2段目=厳密
圧縮/差分 密で効きづらい 構造ありで効く
例外 なし（別確認必要） exceptionsで矛盾を安全に補正
R=Uなど極端 表現が難しい m=0,\ inverted=true で自然
帯域（実例） 大きくなりがち ブログ例：平均**~300KB/日**

8) 例外（exceptions）の選び方と容量

  • いつ出る？ 挿入でゼロ行に落ち、右辺 b=1（0=1）になったとき → その要素を exceptions へ。

  • なぜ少ない？

    • 行数 m\approx(1+\varepsilon)|R| を少し余らせる。
    • 挿入順を R（b=0）→ U\setminus R（b=1） にして矛盾を U\R 側へ寄せる。
    • パーティションで局所化。

  • 例外はブロック内のキー列（discriminant()）として持つ。増えてもそのブロックだけの増分。

9) パーティション設計と“差分だけで済む”理由

9.1 パーティションは固定写像

例：

\text{block\_id}=\operatorname{prefix}_K\big(H(\text{issuer}\ \|\ \text{serial})\big)
  • これはルール固定。同じ証明書は常に同じブロックへ。
  • 失効の新旧でパーティションを選び直す必要はない。判定は中身（X,Y,例外）を差し替えるだけで変えられる。

9.2 どのくらいのブロックが“その日”変わる？

1日に新規失効が \Delta 件、ブロック数 P=2^K。
一様分布なら、その日触るブロック割合は

1-\left(1-\frac{1}{P}\right)^\Delta\ \approx\ 1-e^{-\Delta/P}.
  • 例：K=20(P\approx10^6)、\Delta=50{,}000 → 約4.7%。
    K を大きくすれば触る割合は下がる。

9.3 “差分だけ”で足りるわけ

  • CTログは追記型 → バックエンドは増分だけ取り込み、そのブロックの X,Y を再構成。
  • クライアントは そのブロックの列ベクトルと index メタだけ置換すればよい。
  • offset が動く場合も index を一緒に更新するので整合は崩れない。
  • さらに HTTP圧縮・辞書圧縮で小さくなる。

9.4 スナップショットとデルタ

  • スナップショット（~45日ごと）：完全状態を配り直し。必要ならこのタイミングで K を増やす等のエポック切替。
  • デルタ（12時間ごと）：変わったブロックだけ差し替え。
  • ブログの運用値（提示文より）：平均 ~300KB/日、スナップショット ~4MB/45日。

10) デプロイ実績（提示ブログの要点）

  • Firefox 137：デスクトップ全ユーザーに CRLite（Clubcard ベース）有効化。
  • プライバシー：失効照会はローカル完結（Mozillaにも送らない）。
  • OCSP 無効化：Firefox 142 で DV 証明書の OCSP を無効に。（OCSP はプライバシー漏洩＆中間者に見える／HTTPで平文／遅い）
  • 性能：OCSP はハンドシェイクを中央値 ≈100msブロック。CRLite 展開で 56.4ms→39.9ms に改善（ブログ掲載グラフ）。
  • サイズ：CRL 全量 ~300MB（非現実）、Chrome CRLSet 600KB/日で全体の1%のみ、CRLite は**~300KB/日で全失効**をカバー。
  • 今後：パーティション最適化、大量失効イベントの圧縮、HTTP辞書圧縮、証明書の短期化で帯域さらに削減。

11) Go 風・最小擬似コード（本質だけ）

// --- GF(2) 内積（AND→1の個数の偶奇） ---
func evalGF2(a, z []uint64, s int) uint8 {
    limb, shift := s/64, s%64
    var acc uint64
    for i := 0; i < len(a) && limb+i < len(z); i++ {
        seg := z[limb+i] >> shift
        if shift != 0 && limb+i+1 < len(z) { seg |= z[limb+i+1] << (64-shift) }
        acc ^= seg & a[i]
    }
    return uint8(bits.OnesCount64(acc) & 1)
}

// --- 1 行（Equation）：a(x)=b ⊕ Σ a_i x_i ---
type Eq struct { s int; a []uint64; b uint8 }

func (e *Eq) addAligned(o Eq) { /* pivot列が同じなら a^=o.a, b^=o.b, pivotをLSBに整列 */ }

// --- 行を積んで解く（Ribbon） ---
type Ribbon struct { rows []Eq; inverted bool; exceptions [][]byte }

func (r *Ribbon) insert(eq Eq) bool {
    for {
        // ゼロ行：b==0は冗長OK、b==1は矛盾→例外
        isZero := true; for _,v := range eq.a { if v!=0 { isZero=false; break } }
        if isZero { return eq.b == 0 }
        if eq.s >= len(r.rows) { grow := eq.s-len(r.rows)+1; r.rows = append(r.rows, make([]Eq, grow)...) }
        cur := &r.rows[eq.s]; empty := true; for _,v := range cur.a { if v!=0 { empty=false; break } }
        if empty { r.rows[eq.s] = eq; return true }
        eq.addAligned(*cur) // 衝突→XOR→pivot右送り
    }
}

func (r *Ribbon) solve(tail []uint64) []uint64 {
    // rowsの長さ＋tailぶんのビット長を確保して後退代入
    // （実装詳細は割愛：各行 i で z_i = evalGF2(row_i, z) ^ b）
    return z
}

// --- Clubcard：2段＋パーティション ---
type Index struct { Offset, M, Rank int; Inverted bool; Exceptions [][]byte }
type Card struct { X [][]uint64; Y []uint64; Index map[string]Index }

type Q interface {
    Block() []byte; Discriminant() []byte
    AsApprox(m, off int) Eq // h(u)
    AsExact(m, off int)  Eq // g(u)
}

func (c *Card) Contains(q Q) bool {
    meta, ok := c.Index[string(q.Block())]; if !ok { return false } // NoData
    if meta.M != 0 {
        e := q.AsApprox(meta.M, meta.Offset)
        for i := 0; i < meta.Rank; i++ { if evalGF2(e.a, c.X[i], e.s) != 0 { res := false; if meta.Inverted { res = !res }; return res } }
    }
    e2 := q.AsExact(meta.M, meta.Offset)
    res := (evalGF2(e2.a, c.Y, e2.s) == 0)
    for _, ex := range meta.Exceptions { if bytes.Equal(ex, q.Discriminant()) { res = false; break } }
    if meta.Inverted { res = !res }
    return res
}

12) まとめ

  • 数学の骨格：

    \text{近似：}\ H\cdot X=0,\quad \text{確定：}\ G\cdot Y=C,\quad \text{判定：}\ h(u)\cdot X=0\ \land\ g(u)\cdot Y=0.

  • 設計の肝：

    1. 2段目が厳密（Bloomと違う）、
    2. 解ベクトルを配るから圧縮・差分・局所更新が効く、
    3. パーティションは固定写像で、変わったブロックだけ差し替えれば良い。

  • 実績（ブログ要旨）：Firefox 137 でデスクトップ全体に展開、OCSP の中央値 ~100ms → CRLite でハンドシェイク 56.4→39.9ms、帯域は平均 ~300KB/日、DV の OCSP は v142 で無効化予定。

一言で：「Xで速くふるい、Yで確実に決める。配るのは“ビット配列”でなく“方程式の解”。」
だから軽く・速く・漏らさない。