【ITニュース解説】Your blocklist is 2.2 MB of strings. It only needs 550 KB.

インターネットを利用する上で、私たちは多くの広告や不必要な追跡（トラッカー）に遭遇する。これらをブロックするために「広告ブロックリスト」というものが使われている。このリストには、ブロックすべき広告配信サーバーやトラッカーのドメイン名（例えば「ads.example.com」のようなアドレス）が大量に記載されている。一般的なブロックリストには何十万ものドメインが含まれており、これら全てをテキスト（文字列）のまま保存すると、非常に大きなデータ量になるという課題がある。例えば、ある有名な広告ブロックリストは、テキスト形式で保存すると2.2メガバイト（MB）もの容量を必要としていた。

このデータ量の問題は、特に高性能ではない、メモリなどのリソースが限られた小さなデバイスにとって深刻である。ニュース記事に登場する「ESP32-C3」のような安価なマイクロコントローラチップは、一般的なパソコンやスマートフォンとは異なり、利用できるメモリ（RAM）が数百キロバイト（KB）程度と非常に少ない。このような制約のあるデバイスで巨大なブロックリストをメモリに全て読み込んで処理することは実質不可能である。これらのデバイスは、ウェブサイトへのアクセス要求が来たときに、そのドメイン名がブロックリストに含まれているかを高速に判断する必要があるが、大量の文字列の中から特定のドメイン名を毎回探し出す処理は、デバイスに大きな負担をかけ、動作が遅くなる原因にもなる。

そこで、この問題を解決するために非常に効率的な手法が考案された。それは、ドメイン名を文字列のまま保存するのではなく、「ハッシュ値」と呼ばれる短い数値に変換して保存するという方法である。ハッシュ値とは、元のデータ（この場合はドメイン名）から特定の計算（ハッシュ関数）によって生成される、固定の長さを持つ数値のことだ。同じドメイン名からは常に同じハッシュ値が生成されるが、ハッシュ値から元のドメイン名を復元することは非常に難しいという特性がある。

このプロジェクトでは、各ドメイン名を「FNV-1a」というハッシュアルゴリズムを使って64ビットのハッシュ値に変換し、さらにその下位40ビットだけを利用する。40ビットの数値は、たった5バイトのデータで表現できる。例えば、「ads.tracker.example.com」のような長いドメイン名も、5バイトの短い数値に変換されるのだ。このようにして、11万を超えるドメイン名がそれぞれ5バイトのハッシュ値に変換され、合計で550キロバイト（KB）のデータ量に削減された。これは元のテキストデータの約4分の1のサイズであり、2.2MBが0.55MBになったことになる。この大幅なデータ削減により、メモリの少ないESP32-C3のようなデバイスでも、ブロックリストを効率的にフラッシュメモリ（書き換え可能な記憶領域）に保存し、扱うことが可能になった。

生成されたハッシュ値のリストは、検索しやすいように数値順にソートされてフラッシュメモリに保存される。ユーザーがウェブサイトにアクセスしようとすると、そのドメイン名（例えば「ads.tracker.example.com」）とその親ドメイン名（例えば「tracker.example.com」「example.com」）のハッシュ値が計算される。そして、この計算されたハッシュ値が、デバイスに保存されているソート済みのハッシュ値リストの中に存在するかどうかを「バイナリサーチ」という高速な方法で探し出す。バイナリサーチは、ソートされたデータの中から目的のデータを探すのに非常に効率的なアルゴリズムで、リストの規模が大きくなっても少ないステップで検索を完了できる。これにより、広告ブロックの判断を非常に高速に行うことができるのである。

このハッシュ値を使う方法には、「ハッシュ衝突」という概念が伴う。ハッシュ衝突とは、異なる二つの元のデータ（ドメイン名）から、偶然にも同じハッシュ値が生成されてしまう現象を指す。このシステムにおいて、もしブロック対象である異なる二つのドメインが同じハッシュ値になったとしても、両方ともブロックされることに変わりはないため、これは特に問題にはならない。むしろ、データ量をわずかに節約できるという側面もある。本当に問題となるのは、「偽陽性（False Block）」と呼ばれる現象である。これは、ブロックリストには含まれていない無害なドメインが、偶然にもブロックリスト内の別のドメインのハッシュ値と同じになってしまい、誤ってブロックされてしまうことだ。

このような偽陽性の発生率は、ハッシュ値のビット長が長いほど低くなる。このプロジェクトでは40ビットのハッシュ値を使用しているため、偽陽性の発生率は非常に低い。具体的な測定結果では、約1000万回に1回の検索でしか偽陽性が発生しないことが示されている。これは、一般的な家庭のネットワークで1年間にアクセスする約2万個の異なるドメインに対して、誤ってブロックされるドメインがほとんど発生しないことを意味する。もしハッシュ値が32ビットと短ければ、1年間に1つか2つの偽陽性が発生する可能性があるとされているため、40ビットという選択は、実用性と安全性とのバランスが考慮されたものと言えるだろう。

このハッシュ値を利用したアプローチは、広告ブロックリストだけに留まらない、より広い応用範囲を持つ技術である。「このデータはリストの中にありますか？」という問いに答えるだけでよい、大規模なリストを扱うあらゆるシステムで有効だ。例えば、スパムメールの送信元ドメインリスト、ウェブブラウザの拡張機能に組み込まれたトラッカーリスト、セキュリティシステムで不正なアクセスを検出するためのIPアドレスやキーのフィンガープリントリスト、さらにはユーザーIDのリストなど、メモリに大量の文字列リストを保持している様々な場面で、この技術を適用してメモリ使用量を大幅に削減できる可能性がある。これにより、システム全体のパフォーマンス向上や、より小さなデバイスでの運用が可能になる。

ただし、この手法を採用することにはいくつかのトレードオフも存在する。まず、一度偽陽性が発生してしまうと、その誤ってブロックされたドメインは常にブロックされ続ける。元の文字列がないため、なぜブロックされたのか、ユーザーに具体的な理由を提示することができない。また、ハッシュ値から元のドメイン名を復元できないため、リストの個々のエントリを直接編集したり、例えば「親ドメインはブロックするが、このサブドメインだけは許可する」といった詳細なルールを設定したりすることはできない。デバイス上で手動で追加するドメインは、別に小さなリストとしてメモリに保持する必要がある。

リストの内容を変更する際には、全てのドメインを再度ハッシュ化し、ソートし直して新しいファイルを作成する必要がある。この「再構築」のプロセスは、現代のパソコンでは非常に高速（数秒程度）に行えるが、新しいファイルをデバイスに配布するコストが発生する。現在のプロジェクトでは、週に一度このプロセスを自動で行っている。また、ブロックリストのファイルが単なるハッシュ値の羅列であるため、ファイルが破損していないか、あるいは正しいリストであるかを検証する仕組みが必要となる。この点については、ファイルの先頭に識別子（マジックナンバー）やデータ整合性を確認するためのチェックサム（CRC）を追加する改善が進行中である。

まとめると、この技術は、大きな文字列リストを扱う際のメモリ消費量を劇的に削減し、リソースが限られたデバイスでも高速な検索を実現するための強力な解決策である。ハッシュ値の適切なビット長を選択することで、偽陽性のリスクを実用上問題ないレベルに抑えつつ、多くのシステムでその恩恵を享受できる。一方で、透明性の欠如やリスト編集の制限といったデメリットも理解し、システムの要件に合わせてこの手法の採用を検討することが重要となる。