最近理解したので、忘備録も兼ねて投稿します。
ブロックチェーンのProof of Workについて、良く解説されるのが、
「前のブロックをハッシュ化してNonce（一度限りの数字）を付加して新ブロックをハッシュ化する。ブロックを改竄しようとしたら、このNonceをすべて再計算する必要があり、その間に新しいブロックが作られるため、改竄ができないようになっている」
というものですが、なかなかイメージがつかみづらいかと思います。
・ブロックには何がどう書かれている？
・ブロックのハッシュ化とは何？
・Nonceはどうやって決める？
・なぜNonceを決めるのが難しい？
・なぜ改竄ができない？
という疑問に答えるため、サンプルをもとに実演します。
なお、本記事には、下記のサイトを参考に記載しました。
https://qiita.com/trey0329/items/d859cc9df6d7b188c6a3
https://hackernoon.com/learn-blockchains-by-building-one-117428612f46
1. ブロックには何がどう書かれている？
ブロックには、
・インデックス
・前のブロックのハッシュ値
・タイムスタンプ
・新しいブロックの取引情報
・Nonce
が記録されます。
Pythonの辞書型で表現すると、
block = {
"index":2
"timestamp":1665386454.385751
"transactions":[]
"proof":8719932
"previous_hash":'06e3866abfc84d40057e9e27109c9945cb62e065772f60a6eb4f58db2df0f92b'
}
等となり、
取引(transactions)の内容は、
[{"sender":"A",
"recipient":"B",
"amount":100,
}, {"sender"....}
]
等と記録されます。
2.ブロックのハッシュ化とは？
ハッシュ化とは、不可逆な変換であり、ハッシュにするのは簡単ですが、出力されたハッシュから元の値を復元するのは実質不可能、というものです。
実際に、ブロックをハッシュ化してみましょう。
１つのブロックのサンプルとして、下記を使用します。
block = {
"index":2,
"timestamp":1665386454.385751,
"transactions":[{"sender":"8527147fe1f5426f9dd545de4b27ee00",
"recipient":"a77f5cdfa2934df3954a5c7c7da5df1f",
"amount":5,}],
"proof":8719932,
"previous_hash":'06e3866abfc84d40057e9e27109c9945cb62e065772f60a6eb4f58db2df0f92b',
}
これは、辞書型なので、json.dumps で文字列型に変換します。
import json
block_string = json.dumps(block, sort_keys=True)
block_string
sort_keys=Trueにより、キーをアルファベット順に並び替える事で、ハッシュ化の結果に違いが出ないようにしています。
{"index": 2, "previous_hash": "06e3866abfc84d40057e9e27109c9945cb62e065772f60a6eb4f58db2df0f92b", "proof": 8719932, "timestamp": 1665386454.385751, "transactions": [{"amount": 5, "recipient": "a77f5cdfa2934df3954a5c7c7da5df1f", "sender": "8527147fe1f5426f9dd545de4b27ee00"}]}
これを、hashlib.sha256を使ってハッシュ化します。
import hashlib
hashlib.sha256(block_string.encode()).hexdigest()
hashlib.sha256を使うために、block_stringをencode()しています。また、この結果はオブジェクト型なので、hexdigest()により、16進表記にしています。
833a621897c2795852c0c03f9e1620d05361ee8fe339fa18d7f2fb0ebaf9d6bc
長ったらしい辞書型の文字列が、固定長のすっきりした文字列になりました。
3. Nonceはどうやって決まるのか？
ブロックチェーンの特徴の１つが、Nonceと呼ばれる、一度限りの数値です。
「このNonceを求めるのが計算力を使う」と言われますが、具体的にはどうやっているのでしょうか？
これは、「前のブロックにNonceをつけてハッシュ化した値が、左〇〇桁が"0"になるようにする」というものになります。
ハッシュ化した後の値は、元の値が１文字異なっただけでも、まったく異なる値となるのが特徴です。
たとえば、上記ハッシュ値に「０」「１」の文字を加えたものを、それぞれハッシュ化してみましょう。
orig_value="833a621897c2795852c0c03f9e1620d05361ee8fe339fa18d7f2fb0ebaf9d6bc"
hash_1 = hashlib.sha256((orig_value + "0").encode()).hexdigest()
hash_2 = hashlib.sha256((orig_value + "1").encode()).hexdigest()
print(hash_1)
print(hash_2)
aaa5ca23ad949385adb93ba58fab4ee3781f6b03acfa3a95398833f3abbfa4a2
789067aa346e4e04b135fcc8803ae963335935855ae94438ab27f7abe37b3b17
全く関連性のない２つの値となりました。
したがって、「左〇〇桁が"0"になるように」というのは、計算で予測できるものではなく、ひたすらNonceを変えて試す必要があります。
たとえば、左１桁が"0"になるNonceを求めてみましょう。
nonce = 0
while 1:
hash_value = hashlib.sha256(f'{orig_value}{nonce}'.encode()).hexdigest()
if hash_value[0:1] == "0":
break
nonce += 1
print(nonce)
print(hash_value)
9
0d9e49f8f1c68019698008a44270cb93879aa3f93e1a9bb41b8ccab1213982d5
Nonceが9となり、見事ハッシュ化した後の左１桁が"0"となりました。
4. なぜNonceを決めるのが難しい？
先ほどの例は、左１桁が"0"でしたが、次は左２桁が"0"となるようにしてみましょう。
nonce = 0
while 1:
hash_value = hashlib.sha256(f'{orig_value}{nonce}'.encode()).hexdigest()
if hash_value[0:2] == "00":
break
nonce += 1
print(nonce)
print(hash_value)
333
0048434a5f9d2b5cad35a59341ec721df4835be2e3fdd2529a20f249adb41bb2
見事333回目に左２桁が"0"となりました。
ここまでは何の問題もないように見えます。
今度は、左５桁が"0"になるようにしてみましょう。
コードは省略しますが、結果として、
1543749
000003c5183ed8bda418eb426020b780ce6da109198cadf6365cfbc3dc803b9c
となり、1,543,749回の計算となりました。google colabのCPUでは、約2秒かかっています。
これが、左６桁となると、
7275800
00000070288462ba705c356feb366a9c44900f67bed523111953a5ab5075b3f
で、約11秒、
左７桁では、
600578735
0000000faf2edfd66768c6f76dd6c725a1e800ac8fe68dee23c321b537f1d461
で、なんと15分かかってしまいました。６億回(!)を超える計算をしています。
このように、桁数が増えると、途端に計算に時間がかかるようになります。
この左側を"0"にする桁数を、難易度(difficulty)といいます。
これが、「計算に大量の電力を消費する」と言われる所以です。
ブロックを追加、すなわちビットコインの報酬を得るのは、この計算を一番早く完了させた１人のみです。15分も計算して、報酬がゼロになるのは、やりきれないですね。
5. なぜ改竄ができない？
それでは、なぜこのような計算をさせるのでしょうか。
この計算は、取引に全く関係のない、無駄な計算となります。
しかし、逆説的に言えば、この計算の長さが改竄防止効果となるのです。
たとえば、次の４つのブロックを考えてみましょう。なお、参考にしたサイトに従い、コードではNonceをproofという名前のキーにしています。
BLOCK = [{},{},{},{}]
BLOCK[0] = {'index': 1,
'timestamp': 1665577856.9328945,
'transactions': [],
'proof': 100,
'previous_hash': 1}
BLOCK[1] = {'index': 2,
'timestamp': 1665577872.818851,
'transactions': [{'sender': '8527147fe1f5426f9dd545de4b27ee00',
'recipient': 'a77f5cdfa2934df3954a5c7c7da5df1f',
'amount': 5}],
'proof': 47574599,
'previous_hash': 'f768e1ff0146b9fa0fd5e92d6b5be32e7fd4523f8bd59f9d36cef580e325552b'}
BLOCK[2] = {'index': 3,
'timestamp': 1665577880.5739865,
'transactions': [{'sender': 'a77f5cdfa2934df3954a5c7c7da5df1f',
'recipient': 'a77f5cdfa2934df3954a5c7c7da5df2g',
'amount': 3}],
'proof': 20642823,
'previous_hash': '19323c4b1f6bda711505bc56eb73865305ec3f260d5e8e5c1cd9bdbd9d8fa523'}
BLOCK[3] = {'index': 4,
'timestamp': 1665577886.553881,
'transactions': [{'sender': 'a77f5cdfa2934df3954a5c7c7da5df1f',
'recipient': 'a77f5cdfa2934df3954a5c7c7da5df3h',
'amount': 2},
{'sender': 'a77f5cdfa2934df3954a5c7c7da5df3h',
'recipient': 'a77f5cdfa2934df3954a5c7c7da5df4i',
'amount': 2}],
'proof': 13515079,
'previous_hash': 'dd07ff6a8fe79fcfa309f5a7111096d6f5c5bcab5b698d91053fa91365ed7a70'}
まず、このブロックが正当なものであるかを検証します。
ポイントは、
・previoud_hashが、本当に前のブロックのハッシュ値と一致しているか。
・Nonceの設定は正しいか(i.e. ハッシュ化した場合、"0"が指定桁数並んでいるか)
です。
なお、上記例では、難易度(difficulty)を6に設定しています。
BLOCK[0]のハッシュ値を計算すると、
hashlib.sha256(json.dumps(BLOCK[0], sort_keys=True).encode()).hexdigest()
'f768e1ff0146b9fa0fd5e92d6b5be32e7fd4523f8bd59f9d36cef580e325552b'
となり、見事BLOCK[1]のprevious_hashの値と一致します。
また、この値にBLOCK[1]のNonceである47574599を付加してハッシュ値をとると、
hashlib.sha256(f'{BLOCK[1]["previous_hash"]}{BLOCK[1]["proof"]}'.encode()).hexdigest()
'0000001a2b41105bf60d1a0d680327f399904051f8eede53ace7d34c414ac469'
となり、左6桁が"0"となっています。
計算は省略しますが、BLOCK[2], BLOCK[3]も同様に確認できます。
それでは、ここで、BLOCK[1]の内容を改竄してみましょう。
具体的には、トランザクションのamountを5から10に変えてみます。
BLOCK[1] = {'index': 2,
'timestamp': 1665577872.818851,
'transactions': [{'sender': '8527147fe1f5426f9dd545de4b27ee00',
'recipient': 'a77f5cdfa2934df3954a5c7c7da5df1f',
'amount': 10}],
'proof': 47574599,
'previous_hash': 'f768e1ff0146b9fa0fd5e92d6b5be32e7fd4523f8bd59f9d36cef580e325552b'
}
このハッシュ値をとってみましょう。
85207769c4052306aced392cc5356efb6a51c80b3b450df1617fc131dac680bf
となり、BLOCK[2]のprevious_hashと異なってしまいます。
それでは、BLOCK[2]のprevious_hashを書きかえればよいのでしょうか。
実際に書き替えてみましょう。
BLOCK[2]["previous_hash"] = "85207769c4052306aced392cc5356efb6a51c80b3b450df1617fc131dac680bf"
これは大丈夫でしょうか。
ここで、BLOCK[2]のNonceが正しいか、もう一度確認してみましょう。
hashlib.sha256(f'{BLOCK[2]["previous_hash"]}{BLOCK[2]["proof"]}'.encode()).hexdigest()
'f612fffab04a9eca9654f1947787d6fd57b381d36a3bff4ecf922bc5446cf98c'
となると、"0"が6桁並ばなくなりました。
これの辻褄を合わせるために、もう一度Nonceを計算しなければならないようです。
def proof_of_work(input_value):
difficulty=6
nonce = 0
check_value = "0" * difficulty
while 1:
hash_value = hashlib.sha256(f'{input_value}{nonce}'.encode()).hexdigest()
if hash_value[0:difficulty] == check_value:
break
nonce += 1
#print(nonce)
#print(hash_value)
return nonce
proof_of_work()
22176632
33秒かかって、Nonceを計算し直しました。
これで、BLOCK[2]の辻褄は合います。
ところが、Nonceとprevious_hashの値を変えたため、BLOCK[2]のハッシュ値もBLOCK[3]のprevious_hashと異なってしまいました。
また、つじつま合わせのためにBLOCK[3]のNonceを再計算する必要がありそうです。
BLOCK[2]["proof"]=22176632
BLOCK[3]["previous_hash"]=hashlib.sha256(json.dumps(BLOCK[2],sort_keys=True).encode()).hexdigest()
proof_of_work(BLOCK[3]["previous_hash"])
15390054
24秒かかって、Nonceを再計算しました。
これで、新しいブロックをつくれば、改竄完成です。
ところが、ちょっと待ってください。
2回計算して、59秒経過している間に、他のマイナーが新しいブロックを追加してしまいました。
もはや、改竄したブロックが一番長いブロックではなくなり、承認される事はなくなってしまいました。
今回は４ブロックでdifficultyが６のサンプルでしたが、実際はもっと長いブロックで、difficultyも大きいので、より、改竄が非現実的となってきます。
これが、Proof of workの計算が、改竄防止につながる、という理屈になってくるわけです。