マークルツリーとは

マークルツリーとは

マークルツリーは、データの要約結果を格納するツリー状のデータ構造のことです。
「ラルフ・マークル」によって1979年に発明されました。

データの要約にはハッシュ値が使われていることからハッシュツリーと呼ばれてます。

マークルルートとは、マークルツリーの頂点に位置するハッシュ値です。

ブロックチェーンでは、この値をブロックヘッダに記録することにより、その配下の各トランザクションデータの改ざんを検知できるようにしてます。

以前投稿したブロックチェーンとはの中で以下のように説明しました。

「マークルルートには全トランザクションのそれぞれをトーナメント戦方式で次々にハッシュ化していき先頭のハッシュ値がここに記載されます。
これによりトランザクションをたとえ1ビットでも変更すると、ハッシュ値の性質から個々の値が大きく変わってしまいます。」

マークルルートの堅牢性について

マークルルートのハッシュ値の詳細を説明する前に、ブロックチェーンの堅牢性をどのように支えているのかを見ていきます。

ブロックのデータ構造を表している下記の図を使って説明していきましょう。

※）マークルハッシュ
この図ではマークルルートがハッシュ値であることを強調するために便宜的に「マークルハシュ」と記載してます。

1つのブロックは通常１MBで、トランザクションデータがおよそ2000～4000個格納されてます。
図の左上の箱はブロックヘッダ（80バイト）で、右下の箱の最下部に並んでいるTx1~Tx8というのがトランザクションデータです。

❶トランザクションはUTXOでリンク

トランザクション２の稿で説明したように各トランザクションはUTXOを経由して互いにリンクしあっており、トランザクションスクリプト（ScriptSigとScriptPubkey）により2重支払ができない仕組みとなっていましたね。

❷ハッシュツリー

各トランザクションのハッシュ値を求め、隣り合うハッシュ値を加算した後、更にハッシュ値を計算し・・・というようにトーナメント戦のように次々にハッシュ値を計算していくと最後の決勝戦の結果出てきたハッシュ値、これがマークルルート（ハッシュ値）ととしてブロックヘッダに書き込まれます。

トランザクションを1ビットでも変更してしまうと、結果的にブロックヘッダのマークルハッシュに全く異なる数値が記載されるので、トランザクションデータに対する改ざんはほぼ不可能ということになるわけです。

❸ハッシュチェーン

それでは、実際にどのように改ざんを検知するのか？
それを明確にするために、前後のブロックを追加した以下の図を用いて説明します。

ここには3つのブロックがあります。
中央のブロックはBlock(n)、左側にあるのがその前のブロックBlock(n-1)、右側にあるの次のブロックBlock(n+1)の３つで、各ブロックのデータ構造（フォーマット）は同じです。

中央のブロックblock(n)のブロックヘッダの先頭に「前ハッシュ」がありますが、これはBlock(n-1)のブロックヘッダのハッシュ値が書き込まれ、Block(n)のブロックヘッダのハッシュ値は次のブロックBlock(n+1)に書き込まれます。

従って、もし中央のブロックBlock(n)のトランザクションを改ざんするとブロックヘッダのマークルルート（図ではマークルハッシュ）が変更され、その結果ブロックヘッダのハッシュ値も書き換わるため、次のブロックBlock(n+1)に書いてある「前ハッシュ」と値が異なってしまいます。

これを書き換えると更にその次のブロックBlock(n+2)のブロックヘッダの「前ハッシュ値」が異なってしまい、更にその次のブロックヘッダの「前ハッシュ」が異なり・・・のように、最後まで書換える必要があるため、結果的に改ざんは不可能だということになります。

マークルルートのハッシュ値の計算方法とは

それではハッシュツリーをどのように生成するのかを以下の図で説明しましょう。

 

Hash(Tx1)～Hash(Tx4)

まず、トランザクションデータTx1~Tx4それぞれにSHA256で2回ハッシュ化（ダブルハッシュ）した値H1,H2,H3,H4を算出します。

Hash(H1+H2), Hash(H3+H4)

隣り合う2つのデータを加算した値に対して更にダブルハッシュ化してH12, H34を算出します。

Hash(H12+H34)

更にH12とH34を加算してダブルハッシュ化した値H1234を算出すると、これが頂点となりますのでマークルルートのハッシュ値が求まりました。
この値をマークルルート、あるいはトップハッシュ、マスターハッシュなどと呼んでます。

トランザクションが奇数の場合

マークルツリーを構築する際に、トランザクションの数が奇数の場合はどのようにして算出するのでしょうか？
答えは簡単で、最後のトランザクションデータを複製することにより偶数にしてから算出しています。

直感的にイメージしよう

実際のどのようにマークルツリーを生成し最終的にマークルルートのハッシュ値を算出するかはやはり動画をみて直感的にイメージしたほうが早いので、弊社内で開催したALT（ライトニングトーク）で録画したビデオをピンポイントでご紹介しましょう。

 

（アーパボー）