ポルまいと学ぶ！ATProtocol入門 ~Merkle Search Tree編~
🦁「麻衣ちゃん！聞いて〜！BlueskyっていうSNS始めたんだ！」
🦁「でね、Blueskyって、なんかXと違って分散型っていうのがすごいって聞いたんだけど、分散型ってどういうことなの？麻衣ちゃん！教えて！」
💻「おもしろいところに目をつけたわね。突然だけどポルカ、TwitterをBANされたことはある？」
🦁「あるよ〜💦、なにも悪いことしてないのに、みんなの投稿が見れなくなって、困っちゃったんだ〜。」
💻「そう、それが中央集権型SNSと呼ばれる、既存のSNSの問題なの。ひとつの企業がSNSの治安を守らなくてはいけないから、どうしてもモデレーションのミスが起きやすい。しかも、企業はユーザーを囲い込むことで利益を得られるので、BANされたあとの脱出口も用意してはくれないの。」
🦁「脱出口？」
💻「例えば、もしTwitterをBANされても、いきづらい部のみんなの投稿を、同じように見れる別のアプリがあれば問題ないじゃない？」
🦁「それなら困らない！」
💻「でも、現状、みんなの投稿はすべてX社のサーバーに保存されていて、X社はそれをオープンにしていないの。だから、みんなの投稿を読めるアプリを第三者がつくることはできない。」
💻「分散型SNSは、そういった不当なモデレーションや、ユーザーにとって不利益となる囲い込みが起きないような仕組みを実現したSNSなの。」
🦁「麻衣ちゃんもBANされたことあるの？」
💻「あるわよ💩」
💻「それはそれとして、分散型SNSにもいろいろ考え方が違うものがあるのだけど、せっかくだから今日はポルカが始めたBlueskyが使っている、ATProtocolという仕組みについて見ていきましょう。」
🦁「楽しみ〜！」
💻「それはそうと、ポルカ、アカウントは戻ってきたの？」
🦁「戻ってきたよ！」
💻「相変わらず、運だけはいいのね…」
🦁「えっへん！豪運のヨネの孫ですから！」
ATProtocol？何それ？知らん？らん！
🦁「ATProtocol？それを使うとどんないいことがあるの？」
💻「ATProtocolは、さっき挙がったような問題が起きないようにするための、SNSを作る上での決まり事よ。」
🦁「決まり事？」
💻「たとえば、Xのようなプラットフォームは、投稿の本体を持たず、検索用のコピーしか持ってはいけない。という決まりを作るの。」
🦁「じゃあ、投稿の本体はどこに置かれるの？」
💻「投稿の本体は、PDS(Personal Data Server)という、専用のデータ置き場サーバーに置かれるわ。このサーバーは、誰でも建てることができるから、自分で誰にデータを預けるかを選択することができる。」
🦁「そしたら、プラットフォーム側はポルカの投稿を消したりできないね！」
💻「そう、プラットフォームが、データの源泉からただの検索サーバーに変わるの。ATProtocolの世界では、この検索サーバーのことをAppViewと呼ぶわ。」
💻「今挙げたPDS、AppView、それぞれ別々の人が建てることもできるの。SNSを細かいパーツに分けて、それぞれ別々の管理者をたてられるようにしたことが、ATProtocolの分散型SNSとしての特徴ね。」
🦁「あれ？でも気づいちゃったんだけど、もしPDSの管理者が悪い人で、ポルカの投稿を勝手に書き換えちゃったら？Xならある程度信頼できるけど、運営者がよく知らない人だったら完全に信頼できないよ？」
💻「いい質問ね！管理者がたくさんいて、全員を完全に信頼できる環境にない分散型SNSだからこそ、自分で自分を守る仕組みが必要なの。それが、暗号よ。」
🦁「暗号？謎解きゲームの話？」
💻「謎解きゲームの暗号とは少し違って、ATProtocolが使っている暗号は、デジタル署名というものね。これは、秘密鍵という秘密の値を使ってデータに署名すると、公開鍵という値を使って、そのデータが確かに対応する秘密鍵の持ち主によって作られたものだと、数学的に証明できる仕組み。」
🦁「数学〜！？わかんないよぉ〜😫」
💻「誰にも頼らずに、あるデータを自分が作ったことを証明できる技術、と言えばわかりやすい？」
🦁「それならわかる気がする！」
💻「ATProtocolは、このデジタル署名技術をつかって、PDSの管理者が悪意を持ってデータを書き換えても、すぐにそれを検出できる美しい仕組みがあるの。それが、Merkle Search Treeというデータ構造よ。」
Merkle Search Tree(ハッシュ編)
🦁「まーくる、さーち、つりー？ツリーって、木ってこと？」
💻「そう、Merkle Search Treeは、木構造と呼ばれる種類のデータ構造の一種ね。」
💻「さっき話したデジタル署名を使って、SNSのデータに署名をしたい。ポルカならどうする？」
🦁「えーっと、投稿の最後に署名をくっつければいいのかな？」
💻「そうね、そうすれば、その投稿を書いたのはポルカだということが証明できる。」
💻「じゃあ、ポルカの使っているPDSの管理者が、ランダムに一つ投稿を選んで書き換えたとする。どうやって書き換えられた投稿を探す？」
🦁「一つずつ投稿の署名を確認する！」
💻「投稿が少ないならそれでいい。たとえば、投稿が1000件あったら？」
🦁「大変だぁ〜😫、こういうときは🌻 まいまいに聞いてみよう🐌✨ 助けてまいまい〜⛩✨」
💻「今は無理 明日ね💻」
💻「…とならないようにするために使うのが、ハッシュ関数よ。」
🦁「ポテトの話？また食べさせてもらいたいの？」
💻「その話じゃなくて！」
💻「ハッシュ関数というのは、こういう性質をもつ関数なの。」
- 同じ入力からは、必ず同じ出力が出る
- 入力とは全く関係のない値が出てくる。入力が少しでも変われば、全く違う値が出てくる。
- 出力から入力を予測することができない
💻「下2つは、ハッシュ関数の中でも、暗号学的ハッシュ関数の性質ね。」
🦁「これがあるとなにが便利なの？」
💻「たとえば、ポルカの投稿を時系列に並べて、一件前の投稿のハッシュ値を投稿本文に持つようにする。」
💻「で、投稿を読むときは、必ず自分の手元で1件前の投稿のハッシュ値をとって、読んでいる投稿に書いてあるハッシュ値と比較する。」
💻「こうすると、署名するのは最新の投稿1件でいいの。」
🦁「すごい！でもどういうこと？」
💻「たとえば、PDSの管理者がポルカの投稿を書き換えたとする。」
💻「ハッシュ関数の性質から、投稿を書き換えるとその投稿のハッシュ値も変化するので、当然その前のハッシュも書き換えないといけない。でもその前のハッシュを書き換えたことは、更にその前も…という風に、ハッシュを連鎖させることで書き換えがとても難しい構造を作ることができるの。ハッシュチェーンといって、ブロックチェーンなんかでも使われている仕組みね。」
🦁「う〜ん、よくわからないけど、とにかく署名検証が1回で済むんだね！」
💻「そういうこと。最新のハッシュは、投稿の履歴全体の状態を表しているとも言えるわね。」
💻「ただし、こんな風に投稿が横並びだと、ハッシュを検証したり、特定の値を探したりするコストが高いの。そのために、Merkle Search Treeというデータ構造が登場するわ。」
Merkle Search Tree(検索木編)
💻「Merkle Search Treeは、このハッシュチェーンの考え方を、検索木に応用したものよ。」
🦁「検索木？さがしやすい、ってこと？」
💻「そう。さっきも言ったように、投稿が横並びだと左から順に探していくしかないので、コストがかかる。そこで、深さという概念を導入するの。」
💻「Merkle Search Treeには、keyという、データを一意に表す値があって、その値は辞書順に並べる、という決まりがある。」
🦁「辞書順…？、あ！abというkeyとbcというkeyがあったら、ab, bcのように並べる、ってこと？」
💻「そう。辞書順に並べた上で、横並びの量を減らしていくの。」
💻「たとえば、a, b, c, d, eというkeyがあるとする。dというkeyの値を得たいので、dを探す。」
💻「まず、木の根っこを見ると、(bより小さい値のみの部分木への参照), b, (b以上c未満の部分木への参照), c, (cより大きい値のみの部分木の参照)というデータがある。dはcの次だから、何を見に行くと思う？」
🦁「えっと、cより大きい部分木？」
💻「そう。すると、cより大きい部分木にdの値がある。」
💻「bより小さいaの部分木には一切触っていないの、わかる？」
🦁「ほんとだ！すごい！」
💻「こういう風にして、横並びの量を減らしていくことで自然と高速に取得できるような構造なの。」
💻「ここまでは普通の検索木なんだけど、さっき(bより小さい値のみの部分木への参照)という書き方をした部分は、実際にはその木へのCIDで表されているわ。」
🦁「CID…？、略語ばっかりでわからないよぉ〜！」
💻「Content Identifierの略で、仕様が厳格になっているだけで、さっき説明したハッシュ値と変わらないわ。」
💻「一つ違うのは、CIDはBlockStoreという仕組みで使われていて、CID自体が実データへのポインタになっているというところ。…まぁ、このあたりはまた複雑なので、また今度にしましょう。」
💻「このハッシュ値を参照として持っている構造、ハッシュチェーンになっていると思わない？」
🦁「投稿を順番に並べていたときと一緒だ！」
💻「あとは、木の根っこのCIDに対して、署名をすればいい。」
🦁「あれ、でも、木の深さってどうやって決めるの？ランダム？」
💻「いい質問ね！実は、こういう検索木は、左右どちらかに値が偏って、木の形が歪になると、検索効率が落ちてしまうの。Merkle Search Treeは、この問題もハッシュ値で解決している。」
💻「ハッシュ関数の性質で、入力と全く関係のないランダムな値が出る、って言ったでしょ。このランダムさを利用するの。まず、追加したいkeyのハッシュ値を取って、それを二進数で表して、先頭に0が並んでいる数でlayerを決定するの。」
🦁「二進数！麻衣ちゃんが得意なやつだ！」
💻「検索木の部分木同士の参照をハッシュ値で持つ、というだけで、高速に検索できる検索木の特性と、素早い検証が可能になるハッシュチェーンの特性を同時に得ているの。美しいと思わない？」
🦁「う〜ん、難しくてよくわからないけど、ハッシュ関数が便利だってことと、麻衣ちゃんが興奮してることはわかった！踊っちゃう〜！」
おわりに
💻「ATProtocolはもっと色々な要素があって複雑なんだけど、私はリポジトリ構造が一番美しいと思っているの。」
🦁「詳しいところはよくわからなかったけど、すごい技術だってことはわかったよ！ポルカが使っているSNSの裏側でそんなことが起こっているなんて、知らなかった！」
🦁「なんか難しかったけど、ポルカのBlueskyはもう誰にも消せないってこと！？すごい！踊っちゃう〜！」
💻「…厳密には違うけど、まぁそういうことにしておいて💻」
💻「それとポルカ、Blueskyで歌うのもやめてね。」
🦁「え！？なんで知ってるの！？」
参考文献
💻「もっと詳しく知りたい人は、この資料も読んでみてね。」
https://blog.final-techblog.com/atproto-repository-details.html