関連: 初期草稿（2008年10月3日）

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

Satoshi Nakamoto
satoshin@gmx.com
www.bitcoin.org

概要完全なピアツーピア版の電子キャッシュは、金融機関を経由せずに、オンライン決済を当事者間で直接送金することを可能にする。デジタル署名はソリューションの一部を提供するが、二重支払いの防止に信頼できる第三者が依然として必要であれば、主要な利点は失われる。我々は、ピアツーピアネットワークを用いた二重支払い問題の解決策を提案する。ネットワークは、トランザクションをハッシュベースのプルーフ・オブ・ワークの継続的なチェーンにハッシュ化することでタイムスタンプを付与し、プルーフ・オブ・ワークをやり直さない限り変更できない記録を形成する。最長のチェーンは、目撃されたイベントの順序の証明としてだけでなく、それが最大のCPUパワーのプールから生まれたことの証明としても機能する。CPUパワーの過半数がネットワークへの攻撃に協力しないノードによって制御されている限り、彼らは最長のチェーンを生成し攻撃者を凌駕する。ネットワーク自体は最小限の構造しか必要としない。メッセージはベストエフォートベースでブロードキャストされ、ノードは自由にネットワークを離脱・再参加でき、不在中に何が起きたかの証明として最長のプルーフ・オブ・ワークチェーンを受け入れる。

1. はじめに

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

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

2. トランザクション

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

Transactions

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

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

3. タイムスタンプサーバー

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

Timestamp Server

4. プルーフ・オブ・ワーク

ピアツーピアベースで分散型タイムスタンプサーバーを実装するには、新聞やUsenetの投稿ではなく、Adam BackのHashcash [6]に類似したプルーフ・オブ・ワークシステムを使用する必要がある。プルーフ・オブ・ワークは、SHA-256などでハッシュした場合に、ハッシュが一定数のゼロビットで始まる値をスキャンすることを含む。必要な平均作業量はゼロビットの数に対して指数関数的であり、単一のハッシュを実行することで検証できる。

我々のタイムスタンプネットワークでは、ブロック内のnonceをインクリメントし、ブロックのハッシュに必要なゼロビットを与える値が見つかるまで処理することでプルーフ・オブ・ワークを実装する。プルーフ・オブ・ワークを満たすためにCPUの労力が費やされると、その作業をやり直さなければブロックを変更することはできない。後のブロックがその後にチェーンされるため、ブロックを変更する作業にはその後のすべてのブロックのやり直しが含まれる。

Proof-of-Work

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

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

5. ネットワーク

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

新しいトランザクションはすべてのノードにブロードキャストされる。
各ノードは新しいトランザクションをブロックにまとめる。
各ノードはそのブロックの困難なプルーフ・オブ・ワークの発見に取り組む。
ノードがプルーフ・オブ・ワークを発見すると、そのブロックをすべてのノードにブロードキャストする。
ノードは、ブロック内のすべてのトランザクションが有効であり、まだ使用されていない場合にのみ、そのブロックを受け入れる。
ノードは、受け入れたブロックのハッシュを前のハッシュとして使用して、チェーンの次のブロックの作成に取り組むことで、そのブロックの受け入れを表明する。

ノードは常に最長のチェーンを正しいものと見なし、その延長に取り組み続ける。2つのノードが異なるバージョンの次のブロックを同時にブロードキャストした場合、一部のノードはどちらかを先に受信する。その場合、最初に受信したものに取り組むが、もう一方の分岐がより長くなった場合に備えて保存する。次のプルーフ・オブ・ワークが発見され、一方の分岐がより長くなったとき、同点は解消される。もう一方の分岐に取り組んでいたノードは、より長い方に切り替える。

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

6. インセンティブ

慣習として、ブロックの最初のトランザクションは、ブロックの作成者が所有する新しいコインを開始する特別なトランザクションだ。これはノードがネットワークを支援するインセンティブを追加し、発行する中央機関がないため、コインを流通に最初に分配する手段を提供する。一定量の新しいコインの安定的な追加は、金の採掘者が資源を費やして金を流通に追加することに類似している。我々の場合、費やされるのはCPU時間と電力だ。

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

インセンティブはノードが正直であり続けることを促進する。貪欲な攻撃者がすべての正直なノードよりも多くのCPUパワーを集めることができた場合、自分の支払いを盗み返すことで人々を欺くためにそれを使用するか、新しいコインを生成するためにそれを使用するかを選択しなければならない。ルールに従ってプレイする方がより利益的であると考えるべきだ——そのルールは他のすべての参加者を合わせたよりも多くの新しいコインを彼に有利にする——システムと自身の富の正当性を損なうよりも。

7. ディスクスペースの回収

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

Reclaiming Disk Space

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

8. 簡易支払い検証

フルネットワークノードを実行せずに支払いを検証することが可能だ。ユーザーは、最長のプルーフ・オブ・ワークチェーンのブロックヘッダーのコピーのみを保持すればよく、最長のチェーンを持っていると確信できるまでネットワークノードに問い合わせ、トランザクションをタイムスタンプされたブロックにリンクするマークル分岐を取得する。トランザクション自体をチェックすることはできないが、チェーン内の場所にリンクすることで、ネットワークノードがそれを受け入れたことが確認でき、その後に追加されたブロックがネットワークがそれを受け入れたことをさらに確認する。

Simplified Payment Verification

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

9. 価値の結合と分割

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

Combining and Splitting Value

なお、ファンアウト——トランザクションが複数のトランザクションに依存し、それらのトランザクションがさらに多くに依存する——はここでは問題にならない。トランザクションの履歴の完全なスタンドアロンのコピーを抽出する必要は決してない。

10. プライバシー

従来の銀行モデルは、関係当事者と信頼できる第三者への情報アクセスを制限することでプライバシーのレベルを達成する。すべてのトランザクションを公に公表する必要性はこの方法を排除するが、公開鍵を匿名に保つという別の場所で情報の流れを断つことでプライバシーを維持できる。ある人が他の誰かに金額を送っていることは公開されるが、トランザクションを誰かにリンクする情報はない。これは証券取引所が公開する情報のレベルに類似しており、個々の取引の時間とサイズ（「テープ」）は公開されるが、当事者が誰であるかは明かされない。

Privacy

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

11. 計算

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

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

攻撃者が与えられた差から追いつく確率は、ギャンブラーの破産問題に類似している。無限のクレジットを持つギャンブラーが赤字からスタートし、ブレイクイーブンに到達しようと潜在的に無限の試行を行うとする。ギャンブラーがブレイクイーブンに到達する確率、すなわち攻撃者が正直なチェーンに追いつく確率は、以下のように計算できる [8]：

p = 正直なノードが次のブロックを見つける確率
q = 攻撃者が次のブロックを見つける確率
q_z = 攻撃者がzブロック後方から追いつく確率

$q_z = \begin{cases} 1 & \text{if } p \leq q \\ (q/p)^z & \text{if } p > q \end{cases}$

p > q という仮定のもと、攻撃者が追いつかなければならないブロック数が増えるにつれて、確率は指数関数的に低下する。不利なオッズに対して、早い段階で幸運な前進ができなければ、遅れるほどチャンスはますます小さくなる。

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

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

受取人は、トランザクションがブロックに追加され、その後にzブロックがリンクされるまで待つ。攻撃者がどれだけ進捗したかの正確な量はわからないが、正直なブロックがブロックあたりの平均期待時間を要したと仮定すると、攻撃者の潜在的な進捗は以下の期待値を持つポアソン分布となる：

$\lambda = z \frac{q}{p}$

攻撃者が現時点でまだ追いつける確率を得るために、攻撃者が達成し得た各進捗量のポアソン密度と、その時点から追いつける確率を乗じる：

$\sum_{k=0}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \cdot \begin{cases} (q/p)^{(z-k)} & \text{if } k \leq z \\ 1 & \text{if } k > z \end{cases}$

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

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

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%未満となる値を求める…

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

12. 結論

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

参考文献

[1] W. Dai, “b-money,” http://www.weidai.com/bmoney.txt, 1998.

[2] H. Massias, X.S. Avila, and J.-J. Quisquater, “Design of a secure timestamping service with minimal trust requirements,” In 20th Symposium on Information Theory in the Benelux, May 1999.

[3] S. Haber, W.S. Stornetta, “How to time-stamp a digital document,” In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.

[4] D. Bayer, S. Haber, W.S. Stornetta, “Improving the efficiency and reliability of digital time-stamping,” In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.

[5] S. Haber, W.S. Stornetta, “Secure names for bit-strings,” In Proceedings of the 4th ACM Conference on Computer and Communications Security, pages 28-35, April 1997.

[6] A. Back, “Hashcash - a denial of service counter-measure,” http://www.hashcash.org/papers/hashcash.pdf, 2002.

[7] R.C. Merkle, “Protocols for public key cryptosystems,” In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980.

[8] W. Feller, “An introduction to probability theory and its applications,” 1957.

ビットコイン：ピアツーピア電子キャッシュシステム（ホワイトペーパー）