Skip to content

Instantly share code, notes, and snippets.

@culage
Created April 23, 2014 03:06
Show Gist options
  • Save culage/11201595 to your computer and use it in GitHub Desktop.
Save culage/11201595 to your computer and use it in GitHub Desktop.

ビットコイン(Bitcoin)学習

i. これは何か

自分なりのビットコイン論文の再翻訳。

  1. 目次

  1. イントロダクション 目的と、概要の説明。

  2. 取引 公開しても捏造・改変されない取引履歴の作成する方法 (二重支払いは防止できない)

  3. タイムスタンプ・サーバ 過去の取引ほど強力に改ざんを防ぐ方法。

  4. プルーフ・オブ・ワーク 取引に計算量証明をつける方法。(偽の取引を作るにはCPUパワーが必要)

これを入れることで、 取引を確定されるためにはCPUパワーが必要になる。

さらに、作成にCPUが必要なデータは一番長いチェーンが「正しい」という仕様を入れると、 一番CPUパワーを多く持つ存在のみが「正しい」データを作れることになる。 そして、一番CPUパワーを多く持っている存在はネットワーク全体である。

これが入っていないと、CPUパワーをそんなに持っていない攻撃者でも一瞬で 取引を確定された偽データが作れるので、一番長いチェーンが「正しい」という仕様が機能しない。

  1. ネットワーク ネットワークの総意として正しい取引を判定する方法。

  2. ネットワーク参加者への報酬 利己的なノードだけで、ネットワークの正常性を維持する方法。

以降は、細かいtips的な章になる。 7. 使用ディスクスペースの節約(ハッシュ木の採用によるメリット1) 8. 取引の簡易検証法(ハッシュ木の採用によるメリット2:使用ディスクスペースを減らしても取引が正しいか検証が可能) 9. コインの融合と分離 10. プライバシー 11. 計算 12. 結論

  1. イントロダクション

本論文で提案するのは、第三者機関を利用せずに多重使用問題をP2Pネットワークで解決する方法である。

現在も信用できる第三者機関(金融機関等)に価値の譲渡を依頼すればそれは可能だが、 どうしても信用できる第三者機関が必要である。

本システムは、良心的なノードが集合的に、攻撃者グループのノードを上回るCPUパワーをコントロールしている限り安全である。

  1. 取引

一つの電子コインは、連続するデジタル署名のチェーンと定義される。 電子コインの各所有者は、

直前の取引のハッシュ 次の所有者のパブリック・キー(公開鍵) ……を所有者の秘密鍵で暗号化したデジタル署名(取引全体のハッシュを暗号化したもの)

をコインの最後に加えることにより、電子コインを次の所有者に転送する。 受取人は一連の署名を検証することで、過去の所有権を検証できる。

aがbへ所有権を移動させる場合

  1. トランザクションは直前の取引のハッシュを含むことで、どの取引の次に行われた取引かが証明される
  2. トランザクションはbの公開鍵を含むことで、bに所有権があることを証明される
  3. トランザクションはaが持つ秘密鍵で暗号化した署名を含まねばならないため、aにしか生成できない。

これだけでは問題がある。 それは受取人に、過去の所有者がコインを二重使用していないことを検証できないことだ。

一般的な解決法は信用のおける中央機関もしくは造幣局を間に入れ、全取引を監視させることである。

  • 取引の度にコインは造幣局に戻され、新しいコインが発行され、造幣局から新しく発行されたこのコインのみが二重使用されていないものとして信用される。
  • この解決法の問題は、全取引が造幣局を通じて行われるため、銀行と同様に造幣局を運営している企業に、金融システム全ての運命が左右されることである。

これを第三者機関なしに行うには、 取引が公開され、参加者たちが唯一の取引履歴に合意することのできるシステムが必要となる。 受取人は取引毎に、取引が行われた時点で大多数のノードがそのコインが初めて使用されたことに賛同したという証明を必要とする。

以降で、、参加者たちが唯一の取引履歴に合意することのできるシステムの説明を行う。

  1. タイムスタンプ・サーバー

このアイディアは、データの塊(ブロック)をチェーン状にして、ブロック・チェーンの改ざんを 不可能にする方法である。

各ブロックは、そのブロックの中に直前のブロックのハッシュを含むことでチェーンを形成する。 そのため過去のブロックを改ざんするには、それ以降の全てのブロックを改ざんしなければ整合性が失われる。

ブロックのチェーンは1つ過去のブロックのハッシュを含むので、改ざんすると検出される。 例えばABCDチェーンのBを改ざんした場合Cが持つBハッシュとBから実際に算出したハッシュが一致しなくなる。 かといってCの持つBハッシュを改ざんすると、今度はDの持つCハッシュとCから実際に算出したハッシュが一致しなくなる。 このように、ある時点のブロックを改ざんして、その改ざんを検出されないようにするには、そこから未来に続くチェーンを全てを改ざんしなければならない。

ある時点のブロックは、それ以降に続く全てのチェーンはで改ざんされていないことを保証される。 A,B,C,D…… のブロックがあった場合、

  • AのハッシュはAのデータが改ざんされていないことを保証する。
  • Bのハッシュは「Aのハッシュと、Bのデータ」から生成されるのでAとBが改ざんされていないことを保証する。(二重に保障)
  • Cのハッシュは同じようにBとCが改ざんされていないことを保証する、……Bが改ざんされていないということは Aが改ざんされていないということでもある。(三重に保障)
  • Dもハッシュも同じようにAの正当性Aが改ざんされていないことを保証している。(四重に保障)

以降のハッシュも全てAが改ざんされていないこと保証している。

たとえば、Dハッシュからそれを確かめるには

  1. DとCハッシュから、Dハッシュが出ることを確認 (1回確認)

  2. CとBハッシュから、Cハッシュが出ることを確認 (2回確認)

  3. BとAハッシュから、Bハッシュが出ることを確認 (3回確認)

  4. Aから、Aハッシュが出ることを確認 (4回確認)

  5. プルーフ・オブ・ワーク


http://kogarashi.net/pitchblende/archives/84

プルーフ・オブ・ワークは、演算に費やした時間を他人に頼らずに証明する手法である。 例えば「SHA-256のようなハッシュ関数を通すと最初のnビットがすべて0となるような値」を 総当たりで発見することによって実現できる。そのような演算にかかる平均時間は、nに対して指数関数的に増大する。 それに対して、検証する側はハッシュ関数を1回計算するだけで良い。

提案するタイムスタンプネットワークでは、ブロックデータとNonceと呼ばれる数字を組み合わせる。Nonceを適当な値から1ずつ増やし続けて、 ハッシュ値の最初のnビットがすべて0になる場合を探索する。このようにCPUを使って演算量を証明しておけば、 ブロックの内容を改ざんして辻褄を合わせるためには、同じ計算をもう一度行わなくてはならなくなる。 さらにその未来にブロックがチェーンでつながっていたら、それらすべてに対する演算をやり直す必要がある。

※ビットコインの実装では、ブロック内にタイムスタンプも含むので1秒ごとに探すべきNonceは変わってゆく。

演算量を証明することにより、集団における意思決定をどのように行うべきかという問題も解決する。 例えば、多数決方式を採用し各IPアドレスに1票ずつを割り当てると、誰かがIPアドレスを大量に確保した時点で制度が崩壊する。

それに対して、演算量証明に基づく本システムは、各CPUに1票を与えるようなものである。 実際には、最もCPU能力を費やして作られた情報、すなわち最も長いチェーンを、集団の意思決定の結果であると取り決める。 CPU能力の大多数が善良なノードによって構成されていれば、不正がないチェーンが最速で成長し、ねつ造した情報を含むチェーンよりも長くなるはずである。 もし、攻撃者が過去のブロックを改ざんしようとしたら、それ以降のブロックをすべて計算し直し、善良なノード群が計算するチェーンの 長さに追いつき追い越す必要がある。後に示すが、能力的に劣る攻撃者が正しいチェーンに追いつく確率は、 追いつくべきブロック数に対して指数関数的に小さくなる。

年月が経つと、ハードウェアの速度が向上したり、世間の注目度合いによって参加ノード数が変動したりするだろう。 生成されるブロック数がそのような影響を受けないように、『演算量証明の難易度は、過去一定期間の生成ブロック数をもとに設定される。』 ブロックの生成間隔が短すぎる時には、難易度が高くなる。

※ビットコインの実装では、直前の2016ブロック(だいたい2週間分)を 生成するのにかかった時間を元に難易度が算出されるようになっている。

ブロックdを改ざんしようとする攻撃の例

a b c d *-*-*-*… ネットワークの参加者全てによる並列演算で伸びる      \       … 攻撃者のみの演算で伸びる

攻撃が成功するには、 本物のブロックeが作成されるまでに 偽のdと偽のdに続くブロックeを作成する必要がある。

注意したいのは、この攻撃が成功して履歴が書き換えが成功しても、書き換え後の取引履歴に不整合が発生するわけではないことだ。 過去に存在していた本物のブロックdでの取引が行われなかったことになり、代わりに別の取引が行われたことになるだけである。 改ざん後も、ビットコインの取引としては二重支払いも何も無い完全に正しい履歴が残る。 (取引データの作成には秘密鍵が必要なため、自分に対して偽の送金をする取引データを作ることは不可能)

問題は 改ざんが行われる前は取引が完了したという情報が正しいのに、改ざんが行われた後は取引が行われなかったという情報が正しくなることだ。 改ざんが行われる前、ビットコインと引き換えに現実の価値を移動させてしまうと 改ざんが行われた後にはビットコインの移動なしに(無料で)その価値を相手に渡してしまったことになる。 ビットコインの振り込みからある程度のブロックが作成された後で現実の価値を移動させることで、この問題を回避することが可能である。 なぜならば、タイムスタンプ・サーバーの原理によって過去になればなるほど履歴を改ざんすることが爆発的に困難になっていくためだ。

※多くの取引所は取引がブロック・チェーンに組み込まれてから10ブロック以上生成されたら  取引が確定したと判定するなどの対応をとっている。

Note:

あるデータに対して、計算量を消費した保証を与えるにはハッシュ関数を通した結果が 定形のデータになるよう追加データ(Nonce)を加えさせることで実現される。 こうすれば、 計算量を消費したことを証明するための追加データ(Nonce)を求めるには、Nonceを適当な値から1ずつ増やし続けて計算を繰り返す必要があるが、 計算量を消費したことを確認するにはデータ内容とNonceを合わせてハッシュ関数を通すだけでよい。

メールを1通送るために1円必要になればスパムメールは存在しなくなるということを実現できる方法でもある。 (実際消費したのは計算能力だが、計算能力をつぎ込むためには電力が必要で電力は貨幣を消費して得られるものである) スパムメールが増えれば電力会社が儲かるとか、かなり風が吹けば桶屋が儲かる的ロジックで面白い

  1. ネットワーク

http://kogarashi.net/pitchblende/archives/116

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

といっても投票を集計して判定するといったことをしているわけではなく、 早く作成されたブロックほど早く全体に拡散して子孫ブロックが生き残りやすくなるという原理で、 より早く出来た、より多数を占めるブロックがネットワーク全体で支配的になるという仕組みで 多数決投票が実現されている。

本ネットワークは、次に示すステップで動作する。

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

各ノードは、最も長いチェーンのみを正当なものと見なし、その先端ブロックから演算量証明を開始して、チェーンを伸ばそうとする。

2つのノードが、それぞれ異なる最長チェーンのブロックを同時に広めている場合は、集団が別々のチェーンに対して演算を始めるかもしれない。 その場合、各ノードは演算しない側のブロックも保存しておく。 この引き分けの状況は、次に誰かが演算を終えてチェーンを伸ばしたときに解消する。 演算量証明に負けた側のチェーンを計算していたノードは、長い方に乗り換える。

取引情報は、必ずしも全てのノードに行き渡る必要は無い。 一定数のノードに情報が届けば、ある程度の時間が経てばブロックに取り込まれるからである。 ブロック化された後も、多少の通信障害には耐えて拡散する。

もし、あるノードがブロックを受信できなかった場合は、次のブロックが届いたときにそのことがわかるので、欠けたブロックを他のノードに要求する。

  1. ネットワーク参加者への報酬

http://kogarashi.net/pitchblende/archives/142

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

また、ビットコインには中央金融機関が存在しないため通貨の発行権限を持った人がどこにも居ない。 そのため何かの仕組みを設けないと、通貨を継続的に発行することが不可能になる。

ネットワーク参加者への報酬は、上記2つの問題を同時に解決する。

正しいブロックを生成した者には、2つの報酬が与えられる。

  1. 採掘コイン 各ブロックの最初には、特殊な取引が記述される。 ここに書かれるのは、コインが新たに生まれ、それをブロックの生成者が所有したという情報である。

コイン生成取引も拡散する際に他のノードによって検証されるため、不正にコインを生成してもそのブロックは拡散されない。 (ビットコインの実装では、コインの価値が高くなっても得られる価値を一定にするために、生成されるコインをだんだん減らす仕様になっている。)

ブロックを生成するとコインを得られることは、各ノードがネットワークを維持する動機となり、また中央機関が権威を使ってコインを配分する代わりの枠組みともなる。 新たなコインが一定量ずつ生まれることは、金鉱採掘で言えば、資金を投入して金を採掘し流通に乗せることに該当する。資金に当たるのは、本システムではCPU時間や電力である。

  1. 手数料コイン コインの生成者は、報酬として取引手数料も受け取れる。これは、各取引において、受取額を支払額よりも少なく設定すれば良い。 その取引を含むブロックを生成した者が、取引手数料として差額を受け取る取引をブロック内に含めることができる。

手数料コインの受取取引も拡散する際に他のノードによって検証されるため、不正に手数料を得るブロック生成してもそのブロックは拡散されない。 (ビットコインの実装では、手数料の決定権は送信者側にあり、取引のトランザクションの中に手数料をいくらにするかが含まれている) (ただし手数料が少ない取引をブロックに含めるか含めないかの決定権はノード側にある。つまり、必要なCPUパワーに対して手数料が少ないと判断したら、その取引を無視するということができる)

決められた全枚数のコインが流通に乗った後には、取引手数料がブロックを生成する動機となる。

……報酬には、各ノードが不正を働かないように動機付ける役割もある。 もし、欲張りな攻撃者がCPU能力を集め、善良なノード群のそれを上回ったとする。 攻撃者はその能力を、自身が支払った額を奪い戻して横領するか、真っ当な方法で新たなコインを生成するかのどちらかしか選択できない。 この場合、ルールを破り通貨システムと自身が持つ価値を崩壊させるよりも、ルールに従って、新たに生まれるコインの過半数を得る方が賢明だと、判断するだろう。

  1. 使用ディスクスペースの節約(ハッシュ木の採用によるメリット1)

http://kogarashi.net/pitchblende/archives/204

コインの取引履歴が十分な数のブロックに埋め込まれたら、使用しているディスクスペースを節約するために、古い履歴は消去しても構わない。 取引のデータ構造にハッシュ木を採用しているから、データを消去してもブロックのハッシュ値は変わらない。 ハッシュ木なので、そのルートハッシュ値は取引データ全体のハッシュ値となり、その値がブロックのヘッダーに格納されている。 古くなったブロックでは、ハッシュ木の枝を刈り取ってサイズを縮小するが、この際、途中の不要なハッシュ値も削除して良い。

ブロックのヘッダー部分の大きさは約80byteである。 ブロックを10分に1 個ずつ生成する場合、1年間に80byte×6×24×365=4.2MBが必要となる。 2008年現在、一般的なPC は2MB のRAM を搭載して販売されており、ムーアの法則によればこれが1年間1.2GBの勢いで成長している。 従ってヘッダー部分だけならば、すべてをメモリに格納しても問題はないだろう。

  1. 取引の簡易検証法(ハッシュ木の採用によるメリット2:使用ディスクスペースを減らしても取引が正しいか検証が可能)

http://kogarashi.net/pitchblende/archives/207

取引を検証するだけで良いなら、ノードの全役割を果たしていなくても構わない。

※ハッシュ木は大きなデータを分割したときに、その一部のデータだけでも正当であるか判断することができる。

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

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

  1. コインの融合と分離

http://kogarashi.net/pitchblende/archives/210

コインを一枚一枚別々に処理すると、すべての送金を最小単位に分割せざるを得ず不便である。 そこで、 1度の取引に複数のインプット(前回の取引への参照)と 複数のアウトプット(支払先のビットコインアドレスと支払額)を設け、コイン額を融合・分離できるようにする。 (ビットコインの実装では、分割できる最小単位は 1Satoshi=0.00000001 BTC である)

これは、取引が行われるときに任意の金額のコインを作り出すイメージである。 (例えば、100BTCの価値があるコインを20BTCの価値があるコイン5つにしたり、 20BTCの価値があるコイン2つかを40BTCの価値があるコイン1つにする)

複数アウトプットは、受取者への支払いや、お釣りの返却(自分自身に対する送金)とで成り立つ。

受渡者A100→受取者B30(Aの署名を含む)      →受取者C30(Aの署名を含む)      →受取者A40(Aの署名を含む) ※お釣り

複数インプットは、複数の小さな取引を寄せ集めたもの。

受渡者A40→受取者C50(Aの署名と、Bの署名を含む) 受渡者B10→

計算が合わない融合取引や分離取引は、ブロック作成時と、ブロック拡散時にチェックされて弾かれる。

このように設計すると、一つの取引が複数の取引に依存し、それらの取引もさらに多くの取引に依存することになるが、問題ではない。 コインの取引履歴を、1本に連なったリストとして取り出す必要性は無いからである。

  1. プライバシー

http://kogarashi.net/pitchblende/archives/214

現実の銀行モデルでは、取引情報へのアクセスを関係者に限定することによって、プライバシーを維持している。 ビットコインでは、全ての取引を公開するのでこの手法は使えない。

ビットコインでは公開鍵(所有者を示す情報)を匿名にすることで匿名性を確保する。 つまり、ある額を誰かが誰かに送金していることは全参加者に知られるが、 他に情報がなければ、どういった人物が取引をしているのかはわからないということだ。

さらなる安全策として、取引のたびに公開鍵(と秘密鍵)を生成してもよい。 そうすることで、1つの公開鍵が現実世界の人物と対応付けられてしまった場合でも、 それにより暴露される取引を1取引のみに抑えることができる。

問題点: (すべてのコインを同じ公開鍵で管理していれば) ある取引で使われた鍵が出金者にリンクされた時には、その他の取引も知られてしまうというリスクはある。

(すべてのコインを同じ公開鍵で管理していれば) 複数コインを融合して一つにする取引の場合、支払人が同一であればそのことが知られてしまう。

  1. 計算

ここは安全性を数学的に示しているセクションなので、割愛。

  1. 結論

論文では、信用に依存しない電子取引のシステムを提案した。

電子署名で作られるコインは所有権のコントロールを実現できる。 しかし二重支払い防止はされない。

二重支払いの解決策として、良心的なノードがCPUパワーの過半数をコントロールする限り、 プルーフ・オブ・ワークを使って記録された公開型の取引履歴を攻撃者が変えようとすることが、 加速度的に困難になっていくP2Pネットワークを提案した。

ノードは以下の特性を持つ。

  • 各ノードは同時に動作するが協調性は低くて構わない。
  • メッセージは最善努力原則で送信すればよく、また特定の場所に転送されるわけではないのでノードが特定される必要性はない。
  • ノードは自由にネットワークに接続、離脱できる。
  • 離脱していた間の取引は、他のノードからプルーフ・オブ・ワークで証明されたブロックを受け取り、自身でもその内容を検証して受け入れる。
  • ノードはCPUパワーを用いて作成されたブロックを受信し、チェーンへの受入・拒絶をする。
  • 受信したブロックが有効である場合には、そのブロックを延長するブロックを生成・受入することで承認を表明する。
  • 受信したブロックが無効である場合には、そのブロックを無視することで拒絶を表明する。
  • 必要なルールやインセンティブはこの合意メカニズムに従って実行できる。
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment