オブジェクトの広場は株式会社オージス総研グループのエンジニアによる技術発表サイトです

クラウド/Webサービス

ビットコイン論文からさぐる ブロックチェーンのヒント

第6回 ネットワークと誠実なノード 前編:理論編
オージス総研
樋口 匡俊
2019年7月30日

今回と次回は、二回に分けて、ビットコインのネットワークについて見ていきます。前編となる今回は、ビットコイン論文の第5章「Network」や、第4章「Proof-of-Work」のうち前回とり上げなかった箇所を読んでいきます。

ブロックチェーンはデータベースである?

いわゆるスノーデン事件で有名なエドワード・スノーデン (Edward Snowden) は、ブロックチェーンについて解説するにあたり、「(ブロックチェーンは)基本的に新種のデータベースだ」と述べています。 ※1

たしかに、ブロックチェーンと称するものの多くは、従来からあるデータベースを利用しています。ビットコインも、Berkeley DBLevelDB という十年以上の歴史を持つデータベース・ライブラリを使ってきました。そのことだけを見れば、ブロックチェーンは新種どころか既存のデータベースを活用したアプリケーションにすぎません。

また、「ブロックチェーン」という呼び名は、明らかにブロックをチェーンのようにつなげるデータ構造に着目したものです。けれども第4回で見たとおり、ビットコインのそのデータ構造は、既存のタイムスタンプ技術にならったものです。その形だけ眺めていても、ブロックチェーンならではと言える特徴は見えてこないでしょう。

ビットコイン: P2P 電子マネーシステム

本連載の初回では、Abstract の最初の一文に書かれている「純粋な P2P (purely peer-to-peer)」をとり上げました。Abstract には続けて、論文の主題である二重使用問題は P2P ネットワークを用いて解決すると書かれています (We propose a solution to the double-spending problem using a peer-to-peer network.) 。

第3回で見たとおり、TTP を用いずに二重使用問題を解決するには、ネットワークの参加者がトランザクションのたったひとつの順番に合意できる仕組みが必要だとサトシは考えました。 ※2

データベースもチェーンのようなデータも、一か所に固まっているのではなく、サトシがそのように問題解決の基本的な枠組みとしたネットワーク上に散らばっているという視点で見る必要があるでしょう。

そんなネットワークが、冒頭のような短い説明において無視されがちな理由の一つは、その複雑さにあるのかもしれません。ビットコイン論文は、さまざまな要素が絡み合う複雑なネットワークについて完璧に説明できているわけではありませんが、ともかくまずは第5章「Network」を読んでみることにしましょう。

ネットワークの六つのステップ

第5章「Network」では、ビットコインの P2P ネットワークを説明するにあたり、参加者が運営するノード (node) の動きを六つのステップに分けています。各ステップを一言で述べると、次のようになります。

1) トランザクションのブロードキャスト
2) トランザクションの蓄積
3) PoW
4) ブロックのブロードキャスト
5) ブロックの検査
6) ブロックの受け入れ

以下では、それぞれのステップについて見ていきます。これまでの連載のおさらいのようにもなっていますので、不明な点があれば特に第3, 4, 5回を参照してください。

1) トランザクションのブロードキャスト

1) New transactions are broadcast to all nodes.

1) 新たなトランザクションは全てのノードにブロードキャストされる。

ブロードキャスト (broadcast) というのは、通信技術の一般的な用語ですね。論文では、ビットコインのネットワークに参加している全てのノードにデータを送るという意味で使われています。

サトシは、二重使用を検査するには全てのトランザクションを知る必要があると考えていましたね。従来の電子マネーにおいて、その役目を果たしていたのは中央の貨幣鋳造所でした。ビットコインにおいては、ネットワークに散らばる各ノードが貨幣鋳造所のかわりに働きます。そのため、コインが使用され、新たなトランザクションが生成されたら、分け隔てなく全てのノードに知らせなければならないのです。

トランザクションのブロードキャスト

ビットコインのノードの数は、最近では数千は下らないと言われています。一つのノードが直接つながることができるノードは、全体の一部にすぎません。例えば、図のようにアリスはボブとは直接つながっていますが、キャロルやテッドとは他のノードを介して間接的にしかつながっていません。

このため、トランザクションをブロードキャストするには、ノードからノードへバトンのようにリレー (relay) していくことが必要です。仲間と仲間がつながりあって協力することでブロードキャストが実現される、まさにピア・トゥ・ピアのネットワークなのです。

2) トランザクションの蓄積

2) Each node collects new transactions into a block.

2) 各ノードは新たなトランザクションを一つのブロックにまとめる。

ビットコインの各ノードは、ラウンド方式の分散タイムスタンプサーバーでしたね。各ノードは、ブロードキャストされたトランザクション一つ一つに対してつどつどタイムスタンプを発行するのではありません。複数のトランザクションをため込み、ブロックという単位にまとめてからタイムスタンプを発行します。

3) PoW

3) Each node works on finding a difficult proof-of-work for its block.

3) 各ノードはそのブロックの困難なプルーフ・オブ・ワークを発見すべくワークを行う。

本連載では、翻訳は原文の意味が通りにくい箇所も含めてなるべく逐語的に行い、解釈はその後の解説文で行うようにしています。この文は要するに、各ノードは PoW(プルーフ・オブ・ワーク) を行うということですね。「difficult」が余計な語に見えますが、難易度 (difficulty) の存在を意識しているのでしょう。

PoW の難易度は、あらかじめ決められた基準(平均1ブロック10分)に従い各ノードが決定します。不正な難易度を設定しても、あとで検査されてばれてしまいます。

4) ブロックのブロードキャスト

4) When a node finds a proof-of-work, it broadcasts the block to all nodes.

4) あるノードがプルーフ・オブ・ワークを発見したら、そのブロックを全てのノードにブロードキャストする。 ※3

PoW はくじ引きのようなものでしたね。アタリを引いたノードは、そのナンスなどブロックの情報をブロードキャストします。

これはラウンド方式のタイムスタンプにおいて、ビッグ・ラウンド・バリューを新聞に掲載するようなものですね。大勢の人にブロックを配達するわけです。異なるのは、ビッグ・ラウンド・バリューが生成したラウンド・バリューの一部であるのに対し、ブロックはどれも毎回ブロードキャストされることです。

5) ブロックの検査

5) Nodes accept the block only if all transactions in it are valid and not already spent.

5) ブロック内の全てのトランザクションが有効でかつ既に使用されていない場合に限り、ノードはそのブロックを受け入れる。

各ノードは、受け取ったブロックに関するさまざまな検査を行います。

一つは、もちろん二重使用の検査です。各ノードは、ブロードキャストされたトランザクションもブロックもだいたい全て把握しているはずですので、使用済みのコイン、つまり使用済みのトランザクションがあれば検出できるはずです。

他にはどのような検査を行うのか、初期のビットコインのソースコードをもとにいくつか挙げてみます。

  • トランザクションのコインの額がマイナス値になっていないか?
  • トランザクションの数は上限を超えていないか?
  • 難易度など PoW の検証結果は有効か?

各ノードは、こうした検査を全て通過した有効なブロックだけを受け入れ、無効なブロックは捨ててしまいます。

6) ブロックの受け入れ

6) Nodes express their acceptance of the block by working on creating the next block in the chain, using the hash of the accepted block as the previous hash.

6) ノードは、チェーンの次のブロックを生成すべくワークを行うことで、ブロックを受け入れたことを表現する。その受け入れたブロックのハッシュを一つ前のハッシュとして用いるのである。

PoW を競争ととらえると、ブロックを受け入れることは、そのブロックの作成者を競争の勝者として認めることを意味します。そして、今回の競争は終わりにして、またすぐに次のブロックをつなげる競争を開始することも意味します。

最長のチェーン

以上の六つのステップのうち、「3) PoW」や「6) ブロックの受け入れ」には一つ大事な約束事があります。

Nodes always consider the longest chain to be the correct one and will keep working on extending it.

ノードは常に最長のチェーンを正しいものとみなし、それを伸ばそうとし続ける。

各ノードは、ブロードキャストされたブロックをつなげつつ、自らも PoW を行いブロックのチェーンを伸ばそうとします。その際、どのチェーンを伸ばすかを、各ノードが好き勝手に決めるのは望ましくありません。サトシが決めたとおり、最も長いチェーンを伸ばすべきなのです。

最も長いチェーンがあるということは、二番目、三番目もあるということですね。二番目、三番目のチェーンはどのように扱えばよいのでしょうか?

また、もしも同じ長さのチェーンが複数ある場合はどうすればよいのでしょうか?それらが最長のチェーンの場合、どのチェーンを伸ばせばよいのでしょうか?

サトシは、そうした疑問に答えるべく、さらなるルールとして、ブロックは先着優先で処理すること、状況に応じて最長のチェーンに切り替えることを述べています。

ブロックは先着優先

If two nodes broadcast different versions of the next block simultaneously, some nodes may receive one or the other first.

もしも二つのノードが相異なる次のブロックを同時にブロードキャストする場合、どちらのブロックを最初に受け取るかはノードにより異なるかもしれない。

そのときどきのネットワークの状況次第で、ブロックを受け取る順番は、ノードによって異なる可能性があります。

例えば、先ほどのブロードキャストの図において、アリスとキャロルが同時にブロックをブロードキャストしたとします。その場合、ボブは直接つながっているアリスのブロックを、テッドはキャロルのブロックを、それぞれ先に受け取る可能性が高いでしょう。

では、中継するノードが少ない方が必ず早く受け取れるかというと、そうとも限りません。たまたま回線が混雑していたなどの理由で、ブロックが送られるスピードは変わるからです。

In that case, they work on the first one they received, but save the other branch in case it becomes longer.

その場合、各ノードは最初に受け取ったブロックに対しワークを行う。ただし他の枝も、長くなった場合に備えて残しておく。

複数のブロックを受け取った場合は、ひとまず一番最初に受け取ったブロックのチェーンを伸ばします。

ただし、後から届いたブロックも、今後のために残しておきます。そのブロックでチェーンを枝分かれさせておいて、のちのち受け取ったブロックたちによって、枝分かれさせたチェーンの方が長くなってしまう場合に備えるのです。

ブロックは先着優先

チェーンの切り替え

The tie will be broken when the next proof-of-work is found and one branch becomes longer; the nodes that were working on the other branch will then switch to the longer one.

この拮抗状態は、次のプルーフ・オブ・ワークが発見され、いずれかの枝がより長くなると解消される。他の枝でワークを行っていたノードはより長い枝に切り替える。

ブロックのチェーンを伸ばすのは、自身のノードだけではありません。他のノードから随時送られてくるブロックによってもチェーンは伸びていきます。

時には、他のノードから受け取ったブロックによって伸びたチェーンが、それまで最長だったチェーンを追い越すことがあります。そんなときは切り替えて、その新たな最長のチェーンを伸ばすようにします。

チェーンの切り替え

このように、各ノードは、そのときどきの最長のチェーンに随時切り替えながら PoW を行います。ネットワークの構成や、混雑具合などによって、各ノードが知っているブロックは随時変化していくからです。ビットコインのブロードキャストは、時間が経てば大多数のノードに行き渡るはずというものであって、全てのノードが同時に全てのブロックを共有することを保証するものではないのです。

論文ではこれをベストエフォート (best effort) と表現しており、第5章の残りは、そのようなベストエフォートでも問題ないという趣旨の説明が数行書かれています。

多数決による意思決定

さて、以上のような六つのステップを繰り返すことが、サトシのいう「たったひとつの順番に合意できるような仕組み」であり「多数派のノードが合意したことの証明」になるわけですが、それはなぜでしょうか?第4章「Proof-of-Work」に戻って、その理由を見てみましょう。

The proof-of-work also solves the problem of determining representation in majority decision making.

(ビットコインの)プルーフ・オブ・ワークは多数決による意思決定で代表を決める問題をも解決する。 ※4

唐突に、ここから数行は、まるで選挙制度という社会的な課題について語っているかのような表現が続きます。

If the majority were based on one-IP-address-one-vote, it could be subverted by anyone able to allocate many IPs.

もしも多数派というものが一IPアドレス・一票に基づくのであれば、多数の IPアドレスを割りふれる誰もがそれを覆せるはずである。

日本の選挙や、会社や学校で行う多数決では、一人・一票が常識のようになっているかと思います。

ビットコインで一人一票を実現するとしたら、一ノード・一票にすればよいでしょうか?一人につき一つのノードしか持てないのであれば、それでもよいでしょう。各ノードはそれぞれ固有の IPアドレスを持ちますので、一IPアドレス・一票 (one-IP-address-one-vote) で、一ノード・一票が実現できます。

けれども実際には、一人で複数のノードを持つことが可能です。一IPアドレス・一票にした場合、一人で複数のノードに IPアドレスを割り当てられれば、一人で多数派を形成することも簡単かもしれません。後で見るように、悪意を持った人が多数派を形成できれば、コインの二重使用も可能です。

こうした問題のある一IPアドレス・一票のかわりに、サトシは PoW を利用します。

Proof-of-work is essentially one-CPU-one-vote.

プルーフ・オブ・ワークというものは、本質的に一CPU・一票である。

まるで PoW 全般に通ずる法則、本質を発見したかのようですが、一CPU・一票という表現はあまり適切ではないように思います。次に述べるとおり、一人・一票から想像するような「平等」とは異なるものですし、また、CPU だけが「票」になるわけではないからです。

The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it.

多数決は最長のチェーンによって表される。最長のチェーンは、つぎ込まれたプルーフ・オブ・ワークの労力のうち最大のものを有する。

最長のチェーンとは、多数決で最も票を集めたチェーンなのだとサトシは言います。チェーンを伸ばすには PoW を行う必要があり、最長のチェーンには、他のどのチェーンよりも多くの計算資源がつぎ込まれているはずだからです。

つまりこれは、ビットコインの多数決では、ワークを行う処理能力が「票」であることを意味します。一CPU・一票と言われると、CPU 一つにつき一票を投じることができそうな感じがしますが、そうではありません。例えば、性能の低い CPU 一つを持つ人を二人合わせても、その三倍の計算力を有する CPU を持つ一人の方が、投じることができる票は多いことになります。

このことは、高度なハードウェアを投入できる資金や技術力を持った人が、より多く投票できることを意味します。一人・一票のように、財産や知識等にかかわらず、誰もが一票だけ持っているわけではないのです。

また、ビットコインの PoW は、CPU だけで行われるわけではありません。むしろ、時とともに、GPU や FPGA、ASIC と総称される専用装置など、CPU よりはるかに高速なハードウェアを用いることが主流となっていきました。この後も、CPU 前提の記述は出てきますが、頭の中では PoW を行えるもの全般に置き換えながら読み進めてください。

誠実なノードによる二重使用の防止

If a majority of CPU power is controlled by honest nodes, the honest chain will grow the fastest and outpace any competing chains.

CPUパワーの大多数が誠実なノードによって制御されるならば、誠実なチェーンが最も速く伸び、他の競合するチェーンを上回るだろう。

誠実な (honest) ノードが、CPUパワーを豊富に持つという意味での多数派なら、それらが伸ばしている誠実なチェーンが、ネットワーク上に存在する他のどのチェーンよりも長くなると言っています。

なぜかハッキリ書かれていないのですが、その誠実な最長のチェーンこそが、サトシが必要とした、多数派のノードが合意したことを証明できるトランザクションのたったひとつの順番だというわけです。

To modify a past block, an attacker would have to redo the proof-of-work of the block and all blocks after it and then catch up with and surpass the work of the honest nodes.

過去のブロックを書き換えるには、そのブロックとその後のすべてのブロックに対して、攻撃者はプルーフ・オブ・ワークを再実行し、その後で誠実なノードのワークに追いつき、追い越さなければならないだろう。

誠実なノードとは何かについても、サトシは明確には説明していませんが、攻撃者 (attacker) とは異なるノードを指していることは明らかでしょう。ここでいう攻撃者とは、二重使用を試みるノードのことです。

二重使用を行うには、攻撃者はまず、第3回で見たように使用済みのトランザクションのチェーンを枝分れさせます。さらに、その二重使用のトランザクションを含むブロックを新たに作って、ブロックのチェーンを枝分れさせます。

二重使用の試み

上の図では、ボブへコインを譲渡したトランザクションを含むブロックのチェーンが最長です。同じコインを、攻撃者はアリスへ譲渡し、ブロックのチェーンを枝分れさせています。

ここから攻撃者は、PoW を素早くこなして、枝分れさせたチェーンを伸ばしていきます。下の図のように、最長のチェーンになるまで伸ばせれば、ひとまず二重使用成功です。 ※5

二重使用の成功

こうなると、ボブへの譲渡は無効とみなされ、かわりにアリスへの譲渡が有効となってしまいます。もしもボブがコインと引き換えに、攻撃者に商品等を渡し終えていたら、ボブは損してしまうわけです。

We will show later that the probability of a slower attacker catching up diminishes exponentially as subsequent blocks are added.

後で明らかにするが、(誠実なノードより)遅い攻撃者が追いつく確率は、後続のブロックが追加されるにしたがい急激に減少する。

このような二重使用の試みは、チェーンが伸びるにしたがい、ほぼ成功することはなくなります。今後も誠実なノードが多数派であれば、ワークをこなす力に劣る攻撃者が、誠実な最長のチェーンを追い抜くことは、確率的にほぼありえないからです。このことは、第11章「Calculations」で詳しく説明されます。

悪魔は細部に潜む

ところで、以上のようなサトシの説明を一目読んで、なるほどよく分かった、この仕組みはきっとうまくいく、と確信できた人はどれほどいるでしょうか。

そのように確信できなくても、特に不思議はありません。

ビットコイン論文の発表から二日後、メーリングリストで初めて反応を見せたのは、古くからのメンバーと目されるジェームズ・ドナルド (James A. Donald) でした。ドナルドは、直前に発生したリーマン・ショックもからめながら、いくつも鋭い指摘を行っています ※6 。中でも正常時の説明が不十分だという指摘は、ハル・フィニーも同意しているように的確なものと言えるでしょう。

攻撃された時の分析を繰り返すサトシに対し、問題はそこではないとドナルドは言います。正常時に全てのノードが共通の認識を持つに至るまでの過程を十分に説明できるまでは、攻撃された時のことについては語れないと言うのです。

ドナルドは、「神は細部に宿る」ならぬ「悪魔は細部に潜む (the devil is in the little details ※7)」という警句も持ち出しています。概要としては良いが詳細を詰めないと危険だというわけです。

その警句に対し、サトシは「詳細は一年半コーディングしながら詰めた (I believe I’ve worked through all those little details over the last year and a half while coding it, and there were a lot of them.)」と応じて譲りません。

「honest」の意味

そうは言っても、サトシ自身もまた、ドナルドが指摘するように正常時の説明が不十分だと感じていたかもしれません。

あるメールでサトシは、攻撃者が誠実なノードに変化する可能性にふれる中で、「"honest" よりもっと良い用語が必要だ (I need a better term than “honest”)」と述べています。

「honest」という形容詞は、セキュリティや分散処理の領域では普通に出てくる言葉であり、この言葉を採用したこと自体は、特におかしなことではありません。ただ、「honest」の意味や「attacker」との区別が、ビットコイン論文では明確には示されておらず、暗黙の了解のようになっていることもたしかです。

誠実なノードと攻撃者の区別

実際のところ、誠実なノードと攻撃者は、それほど明確に区別できるものではありません。

気付いたかもしれませんが、先ほどの先着優先やチェーンの切り替えの図と二重使用の図は、ほとんど同じです。直感的に、誠実なノードと攻撃者の動きには共通のものが多いことが分かるかと思います。

例えば、攻撃者は二重使用を成功させるために、誠実なノードによる検査を通過できる「正しい」トランザクションやブロックを生成します。検査を通過できないおかしなデータを作るわけではありません

攻撃者のチェーンが誠実な最長のチェーンを追い抜くと二重使用成功なわけですが、すると誠実なノードも切り替えて、攻撃者のチェーンを伸ばそうとします。そうした動きは、サトシが決めたルールに反するものではありません

攻撃者が問題なのは、最長ではないチェーンを意図的に伸ばしていることです。しかし、誠実なノードも、最長ではないチェーンを伸ばしていることはあります。チェーンの切り替えを行う直前がそうですね。ブロックを受け取っておらず知らなかったとはいえ、切り替えたということは、他の誠実なノードが伸ばしている最長のチェーンとは異なるチェーンを伸ばしていた可能性が高いのです。

最長ではないと知っていて伸ばしているのか、知らずに伸ばしているのか、各ノードにいちいち聞いて回るわけにはいきません。また、聞いたところで、攻撃者が正直に答えるはずもありません。

ノードの外からも観察できるデータをもとに不審なノードをスコアリングする機能を導入するなど、改良が進められてはいますが、どのノードが誠実でどのノードが攻撃者なのか、100%確実に判定することは、技術的には困難でしょう。

「誠実な」人間

誠実なノードと攻撃者を区別し、誠実になることを強制することが技術的に困難であるならば、ネットワークの多数派が誠実なノードであるかどうかを左右するのは、ノードを運営する人間ということになるでしょう。

今回見てきた誠実なノードのふるまいは、あらかじめサトシが決定し、ソフトウェアとしてプログラミングするものです。そのサトシのソフトウェアを利用する「誠実な」人間が、二重使用問題を解決するためには不可欠なのです。

ノードの視点からは、二重使用問題を解決するためには、トランザクションのたったひとつの順番に合意することが必要と言えるでしょう。しかしノードはあくまで、ノードを運営する人たちが受け入れ、共有しているルールに従って動いているだけです。人間の視点からは、二重使用問題を解決するためには、CPUパワーを豊富に持つという意味での多数派の人たちが、あらかじめルールに合意している「誠実な」人たちであることが必要と言えるでしょう。

おわりに

今回は、第5章「Network」を読みながら、ビットコインの P2P ネットワークの仕組みについて見てきました。また、第4章「Proof-of-Work」を読んで、なぜその仕組みで二重使用を防げるのかも説明しました。

ブロックチェーンは、簡易な説明ではデータベースの一種とされることがありますが、データベースは P2P ネットワーク上に散らばっているという点を無視するわけにはいきません。

ビットコインのネットワークの仕組みは複雑であり、論文でも十分に説明されているとは言い切れません。「honest」という単語一つとっても、「attacker」との区別が難しいなど、論文では語られていない要素が見え隠れしています。

次回は、論文の内容を補足すべく、具体的な事例を通じて、ネットワークの仕組みについてさらに詳しく見ていく予定です。


※1: 原文は「It’s basically just a new kind of database.」。その後、「トラスト (trust)」を持ち出して説明は続きます。

※2: 論文中で「合意」と訳せそうな単語が出てくるのは、第2章の「agree on」「agree(d)」と、第12章「Conclusion」の最後の言葉「consensus (mechanism)」の三回です。ブロックチェーンでよく出てくる「consensus algorithm(コンセンサスアルゴリズム/合意形成アルゴリズム)」という言葉は、論文には出てきません。

※3: この文のように「proof-of-work」という言葉は、プロトコルとしてだけでなく「アタリ」としても使われます。

※4: 「representation」を「表現」と訳すべきか悩みましたが、いずれにせよ、多数派の意思を PoW を利用して表すことの説明がしたいのでしょう。

※5: 取引の当事者同士のとり決めなどによって異なります。

※6: ドナルドは、ビットコインはビザンチン将軍問題 (Byzantine Generals Problem)のような古典的な分散データ処理の難問を抱えているとも指摘しています。対してサトシは、「PoW のチェーンはビザンチン将軍問題を解決する。(The proof-of-work chain is a solution to the Byzantine Generals’ Problem.)」と応じていますが、その説明は、サトシ自身も「rephrase(言い換える)」と表現しているように、基本的には「ノード」を「将軍」に置き換えて第4, 5章をなぞっただけに見えます。また、ビットコイン論文には、ビザンチン将軍問題という言葉は出てきません。

※7: 「little」が無かったり「the/a」「detail/details」などいくつかバリエーションがあります。

参考資料