ビットコイン：ピアツーピア電子キャッシュシステム

Abstract

純粋なpeer-to-peerの電子キャッシュにより、金融機関を介さずに一方の当事者からもう一方へ直接オンライン決済を行うことが可能になる。デジタル署名はその解決策の一部を提供するが、二重支払いを防ぐために信頼できる第三者が依然として必要であれば、主な利点は失われてしまう。我々はpeer-to-peerネットワークを用いた二重支払い問題への解決策を提案する。このネットワークは、トランザクションをhashベースのproof-of-workの連鎖にhash化することでタイムスタンプを付与し、proof-of-workをやり直さない限り変更できない記録を形成する。最長のチェーンは、目撃されたイベントの順序の証明としてのみならず、それが最大のCPUパワーのプールから生まれたことの証明としても機能する。CPUパワーの過半数がネットワークへの攻撃に協力していないノードによって制御されている限り、それらのノードが最長のチェーンを生成し、攻撃者を凌駕する。ネットワーク自体は最小限の構造しか必要としない。メッセージはベストエフォートで配信され、ノードは自由にネットワークから離脱・再参加でき、不在中に何が起こったかの証明として最長のproof-of-workチェーンを受け入れる。

Introduction

インターネット上の商取引は、電子決済を処理する信頼できる第三者として機能する金融機関にほぼ全面的に依存するようになった。このシステムはほとんどのトランザクションに対して十分に機能しているが、信頼ベースモデルに固有の弱点を依然として抱えている。金融機関は紛争の仲裁を避けることができないため、完全に不可逆なトランザクションは実質的に不可能である。仲裁コストはトランザクションコストを増大させ、実用的な最小トランザクションサイズを制限し、小規模なカジュアルトランザクションの可能性を断つ。さらに、不可逆なサービスに対して不可逆な支払いができないことによる、より広範なコストも存在する。取消しの可能性がある限り、信頼の必要性が広がる。商人は顧客を警戒し、本来不要な情報まで求めなければならない。一定割合の詐欺は不可避として受け入れられている。これらのコストと支払いの不確実性は、物理的な通貨を使用すれば対面で回避できるが、信頼できる当事者なしに通信チャネルを通じて支払いを行うメカニズムは存在しない。

必要とされているのは、信頼ではなく暗号学的証明に基づく電子決済システムであり、信頼できる第三者を必要とせずに任意の二者が直接取引できるようにするものである。計算上取消しが実質的に不可能なトランザクションは売り手を詐欺から保護し、日常的なエスクローメカニズムで買い手を容易に保護できる。本論文では、peer-to-peer分散タイムスタンプサーバーを用いてトランザクションの時系列順序の計算的証明を生成することで、二重支払い問題への解決策を提案する。このシステムは、正直なノードが協力する攻撃者ノードの集団よりも多くのCPUパワーを集合的に制御している限り安全である。

Transactions

我々は電子コインをデジタル署名のチェーンとして定義する。各所有者は、前のトランザクションのhashと次の所有者の公開鍵にデジタル署名し、これらをコインの末尾に追加することで、次の所有者にコインを転送する。受取人は署名を検証することで所有権のチェーンを検証できる。

もちろん問題は、受取人が所有者の一人がコインを二重支払いしていないことを検証できないことである。一般的な解決策は、すべてのトランザクションの二重支払いをチェックする信頼できる中央機関、つまり造幣局を導入することである。各トランザクションの後、コインは新しいコインを発行するために造幣局に返却されなければならず、造幣局から直接発行されたコインのみが二重支払いされていないと信頼される。この解決策の問題は、銀行と同様に、すべてのトランザクションがそこを経由しなければならず、貨幣システム全体の運命が造幣局を運営する企業に依存することである。

我々は、受取人が以前の所有者がそれ以前のトランザクションに署名していないことを知る方法を必要とする。我々の目的においては、最も早いトランザクションが有効であり、それ以降の二重支払いの試みは問題としない。トランザクションが存在しないことを確認する唯一の方法は、すべてのトランザクションを認識することである。造幣局ベースのモデルでは、造幣局がすべてのトランザクションを認識し、どれが最初に到着したかを決定していた。信頼できる当事者なしにこれを達成するためには、トランザクションは公開で通知されなければならず[^1]、参加者がトランザクションの受信順序の単一の履歴に合意するシステムが必要である。受取人は、各トランザクションの時点で、ノードの過半数がそれを最初に受信したものとして合意したことの証明を必要とする。

Timestamp Server

我々が提案する解決策はタイムスタンプサーバーから始まる。タイムスタンプサーバーは、タイムスタンプを付与するアイテムのブロックのhashを取得し、新聞やUsenetへの投稿のようにそのhashを広く公開することで機能する[^2] [^3] [^4] [^5]。タイムスタンプは、hashに含まれるためにそのデータがその時点で存在していたことを明らかに証明する。各タイムスタンプはそのhash内に前のタイムスタンプを含み、チェーンを形成し、追加のタイムスタンプごとにそれ以前のものを強化する。

Proof-of-Work

peer-to-peerベースで分散タイムスタンプサーバーを実装するには、新聞やUsenetの投稿ではなく、Adam BackのHashcash [^6]に類似したproof-of-workシステムを使用する必要がある。proof-of-workは、hash化した際に（例えばSHA-256で）hashが一定数のゼロビットで始まる値を探索することを含む。必要な平均作業量はゼロビット数に対して指数関数的であり、単一のhashを実行することで検証できる。

我々のタイムスタンプネットワークでは、ブロック内のnonceをインクリメントし、ブロックのhashに必要なゼロビットを与える値が見つかるまで繰り返すことでproof-of-workを実装する。proof-of-workを満たすためにCPUの労力が費やされると、その作業をやり直さない限りブロックを変更することはできない。後続のブロックがその後にチェーンされるため、ブロックを変更するための作業にはそれ以降のすべてのブロックをやり直すことが含まれる。

proof-of-workは、多数決における代表性の決定問題も解決する。もし多数決が1つのIPアドレスにつき1票に基づいていたならば、多数のIPを割り当てられる者によって覆される可能性がある。proof-of-workは本質的に1つのCPUにつき1票である。多数決は最長のチェーン、すなわち最大のproof-of-work労力が投入されたチェーンによって表される。CPUパワーの過半数が正直なノードによって制御されていれば、正直なチェーンが最も速く成長し、競合するいかなるチェーンも凌駕する。過去のブロックを改変するには、攻撃者はそのブロックとそれ以降のすべてのブロックのproof-of-workをやり直し、さらに正直なノードの作業に追いつき追い越さなければならない。遅い攻撃者が追いつく確率は、後続のブロックが追加されるにつれて指数関数的に減少することを後に示す。

ハードウェア速度の向上と、時間の経過に伴うノード運用への関心の変動を補うため、proof-of-workの難易度は1時間あたりの平均ブロック数を目標とする移動平均によって決定される。生成速度が速すぎる場合、難易度は上昇する。

Network

ネットワークを運用する手順は以下の通りである：

1. 新しいトランザクションがすべてのノードにブロードキャストされる。
2. 各ノードが新しいトランザクションをブロックに収集する。
3. 各ノードがそのブロックに対する困難なproof-of-workの発見に取り組む。
4. ノードがproof-of-workを発見すると、そのブロックをすべてのノードにブロードキャストする。
5. ノードは、ブロック内のすべてのトランザクションが有効であり、まだ使用されていない場合にのみ、そのブロックを承認する。
6. ノードは、承認されたブロックのhashを前のhashとして使用し、チェーンの次のブロックの作成に取り組むことで、そのブロックの承認を表明する。

ノードは常に最長のチェーンを正しいものとみなし、その延長に取り組み続ける。2つのノードが異なるバージョンの次のブロックを同時にブロードキャストした場合、一部のノードはどちらか一方を先に受信する可能性がある。その場合、ノードは最初に受信した方に取り組むが、もう一方のブランチがより長くなった場合に備えて保存しておく。次のproof-of-workが発見され、一方のブランチがより長くなった時点で決着がつき、もう一方のブランチで作業していたノードはより長い方に切り替える。

新しいトランザクションのブロードキャストは、必ずしもすべてのノードに到達する必要はない。多くのノードに到達すれば、やがてブロックに取り込まれる。ブロックのブロードキャストもメッセージの欠落に対して寛容である。ノードがブロックを受信しなかった場合、次のブロックを受信した際に欠落に気づき、そのブロックを要求する。

Incentive

慣例により、ブロック内の最初のトランザクションは、ブロックの作成者が所有する新しいコインを生成する特別なトランザクションである。これはノードがネットワークを支援するインセンティブを追加し、発行する中央機関が存在しないため、コインを流通させる初期分配の方法を提供する。一定量の新しいコインの着実な追加は、金鉱夫が資源を費やして金を流通に追加することに類似している。我々の場合、費やされるのはCPU時間と電力である。

インセンティブはトランザクション手数料でも賄うことができる。トランザクションの出力値がその入力値よりも小さい場合、差額はそのトランザクションを含むブロックのインセンティブ値に加算されるトランザクション手数料となる。所定の数のコインが流通に入った後、インセンティブは完全にトランザクション手数料に移行し、完全にインフレーションフリーとなることができる。

インセンティブはノードが正直であり続けることを促す助けとなりうる。貪欲な攻撃者がすべての正直なノードよりも多くのCPUパワーを集めることができた場合、その力を使って自身の支払いを取り戻す詐欺を行うか、新しいコインの生成に使用するかを選択しなければならない。ルールに従って行動する方がより収益性が高いと判断するはずであり、そのようなルールは他の全員を合わせたよりも多くの新しいコインを彼に有利に与えるのであって、システムと自身の富の正当性を損なうよりもましである。

Reclaiming Disk Space

コイン内の最新のトランザクションが十分な数のブロックの下に埋まれば、それ以前の使用済みトランザクションはディスクスペースを節約するために破棄できる。ブロックのhashを壊さずにこれを実現するため、トランザクションはMerkle Tree [^7] [^2] [^5]にhash化され、ルートのみがブロックのhashに含まれる。古いブロックはツリーの枝を切り落とすことでコンパクトにできる。内部のhashは保存する必要がない。

トランザクションを含まないブロックヘッダーは約80バイトとなる。ブロックが10分ごとに生成されると仮定すると、80バイト * 6 * 24 * 365 = 年間4.2MBとなる。2008年時点でコンピュータシステムが一般的に2GBのRAMを搭載して販売されており、ムーアの法則が年間1.2GBの現在の成長を予測していることを考えると、ブロックヘッダーをメモリに保持しなければならないとしてもストレージは問題とはならない。

Simplified Payment Verification

完全なネットワークノードを稼働させずに支払いを検証することが可能である。ユーザーは最長のproof-of-workチェーンのブロックヘッダー">ブロックヘッダーのコピーのみを保持すればよく、最長のチェーンを持っていると確信するまでネットワークノードに問い合わせることで取得でき、トランザクションをそれがタイムスタンプされたブロックにリンクするMerkleブランチを取得できる。ユーザー自身がトランザクションを確認することはできないが、チェーン内の場所にリンクすることで、ネットワークノードがそれを承認したことを確認でき、その後に追加されたブロックがネットワークがそれを承認したことをさらに裏付ける。

そのため、正直なノードがネットワークを制御している限り検証は信頼できるが、ネットワークが攻撃者に圧倒された場合はより脆弱になる。ネットワークノードはトランザクションを自ら検証できるが、この簡易的な方法は、攻撃者がネットワークを圧倒し続けられる限り、攻撃者が捏造したトランザクションに欺かれる可能性がある。これに対する防御戦略の一つは、ネットワークノードが無効なブロックを検出した際にアラートを受け入れ、ユーザーのソフトウェアに完全なブロックとアラートされたトランザクションをダウンロードさせ、不整合を確認することである。頻繁に支払いを受ける企業は、より独立したセキュリティと迅速な検証のために、おそらく自社のノードを運用することを望むだろう。

Combining and Splitting Value

コインを個別に扱うことは可能であるが、送金の1セントごとに別々のトランザクションを作成するのは扱いにくい。価値の分割と結合を可能にするため、トランザクションには複数の入力と出力が含まれる。通常、より大きな前のトランザクションからの単一の入力か、より小さな金額を結合する複数の入力があり、出力は最大で2つ：支払い用の1つと、もしあればお釣りを送信者に返す1つである。

あるトランザクションが複数のトランザクションに依存し、それらのトランザクションがさらに多くのトランザクションに依存するファンアウトは、ここでは問題にならないことに注意すべきである。トランザクションの完全な独立したコピーを抽出する必要は決してない。

Privacy

従来の銀行モデルは、関係当事者と信頼できる第三者に情報へのアクセスを制限することで一定レベルのプライバシーを実現している。すべてのトランザクションを公開で通知する必要性はこの方法を不可能にするが、別の場所で情報の流れを断ち切ることでプライバシーを維持することは可能である：公開鍵を匿名に保つことによってである。誰かが他の誰かに金額を送金していることは公開で見ることができるが、そのトランザクションを個人に結びつける情報はない。これは、証券取引所が公開する情報レベルに類似しており、個々の取引の時間と規模、すなわち「ティッカーテープ」は公開されるが、当事者が誰であるかは明かされない。

追加のファイアウォールとして、各トランザクションに新しいキーペアを使用し、共通の所有者にリンクされることを防ぐべきである。複数入力のトランザクションでは、一部のリンクは依然として不可避であり、それらの入力が同一の所有者のものであったことが必然的に明らかになる。リスクは、鍵の所有者が明らかになった場合、リンクによって同一の所有者に属する他のトランザクションが明らかになる可能性があることである。

Calculations

攻撃者が正直なチェーンよりも速く代替チェーンを生成しようとするシナリオを考える。これが達成されたとしても、無から価値を創造したり、攻撃者に属さない金銭を奪うなど、システムが恣意的な変更に開かれるわけではない。ノードは無効なトランザクションを支払いとして受け入れず、正直なノードはそれを含むブロックを決して受け入れない。攻撃者は、自分自身のトランザクションの1つを変更して最近使った金銭を取り戻すことしか試みることができない。

正直なチェーンと攻撃者のチェーンの競争は二項ランダムウォークとして特徴づけることができる。成功事象は正直なチェーンが1ブロック延長されリードが+1増加すること、失敗事象は攻撃者のチェーンが1ブロック延長され差が-1縮小することである。

攻撃者が所定の不足分から追いつく確率は、ギャンブラーの破産問題に類似している。無限の信用を持つギャンブラーが不足分から出発し、損益分岐点に達しようと無限の試行を行うと仮定する。損益分岐点に達する確率、つまり攻撃者が正直なチェーンに追いつく確率は以下のように計算できる[^8]：

p = probability an honest node finds the next block
q = probability the attacker finds the next block
q = probability the attacker will ever catch up from z blocks behind
``````

\[
qz =
\begin{cases}
1 & \text{if } p \leq q \\
\left(\frac{q}{p}\right) z & \text{if } p > q
\end{cases}
\]

p  qという我々の仮定の下では、攻撃者が追いつかなければならないブロック数が増加するにつれて確率は指数関数的に低下する。不利な状況において、早い段階で幸運にも前進できなければ、遅れるにつれてその可能性は極めて小さくなる。

次に、新しいトランザクションの受取人が、送信者がトランザクションを変更できないと十分に確信するまでにどのくらい待つ必要があるかを考える。送信者は、受取人にしばらくの間支払ったと信じさせた後、一定時間の経過後に自分自身への支払いに切り替えたい攻撃者であると仮定する。受信者はそれが起こった時にアラートを受けるが、送信者はそれが手遅れであることを望んでいる。

受信者は新しいキーペアを生成し、署名の直前に送信者に公開鍵を渡す。これにより、送信者が十分先行できるほどの幸運を得るまで継続的にブロックのチェーンを事前に準備し、そのタイミングでトランザクションを実行することを防ぐ。トランザクションが送信されると、不正な送信者は自分のトランザクションの代替バージョンを含む並行チェーンを秘密裏に作成する作業を開始する。

受取人はトランザクションがブロックに追加され、その後にzブロックがリンクされるまで待つ。攻撃者が正確にどの程度進んでいるかは分からないが、正直なブロックがブロックあたりの平均予想時間を要したと仮定すると、攻撃者の潜在的な進捗は期待値が次のPoisson分布となる：

\[
\lambda = z\frac{q}{p}
\]

攻撃者が今なお追いつける確率を求めるために、攻撃者が到達しうる各進捗量のPoisson密度に、その地点から追いつける確率を乗じる：

\[
\sum_{k=0}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \cdot \left\{
\begin{array}{cl}
\left(\frac{q}{p}\right)^{(z-k)} & \text{if } k \leq z \\
1 & \text{if } k > z
\end{array}
\right.
\]

分布の無限の裾を合計することを避けるために整理すると...

\[
1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left(1-\left(\frac{q}{p}\right)^{(z-k)}\right)
\]

C言語コードに変換すると...

```c
#include math.h

double AttackerSuccessProbability(double q, int z)
{
    double p = 1.0 - q;
    double lambda = z * (q / p);
    double sum = 1.0;
    int i, k;
    for (k = 0; k = z; k++)
    {
        double poisson = exp(-lambda);
        for (i = 1; i = k; i++)
            poisson *= lambda / i;
        sum -= poisson * (1 - pow(q / p, z - k));
    }
    return sum;
}

いくつかの結果を実行すると、確率がzに対して指数関数的に低下することが分かる。

q=0.1
z=0 P=1.0000000
z=1 P=0.2045873
z=2 P=0.0509779
z=3 P=0.0131722
z=4 P=0.0034552
z=5 P=0.0009137
z=6 P=0.0002428
z=7 P=0.0000647
z=8 P=0.0000173
z=9 P=0.0000046
z=10 P=0.0000012

q=0.3
z=0 P=1.0000000
z=5 P=0.1773523
z=10 P=0.0416605
z=15 P=0.0101008
z=20 P=0.0024804
z=25 P=0.0006132
z=30 P=0.0001522
z=35 P=0.0000379
z=40 P=0.0000095
z=45 P=0.0000024
z=50 P=0.0000006

Pが0.1%未満となるzを求めると...

P  0.001
q=0.10 z=5
q=0.15 z=8
q=0.20 z=11
q=0.25 z=15
q=0.30 z=24
q=0.35 z=41
q=0.40 z=89
q=0.45 z=340

Conclusion

我々は信頼に依存しない電子取引のシステムを提案した。デジタル署名から作られるコインの通常のフレームワークから出発した。これは所有権の強力な管理を提供するが、二重支払いを防ぐ方法がなければ不完全である。これを解決するために、proof-of-workを用いてトランザクションの公開履歴を記録するpeer-to-peerネットワークを提案した。正直なノードがCPUパワーの過半数を制御していれば、攻撃者がそれを変更することは計算上急速に非現実的となる。ネットワークはその非構造的な単純さにおいて頑健である。ノードはほとんど協調なしに一斉に作業する。メッセージは特定の場所にルーティングされるのではなくベストエフォートで配信されるだけでよいため、ノードは識別される必要がない。ノードは自由にネットワークから離脱・再参加でき、不在中に何が起こったかの証明としてproof-of-workチェーンを受け入れる。ノードはCPUパワーで投票し、有効なブロックの延長に取り組むことでその承認を表明し、無効なブロックに対しては作業を拒否することで拒絶する。必要なルールとインセンティブはすべてこの合意メカニズムによって施行できる。

References