マークルツリーとは
マークルツリーとは、データの要約結果を格納するツリー状のデータ構造のことです。
「ラルフ・マークル」によって1979年に発明されました。
データの要約にはハッシュ値が使われていることからハッシュツリーと呼ばれてます。
マークルルートとは、マークルツリーの頂点に位置するハッシュ値です。
ブロックチェーンでは、この値をブロックヘッダに記録することにより、その配下の各トランザクションデータの改ざんを検知できるようにしてます。
以前投稿したブロックチェーンとはの中で以下のように説明しました。
「マークルルートには全トランザクションのそれぞれをトーナメント戦方式で次々にハッシュ化していき先頭のハッシュ値がここに記載されます。
これによりトランザクションをたとえ1ビットでも変更すると、ハッシュ値の性質から個々の値が大きく変わってしまいます。」
マークルルートの堅牢性について
マークルルートのハッシュ値の詳細を説明する前に、ブロックチェーンの堅牢性をどのように支えているのかを見ていきます。
ブロックのデータ構造を表している下記の図を使って説明していきましょう。
※)マークルハッシュ
この図ではマークルルートがハッシュ値であることを強調するために便宜的に「マークルハシュ」と記載してます。
1つのブロックは通常1MBで、トランザクションデータがおよそ2000~4000個格納されてます。
図の左上の箱はブロックヘッダ(80バイト)で、右下の箱の最下部に並んでいるTx1~Tx8というのがトランザクションデータです。
❶トランザクションはUTXOでリンク
トランザクション2の稿で説明したように各トランザクションはUTXOを経由して互いにリンクしあっており、トランザクションスクリプト(ScriptSigとScriptPubkey)により2重支払ができない仕組みとなっていましたね。
❷ハッシュツリー
各トランザクションのハッシュ値を求め、隣り合うハッシュ値を加算した後、更にハッシュ値を計算し・・・というようにトーナメント戦のように次々にハッシュ値を計算していくと最後の決勝戦の結果出てきたハッシュ値、これがマークルルート(ハッシュ値)ととしてブロックヘッダに書き込まれます。
トランザクションを1ビットでも変更してしまうと、結果的にブロックヘッダのマークルハッシュに全く異なる数値が記載されるので、トランザクションデータに対する改ざんはほぼ不可能ということになるわけです。
❸ハッシュチェーン
それでは、実際にどのように改ざんを検知するのか?
それを明確にするために、前後のブロックを追加した以下の図を用いて説明します。
ここには3つのブロックがあります。
中央のブロックはBlock(n)、左側にあるのがその前のブロックBlock(n-1)、右側にあるの次のブロックBlock(n+1)の3つで、各ブロックのデータ構造(フォーマット)は同じです。
中央のブロック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を算出すると、これが頂点となりますのでマークルルートのハッシュ値が求まりました。
この値をマークルルート、あるいはトップハッシュ、マスターハッシュなどと呼んでます。
ハッシュ値とは
ハッシュ値というのは、以下の特徴があります。
(詳細は別稿のハッシュ値とはをご参照ください)
- どんなデータを入力しても一定の長さの値が導出される
- 例え1ビットでも変更すると全く異なる値が導出される
言い換えると、2つのトランザクションを要約しても数千個のトランザクションを要約しても、最終的には同じデータ長となります。
ブロックチェーンではこれが32バイトのマークルルート(図ではマークルハッシュ)に記載されてます。
トランザクションが奇数の場合
マークルツリーを構築する際に、トランザクションの数が奇数の場合はどのようにして算出するのでしょうか?
答えは簡単で、最後のトランザクションデータを複製することにより偶数にしてから算出しています。
直感的にイメージしよう
実際のどのようにマークルツリーを生成し最終的にマークルルートのハッシュ値を算出するかはやはり動画をみて直感的にイメージしたほうが早いので、弊社内で開催したALT(ライトニングトーク)で録画したビデオをピンポイントでご紹介しましょう。
以上
ケニー狩野(中小企業診断士、PMP、ITコーディネータ)
キヤノン(株)でアーキテクト、プロマネとして多数のプロジェクトをリード。
現在、株式会社ベーネテック代表、株式会社アープ取締役、一般社団法人Society 5.0振興協会評議員ブロックチェーン導入評価委員長。
これまでの知見を活かしブロックチェーンや人工知能技術の推進に従事。趣味はダイビングと囲碁。
2018年「リアル・イノベーション・マインド」を出版。