FLoCとはなにか - ぼちぼち日記

1. はじめに

Google がChrome/89よりトライアルを開始しているFLoC (Federated Learning of Cohorts)技術に対して、現在多くの批判が集まっています。批判の内容は様々な観点からのものが多いですが、以前より Privacy Sandbox に対して否定的な見解を示してきたEFFの批判「Google Is Testing Its Controversial New Ad Targeting Tech in Millions of Browsers. Here’s What We Know.」が一番まとまっているものだと思います。

これまで Privacy Sandbox 技術に関わってきた身としては、各種提案の中でFLoCは特にユーザへの注意が最も必要なものだと思っていました。しかし、これまでのド直球なGoogleの進め方によって、FLoCのトライアル開始アナウンスから即炎上という流れに結果的になってしまったことは非常に残念で、なかなか複雑な気持ちで見守るしかありませんでした。

このエントリーを書くにあたり、各種批判を否定するつもりは全くありませんし、このブログを読んで頂いた方にその考え直してもらいたいとも思いません。いくつかの批判を読むと自分でも納得する指摘もあります。

しかし先日、個人的に FLoC Simulator を作成して、いくつかFLoCの不明点をGoogle側に確認し、そのシミュレーションを行いました。「FLoC Simulation and Algorithm #95」その際、FLoCを実際に自分の手で計算してみると「なるほどなぁ、こんな仕組みだったのか」と関心してしまうことが多かったのも事実です。

そこで、今騒がれている FLoC とはいったいどういう技術なのか？どうやってidを生成しているのか？その中身を純粋に広く知ってもらうのもよいのではないかと考え、自分の備忘録として書いてみたいと思います。

結局、長いエントリーになっちゃいました。長文嫌いな方は、読むのを避けてください。

2. Disclaimer

繰り返しになりますが、このエントリーはFLoCの技術的な仕組みについてだけ書いたものです。技術以外の部分、例えばFLoCに関する倫理的・法的な問題などについては全く触れるつもりはありませんので、ご了承ください。

3. Privacy Sandboxとは

Googleが提唱しているPrivacy Sandboxは、大きく以下の2つを機能を実現することを指します。

ブラウザフィンガープリントやキャッシュ探索などによる隠れた(covert) tracking の防止
3rd party cookie の廃止に伴う代替技術群の実現

その目的は、ユーザプライバシーに(一定の)配慮をしながらWeb上の広告エコシステムを(ある程度)維持していくことである、と私は理解しています。

現在のChrome/90で Privacy Sandbox の Origin Trial (OT) を開始しているのは、Trust Token API、 Attribution Reporting API (旧 Conversion Measurement API)、 First Party Set、 FLoC の4つになります。

OTとは、Chrome に導入された先行試験実装に対して token をサイトに仕込み、期限限定で試験機能の評価・検証を行う仕組みです。昔、先行試験機能はベンダープレフィックスなどを使ってリリースされていましたが、いつの間にか試験機能のAPIが広く使われて固定化されてしまう事例が発生しました。OTはその問題(API Burning)を避けるために開発されました。

Privacy Sandbox で提唱されている新機能の多くは、W3CのWICG(Web Platform Incubation Community Group)上で仕様ドラフトが議論されます。ChromeではこのOTを通じて Privacy Sandbox のフィールド試験が進められ、その効果や仕様の見直しなどが行われます。WICGで議論・検証された仕様ドラフトが十分評価されれば、晴れて将来的に標準化への道が拓ける見込みになります。

他のPrivacy Sandboxの各機能を説明すると、それぞれブログが数本書けてしまうほどなので、ここではFLoCだけに限定します。

Privacy Sandboxの技術の中で特に広告技術に関連した提案には、鳥にちなんだコード名が付けられます。FLoCは、英語で「群れ」を表す「flock」に掛けていると言われています。

現在のOTは、 FLoC の頭文字になっている Federated Learning(連合学習) を利用していませんので注意してください。当初Googleは連合学習を利用したアルゴリズムを検討したけれども、結局今回のOTでは連合学習を使わない方法になり、しかし名前を変えずにそのままにしてあるといった経緯のようです。

以下、FLoCの説明については、2021年5月時点でOTを行っている "chrome.2.1" のアルゴリズムバージョンをベースに話を進めます。現在のFLoC OTは、アルゴリズムの効果測定や評価検証も大きな目的の一つですので、将来的にFLoCアルゴリズムが大きく見直される可能性が高い、ということを前提にエントリーを読んでください。

4. FLoCとは

Googleを始めとしてWeb上で提供されている広告は、一般的に大きく以下の３つのカテゴリーに分かれてます(自分はadtechの専門家じゃなく、世の中にこの３種類しかないとはっきり断言できないので、他にもあるかもしれません）。

コンテンツ連動型広告(Contextual Advertising)
ユーザーの興味/関心に基づく広告(Interest-Based Advertising)
追従型広告(Remarketing/Retargeting)

FLoCは、2の「ユーザーの興味/関心に基づく広告(オーディエンスターゲティング)」に用いられる技術です。FLoC によって一定期間内ユーザの閲覧履歴、主に広告表示されているサイトドメイン(eTLD+1)の履歴が、数千人単位でグループ化されます。

ただしFLoCだけで全てが実現できるわけではありません。FLoCは単純にユーザグループに割り振られた番号(Cohort Id)を出力するだけです。そのidと広告主やadtechベンダーが持つオーディエンスデータ(ユーザ属性・興味・関心・購買志向のデータ)を組み合わせることによって、初めてFLoCを使ったオーディエンスターゲティングが可能になります。

実はこのオーディエンスターゲティングは、現在でも 3p cookie を最大限に利用して実現できているものです。

3p cookie はユーザ行動を第3者に丸見えの状態にし、これまでそのデータを活用してオーディエンスデータの収集・分析が行われていました。世間からの要請もあり Googleは 3p cookieを廃止し、ダダ漏れ状態であるユーザの閲覧履歴を収集できないようにすることを決めました。しかしその代わりに、ユーザの閲覧行動をブラウザ内に閉じた処理で数値化し、それを数千人単位にまとめるFLoCを開発しました。これで現在よりもユーザプライバシーが配慮された、かつこれまでと同じぐらいの効果を持つオーディエンスターゲティングが実現できるであろうとの考えです。「今までよりマシな仕組みを作ったのになんでこんなに非難されなきゃいけないの？」といった愚痴が聞こえてきそうです。

5. FLoC Simulator

今までよりマシで効果も高い、と言われても本当にそうなのか。技術的にその仕組をちゃんと知っておきたいものです。そこでFLoCの仕組みを理解し、効果を評価できるよう Chrome のFLoCアルゴリズムの実装部分をそのままGoに移植した FLoC Simulator を作成しました。

FLoC Simulator は、7ドメイン以上のホストリストをJSON形式で用意すると(host_list.json)、コマンドラインで Cohort Id を出力してくれるものです。

例えばこんなドメインリストでは、以下のような Cohort Idが計算されます。

$ cat host_list.json
[
  "www.nikkei.com",
  "jovi0608.hatenablog.com",
  "www.nikkansports.com",
  "www.yahoo.co.jp",
  "www.sponichi.co.jp",
  "www.cnn.co.jp",
  "floc.glitch.me",
  "html5.ohtsu.org"
]

$ ./floc_sample host_list.json
domain_list: [nikkei.com hatenablog.com nikkansports.com yahoo.co.jp sponichi.co.jp cnn.co.jp floc.glitch.me ohtsu.org]
sim_hash: 779363756518407
cohortId: 21454

上記シミュレーションでは、21454 の Cohort Id が計算されています。検証・比較のため、下図の同じドメイン履歴を持つ Chrome でも同じ 21454 が出力されているのがわかります。 f:id:jovi0608:20210506151511p:plain f:id:jovi0608:20210506151449p:plain

ソースを見ていただければ、わずか数キロバイトの処理とGoogle側のサーバから配布されるファイルを組み合わせてCohort Idの計算が行われていることがわかります。関数や変数名はできるだけChromeの実装に合わせています。

6. FLoCの仕組み

FLoCアルゴリズムのコア部分は、データマイニングなどの分野で利用されている Locality Sensitive Hash(LSH: 局所性鋭敏型ハッシュ) という技術を使います。これは似たような文章を探したり、同じ特徴を持つ画像を探したり、といった最近傍探索（Nearest neighbor search) で利用される技術です。FLoCではLSHの一種であるSimHashが採用されています。 SimHash は、16年ほど前にGoogle検索で(ほぼ)重複したWebコンテンツ(near-duplicated web contents)を検知するのに使われていたアルゴリズムです。

6.1. だいたいのFLoC計算の流れ

Chrome内で行われているFLoCの処理は、おおよそ以下の4つの部分に別れています。

navigation時にFLoC対象のページ履歴にフラグを付ける
7日間に一回、履歴からSimHashを計算し、Chrome SyncでGoogle側に送る
(FLoCバージョンで1回実施) Google側でユーザのSimHashをまとめ上げてクラスター化する。ブロックするCohort Idを特定し、クラスターファイルを生成し、全Chromeユーザーへ配布する
サイトのFLoC APIの実行に伴い、SimHashとクラスターデータから Cohort Id を計算し、出力する

f:id:jovi0608:20210506151227p:plain

このうち 3. は、事前にGoogle側で処理が行われます。OT期間中に再度3の一部処理が行われ、FLoCバージョンが更新される予定であると github issue で回答がありましたが、現在のところまだ実施されていません。

6.2. FLoCアルゴリズムの詳細

各ステップをもう少し細かく見ていきましょう。

6.2.1. navigation時にFLoC対象のページ履歴にフラグを付ける

ユーザが navigation したページが、以下の3つの条件が全て満たされる場合に FLoC の計算対象となります。

navigation の IP がPublicルーティング可能であること
メインドキュメントの permission policy がFLoCを許可していること
広告が表示されているページ、又は FLoC API (document.interestCohort()) が実行されているページであること

navigation 完了後ユーザ履歴に保存される際に、上記FLoCの対象ページかどうかのチェックが行われ、フラグが付けられることになります。

実は 1. のIP チェックは socket アドレスに対するものなので、「Private IPを持つ内部Proxy経由で外部のサイトを閲覧した場合、全部 FLoC の対象外になっちゃうんじゃない？」とgithubで聞いたら、「試してないけどそうなる」との回答でした。FLoCの利用を回避するハックとして使えるかもしれません。興味のある方がいらっしゃれば検証してください。

6.2.2. SimHashを計算する

ユーザ履歴が7ドメイン以上残っている場合、履歴中の ドメインデータ (= eTLD+1) から計算されます。SimHash計算は、7日毎 にスケジュールされています。

現在の FLoC OT のコアアルゴリズム、LSHの一種であるSimHashとはどういうものでしょうか？

Hashという名前が付いているように、SimHashは任意のサイズのデータを一定の小さなサイズに変換させる機能を持ちます。5年前に20億人を超えたと公表されたChromeユーザは、現在では世界で7割近くのシェアを持つと言われます。FLoC計算対象となるChromeユーザの履歴パターンは膨大なものになるでしょう。それを使えるようにするには、一定のサイズ以下に収めないといけません。そのためユーザ履歴のHash化は必須です。

しかし通常利用されるSHA256などの暗号学的ハッシュをユーザ履歴に適用すると、データサイズを減少させることはできるものの、ハッシュ後は複数の元データ間の関連性をうかがい知ることはできません(原像攻撃に対する防止)。

先に述べたLSHは、似ているデータを近いハッシュ値に変換させるのが特徴です。そこで FLoC の SimHash では、データを多次元ベクトルで表現し、データ間の近さを表す指標としてベクトルの角度を利用します。 SimHashのキモは、いくつかランダムなベクトルを用意し、ユーザデータとランダムベクトルとの角度の関連性からデータの類似性を導出し、同時により低次元のベクトルにサイズを減らす変換を行うことにあります。

あるユーザデータのベクトル(User)に対して1bitのSimHashを計算する場合、1つのランダムベクトル(rv)を用意して下図のような計算を行います。赤色のrv と User のベクトル角度θに注目し、cosθが正値又は0の場合は1，負値の場合は0のビットで表します。この場合２つのベクトル内積の値を計算すると正負が求められます。 f:id:jovi0608:20210506151434p:plain 赤色rvと垂直な平面(破線のrandom hyperplane)から見てみると、ユーザベクトルの先が赤色破線上部のエリアにいるとSimHash=1となり、下側にいると0になります。SimHash:1の複数ユーザデータ間で比べると、SimHashが1のデータは似ているもの、0のユーザデータは似ていないもの、と区別することができます。そしてユーザデータは類似する1bit値にハッシュ化されました。

1つのユーザデータを1bitのSimHashに変換するだけではわかりにくいので、２つのユーザデータ(UserA、 UserB)を使い、3bitのSimHashに変換してみます。

下図の様に、赤・緑・青の3つのランダムベクトル(rv1, rv2, rv3)を用意します。3種類のランダムベクトルとユーザベクトル(UserA, UserB)の角度でSimHash Bitを決めます。その結果、UserA の SimHash は 100、UserB の SimHash は 101 となることがわかります。。頭2bit分だけ同じの3bitハッシュ値に変換されたことになります。もしUserB の角度がもう少しrv3の random hyperplane を超えて User A に近ければ同じハッシュ値になっていたでしょう。 f:id:jovi0608:20210506151252p:plain ランダムベクトルが増えていけば、囲い込まれる部分が狭まり、複数のユーザデータの類似性をより精度高く比較することができます。FLoC では、50個のランダムベクターを使い、ユーザ履歴の情報を50bitのSimHashに変換させます。

6.2.3 ユーザ履歴のドメインデータをベクトル化し、SimHashを計算

では、ユーザ履歴のドメインデータをどうやってベクトル化するのか。インターネット上のドメイン(eTLD+1)の上限数を決めることはできません。そこでGoogleが開発した CityHash64 という非暗号学的ハッシュを使い、ドメイン名を64bitの数字に変換します。そうすると任意のドメイン名が、2⁶⁴個のどれかの数字にマッピングされます。そこでドメイン履歴を2⁶⁴次元のベクトルにして、該当するドメインはドメイン名のCityHash64値をインデックスの要素値を１としたベクトルとして表します(one-hot domain encoding)。

example0.com ドメインの場合、CityHash64をかけると 3771499692761966109 になります。example0.com ドメインのユーザ履歴は、3771499692761966109番目の値を1にした2⁶⁴次元のベクトルに変換するわけです。

その結果、例えばユーザが [example0.com, example1.com, … , example99.com] のドメイン履歴を持っているとしたら、それぞれのドメイン名のCityHash64値番目のインデックスが1となるベクトル(0,...,1,...,1,..1,...,0)のような、100個の1を持つベクトルになります。

このユーザ履歴のドメインベクトルを50bitのSimHashを変換するには、50個のランダムベクトルを用意します。ユーザごとにランダムベクトルが変わってしまうのは困るので、要素の位置をSeedにして決定論的に決まる乱数ベクトルを生成します(コード中では randomGaussian 関数を指します)。こうすれば異なるブラウザ内でもユーザごとに変わらず、同じ乱数ベクトルを生成できます。

ここで生成したガウス分布の乱数ベクトルとユーザ履歴ドメインのベクトルとの内積を取ると、下の図の様に単純に乱数値を加算することと同じになり、加算後に正負を判定すると SimHash ビットを求めることができます。これを50個のランダムベクトルに対して同じ処理すれば、50bitのSimHashの計算が完了です。 f:id:jovi0608:20210506151412p:plain SimHashのコアアルゴリズムのコード部分を以下に示します。SimHashの計算自体、非常にスッキリしていることがわかるでしょう。

func simHashBits(input []uint64, output_dimention uint8) uint64 {
        var result uint64 = 0
        var d uint8;
        for d = 0; d < output_dimention; d++ {
                var acc float64 = 0;
                for _, pos := range input {
                // randomGaussian は2つの整数をSeedにしてガウス分布の乱数を生成する関数
                        acc += randomGaussian(uint64(d), pos)
                }
                if (acc > 0) {
                        result |= (1 << d)
                }
        }
        return result
}

func SimHashString(domain_list []string) uint64 {
        var input []uint64
        for _, domain := range domain_list {
                hash := CityHash64V103([]byte(domain))
                input = append(input, hash)
        }
        sim_hash := simHashBits(input, 50)
        return sim_hash
}

早速 floc_simulator で、example0〜98.comまで一緒で最後の100個目のドメイン履歴(example99.com と example100.com)が異なる場合のSimHashを計算してみます。

SimHash([example0.com, example1.com, ..., example98.com, example99.com]):  10011000111000001101111010001011010110010000010110 (672366295082006)
SimHash([example0.com, example1.com, ..., example98.com, example100.com]): 10011000111000001100111010001011010110010001010110 (672365221340246)

上記の通り、50bit中48bitが同じで2bit分が異なるSimHash値が計算できています。このデータを使えば、ユーザ閲覧ドメインの類似性が評価できます。

6.2.4. SimHashのクラスター化とセンシティブ情報のブロック

ブラウザー内でSimHashを計算できればFLoCは終わりではありません。 SimHashでユーザ履歴のドメインリストが近いユーザ集団を特定することはできますが、SimHashの値をそのまま利用すると以下の問題が発生します。

同じSimHashを持つユーザが少ない場合、個人が特定される恐れがある。
センシティブなカテゴリーの割合が多いユーザ履歴では、センシティブな情報に偏ったCohort Idが生成されてしまい、本来他人に知られたくないセンシティブなユーザ情報が第３者にわかってしまう。

そのためFLoCではSimHashの値をそのまま利用することはせず、計算したユーザのSimHash値を一旦Google側に送り、いくつかまとめるクラスタ化処理を入れます。 Googleへのデータ送信は、ユーザ履歴やプロファイルなどをGoogleアカウントと一緒に同期する Chrome Sync の仕組みが利用されます。

Google側でのSimHashのクラスタ化では以下の２つの処理が行われます。

ユーザから送られたSimHash値をソートし、2000人以上のユーザを含むようにSimHash群に分割する。SimHashの分割群に対して小さい順にIdを割り振りCohort Idとする。
Cohort Id 内に含まれるドメインを洗い出し、センシティブなカテゴリーを含む割合が平均より10%以上大きければそのCohort Idに対して blocked のフラグを付ける。

ここではSimHashを集めてソートして分割しているだけなので、教師あり学習を全く実施していません。なので現在のFLoC OTは、連合学習(Federated Learning)を利用していないということになります。

センシティブなサイトのカテゴリーとして、Googleは以下の項目を定義・管理しています。もちろん具体的なサイトがどこなのかは非公表です。

禁止カテゴリ: アルコール、ギャンブル、カジノ、臨床試験の被験者募集、制限付き薬物に関するもの、13歳未満のユーザ
個人的な苦難: 健康、厳しい経済状況、人間関係、犯罪、虐待や心的外傷、マイナス思考の強制
アイデンティティや信条: 性的指向、政治的思想、政治に関するコンテンツ、労働組合への加入状況、人種や民族、信仰、社会的に阻害された集団、トランスジェンダーの性別認識
性的な関心: 避妊、性的なコンテンツ
機会へのアクセス(米国、カナダ向け): 住居、求人、クレジット情報

クラスタ化した結果のデータは、Google側がバイナリーファイルにまとめてcomponent updator によって各ユーザに配布されています。

MacOSの場合、FLoCのクラスターファイルは、~/Library/Application Support/Google/Chrome/Floc/1.0.6/SortingLshClusters として保存され、クラスターデータが1バイト長でエンコードされています(blocked flag:1bit長とクラスタのSimHashサイズのビット数:7bit長)。

SimHashからクラスターデータを使ってカウントすると下図のように Cohort Id が計算できます。 f:id:jovi0608:20210506151313p:plain 現在 Cohort Id:2 がセンシティブカテゴリーを平均より10%以上の割合で含んでブロックされています。そこに当てはまった全てのユーザの Chort Idは、空の文字列が返されます。Cohort Id:2 以外にも全体の2.3%にあたる792個の Cohort Id がブロックされています。

SimHashの値に該当するスロットを見つければ Cohort Id の計算は完了です。5の例で計算した SimHash は 779363756518407 なのでちょうど21454番目のクラスターに入ります。例で示した通り Cohort Id は 21454 です。

クラスタ化の結果、Cohort Idの最大値は33871でした。各Cohort Idには最低2000人のユーザが含まれているので 33,871x2,000人=67,742,000人となり、最低でも6774万人以上のユーザ履歴データがGoogleで集計されていることがわかります。

クラスターデータが変わってしまうと過去のCohort Idとの互換性が損なわれてしまいます。今回のFLoCのOT中は、blocked の更新を行うことはするが、クラスタを変更を加えるようなアップデートは行わないと回答をもらっています。

7. まとめと今後

ということで、FLoCのCohort Id計算がどう行われているのか、技術的にかなり細かく説明しました。

example???.com というドメイン名を使った自分のシミュレーション結果では、1000ドメイン近くの履歴がないと多少の履歴の違いでも Cohort Id が異なってしまうという結果が出ました。一般のユーザが7日間に1000ドメインも閲覧することはなく、数十レベルだろうとのコメントをgithubでもらっています。もちろんハッシュをかけるドメイン名によって、シミュレーション結果はがらっと変わってしまいます。ドメイン数が少ないと少し履歴が違うだけで異なるCohort Idに計算されてしまうことが多いので、果たして現在のアルゴリズムでどこまで的確なオーディエンスターゲティングができるのだろうか、と考えてしまいます。

また最近、ChromeのFLoCに関して、以下２つの処理が新しく入りました。