この記事はデータ構造とアルゴリズム Advent Calendar 2019 18日目の記事です。
17日目は @takilog さんが「Fréchet距離の計算アルゴリズム」について書かれていました。面白かったので、少し勉強してみようと思いました！
19日目は @tsukasa__diary さんの担当です！
ブロックチェーン技術は、耐改ざん性がある技術として暗号資産やトレーサビリティ、知財管理などさまざまな分野で注目を集めています。そんなブロックチェーンの安全性を高める上で大きな役割を果たしているものの一つがハッシュチェーンというデータ構造です。
#ハッシュ関数を生かした巧みな構造
ハッシュ関数とは、入力値のビット長に関わらず一定の長さのビット長を出力する関数です。ハッシュ関数には、以下のような代表的な特徴があります。
- 入力値のビット長に関わらず一定の大きさのビット長のデータを出力する
- 入力値が微妙に変化しても、出力値が大きく変化する
さて、本題のハッシュチェーンですが、これはハッシュ関数を使って出力されたハッシュ値を他のデータと一緒にさらにハッシュ値を生成し、鎖のようにつないでいくことで生成します。
これによって、前後のハッシュ値に依存関係が生まれます。
ハッシュ関数の特徴の一つである入力値のデータサイズに関わらず一定の長さのデータを出力するという点を考えてみると、ハッシュ値と一緒にハッシュ化されるデータがどれだけ多くても、ハッシュ関数にかけてしまえば長さを一定にできることがわかります。
また、入力値が微妙に変化しても、出力値が大きく変化するという特徴から、あるハッシュ値から見て時間的に前に存在するデータが少しでも変われば、変更されたデータから後ろのデータが大きく変動することがわかります。
このように、ハッシュチェーンはハッシュ関数の特徴をうまく活かすことで、前後に依存関係を作ることができるデータ構造になっています。それによって、時間的に前にデータか、後ろにできたデータかを表現できるため、タイムスタンプ的な使い方ができるものにもなっています。
#ハッシュチェーンの簡単な実装
では、簡単にハッシュチェーンを実装してみましょう。今回はPythonを使って実装します。ちなみにハッシュ関数を使うために、hashlibというパッケージを利用します。なお、ハッシュ関数はSHA256を利用します。
import hashlib
hashchain = ["0000000000000000000000000000000000000000000000000000000000000000"]
for i in range(20):
previous_hash = hashchain[-1]
input_data = previous_hash + str(i)
hash_value = hashlib.sha256(input_data.encode()).hexdigest()
hashchain.append(hash_value)
for h in range(21):
print(str(h).rjust(2, "0") + " → " + hashchain[h])
出力結果は以下のような内容になりました。
00 → 0000000000000000000000000000000000000000000000000000000000000000
01 → e531ef0f962409170917abf9de3287afec23dd1c42c9e1fea66c5feab99e8f7c
02 → 78bfc883be934340ac839dcb172ccc44fb71e321660ff5f96a2fde51987e6dde
03 → 7e09bd321bed764f23e8bf63dacf242c877bf3c220f6e8972f211048493ad482
04 → e4724753b4de43f674d58796e5c34b6a37027ff753f487628f0db1e98d60d6f5
05 → 2c3ad1f6144d93e3a32d16dbcfb35255f2e137a14807bd7d5deba9a9a67a8a59
06 → dfa3e16e515d92158e3cf192b335732526aeaa32214bb1ab176cad4b8dce44cc
07 → 4400045f0173fe5321d0f0804b2c62b087bcba990d780bcecc5e8d9cc3d1bc23
08 → 15fda2298655bb712584d22703c7d479180f2b8657049a67293936a435259382
09 → 5cd5f8e2d12357755c5f6a4c8c87697c112123d04c8c463d546dc2577651aad4
10 → 39e239f7562b413273704c13e7eb9581f04c3257d0ef6be10976c48df6585922
11 → df9cc505cf339e98b59f2da52e24a8d7b8fdf02f7ebee88071677f8f3e7ddff0
12 → 459d019e029356caccfbe78309f740306770e511c483ad3fe8339ddbe7e237dd
13 → 6af212f574623719c3ed33ec84b70a01cf8d9b48c989c83c690f37d969c17d3b
14 → f9fdc2226652ebc68e5898f1e319a1e229587e7d794c5367a6b11365604fa179
15 → f3af5537bc19fb1ad26854ac137fb6161743f5c0cd356971394384a9910bb625
16 → a07c0ca7f03d623ecc5641ab0632146dc7b9519f0b3c651c1075f03e4bd5109f
17 → 1923f411a6b9fa14ac7a4daa0aa93d5a9b78c732533b25af88fd9d1c4e7ca5c1
18 → d18af50c3f49d2f1ae2560064d32be044b17097330964ca6b9a958a1c6e53101
19 → 017c93cf83997aa5f7adb1583e39ced9b98215e154f76931c08821225b7ebd0b
20 → e978d91667b6e2031500ef28282bbe20fc8358945b76e2b229ae58c3f7b1088f
今回はシンプルに前のハッシュ値に単純にインデックスを付けてまとめてハッシュ化するという形にしています。
#実際のブロックチェーンでは？
ブロックチェーン技術では、ハッシュチェーンが利用されていますが、上記の簡単な実装のようにシンプルに作られているわけではありません。コンセンサスアルゴリズムをはじめとした他の技術も組み合わせて利用されています。（実際には、もっと複雑ですが。。。）
##コンセンサスアルゴリズムとは？
コンセンサスアルゴリズムは分散ネットワーク上で正しい情報を一意に決定するための手続きです。
例えば、P2Pネットワークでは、正しいデータを決める主体が存在しないため、どのデータを信じればいいのか決めることができません。そこで対等な立場のマシン同士で合意形成をするために、コンセンサスアルゴリズムというものが存在します。
最近では、ブロックチェーンもさまざまな種類のものが登場しており、コンセンサスアルゴリズムもバリエーションが増えています。有名どころだと、Proof of WorkやProof of Stake、Proof of Importance、Delegated Proof of Stakeなどが存在します。
ハッシュチェーンとコンセンサスアルゴリズムの関係性で言えば、計算されたどのハッシュ値を正しいものとするのかを決めるための手続きと考えれば基本的には大丈夫だと思います。
#まとめ
ハッシュチェーンの先頭にある新しいハッシュ値は、それまでにそのハッシュチェーンで計算されてきた全てのハッシュ計算の歴史を抱え込んでいます。ビットコインなどのブロックチェーンでは、一番長いブロックチェーンを正しい情報であるとするというルールがあります。これは、一番長いチェーンが正しい計算を最も蓄積してきたからということが理由の一つとなっています。
ハッシュチェーンというデータ構造、歴史や時間を内包しながら成長していく生き物のような面白い奴だと個人的に思っていますが、みなさんはどうでしょうか？