$\newcommand{\argmax}{\mathop{\rm arg~max}\limits}$

Banded Hash Tree

2021年7月12日 #BHT #HashTree #MerkleTree

概要

現実的なストレージに対して追記効率が良く、累積的な構造変化の完全な履歴を保持するリスト構造 Banded Hash Tree (BHT) について説明します。この構造はデータの追加が可能なハッシュツリー (Merkle ツリー) であり、一般的なハッシュツリーと同様に小さなデータ片を用いてデータの破損や改ざんを検証することができます。

木構造の直列化レイアウトとしては、よく知られた B-Tree や van Emde Boas Tree、ルートノードが固定で葉が成長する Eytzinger (BFS) layout, ページ化二分木 (paged binary trees) などが存在しますが、このページの内容は該当するアルゴリズムに関する論文や書籍が見つけられなかったので今のところ個人的な研究です。要素の追加によりノードの積層が成長してゆく構造的特徴が Banded Ore (帯状鉱石) や Agate (瑠璃(るり)) を形成する過程と類似しているため、この構造を Banded Hash Tree (縞模様のハッシュツリー) と名付けています。

具体的な実装は https://github.com/torao/banded-hash-tree を参照してください。

概要
特徴
導入
BHT 構造
状態と操作
キャッシュ設計 [under construction]
並行処理
1. 楽観的ロックを使うアイディア
障害耐性
ハッシュグラフとしての拡張
ブロックチェーンへの応用

特徴

Append-only immutable list structure with hash tree. 時系列データのように追加のみが行われる不変リスト型構造に、ハッシュツリー (Merkle ツリー) または $O(\log_2 n)$ インデックスとして使用することのできる木構造を組み合わせている。通常のハッシュツリーと同様に、部分的に参照したデータの変更や破損、改ざんを検出するために使用することができます。
Multi-versioned data structure. 木構造はリスト内のデータを参照するためのインデックスとしても使用されます。この木構造は不変であり、過去の構造の完全な履歴が保存されます。このためデータの追加によってツリーが成長したとしても過去の任意の時点の木構造を再現することができます。
Assign efficiency to more recent data. 木構造の大部分は完全二分木であることから全般的には二分探索に近い特性を持つが、より新しいデータ方向へ探索する方がシーク回数が少なく、また到達までのステップ数も同じか少なくなります。木構造の探索コストは均等ではなく、BHT を直列化した形式では、あるノード $b_{i,x}$ とその右枝のノード $b_{i,y}$ は同一のエントリに書き込まれている。このためノードを右枝方向に走査する探索は I/O を伴うことなく実行することができる。
Serialized layout suitable for file systems. 直列化形式は追記のみで行い、書き込まれたデータは不変となることから、高速な単一ファイル DB として実装することができる。
Security. 認証パスのレベル (ルートノードからの距離) を信頼性と考えたとき、ハッシュ木としての信頼性は長期間存在する要素と新しく追加された要素とで非対称的です。ある要素の信頼性は、別の要素が追加されるたびに対数で増加し、全体が完全二分木となったときすべての要素が通常のハッシュ木と同等の信頼性を持ちます。これはブロックの追加によって過去のブロックの信頼性 (確定性) が増すブロックチェーンと似た特性です。
基本的な操作は append, read, range scan, full scan が可能です。delete はハッシュ値のみを残して論理削除を行うことができるが、そのハッシュ値の信憑を検証する手段は失われるかもしれない。

導入

BHT (banded hash tree; 帯状ハッシュツリー) は追記可能な構造を持つハッシュツリー (Merkle ツリー) である。ブロックチェーンのように単純増加する一つの数値 $i$ によって特定される不変データを連結する、検証可能 (改ざん不可能) なリスト構造に向いている (ハッシュツリーではなくストレージ上の大規模なリスト構造を $O(\log N)$ で検索する目的で使用することもできるが、その場合は二分探索のほうがよりシンプルである)。追加操作はファイルの追記のみで完結するため高速であり、SSD のような二次記憶装置に対するための直列化構造も単純である。

BHT は本質的に完全二分木ではないが、葉ノードの追加により BHT が内包する完全二分木の部分構造を成長させ連結することによって、木構造全体の大半のノードが完全二分木の特性を持っている。Fig 2 に示す図は BHT に 1 から 16 までのデータを追加するときの概念上の木構造の成長と、その直列化された形式を示している。

First slide — Fig 2. BHT に 1 から 16 までの要素を追加したときのツリー構造と直列化表現。

Second slide — Fig 2. BHT に 1 から 16 までの要素を追加したときのツリー構造と直列化表現。

Fig 1 が示すように、BHT の直列化表現は追加のみの操作であることからファイル操作に対して高速である。また、任意の時点の木構造を完全な履歴として保持していることから、過去を基準としたデータ要求でも正しいハッシュツリーで応答するすることができる。

BHT 構造

BHT はその多くの領域を完全二分木が占める二分木である。$n$ 個のユーザデータ (葉ノード) を含む BHT の木構造全体を $T_n$ と表す。あるノード $b$ が木構造 $T$ に含まれていることを示すために $b \in T$ という表記を使用する。$T_1$ が $T_2$ の部分木であることを示すために $T_1 \subseteq T_2$ と表記する。また、特にその成長過程を論ずるとき $n$-th 世代と表現する。

BHT は部分構造として含まれている一つもしくはそれ以上の完全二分木を統合しながら成長する。木構造の大半が完全二分木であることから、完全二分木に近い特性を持ち、また木構造全体から完全二分木を判定する方法が重要である。ここでは BHT 構造の現実的な操作に必要な数学的背景を記述する。

ノード

ユーザデータは BHT の葉ノードに格納される。ここで $i \in \{1,2,\ldots\}$ をユーザデータのインデックスとし、BHT に $i$ 番目に追加された葉ノードを $b_i$ またはより一般化した表記 $b_{i,0}$ と表す。

既存の木構造 $T_{i-1}$ に $i$ 番目の葉ノード $b_i$ を追加するときに発生する中間ノードを $b_{i,j}$ と表記する。ここで $j$ は $b_{i,j}$ をルートノードとする部分木を考えたときに最も遠い葉ノードまでの距離 (高さまたは深さ) を表している。したがって木構造全体で最も大きい $j$ を持つノードはそのルートノードである。また、任意の $b_{i,j}$ をルートノードとする部分木において $j$ が最も大きくなるケースはその部分木が完全二分木のときであることから、ルートノードの取る $j$ の最大値は $\lceil \log_2 i \rceil$ である。ここで $j=0$ を持つ単一の葉ノードも部分木とみなすことに注意。\[ \begin{equation} i \in \{1,2,\ldots\}: 0 \le j \le \lceil \log_2 i \rceil \label{ij} \end{equation} \]

$i$ の定義域を 64-bit 整数としても $j$ の取りうる最大値は高々 64 である。

Fig 1 で薄いグレーと黒塗りで示したように中間ノードには 2 つの種類がある。一つはその中間ノードをルートとする部分木が完全二分木のケースで、これは永続性 (permanent) を持ち $i$-th 世代以降のすべての木構造でも顕在する。もう一つは完全二分木でないケースで、これは他の完全二分木の部分木を接続するために設置された $i$-th 世代でのみ現れる一過性 (ephemeral) の中間ノードである。一過性の中間ノードは、説明を簡略化するためにFig 1 では消去しているが、直列化形式の中では常に存在しており、その木構造はいつでも復元することができる。

ある中間ノード $b_{i,j}$ が左枝に $b_{i_\ell,j_\ell}$、右枝に $b_{i_r,j_r}$ を接続していることを示すために $\underset{(i_\ell,j_\ell)(i_r,j_r)}{b_{i,j}}$ と表記する。

$i$-th 世代の木構造のルートノード $b_{i,j}$ は常に $j=\lceil \log_2 i \rceil$ の高さを持つ。

完全二分木の判定

あるノード $b_{i,j} \in T_n$ をルートとして配下のすべて葉ノードまでを含む部分木を $T_{i,j} \subseteq T_n$ とする。$i,j$ に対して式 ($\ref{pbt}$) が成り立つような整数 $\alpha$ が存在するならば、この部分木構造 $T_{i,j}$ は完全二分木 (perfect binary tree) である。\[ \begin{equation} i = \alpha \times 2^j \label{pbt} \end{equation} \] ここで $\alpha \ge 1$ は同一の高さ $j$ を持つ完全二分木 $T_{*,j} \subseteq T_n$ の中で先頭から何番目の部分木かを意味している。$T_{i,j}$ が完全二分木であることを意図しているとき $'$ (prime) を付けて $T'_{i,j}$ と表記し、同様に完全二分木となる部分木のルートノードを意図しているとき $b'_{i,j}$ と表記する。また式中では完全二分木となる部分木を ${\rm PBST}$ (perfect binary subtree) と表記する。

実装では式 ($\ref{pbt}$) から導かれる式 ($\ref{pbst}$) を使って添字のビット演算のみで $T_{i,j}$ が完全二分木かを判断することができる。\[ \begin{equation} \left\{ \begin{array}{lcll} i \bmod{2^j} & = & 0 & \ \ \mbox{If $T_{i,j}$ is a PBST} \\ i \bmod{2^j} & \ne & 0 & \ \ \mbox{Otherwise} \end{array} \right. \label{pbst} \end{equation} \] ここで整数 $x$, $y$ に対する $x \bmod 2^y$ はビット演算子を用いて x & ((1 << y) - 1) と表現することができる。また $j=0$ であれば式 ($\ref{pbst}$) は必ず true となることは明らかであるから任意の葉ノード $b_i = b_{i,0}$ は完全二分木と等価である。

独立した完全二分木の列挙

$n$ 個の葉ノードを含む ($n$-th 世代の) 木構造 $T_n$ が内包する、独立した (互いに部分構造ではない) 完全二分木を列挙する方法について考える。

このような完全二分木は左から順に、その位置から右に位置する葉ノードを使って構築できる最大の完全二分木となるように並んでいる (余った葉ノードは次の完全二分木の「材料」になる)。そして、$x$ 個の葉ノードを使って構築できる最大の完全二分木は高さ $j=\max\{j\in\mathbb{Z}\mid 2^j\le x\}$ で $2^j$ 個の葉ノードを持つことから、以下のようなアルゴリズムで求めることができる。ここで $\mathcal{B}'_n$ を $T_n$ に含まれる独立した完全二分木のルートノードの集合とする。

1.	$ {\bf function} \ {\rm iterate\_pbst\_roots}(n:{\it Int}) \to {\it Sequence}[{\it Node}] $
2.	$ \hspace{12pt}x := n $
3.	$ \hspace{12pt}\mathcal{B}'_n := \emptyset $
4.	$ \hspace{12pt}{\bf while} \ x \ne 0 $
5.	$ \hspace{24pt}j = \max \{j \in \mathbb{Z} \mid 2^j \le x\} $
6.	$ \hspace{24pt}\mathcal{B}'_n := \mathcal{B}'_n \mid\mid b'_{n-x+2^j,j} $	// $b'_{n-x+2^j,j}$ は完全二分木となる部分構造のルート
7.	$ \hspace{24pt}x := x - 2^j $
8.	$ \hspace{12pt}{\bf return} \ \mathcal{B}'_n $

Algorithm 1. $T_n$ が内包する独立した完全二分木のルートノードを求めるアルゴリズム。

ここで $\mid\mid$ を順序集合 (リスト構造) を連結する演算子とする。Algorithm 1 から得られる $m$ 個の完全二分木のルートノード集合を $\mathcal{B}'_n=(b'_{i_1,j_1},\ldots,b'_{i_m,j_m})$ とする。これらは配置上の左から順序付けられているため $i_1 \lt \ldots \lt i_m$ である。また左に位置する完全二分木がより高いという性質を持つことから $j_1 \gt \ldots \gt j_m$ である。

一過性ノードの列挙

BHT における一過性の中間ノードは、$T_n$ の部分木である独立した完全二分木のルートノードを右から接続したものである。したがって独立した完全二分木を列挙することで一過性の中間ノードも列挙することができる。

Algorithm 1 より得られる $m$ 個の完全二分木のルートノード集合 $\mathcal{B}'_n$ に対して、それらを接続する一過性の中間ノードは $\mathcal{B}_n=(b_{n,j_1+1},\ldots,b_{n,j_{m-1}+1})$ となる。ここで、左から $k$ 番目に位置する任意の一過性中間ノードは式 ($\ref{ephemeral_node}$) のように表される。\[ \begin{equation} \left\{ \begin{array}{ll} \underset{(i_k,j_k)(n,j_{k+1}+1)}{b_{n,j_k+1}} \ \ & (k \lt m - 1) \\ \underset{(i_k,j_k)(i_m,j_m)}{b_{n,j_k+1}} \ \ & (k = m - 1) \end{array} \right. \label{ephemeral_node} \end{equation} \] 式 ($\ref{ephemeral_node}$) で表される一過性中間ノードは、左枝に完全二分木の $b'_{i_k,j_k}$、右枝に一過性ノード $b_{n,j_{k+1}+1}$ または右端の完全二分木 $b'_{i_m,j_m}$ を接続し、$n$-th 世代で一過性の中間ノードであるため $i=n$、右枝に接続する二分木より左枝に接続する二分木の方が必ず高いため $j=j_k+1$ となることを意味している。Algorithm 2 は一過性の中間ノードを生成するアルゴリズムである。

1.	$ {\bf function} \ {\rm iterate\_ephemeral\_nodes}(n:{\it Int}) \to {\it Sequence}[{\it Node}] $
2.	$ \hspace{12pt}\mathcal{B}'_n := {\rm iterate\_pbst\_roots}(n) $	// Algorithm 1
3.	$ \hspace{12pt}\mathcal{B}_n := \emptyset $
4.	$ \hspace{12pt}{\bf for} \ x := {\rm size}(\mathcal{B}'_n)-1 \ {\bf to} \ 1 $
5.	$ \hspace{24pt}i = n, $
6.	$ \hspace{24pt}j = \mathcal{B}'_n[x].j+1 $
7.	$ \hspace{24pt}left = \mathcal{B}'_n[x-1] $
8.	$ \hspace{24pt}right = \mathcal{B}_n[0] \ {\bf if} \ x \ne {\rm size}(\mathcal{B}'_n)-1 \ {\bf else} \ \mathcal{B}'_n[x] $
9.	$ \hspace{24pt}\mathcal{B}_n := b \{i, j, left, right\} \ \mid\mid \ \mathcal{B}_n $
10.	$ \hspace{12pt}{\bf return} \ \mathcal{B}_n $

Algorithm 2. $T_n$ が内包する一過性の中間ノードを求めるアルゴリズム。

また Algorithm 1 と Algorithm 2 に基づいて $n$ から集合 $\mathcal{B}'_n$ と $\mathcal{B}_n$ を求めるスクリプトを以下に示す。

$n$-th 世代の $T_n$ に対して行う操作は $\mathcal{B}'_n$ と $\mathcal{B}_n$ に含まれるノードを頻繁に参照するためこれらはメモリ上にキャッシュしておくと良いだろう。

部分木の範囲

任意の部分木 $T_{i,j} \subseteq T_n$ に含まれている葉ノードのインデックス範囲 $[i_{\rm min}, i_{\rm max}]$ について考える。最大のインデックスが $i_{\rm max} = i$ であることは明らかであるため最小のインデックス $i_{\rm min}$ に注目する。

高さ $j$ を持つ部分木 $T_{i,j}$ は同じ高さ $j$ を持つ部分木 $T_{*,j} \subseteq T_n$ の中で $\alpha=\lceil \frac{i}{2^j} \rceil$ 番目に位置する。ここで、$T_{i,j}$ が完全二分木かどうかにかかわらず $T_{i,j}$ より前の部分木はすべて完全二分木であることに注意。高さ $j$ の完全二分木は $2^j$ 個の葉ノードを含んでいることから、$T_{i,j}$ の最小のインデックス $i_{\rm min}$ は $T_{i,j}$ より前に存在する葉ノードの総数 + 1 と考えることができる。\[ \begin{equation} \left\{ \begin{array}{lcl} i_{\rm min} & = & \left( \left\lceil \frac{i}{2^j} \right\rceil - 1 \right) \times 2^j + 1 \\ i_{\rm max} & = & i \end{array} \right. \label{subtree_range} \end{equation} \] 式 ($\ref{subtree_range}$) より、$T_{i,j}$ に含まれる葉ノードの数は $i_{\rm max}-i_{\rm min}+1$ であることが分かる。また $T_{i,j}$ に隣接する「左隣りの部分木の最大の葉ノード」と「右隣りの部分木の最小の葉ノード」も算出することができる。この考え方は中間ノードの接続の説明で使用する。

実装では、式 ($\ref{pbst}$) を使用して $T_{i,j}$ が完全二分木のときとそうでないときに置き換えることができる。\[ \begin{equation} i_{\rm min} = \left\{ \begin{array}{ll} \left( \left\lfloor \frac{i}{2^j} \right\rfloor - 1 \right) \times 2^j + 1 \ \ & \mbox{If $T_{i,j}$ is a PBST} \\ \left\lfloor \frac{i}{2^j} \right\rfloor \times 2^j + 1 \ \ & \mbox{Otherwise} \end{array} \right. \label{i_min} \end{equation} \] ここで整数 $x$, $y$ に対する $\lfloor\frac{x}{2^y}\rfloor$ はビット演算子を用いて x >> y と、同様に $x \times 2^y$ は x << y と表現することができる。

中間ノードの高さ

BHT において部分木構造 $T_{i,j}$ が完全二分木とならないケースは 2 つある。一つは $b_{i,j}$ が高さの異なる 2 つの完全二分木を左右の枝に接続するケースであり、もう一つは $b_{i,j}$ の右枝 (より大きい $i$ を含む方の辺) が完全二分木でないケースである。ここでどのような中間ノードも左枝と接続している部分木が完全二分木であることに注意。すなはち、任意の $b_{i,j}$ が接続してる 2 つの部分木はレベルが等しいか ($T_{i,j}$ が完全二分木の場合)、または左枝に接続している部分技のほうが大きい ($T_{i,j}$ が完全二分木でない場合)。したがって新しい中間ノード $b_{i,j}$ の左枝に接続する部分技を $T'_{k,\ell}$ とすると $j=\ell+1$ となる。

直列化表現

BHT に $i$ 番目の値 $b_i$ を追加するとき、一つの葉ノード $b_i$ と 0 以上の中間ノード $b_{i,j}$ が発生する。これらのノード情報をまとめ、HVMT の直列化表現 $S$ に $i$ 番目に追加される要素をエントリ $e_i$ と表す。これらは Fig 1 の Serialized Layout のように配置される。ここで、$S$ の最も右に配置されているノードは常に BHT のルートノードである。

エントリ $e_i$ には同一の世代を持つ全てのノード $b_{i,*}$ が含まれている。加えて、中間ノードの右枝に接続しているノードは同一の世代であることから、ノードを右枝側に探索するケースは一度のエントリ読み込みで完了することができる。BHT の特性上、最近追加されたユーザデータが右側に配置されることから、より最近のユーザデータへのアクセスの方が効率的に行うことができる。

検索効率

前述のように BHT の直列化形式においてはある世代で追加されるすべてのノードが同一のエントリに含まれている。言い換えると、任意の中間ノード $b_{i,x}$ の右枝側のノード $b_{i,y}$ は $b_{i,x}$ と同じエントリに含まれており、従って右枝側への探索はストレージ上の 1 回の seek + read で済むことを意味している。従って最悪ケースはルートノードを起点にすべての移動が左枝側となるようなケース、つまり最も古いデータを検索する場合である。最悪ケースではエントリを読み出すための seek + read 回数は $O(log_2 N)$ となる。

最新のエントリをメモリ上にキャッシュしている場合、$T_{16}$ の木構造に含まれている各ノードに到達するまでの seek + read 回数は Fig 3 のようになる。

Fig 3. $N=16$ での各ノードに到達するまでの seek + read 回数。

状態と操作

BHT の直列化表現であるリスト構造を $S$ とし、$S[x]$ を $S$ の $x$ 番目に格納されているノードとする。特に $S[{\rm last}]$ という表記は $S$ の最末尾のノードを表している。

起動時の初期動作

すべての操作は木構造のルートノードである $S[{\rm last}]$ に頻繁にアクセスするため、起動時に $S[{\rm last}]$ の内容を読み込んでメモリ上で保持すべきである。しかし起動時に先頭の $S[1]$ から読み込んでいては $S$ が大きくなったときに時間がかかりすぎることから、ファイルの末尾から $S[{\rm last}]$ を取得できるようにすべきである。

ファイルの末尾から固定長の seek で $S[{\rm last}]$ の先頭が分かる情報を入れておく。$S[{\rm last}]$ からその情報までが正しい情報であることを確認するためのチェックサムを入れておく。ノードとしては正しいがすべての中間ノードが書き込まれていない状況を検知するため、読み込んだ $S[{\rm last}]$ が木構造全体を表していることを確認する。

$S[{\rm last}]$ の破損を検出した場合、$S[1]$ から最後に正しく読み込みができた要素 $b_i$ を $S[{\rm last}]$ として

追加操作

$S$ に新しい葉ノード $b_i$ を追加する操作は Algorithm 1 と Algorithm 2 を用いてエントリ $e_i$ を構築し $S$ に連結する。

以下のノード集合を用いて $e_i$ を構築する。ここですべてのノードは $j$ で降順ソートされるものとする。
- 葉ノード $b_i$
- Algorithm 1 で得た順序集合 $\mathcal{B}'_i$ に含まれる $b'_{i,*}$ である中間ノード
- Algorithm 2 で得た順序集合 $\mathcal{B}_i$ のすべての中間ノード
$e_i$ を $S$ に連結する。

この手順により作成される $e_i$ は、先頭のノードに葉ノード $b_i$、末尾のノードに木構造のルートノードを配置している。

Fig 4 は $T_{13}$ に $b_{14}$ を追加するために上記の操作を行った結果として構築される木構造である。「新しく追加された $b_i$ を含む最大の部分木」と「その部分木の左隣りに位置する最も大きな完全二分木」とを中間ノードが接続し木構造全体が接続されることが分かる。

Fig 4. $n=13$ の BHT に $b_{14}$ を追加したときの中間ノードの構築。

${\rm append}(e:{\it Node})$ 関数

Algorithm 3 は既存の木構造の直列化表現に新しい葉ノード $b_n$ を追加する操作を表している。

1.	$ {\bf function} \ {\rm append}(b_n:Node) $
2.	$ \hspace{12pt}\mathcal{B}'_n = {\rm iterate\_pbst\_roots}(n) $	// Algorithm 1
3.	$ \hspace{12pt}\mathcal{B}_n = {\rm iterate\_ephemeral\_nodes}(n) $	// Algorithm 2
4.	$ \hspace{12pt}e_n = {\rm sort} \ (\{b_n\} \cup \{b_i \in \mathcal{B}'_n \mid i=n\} \cup \mathcal{B}_n) \ {\rm by} \ j $	// $j$ で降順ソートされた順序集合となるように
5.	$ \hspace{12pt}S := S \mid\mid e_i $

Algorithm 3. 木構造に $b_n$ を追加する操作。

検索操作

BHT の検索は通常の二分木検索と同じである。木構造全体が完全二分木となる特殊なケースではすべての葉ノードへは $O(\log_2 N)$ で均等に到達できるが、そうでない場合、最近追加された葉ノードが比較的レベルの低い部分木に属するという偏りを持つことから、最新のデータがより速く検索できる特徴を持つ。ただしその場合、一過性の中間ノードが存在することにより +1 ステップの操作が必要であるため、検索に対する一般化した計算複雑性は $O(\lceil \log_2 N \rceil)$ である。

${\rm range}(b_{i,j}:{\it Node})$ 関数

1.	$ {\bf function} \ {\rm range}(b_{i,j}:{\it Node}) \to ({\it Int}, {\it Int}) $
2.	$ \hspace{12pt}i_{\rm max} = i $
3.	$ \hspace{12pt}i_{\rm min} = (\lfloor 1/2^j \rfloor - (1 \ {\bf if} \ i \bmod 2^j = 0 \ {\bf else} \ 0)) \times 2^j + 1 $
4.	$ \hspace{12pt}{\bf return} \ (i_{\rm min}, i_{\rm max}) $

Algorithm 4. $b_{i,j}$ をルートとする部分木に含まれる葉ノードの範囲を $O(1)$ で算出する関数。

$j$ の範囲が $0..\lceil \log_2 i \rceil$ であることから、$i$ の定義域を 64-bit とすると $2^j$ は 65-bit の値域を取りうることに注意。

${\rm contains}(b_{i,j}:{\it Node},k:{\it Int})$ 関数

二分木の探索で左右の枝のどちらに検索対象の葉ノードが含まれているかは式 ($\ref{subtree_range}$) を使用することができる。あるノード $b_{i,j}$ をルートとする部分木に葉ノード $b_k$ が含まれるかを判定することで中間ノードの左右の枝のどちらに検索対象の葉ノードが含まれているかを判断することができる。

1.	// $b_{i,j}$ をルートとする部分木構造に葉ノード $b_k$ が含まれているかを判定
2.	$ {\bf function} \ {\rm contains}(b_{i,j}:{\it Node}, k:{\it Int}) \to {\it Boolean} $
3.	$ \hspace{12pt}i_{\rm min}, i_{\rm max} = {\rm range}(b_{i,j}) $
4.	$ \hspace{12pt}{\bf return} \ i_{\rm min} \le k \ {\bf and} \ k \le i_{\rm max} $

Algorithm 5. $b_{i,j}$ をルートとする部分木に葉ノード $b_k$ が含まれているかを $O(1)$ で判定する関数。

${\rm retrieve}(e:{\it Node},i:{\it Int})$ 関数

マルチスレッド/マルチプロセス環境で追加と検索の操作を並行処理で行っている場合、追加操作の途中で実行されると $S[{\rm last}]$ が BHT のルートノードでない可能性があることに注意。

1.	$ b_i := {\rm retrieve}(S[{\rm last}], i) $
2.	$ {\bf function} \ {\rm retrieve}(b_{i,j}:{\it Node}, k:{\it Int}) \to {\it Node} $
3.	$ \hspace{12pt}{\bf if} \ j = 0 \ {\bf then} $
4.	$ \hspace{24pt}{\bf return} \ {\bf if} \ i = k \ {\bf then} \ b_{i,j} \ {\bf else} \ {\it None} $
5.	$ \hspace{12pt}{\bf else \ if} \ {\rm contains}(b_{i,j}.{\rm left}, k) \ {\bf then} $
6.	$ \hspace{24pt}{\bf return} \ {\rm retrieve}(b_{i,j}.{\rm left}, k) $
7.	$ \hspace{12pt}{\bf else} $
8.	$ \hspace{24pt}{\bf return} \ {\rm retrieve}(b_{i,j}.{\rm right}, k) $

Algorithm 6. $b_{i,j}$ をルートとする部分木 $T_{i,j}$ から葉ノード $b_i$ を $O(\lceil \log_2 j \rceil)$ で取得する関数。

範囲検索操作

すべての要素は $S$ 上で直列化されているため範囲検索は容易である。$t_0$ から $t_1$ までの要素を取得するには、まず $S$ 上の $b_{t_0}$ の位置を検索し、そこから $S$ を右方向に $b_{t_1}$ を検出するまで読み込むだけで良い。

読み込み位置を $i$ とすると 1 要素あたり 1 から $\log_2 i$ 個の中間ノードの読み込みまたはスキップ (seek) が発生するが、中間ノード自体はそれほど大きくなく、連続した領域であることから I/O バッファが有効に機能して大きな影響はないと考えられる。

$ {\bf function} \ {\rm range\_scan}(b_{i,j}:{\it Node}, i_{\rm min}:{\it Int}, i_{\rm max}:{\it Int}) \to $

Algorithm 7.

ハッシュ付き検索操作

ハッシュツリーとして要素を検索する場合、要素そのものだけではなく経路から分岐する中間ノードのハッシュ値も取得しなければならない。$T_n$ を $b_{n,\ell}$ をルートとする木構造とし、任意のノード $b_{i,j} \in T_n$ に属するすべての葉ノード (ユーザデータ) を取得するときに必要となる中間ノードついて考える。

${\rm level}(b_{n,\ell}:{\it Node}, b_{i,j}:{\it Node})$ 関数

ハッシュ付き検索の結果に必要な中間ノードの個数は $b_{i,j}$ のレベル ($b_{i,j}$ から目的のルートノード $b_{n,\ell}$ までの祖先の数) に等しい。もし $T_n$ が完全二分木であれば $\ell - j$ であることは明らかだが、そうでない場合、$b_{i,j}$ を含む完全二分木までの距離をヒューリスティックに求める必要がある。

1.	$ {\bf function} \ {\rm level}(b_{n,\ell}:{\it Node}, b_{i,j}:{\it Node}) \to Int $
2.	$ \hspace{12pt}{\bf if} \ {\bf not} \ {\rm contains}(b_{n,\ell}, i) \ {\bf then} $
3.	$ \hspace{24pt}{\bf return} \ {\it None} $
4.	$ \hspace{12pt}b := b_{n,\ell} $
5.	$ \hspace{12pt}{\rm step} := 0 $
6.	$ \hspace{12pt}{\bf while} \ b \ne b_{i,j} \ {\bf and} \ b.i \bmod 2^{b.j} \ne 0 $
7.	$ \hspace{24pt}b := b.{\rm left} \ {\bf if} \ {\rm contains}(b.{\rm left}, i) \ {\bf else} \ b.{\rm right} $
8.	$ \hspace{24pt}{\rm step} = {\rm step} + 1 $
9.	$ \hspace{12pt}{\bf return} \ b.j - j + {\rm step} $

Algorithm 8. ノード間の距離 (レベル) を $O(\log n)$ で求める関数。

この関数はサーバ応答に正しい数の中間ノード (ハッシュ値) が含まれていることをクライアント側で検証するために使うことができる。

${\rm retrieve\_with\_hashes}()$ 関数

1.	$ {\bf function} \ {\rm retrieve\_with\_hashes}(b_{n,\ell}:{\it Node}, b_{i,j}:{\it Node}) \to ({\it Set}[{\it Node}], {\it Sequence}[{\it Node}]) $
2.	$ \hspace{12pt}{\bf if} \ {\bf not} \ {\rm contains}(b_{n,\ell}, i) \ {\bf then} $
3.	$ \hspace{24pt}{\bf return} \ {\it None} $
4.	$ \hspace{12pt}b := b_{n,\ell} $
5.	$ \hspace{12pt}{\rm branches} := \emptyset $
6.	$ \hspace{12pt}{\bf while} \ b \ne b_{i,j} $
7.	$ \hspace{24pt}{\bf if} \ {\rm contains}(b.{\rm left}, i) \ {\bf then} $
8.	$ \hspace{36pt}b := b.{\rm left} $
9.	$ \hspace{36pt}{\rm branches} := {\rm branches} \mid\mid b.{\rm right} $
10.	$ \hspace{24pt}{\bf else} $
11.	$ \hspace{36pt}b := b.{\rm right} $
12.	$ \hspace{36pt}{\rm branches} := {\rm branches} \mid\mid b.{\rm left} $
13.	$ \hspace{12pt}i_{\rm min}, i_{\rm max} = {\rm range}(b) $
14.	$ \hspace{12pt}{\rm values} := {\rm range\_scan}(b, i_{\rm min}, i_{\rm max}) $
15.	$ \hspace{12pt}{\bf return} \ ({\rm branches}, {\rm values}) $

Algorithm 9. $b_{i,j}$ 以下に含まれるすべての葉ノードを中間分岐ノード付きで取得する関数。

分岐ノードの算出

ある $T_n$ のルートノードから任意の $b_{i,j} \in T_n$ までを結ぶ距離を求める。Algorithm 1 によって求めた完全二分木の部分構造のルートノードの中で $b_{i,j}$ を含む部分木を $b'_{i',\log_2 i'}$ とする。

対象のノード $b_{i,j}$ を含む完全二分木のルートノードを取得し、$T_n$ のルートノードからの距離を得る。
完全二分木のルートノードを $b'_{i',j'}$ としたとき、$b'_{i',j'}$ からの距離 $j' - j$ を計算する。

1.	$ {\bf function} \ {\rm nodes\_at\_branches}(n:{\it Int}, i:{\it Int}, j:{\it Int}) \to {\it Int} $
2.	$ \hspace{12pt}\mathcal{B}'_n = {\rm Algorithm1}(n) $
3.	$ \hspace{12pt}b := {\rm root \ of \ } T_n $
4.	$ \hspace{12pt}{\bf for} \ b'_{i',j'} \ {\bf in} \ \mathcal{B}'_n $
5.	$ \hspace{24pt}{\bf if} \ {\rm contains}(b'_{i',j'}, i, j) $

ロールバック

ロールバック操作は直列化されたストレージをある世代の位置まで truncate するだけである。

キャッシュ設計

木構造 $T_n$ への追加操作では中間ノードの接続のために $T_n$ 上の完全二分木となる部分構造のルートノードを最大で $\log_2 n$ 個参照する必要がある。もし適切なキャシュを実装していなければ、これらのノードを参照するために直列化表現 $S$ から $O(\log n)$ の検索操作を $\log_2 n$ 回繰り返す必要があるが、幸いキャッシュ対象のノードもその個数も明確である。

並行処理

BHT に書き込まれた要素および関連するツリー構造が不変であることは並行処理に有利に機能する。直列化表現 $S$ への要素や中間ノードの追加は単一プロセスで行う必要があるが、検索については検索開始時点の確定済み木構造を基準に行うことで、追加処理や他の検索処理が進行中であっても安全に行うことができる。

楽観的ロックを使うアイディア

要素の追加頻度がそれほど高くないシステムにおいては楽観的ロックを使うことで CPU リソースの効率化を期待することができる。

一つの方法は、確定済みの高さを表すアトミック更新が可能な変数 $x_1$ と、追加処理が進行中の高さを表す CAS (Compare and Swap) が可能な変数 $x_2$ を使用する。追加処理を開始したプロセス $P$ はまず $x_1$ から最新の確定済み高さを参照し (仮にその値を $n$ とする) 木構造 $T_n$ に基づいて要素や中間ノードの直列化表現をメモリ上で準備する。次に、実際に書き込みを行う直前に $x_2$ に対して $n \to n+1$ の更新を試みる。$x_2$ の更新に成功した場合、実際に書き込みを行い、最後に $x_1$ を $n+1$ に更新する。$x_2$ の更新に失敗した場合は自身が基準にした木構造 $T_n$ が最新ではないため最初からやり直す。ただし、この方法は $x_2$ の更新に成功したプロセスが $x_1$ を更新する前に (外部からのシグナルや disk full などで) 停止してしまうケースである。この場合、ある一定期間 $x_1 \ne x_2$ かつ書き込みが進行していなければ、書き込み中のプロセスが使用している I/O リソースをクローズし、書き込み位置を $x_1$ の最後まで戻し、最後に $x_2$ を $x_1$ と等しくなるように戻すといったタイマー監視の処理が必要になるかもしれない。

障害耐性

BHT では直列化された個々のノードが (ハッシュツリーのハッシュ値はと別に) チェックサムを持つことでデータの破損を検出可能にしている。

要素の追加操作中にシステムが異常終了した場合、次に起動したときに $S[{\rm last}]$ が破損している可能性がある。それぞれのノードはチェックサムを追加することによって破損を検出できるようにしている。

最後のエントリがすべてのデータとツリー構造を要約していることから、完成した BHT の最後のエントリに対する署名を追加することで、第三者が検証可能なように "封印" することができるだろう。

ハッシュグラフとしての拡張

木構造の特定の世代を基準に別のハッシュ木を枝として分岐させることができるだろう。これは git のブランチシステムに似ている。

ブロックチェーンへの応用

一般的なブロックチェーンは、あるブロックに前のブロックのハッシュ値を埋め込むことで概念的にチェーン状のデータ構造を構築します。これは追記型で不変なデータ構造であるため、チェーン状のデータ構造の代わりに BHT を使用することができます。

BHT はハッシュ木であることから、いわゆるライトクライアントと呼ばれる一部のデータのみを追跡するノードは、信頼できる方法でルートハッシュのみを追跡すれば良く、任意のフルノードに問い合わせて得たブロックが正しいかどうかは通常のハッシュ木を使った方法と同様の方法で検証することができるという利点がある。

1.	\( {\bf function} \ {\rm iterate\_pbst\_roots}(n:{\it Int}) \to {\it Sequence}[{\it Node}] \)
2.	\( \hspace{12pt}x := n \)
3.	\( \hspace{12pt}\mathcal{B}'_n := \emptyset \)
4.	\( \hspace{12pt}{\bf while} \ x \ne 0 \)
5.	\( \hspace{24pt}j = \max \{j \in \mathbb{Z} \mid 2^j \le x\} \)
6.	\( \hspace{24pt}\mathcal{B}'_n := \mathcal{B}'_n \mid\mid b'_{n-x+2^j,j} \)	// \(b'_{n-x+2^j,j}\) は完全二分木となる部分構造のルート
7.	\( \hspace{24pt}x := x - 2^j \)
8.	\( \hspace{12pt}{\bf return} \ \mathcal{B}'_n \)

Banded Hash Tree

概要

特徴

導入

BHT 構造