rubyでマークルツリーを書いてみた

ブロックチェーンの勉強をしていてマークルツリーがどんなものかをrubyで書いてみました。 (まだ、勉強したてなので間違えているかもしれません、その際はご教授ください)

マークルツリーについてはわかりやすい記事があるので他のを参考にするといいです。

以下がソースです。
make_merkle_tree(data_list)のdata_listは配列です。

ソース

require "digest/md5"

def make_merkle_tree(data_list)
  loop do
    hash_list = data_list.map {|data| Digest::MD5.hexdigest(data) }
    hash_set_list = make_set(hash_list)
    data_list = integrate_hash(hash_set_list)
    break if data_list.size == 1
  end
  data_list.first
end

def make_set(hash_list)
  hash_list.each_slice(2).to_a
end

def integrate_hash(hash_set_list)
  hash_set_list.inject([]) do |integrated_data_list, hash_set|
    hash_set << hash_set.first if hash_set.size < 2
    integrated_data_list << "#{hash_set[0]}#{hash_set[1]}"
  end
end

実際に動かしてみました。
data_listのなかがビットコインでいうトランザクション(取引)データです。
取引データが
["a","b","c","d","e"] とあったら。
全ての取引は
"dfbd34a5b6634d7ccd0aa26a4dec2eccfb8a3688c2f3cc709e72181bd8074cc3"
で全て表現できているということを表しています。

もし、["a","b","c","d","e"]が ["a","b","c","f","e"]のように書換えられてしまうと、 異なるハッシュ値を返してしまいます。

これはどういうことかというと、ビットコインの生成するための計算ではタイムスタンプやナンスなどとこのトランザクションの結果をまとめてハッシュ化しており、取引データが改竄されると、計算が合わなくなり、改竄が発覚します。

なので、ブロックチェーンのデータの改竄は難しくなっているのです。 この他にも、改竄対策にはデータのコンセンサスの問題などもあるのですが、今回はマークルツリーの実装の話なので、置いておきます。

実行

[9] pry(main)> make_merkle_tree(["a"])
=> "0cc175b9c0f1b6a831c399e2697726610cc175b9c0f1b6a831c399e269772661"
[10] pry(main)> make_merkle_tree(["a","b"])
=> "0cc175b9c0f1b6a831c399e26977266192eb5ffee6ae2fec3ad71c777531578f"
[11] pry(main)> make_merkle_tree(["a","b","c","d"])
=> "3bc22fb7aaebe9c8c5d7de312b876bb81ee715fcc373a83611d163d9d4ea02a3"
[12] pry(main)> make_merkle_tree(["a","b","c","d","e"])
=> "dfbd34a5b6634d7ccd0aa26a4dec2eccfb8a3688c2f3cc709e72181bd8074cc3"