セグメント木, より一般に「区間積クエリを高速計算する方法」の圏によるモデル

TL;DR

セグメント木とは, ある半開区間の圏表現$\mathbb{I}$から何らかの圏$C$への関手$F$である. セグメント木の一点・多点更新クエリとは自然変換である.

セグメント木という呼称はあくまで関手の計算グラフのとり方によるものであって, Sparse Table等の(列を計算するための)手法も, 基本的には統一した観点で見ることができる.

はじめに

本記事は「高速計算可能な区間クエリとはどのようなものか」へと圏論的なモデルを与える. 特にセグメント木にフォーカスしているが, [2]における議論を前提とするならば, 本記事の内容はSparse Tableや累積和にも一般化可能であるはずである. ただしそれらに対しては未証明の部分が大きい.

もともとは先日公開した論文[4]における議論から発展したものであるが, @convexineq氏によって計算機科学的視点からのセグメント木・(Disjoint) Sparse Table・累積和等の再整理[2]がなされたことをきっかけに, 代数的モデルも改めて区間積・区間乗算等の(より一般の)形で議論すべきではないかと考え, そのような方針で再整理した. なお, 区間乗算クエリは(記事が長くなってしまったため)別記事に書き起こす予定である.

[2]において議論されているのはあくまで計算アルゴリズムの観点からの議論である. 特に双対セグメント木の双対性を前処理・後処理の観点から説明していることは興味深いところである. なぜならば, 圏論的モデルを与える議論からも全く同じ結論に至っているためだ.

しかしながら, 本記事においてアルゴリズム的な観点は殆ど登場しない. セグメント木において重要なのは「区間積クエリを高速計算するための方法とは何であるか」であって, 「区間積クエリとして計算できるような代数構造とは何であるか」はまた別の問題である. [2]は前者に関するまとめとなっており, 本記事は後者を目指すものである.

準備

本記事では[1]における圏の定義を採用している. しかしこの定義はあまり一般的ではないように思われるため, 本節でこの定義を紹介する. なお, 関手や自然変換といった用語に関しては既知であるものとする (即ち, 本節を読んで初めて圏を知る場合, 本節の内容は意味をなさない).

Def (ファイバー積). 集合$X, Y, S$, 写像$f\colon X \to S$, $g\colon Y \to S$に対し, $$ X\times _ {f, S, g} Y := \lbrace\,(x, y)\mid (x, y)\in X\times Y.\ f(x) = g(y).\,\rbrace $$ と定義する. これを$X$と$Y$の($f$と$g$による)ファイバー積という.

明白な場合, $f$, $g$は省略することもある.

Def (射影). ファイバー積$X\times _ {f, S, g} Y$に対し$\mathrm{pr} _ 1\colon X\times _ {f, S, g} Y\ni (x, y) \mapsto x\in X$, $\mathrm{pr} _ 2\colon X\times _ {f, S, g} Y\ni (x, y) \mapsto y\in Y$をそれぞれ第一成分への射影, 第二成分への射影という.

ファイバー積は幾何学的な貼り合わせ, のりしろの概念を抽象化したものである. これを用いて圏を定義する.

Def (圏). 集合$C$, ${M}$に対し, $s\colon M \to C$, $t\colon M \to C$, $c\colon M\times _ {s, C, t} M \to {M}$, $e\colon C \to {M}$が定義されており, なおかつ次の7つが成立しているとき, またそのときに限り, $(C, M, s, t, c, e)$を圏という. ただし, 集合$S$に対し$1 _ S\colon S\to S$は$S$の恒等写像.

  1. $t\circ c = t\circ \mathrm{pr} _ 1$
  2. $s\circ c = c\circ \mathrm{pr} _ 2$
  3. $c\circ (1 _ M\times c) = c\circ(c\times 1 _ M)$
  4. $s\circ e = 1 _ C$
  5. $t\circ e = 1 _ C$
  6. $c\circ(e\circ t, 1 _ M) = 1 _ {M}$
  7. $c\circ (1_M, e\circ s) = 1 _ {M}$

この定義は[1, p.3, 定義1.2.1]における可換図式(1.3), (1.4)を等式に開いたものである. はてなブログに記事を書く都合上, 可換図式ではなく等式による表現のほうが楽であったため, このような形をとった.

圏$(C, M, s, t, c, e)$はしばしば省略して$C$と書かれる. 多くの場合, 対象の集合(の記号表記)からその圏は文脈上一意に定まるためである. 勿論, 同じ対象に対して異なる圏を考える場合にはこの限りではない.

半開区間からなる圏

本記事において, $\mathbb{I} _ {i\to j}$を半開区間$\lbrack i, j)$による圏として定義する. 本節はその定義を与えるものである.

Def. $i, j\in\mathbb{N}$とする. $i\leq j$のとき, $\lbrack i, j) := \lbrace\,x\mid x\in\mathbb{N}.\ i\leq x\lt j.\,\rbrace$を($i$から$j$への)半開区間という.

$\lbrack i, i) = \emptyset$を許すことに注意. このため$\lbrack 0, 0) = \lbrack 1, 1) = \cdots = \lbrack N, N) = \cdots$のように複数の表現を持ちうる. ただし, 便宜上のラベルとして$(1, \lbrack 1, 1))$のような直積を考えることでこれは弁別可能である.

Prop. 1. 半開区間$\lbrack i, j)$について以下のように定義する.

  • $C := \lbrack i, j)$.
  • $M := \lbrace\,\lbrack a, b)\mid a, b\in\mathbb{N}.\ i\leq a\leq b\leq j.\,\rbrace$
  • $s\colon M \ni \lbrack a, b) \mapsto a\in C$
  • $t\colon M \ni \lbrack a, b) \mapsto b\in C$
  • $c\colon M\times _ {s, C, t} M\ni (\lbrack b, c), \lbrack a, b)) \mapsto \lbrack a, c)\in {M}$
  • $e\colon C\ni a\mapsto \lbrack a, a)\in {M}$

このとき, $\mathbb{I} _ {i\to j} := (C, M, s, t, c, e)$は圏.

Proof. 定義を直接確かめればよい. 以下に登場する半開区間はいずれも$C$の元であるものとする.

  1. $(t\circ c)(\lbrack b, c), \lbrack a, b)) = t(\lbrack a, c)) = c = t(\lbrack b, c)) = (t\circ \mathrm{pr} _ 1)(\lbrack b, c), \lbrack a, b))$
  2. $(s\circ c)(\lbrack b, c), \lbrack a, b)) = s(\lbrack a, c)) = a = s(\lbrack a, b))= (c\circ \mathrm{pr} _ 2)(\lbrack b, c), \lbrack a, b))$
  3. $$ \begin{aligned} (c\circ (1 _ M\times c)))(\lbrack c, d), \lbrack b, c), \lbrack a, b)) &= c(\lbrack c, d), \lbrack a, c))\cr &= \lbrack a, d)\cr &= c(\lbrack b, d), \lbrack a, b))\cr &= (c\circ(c\times 1 _ M))(\lbrack c, d), \lbrack b, c), \lbrack a, b)) \end{aligned} $$
  4. $(s\circ e)(a) = s(\lbrack a, a)) = a = 1 _ C(a)$
  5. $(t\circ e)(a) = t(\lbrack a, a)) = a = 1 _ C(a)$
  6. $(c\circ(e\circ t, 1 _ M))(\lbrack a, b)) = c(\lbrack b, b), \lbrack a, b)) = \lbrack a, b) = 1 _ M(\lbrack a, b))$
  7. $(c\circ (1_M, e\circ s))(\lbrack a, b)) = c(\lbrack a, b), \lbrack a, a)) = \lbrack a, b) = 1 _ M(\lbrack a, b))$

よって成立. $\Box$

セグメント木

Def. 区間$\lbrack 0, N)$と圏$C$について, 関手$F\colon\mathbb{I} _ {0\to N}\to C$をセグメント木という.

上の定義は非直感的であろうと思われるため, 次の命題でこのことを詳しく説明する. なお, 本命題の証明は完全に形式化されているわけではない (厳密には未証明である).

Prop. 2. セグメント木$F\colon\mathbb{I} _ {0\to N}\to C$をとる. $C$における射の合成が$O(1)$で計算でき, また射を空間計算量$O(1)$で保持・表現できるとき, 次が成立.

  1. $\lbrack i, j) \subseteq \lbrack 0, N)$に対し, $F(\lbrack i, j))$は空間計算量$\Omega(N)$で計算できる1.
  2. $\lbrack i, j) \subseteq \lbrack 0, N)$に対し, $F(\lbrack i, j))$は時間計算量$O(\log N)$で計算できる.

Proof.

  1. 任意の$a\in\lbrack 0, N + 1)$に対し, $F(\lbrack a, a))$は$F(a)$の単位射へと移るため, $F(\lbrack i, j)) = F(\lbrack j-1, j))\circ F(\lbrack j-2, j-1))\circ\cdots\circ F(\lbrack i, i + 1))$より, $F$の計算には長さ1の区間全てに対応する値を持っていればよい. したがって, $a _ i := F(\lbrack i, i + 1))$とするとき, $a _ 0, a _ 1, \ldots, a _ {N - 1}$が計算のために最低限必要な元である.
  2. 計算したいものは(1.)と同様に長さ1の半開区間の像の合成である. 射の全体はモノイドをなすことから, これはモノイドの区間積演算の議論をそのまま適用できる. よって, [2]における計算グラフの前計算を実施することによって達成できる. $\Box$

Prop. 2 (2.)はそのままセグメント木に載せることを言っている. この点は[2]において議論されているものそのままであり, 特に難しい話ではない. 重要なのは, Prop. 2 (1.)にある通り, 区間の圏からの関手は列を中に持ち, またその計算結果全体を同時に持つことである. このことをもって, 我々が「区間積クエリ」と呼んでいるものは関手の計算に等しいと言えるのである.

この定義に沿えば, 「セグメント木に乗る代数構造」とは圏$C$のことである. 「セグメント木に乗る構造は圏である」という主張[3]はこのように表現される.

一点更新クエリについて

ここまで関手の計算に触れてきたわけだが, 関手の計算だけではあくまでオフラインの(更新の無い)アルゴリズムとしてしか扱えない. そこで, 一点 / 多点更新クエリがどのように形式化されるのかに関して本節で検討する.

まず素朴な観察として, モノイド${M}$を載せたセグメント木においては自由に更新できる.

次に, 実数値行列の全体からなる圏$C$を考えよう. 対象は$\mathbb{N}\setminus\lbrace\,0\,\rbrace$, 射$i \to j$は$i\times j$行列である. このとき$\mathbb{I} _ {0\to 4}\to C$なるセグメント木において次のような設定であるものを考えられる:

  • $F(0) = 1$, $F(1) = 2$, $F(2) = 3$, $F(3) = 4$, $F(4) = 5$
  • $F(\lbrack i, j))$: $i\times j$行列
  • $F(\lbrack j, k))\circ F(\lbrack i, j))$: $i\times j$行列と$j\times k$行列の積

言い換えれば, この関手$F$は[1x2行列, 2x3行列, 3x4行列, 4x5行列]を管理しているわけである. そしてこの場合, 更新できない場面を考えなければならない. 具体的には「0番目を2x3行列にする」という操作はこのセグメント木に対しては無効である (2x3行列と2x3行列の積は計算不可能). この要件はその上に載っている代数構造の制約から来ているものであり, それゆえ「セグメント木の一点更新は代数的な意味をもたなければならない」という仮説をたてられるのである.

さて, セグメント木$F\colon\mathbb{I} _ {0\to N} \to C$, $G\colon\mathbb{I} _ {0\to N} \to C$を取り, この間に次の条件が課されている場合を考えよう: $F\colon\mathbb{I} _ {0\to N} \to C$, $G\colon\mathbb{I} _ {0\to N} \to C$をセグメント木とする. ある$i$が存在して$F(\lbrack i, i+1)) \ne G(\lbrack i, i+1))$であり, なおかつ$j\ne i$なる任意の$j\in \lbrack 0, N)$に対して$F(\lbrack j, j+1)) = G(\lbrack j, j+1))$である.

よりinformalに言えば, この条件は「一点だけ違う列」という条件である. このように翻訳することで, 一点更新クエリの可能性とは「この関手の間に自然変換を構成できるだろうか?」という問題と本質的に同じであることがわかる (一般の場合は多点更新クエリとして取り扱う).

実際, モノイドに対しては一般に自然変換を構成できる. このことを以下に示す.

Thm. 3. セグメント木$F\colon\mathbb{I} _ {0\to N} \to C$, $G\colon\mathbb{I} _ {0\to N} \to C$に対し, $\delta\colon F(N)\to G(0)$が存在するものとする. このとき, 自然変換$\theta\colon F\Rightarrow G$がある. 換言すれば, 多点更新クエリの十分条件は$\delta$の存在である.

Proof. $\theta _ k := G(\lbrack 0, k))\circ \delta\circ F(\lbrack k, N))$とおく. $G(\lbrack 0, 1))\colon G(0)\to G(1)$, $F(\lbrack N - 1, N))\colon F(N-1)\to F(N)$であるから, $G(\lbrack 0, k))\circ \delta\circ F(\lbrack k, N))$は$F(k)\to F(N)\to G(0)\to G(k)$なる射の合成として意味をもつ. このとき任意の$\lbrack i, j)\in\mathbb{I} _ {0, N}$について $$ \begin{aligned} \theta _ j\circ F(\lbrack i, j)) &= G(\lbrack 0, j))\circ \delta\circ F(\lbrack j, N))\circ F(\lbrack i, j))\cr &= G(\lbrack 0, j))\circ \delta\circ F(\lbrack i, N))\cr \end{aligned} $$ $$ \begin{aligned} G(\lbrack i, j))\circ \theta _ i &= G(\lbrack i, j))\circ G(\lbrack 0, i))\circ \delta\circ F(\lbrack i, N))\cr &= G(\lbrack 0, j))\circ \delta\circ F(\lbrack i, N))\cr \end{aligned} $$ である. それぞれ一致するため成立. $\Box$

Cor. 4. セグメント木$F\colon\mathbb{I} _ {0\to N} \to C$, $G\colon\mathbb{I} _ {0\to N} \to C$に対し, $C$がモノイドであるならば, 多点更新クエリを実行できる.

Proof. モノイドにおいて対象は唯一つであるため, $F(N) = G(0)$である. ゆえに$\delta$として恒等射をとればThm. 3より成立. $\Box$

先に見たような行列積演算もCor. 4同様に取り扱える. なぜならば, $F(N)\times G(0)$行列として適当な行列をとればこれを満たすからである.

セグメント木の合成

[4]において触れていた話題の一つに, セグメント木の合成を考えていたものがあった. これは次の定理で存在を保証される.

Thm. 5. セグメント木$F\colon\mathbb{I} _ {0\to N}\to C$, $G\colon\mathbb{I} _ {0\to N}\to D$をとる. このとき$F\times G\colon \mathbb{I} _ {0\to N}\to C\times D$はセグメント木.

Proof. 自明. $\Box$

おわりに

双対セグメント木ぐらいは書きたかったのだが, セグメント木だけでも分量過多になってしまっている. 現時点で双対セグメント木は以下の通り定義されており, 次の記事ではこれをもとに双対セグメント木・遅延伝播セグメント木の上に乗る構造について, その圏論的モデルを与える予定である.

Def. 区間$\lbrack 0, N)$と圏$C$, $D$について, 関手$F\colon D\to \mathrm{Fun}(\mathbb{I} _ {0\to N}, \operatorname{End}(C))$を双対セグメント木という.

双対セグメント木はセグメント木の一種であるが, 自己関手を得るための前段階が挟まっているのが特徴である. また, 最終的に得られるものはあくまで自己関手である. そうやって得られた自己関手を適用する操作は利用する側の都合であり, あくまで双対セグメント木が行っている操作は「一点取得」ではなく「関手を得る操作」であると解釈すべきであろう.

遅延伝播セグメント木はセグメント木と双対セグメント木を組み合わせたものである. 即ち, 「区間から圏への関手」「区間に応じて自己関手への関手を与える関手」の二つが遅延伝播セグメント木を構成している.

[4]で触れたような合成の議論は関手圏における圏論的直和を効率的に計算できるかどうかに関わっている. しかしながら, 未だ議論し尽くせていないように思えているのも事実であり, 目下この点が最大の研究課題と見ている.

本記事は「セグメント木に対する更新クエリは自然変換である」と主張しているわけだが, その自然変換を与えるための必要十分条件に関しては未だ議論し尽くせていない. 随伴関手を与えるとどうなるかについて現状考えている状態であるが, 上手なまとまり方はしていないため, future workとしてこの点も検討しておきたい. 自然変換の計算量を込みに考えた場合も同様である.

References

  1. 斎藤毅. 2020. 数学原論. 東京大学出版会.
  2. @convexineq. 2021. 半群区間積クエリについて. https://qiita.com/convexineq/items/4b6920af3e3d37a96540
  3. @kimiyuki_u. 2018. セグメント木の上に乗る構造はモノイドではなく圏である. - https://kmyk.github.io/blog/blog/2018/12/06/categories-on-segment-tree/
  4. @kimiyuki_u and @elliptic_shiho. 2021. セグメント木と代数構造の理論. https://elliptic-shiho.github.io/segtree/segtree.pdf

  1. 動的セグメント木のような形で, 必要に応じて区間を作ることにするのであればこの限りではない. しかしそれはオンラインアルゴリズムである前提を置いているために成立する工夫であって, 今回の前提からは外れる.

「セグメント木と代数構造の理論」の補遺

先日, 表題に挙げた名前で文書(というよりは論文)を公開した: https://elliptic-shiho.github.io/segtree/segtree.pdf

この論文は@kimiyuki_uと私が書いたものである. 書いていたのは2019年のはじめから2021年にかけてであり, しかしその後約三年の間塩漬けとなってしまっていた. 公開にあたっての心持ちについてはPDF先頭に書いているので省略することとし, 本記事はその後読み直していて色々と思い出してきたことを書き綴っておきたい.

なお, 2024年現在における新規性の有無については未検証である. もしも研究が出ているのであれば教えてほしい.

我々の目指したかったところについて

そもそもこの論文を書く理由は(競プロ的な意味では)殆ど存在しない. 仮にこれを読んだところで新しく解けるようになる問題があるわけではないし, 確実な新規性と言えるものもない. しかしながら, 私も彼も数学の目線で競プロに関する話をしたい, なおかつ面倒な計算の嫌いな人間であった. それが執筆を始めた一つの理由である.

たとえば当時の記録によれば, 我々の間では木構造とは次のように定義されている:

$V$を集合としたとき, $\top\in V$, $P\colon V\setminus\left\lbrace\,\top\,\right\rbrace\to V$について以下が成立するならば$(V, P, \top)$を根付き木と呼ぶ.

$$ \forall v\in V\setminus\left\lbrace\,\top\,\right\rbrace.\ \exists! k\in\mathbb{N}.\ \mathrm{s.t.}\ P ^ k(v) = \top. $$

根付き木$T = (V, P, \top)$について, $v\in V$を$T$の頂点と呼び, $v\in V$を$v\in T$で略記する. また, $\top$を$T$の根と呼び, $\mathrm{root} _ T$で表す. $T$が明らかな場合には$\mathrm{root}$とすることもある. 各$v\in T$について$P ^ k(v) = \mathrm{root}$なる$k\in\mathbb{N}$は唯一つ定まることから, これを$\operatorname{depth}(v) := k$とおいて$v$の深さと呼ぶ.

$P$の逆像$P^{-1}$について, $P ^ {-1}(v)$の元を$v$のと呼ぶ. また, $\operatorname{{Le}{af}}(T) := \left\lbrace\,v\mid v\in V, P ^ {-1}(v) = \emptyset\,\right\rbrace$の元を$T$のと呼ぶ. 以降, $C(v)$で$P ^ {-1}(v)$を表すものとする. $v\in V$, $k\in\mathbb{N}$について$P ^ k(v)$を$P$の祖先と呼ぶ. 明らかに$\mathrm{root}$は任意の頂点について祖先である. このことから, $v, u\in V\setminus\left\lbrace\,\mathrm{root}\,\right\rbrace$について$P ^ a(v) = P ^ b(u)$なる$a, b\in\mathbb{N}$が必ず存在し, $v$が$u$の祖先でない場合(あるいは$u$が$v$の祖先でない場合)には$P ^ {a-1}(v)\ne P ^ {b-1}(u)$が成立. この$P ^ a(v)$あるいは$P ^ b(u)$は$v, u$の最近共通祖先と呼ばれる.

このように, (病的なまでに)形式化された状態で数学の世界に競プロに頻出の概念を埋め込んでしまえば, 面倒な具体計算を減らせるし, それにある程度は自動化した議論ができるようになる. そのためには「お気持ち解説」では不足なのである1. 彼はkmyk/Jikkaにおいてその夢を(競プロ問の自動回答という形で)いくらか実現していたし, 私はデータ構造という曖昧な対象をより深く理解できるようになった.

しかしながら, セグメント木の定義そのものを研究するのはとても難易度が高かった(次節参照). そのため「セグメント木の上には代数的な構造がいろいろと"乗る"らしい」というところから「セグメント木の上に乗る代数的構造とはどのようなものか」について興味を向けたのは自然な成り行きだと言えよう. 私は, 彼が既存研究として持っていた「複数のクエリの合成を一般的にやるための十分条件」について, それを遅延伝播構造・遅延伝播積といった道具を追加定義して純数学的な立場から示した. その結果を整理・体系化したものがこの論文である.

圏への拡張の際には加群圏やモノイダル圏, 加群によって豊穣化された圏などを用いて表現できるだろうかという夢想をしていたが, 今の所それらは検討段階のままである.

セグメント木そのものについて

構造だけ見ればセグメント木はただの二分探索木である. 実際には区間クエリとの束として扱うことでセグメント木はセグメント木として扱われている. ところで, たとえば動的セグメント木の木構造は完全二分探索木としては扱われず, 単なる二分木として扱われる. セグメント木は完全二分木に限定されたデータ構造ではない にあるように, 学術的・歴史的にも平衡二分木として扱われるケースはあるようだ. いずれにせよ, 完全二分探索木の場合にのみ適用可能なテクニックはこれらにおいて通用しない.

ここまで二分木が用いられてきたわけだが, その理由が最終的に「二分探索するのがoptimal caseになるから」になることは想像に難くない. この点は事実そうなのだが, 実際には一般の木構造であっても, 適切に区間を割り振れば同様の構造を実現できる. このことから, 「セグメント木とはたんに木構造の各頂点に区間を割り当てる写像としては理解できないだろうか?」ということを考えていた.

実際, 彼は 完全二分木への添字付けであってセグメント木ではないものを考える において「添字の割り当て方」としてこの区間割当の考え方に触れている. 半年ほどの間「セグメント木とはどのような区間割当のことか, 或いは区間割当写像はいつセグメント木になるのか」について考え続けはしたのだが, 結局この点については考えがまとまらないままストールしてしまった.

セグメント木のなす空間について

管理したい列の長さを$n$としたとき, 半群$S$の乗っているセグメント木の区間操作は$S ^ n \to S ^ n$という写像だと思える. 列から列への状態遷移全てを収めてしまえば, 実際にはそのセグメント木によって表現可能な世界は一つの圏をなすのではないか. というような仮説を立てて考えていたことがある. その場合クエリは関手として取り扱われる (ことになるだろう. 完全には未証明, 検証段階のネタ).

上述定義は「セグメント木は何らかの圏として表される」という見方である. でも実際にはそれよりも面白そうな世界がある. それは「遅延伝播構造を対象, 遅延伝播構造の間の準同型を射とした圏」である. これは「遅延伝播セグメント木を対象, 遅延伝播セグメント木の間の(代数構造に関する)準同型を射とした圏」と言い換えてもよい.

本論文において示している「一定の十分条件を満たせば, セグメント木同士で直積・直和に相当する演算が可能である」という主張は, 上の圏における直和・直積の議論に言い換えられることが予想される(完全には未証明). これは「セグメント木全体からなる世界は何かしらの構造を持っていそうだ」という示唆だと思えないだろうか. セグメント木からセグメント木への射の形次第では「セグメント木同士の射が一体どのような形をしているのか」という表現論的な研究もできるだろう2.

加えて, "セグメント木全体がなす圏"が仮に$\mathbf{Sets}$や$\mathbf{Ab}$の部分圏に収まるような範囲だとすれば, そこには自然にトポス的な距離感を入れることも可能であろう. 実際のところ, 2024年現在の私が気にかかっているのはこの点, あるいはもっと引いた「セグメント木のモジュライ空間とはいかなる形をしているか」という代数幾何学的な視点である. ここまで来ると計算可能性などどうでもよくなってしまうので, その点でも彼の(あくまで計算する立場からの)助言は嬉しかったなと反復している次第だ.

最後に

セグメント木に注目して, 思い出せた範囲でこの論文に関するトピックをいくつか並べてみた. 他にもより一般の議論ができそうな箇所はあるし, 山のように存在するメモ用紙やノートを掘り返せばネタはあると思うのだが, 今思い出せないのであればそれほど考えてもいなかったことなのだろうと一旦区切ることにする. 公開できずにストールするよりも, 公開できたほうがよい.

彼の関東における住居は私の家から数駅の場所だった. その選定理由が私とこの論文に関する議論をしやすくするためだと本人に聞いた際には驚いたものだ3が, 実際そのぐらい熱を入れて書かれた作品でもある. 今となっては拙い証明も含まれているが, Twitterにおける発言の通りどうか読んでやってくれという気持ちだ.


  1. 実際のところ, 私がセグメント木について実務的要請から調べている際に「競プロにおける解説はどれもお気持ち解説しかない! まともな解説かと思ったらコード書いてるだけ! こんなんで一体人々はどうやってセグメント木という対象を理解・勉強してるんだ?」とキレて彼に質問した際に「それはまともな定義がそもそも存在しないからですよ」と返ってきたのが本研究の端緒である. なお, 目的が違うがためにこのような感想になっているだけで, お気持ち解説自体を批判する意図はない.
  2. 計算量とセットで考えなければならない計算機科学の文脈においては, 線形演算が如く 「小さい演算」の形式的定義 をwell-definedに定義してやらなければならない可能性は実際に高い.
  3. 普段からの交流もしやすくなったのはとてもよかった. たとえば mod で計算するときに零の重複度も持つテク は私が暇だからと彼を呼びつけたコメダでの議論が元になっている. リモート勤務全盛の今言うのも何だが, オフラインでの自由度の高さは生産性に無視できない影響を与えることを実感した.

TPMとの戯れ long version

はじめに

この記事はセキュリティ・キャンプ全国大会 2023のLT大会で発表した以下のスライドを解説するものです. このときは5分程度しかなかったのでまともに解説できなかった. なんか色々書いていたら9000文字を越えてしまったので, 暇なときにつまみ読んでもらえればと思います.

https://elliptic-shiho.github.io/slide/Playing_with_TPM.pdf

この記事は少し砕けた形で書いてみようかと思いますが, 普段硬い文章ばかり書いているので読みづらいかもしれません. その点ご容赦ください. あとやたら長い.

前提としては「認証と認可の違い」「応用情報処理程度のPKIの知識」あたりがあるとわかりやすいと思います.

TPMとは

皆さんTPM使ってますか? Windows 11へのアップグレード時にお世話になるあれです1. TPMという単語はTrusted Platform Moduleのアクロニムで, Windows11で要求される「2.0」は2023年現在の最新バージョンです. 実はTPM 2.0はちゃんとISO規格にもなっています2. 策定はTrusted Computing Group (TCG) が行っており, 著名なチップメーカーやOSメーカーが名を連ねています.

2.0の一個前のバージョンは1.2です. こちらもISO規格となっており3, BitLocker等で既に利用されています.

BitLockerという単語が登場したことで, TPMが暗号に関係することを皆さんは想像したことでしょう. 大正解です. TPMは暗号処理に関するコプロセッサとして登場したものです. 特に「安全な乱数生成」「TPMチップ固有の情報を用いた所有者認証」あたりが目玉でしょうか. TPM2.0は更に複雑になっているのですが, そのあたりの詳細はそのうちまた別に記事を書くこととします.

TPMは暗号処理全般を担当できますから, 「TPMを用いることによって, 暗号に関する処理をCPU上で行う必要がなくなる」というメリットもあります. 耐タンパ性より「安全に鍵を保存できる」という性質もあるといたれりつくせりですね. 当然TPM内から秘密鍵を持ち出せないようにするオプションもあり, これを用いることで「当該TPMをもっていない場合秘密鍵の復元はできない」というような状況を容易に作り出せます.

ハードウェア編

そんなTPM, ぜひともお話してみたいと思いませんか? ここでは思うことにしておいてください. この手の部品は秋月や千石ではまず手に入りませんので, 初手でDigi-keyを見に行きます.

調べると結構出てくるもので, アクティブな製品に限ってもInfineon, Microchip, STMicroelectronicsと著名なメーカーの製品が100件ほどヒットします.

今回は手元にだぶついていたMicrochip MCP2221A (USB - I2C / UART / GPIOコンボという便利なチップ)を使いたかったため, 通信手段はI2Cに限定します. そしてMicrochip / Atmelの製品は細かいデータシートが公開されていないため4に一旦除外. 当然バージョンは2.0固定. 絞っていくと案外製品は少なくなるもので, 最終的にはInfineon社のSLB96735というチップに収まりました. 購入当時は1チップ828円でした.

次は回路設計です. 今回はハードウェアの話をしたいわけではないので, 詳細は省きます. 実は私はプログラミングに触れるより前から回路設計をしています.

シンプルにつないだだけで, それ以外はSLB9673のデータシートにある推奨回路とUSB回りの設計からESD対策を抜いたぐらいです. 良い子の皆さんはちゃんと入れましょう. 一点もののつもりだったので, 完成品は以下のとおりユニバーサル基板製です.

0.5mmピッチのQFNはそこまではんだ付けしにくくなく, どれかといえばmicroUSB端子へのはんだ付けの難易度のほうが高かった. あれはすぐ外れてしまう...

ソフトウェア編 - MCP2221A

今回はMCP2221AのUSB-HIDデバイスドライバをRustで自作しています. その要約をさらっと書き記します.

当初MCP2221AのドライバがLinux kernelに取り込まれていると聞き喜んでそちらを使っていたのですが, 実はこの実装はいくらかバグっています. 具体的にはI2C通信がたまにストールします. そもそもLinux専用ですので, MacWindowsでは動きません. それではUSBドングルとしての汎用性に欠けてしまいます. ということで既存実装を探しました. そのうちgoogle/mcp2221-rsZakKemble/libmcp2221をここで取り上げます.

まず前者はRustとlibusbによる実装で, 最初から開発に利用していたものです. しかしlibusbは新し目のMacと相性が悪く6, カフェなんかに出ておしゃれに7TPMプロトコル・スタック開発をやろうとしていた私の用途には合いませんでした.

後者はC言語による実装ですので, Rustで使う場合FFIを書かないといけません. 今回Unsafe Rustは可能な限り扱いたくなかったので, この選択肢も結局除外されます.

最終的に, これなら作ったほうがいいやとエイヤで書きました. USB-HIDレイヤまではhidapi任せなのでそこまで難しくありません. 普通のデバドラ開発と同じですね.

ソフトウェア編 - TCTI

TPMの仕様書は4分冊となっていますが, 実はこれは不完全です. というのも, この仕様書では「TPMに対するコマンド体系とその基本思想」は完璧に定義されているのですが, 「具体的にどう送るのか」に関しては一切定義がないのです.

当然これは意図的なもので, TCGはその下位レイヤーをTPM Command Transmission Interface (TCTI) と称し, 様々なインターフェイスごとに別個に規格書を出しています. I2C, SPI, LPC, TCPといったインターフェイスそれぞれについてです.

特にPC関連のTCTIに関する記述は TCG PC Client Platform TPM Profile Specification for TPM 2.0 - https://trustedcomputinggroup.org/resource/tcg-tpm-i2c-interface-specification/物理層からの全てが記載されています. プルアップ抵抗値やデバイスアドレス, チップ形状ごとのピンアサインまで細かく規定されており, これを読んでいればメーカーのデータシートは不要なのではと思わせるほどです.

また, TCG PC Client Device Driver Design Principles for TPM 2.0 - https://trustedcomputinggroup.org/resource/tcg-pc-client-device-driver-design-principles-for-tpm-2-0/ という素晴らしいドキュメントのおかげで, 我々はTCTIレイヤに関して詰まることなく実装を進められます. 実はTPM 2.0の参考書というものはほぼ見当たらないのですが, その一因はこの親切な定義にあるのではとちょっとばかり思っています.

tpmGoフラグを1にし忘れていたがために動作しない, MCP2221A側のデバドラがバグっていたなどの困難はありましたが, ここまでを実装してようやくTPMとお話できるようになります.

ソフトウェア編 - TPM API

TPM自体の仕様書はTrusted Platform Module Libraryという名前で総称されており, それは以下の4冊からなります. この4冊は合計でも2000ページほどしかなく, Intel SDMやTegraの仕様書を読み慣れた低レイヤーの民としては短くて感謝の念が起きるほどです.

  1. Part 1: Architecture (TPM 2.0のアーキテクチャ・理念)
  2. Part 2: Structures (TPM 2.0に関する構造・型)
  3. Part 3: Commands (TPM 2.0に搭載されているコマンド)
  4. Part 4: Supporting Routines (TPM 2.0の仕様の利用に関する情報8)

しかしそれでも問題は起きます. たとえばTPMTPM2_Startup というコマンドを実行することでスタートアップ処理を実行するのですが, 「このコマンドを実行するために何をどうエンコードして送ればいいのか」に関する直接的な情報はどこにもありません. 要するに, 「この4分冊をどう読めばいいのか」という段階で詰まってしまうのです.

理解した今であれば「Part 1でコマンド実行体系を掴み, Part 3でコマンドごとのパラメータリストをチェックした上で, Part 2に書かれている構造体に格納・エンコードする」と言えるのですが, 読み始めた当時はそんなことはわかりません.

色々と探した結果, 入門書として公開されている A Practical Guide to TPM 2.0: Using the Trusted Platform Module in the New Age of Security という書籍の第五章 "Navigating the Specification" に行き着きました. この章はTCP経由で利用できるTPMのシミュレータを利用し, 実際に仕様書のどこを読めばいいのかに関する読み方を提供するもので, これをもとに試しにいくつか手で作ったコマンドを送って確かめることで読み方を学びました.

とりあえず TPM2_Startup を実行できたら, 次は TPM2_SelfTest を実行できるように. 今度は TPM2_GetRandom で乱数を...といった形で実装し, 後は必要な構造体を必要なときに作るだけでよいところまで来ました.

実装に悩んだ箇所として, TPM2にはinterface typeという特殊な型があります. これは「TPMチップに依存して実装有無が変わるもの」という認識でよいです. Rustで書いている都合上, 動的にenumを変化させるのは難しいですし, かといって定数化してしまうのはちょっとどうかなというところ. 結局subenum crateを使って「実装されているかどうかはユーザーの責任として確認」「基本interface typeは部分型として実現」という形に収めました.

また, interface typeの最大の活用例である「暗号アルゴリズムの実装状況によって変化する型」には一番悩まされました. TPM2の仕様書には !ALG.ax のような謎の表記があります. これは「任意の非対称かつ署名に利用できるアルゴリズム」と読みます. そして !ALG.AX になると「任意の非対称かつ署名に利用できるアルゴリズムで, 特にそれ以外の用途に使えないもの」と読みます. TPMの世界においては暗号アルゴリズムにはa(非対称)やx(署名)といった属性が付与されており, これらを選択するためのものです. 以下に Trusted Platform Module Library Part 2: Structures p.93 §9.33 TPMI_ALG_SIG_SCHEMEより例を引用します:

これをsubenumで実装することに私は負けてしまい, だいぶ煩雑な形で実装することになってしまいました. いまでもこれをどう書くときれいに収まるのかに関しては悩み続けています. どなたかいい案あったら教えてください: https://github.com/ssh-slb9673-playground/tpm-ssh-agent/blob/b5e5aef420cfede64592fe19668830669a72254c/tpm_i2c/tpm/structure/algorithm/identifiers.rs

ソフトウェア編 - SSH Agent

せっかく単体で動くTPMボードがあるのですから, なにか実用的な目的を設定したいです. ということでSSH Agent9を作りました. といっても中身は殆ど既存crate( wiktor-k/ssh-agent-lib )を利用したもので, 私が書いたのはTPMとの通信処理と鍵生成ぐらいです.

なお, 私の書いたコードは TPM2_CreatePrimary を利用したもので, 特に TPM2_EvictControl による永続化をしているわけではないため, 再接続時に鍵は失われます. それでもちゃんと接続はできました. 「特定のハードウェアをもっていなければ接続できないSSHサーバー」の完成です.

ただし, プライマリキーの生成方法の都合上, 実はここにはセキュリティ的な課題があります. この点はTPMアーキテクチャに深く関わるものですので, 皆さんも是非この「CreatePrimaryが作る鍵は一体なんなのか」から仕様書と仲良くなってみてはいかがでしょう?

おわりに

今回書いたコードは https://github.com/ssh-slb9673-playground/tpm-ssh-agent にあります. 開発期間は概ね2週間程度, キャンプ終了時点の行数は4700行程度とそこそこの大きさになりました. いい勉強にはなったのではないでしょうか.

TPM 2.0はあまり国内のアマチュアが触れていない領域ということもあり, 今後何かしらこの分野の情報発信ができたらいいなあなどと考えています. USBは皆仕様書を読んでいるのに, TPM 2.0は誰も読んでいない. 不公平.

現時点ですぐに触れられる情報源のうち最も有名なのは Will Arthur, David Challener, and Kenneth Goldman. 2015. A Practical Guide to TPM 2.0: Using the Trusted Platform Module in the New Age of Security. Apress Berkeley, CA. だと思います. これは無料公開もされているため, 皆さんもすぐに読み始めることができます: https://link.springer.com/book/10.1007/978-1-4302-6584-9

また, Trusted Computing全体を通観するために私が読んだ本として Graeme Proudler, Liqun Chen, and Chris Dalton. 2014. Trusted Computing Platforms: TPM2.0 in Context. Springer. を挙げておきます. というかこの2冊以外にすぐに手に入る範囲のTPM 2.0の解説書はありませんでした. 本書は実務でTPM関連の開発をする人にも有用と思われますが, 些かアーキテクトに寄っている感もあります. TPM1.2とTPM2.0の差分に関する記述もありますので, 研究の際にもよい資料となるでしょう.

情報源が少ない理由はいくつかありますが, そのうち1つは間違いなく「十分に使いやすいプロトコルスタックの提供がなされている」という点にあるでしょう. たとえば https://github.com/tpm2-software/tpm2-tsshttps://github.com/microsoft/TSS.MSR です. 自作する必要性がない上, この中身に触れるような人は間違いなく仕様書を読めます. つまり解説の必要がない.

単純に「TPM 2.0はできることが多すぎる」という点も挙げられます. 今のTPM 2.0はPCRバンクを用いた起動時の整合性検証(所謂secure boot)の他, 「TPMに対して発行したコマンド列とその結果が間違いなくこちらの指示通りであることを確認しつつ, その実行されているTPMが本当に我々の指定したTPMであるか否かを識別する」とか, 「OSから特定の条件を与え, 起動ステートが一定の状態になっていなければ復号できない秘密鍵」みたいなものを作ることもできます.

上記事項に関してはPCR, ポリシー, remote attestation, audit sessionで調べてみると魔境が見えるのでおすすめです. 当然CPU - TPM間の通信を暗号化することもできますし, 生成した秘密鍵にはAuthValueなる個別のパスワード的なものを設定できます. TPM内のオブジェクトの認可制御だけで一冊書けるのではないでしょうか.

SSH agentにする際並行実行可能にする必要に気づき, そこからほぼ手を付けていなかったRustでの並行プログラミングをやるようなこともありましたね. tokio + reqwest程度なら触っていたけど, ちゃんと構造体にSync書いたのは初めてに思います.

最近実は少しアップデートを挟んでおり, Remote AttestationのProof-of-Conceptを実装してあります. 回路図のpdfも置いてあるので, もし必要であればご利用ください.

Future work

勢いで書いただけあってコードがかなり汚いです. もう少し真面目にクラス図描いた方が良かった気がします. ということで来年以降もう少し行儀の良いTPMプロトコル・スタックを作りたいと思っています.

TPM 2.0は認可制御が本当に複雑で, その上TPMにおけるセッションと認可の間の包含関係はベン図がないと理解できない状態です (A Practical Guide to TPM 2.0 p.168 Figure 13-1. Authorizations and sessions Venn diagram にその図があります). このあたりをきれいに見通せるよう組み直す試みだけで2ヶ月ほど経過してしまった.

私が今回調べた限り, アカデミア領域では研究対象になっているTPM 2.0も, アマチュアで楽しむには情報源が少ない状況です. 時間に余裕があれば, セキュリティモデルの概説や各種技術詳細を読む記事を書いていくのもありなのかなと夢想はしています. どこにそのような時間が?

おまけ

私は一点もののつもりだったのですが, このUSBドングルはどうせならもっとドングルらしくしたいなとは思っていました. チップも余っていますし...

そこで, 昨年のキャンプ受講生だったsaitenさん ( @sort_reverse )はそういえばプリント基板作ってたじゃんとお願いしてみたところ, USBドングル然としたTPM基板が出来上がりました. 大変感謝しています (いつも面倒だからPCB設計やらないのです...).


本記事は@leno3sさんに軽くレビューしてもらいました. ありがとうございます.


  1. 実は私はWindows10登場後ちょっとしてからWindowsを見限ってしまい, この経験はありません... 2023年末になってもオフラインの検証機はWindows7です.
  2. ISO/IEC 11889:2015
  3. ISO/IEC 11889:2009
  4. NDA必須. なお通信プロトコルやピンアサインはTPM仕様側で決まっており, 特殊なことをしない限りは利用可能.
  5. 当時はアクティブステータスだったのですが, 今見ると最終購入期限が設定されてしまっています. SLB9670の上位機種としてはあまり売れなかったのでしょうか... (I2CでTPMと通信する需要自体があまりなかった...?)
  6. https://github.com/libusb/libusb/issues/1014
  7. カフェに居るぐらいしか時間がなかったとも言う
  8. 実はPart 2, Part 3は機械可読であるように書かれており, 手実装する必要はありません. そのためのフォーマット情報や, 環境依存のパラメータリストの既定値等が収録されています.
  9. SSHの公開鍵認証を代行するデーモン. 便利.