マークルルート、マークルツリー｜詳解ビットコイン⑪

『詳解ビットコイン』（Kalle Rosenbaum著、オライリージャパン）を読んでいます。その個人的なまとめとして書いていきます。

マークルルートの役割

トランザクションの改ざんや削除を防ぐために、ビットコインではブロックチェーンが使われています。

上図のように各ブロックには様々なものが入っていますが、今回はそのうちのマークルルートについてみていきます。

このマークルルートはブロック内のトランザクションを元にしてできているので、トランザクションに変更があれば変わります。したがって、マークルルートの値が変わっていればトランザクションに変更があったことがわかります。

マークルルートには、そのブロック内のトランザクションを改ざんや削除から守る役割があるといえます。

マークルルートの作り方

先ほどは、マークルルートはブロック内のトランザクションからできているとざっくり記載しましたが、ここからはより具体的にマークルルートの作り方について見ていきます。

そもそもマークルルートとは、マークルツリー（ハッシュツリー）と呼ばれるデータ構造のトップにあるハッシュを指すようで、以下の図の「Top　Hash」という部分がそれに該当すると思われます。

画像引用：Wikipedia

ビットコインでは、ブロック内のすべてのトランザクションを下図の一番下の位置に配置し、それからマークルツリーを作っています。

上図の（1）から（5）の箇所についてそれぞれ補足していきます。

（1）について

ブロック内に含めたいトランザクションを順番に並べます。ちなみに、各トランザクションの入力に、先に配置されているトランザクションのUTXOを用いることは可能です。たとえば、TX3の入力にTX2のUTXOを用いることは可能です。また、一番目にはコインベーストランザクションを配置します。

（2）について

ブロックに含めるトランザクション数が奇数の場合、最後のトランザクションのクローンを作ります（上図ではTX3）。クローンはマークルルートを計算するために一時的に必要になるだけで、ブロック内には含めません。

（3）について

各トランザクションをダブルSHA-256で処理します。つまり、トランザクションIDを算出しています。上図のカッコ内には、ハッシングの結果としてこんなハッシュ値が出てくるという例です。たとえば、TX1をハッシングした結果、 (1…a)という出力が出てきたといった意味合いで記載しています。

（4）について

（3）で求めたハッシュのうち、隣接する位置関係にある2つを連結していきます。たとえば、「1…a」というハッシュと「2…b」というハッシュが隣り同士の位置関係にあるとき、それらを連結して（そのままくっつけて）、「1…a2…b」という値を得ます。

その後、連結してできた値をダブルSHA-256でハッシングします。

（5）について

（4）の操作を繰り返していると、いずれは出力されるのが1つのハッシュのみとなります。このようにしてできたハッシュがマークルルートです。

マークルルートがブロック内のすべてのトランザクションの要素を含んでいる様子がよくわかりますね。

こうしてできたマークルルートはブロックヘッダーに入れられ、トランザクションの変更や削除、追加などを検知する役割を果たします。