マークルツリーは、コンピュータサイエンスと暗号学で使われるデータ構造です。仮想通貨市場においてマークルツリーとは、ブロックチェーン上でハッシュ関数によって処理された取引の要約を保持するデータ構造を指します。マークルツリーがあることで、ブロックチェーン上の取引ブロックを簡単かつ効率的に検証できます。この記事では、マークルツリーとは何かという疑問にお答えします。
マークルツリーを考案したのはラルフ・マークルです。彼は1979年にこの概念で特許を取得し、1987年に発表した論文「従来型暗号化関数に基づくデジタル署名」の中でマークルツリーの考え方に言及しました。マークルツリーは、ハッシュ値で構成された図式状のデータ構造です。データのハッシュコードは、下から上へと図の形に並べられます。下の段のハッシュを結合することで、その上のハッシュの値が決まる仕組みです。
システム内のデータの完全性は、まさにこの構造によって守られています。ハッシュ値が図の中に整然と並び、下から上へと順番にまとめられていくからです。マークルツリーは、個人から個人へのデータ転送やピアツーピア（P2P）でのやり取り、そして転送されたデータの検証に使われます。マークルツリーを使えば、転送されたデータやデータブロックが破損していないか、改ざんされていないかを判断できます。ブロックが正しいかどうかも、同じ仕組みで確認できます。
マークルツリーの仕組み
マークルツリーは、ブロックの中にあるハッシュ値で構成されています。ツリーの最下層にあるのが取引データです。このデータにハッシュ関数を実行すると、ハッシュ値（ハッシュコード）が得られます。次に、図の下段にある値どうしを結合し、得られた値を一つ上の段に書き込みます。この処理を繰り返すことで、マークルツリーが組み上がっていきます。最終的に、図の頂点にあるハッシュ値はルートハッシュ（マークルルート）と呼ばれます。算出されたルートハッシュは、ブロックに誤りがあるかどうかを映し出します。ルートハッシュを構成する値に不整合があれば、システムのアルゴリズムは誤りのないマークルルートが生成されるまでハッシュ関数による処理を続けます。
ビットコインでマークルツリーが使われる理由
ビットコインのブロックチェーン上でブロックを検証したいマイナーにとって、作業が格段に楽になるからです。ビットコインのブロックチェーンでは、マイナーがハッシュ関数を実行してブロックを検証します。データは順番に並べられてマークルツリーに格納され、その後アルゴリズムのハッシュ関数が働いてルートハッシュが算出されます。得られたルートハッシュは、その後のマイニング作業にも利用できます。こうしてマイナーは、すべてのブロックをハッシュ化する代わりに、ルートハッシュだけをハッシュ化して作業を続けられるのです。マークルツリーは、ビットコイン以外の仮想通貨のブロックチェーンでも同じように役立っています。