1.1 暗号学の基礎
ハッシュ
範囲は十分に大きい 2**256
以下の 3 つの特性を満たす必要があります:
collision resistance ハッシュ衝突耐性
hiding 入力情報を隠すことができる、つまりハッシュ結果から入力や入力の規則を逆推測できない
puzzle friendly マイニングの難易度を保証する、暴力的な総当たり以外に近道はない、pow プルーフ・オブ・ワーク
非対称暗号
取引時にプライベートキーで署名し、パブリックキーで検証します。
1.2 プライベートキーとアドレス
ランダムにプライベートキーを生成し、次に楕円曲線の乗法を通じて一連のパブリックキーを生成できます。
ビットコインはパブリックキーをアドレスとして直接使用せず、一連の変換を行います:
A = RIPEMD160(SHA256(K))
A: アドレス
K: パブリックキー
その後、base58 などのエンコーディングが行われます。要するに、パブリックキーとアドレスは一対一であり、パブリックキーからアドレスを計算できますが、その逆はできません。
1.3 コアデータ構造
ハッシュポインタ: H は構造体のアドレスを指すだけでなく、対象のハッシュ値も保存する必要があります。
ブロックチェーン
ハッシュポインタを使用したブロックの連結リストです。
ブロックヘッダーは 80 バイトであり、ブロックは取引を含むため、一般的にブロックはブロックヘッダーのサイズの数百倍から数千倍になります。
各ブロックヘッダーは常に前のブロックのハッシュ値を含むため、任意のブロックの変更は後続のブロックのハッシュ値を変更させます。したがって、最新のブロックのハッシュ値を確認することで、以前のすべてのブロックデータが改ざんされていないかどうかを確認できます。
現在のブロックのハッシュはマイナーが計算したものであり、ブロックチェーンシステム内部には存在しません。ノードが新しいブロックのブロードキャストを受け取ったとき、現在のブロックのハッシュを計算し、難易度に合致するかどうかを確認するだけで、マイナーが提供する必要はありません。しかし、アプリケーション層では効率的にデータを照会できるように、アプリケーション層でブロックハッシュからブロックデータへのインデックスを維持します。
創世ブロック：最初のブロック、ブロックチェーンの頭、コードにハードコーディングされています。
ブロックの高さ：創世ブロックは 0 であり、その後新しいブロックが生成されるたびに高さが 1 増加します。
マイニング：簡単に言えば、異なる Nonce（タイムスタンプやマークルルートも使用可能）を試行することで、現在のブロックハッシュ H (block header) <= target、つまり前に一定数の 0 が必要です（例えば 000000000000000000040b38097e0a61ef1ad31b184c908a738cfff013c094b2）。
マークルツリー
ブロック内の取引データを保存します。
バイナリツリーに似ていますが、2 つの点が異なります:
ハッシュポインタを使用
葉ノードのみが取引情報を保存し、中間ノードは左右の子ノードのハッシュのハッシュを保存
オンラインコースの知識ポイント:
第 2 節:
ビットコインは暗号通貨（crypto-currency）と呼ばれます。
ブロックチェーン上の内容はすべて公開されており、ブロックのアドレスや送金額を含みます。
ビットコインは主に暗号学の 2 つの機能を使用しています: 1. ハッシュ 2. 署名
- 暗号学で使用されるハッシュ関数は cryptographic hash function と呼ばれます：それには 2 つの重要な特性があります:
① collision（ここではハッシュ衝突） resistance: 例えば x≠y H (x)=H (y) 2 つの異なる入力が出力は等しい場合、これをハッシュ衝突と呼びます。これは避けられません、なぜなら入力空間は常に出力空間より大きいからです。x が与えられたとき、y を見つけるのは難しい、力任せの解法（brute-force）を除いて。
この特性の役割：メッセージのダイジェストを求めること。
例えばメッセージを m とすると、m のハッシュ値は H (m)=digest もし誰かが m の値を改ざんしようとし、H (m) を変えずに行うことはできません。
ハッシュ衝突は人為的に作り出すことはできず、検証もできません、これは実践的な経験に基づいています。
② hiding ハッシュ関数の計算プロセスは一方向であり、逆行できません（H (x) から x を導出できません）。hiding 特性の前提は入力空間が十分に大きく、分布が比較的均一であることです。十分に大きくない場合、一般的には x の後ろにランダム数を連結します、例えば H (x||nonce)。
この特性の役割: collision resistance と組み合わせて、digital commitment（デジタル封筒のデジタル同等物とも呼ばれます）を実現するために使用されます。
予測結果を入力 x として、ハッシュ値を計算し、ハッシュ値を公表し、hiding により人々はハッシュ値を知っているが予測値を知らない、最後に x を公表します。collision resistance の特性があるため、予測結果は改ざんできません。
暗号学で要求されるこの 2 つの特性に加えて、ビットコインで使用されるハッシュ関数には 3 つ目の特性があります:
③ puzzle friendly ハッシュ値の予算は事前に予測できません。もしハッシュ値が 00...0XX...X であれば、どの値がこの結果を計算しやすいかを事前に知ることはできず、やはり一つ一つ代入する必要があります。
ビットコインのマイニングプロセスは、実際には nonce を探すことです。nonce はブロックのヘッダー内の他の情報と一緒に入力として使用され、得られたハッシュ値は指定された目標予値以下でなければなりません。H (block header)≤target。block header はブロックヘッダーを指し、ブロックヘッダーには多くのフィールドがあり、その中の 1 つは設定可能なランダム数 nonce です。マイニングプロセスは、ブロックヘッダーが指定された範囲内にハッシュされるようにランダム数を試し続けることです。
puzzle friendly は、マイニングプロセスに近道がないことを意味します。出力値を指定された範囲に落とすためには、一つ一つ試すしかありません。したがって、このプロセスは作業証明（proof of work）としても機能します。
マイニングは難しく、検証は容易です（difficult to solve, but easy to verify）。
ビットコインで使用されるハッシュ関数は SHA-256（secure hash algorithm）であり、上記の 3 つの特性を満たしています。
ビットコインシステムでアカウントを開設する:
ローカルでパブリックキーとプライベートキーのペア（public key, private key）を作成します。これがアカウントです。パブリックキーとプライベートキーのペアは非対称暗号技術（asymmetric encryption algorithm）から来ています。
2 人間の情報のやり取りはキー（encryption key）を利用できます。A は情報を暗号化して B に送信し、B は受け取った後にキーを使って復号化します。暗号化と復号化に同じキーを使用するため、対称暗号と呼ばれます。前提は、通信の両者に安全にキーを配布できるチャネルがあることです。したがって、対称暗号の欠点は、キーの配布が不便であり、ネットワーク上で簡単に盗聴される可能性があることです。非対称キーは、1 対のキーを使用し、暗号化にはパブリックキーを、復号化にはプライベートキーを使用します。暗号化と復号化に使用されるのは受信者のパブリックキーとプライベートキーです。パブリックキーは秘密にする必要はなく、プライベートキーは秘密にする必要がありますが、プライベートキーはローカルに保存するだけで、相手に渡す必要はありません。パブリックキーは銀行口座に相当し、他の人が送金するにはパブリックキーを知っていればよく、プライベートキーはアカウントのパスワードに相当し、プライベートキーを知っていればアカウントの資金を移動できます。パブリックキーとプライベートキーは署名に使用されます。
もし A が B に 10 ビットコインを送金したい場合、A は取引をブロックチェーンに置きます。他の人はこの取引が A によって開始されたことをどうやって知るのでしょうか？これには A が自分のプライベートキーを使って取引に署名する必要があります。他の人がこの取引を受け取った後、A のパブリックキーを使って署名を検証します。署名にはプライベートキーを使用し、検証にはパブリックキーを使用します。使用されるのは同じ人のものです。アカウントを作成する際に同じパブリックキーが生成される可能性は非常に低いため、大量にアカウントを作成して他の人のアカウントを盗むことは不可能です。
プライベートキーを生成する際に良いランダムソース（a good source of randomness）があると仮定します。プライベートキーの生成はランダムであり、ランダムソースが悪いと同じプライベートキーとパブリックキーが生成される可能性があります。ビットコインで使用される署名アルゴリズムは、プライベートキーを生成する際に良いランダムソースが必要であり、その後の各署名時にも良いランダムソースが必要です。署名に使用されるランダムソースが悪い場合、プライベートキーが漏洩する可能性があります。
第 3 節：ビットコインのデータ構造
通常のポインタは、特定の構造体のメモリ内のアドレスを保存します。もし P が構造体を指すポインタであれば、P に保存されているのはその構造体のメモリ内の開始位置です。しかし、ハッシュポインタはアドレスを保存するだけでなく、その構造体のハッシュ値 H () も保存します。利点は、ハッシュ値からこのハッシュポインタを使用して、その構造体の位置を見つけるだけでなく、その構造体の内容が改ざんされていないかどうかを検出できることです。なぜなら、ハッシュ値を保存しているからです。
ビットコインの最も基本的な構造はブロックチェーンであり、ブロックチェーンは 1 つのブロックから構成される連結リストです。ブロックチェーンは通常の連結リストと何が違うのか:
① ハッシュポインタが通常のポインタの代わりに使用されています（B ブロックチェーンはハッシュポインタを使用した連結リストです）。
ブロックチェーンの最初のブロックは創世ブロック（genesis block）と呼ばれ、最後のブロックは最近生成されたブロック（most recent block）です。各ブロックは前のブロックを指すハッシュポインタを含んでいます。
1 つのブロックのハッシュポインタはどう計算されるのか：前のブロックの内容全体を、ハッシュポインタを含むすべてを結合してハッシュ値を取得します。この構造を通じて、tamper-evident log を実現できます。もし誰かが 1 つのブロックの内容を変更した場合、次のブロックのハッシュポインタは一致しなくなります。なぜなら、次のブロックのハッシュポインタは前のブロックの内容に基づいて計算されるからです。したがって、次のハッシュポインタも変更する必要があります。これを繰り返すことで、最後のハッシュ値も変わります（見た画像①）。
② 通常の連結リストは任意の要素を変更できますが、連結リストの他の要素には影響を与えません。しかし、ブロックチェーンは一つの要素を変更すると全体に影響を与えます。最後のハッシュ値を保存するだけで、ブロックチェーンが変更されたかどうかを判断できます。したがって、ビットコインはすべてのブロックの内容を保存する必要はなく、最近の数千のブロックだけを保持できます。以前のブロックを使用する必要がある場合は、システム内の他のノードにそのブロックを要求できます。悪意のあるノードがある場合、どうやって判断するのか？ここでハッシュ値の特性を使用します。以下のように:
他のノードがブロックを提供してくれた場合、それが正しいかどうかをどうやって判断するのか？そのハッシュ値を計算し、保持しているブロックのハッシュ値と比較すればよいのです。
ビットコインのもう一つの構造はマークルツリーです（見た画像②、最下層はデータブロック（data blocks）、上の 3 層の内部ノードはハッシュポインタ（hash pointers）、最上層はルートノードで、ルートノードのブロックもハッシュを取ることができ、ルートハッシュ（root hash）と呼ばれます）。
もう一つの概念はバイナリツリーです。
この構造の利点は、ルートハッシュ値を覚えておくだけで、ツリー内の任意の部分の変更を検出できることです。
それらの違いは、① ハッシュポインタが通常のポインタの代わりに使用されていることです。
ビットコインでは各ブロックがハッシュポインタで接続されており、各ブロックに含まれる取引はマークルツリーの形式で組織されており、最下行のデータブロックは実際には 1 つの取引です。各ブロックはブロックヘッダーとブロックボディ（block header, block body）の 2 つの部分に分かれています。ブロックヘッダーにはルートハッシュ値が含まれており、各ブロックに含まれるすべての取引から構成されるマークルツリーのルートハッシュ値がブロックのブロックヘッダー内に存在しますが、ブロックヘッダーには取引の具体的な内容はなく、ルートハッシュ値のみが含まれています。ブロックボディの中には取引のリストがあります。
マークルツリーの役割:
① マークル証明を提供します。
ビットコインのノードは 2 つのタイプに分かれます：フルノード（全ブロックの内容を保存し、ブロックヘッダーとボディの両方に取引の具体的な情報があります）とライトノード（例えばスマートフォンのビットコインウォレット）（ブロックヘッダーのみ）。
この時、問題が発生します：ライトノードに対して、特定の取引がブロックチェーンに書き込まれていることをどうやって証明するのか？
この時、マークル証明を使用する必要があります：取引が存在する位置（最下行のいずれかのブロック）を見つけ、このブロックが根ノードに至るまでのパスをマークル証明と呼びます。
見た画像 3: 最上行は小型のブロックチェーンであり、この図は 1 つのブロックのマークルツリーを示しており、最下行は含まれる取引です。仮にあるライトノードが図中の黄色の取引がマークルツリーに含まれているかどうかを知りたい場合、このライトノードは取引リストを含んでおらず、マークルツリーの具体的な内容も持っておらず、ルートハッシュ値のみを持っています。この時、ライトノードはフルノードにリクエストを送信し、黄色の取引がこのマークルツリーに含まれていることを証明するマークル証明を要求します。フルノードはこのリクエストを受け取った後、図中で赤色の 3 つのハッシュ値をライトノードに送信するだけで済みます。これらのハッシュ値を取得した後、ライトノードはローカルで図中の緑色の 3 つのハッシュ値を計算できます。まず黄色の取引のハッシュ値を計算し、その上の緑色のハッシュ値を取得し、隣の赤色のハッシュ値と結合して、上層ノードの緑色のハッシュ値を計算します。さらに結合して、上層の緑色のハッシュ値を計算し、結合して、全体の木のルートハッシュ値を計算できます。ライトノードはこのルートハッシュ値をブロックヘッダー内のルートハッシュ値と比較することで、黄色の取引がこのマークルツリーに含まれているかどうかを確認できます。
フルノードがマークル証明で提供するこれらのハッシュ値は、黄色の取引が存在するノードの位置から木の根までのパスで使用されるハッシュ値です。ライトノードはこのようなマークル証明を受け取った後、下から上に検証し、経路上のハッシュ値が正しいことを確認するだけです（検証時にはその経路のハッシュ値のみを検証でき、他の経路は検証できません。つまり、図中の赤色のハッシュ値は検証できません）。
このようにして安全ではないのでしょうか？もし黄色の取引が改ざんされた場合、そのハッシュ値が変更されると、隣の赤色のハッシュ値を調整して、それらを結合したハッシュ値を変えずに保つことができるのでしょうか？できません。collision resistance に基づいて、これは不可能です。
マークル証明は、マークルツリーに特定の取引が含まれていることを証明できるため、この証明はメンバーシップの証明（proof of membership）または包含の証明（proof of inclusion）とも呼ばれます。
ライトノードにとって、マークル証明を検証する複雑さはどのくらいですか？最下層に n 個の取引があると仮定すると、マークル証明の複雑さは θ(log (n)) です。
マークルツリーに特定の取引が含まれていないことを証明するにはどうすればよいですか？すなわち、非メンバーシップの証明（proof of non-membership）。木全体をライトノードに送信し、ライトノードが受け取った後、木の構造が正しいことを検証し、各層で使用されるハッシュ値が正しいことを確認することで、木の中にこれらの葉ノードのみが存在し、探している取引が含まれていないことを証明できます。この問題は、複雑さが線形の θ(n) であり、比較的鈍い方法です。
葉ノードの並び順にいくつかの要件を設けることができれば、例えば取引のハッシュ値でソートすることができます。各葉ノードは 1 回の取引であり、取引の内容を 1 回ハッシュし、ハッシュ値を小さい順に並べます。探している取引のハッシュ値を計算し、それがどの位置にあるかを確認します。例えば、3 番目と 4 番目の間にある場合、提供される証明は 3 番目と 4 番目の葉ノードが根ノードに向かって上がる必要があります。もしそのハッシュ値が正しい場合、最後に根ノードで計算されたハッシュ値も変更されていないことが確認できます。3 番目と 4 番目のノードが元のマークルツリーの中で隣接している点であるべきです。探している取引が存在する場合、それはこの 2 つのノードの間にあるはずです。しかし、それは現れないので、存在しないことが証明されます。その複雑さも対数形式であり、コストはソートする必要があります。ソートされたマークルツリーと呼ばれます。ビットコインではこのようなソートされたマークルツリーは使用されていません。なぜなら、ビットコインでは存在しない証明を行う必要がないからです。
この節では、ビットコインの 2 つの最も基本的な構造、ブロックチェーンとマークルツリーについて説明しました。これらはハッシュポインタを使用して構築されています。これらの他にも、ハッシュポインタは別の側面でも使用できます。
データ構造が循環していない（非循環連結リスト）限り、すべてのデータ構造はハッシュポインタで通常のポインタの代わりに使用できます。循環している場合、ハッシュ値を計算できず、固定されたハッシュ値のブロックを特定できないという問題があります。
ビットコインのコンセンサスプロトコル#
デジタル通貨と紙幣の違いは、複製できること、これを二重支出攻撃（double spending attack）と呼びます。
非中央集権通貨は 2 つの問題を解決する必要があります: ① デジタル通貨の発行 ② 取引の有効性を検証し、二重支出攻撃を防ぐこと。
答え: ① ビットコインの発行はマイニングによって決まります。
② ブロックチェーンのデータ構造に依存します。
ビットコインの発行者 A は鋳造権（createcoin）を持ち、10 ビットコインを発行するとします。A (10) は B と C にそれぞれ 5 個ずつ渡します → B (5) C (5) この取引には A の署名が必要で、A の同意を証明します（designed by A）。同時に、消費された 10 ビットコインがどこから来たのかを示す必要があります。
見た画像 4 の 2 番目のボックスの中のお金は、最初のボックス内の鋳造取引から来ています。
ビットコインシステムでは、各取引は入力と出力の 2 つの部分を含みます。入力部分はコインの出所を示し、出力部分は受取人のパブリックキーのハッシュを示します。
取引部分が比較的複雑な場合、C の通貨の出所は 2 番目と 3 番目のボックスで、明確に識別する必要があります。
図 4 は小型のブロックチェーンを構成しており、ここには 2 種類のハッシュポインタがあります。1 つのハッシュポインタは各ブロック間を接続し、それらを連結リストとして構成します。前に学んだのはこのハッシュポインタです。そして、この図にはもう 1 つのハッシュポインタがあります。それは前の取引の指し示すポインタで、コインの出所を示すために使用されます。なぜコインの出所を示す必要があるのか：コインが無から生成されたのではなく、記録があることを証明するためです。また、二重支出を防ぐためでもあります。
現在、2 番目のボックスで A から B への送金が行われます。この取引には A の署名と B のアドレスが必要です。ビットコインシステムで受取人のアドレスはパブリックキーから推算されます。例えば、B のアドレスは B のパブリックキーをハッシュし、いくつかの変換を経て得られます。
A はどうやって B のアドレスを知るのか？ビットコインシステムには相手のアドレスを照会する機能がなく、他のチャネルを通じて知る必要があります。例えば、ある電子商取引サイトがビットコイン支払いを受け入れている場合、そのアドレスやパブリックキーを公開することができます。
A は B のアドレスを知る必要がありますが、B は A の何かの情報を知る必要がありますか？B も実際には A のパブリックキーを知る必要があります。これは A の身分を示します。B だけでなく、すべてのノードが A のパブリックキーを知る必要があります。そして、署名はプライベートキーで署名し、パブリックキーで検証します（前の知識と混同しないように注意してください。暗号化は受信者のパブリックキーで暗号化し、プライベートキーで復号化します）。したがって、ブロックチェーン上の各ノードは独立して検証する必要があります。
では、A のパブリックキーをどうやって知ることができるのでしょうか？実際には取引の中に含まれています。入力時にはコインの出所だけでなく、パブリックキーも入力する必要があります。ここで安全の穴が生じます。もし B の仲間がこの取引を偽造した場合、実際には最初のボックスの鋳造取引の出力に A のパブリックキーのハッシュがあるため、2 番目のボックスの取引で A のパブリックキーが前のハッシュと一致する必要があります。
ビットコインシステムでは、前述の検証プロセスはスクリプトを実行することで実現されます。各取引の入力にはスクリプトの一部が含まれており、パブリックキーを提供するプロセスが含まれています。各取引の出力もスクリプトの一部であり、その合法性を検証するには、現在の取引の入力スクリプトと前の取引（コインの出所を提供する取引）の出力スクリプトを結合し、スムーズに実行できるかどうかを確認する必要があります。これがビットコインスクリプト（BitCoin Script）です。
この図は取引システムを簡略化したもので、実際には各ブロック（図中の各ボックスに対応する）は多くの取引を含むことができます。これらの取引はマークルツリーを構成します。各ブロックはブロックヘッダーとブロックボディに分かれています。
ブロックヘッダーにはブロックのマクロ情報が含まれています。例えば、ビットコインのどのバージョン（version）のプロトコルを使用しているか、ブロックチェーン内の前のブロックへのポインタ（hash of previous block header）、全体のマークルツリーのルートハッシュ値（merkle root hash）、そしてマイニングに関連する 2 つのフィールドがあります。1 つはマイニングの難易度目標予値（target）、もう 1 つはランダム数 nonce です。
ここでの target は、前述のように、ブロックヘッダー全体のハッシュがこの予値より小さくなる必要があることを示しています。つまり、H (block header)≤target。block header にはこの目標予値のエンコーディング（nBits）が保存されています。ここで注意が必要なのは、前のブロックのハッシュは前のブロックのブロックヘッダーのみを計算しているため、前に描いたように、1 つのブロックが別のブロックを指す矢印を描くのは正しくありません。そのため、一部の書籍では矢印が 1 つのブロックの上を指しています。ハッシュを取得する際は、ブロックヘッダーのすべての部分をハッシュします。
ブロックボディには取引リスト（transaction list）が含まれています。
前述の内容では、各ノードがすべての取引を検証する必要があることを簡略化しました。実際には、システム内のノードはフルノード（全ブロックの情報を保存し、すべての取引を検証します）とライトノード（ブロックヘッダーの情報のみを保存します）に分かれています。一般的に、ライトノードは独立して取引の合法性を検証できません。
例えば、取引が二重支出かどうかを判断する場合、ライトノードは以前の取引情報を保存していないため、検証できません。システム内の大多数のノードはライトノードであり、この授業の内容は主にフルノードに焦点を当てています。なぜなら、ライトノードはブロックチェーンの構築や維持に参加せず、ブロックチェーンの情報を利用していくつかのクエリを行うだけだからです。
ブロックチェーンの内容はどのようにブロックチェーンに書き込まれるのでしょうか？各ノード、各アカウントは取引を発行でき、取引はすべてのノードにブロードキャストされます。いくつかの取引は合法であり、いくつかは違法です。次のブロックにどの取引が書き込まれるべきか、どの順序で書き込むべきかを決定するのは誰でしょうか？各ノードが自分で決定できるのでしょうか？もし各人がローカルでブロックチェーンを維持するなら、ブロックチェーンの一貫性は保証されず、帳簿の内容は分散合意（distributed consensus）を得る必要があります。
以下のメモはビットコインのアプリケーションとの関係はあまりありませんが、理解のために役立ちます:
分散合意の簡単な例は分散ハッシュテーブル（distributed hash table）です。例えば、システム内に多くのマシンがあり、共同でグローバルなハッシュテーブルを維持します。
ここで合意を得る必要がある内容は何でしょうか？ハッシュテーブルに含まれるキーと値のペアです。もし誰かが自分のコンピュータにキーと値のペアを挿入した場合、'xiao' というペアが 12345 に対応します。つまり、'xiao'→12345 です。そうすると、他の人が別のコンピュータでそれを読むときにも、これを読み取ることができる必要があります。これがグローバルなハッシュテーブルです。
分散システムには多くの不可能な結論（impossibility result）があり、その中で最も有名なのは FLP です。この 3 つの文字は 3 人の専門家の名前の頭文字を取ったもので、彼らの結論は次の通りです：非同期（asynchronous）システムでは、（ネットワーク伝送の遅延に上限がない場合は非同期システムと呼ばれます）、たとえ 1 人のメンバーが問題を抱えていても（faulty）、合意を得ることは不可能です。
もう 1 つの有名な結論は CAP 定理です（CAP は分散システムの 3 つの望ましい特性、整合性（Consistency）、可用性（Availability）、分割耐性（Partition tolerance）を指します）。この理論の内容は、任意の分散システム、例えば分散ハッシュテーブルでは、この 3 つの特性のうち、最大で 2 つしか満たすことができないということです。もし前の 2 つの特性を望むなら、3 つ目の特性は得られません。
分散合意の有名なプロトコルは Paxos であり、このプロトコルは整合性を保証できます。つまり、最初の特性です。このプロトコルが合意に達した場合、その合意は必ず整合性があり、各メンバーが考える合意は同じです。しかし、ある状況では、このプロトコルは永遠に合意に達することができない可能性があります。この可能性は比較的小さいですが、客観的に存在します。
ビットコインのコンセンサスプロトコル（consensus in BitCoin）:
ビットコインのコンセンサスが解決すべき問題の 1 つは、悪意のあるノードが存在する可能性があることです。システム内の大多数のノードが良いと仮定すると、どのようにコンセンサスプロトコルを取得するのでしょうか？
最初の提案は投票です。まず、どのブロックが投票権を持つかを特定する必要があります。いくつかのメンバーシップには厳格な要件があります。この場合、投票に基づく提案は実行可能です。しかし、ビットコインシステムではアカウントを作成するのが非常に簡単で、1 人がパブリックキーとプライベートキーを生成しても他の人にはわかりません。送金時に他の人が初めて知ることになります。したがって、ある人がアカウントを無限に作成し、アカウントの総数の半分を超えると、制御権を得ることができます。これをシビル攻撃（sybil attack）と呼びます。したがって、投票方法は適切ではありません。
ビットコインアカウントはこの問題を巧妙に解決しました。アカウント数で投票するのではなく、計算能力に基づいて投票します。各ノードはローカルで候補ブロックを組み立て、合法的な取引をその中に入れ、さまざまな nonce 値を試し始めます。どれが不等式 H (block header)≤target の要件を満たすかを確認します。もしあるノードが要件を満たす nonce を見つけた場合、そのノードは記帳権を獲得します。
記帳権とは、ビットコインの帳簿に次のブロックを書き込む権利を指します。この nonce を見つけたノードだけが次のブロックを発表する権利を持ちます。他のノードがこのブロックを受け取った後、そのブロックの合法性を検証する必要があります。
例えば、括弧内のブロックヘッダーの内容が正しいかどうか；ブロックヘッダー内には nBits というフィールドがあり、実際には目標予値のエンコーディングをチェックします。nBits フィールドがビットコインプロトコルで規定された難易度要件に合致しているかどうか；その不等式が成立するかどうか。仮にすべての要件が満たされていると仮定し、次にブロックボディ内の取引リストをチェックし、各取引が合法であることを確認します: ① 合法的な署名が必要 ② 以前に使用されていないこと。もし 1 つでも要件が満たされていない場合、このブロックは受け入れられません。すべての条件が満たされていても、必ずしも受け入れられるわけではありません。
もし新しいブロックが生成された場合、どのようにして新しいブロックがどこに挿入されたかを知るのでしょうか？生成されたブロックのポインタに基づいています。問題が発生する可能性があります。図 5（第 4 ビデオの 65 分）では、これらの 2 つの取引は A から B への送金と、A から自分への送金を指しています。この場合、二重支出ではありません。取引が二重支出かどうかを判断するには、そのブロックが存在するブランチでコインが使用されていないかどうかを確認します。図のように、3 番目のブロックまでコインが使用されていない場合、この取引は合法です。この取引は合法ですが、最長の合法チェーン（longest valid chain）には含まれていません。これをフォーク攻撃（forking attack）と呼びます。したがって、受け取ったブロックは最長の合法チェーンを拡張する必要があります。
ブロックチェーンは通常の状況でもフォークが発生する可能性があります。2 つのノードが同時に記帳権を獲得する場合です。各ノードはローカルで自分が適切だと思うブロックを組み立て、その後さまざまな nonce を試します。もし 2 つのノードがほぼ同時に要件を満たす nonce を見つけた場合、両方のノードがブロックを発表でき、2 つの同じ長さのフォークが発生します。これらの 2 つは最長の合法チェーンであり、どちらを受け入れるべきでしょうか？ビットコインプロトコルでは、デフォルトで各ノードは最初に受け取ったものを受け入れます。したがって、異なるノードはネットワーク上の位置によって異なり、あるノードは新しく生成されたブロックの 1 つを最初に聞いた場合、そのブロックを受け入れます。他のノードは別のブロックを最初に聞いた場合、そのブロックを受け入れます。
ブロックを受け取ったかどうかをどうやって判断するのでしょうか？ビットコインプロトコルでは暗黙の承認（implicit consign）を使用しています。このブロックを下に拡張し続けると、その発表されたブロックを承認したことになります。例えば、新しく生成されたブロックの後にさらにブロックを拡張すると、発表されたこの新しいブロックを承認したことを示します。
同じ長さの一時的なフォークはしばらく維持され、最終的に 1 つのフォークが勝ちます。つまり、どのチェーンが新しいブロックを最初に生成したかが最長の合法チェーンになります。もう 1 つは孤児ブロック（orphan block）と呼ばれます。これらの 2 つの新しいブロックはそれぞれ引き寄せ合う可能性があり、2 つのブロックチェーンがどちらの計算能力が強いかを見ます。時には運が良い方が勝つこともあります。
記帳権を競う利点：最初に記帳権を獲得したノードは、ある程度の権限を持ち、どの取引を次のブロックに書き込むかを決定できます。しかし、これらは記帳権の競争の動機として設定されるべきではないため、巧妙にメカニズムが構築されています：ブロック報酬（block reward）。
ビットコインプロトコルでは、記帳権を獲得したノードが発表するブロック内に特別な取引を持つことができると規定されています：鋳造取引（coinbase transaction）。この取引では、一定数量のビットコインを発行できます。
ここで前述の問題①に戻ります。誰が通貨の発行を決定するのか？coinbase transaction はビットコインシステムで新しいビットコインを発行する唯一の方法であり、後の取引はビットコインの移転です。この取引はコインの出所を示す必要はありません。
では、どれだけのコインを作れるのでしょうか？ビットコインが最初に立ち上がったとき、発表された各ブロックは 50BTC（BTC はビットコインのシンボル）を生成できました。プロトコルでは、21 万ブロック後に初期のブロック報酬が半減し、25BTC になります。さらに 21 万ブロック後、再び半減します。
したがって、1 つのブロックが勝ち取られた場合、もう 1 つの無効なブロックが得たビットコインは無効です。他の誠実なブロックはそれを認めません。
ビットコインシステムで何の合意を得る必要があるのか？非中央集権の帳簿は合意を得る必要があります。誰が帳簿の内容を決定できるのでしょうか？記帳権を獲得したノードだけが書き込むことができます。どうやって記帳権を獲得するのか？それは pow を解くことです（マイニング）。計算能力に基づいて投票し、計算能力は 1 秒あたりに試すことができる nonce の数で表すことができます。では、シビル攻撃を防ぐにはどうすればよいのでしょうか？計算能力に基づいて投票し、アカウントをいくら作成しても、計算能力を強化することはできません。
ビットコインの記帳権を争うプロセスはマイニング（mining）と呼ばれ、ビットコインはデジタルゴールド（digital gold）と呼ばれ、記帳権を争うノードはマイナー（miner）と呼ばれます。
ビットコインシステムの実装#
ブロックチェーンは非中央集権の帳簿であり、ビットコインは取引ベースのこの帳簿モデル（transaction-based ledger）を使用しています。システム内では、各アカウントにいくらあるかは表示されません。
ビットコインシステムのフルノードは、UTXO（未使用取引出力）（まだ使われていない取引の出力）のデータ構造を維持する必要があります。ブロックチェーン上には多くの取引があり、一部の取引の出力はすでに使われているかもしれませんが、一部はまだ使われていません。すべて未使用の出力の集合を UTXO と呼びます。
1 つの取引には複数の出力がある場合があります。例えば、A が B に 5 ビットコインを送り、B がそれを使った場合、A は C に 3 ビットコインを送り、C は使っていない場合、この時 5 ビットコインは UTXO にはカウントされず、3 ビットコインはカウントされます。UTXO 集合の各要素は、出力を生成した取引のハッシュ値と、その取引内での出力の順序を示す必要があります。この 2 つの情報で UTXO 内の出力を特定できます。
UTXO 集合にはどのような役割がありますか？
二重支出を検出するためです。つまり、新しく発表された取引が合法であるかどうかを検出するためです。したがって、フルノードはメモリ内で UTXO というデータ構造を維持し、二重支出を迅速に検出できるようにします。
各取引は一部の出力を消費し、新しい出力を生成します。上の例を見てみると、B が使った 5 ビットコインは UTXO 内にはありませんが、もし彼が D に送金した場合、D がそれを使っていない限り、その 5 ビットコインは再び UTXO 内に保存されます。もし D が使わなければ、その情報は UTXO 内に永遠に保存されます。使いたくない場合もあれば、秘密鍵を失った場合もあります。
各取引には複数の入力がある場合もあれば、複数の出力がある場合もあります。すべての入力金額の合計は出力金額の合計と等しくなければなりません。つまり、total inputs=total outputs です。したがって、1 つの取引は複数のアドレスから来る可能性があり、複数の署名が必要です。
一部の取引では、total inputs が total outputs よりわずかに大きい場合があります。
例えば、入力が 1 ビットコインで、出力が 0.99 ビットコイン、残りの 0.01 ビットコインは取引手数料として、ブロックを発表したノードに渡されます。
ブロック報酬もマイニングの報酬として完全には機能しません。ブロックを発表したノードは、なぜあなたの取引をブロックにパッケージ化する必要があるのでしょうか？彼らはあなたの取引の合法性を検証する必要があり、取引が多い場合は帯域幅を多く占有し、ネットワークの伝播速度も遅くなります。したがって、ブロック報酬だけでは不十分です。
したがって、ビットコインシステムは 2 つ目のインセンティブメカニズムを設計しました：取引手数料（transaction fee）。つまり、あなたの取引をブロックにパッケージ化する際に、少しのチップを渡すということです。取引手数料は一般的に非常に小さく、簡単な取引には手数料がない場合もあります。
21 万ブロックを掘るのにどれくらいの時間がかかるのでしょうか？約 4 年です。ビットコインシステムの設計では、平均ブロック生成時間は 10 分であり、つまりシステム全体で平均 10 分ごとに新しいブロックが生成されます。
ビットコインの取引ベースのモデルに対して、対応するのはアカウントベースのモデル（account-based ledger）です。例えば、イーサリアムシステムです。このモデルでは、システムは各アカウントにいくらのコインがあるかを明示的に記録する必要があります。
ビットコインの取引ベースのモデルは、プライバシー保護性が高いです。欠点は、ビットコインの取引ではコインの出所を示す必要があるのに対し、アカウントベースのモデルではその必要がないことです。
図⑥（第 5 節ビデオ 16 分）では、1 つのブロックの例を示しています。
最初の行は、このブロックが 686 の取引を含んでいることを示しています。
2 行目：総出力 XXX ビットコイン
4 行目：総取引手数料（686 の取引の手数料の合計）
最下行：ブロック報酬（マイナーの主な動機）
5 行目：ブロックのシーケンス番号
6 行目：ブロックのタイムスタンプ
9 行目：マイニングの難易度（2016 ブロックごとにマイニングの難易度を調整し、出力時間を約 10 分に保ちます）
倒数第二行：マイニング時に試みたランダム数
右側：最初の行：このブロックヘッダーのハッシュ値
2 行目：前のブロックヘッダーのハッシュ値
（注意：ハッシュ値を計算する際はブロックヘッダーのみを計算します）
2 つのハッシュ値の共通点：前に一連の 0 があります。これは、設定された目標予値を 16 進数で表すと、前に長い一連の 0 があることを示しています。したがって、難易度要件を満たすブロックは、ブロックヘッダーのハッシュ値が長い一連の 0 を持つ必要があります。
4 行目：マークルルートは、このブロックに含まれる取引から構成されるマークルツリーのルートハッシュ値です。
図⑥（第 5 節ビデオ 20 分）ブロックヘッダーのデータ構造
最後の行: 32 ビットの符号なし整数。nonce は 2 の 32 乗の可能な値を持ちます。ビットコインの現在のマイニング状況では、2 の 32 乗の値をすべて試しても適切なものが見つからない可能性が高いです。では、どうすればよいのでしょうか？ブロックヘッダーのデータ構造には他にどのフィールドを調整できるのでしょうか？
図⑦ ブロックヘッダーの各フィールドの説明（第 5 ビデオ 21 分）
最初の行：ビットコインプロトコルのバージョン番号（変更できません）
2 行目：前のブロックのブロックヘッダーのハッシュ値（変更できません）
3 行目：マークルツリーのルートハッシュ値（変更可能）
4 行目：ブロック生成の時間（調整可能）ビットコインシステムは特に正確な時間を要求せず、一定の範囲内で調整できます。
5 行目：目標予値（エンコーディングされたバージョン）（プロトコルの要件に従って定期的に調整する必要があります）
6 行目：ランダム数
マイニング時にランダム数を変更するだけでは不十分で、ルートハッシュ値も変更できます。
図⑧（第 5 ビデオ 23 分）
鋳造取引には入力がなく、coinbase があり、任意の内容を書くことができます。デジタルコミットメントの中の commit のハッシュ値をここに書き込むこともできます。第一節で説明した株式市場の予測内容をここに書き込むこともできます。coinbase の内容は誰もチェックしないので、あなたの気持ちを書くこともできます。
このフィールドは私たちにとって何の役に立つのでしょうか？
図⑨（第 5 ビデオ 24 分）
これは最後のブロックヘッダーのルートハッシュ値に対応するマークルツリーであり、左下の取引は coinbase であり、そのフィールドを変更すると、そのハッシュ値が変化し、マークルツリーの構造に沿って上に伝わります。最終的にブロックヘッダーのルートハッシュ値が変化します（マークルルートはブロックヘッダーの一部です）。ブロックヘッダーの 4 バイトの nonce が不足している場合、他のバイトを使用することもできます。例えば、coinbase フィールドの最初の 8 バイトを extra nonce として使用することで、検索空間が 2 の 96 乗に増加します。
したがって、実際のマイニングでは、外側のループで coinbase フィールドの extra nonce を調整し、ブロックヘッダーのルートハッシュ値を計算した後、内側のループでヘッダー内の nonce を調整します。
図⑩（普通の送金取引の例）（第 5 ビデオ 26 分）
この取引には 2 つの入力と 2 つの出力があります。
左上：ここでの出力は実際には入力であり、以前の取引の出力を指します。
右上：ここでの出力はすべて未使用であり、UTXO に保存されていません。
右側の表の最初の行：入力の合計金額。
以下、出力の合計金額、両者の差額。
両方の表の下：入力と出力はスクリプトの形式で指定されていることがわかります。
ビットコインシステムで取引の合法性を検証するのは、input scripts と output script をペアにして実行することによって行われます。注意：図中の input scripts と output scripts をペアにするのではなく、これらの 2 つのスクリプトは 1 つの取引内のスクリプトです。同じ取引内の入力スクリプトと出力スクリプトをペアにするのではなく、ここでの入力スクリプトと前の取引の出力スクリプトをペアにします。もし入力出力スクリプトが結合され、スムーズに実行され、エラーが発生しなければ、その取引は合法です。
図 11 は、パズルを解くプロセスを示しています。
注意：ハッシュを求める際にはブロックヘッダーの内容のみが使用され、取引の具体的な情報はブロックヘッダー内にはありません。ブロックヘッダーにはマークルツリーのルートハッシュ値のみが含まれており、これにより取引が改ざんされていないことが保証されます。
マイニングプロセスでは、各 nonce を試すことはベルヌーイ試行（Bernoulli trial）として考えることができます。各ランダムなベルヌーイ試行はベルヌーイプロセスを構成します。その特性の 1 つは、無記憶性です。
各 nonce を試す成功の確率は非常に小さく、大量の実験を行う必要があります。この時、ポアソン過程をベルヌーイ過程の代わりに使用できます。私たちが本当に関心を持っているのは、システムの出力時間であり、出力時間は指数分布に従います。座標軸を描くことができ、縦軸は確率密度、横軸は出力時間（システム全体の出力時間であり、各マイナーの出力時間ではありません）。特定のマイナーにおいて、彼が次のブロックを掘る時間は、マイナーの計算能力がシステムの計算能力の何パーセントを占めるかによって決まります。
もしある人の計算能力がシステム全体の 1% を占めている場合、システムが 100 個のブロックを生成すると、そのうちの 1 つはその人が掘ったものになります。
指数分布も無記憶性を持っています。確率分布曲線の特性は、どこからでも切り取っても、残りの部分の曲線は元のものと同じであることです。例えば、すでに 10 分待っても誰も合法的なブロックを見つけていない場合、さらにどれくらい待つ必要があるのでしょうか？平均してまだ 10 分待つ必要があります。将来、どれくらいの時間を掘る必要があるかは、過去にどれくらいの時間を掘ったかとは関係ありません。このプロセスは progress free とも呼ばれます。
もし progress free がなければ、どのような現象が発生するのでしょうか？計算能力の強いマイナーは不釣り合いな利点を持つことになります。なぜなら、計算能力の強いマイナーは過去に多くの作業を行っており、過去に多くの不成功な nonce を試した後、後の nonce の成功確率が増加するからです。したがって、progress free はマイニングの公平性を保証します。
出力報酬はシステム内で新しいビットコインを生成する唯一の手段です。生成されたビットコインは幾何級数を構成します。21 万＊50+21 万＊25+21 万＊12.5+......=21 万＊50＊(1+1/2+1/4+......)=2100 万
ビットコインのパズルを解くことは、計算能力を競うこと以外には実際的な意味はありません。ビットコインの希少性は人為的に作られています。
マイニングの過程でパズルを解くこと自体には実際的な意味はありませんが、マイニングのプロセスはビットコインシステムの安全性を維持するために非常に重要です。マイニングは計算能力に基づく投票の有効な手段を提供します。大部分の計算能力が誠実なノードに掌握されている限り、システムの安全性が保証されます。
マイニング報酬は次第に小さくなり、難易度はますます高くなっていますが、これらの数年間、マイニングの競争はますます激化しています。なぜなら、ビットコインの価格が急上昇しているからです。最終的にブロック報酬が 0 になった場合、マイニングの動機はなくなるのでしょうか？そうではありません。なぜなら、取引手数料のインセンティブメカニズムがあるからです。
もし大部分の計算能力が誠実なマイナーに掌握されている場合、どのような安全保証を得られるのでしょうか？ブロックチェーンに書き込まれた取引がすべて合法であることを保証できるのでしょうか。マイニングは確率的な保証を提供します。次のブロックが誠実なマイナーによって発表される確率が高いと言えますが、記帳権が悪意のあるノードの手に落ちることは保証できません。
例えば、良いマイナーが計算能力の 90% を占め、悪いマイナーが 10% を占めているとします。この場合、10% の確率で記帳権が悪意のあるマイナーの手に落ちることになります。この時、どのような状況が発生するのでしょうか？
最初の問題を考えてみましょう：彼はコインを盗むことができるのでしょうか？他人のアカウントのお金を自分のものにすることができるのでしょうか？できません。なぜなら、他人の署名を偽造する方法がないからです。
もし M が悪意のある場合、彼は A のアカウントのお金を盗もうとし、A から M への取引を発表しますが、この取引には A の署名が必要です。M は記帳権を獲得しても、A のプライベートキーを知らないため、署名を偽造することはできません。
もし M が取引をブロックチェーンに強制的に書き込んだ場合、誠実なノードはこのブロックを受け入れません。なぜなら、それには違法な取引が含まれているからです。したがって、誠実なノードは前のブロックに沿って掘り続け、新しいブロックを生成して違法なブロックを置き換えます。他の誠実なブロックはこの合法なブロックに沿って掘り続けます。ビットコインの要件は正常な合法チェーンを拡張することであり、M が生成したブロックは合法ではないため、そのブロックは無効です。彼にとってのコストは非常に大きくなります。なぜなら、ブロック報酬がなくなり、お金を盗むこともできないからです。
次の問題：彼はすでに使ったコインを再び使うことができるのでしょうか（つまり二重支出）？もし彼が M→A の取引をブロック内に書き込み、記帳権を獲得した場合、別の取引を発表してそのお金を自分に戻すことができるのでしょうか？つまり M→M' です。同様に、これは明らかに二重支出です。誠実なノードはこのブロックを受け入れません。
彼がこのブロックを発表したい場合、M→A の取引が存在するブロックの前のブロックに連結する必要があります。注意：ブロックがどの位置に挿入されるかは、マイニング時に決定されます。なぜなら、設定されたブロックヘッダーには前のブロックヘッダーのハッシュを記入する必要があるからです。したがって、彼がそのブロックに挿入したい場合、最初から認定する必要があり、記帳権を獲得した後に認定するのではありません。
このように生成された 2 つのブロックチェーンは、どちらも合法です。図 12（第 5 ビデオ 56 分）を参照してください。他のノードがどのチェーンに沿って拡張するかを見て、最終的に 1 つが勝ち、もう 1 つが無効になります。
この攻撃の目的は何でしょうか？もし M→A の取引が何らかの不可逆的な外部効果を生じさせ、その後 M→M' で M→A の取引を巻き戻すことができれば、M は不当な利益を得ることができます。
例えば、オンラインショッピングの際、M が商品を購入し、そのウェブサイトがビットコイン支払いを受け入れる場合、M は取引を発起し、ウェブサイトにお金を送ります。ウェブサイトは取引がブロックチェーンに書き込まれたことを監視し、支払いが成功したと思い、商品を M に渡します。M が商品を受け取った後、再び取引を発起し、その支出のお金を自分に戻し、次にブロックを最長の合法チェーンに拡張します。この結果、商品を手に入れ、お金を戻すことができ、二重支出の目的を達成します。
この攻撃を防ぐ方法はありますか？もし M→A の取引が存在するブロックが最後のブロックでない場合、この攻撃の難易度は大幅に増加します。M→A の取引を巻き戻したい場合、前のブロックに挿入する必要があり、その後最長の合法チェーンを形成するために努力する必要があります。この難易度は非常に高いです。なぜなら、誠実なノードは生成したブロックに沿って拡張せず、合法なブロックに沿って掘り続けるからです。したがって、この攻撃を防ぐ方法は、いくつかのブロックを待つか、いくつかの確認を待つことです。
M→A の取引がブロックに書き込まれたばかりのとき、これを one confirmation と呼びます。この時、後に追加されたブロックは、順次 two confirmation、three confirmation と呼ばれます... ビットコインプロトコルでは、デフォルトで 6 つの確認を待つ必要があります。6 つの確認が得られた場合、M→A の取引は改ざんされないと認定されます。これにはどれくらいの時間がかかるのでしょうか？平均的なブロック生成時間は 10 分であるため、約 1 時間待つ必要があります。
ブロックチェーンは改ざん不可能な帳簿ですが、ブロックチェーンに書き込まれた内容は永遠に変更できないのでしょうか？上記の分析からわかるように、この分析は確率的な保証に過ぎません。ブロックチェーンに書き込まれた内容は、比較的容易に変更される可能性があります。一定の待機時間が経過した後、または後続のいくつかのブロックが確認された後、改ざんされる確率は大幅に低下します（指数的に低下します）。
実際には、ゼロ確認（その具体的な位置は第 5 ビデオ 62 分 26 秒で確認できます）という概念もあります。これは、送金取引が発表されたが、まだブロックチェーンに書き込まれていないことを意味します。つまり、M→A の取引が発表されたが、M→M' を含むブロックがまだ掘られていない場合です。
この概念は、オンラインショッピングの例で、支払い時に取引を発表し、電子商取引サイトに自分がすでにお金を送ったことを知らせることに相当します。電子商取引サイトはフルノードを実行するか、ブロックチェーン上の取引を監視するためにフルノードを委託します。取引を受け取った後、取引の合法性（合法的な署名があり、以前に使用されていないこと）を検証し、ブロックチェーンに書き込まれるのを待つ必要はありません。この操作はリスクが高いように聞こえます。取引が発表されたばかりで、まだブロックチェーンに書き込まれていないのです。実際には、ゼロ確認は現実の中で比較的普遍的に使用されています。なぜでしょうか？
この理由は 2 つあります:
① ビットコインプロトコルのデフォルト設定は