最近理解したので、忘備録も兼ねて投稿します。
ブロックチェーンの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.ブロックのハッシュ化とは？

ハッシュ化とは、不可逆な変換であり、ハッシュにするのは簡単ですが、出力されたハッシュから元の値を復元するのは実質不可能、というものです。
実際に、ブロックをハッシュ化してみましょう。

１つのブロックのサンプルとして、下記を使用します。

python

block = {
    "index":2,
    "timestamp":1665386454.385751,
    "transactions":[{"sender":"8527147fe1f5426f9dd545de4b27ee00",
    "recipient":"a77f5cdfa2934df3954a5c7c7da5df1f",
    "amount":5,}],
    "proof":8719932,
    "previous_hash":'06e3866abfc84d40057e9e27109c9945cb62e065772f60a6eb4f58db2df0f92b',
    }

これは、辞書型なので、json.dumps で文字列型に変換します。

python

import json
block_string = json.dumps(block, sort_keys=True)
block_string

sort_keys=Trueにより、キーをアルファベット順に並び替える事で、ハッシュ化の結果に違いが出ないようにしています。

console

{"index": 2, "previous_hash": "06e3866abfc84d40057e9e27109c9945cb62e065772f60a6eb4f58db2df0f92b", "proof": 8719932, "timestamp": 1665386454.385751, "transactions": [{"amount": 5, "recipient": "a77f5cdfa2934df3954a5c7c7da5df1f", "sender": "8527147fe1f5426f9dd545de4b27ee00"}]}

これを、hashlib.sha256を使ってハッシュ化します。

python

import hashlib
hashlib.sha256(block_string.encode()).hexdigest()

hashlib.sha256を使うために、block_stringをencode()しています。また、この結果はオブジェクト型なので、hexdigest()により、16進表記にしています。

console

833a621897c2795852c0c03f9e1620d05361ee8fe339fa18d7f2fb0ebaf9d6bc

長ったらしい辞書型の文字列が、固定長のすっきりした文字列になりました。

3. Nonceはどうやって決まるのか？

ブロックチェーンの特徴の１つが、Nonceと呼ばれる、一度限りの数値です。
「このNonceを求めるのが計算力を使う」と言われますが、具体的にはどうやっているのでしょうか？

これは、「前のブロックにNonceをつけてハッシュ化した値が、左〇〇桁が"0"になるようにする」というものになります。

ハッシュ化した後の値は、元の値が１文字異なっただけでも、まったく異なる値となるのが特徴です。

たとえば、上記ハッシュ値に「０」「１」の文字を加えたものを、それぞれハッシュ化してみましょう。

python

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)

console

aaa5ca23ad949385adb93ba58fab4ee3781f6b03acfa3a95398833f3abbfa4a2
789067aa346e4e04b135fcc8803ae963335935855ae94438ab27f7abe37b3b17

全く関連性のない２つの値となりました。

したがって、「左〇〇桁が"0"になるように」というのは、計算で予測できるものではなく、ひたすらNonceを変えて試す必要があります。

たとえば、左１桁が"0"になるNonceを求めてみましょう。

python

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)

console

9
0d9e49f8f1c68019698008a44270cb93879aa3f93e1a9bb41b8ccab1213982d5

Nonceが9となり、見事ハッシュ化した後の左１桁が"0"となりました。

4. なぜNonceを決めるのが難しい？

先ほどの例は、左１桁が"0"でしたが、次は左２桁が"0"となるようにしてみましょう。

python

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)

console

333 
0048434a5f9d2b5cad35a59341ec721df4835be2e3fdd2529a20f249adb41bb2

見事333回目に左２桁が"0"となりました。

ここまでは何の問題もないように見えます。

今度は、左５桁が"0"になるようにしてみましょう。
コードは省略しますが、結果として、

console

1543749
000003c5183ed8bda418eb426020b780ce6da109198cadf6365cfbc3dc803b9c

となり、1,543,749回の計算となりました。google colabのCPUでは、約2秒かかっています。

これが、左６桁となると、

console

7275800
00000070288462ba705c356feb366a9c44900f67bed523111953a5ab5075b3f

で、約11秒、

左７桁では、

console

600578735
0000000faf2edfd66768c6f76dd6c725a1e800ac8fe68dee23c321b537f1d461

で、なんと15分かかってしまいました。６億回(!)を超える計算をしています。

このように、桁数が増えると、途端に計算に時間がかかるようになります。
この左側を"0"にする桁数を、難易度(difficulty)といいます。

これが、「計算に大量の電力を消費する」と言われる所以です。
ブロックを追加、すなわちビットコインの報酬を得るのは、この計算を一番早く完了させた１人のみです。15分も計算して、報酬がゼロになるのは、やりきれないですね。

5. なぜ改竄ができない？

それでは、なぜこのような計算をさせるのでしょうか。
この計算は、取引に全く関係のない、無駄な計算となります。

しかし、逆説的に言えば、この計算の長さが改竄防止効果となるのです。

たとえば、次の４つのブロックを考えてみましょう。なお、参考にしたサイトに従い、コードではNonceをproofという名前のキーにしています。

python

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()

console

'f768e1ff0146b9fa0fd5e92d6b5be32e7fd4523f8bd59f9d36cef580e325552b'

となり、見事BLOCK[1]のprevious_hashの値と一致します。

また、この値にBLOCK[1]のNonceである47574599を付加してハッシュ値をとると、

python

hashlib.sha256(f'{BLOCK[1]["previous_hash"]}{BLOCK[1]["proof"]}'.encode()).hexdigest()

console

'0000001a2b41105bf60d1a0d680327f399904051f8eede53ace7d34c414ac469'

となり、左6桁が"0"となっています。
計算は省略しますが、BLOCK[2], BLOCK[3]も同様に確認できます。

それでは、ここで、BLOCK[1]の内容を改竄してみましょう。
具体的には、トランザクションのamountを5から10に変えてみます。

python

BLOCK[1] = {'index': 2, 
'timestamp': 1665577872.818851, 
'transactions': [{'sender': '8527147fe1f5426f9dd545de4b27ee00',
 'recipient': 'a77f5cdfa2934df3954a5c7c7da5df1f',
 'amount': 10}], 
'proof': 47574599,
 'previous_hash': 'f768e1ff0146b9fa0fd5e92d6b5be32e7fd4523f8bd59f9d36cef580e325552b'
}

このハッシュ値をとってみましょう。

console

85207769c4052306aced392cc5356efb6a51c80b3b450df1617fc131dac680bf

となり、BLOCK[2]のprevious_hashと異なってしまいます。
それでは、BLOCK[2]のprevious_hashを書きかえればよいのでしょうか。
実際に書き替えてみましょう。

python

BLOCK[2]["previous_hash"] = "85207769c4052306aced392cc5356efb6a51c80b3b450df1617fc131dac680bf"

これは大丈夫でしょうか。
ここで、BLOCK[2]のNonceが正しいか、もう一度確認してみましょう。

python

hashlib.sha256(f'{BLOCK[2]["previous_hash"]}{BLOCK[2]["proof"]}'.encode()).hexdigest()

console

'f612fffab04a9eca9654f1947787d6fd57b381d36a3bff4ecf922bc5446cf98c'

となると、"0"が6桁並ばなくなりました。
これの辻褄を合わせるために、もう一度Nonceを計算しなければならないようです。

python

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()

console

22176632

33秒かかって、Nonceを計算し直しました。

これで、BLOCK[2]の辻褄は合います。
ところが、Nonceとprevious_hashの値を変えたため、BLOCK[2]のハッシュ値もBLOCK[3]のprevious_hashと異なってしまいました。

また、つじつま合わせのためにBLOCK[3]のNonceを再計算する必要がありそうです。

python

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"])

console

15390054

24秒かかって、Nonceを再計算しました。

これで、新しいブロックをつくれば、改竄完成です。

ところが、ちょっと待ってください。

2回計算して、59秒経過している間に、他のマイナーが新しいブロックを追加してしまいました。
もはや、改竄したブロックが一番長いブロックではなくなり、承認される事はなくなってしまいました。

今回は４ブロックでdifficultyが６のサンプルでしたが、実際はもっと長いブロックで、difficultyも大きいので、より、改竄が非現実的となってきます。

これが、Proof of workの計算が、改竄防止につながる、という理屈になってくるわけです。