読者です 読者をやめる 読者になる 読者になる

たなかこういちの資料室

システム開発に携わる筆者があれこれ試したことや学んだことについてのまとめ

ビットコインとブロックチェーンについて、その1

ビットコインとブロックチェーン、*冬休み*に調べてみました。現時点(※2016年1月上旬)での私の理解を記します。
 
※私の理解を記しているので、誤りやあまり正しくない説明が含まれている可能性があります。
 
 
「仮想通貨」と称されるようですが、実態としては「P2P決済システム」と認識するのがよさそうです。もう一段掘り下げるならば、、
 
「取引」の正当性を、第三者機関に依存せずに、ネットワーク上で相互に信任し合あえるようにした仕組み
 
であり、それを「通貨の取引」、即ち決済に適用したのが、アプリケーションとしてのビットコインである、と理解されます。繰り返しになりますが、重要なポイントは、第三者機関が無くても確かな取引を成立させられる仕組みを考案した、という点です。
 
なお、「ビットコイン」という用語は、下記の意味で用いられています。
 
(1) P2P決済アプリケーションとしてのビットコイン
 
(2) (1)のシステムのオープンソース実装の名前としてのビットコイン
 
ビットコインの実装はOSSとして公開されています。下記GitHubリポジトリーにて保守されています。(ちなみに中核はC++で実装されています。)
 
 
(3) (1)のアプリケーションで流通する“通貨単位”としてのビットコイン
 
ビットコインの仕組み
 
P2P決済システムを運用する上の要点、つまり、P2Pで「取引」の相互信任を可能とするための技術上の要点は、次の2点に集約されるとのことです。
 
(1) 本人性保証
(2) 多重取引が為されていないことを如何に保証するか
 
ビットコインでは、下記技術でこれらを解決しています。
 
(b) ブロックチェーン
 
(a)は本人性確認に用いられます。ビットコインにおいて公開鍵は、ビットコイン参加ノードの「アドレス」そのものとして扱われます。「アドレス」とはビットコインの“口座”に相当します。ビットコインの取引は、「送金人のアドレスから受取人のアドレスへ、Xの量のコインを移管する」、という形式で表現されます。この取引依頼(の電子データ)が送金人の秘密鍵によって電子署名されていることで、確かに送金人本人による取引依頼である、と確認されます。
 
公開鍵暗号による電子署名による本人性保証は、インターネット上のサービスにおいて既に広く使われている技術です。正当性を確認するには、取引依頼のデータを送金人の公開鍵でデコードします。正しくデコードできるということは、確かに送金人の秘密鍵エンコードされたのだ、と云えるのです。注意点として、電子署名(自体)は、データが確かに本人によって作成されたものであり、かつ途中で改竄されていないことを保証するものですが、データの内容を秘匿するものではありません。ビットコインにおいても、取引データは完全公開されています。
 
そして(b)について。一般に、多重取引が為されていないことを証明するためには、有効取引の全履歴を保全する、という手だてを取るしかありません。(※その全取引履歴に含まれていない取引は、存在しない取引である、と認識されます。)その全取引履歴保全のために、一般には、取引参加者全員が信頼する第三者機関を設ける必要があります。
 
ビットコインのネットワークは2009年に運用が始まっていますが、ビットコインにおけるブロックチェーンには、2009年からの全取引履歴が記録されています。この全取引履歴は、ネットワークに参加している全ノードが保持しています。新しい取引依頼は、既存のブロックチェーンに新しいブロックとして追記されることで“確定”します。
 
※実際には複数の取引依頼がまとまって一つのブロックとなるようですが、技術詳細として無視し、ここでは、おおよそ一取引が一ブロックであるとして理解しておきます。
 
ブロックチェーンは、ビットコインP2Pネットワークにおいて為された全取引の履歴を改竄不可能な状態で保全するための仕組みです。P2Pにおいて全取引履歴の保全が可能となったことで、P2Pで多重取引が為されていないことの保証が可能となりました。
 
ブロックチェーンは、中央の第三者機関に依らずに、取引の順序性の決定と取引履歴を改竄不可能とする仕組み、即ち、第三者機関に依らずに多重取引を否定できる仕組みを、初めて実現しました。この点がブロックチェーンが、革命的革新性をもつ発明だとされるところです。
 
“Satoshi Nakamoto”氏
 
2008年、Satoshi Nakamotoを名乗る人物が、暗号理論に関するメーリングリストに「Bitcoin: A Peer-to-Peer Electronic Cash System」と題される論文をポストしました。
 
 
ブロックチェーンの仕組みとそれに基づくビットコインという発明について説明する論文です。
 
Satoshi Nakamoto氏のリアルワールドにおけるアイデンティティーは特定されていません。「Satoshi Nakamoto」という名も偽名であると認識されており、個人かグループか日本人なのかどうかも不明、とされています。
 
Nakamoto氏はその後、ビットコインオープンソース実装に寄与し、ビットコイン・ネットワークの運用を開始、現在では"genesis block"と称されるブロックチェーンの最初の1ブロックを生成しました。
 
2010年12月に最後の投稿をして以降、“Satoshi Nakamoto”氏の(表立った)活動は停止しているそうです。
 
ブロックチェーンの仕組み
 
ビットコインにおけるブロックチェーンには、ビットコイン・ネットワークの運用が始まって以来の全取引履歴が記録されています。新しい取引依頼は、既存のブロックチェーンに新しいブロックとして追記されることで“確定”します。
 
※実際には複数の取引依頼がまとまって一つのブロックとなるようですが、ここではおおよそ一取引が一ブロックであるとして理解しておきます。
 
ここで、ブロックを一つ伸長するためには、ビットコインのネットワークに参加している全ノード(=コンピューター)のCPUパワーを投入して10分程かかる処理の結果が必要なように設計されています。10分ほどかかる処理とは、具体的には特定のハッシュ値の入力値を探すという処理です。
 
ハッシュ値から入力値を得るには総当たりで探すしかありません。対して、入力値からハッシュ値はミリ秒で算出できます。ハッシュ値から入力値を探すのに時間はかかりますが、それが正しいかどうかの検証は一瞬で終わります。
 
この“Proof of Work”と称される、ハッシュ値に対する入力値探しというCPU負荷は、下記2点の実現に寄与しています。
 
(1) 新しいブロックの追記が、確率的に1ノードだけが実施できるようにする
(2) 一旦ブロックが伸長されたブロックチェーンの改竄が、確率的に不可能と云える状態を作り出す
 
 
(1)について。ビットコインP2Pネットワークでは、マネージャーあるいはコーディネーターといった特別なあるいは特権的なノードは存在しません。ブロックチェーンの伸長は、どのノードでも自由に実施できます。ノードは、ブロックチェーンの伸長のために、次の様な処理を実施します。
 
1. ネットワークにプールされている未処理の取引依頼から任意の1つを選びます。
 
2. そして既存の全取引履歴を走査して、送金人にその能力があるか、つまり取引依頼に対して残高が足りているか検証します。
 
3. 問題が無ければ、取引依頼を組み込んだ新しいブロックを作成し、既存のブロックチェーンに追記します。
 
4-1. ところが「3.」を実施するには、ハッシュ値に対する入力値探しを実施しなければなりません。ここで、ネットワークに参加している全ノードが競争的に“答え探し”を始めます。
 
4-2. “お題”の難しさ=平均的に必要とされる計算量(時間)は、常に約10分となるように、前回正答を得るに要した時間に基づき、ビットコイン実装のアルゴリズムが自動的に調整します。
 
※ノード数が増えたり、ノードあたりの計算速度が速くなったりしたら、それに応じて必要とされる計算量が増やされます。
 
4-3. 結果として、確率的に10分間に1ノードだけが正答にたどり着けるように、常に“お題”は調整されます。
 
4-4. 例えば、ノードXが取引依頼T1を追記しようとしていて、ノードYが取引依頼T2を追記しようとしているとします。両方の追記処理が同時に成立してしまっては一貫性が破綻します。しかし、確率的に10分間に1ノードだけが追記できるので、ノードXが正答を探し当てて追記に成功したとき、ノードYは確率的に追記はできていない、と云えるのです。
 
4-5. ノードXが正答を探し当てて追記に成功した場合、ノードXは、正答を用いてブロックの伸長をおこなったブロックチェーンをネットワークにブロードキャストして、「これが今回ターンの追記だ。皆受け入れろ!」と宣言します。
 
5. 未だ正答を得られていないノードYは、ノードXからの通達を受け取ったならば、自分の答え探し作業は中止して、ノードXの通達の内容の正当性を確認します。
 
※確認はいとも簡単で、ノードXの云う正答たる入力値を以って、“お題”のハッシュ値が確かに得られるか計算するだけです。ハッシュ値から入力値を探すのに時間はかかりますが、入力値からハッシュ値はミリ秒で算出できます。
 
6. 正当性が確認されたならば、伸長された新しいバージョンのブロックチェーンを受け入れ、ノードが保持する全取引履歴たるブロックチェーンのローカルコピーを更新します。
 
以上のような処理において、仮に、取引依頼T1とT2が共に送金人Zによるもので、送金人Zの残高的にT1とT2のいずれか一方しか執行できないような状態だったとします。つまり、送金人Zが多重取引を試みた、という状況です。ノードXとノードYがそれぞれT1とT2を正当な取引として“確定”させようと努力を始めたとします。XとYの“努力”がほぼ同時に成就してしまうようでは、多重取引の成功となってしまいます。しかし、確率的に10分間に1回だけ努力が成就するように調整されているので、XかY、つまりT1かT2のいずれか一方だけが、結果的に正当な取引として確定されるのです。次のターンで、T2かT1、先ほど確定されなかった方の取引依頼の確定が試みられたとしても、既にT1かT2の執行が確定した後の全取引履歴に対しての追記となるので、残高不足で拒否されます。
 
ここで、T1とT2の間の順序性はどうなるのか?という疑問が湧きます。ビットコイン(ブロックチェーン)では、同一の送金人が出した複数の取引依頼の間の時間順序は無視します。つまり、取引依頼が出された順序通りに執行されるかどうかは決定されていません。代わり、ではありませんが、取引依頼毎にある種の執行の優先度付けができます。取引依頼の発順というより、こちらの優先度に従う、という理解です。
 
 
(2)について。(1)の処理手続きにて、ハッシュ値に対する入力値探し、その“お題”と“答え”、という話をしました。このとき実際に探すのは、入力値そのものではなく、前回ブロック伸長時の“お題”たるハッシュ値を、所定のルールで入力値の一部として用いた場合の、入力値の残りの部分を探す、というものになっています。それが数珠つなぎになっている訳です。これがブロックチェーンのチェーンたる所以です。
 
ブロックチェーンのこの構造により、例えば3ブロック前の改竄を試みようとした時、“お題”3回分をやり直す必要が出てきます。“お題”3回分のやり直しには、ビットコイン・ネットワーク参加コンピューターの全CPUを投入して約30分かかる、という見積もりになります。(※この10分×3の演算をサボって作成したブロックは、ミリ秒で不正だと判定され、ネットワークから除去されてしまいます。)その間もビットコイン・ネットワークの本体も稼働しているので、正規のブロックチェーンも次々伸長していきます。つまり、正規のブロックチェーンを置換できるような偽造ブロックチェーンを後から作成しようにも、一般には追いつくことができないのです。計算では、ビットコインのネットワークに参加している全CPUパワーの51%を調達できれば、追い越し可能=偽造可能とされています。
 
分散合意
 
P2Pで相互信任する」という話は、コンピューターサイエンスにおいて「分散合意」といわれるテーマの一環と捉えられるとのことです。
 
※「合意」といっても、コンピューター同士の合意の話です。複数のコンピューターのノードが、ある時刻において、ある処理が実施されたか、それともされていないかについて、どうやって同じ“認識”を持つのか、というテーマです。少し形式的には、「複数のノードがそれぞれローカルに持つ状態遷移マシンが、同一の状態であることを維持するためのプロトコル」、といった感じになるようです。
 
「分散合意」というと「Paxos」やその簡略・改良版たる「Raft」といったプロトコルが、デファクト標準の地位にあるようです。
 
ビットコインのブロックチェーンは、分散合意プロトコルの一種である、とみることができます。
 
Paxos/Raftとブロックチェーンを比べると、技術的課題の捉え方において共通性が見られます。
 
・同時並行に発せられるリクエストを如何にシリアライズするか(=適用順序をどのように決定するか)
・代表者選出の問題
シリアライズ結果をログとして保管する
・ログを全ノードに同期させる
 
対して、(本記事執筆時点では、Paxos/Raftについてはほぼ何も調べてませんので、完全に単なる想像ですが、)Paxos/Raftではさすがに確率的に処理するような手立て取ってないのではないでしょうか。
 
ブロックチェーンは、
・ネットワーク全体が稼働し続けること
・大半の参加者は一般に良心的であろうということ
を前提に、P2P相互信任を確率的に達成しています。
 
 
参考文献
 
◆以上
(※その2へ続きます。)