論文で見るP2Pビットコインシステムの裏側

昨年の秋あたりから急にビットコインという言葉を発する人が増えてきました。前回の Mt.Gox 事件での登場以来二度目の流行です。

単に投機対象として見られている節がありますが、内部の処理はこれまでの電子決済方法とは大きく異なります。これも最近よく聞くブロックチェーンという仕組みが使われていることは有名だと思いますが、結構面白そうなので少し掘り下げてみようと思います。

スポンサーリンク

ビットコイン論文に触れてみる

完璧な翻訳ではないです。意訳も含みます。

概要

公開された論文によると、重複使用を許さず金融機関を通さない P2P 電子決済を可能にすることがビットコインシステムの最も大きな目的です。

例え暗号技術を利用した電子署名を用いても、経由する第三者に信用が置けなければ意味がないため、それを解決する方法として提案されました。

取引内容を取引時間とともに Proof-of-Work (以下、PoW) のチェーンに追加し、その処理にハッシュアルゴリズムをかませることで、取引記録を変更するには PoW を求め直すような仕組みにします。

このようにしてチェーンを構成していくと、演算に参加しているコンピュータネットワークの CPU の出力が集中しているチェーンが最長になります。

一般的には攻撃者が圧倒的な演算能力を獲得するのは容易いことではなく、ネットワークのノードに攻撃者を含まない (= チェーンを構成するための演算能力が非攻撃者によって支持される) 限りは、このチェーンでは正しい処理が行われていると判断できるというわけです。

メッセージは最大の労力を基準に送信され、ノードはネットワークに参加するも離脱するも自由です。離脱している間に起きたことの記録は最長のチェーンを以てその証拠とします。

イントロダクション

インターネット上の商取引は電子決済を扱う金融機関に依存しており、十分に機能しているものの、現在のシステムは信頼ベースである点が問題として残ります。

実店舗では商品・サービスと現金が直接やり取りされるため、トラブルは発生しません。しかし、インターネット上では完全に信頼できる当事者がいないため、このような不可逆的取引を完全に実現することは不可能な状態にあります。

ここには信頼問題がかかわっており、不可逆的という点でより安全な取引を行うことができるシステムを維持するために多くのコストを割いています。そのため、費用対利益の少ない個人レベルの取引は制限されることになり、莫大なコストをかけない代わりに一定の割合の詐欺も許容しなければなりません。

ここで必要になるのは信頼ベースではなく、暗号証明ベースの P2P 電子決済システムです。逆算が実用的でなければ取引の改竄は難しく、売り手も買い手も保護されます。

こうして提案されたのが P2P 分散型タイムスタンプサーバです。取引の時系列を演算によって保証することができます。また、システムの安全性は非攻撃者のノードの集合が攻撃者のノードの集合より多くの CPU 演算能力でこれを制御する限り保たれます。

トランザクション

電子署名のチェーンとして電子的な通貨を定義します。所有者は前の取引のハッシュ値と次の所有者の公開鍵を署名し、チェーンの最後に追加して次の取引先に転送します。次の所有者は、受け取ったときに署名を検証すれば所有権が証明されます。

しかし、この方法では受取人は過去の所有者が通貨を重複使用していないか確認できません。一般的には、重複使用がないかすべての取引をチェックする中央機関を導入することで解決できますが、この対策では中央機関に依存してしまい、現行と同様の問題を抱えることになります。

そこで、過去の所有者が以前の取引に署名していないことを受取人が確認できるようにする必要があります。重複使用があったとしても、最も早く行われた取引のみを承認するようにします。

中央機関が存在するモデルでは、中央機関がすべての取引を認識し、それらの中で最初のものを承認する形を採ります。これを中央機関なしで実現するため、ノードの参加者の大部分が公開された単一の取引履歴に同意したということを以て、受取人が重複使用がないことを確認できるようにします。

タイムスタンプサーバ

タイムスタンプサーバの役割はアイテムを含むブロックのハッシュ値を計算し、それを広く公開することです。これによって、データがその時点で存在していたことを証明できます。

タイムスタンプは前のタイムスタンプを含むようにしてチェーンを構成していきます。

Proof-of-Work (PoW)

Hashcash アルゴリズムを使ってタイムスタンプサーバを実装します。ビットコインの場合は暗号学的ハッシュ関数ハッシュ関数の中でも暗号などの情報セキュリティでの用途に適している暗号数理的性質をもつもの SHA-2 のうち、出力長 256bit である SHA-256 が使われています。ちなみに、シャーニゴロと読むらしいです。

PoW では、ハッシュ値について最初にいくつ 0bit が付与されているかのスキャンも行います。要求される平均作業量はこの 0bit の数に対して指数関数的に増加し、ここでアルゴリズムの難易度調整を行っています。ビットコインのタイムスタンプネットワークでは、ブロックのハッシュに必要な数の 0bit を与える値 Nonce使い捨てのランダムな 32bit の数値 を見つけるという形で PoW を実装します。

そのブロックについて Nonce が求められた後は一からやり直さなければブロックを変更することはできず、その後にブロックが連鎖していくため、途中のブロックを変更するためにはその後に連なるすべてのブロックについて再度 Nonce を求める必要があります。

PoW では多数決の原理は通用しません。1 IP アドレスに一票を割り当てた多数決に基づくなら、IP アドレスを多数所有する誰かによって破壊することが可能になりますが、この仕組みは本質的には 1 CPU に一票になっています。多数決の結果は最長のチェーンとして表れ、そのチェーンに費やされた PoW による労力が最大であることがわかります。

大部分の CPU 演算能力が非攻撃者のノードによって制御されている場合、この正当なチェーンが最も速く拡張され、競合するチェーンを上回ります。

攻撃者が改竄を図ったとしても、当該ブロック以降のすべてについて Nonce を求め、かつ正当なチェーンを上回るスピードで処理しなければなりません。攻撃者が追いつく確率は後続のブロック追加に対して指数関数的に減少します。

時間変化の影響に対応するために PoW の難易度は時間当たりの平均ブロック数を目標とする移動平均で決定します。

ネットワーク

ネットワークは次の手順で実行されます。

  1. 新しいトランザクションがすべてのノードに送信される
  2. 各ノードは新しいトランザクションをブロックに集める
  3. 各ノードはそのブロックに対して Nonce を求める
  4. ノードが Nonce を求めるとブロックをすべてのノードに送信する
  5. ノードはブロック内のすべてのトランザクションが有効で重複使用がない場合のみ、それを受け入れる
  6. ノードは受け入れたブロックのハッシュを使用して、チェーン内の次のブロック作成に取り組む

各ノードは常に最長のチェーンを正当とみなして拡張していきます。二つのノードが異なるバージョンのブロックを同時に送信した場合、ノードによって受信するブロックが異なることがあります。

この場合、最初に受け取ったブロックを処理しますが、もう片方のチェーンが伸びた場合に備えてそちらも保存しておきます。次の Nonce が求められたときに片方のチェーンが長くなり、もう片方が消滅します。また、消滅したチェーンで処理していたノードは長くなったチェーンに切り替わります。

送信された新しいトランザクションは多くのノードに到達すればブロックに組み込まれるため、すべてのノードに到達する必要はありません。また、ノードがブロックを受信しなかったことは、その次のブロックを受信したときに認識できます。

インセンティブ

ブロック内の最初のトランザクションは、ブロックの作成者が所有する新しい電子署名チェーン (= 通貨) を開始する特別なものです。これにより、ノードにネットワークを支持する報酬が与えられ、通貨を発行する中央機関がない中で最初に通貨を流通させる方法になります。

一定量の新しい通貨が安定的に付与されることは、金を掘るために資源を消費することに似ていて、この場合は CPU の稼働時間と電力を消費しています。

また、取引手数料からも報酬を受け取ることができます。トランザクションの出力値が入力値より小さい場合、その差額は取引手数料として報酬に加算されます。そして、発行量上限に達すると報酬は取引手数料に限られ、インフレはなくなります。

この報酬によって、ノードが攻撃者になることを防ぐことができます。大きな CPU 演算能力を持つ攻撃者が現れたとしても、取引履歴を書き換えるより正規の演算に参加したほうが有益であり、自ずとルールに従うと考えられます。

ディスク容量の再利用

電子署名チェーン (= 通貨) 内の最新の取引から十分なブロック数が構築されたら、それまでのトランザクションを破棄してディスク領域を節約できます。

ブロックのハッシュを壊さないために Merkle ハッシュ木を用い、そのルートのみがブロックのハッシュに含まれます。ブロックが古くなったら枝を切り、圧縮します。

トランザクションのないブロックヘッダーは約 80Byte で、ブロックが 10 分ごとに生成されると仮定すると 4.2MB/year です。ムーアの法則に基づけばストレージに問題はないと考えられます。(← 2008 年なので。)

簡略的な支払いの検証方法

ユーザーは最長の PoW チェーンのブロックヘッダーのコピーを保持しておくだけでよく、それはネットワークノードに照会するだけで得ることができ、トランザクションをタイムスタンプされたブロックにリンクする Merkle ハッシュ木の枝を取得すればいいでしょう。

自分自身でトランザクションをチェックすることは適いませんが、チェーン内の場所にリンクすることでネットワークノードが受理したことがわかり、受理したノードがより多く確認できればブロックが追加されます。

したがって、非攻撃者のノードがネットワークを制御する限りは信頼できますが、攻撃者のノードがこれを圧倒した場合はより脆弱になります。ノードは自分自身でトランザクションを検証できますが、この状況では、簡略化された検証方法を用いることで攻撃者が作成したトランザクションに騙される可能性があります。

これを防ぐための戦略は、無効なブロックを検出したときにネットワークノードから警告を受け取ることです。頻繁に支払いを受ける企業はより独立したセキュリティと迅速な検証のために独自のノードを実行したいと考えるでしょう。

分割と結合

個別に処理することは可能ですが扱いにくくなります。値を分割・結合するために、トランザクションは複数の入出力を含んでいます。通常、より大きなトランザクションからの単一の入力、または小さなものを組み合わせた複数の入力。それに対して高々二つの出力があり、一方は支払いのため、もう一方は送信者に対するお釣りの返金のための出力です。

トランザクションが複数のトランザクションに依存することはここでは問題になりません。

プライバシー

現在の銀行は当事者と信頼できる第三者のみ情報にアクセスできるため、プライバシーが保たれます。

提案するシステムではすべての取引を公表する必要がありますが、公開鍵を匿名で保持することでプライバシーを保つことができます。第三者がわかるのは誰かが誰かにある金額を送ったということだけで、送信先はわかりません。

追加のファイアウォールとして、各トランザクションごとに新しいキーペアを使用する必要があります。複数のトランザクションの入力がある環境で同一のキーを用いると、キーの所有者が明らかになった場合、リンクすると同じ所有者に属する他の取引が明らかになってしまうリスクがあるからです。

計算

正規チェーンよりも速く代替チェーンを生成する攻撃者を考えると、これを達成したとしても、何もないところから価値を想像したり攻撃者に属していないところからお金を盗んだりといった任意の変更はできません。なぜなら、ノードは無効なトランザクション、それを含むブロックを受理しないからです。攻撃者にできるのは、過去に支払ったトランザクションを変更してお金を取り戻すことです。

正規チェーンと攻撃者のチェーンの競争は二項ランダムウォークとして特徴づけられます。

  • 成功:正規チェーン 1 ブロック拡張、リード +1
  • 失敗:攻撃者のチェーン 1 ブロック拡張、ギャップ -1

これは Gambler’s Ruin の問題に似ています。無制限の信用をもつギャンブラーが赤字から損益分岐点に到達しようとする試みを無限に行うと考えます。

\(p = 非攻撃者が次のブロックを見つける確率 \\
q = 攻撃者が次のブロックを見つける確率 \\
q_z = 攻撃者がzブロック後ろに追いつく確率 \)

\[ \begin{eqnarray} q_z = \begin{cases} 1 & if ~~ p \le q \\ (q/p)^z & if ~~ p > q \end{cases} \end{eqnarray} \]

\( p > q \) と仮定すると、攻撃者が追いつくブロック数に応じて確率は指数関数的に減少します。

次に、新しいトランザクションの受信者が、送信者がトランザクションを変更できないことを確認するのに必要な待ち時間を考えます。攻撃者である送信者は受信者に暫くの間支払いが正当だと信じさせたいものと仮定し、ある時間経過したら返金に切り替えます。これは受信者に通知されますが、通知が遅ければ送信者は返金処理が完了。つまり、お金を使わなかったことにできるということです。

受信者は新しいキーペアを作成し、署名直前に送信者に公開鍵を与えるようにします。これによって、送信者は事前に得た公開鍵でその時点のトランザクションを実行し、ブロックのチェーンを準備できなくなります。トランザクションが送信されると、攻撃者は代替となるトランザクションを含む並列のチェーン上で作業し始めます。

受信者はトランザクションがブロックに追加され、その後に \(z\) ブロック繋がるまで待ちます。受信者は攻撃者の進捗を正確に把握しませんが、正当なブロックがブロックあたりの平均予想時間を使うと仮定すると、攻撃者の潜在的な進捗は期待値のポアソン分布になります。

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

攻撃者が追いつく可能性のある可能性を求めるために、その時点から追いつく可能性のある進捗ごとにポアソン密度をかけます。

\[ \sum_{k=0}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \cdot \begin{Bmatrix} (q/p)^{z-k} & if ~ k \le z \\ 1 & if ~ k>z \end{Bmatrix} \]

無限の部分の処理のために変形します。

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

C 言語で書くとこのような処理になります。

これを基に \( p < 0.001 \) となるような \(q, ~ z \) の値を求めると、このようになります。

\( q \) \( z \)
0.10 5
0.15 8
0.20 11
0.25 15
0.30 24
0.35 41
0.40 89
0.45 340

結論

このようにして、信頼に依らない電子取引システムを構築できます。そして、所有権を強力にコントロールできる電子署名チェーンによる通貨の概念と、重複使用を防ぐために多くの非攻撃者ノードで構成された P2P ネットワークを提案しました。

ネットワークの仕組みは単純で、ノードを次第に増やしていくことができます。また、ノードの参加、離脱は自由であり、PoW のチェーンによって離脱中の出来事も捕捉できます。

システムでは、CPU 演算能力による多数決で有効なブロックを受理、拡張していきます。このコンセンサスの仕組みにより、必要なルールやインセンティブを実施できるのです。

最後に

ほんとはもっと色々書きたかったはずなんですけど、思ったより翻訳部分が長くなってしまったので、次回以降に…。

それから、翻訳のほうは自己の見解が加わったものなので、間違いが含まれるかもしれませんがご容赦ください。

スポンサーリンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA