最小限の信頼要件で安全なタイムスタンプサービスを設計する Henri Massias, Xavier Serret-Avila, Jean-Jacques Quisquater 第20回ベネルクス情報理論シンポジウム (1999-05)
デジタル文書にタイムスタンプを付ける方法 Stuart Haber, W.Scott Stornetta Journal of Cryptology (1991) DOI: 10.1007/bf00196791
デジタルタイムスタンプの効率と信頼性の向上 Dave Bayer, Stuart Haber, W. Scott Stornetta Sequences II (1993) DOI: 10.1007/978-1-4613-9323-8_24
ビット文字列の安全な名前 Stuart Haber, W. Scott Stornetta Proceedings of the 4th ACM conference on Computer and communications security - CCS '97(1997) DOI: 10.1145/266420.266430
Hashcash - サービス拒否対策 Adam Back (2002-08-01)
公開鍵暗号のプロトコル Ralph C. Merkle 1980 IEEE Symposium on Security and Privacy (1980-04) DOI: 10.1109/sp.1980.10006
An Introduction to Probability Theory and its Applications William Feller John Wiley & Sons (1957年)
15周年記念クラシック再読:ビットコイン白書の中国語版全文
著者:サトシ・ナカモト; 中国語字幕翻訳:李暁来(リー・シャオライ)
概要: 電子マネー・システムの純粋なピア・ツー・ピア・バージョンで、金融機関を介さずに、ある当事者から別の当事者に直接オンライン決済を送金することができます。 デジタル署名はいくつかの解決策を提供しますが、二重支払いを防ぐために信頼できる第三者が依然として必要な場合、電子決済の主な利点は相殺されます。 ピアツーピアネットワークを利用して二重支出の問題を解決するソリューションを提案します。 ピアツーピアネットワークは、トランザクションのハッシュ化されたデータを、完全にやり直さない限り変更できない広範なハッシュベースのプルーフオブワークチェーンに入力することにより、各トランザクションにタイムスタンプを付けます。 最長のチェーンは、目撃されたイベントとその順序を証明するために使用され、一方で、それがCPUハッシュパワーの最大のプールから来ていることを証明するために使用されます。 CPUの計算能力の大部分が良性のノードによって制御されている限り、つまり、ネットワークを攻撃しようとするノードに協力しない限り、良性のノードは最長のチェーンを生成し、攻撃者を凌駕します。 ネットワーク自体には最小限の構造が必要です。 情報は最善の努力に基づいて広められ、ノードは自由に行き来します。 ただし、参加するときは、関与していない期間に起こったすべての証拠として、最も長いプルーフ・オブ・ワークのチェーンを常に受け入れる必要があります。
1. 紹介
インターネット商取引は、電子決済を処理するために、信頼できる第三者として金融機関にほぼ完全に依存しています。 このシステムはほとんどの取引でかなり優れていますが、信頼ベースのモデルに固有の欠陥によって妨げられています。 完全に不可逆的な取引は、金融機関が仲裁紛争を避けることができないため、現実的には不可能です。 仲裁のコストは取引コストを増加させ、その結果、可能な限り最小の取引のサイズが制限され、多くのマイクロペイメント取引が妨げられます。 その上、システムは可逆的でないサービスに対して不可逆的な支払いを行うことができないという、さらに大きなコストがかかります。 逆転の可能性は、信頼へのあらゆるニーズを生み出しました。 マーチャントは顧客を警戒し、(信頼されていれば)必要のないより多くの情報を提供するように気を配らなければなりません。 一定の割合の不正は避けられないと考えられています。 これらのコストと支払いの不確実性は、物理的な通貨を使用して人々の間で直接支払いが行われる場合に回避できます。 ただし、どちらか一方が信頼されない限り、両当事者が通信チャネルを介して支払いを行うメカニズムはありません。
私たちが本当に必要としているのは、信頼ではなく暗号証明に基づく電子決済システムであり、第三者を信頼することなく、2つの当事者が直接取引できるようにすることです。 ハッシュレート保証の不可逆的な取引は、売り手が詐欺を回避するのに役立ち、買い手を保護するための毎日の保証メカニズムは簡単に実装できます。 本稿では、ピアツーピアの分散型タイムスタンプサーバーを使用して、各トランザクションを時系列で記録するハッシュレートベースのプルーフを生成する、二重支払いのソリューションを提案します。 正直なノードが、互いに協力する攻撃者よりも多くのCPUパワーを持っている限り、システムは安全です。
2. トランザクション
電子コインは、デジタル署名のチェーンとして定義されています。 所有者がコインを他の人に与えるとき、彼または彼女はデジタル署名チェーンの末尾に次のデジタル署名を追加することによってそうします:以前のトランザクションのハッシュと新しい所有者の公開鍵。 受取人は、署名を検証することで、デジタル署名チェーンの所有権を確認できます。
このパスの問題は、受取人が前の所有者の間で誰も二重に支払っていないことを確認できないことです。 一般的な解決策は、信頼できる中央集権的な機関、つまり「ミント」を導入し、すべてのトランザクションで二重支払いをチェックさせることです。 各取引の後、コインは造幣局に返却されなければならず、造幣局は新しいコインを発行します。 さらに、造幣局が直接発行した硬貨のみが信頼でき、二重に支払われていません。 この解決策の問題点は、貨幣システム全体の運命が造幣局を運営する会社(銀行など)に縛られており、すべての取引が造幣局を通過しなければならないことです。
前の所有者が以前の取引に署名していないことを受取人が確認する方法が必要でした。 ここでは、最初のトランザクションのみがカウントされるため、その後の二重支払いの試行は気にしません。 トランザクションが存在しないことを確認する唯一の方法は、すべてのトランザクションを通知することです。 造幣局モデルでは、造幣局はすべての取引を認識しており、それらの取引の順序を確認することができます。 「信頼できる当事者」を介さずにこれを実現するためには、取引記録を公に宣言する必要があり1、参加者が受け取るのと同じ固有の取引履歴に同意できるシステムが必要です。 受取人は、各取引の時点で、ノードの過半数が最初に受け取ったことに同意できることを証明する必要があります。
3. タイムスタンプサーバ
このソリューションは、タイムスタンプサーバーから始まります。 タイムスタンプサーバは、レコードの集合のハッシュにタイムスタンプを付け、新聞のように、あるいはUsenetの投稿のように、そのハッシュをブロードキャストします2 3 4 5。 明らかに、タイムスタンプは、その時点より前にデータが存在していたことを証明し、そうでなければハッシュは生成されませんでした。 各タイムスタンプには、ハッシュに以前のタイムスタンプが含まれているため、チェーンが形成されます。 新しいタイムスタンプは、前のタイムスタンプの後に追加されます。
4. プルーフ・オブ・ワーク
ピアツーピアベースの分散型タイムスタンプサーバーを実装するには、新聞やニュースグループの投稿のようなものではなく、Adam BurkeのHash Cash 6のようなプルーフオブワークシステムを使用する必要があります。 いわゆるプルーフ・オブ・ワークは、価値を見出すことです。 この値が真であるためには、そのハッシュ値を抽出した後 (たとえば、SHA-256 を使用してハッシュ値を計算する場合)、ハッシュ値は特定の数のゼロで始まる必要があります。 要件が 0 になるたびに作業量が指数関数的に増加し、この作業量の検証に必要なのはハッシュを計算するだけです。
タイムスタンプネットワークでは、プルーフ・オブ・ワークを次のように実装しています:条件を満たす値が見つかるまで、ブロックにノンスを追加し続けます。 この条件は、ブロックのハッシュが指定された数の 0 で始まることです。 CPU のコンピューティング電力消費の結果がプルーフ オブ ワークを満たすと、以前のすべての作業がやり直されない限り、ブロックを変更できなくなります。 新しいブロックは常に追加されるため、現在のブロックを変更すると、後続のすべてのブロックが再仕上げされます。
プルーフ・オブ・ワークは、誰が多数派に代わって決定を下すことができるかという問題も解決します。 いわゆる「多数派」が「1つのIPアドレス、1票」のアプローチに基づいている場合、多くのIPアドレスを処理できる人は誰でも「多数派」と見なすことができます。 プルーフ・オブ・ワークは、基本的に「1つのCPU、1つの投票」です。 いわゆる「多数決」は、最も多くの労力が費やされたチェーンであるため、最も長いチェーンで表されます。 CPUの計算能力の大部分が正直なノードによって制御されている場合、正直なチェーンは最も速く成長し、他の競合するチェーンよりもはるかに高速になります。 すでに生成されたブロックを変更するには、攻撃者はそのブロックと後続のすべてのブロックのプルーフ・オブ・ワークを再完了し、誠実なノードの作業に追いつき、それを超える必要があります。 この記事では、ブロック数が増えるにつれて、遅延した攻撃者が追いつく可能性が指数関数的に減少する理由を示します。
ハードウェアの計算能力の増加と、時間の経過とともに変化する可能性のあるノードの貢献度に対処するために、プルーフ・オブ・ワークの難易度は、平均して1時間あたりに生成されるブロック数の移動平均によって決定されます。 ブロックの生成が速すぎると、難易度が上がります。
5. ネットワーク
ネットワークを実行する手順は次のとおりです。
ノードは常に最長のチェーンが正しいチェーンであると考え、新しいデータを追加し続けます。 2つのノードが同時に2つの異なるバージョンの「ネクストブロック」をネットワークにブロードキャストする場合、一部のノードはそのうちの1つを最初に受信し、他のノードはもう1つを最初に受信します。 この場合、ノードは最初に受け取ったブロックで作業を続けますが、他のブランチが最長のチェーンになった場合に備えて保存します。 次のプルーフ・オブ・ワークが見つかり、ブランチの1つが長くなると、この一時的な分岐が解決され、もう一方のブランチで作業しているノードはより長いチェーンに切り替わります。
新しいトランザクションは、必ずしもすべてのノードにブロードキャストする必要はありません。 十分なノードに到達している限り、それらのトランザクションがブロックにパックされるまでにそれほど時間はかかりません。 ブロック ブロードキャストでは、一部のメッセージを破棄することもできます。 ノードがブロックを受信しない場合、ノードは次のブロックを受信したときに前のブロックを見逃したことを認識し、不足しているブロックを置き換える要求を行います。
6. 誘因
慣例により、各ブロックの最初のトランザクションは、新しいコインを生成する特別なトランザクションであり、ブロックのジェネレーターに属します。 そうすることで、ネットワークをサポートし、コインを発行する中央集権的な権限がないシステムで、コインを流通させる方法を提供するノードに報酬が与えられます。 したがって、一定数の新しい硬貨を着実に流通させることは、金鉱夫が常に資源を使って金を流通させるようなものです。 私たちのシステムでは、消費されるリソースは、CPUが動作している時間とCPUが使用する電力です。
報酬は、取引手数料からも得られます。 トランザクションの出力値が入力値よりも小さい場合、差はトランザクション手数料です。 トランザクション手数料は、トランザクションをこのブロックにパッケージ化したノードに報酬を与えるために使用されます。 設定された数のコインが流通すると、報酬は取引手数料で完全にカバーされ、インフレはまったく発生しません。
また、報酬の仕組みは、ノードが正直であることを奨励するかもしれません。 貪欲な攻撃者が、すべての誠実なノードよりも多くのCPUパワーを罠にかけることができる場合、その計算能力を使用して、自分が費やしたお金を盗み出すことで他の人を欺くべきか、選択を迫られます。 それとも、この計算能力を使って新しいコインを生成しますか? 彼はルールに従ってプレイする方が費用対効果が高いと感じるはずで、他のコインを合わせたよりも多くのコインを稼ぐことができ、密かにシステムを破壊して富を無にするよりも明らかに費用対効果が高いのです。
7. ディスク領域の再利用
コインの最新のトランザクションが十分なブロック数より前に発生した場合、ディスク容量を節約するために、そのトランザクション以前のコインの支出トランザクション履歴を破棄できます。 ブロックのハッシュを壊さずにこれを行うために、トランザクションレコードのハッシュはマークルツリーに含まれ、ツリーのルートのみがブロックのハッシュに含まれます。 枝を切り落とすことで、古いブロックを圧縮することができます。 内部ハッシュを保存する必要はありません。
トランザクション履歴のないブロックヘッダーは約80バイトです。 ブロックが 10 分ごとに生成されると仮定すると、80 バイトに 6 x 24 x 365 を掛けると、年間 4.2M になります。 2008年の時点で、販売されているほとんどのコンピュータには2GBのRAMが搭載されており、ムーアの法則では、ブロックヘッダーをメモリに保存する必要がある場合でも、年間1.2GBが追加されると予測されています。
8. 支払い確認の簡素化
完全なネットワークノードを稼働させなくても、支払いを確認することが可能です。 ユーザーに必要なのは、プルーフ・オブ・ワーク付きの最長チェーンのブロックヘッダーのコピー(オンラインノードをチェックして、自分が最も長いチェーンを持っていることを確認できます)と、マークルツリーのブランチノードを取得し、ブロックにタイムスタンプが付けられたときにトランザクションに接続することだけです。 ユーザーは自分でトランザクションを確認することはできませんが、チェーン上の特定の場所に接続することで、ネットワークノードがトランザクションを受け入れたことを確認することができ、その後に追加されるブロックは、ネットワークがトランザクションを受け入れたことをさらに確認します。
誠実なノードがネットワークを制御している限り、検証は信頼できます。 ただし、ネットワークが攻撃者によって制御されている場合、検証の信頼性は低くなります。 ネットワークノードはトランザクション自体を検証できますが、攻撃者がネットワークを制御している限り、簡略化された検証方法は、攻撃者の偽造されたトランザクション記録に欺かれる可能性があります。 対策の 1 つは、クライアント ソフトウェアがネットワーク ノードからの警告を受け入れることです。 ネットワークノードが無効なブロックを見つけると、アラートが送信され、ユーザーのソフトウェアに通知がポップアップ表示され、ブロック全体をダウンロードするようにユーザーに通知し、トランザクションの一貫性を確認するようにユーザーに警告します。 高頻度の支払いを行う加盟店は、より独立したセキュリティとより迅速な取引確認を確保するために、独自のフルノードを実行したいと考える必要があります。
9. 価値の組み合わせと分割
硬貨を1枚ずつ処理することは可能ですが、1ペニーごとに別々の記録を設定するのは不格好です。 値の分割と連結を可能にするために、トランザクションには複数の入力と出力が含まれます。 一般に、比較的大きな前のトランザクションからの単一のインプット、またはより少ない量からの多くのインプットの組み合わせのいずれかです。 同時に、出力は最大で 2 つあり、1 つは支払い (受取人) 用、もう 1 つは必要に応じて変更用 (送信者) です。
ここで重要なのは、「ファンアウト」は問題ではないということです - 「ファンアウト」とは、1つのトランザクションが複数のトランザクションに依存し、それらのトランザクションがより多くのトランザクションに依存することを意味します。 トランザクションの完全で独立した履歴コピーを抽出する必要はありません。
10. プライバシー
従来の銀行モデルでは、トレーダーや信頼できる第三者に関する情報へのアクセスを制限することで、ある程度のプライバシー保護を実現しています。 このアプローチは、すべての取引記録を公開する必要があるため、却下されました。 しかし、プライバシーの維持は、公開鍵の匿名性という別の場所で情報の流れを遮断することで実現できます。 一般の人々は、ある金額を○○に送金したことはわかりますが、特定の人物を指す情報はありません。 このレベルの情報公開は株式市場の取引に少し似ており、個々の取引の時間と金額のみが発表されますが、取引の両側が誰であるかは誰にもわかりません。
ファイアウォールには別の層があります。 トレーダーは、他の誰もこれらのトランザクションを同じ所有者にさかのぼることができないように、トランザクションごとに公開鍵と秘密鍵の新しいペアを有効にする必要があります。 一部のマルチインプットトランザクションは、必然的に同じ所有者からのものとして識別されるため、必然的に遡及的になります。 危険なのは、公開鍵の所有者が公開されると、それに関連する他のすべてのトランザクションが公開されることです。
11. 計算
たとえば、攻撃者が正規のチェーンよりも高速な代替チェーンを生成しようとしているシナリオを考えてみましょう。 たとえ成功したとしても、システムを変えることはできない、つまり、何もないところから価値を生み出すことはできないし、自分のものではないお金を得ることもできない。 ネットワークノードは無効なトランザクションを支払いとして扱わず、誠実なノードはそのような支払いを含むブロックを受け入れることはありません。 せいぜい、攻撃者は自分の取引を変更し、すでに使ったお金を取り戻そうとするだけです。
正直なチェーンと攻撃者の間のライバル関係は、二項ランダムウォークで説明できます。 成功イベントとは、新しいブロックが正直チェーンに追加され、そのアドバンテージが1増加した場合であり、失敗イベントは、攻撃者のチェーンに新しいブロックが追加され、正直チェーンの利点が1減少した場合です。
攻撃者が背後から追いつくことができる確率は、ギャンブラーが破産する問題に似ています。 無制限のチップを持つギャンブラーが、赤字から始めて、すでに持っている赤字を埋めることを目的として、無制限の回数賭けることができるとします。 彼が最終的に不足を埋めることができる確率、つまり攻撃者が正直なチェーンに追いつくことができる確率は、次のように計算できます。
p>,qと仮定したので、攻撃者はより多くのブロックに追いつく必要があるため、成功の確率は指数関数的に減少します。 アタッカーが幸運にも最初に飛躍しなければ、勝率は一掃され、さらに遅れをとってしまいます。
次に、新しいトランザクションの受信者が、送信者がトランザクションを変更できないことを完全に確信するまで、どのくらいの期間待機する必要があるかを考えます。 送信者は、一定期間支払いを済ませたことを受取人に納得させ、そのお金を自分自身に送金しようとする攻撃者であると仮定します。 こうなると、もちろん受取人は警告を受けますが、送り主は木造船がすでに船に乗っていることを望んでいます。
受信者は、公開鍵と秘密鍵の新しいペアを作成し、署名の直前に公開鍵を送信者に伝えます。 これにより、送信者が連続計算でチェーン上のブロックを事前に準備し、それまでトランザクションを実行するのに十分なほど先手を打てるという状況を防ぐことができます。 お金が送金されると、不正な送信者は別のパラチェーンで密かに作業を開始し、トランザクションの逆バージョンを追加しようとします。
受取人は、トランザクションがブロックにパックされるまで待機し、その後に追加されたzブロックがすでにあります。 攻撃者がどの程度うまくやっているかは正確にはわかりませんが、誠実なブロックは各ブロックを生成するプロセスに平均的な時間を費やすと想定できます。 攻撃者の潜在的な進行はポアソン分布に準拠し、期待値は次のようになります。
攻撃者がまだ追いつくことができる確率を計算するには、攻撃者が追いつく必要があるブロック数のパルゾン分布の確率密度に、その数のブロックより遅れている場合に追いつくことができる確率を掛ける必要があります。
C プログラムに変換...
結果の一部を見ると、zが増加するにつれて確率が指数関数的に減少することがわかります。
Pが0.1%未満の場合...
12. 結論
信頼に頼らない電子取引システムを提案します。 出発点は、デジタル署名を使用する無地のコインフレームであり、堅牢な所有権管理を提供しますが、二重支出を回避することはできません。 この問題を解決するために、プルーフ・オブ・ワークの仕組みを用いて公開取引履歴を記録するピアツーピアネットワークを提案し、誠実なノードがCPUの計算能力の大部分を制御できるのであれば、攻撃者が計算能力だけでシステムを改ざんすることは不可能です。 このネットワークの堅牢性は、その非構造化された単純さにあります。 ノードは、ほとんどコラボレーションすることなく、瞬時に同時に動作できます。 メッセージのパスは特定の宛先に依存しないため、認識する必要さえありません。 メッセージは、ベストエフォートベースで広めるだけで済みます。 ノードは自由に出入りし、再参加するときは、オフライン中に起こったすべての証拠としてプルーフ・オブ・ワーク・チェーンを受け入れるだけで済みます。 彼らはCPUパワーに投票し、常に新しい有効なブロックをチェーンに追加し、無効なブロックを拒否することで、有効なトランザクションの受け入れを示します。 必要なルールや報酬は、このコンセンサスメカニズムを通じて実施することができます。
参考文献 (References)