1.1 暗号学の基礎
ハッシュ
範囲は十分大きい 2**256
以下の三つの特性を満たす必要があります:
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 章:
ビットコインは暗号通貨と呼ばれています。
ブロックチェーン上の内容はすべて公開されており、ブロックのアドレスや送金額も含まれています。
ビットコインは主に暗号学の 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 です。マイニングプロセスは、block header がハッシュを取った後、指定された範囲内に収まるようにランダム数を試し続けることです。
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 () も保存する必要があります。利点は、ハッシュ値からこのハッシュポインタを使用して、その構造体の位置を見つけるだけでなく、その構造体の内容が改ざんされていないかを検出できることです。なぜなら、ハッシュ値を保存しているからです。
ビットコインの最も基本的な構造はブロックチェーンであり、ブロックチェーンは一つ一つのブロックで構成される連結リストです。ブロックチェーンと通常の連結リストの違いは次の通りです:
①ハッシュポインタが通常のポインタの代わりに使用されています (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 に基づいて、これは不可能です。
マークル証明は、マークルツリーに特定の取引が含まれていることを証明できるため、この証明はメンバーシップの証明または包含の証明と呼ばれます。
ライトノードにとって、マークル証明を検証する複雑さはどのくらいですか？最下層に n 個の取引があると仮定すると、マークル証明の複雑さは θ(log (n)) です。
マークルツリーに特定の取引が含まれていないことを証明するにはどうすればよいですか？つまり、非メンバーシップの証明です。木全体をライトノードに渡すことができます。ライトノードは受け取った後、木の構造が正しいことを検証し、各レイヤーで使用されるハッシュ値が正しいことを確認します。これにより、木の中にこれらの葉ノードのみが存在し、探している取引が含まれていないことを証明できます。問題は、その複雑さが線形 θ(n) であり、比較的鈍い方法です。
もし葉ノードの並び順にいくつかの要件を設けると、例えば取引のハッシュ値でソートすることができます。各葉ノードは 1 回の取引であり、取引の内容をハッシュして、ハッシュ値の小さい順に並べます。探している取引のハッシュ値を計算し、それがどの位置にあるべきかを確認します。例えば、3 番目と 4 番目の間にある場合、提供される証明は 3 番目と 4 番目の葉ノードが根ノードまで上がる必要があります。もしそのハッシュ値がすべて正しい場合、最後に計算されたルートノードのハッシュ値も変更されていないことが確認され、3 番目と 4 番目のノードが元のマークルツリー内で隣接していることが確認されます。探している取引が存在する場合、それはこの 2 つのノードの間にあるはずですが、存在しないため、存在しないことが証明されます。その複雑さも対数形式であり、コストはソートが必要です。ソートされたマークルツリーと呼ばれます。ビットコインではこのようなソートされたマークルツリーは使用されていません。なぜなら、ビットコインでは存在しない証明を行う必要がないからです。
この章では、ビットコインの 2 つの最も基本的な構造、ブロックチェーンとマークルツリーについて説明しました。これらはすべてハッシュポインタを使用して構築されています。これらの 2 つの他にも、ハッシュポインタは別の側面でも使用できます。
データ構造が循環していない限り（非循環連結リスト）、すべてのデータ構造はハッシュポインタで通常のポインタの代わりに使用できます。循環している場合、ハッシュ値を計算できず、固定されたハッシュ値のブロックを特定できないという問題が発生します。
ビットコインのコンセンサスプロトコル#
デジタル通貨と紙幣の違いは、複製できること、これを二重支出攻撃 (double spending attack) と呼びます。
非中央集権通貨は 2 つの問題を解決する必要があります: ①デジタル通貨の発行 ②取引の有効性を検証し、二重支出攻撃を防ぐこと。
答え: ①ビットコインの発行はマイニングによって決定されます。
②ブロックチェーンのデータ構造に依存します。
ビットコインの発行者 A は通貨発行権 (createcoin) を持ち、10 ビットコインを発行します。A (10) は B と C にそれぞれ 5 ビットコインずつ与えます → B (5) C (5) この取引には A の署名が必要で、A の同意を証明します。(A によって設計されています) 同時に、消費された 10 ビットコインがどこから来たのかを示す必要があります。
撮影した図 4 では、2 つ目のボックスの資金は最初のボックスの発行取引から来ています。
ビットコインシステムの各取引には、入力と出力の 2 つの部分が含まれています。入力部分はコインの出所を示し、出力部分は受取人の公開鍵のハッシュを示します。
一部の取引は比較的複雑であり、C の通貨の出所は 2 つ目と 3 つ目のボックスであり、明確に識別する必要があります。
図 4 は小型のブロックチェーンを構成しており、ここには 2 種類のハッシュポインタがあります。1 つのハッシュポインタは各ブロック間を接続し、それらを連結リストとして構成します。前に学んだのはこのハッシュポインタです。この図には、前の取引を指す 2 つ目のハッシュポインタもあり、コインの出所を示すために使用されます。なぜコインの出所を示す必要があるのか：コインが無から作られたのではなく、記録があることを証明するためであり、同時に二重支出を防ぐためです。
現在、2 つ目のボックスでの A から B への送金取引には、A の署名と B のアドレスが必要です。ビットコインシステムでの受取人のアドレスは公開鍵から推測されます。例えば、B のアドレスは B の公開鍵をハッシュしてからいくつかの変換を経て得られます。
A は B のアドレスをどうやって知るのか？ビットコインシステムには相手のアドレスを照会する機能がなく、他のチャネルを通じて知る必要があります。例えば、ある EC サイトがビットコインの支払いを受け入れている場合、そのアドレスや公開鍵を公開することができます。
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。ブロックヘッダーにはこの目標予値のエンコーディング (nBits) が保存されています。ここで注意が必要なのは、前のブロックのハッシュは前のブロックのブロックヘッダーのみを計算しているため、前に描いたように、1 つのブロックが別のブロックを指す矢印を描くのは正しくありません。したがって、一部の書籍では矢印が 1 つのブロックの上に指していることがあります。ハッシュを取得する際には、ブロックヘッダーのすべての部分をハッシュします。
ブロックボディには取引リスト (transaction list) があります。
前述の内容では、各ノードがすべての取引を検証する必要があると簡略化しましたが、実際にはシステム内のノードはフルノード (full node) とライトノード (light node) に分かれます。フルノードはブロックチェーンのすべての情報を保存し、各取引を検証するため、フルノードは完全に検証するノード (fully validating node) とも呼ばれます。ライトノードはブロックヘッダーの情報のみを保存し、一般的にライトノードは取引の合法性を独立して検証することができません。
例えば、取引が二重支出かどうかを確認する場合、ライトノードは以前の取引情報を保存していないため、検証できません。システム内のほとんどのノードはライトノードであり、この授業の内容は主にフルノードに焦点を当てています。なぜなら、ライトノードはブロックチェーンの構築と維持に参加せず、ブロックチェーンの情報を利用していくつかのクエリを行うだけだからです。
ブロックチェーンの内容はどのようにブロックチェーンに書き込まれるのでしょうか？各ノード、各アカウントは取引を発行でき、取引はすべてのノードにブロードキャストされます。いくつかの取引は合法であり、いくつかは違法です。次のブロックにどの取引が書き込まれるべきか、どの順序で書くべきかを誰が決定するのでしょうか？各ノードが自分で決定してもよいのでしょうか？もし各人がローカルでブロックチェーンを維持していたら、ブロックチェーンの一貫性は保証されず、帳簿の内容は分散コンセンサス (distributed consensus) を得る必要があります。
以下のメモはビットコインのアプリケーションとはあまり関係がなく、理解のためのものです:
分散コンセンサスの簡単な例は分散ハッシュテーブル (distributed hash table) です。例えば、システム内に多くのマシンがあり、共同でグローバルなハッシュテーブルを維持しています。
ここでコンセンサスを得る必要がある内容は何でしょうか？ハッシュテーブルに含まれるキーと値のペア (key value pair) です。もし誰かが自分のコンピュータにキーと値のペアを挿入した場合、'xiao' というペアが 12345 に対応する、つまり 'xiao'→12345 です。そうすると、他の人が別のコンピュータでこれを読んでも、同じように読み取れる必要があります。これがグローバルなハッシュテーブルです。
分散システムに関する多くの不可能性の結論 (impossibility result) がありますが、その中で最も有名なのは FLP です。この 3 つの文字は 3 人の専門家の名前の頭文字を取ったもので、彼らの結論は次の通りです：非同期 (asynchronous) システムでは、(ネットワーク伝送の遅延に上限がない場合は非同期システムと呼ばれます)、たとえ 1 人のメンバーが問題を抱えていても (faulty)、コンセンサスを得ることは不可能です。
もう一つの有名な結論は 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 を見つけて記帳権を獲得したノードだけが次のブロックを発表する権利を持ちます。他のノードがこのブロックを受け取った後、そのブロックの合法性を検証する必要があります。
例えば、括弧内の block header の内容が正しいかどうか；block header 内には nBits というフィールドがあり、実際には目標予値のエンコーディングで、nBits フィールドがビットコインプロトコルで規定された難易度要件に適合しているかどうかを確認します；この不等式が成立するかどうか。すべての要件が満たされていると仮定し、次に block body 内の取引リストを確認し、各取引が合法であることを検証します: ①合法的な署名が必要です ②以前に使用されていないこと。もし 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 つの分岐が勝ちます。つまり、どのチェーンが新しいブロックを生成するのが早いかによって、どちらが最長の合法チェーンになります。もう 1 つは孤児ブロック (orphan block) と呼ばれます。これら 2 つの新しいブロックはそれぞれ引き寄せられる可能性があり、2 つのブロックチェーンがどちらの計算力が強いか、時にはどちらの運が良いかによって勝ちます。
記帳権を競うことの利点：最初に記帳権を獲得したノードは一定の権限を持ち、次のブロックにどの取引を記載するかを決定できます。しかし、これらは記帳権の競争の動機として設定されるべきではないため、巧妙にブロック報酬 (block reward) というメカニズムが構築されました。
ビットコインプロトコルでは、記帳権を獲得したノードが発表したブロック内に特別な取引を持つことができると規定されています：鋳造取引。これにより、一定数量のビットコインを発行できます。
ここで前述の質問に戻ります: ①誰が通貨の発行を決定するのか？coinbase transaction コインベース取引はビットコインシステムで新しいビットコインを発行する唯一の方法であり、後の取引はビットコインの移転です。この取引はコインの出所を示す必要はありません。
では、どれだけのコインを作れるのでしょうか？ビットコインが最初に立ち上がったとき、発表された各ブロックは 50BTC (BTC はビットコインのシンボル) を生成できました。プロトコルでは、21 万ブロック後に初期ブロック報酬が半減し、25BTC になります。さらに 21 万ブロック後、再び半減します。
したがって、新しいブロックが勝利した場合、もう 1 つの無効なブロックが得たビットコインは無効になります。他の誠実なブロックはそれを認めません。
ビットコインシステムで何のコンセンサスを得る必要がありますか？非中央集権の帳簿はコンセンサスを得る必要があります。誰が帳簿の内容を決定できるのでしょうか？記帳権を獲得したノードだけが書き込むことができます。記帳権を得るには、pow を解決する必要があります (マイニング)。計算力で投票し、計算力は毎秒どれだけの nonce 値を試せるかで表現できます。では、シビル攻撃を防ぐにはどうすればよいでしょうか？計算力で投票することで、アカウントをいくら作成しても計算力を強化することはできません。
ビットコインの記帳権を争うプロセスはマイニング (mining) と呼ばれ、ビットコインはデジタルゴールド (digital gold) と呼ばれ、記帳権を争うノードはマイナー (miner) と呼ばれます。
ビットコインシステムの実装#
ブロックチェーンは非中央集権の帳簿であり、ビットコインは取引ベースのこの帳簿モデル (transaction-based ledger) を使用しています。システム内では各アカウントにいくらあるかは表示されません。
ビットコインシステムのフルノードは UTXO (unspent transaction output)(まだ使われていない取引の出力) というデータ構造を維持する必要があります。ブロックチェーン上には多くの取引があり、一部の取引の出力はすでに使われている可能性があり、一部はまだ使われていない可能性があります。すべての未使用の出力の集合を 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 分) は通常の送金取引の例です (第 5 章のビデオ 26 分)。
この取引には 2 つの入力と 2 つの出力があります。
左上：ここでの出力は実際には入力であり、以前の取引の出力を指します。
右上：ここでの出力はすべて未使用であり、UTXO に保存されていません。
右側の表の最初の行：入力の合計金額。
次に出力の合計金額、両者の差額。
両方の表の下：入力と出力はスクリプトの形式で指定されています。
ビットコインシステムで取引の合法性を検証する方法は、input scripts と output script をペアにして実行することです。注意：図中の input scripts と output scripts をペアにするのではなく、これらの 2 つのスクリプトは同じ取引のスクリプトです。同じ取引内の入力スクリプトと出力スクリプトをペアにするのではなく、ここでの入力スクリプトと前の取引の出力スクリプトをペアにします。もし入力出力スクリプトが結合され、スムーズに実行されてエラーが発生しなければ、その取引は合法です。
図 11 はパズルを解く過程です。
注意：ハッシュを求める際にはブロックヘッダーの内容のみを使用し、取引の具体的な情報はブロックヘッダーには含まれていません。ブロックヘッダーにはマークルツリーのルートハッシュ値のみが含まれており、これにより取引が改ざんされていないことが保証されます。
マイニングプロセスでは、各 nonce を試すことはベルヌーイ試行 (Bernoulli trial) として考えることができます。各ランダムなベルヌーイ試行はベルヌーイプロセスを構成します。その特性の 1 つは無記憶性です。
各 nonce を試す成功の確率は非常に小さく、大量の実験が必要です。この時、ポアソン過程を使用してベルヌーイ過程を代替できます。私たちが本当に関心を持っているのはシステムの出力時間であり、出力時間は指数分布に従います。座標軸を描くことができ、縦軸は確率密度、横軸は出力時間 (システム全体の出力時間であり、各マイナーの出力時間ではありません)。具体的に各マイナーに関して言えば、次のブロックを掘る時間はマイナーの計算力がシステムの計算力の何パーセントを占めるかによって決まります。
もしある人の計算力がシステム全体の 1% を占めている場合、システムが 100 個のブロックを生成すると、そのうち 1 つのブロックはその人が掘ったものになります。
指数分布も無記憶性を持っています。確率分布曲線の特徴は、どこから切り取っても、残りの部分の曲線は元のものと同じであることです。例えば、すでに 10 分待っても誰も合法的なブロックを見つけていない場合、さらにどれくらい待つ必要があるのでしょうか？平均してまだ 10 分待つ必要があります。将来どれくらいの時間を掘る必要があるかは、過去にどれくらいの時間を掘ったかとは関係ありません。このプロセスは進捗フリー (progress free) とも呼ばれます。
もし進捗フリーがなければ、どのような現象が発生するでしょうか？計算力の強いマイナーは不釣り合いな利点を持つことになります。なぜなら、計算力の強いマイナーは過去により多くの作業を行っており、過去に多くの試行を行った後、次の nonce が成功する確率が増加するからです。したがって、進捗フリーはマイニングの公平性を保証します。
出力報酬はシステム内で新しいビットコインを生成する唯一の手段です。生成されたビットコインは幾何級数を構成します。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→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' を含むブロックはまだ掘られていません。
この概念は、オンラインショッピングの例において、支払い時に送金取引を発表し、EC サイトに自分がすでにお金を送ったことを知らせることに相当します。EC サイトはフルノードを運営するか、フルノードを委託してブロックチェーン上の取引を監視します。取引を受け取った後、合法性を検証する必要があります（合法的な署名があり、以前に使用されていないこと）。ブロックチェーンに書き込まれるのを待つ必要はありません。この操作はリスクが高いように思えます。取引が発表されたばかりで、まだブロックチェーンに書き込まれていないのです。実際には、ゼロ確認は実際に比較的普及しています。なぜでしょうか？
この中には 2 つの理由があります:
①ビットコインプロトコルのデフォルト設定は、ノードが最初に聞いた取引を受け入れることです。したがって、ゼロ確認の位置で、M→A のノードが受け取った後、M→M' の取引を発表すると、誠実なノードは受け入れない可能性が高いです。
②多くのショッピングサイトでは、支払いが成功してから発送までに一定の時間間隔があります。つまり、処理時間があるということです。
前述の質問に戻ります：もし悪意のあるノードが記帳権を獲得した場合、彼は何を悪事を働くことができるのでしょうか？特定の合法的な取引をブロックチェーンに書き込まないように故意にすることができるのでしょうか？つまり、発表されたブロックが特定の取引をブロックに含まないようにすることができます。これは可能です。
ビットコインプロトコルは、記帳権を獲得したノードが必ずしもその取引をブロックに発表する必要があるとは規定していません。しかし、このような状況が発生しても問題はありません。なぜなら、これらの合法的な取引は必ず次のブロックに書き込まれるからです。必ず誠実なノードがこれらの取引を発表することを望んでいます。
実際、ブロックチェーンが正常に機能している場合でも、合法的な取引が含まれない状況が発生することがあります。これは、取引の数が多すぎるためです。ビットコインプロトコルでは、各ブロックのサイズに制限があり、最大で 1 メガバイトを超えることはできません。した