(ビッドコインの原論文)「演算量証明(プルーフ・オブ・ワーク)」という考え方

ビッドコインの原論文の日本語解説にて「ブロックチェーン」をスタディした際のメモ
下記のサイトが大変参考になった。

ビットコインの原論文を読む

http://kogarashi.net/pitchblende/wp-content/uploads/2014/03/BitcoinWhitepaperJapanese.pdf
ビットコイン自体は、Mt.Gox閉鎖騒動などがあり、電子通貨システムの今後は不透明です。
ビットコイン以降、ライトコイン、フェザーコイン、モナーコインなどの後継が続々と登場しています。
電子通貨が本格的に普及するとしたら、そういった改良版、またはその後継、あるいはさらに何代か後のコインが主役になると思われます。

しかし、論文の「演算量証明」という考え方はいろいろと応用が広そうです。

例えば経理の分野で、台帳をハッシュ化してタイムスタンプを作っておけば、後で偽造したものではないことを示せます。
創作物も、作った時点でその証拠を取っておけば、盗作騒動を避けられます。
遺言状に利用すると、信頼性が大いに増すでしょう。
問題は、誰がその演算証明を行うかですが、上手く受益者からノード稼働者に報酬が伝わるようなシステムを作れるとよい。
ビットコインに対する批判として、何の役にも立たない無駄な計算に電力が使われているというものがあります。
省エネが叫ばれているご時世に、これに関しては反論の余地がありません。
何とかして、白血病解析やSETI@HOMEのような分散コンピューティングの問題を組み込めれば、通貨システムを維持しながら社会の役にも立ち、理想的です。

特徴

P2P
金融機関のような第三者機関が無くとも二者が取引を行える。
そのために「信頼」ではなく「暗号技術」に基づいた支払いシステム
当事者同士で行うことでの低コストでの為替取引が可能

非可逆的取引
支払人が確実に相手に送金できることが保証された現金同様に非可逆的取引である。
支払いをキャンセルする仕組みはない。
買った商品が不良品だったり、振り込め詐欺の場合でも現金同様支払い先の相手の了承がないかぎり戻ることはない。
そのような対処が必要な場合は、通貨の枠組みの外側でやる。

悪意による改竄がされない仕組みが導入されている
取引履歴に残された時刻を計算理論で検証すれば、通貨を多重には使用されなくなる。
そのために、P2P分散タイムスタンプサーバを利用する。
善良なノード群が、攻撃者のノード群よりもCPU能力で上回ることでシステムセキュリティの安全が保たれている。

2節 電子通貨のやり取り

コインの使用履歴そのものをコインと定義する
コインを送る=「利用者1の秘密鍵」にてに「署名」をすることで、利用者1から利用者2へコインを送るアクションそのものとなる。

ハッシュ化
数値や文字列を「暗号学的ハッシュ関数」に通すこと。
暗号学的ハッシュ関数とは、「xが分かればf(x)は簡単に求められるが、yが分かってもf(x)=yとなるxを求めるのは非常に難しい」ような関数fのこと。
ビットコインでは主にSHA-256のを使用する。
これにより、単に取り扱うデータサイズを小さくできる。
ビットコインでは、取引の操作では、小さいサイズのハッシュ値を使い、検証する時だけ元データを使うことで、効率が良い。

多重取引の防止方法
ビットコイン以前の解決法は、信頼できる「造幣局」がすべての取引を監視し、多重使用がないことを保証する。
取引が成立するたびにコインは造幣局に返され、新たなコインが発行される。造幣局が直接発行したコインであることが、多重使用されていないことの証明となる。
これは、すべての取引を造幣局経由で行うのと同じで、金融システムの命運が造幣局を運営する組織に左右されるという、銀行と同様の問題を含んでいる。
ビットコインでは、過去の所有者の誰もがコインを他に使用していないことを、受取人が検証することを保証した。
コインが多重に使用された場合は最初の取引だけを有効とし、それ以降の取引は無効であるとする。
このように取り決めておけば、すべての取引を調査し、自分の取引が2番目以降でないことを確認すれば良い。
全取引が公開され、それを元にした同一の取引履歴を、利用者全員が共有しているようなシステムを構築する。
受取人は取引のたびに、コインが他人に送られていないことについて、ノードの大多数が認めるか否かを確認する。
もしかしたら、悪意を持った人物が偽の取引履歴をネットワークに流すかもしれない。
そのように各人が異なる取引履歴を主張している場合は、一種の多数決採決が行われる。

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

タイムスタンプサーバの目的は、ある時間に、あるデータが存在したことを証明すること。
これは、信頼できる中央機関があれば容易に実装できます。
「○時○分に○○というデータ(のハッシュ値)が存在したことを証明する」という文書を、電子的に署名して配布すれば良い。
ビットコインのように、中央機関が無い場合にある取引がある時刻に行われたこと証明する方法を検討する必要がある。
ビットコインでは取引時刻をそれほど厳密には扱いません。「ビットコインでは取引に10分程度の時間がかかる」。
つまり、およそ10分以内に為された2つの取引は順序が入れ替わる可能性があるため、多重取引ではないと下した判定がその間に覆る可能性がある。
取引時刻の曖昧さを許した代わりに、即時性が多少犠牲になっている。
分単位での時刻証明は得られなくとも、24時間前に確認したはずの取引が突然無効になるという事態は避けるためビットコインでは、「世界中のコンピュータを集めても、24時間かけて計算しな

くては作れないようなデータ」を作ることで解決している。(演算量証明)

4節 演算量証明(プルーフ・オブ・ワーク)

アダム・バックのハッシュキャッシュは、電子メールによるSPAM(迷惑メール)を防止するために考案されたシステムです。
例えば、すべてのメールシステムが「演算を1秒間実行した証拠が付属していなければメッセージを受け取らない」というポリシーで作られていたとする。
するとSPAM業者は、1秒間に1通以上はメールを送れなくなり、何百万通のSPAMを一斉配信などができなくなります。
この演算量証明の実装を応用しビットコインでは、「全参加者が協力して平均で10分かかる問題」を解きます。
演算量証明をチェーンでつなげることによって、例えば24時間前の取引データには、24時間分の演算量証明が重ねられている。
例えば「SHA-256のようなハッシュ関数を通すと最初のnビットがすべて0となるような値」を総当たりで発見することによって実現できる。
そのような演算にかかる平均時間は、nに対して指数関数的に増大する。
ビットコインでは、ブロックデータとNonceと呼ばれる数字を組み合わせる。
Nonceを適当な値から1ずつ増やし続けて、ハッシュ値の最初のnビットがすべて0になる場合を探索する。
このようにCPUを使って演算量を証明しておけば、ブロックの内容を改ざんして辻褄を合わせるためには、同じ計算をもう一度行わなくてはならなくなる。
さらにその後ろにブロックがチェーンでつながっていたら、それらすべてに対する演算をやり直す必要がある。
これにより、「世界中のコンピュータを集めても、24時間かけて計算しなくては作れないようなデータ」となっている。
演算量を証明することにより、集団における意思決定をどう行うべきかという問題も解決する。
多数決方式を採用し各IPアドレスに1票ずつを割り当てるような方法では、誰かがIPアドレスを大量に確保した時点で制度が崩壊してしまう。
それに対して、演算量証明に基づく本システムは、各CPUに1票を与えるようなものである。
実際には、最もCPU能力を費やして作られた情報、すなわち最も長いチェーンを、集団の意思決定の結果であると取り決める。
CPU能力の大多数が善良なノードによって構成されていれば、不正がないチェーンが最速で成長し、ねつ造した情報を含むどのチェーンよりも長くなるはずである。
もし、攻撃者が過去のブロックを改ざんしようとしたら、それ以降のブロックをすべて計算し直し、善良なノード群が計算するチェーンの長さに追いつき追い越す必要がある。
年月が経つと、ハードウェアの速度が向上したり、世間の注目度合いによって参加ノード数が変動したりするだろう。
生成されるブロック数がそのような影響を受けないように、演算量証明の難易度(difficulty)が、過去一定期間の生成ブロック数をもとに設定される。
ブロックの生成間隔が短すぎる時には、難易度が高くなる。

「ノード」とは、ビットコインでは、「採掘」を行っているPCやサーバ、専用マシンなどを指す。
ただし、現在は参加者の増大により、一人でブロックを発見できる確率がほとんど0になったため、プール(共同採掘場)に登録して採掘していることが多い。
プールはプール全体で見ればノードですが、協力している各PCだけでは、ノードとは言えない。
各PCはハッシュ関数を総当たりで試しているだけで、チェーンのデータを持っていない。
つまり、現在は集団ではなくプールの管理者に大きな権限が集中している。
これは、ごく小数の管理者が悪意を持ってネットワークを崩壊させる可能性があり課題である。
difficultyは、ハッシュ値の最初の何ビットを0とするNonceを見つけるかで調整します。
平均で10分に1つのブロックを生成するというのは、これで設定する。

5節 ネットワーク

ビットコインでは、最終的に全参加者が一つの取引履歴を共有する。
また、誰かが不正な取引をネットワークにねじ込もうとしても、ノード間で多数決投票(のようなもの)が行われ、少数派は負けます。
本ネットワークは、次に示すステップで動作する。

1.取引を行うと、その情報がすべてのノードに広められる。
2.各ノードは、取引情報を集めてブロックを生成する。
3.各ノードは、ブロックに対する演算量証明を開始する。
4.演算量証明に成功した最初のノードは、そのブロックを全ノードに広める。
5.各ノードは、ブロックを、多重使用が無く正しい取引だけを含むことを確認して、受け付ける。
6.各ノードは、受け付けたブロックのハッシュ値を埋め込んで、次のブロックを生成し始める。これが、ブロックを受け付けたことの表明ともなる。

各ノードは、最も長いチェーンのみを正当なものと見なし、その最終ブロックから演算量証明を開始して、さらにチェーンを伸ばそうとする。
2つのノードが、内容の異なるブロックを同時に広めている場合は、受信順序の食い違いにより、演算量証明の対象チェーンが集団で統一されていないかもしれない。
その場合、各ノードは演算しない側のブロックも保存しておく。
この引き分けの状況は、次に誰かが演算を終えチェーンを伸ばしたときに解消する。
演算量証明に負けた側のチェーンを計算していたノードは、長いチェーンに乗り換える。
取引情報は、必ずしも全てのノードに行き渡る必要は無い。
一定数のノードに情報が届き、ある程度の時間が経てば、ブロックに取り込まれるからである。
ブロック化された後も、多少の通信障害には耐えて拡散する。
ノードがブロックを受信できなかった場合は、次のブロックが届いたときにそのことを知り得るので、欠けたブロックを他のノードに要求できる。

取引は、不正がないかどうか2段階でチェックされます。
1段目は各ノードがブロックを生成する過程で、整合性がない取引がブロックに入るのを防ぎます。
しかし、ノード自体が不正を行ったらどうなるか。
それが2段目で、不正な取引を含むブロックをどこかのノードが生成しても、他のノードは受け付けません。
でたらめな取引を全体に拡散させるのは、ほぼ不可能でしょう。
ただしノードは、自分が支払った取引を無効にすることが可能です。
例えば、その送金以前に、ダミーのアドレスに対して全額を送金したというデータを作れば良いわけです。
ですから、受取人はブロックが生成されるまでの10分間、さらに安全を期すなら、不正ノードの演算量証明が追いつけなくなるだろう数十分間を待って、取引を確認すべきです。
なお、どれほどCPU能力を持つノードでも、他人が自分に大金を支払ったというように取引情報をねつ造するのは、不可能です。
取引データを作るには支払い側の秘密鍵が必要だからで、それが無い場合署名を検証できず、2段階のうちいずれかで却下されます。

6節 ネットワーク参加者への報酬

ビットコインのシステムは、誰かが演算量証明を行うことにより成り立ちますが、演算量証明には電気代などのコストがかかります。
コストを嫌がって誰もコンピュータを動かさなかったら、僅かなCPU能力でビットコインの世界を乗っ取れてしまいます。
ではどうするか。そこも考えてあります。

ブロックの最初には、特殊な取引が記述される。
ここに書かれるのは、コインが新たに生まれ、それをブロックの生成者が所有したという情報である。
ブロックの生成者にコインを与えることは、各ノードがネットワークを維持する動機となり、また中央機関が権力を使ってコインを配分する代わりの枠組みともなる。
新たなコインが一定量ずつ生まれることは、金鉱採掘に例えれば、資金を投入して金を採掘し流通に乗せることに該当する。
資金に当たるのは、本システムではCPU時間や電力である。
コインの生成者は、報酬として取引手数料も受け取れる。
これは、取引上の受取額を支払額よりも少なく設定できれば良い。
その取引を含むブロックを生成した者が、差額を手数料として得る。
将来、決められた全枚数のコインが流通に乗った暁には、インフレから解放された状況が出来上がるが、それ以降は取引手数料がブロックを生成する動機となる。
報酬には、各ノードが不正を働かないように動機付ける役割もある。
もし、欲張りな攻撃者がCPU能力を集め、善良なノード群のそれを上回ったとする。
攻撃者はその能力を、自身が支払った額を奪い戻して横領するか、真っ当な方法で新たなコインを生成するかのどちらかしか選択できない。
この場合、ルールを破り通貨システムと自身が持つ価値を崩壊させるよりも、ルールに従って、新たに生まれるコインの過半数を得る方が賢明だと、判断するだろう。

「善良なノードが大多数ならばシステムが上手く働く」という理屈を各自が理解しても、電気代やハードなどのコストを費やして演算量証明を実行しようとは思わないでしょう。
報酬に釣られて多数の人がPCを動かすからこそ、結果的に不正が難しくなるわけです。
各自が利己的な選択を行っても上手く働くシステムというのは、作るのが難しいものです。
ビットコインでは、むしろ参加者が利己的に動くことを利用して、ネットワークのセキュリティを確保します。
「コインの最初の所有者をどう選ぶべきか」という問題もこれで解決するわけで、実に巧妙な仕組みです。

手数料の決定権は送信者側にある。
そしてブロックの生成者は、手数料が低すぎだと思ったら、その取引をブロックに入れなくて良い(次のブロック生成者に先送りする)とされている。
もっとも、ビットコインのソフトウェアでは、ほとんどが推奨の額で固定されていて末端ユーザは変えられない。
これが変えられるようになると、ゲーム理論的に面白そうです。

7節 使用ディスクスペースの節約

コインの取引履歴が十分な数のブロックに埋め込まれたら、使用ディスクスペースを節約するために、古い履歴を消去しても構わない。
ブロックのヘッダー部分の大きさは約80byteである。
従って、ブロックを10分間に1個ずつ生成する場合、1年間に80byte×6×24×365=4.2MBが必要になる。
2008年現在、一般的なPCは2GBのRAMを搭載して販売されており、ムーアの法則によればこれが1年間に1.2GBの勢いで成長している。
そのため、ヘッダー部分だけならば、すべてのブロックをメモリに格納できるだろう。
ハッシュ木は、末端のデータからハッシュ値を積み上げて、全体のハッシュ値を決める方式です。
ハッシュ木を使う利点は、データを削除しても全体のハッシュ値が変わらないことです。
普通のハッシュ値では、少しでもデータを削除すると全体のハッシュ値が変わってしまうので、演算量証明をやり直す必要があり、困るわけです。
たとえ全参加者が元データを削除しても、ブロックのヘッダー部分、つまりハッシュ値のチェーンは残るため、ビットコイン創成時から現在までの演算量証明は誰でも追跡できます。
とにかくチェーンが長い方が勝つので、たとえば「ビットコイン開始時からのデータをすべてねつ造しよう」とする人が現れても、長大な演算量証明を築き上げられず、成功しないでしょう。

8節 取引の簡易検証法

取引を検証するだけで良いなら、ノードの役割をすべて果たす必要はない。
その代わりに普段は、最長チェーン内の各ブロックヘッダーを、それを確実に持っているノードに要求して手に入れておけば良い。
そして検証時には、その取引を含むブロックのハッシュ木を要求する。
ユーザ単独では取引を検証できないが、そのブロックを調べれば、ネットワーク上のいずれかのノードが取引を受け入れたと確認できる。
また、その後にブロックが連なっていれば、ネットワーク全体が取引を承認したこともわかる。

善良なノード群がネットワークを制御できていれば、この検証法は信頼できる。
しかし攻撃者の力が強くなると、信頼性は減少する。
各ノードは自身で取引を検証できるので問題ないが、この簡易検証法しか使わないユーザは、攻撃者がネットワーク内で一定の演算能力を持つ場合に、ねつ造された取引を見破れない。
これに対抗するには、不正ブロックを発見した善良なノードが、そのことをユーザに知らせるような仕組みが必要かもしれない。
ユーザの画面に対して、ブロック全体をダウンロードして問題がある取引の整合性を確認するように、警告を伝えられれば良い。
頻繁に支払いを受けるようなビジネス利用者は、セキュリティを確保するために素早い検証が必要なので、他者に頼らず自身でノードを設置すべきだろう。

前節の方法でデータ量は削減できますが、それでも各コインの直近の取引履歴は残しておかねばなりません。
ビットコインを利用するだけのユーザ、特にモバイルクライアントに全コインのデータを保持させるのは、酷というものです。
そこで、採掘を行っているノードからデータを取り寄せて検証するという仕組みが用意されています。
その際も、ブロックデータすべてを取り寄せる必要はなく、関係する部分だけを得られるようになっています。

9節 コインの融合と分離

ビットコインでは、コインを一枚一枚別々に処理するので、そのままではすべての送金を最小単位に分割せざるを得ず、不便である。
そこで、1度の取引に複数のインプット(前回の取引への参照)と複数のアウトプット(支払先のビットコインアドレスと支払額)を設け、コイン額を融合・分離できるように作られている。
あらかたの場合、インプットは、過去のより大きな取引への参照か、複数の小さな取引への参照を寄せ集めたものになるだろう。
対してアウトプットは、受取人への支払いと、もしあればお釣りの返却とで成り立つ。
このように設計すると、一つの取引が複数の取引に依存し、それらの取引もさらに多くの取引に依存することになるが、問題ではない。
コインの取引履歴を、1本に連なったリストとして取り出す必要性は無いからである。

コインとは取引履歴そのものでした。
ですから、誰かが誰かにコインを支払うということは、単にそのコインの最後に受取人のアドレスを追加するだけの作業となります。
ネットワークは、誰が幾ら持っているかではなく、コイン毎にその持ち主が誰であるかを管理しているわけです。
しかしこれでは、一円玉しか発行されない通貨体系のようなものです。
例えば、1コインの支払いと1,000コインの支払いを同じ体系で扱うのが困難です。
金額が低い方に合わせる必要があり、後者の場合、少なくとも1,000個ものコインの取引履歴を変更せねばならず、それぞれに電子署名などの処理が必要です。
積み重なると、耐えられないほどの重い処理になるでしょう。
これを避けるため、取引履歴を合流・分岐、つまりコインを融合・分離できるように作られているわけです。
現実の通貨では10円玉や100円玉など決まった額のコインを使用しますが、ビットコインではその場で任意の額(正確には1Satoshi=0.00000001 BTC単位)のコインを作り出せます。

10節 プライバシー

既存の銀行モデルでは、取引情報へのアクセスを関係者や第三者信頼機関のみに限定することによって、ある程度のプライバシーを維持している。
本システムでは、全ての取引を公開するのでこの手法は使えないが、情報の流れを別の方法でせき止め、プライバシーを確保する。
それは、公開鍵を匿名にすることである。
ある額を誰かが誰かに送金したことは全参加者に知られるが、他に情報がなければ、どういった人物が取引に関わったかは見抜かれない。
株式市場で言えば、取引の時刻や額を示すティッカーテープが公になっても、誰が売買したかはわからないのと同じことである。
さらなる安全策として、取引のたびに鍵のペアを生成し、参加者が取引とリンクされないようにしても良い。
ただし、複数の出金が融合して一つになった取引では、出金者が同一である場合はそのことが知られてしまう。
何らかの原因で、取引に使われた鍵と出金者とがリンクされた時には、その他の取引も知られてしまうというリスクはある。

原文の「鍵のペア」とは、ビットコインアドレスを指します。
ビットコインのウォレット上のボタンを押せばアドレスはいくつでも作れます。
その際に、内部では公開鍵と秘密鍵のペアが生成されているわけです。
そのうち送金者に渡るのは、公開鍵のみです。
誰がどのアドレスを持っているかの情報は、ビットコインネットワーク上にはありません。
それは利用者が管理すべきことで、手元にアドレスの秘密鍵があることが、そのアドレスを持っていることの証拠になります。
ですから何もしなくても匿名性は高いのですが、取引ごとに違うアドレスを使えば、追跡される可能性はさらに少なくなります。
ただし、前節の操作でコインが融合された場合は、セキュリティが落ちます。
例えば、顧客を多数持つお店が、取引先に大量のコインを送金したとします。
そのコインは、顧客からの送金を融合したものでしょう。
すると顧客は誰でも、店が誰かに大金を送金したこと、各顧客が一人当たり幾らぐらいの買い物をしたか、などを知ることが可能です。
この問題はビットコインシステムだけでは解決できませんが、外部機関が取引を中継することにより匿名性を付与することが可能で、すでにそのような機関が存在しているようです。

11節 数学的根拠(前編)
11節 数学的根拠(後編)

省略

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中