50KBのRAMに広告ブロック用50万ドメインを詰め込んだファームウェア

Raspberry PiでPi-holeを動かすのも悪くないですが、 数千円の出費 （アフィリエイトリンク）がかかる上にコンセントを常時占領してしまいます。そこでM-Abozaidが同じことを 安価なESP32-C3スティック （アフィリエイトリンク）で実現してしまいました。このファームウェアはわずか50KBのRAMで537,000件の広告ドメインをブロックし、ブロック対象のDNSクエリに10ミリ秒以内で応答できます。

これで興味を持ってもらえたと思うので、仕組みを説明しましょう。通常のPi-holeはブロックリスト全体をRAMに読み込みます。ところがESP32は数百KBのRAMしかなく、PSRAMも搭載していないため、50万件ものドメインをそのまま乗せるのは技術的に不可能です。そこで開発者は一工夫して、ブロック対象の各ドメインを最大5バイト（40ビット）のハッシュに変換することにしました。

生成したハッシュはすべてソートされ、チップのフラッシュメモリに直接書き込まれます（4MBあれば十分）。DNSクエリが来ると、ファームウェアはリクエストされたドメインをハッシュ化し、フラッシュ上で二分探索を実行します。537,000件のエントリを絞り込むのに必要な読み込みはわずか約18回--これがあの10msの秘密です。RAMはリスト保存には一切使われず、ネットワーク処理の実行だけに使われます。

さらに巧妙なのは、40ビットのハッシュではほぼ衝突が起きないという点です。141,000ドメインまでは衝突ゼロ、537,000ドメインでもたった1件--実質無視できるレベルです！

とはいえ、今のところPi-holeの完全な代替にはなりにくいです。DHCPサーバー機能がないのと、OTAファームウェアアップデートを有効にするには2つのパーティションが必要になるため、ESP32が扱えるドメイン数が250,000件に下がってしまいます。

ダッシュボードはなかなか見やすく、c3adblock.localというmDNSアドレスでアクセスできます。クライアントごとのブロック数カウンター、特定デバイスのアクセス遮断、独自ドメインの追加ブロックといった機能も備えています。

個人的には、Pi-holeの完全な置き換えというより「バックアップDNSリゾルバ」として使うのがベストだと思います。メインのDNSサーバーの後ろに置いておけば、障害時にこの小さなスティックが格安で自動的に引き継いでくれます。動画でも分かるように、ルーターのUSBポートから給電できるのも便利なポイントです。

MITライセンスの完全オープンソースで、StevenBlackやHageziのリストからハッシュテーブルを生成するPythonスクリプトも付属しています。今後の予定としては、どのドメインにもマッチしない99%のクエリでフラッシュ読み込みをスキップするためのBloomfilterのRAM実装や、前述のDHCPサーバー機能が計画されています。

自前のDNSサーバーに興味があるなら、以前紹介した Pi-hole・Unbound・BINDをまとめて置き換えるTechnitium [FR] もチェックしてみてください。数百円のESP32を使ったハックなら、 AppleのTouch IDを再現したもの [FR] なんかもあります。

USBメモリより小さなチップで50万件の広告ドメインをブロックとは、なかなかやりますね！気になる方は GitHubのリポジトリ をどうぞ。

ソース