データ検証などで利用するMerkle Treeのメモ

データの検証などで利用される Merkle tree/マークル木/hash tree/ハッシュ木についてメモ。

Merkle Tree の概要

wikipedia の概要をそのままコピペ。

暗号理論および計算機科学において、ハッシュ木(Hash tree, ハッシュツリー)またはマークル木(Merkle tree)とは、より大きなデータ(例えばファイル)の要約結果を格納する木構造の一種であり、データの検証を行う際に使用される。このデータ構造はハッシュリストとハッシュチェインの組み合わせでできており、ハッシュ法の延長上にある手法といえる。

Merkle tree の利用例

merkle tree が2つ与えられた時に、ルートノードから子ノードに向かってハッシュ値をたどっていけば、どこが壊れているのか特定が簡単で、壊れている部分木だけを更新すればよい。
Amazon dynamo/cassandra/riak はレプリカ間の同期(anti-entorpy)に Merkle tree を使っている。

別の例として、AWS Glacier のマルチパートアップロード

  1. マルチパートアップロード開始時にブロックサイドを指定
  2. マルチパートアップロード時に各ブロックのデータとハッシュ値と位置(アーカイブのXバイト-Yバイト目)を指定
  3. マルチパートアップロード終了時にアーカイブ全体のファイルサイズと Merkle tree のルートハッシュ値を指定

するAPIになっている。

サーバ側は、分割アップロードされた各ブロックを位置順に並び直し、Merkle tree のルートハッシュ値を求め、クライアントがマルチパート終了時に送信したチェックサムと突き合わせている。

ハッシュ値を実際に計算してみる

Merkle Tree の理解を深めるため wikipedia の記事で使われてる例を元に 実際に Merkle Tree のハッシュを計算してみる。

処理の流れは以下

  1. データをブロックサイズで分割
  2. 各ブロックのハッシュ値を求め、葉ノードとする
  3. 親ノードは各子ノードのハッシュ値を連結した文字列のハッシュ値とする
  4. 根ノードに辿り着くまでこの操作を繰り返す。

データを分割

ハッシュ値を求めるファイル(サイズは 4 MiB)を作成する。

$ FILENAME=file.txt
$ dd if=/dev/urandom of=$FILENAME bs=1048576 count=4
4+0 records in
4+0 records out
4194304 bytes (4.2 MB) copied, 3.37527 s, 1.2 MB/s

ブロックサイズ 1MiB でファイル分割する。
分割ファイル名は”L”で始まり、分割ファイルは1からの数字で採番(–numeric=1)する

$ BLOCKSIZE=1048576 # 1MiB
$ split -b  -d $FILENAME
$ split --bytes=$BLOCKSIZE --numeric=1 --suffix-length=1 $FILENAME L

$ ll
total 8192
-rw-rw-r-- 1 jsmith jsmith 1048576 Apr 11 20:31 L1
-rw-rw-r-- 1 jsmith jsmith 1048576 Apr 11 20:31 L2
-rw-rw-r-- 1 jsmith jsmith 1048576 Apr 11 20:31 L3
-rw-rw-r-- 1 jsmith jsmith 1048576 Apr 11 20:31 L4
-rw-rw-r-- 1 jsmith jsmith 4194304 Apr 11 20:30 file.txt

ちなみに –numeric オプションは version 8.16 以上でないと動作しない。最近の Amazon Linux であれば OK.

葉ノード

各ブロックのハッシュ(今回はハッシュ関数に sha256 を利用)を求める

Hash 0-0 = hash(L1)
...
Hash 1-1 = hash(L4)

なので、 openssl コマンドでハッシュ値を求める

$ openssl dgst -sha256 -binary L1 > H00
$ openssl dgst -sha256 -binary L2 > H01
$ openssl dgst -sha256 -binary L3 > H10
$ openssl dgst -sha256 -binary L4 > H11

親ノード

次に、これらノードの親ノードのハッシュ値を求める。
Hash 0-0 と Hash 0-1 の親ノード Hash 0 のハッシュを求めるには、Hash 0-0 と Hash 0-1 を連結した文字列をハッシュ関数に渡せばよい。つまり

Hash 0 = hash(Hash 0-0 + Hash 0-1)

openssl コマンドで書き換えると

$ cat H00 H01 | openssl dgst -sha256 -binary > H0

となる。同様に

Hash 1 = hash(Hash 1-0 + Hash 1-1)

なので

$ cat H10 H11 | openssl dgst -sha256 -binary > H1

となる。

根ノード

最後に、根ノードのハッシュ値を求める。親ノードの時と同様に

TopHash = hash(Hash0 + Hash1)

openssl コマンドで書き換えると

$ cat H0 H1 | openssl dgst -sha256 -hex # ハッシュ値を確認しやすいようにバイナリ(-binary)ではなくヘックス値(-hex)で出力
(stdin)= dc6dbbb01f9cba0439ded090133e6250ada132e915f15d989d12d7ab4b601657

検証として aws-cli が glacier API で利用している Merkle Tree 実装を利用して、ハッシュ値が一致しているか確認。

$ cat tree_hash.py
# vim: set fileencoding=utf8
import sys
from botocore.utils import calculate_tree_hash
print (calculate_tree_hash(open(sys.argv[1], "rb")))

aws glacer のハッシュ関数は sha256 で、 aws-cli は内部的にブロックサイズを 1MiB としているので、コマンドラインの計算結果と一致するはず。

$ python tree_hash.py file.txt
dc6dbbb01f9cba0439ded090133e6250ada132e915f15d989d12d7ab4b601657

ということで、完全一致。めでたしめでたし。

Advertisements
Tagged with: , ,
Posted in algorithm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Archives
  • RT @__apf__: How to write a research paper: a guide for software engineers & practitioners. docs.google.com/presentation/d… /cc @inwyrd 6 months ago
  • RT @HayatoChiba: 昔、自然と対話しながら数学に打ち込んだら何かを悟れるのではと思いたち、専門書1つだけ持ってパワースポットで名高い奈良の山奥に1週間籠ったことがある。しかし泊まった民宿にドカベンが全巻揃っていたため、水島新司と対話しただけで1週間過ぎた。 それ… 6 months ago
  • RT @googlecloud: Ever wonder what underwater fiber optic internet cables look like? Look no further than this deep dive w/ @NatAndLo: https… 6 months ago
  • @ijin UTC+01:00 な時間帯で生活しています、、、 1 year ago
  • RT @mattcutts: Google's world-class Site Reliability Engineering team wrote a new book: amazon.com/Site-Reliabili… It's about managing produc… 1 year ago
%d bloggers like this: