マークル木【Markle Tree】

マークル木 とは、ファイルのような大きなデータを要約した結果を格納するツリー構造の一種です。

主に入出金記録などの大きなデータの要約と検証を行う際に使用されます。

データ要約および検証時の計算にハッシュ関数を用いているので、ハッシュ木とも呼ばれます。

マークル木は、公開鍵暗号方式の開発者ラルフ・マークルが1979年に発明しています。

原著論文はこちら

マークル木 の構造

マークル木では、2つのデータを1つにまとめて1単位のデータとして取り扱います。

 マークル木 【Markle Tree】 ファイルのような大きなデータを要約した結果を格納するツリー構造の一種です。 主に入出金記録などの大きなデータの要約と検証を行う際に使用されます。 データ要約および検証時の計算にハッシュ関数を用いているので、ハッシュ木とも呼ばれます。

上の図では、トランザクション0(Tx0)のハッシュ、トランザクション1(Tx1)のハッシュをそれぞれ計算しています。

このAのハッシュ、Bのハッシュそれぞれを合わせた値のハッシュが頂点のハッシュ値となります。

データが蓄積されるにつれ、複数段のツリー構造が構成されてゆき、2段、3段と2個ずつハッシュ値がまとめられてゆきます。

最終的に得られた頂点のハッシュ値はマークルルート(トップハッシュやマスターハッシュとも)と呼ばれています。

マークル木には、どんなデータを入力しても一定長の値を返すハッシュ関数が使用されています。

そのため、どんなに多くの大きなデータを入力しても最終的に得られる値は一定のデータ長になります。

つまり、2個のデータを要約しても、175386個のデータを要約しても、最終的には同じデータ長にまとめることができるのです。

また、計算が単純なため、マークルルートの値を得るのに負荷が少なくて済みます。

ビットコインなどの仮想通貨では、この特性を応用することで要約元のデータの検証に用いています。

すなわち、予め保存しておいたマークルルート値とブロックのデータがあれば、

新たなブロックのデータから算出したマークルルートの値と、予め保存されたマークルルートの値を比較検証することが可能になっています。

BAPチャットボット x

  • BAP

    BAPのオフショア開発サービスに関する基本情報をご案内いたします。 以下よりご関心の項目をご選択ください:

    詳細な仕様が伝わらないなど、コミュニケーション面の心配があります。日本語でのコミュニケーションには問題ありませんか?
    開発のみならず、リリース後の保守もお願いしたいのですが可能ですか?
    オフショア開発はサービスの品質に不安がありますが、品質を保証していただけますか?
    オフショア開発は未経験です。依頼をする場合は、どのような体制でどのような資料を準備するのが一般的なのでしょうか?
    業務システムでオフショアにお願いしようと考えているが、業務や複雑な仕様でも理解することは可能ですか?
    開発現場を見に行くことは可能ですか?
    AI研究を行いたいのですが、依頼は可能でしょうか?
    開発体制・技術スキルを教えてください
    品質保証はどうされていますか。
    プロジェクトの納期をしっかり守るためにどのようなことをしていますか?
    支払タイミングは顧客の都合に合わせてくれますか?
    検収はどのように行っていますか。
    緊急対応が発生する場合、どのような体制で対応していますか。
    20/02 10:36 ✓