ブロックチェーンのProof of WorkをPythonでやってみた

最近理解したので、忘備録も兼ねて投稿します。
ブロックチェーンの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:python
block = {
    "index":2,
    "timestamp":1665386454.385751,
    "transactions":[{"sender":"8527147fe1f5426f9dd545de4b27ee00",
    "recipient":"a77f5cdfa2934df3954a5c7c7da5df1f",
    "amount":5,}],
    "proof":8719932,
    "previous_hash":'06e3866abfc84d40057e9e27109c9945cb62e065772f60a6eb4f58db2df0f92b',
    }
```
これは、辞書型なので、`json.dumps` で文字列型に変換します。
```python: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: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: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: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: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: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: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: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:python
BLOCK[2]["previous_hash"] = "85207769c4052306aced392cc5356efb6a51c80b3b450df1617fc131dac680bf"
```


これは大丈夫でしょうか。
ここで、`BLOCK[2]`の`Nonce`が正しいか、もう一度確認してみましょう。
```python:python
hashlib.sha256(f'{BLOCK[2]["previous_hash"]}{BLOCK[2]["proof"]}'.encode()).hexdigest()
```
```:console
'f612fffab04a9eca9654f1947787d6fd57b381d36a3bff4ecf922bc5446cf98c'
```

となると、"0"が6桁並ばなくなりました。
これの辻褄を合わせるために、もう一度`Nonce`を計算しなければならないようです。
```python: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: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の計算が、改竄防止につながる、という理屈になってくるわけです。