ビットコインの原論文を読む 11節 数学的根拠(後編)

引き続きMathJaXを使用します。古いブラウザでは読めないかもしれません。

$p>q$という本システムの前提下では、攻撃者が追いつく確率は、追いつくべきブロック数が増えるほど指数関数的に小さくなる。従って、もし最初に運良く相手との差を詰められなければ、差が急激に開き、追いつく可能性はほとんど無くなるだろう。

支払人による取引改ざんを事実上不可能にするために、受取人はどの程度待てば良いだろうか。攻撃者は、受取人に対してしばらくの間正しく支払われたと思い込ませ、その後に払った額を奪い戻す。受取人は、いずれ不正な取引であるとの警告を受けるが、支払人はその時刻をできるだけ遅らせたい。

続きを読む »

ビットコインの原論文を読む 11節 数学的根拠(前編)

この節は数式が多いので、MathJaXを使用します。古いブラウザでは読めないかもしれません。

個人的には、論文の中で一番面白い節です。

11 数学的根拠

正しいチェーンよりも速く、攻撃者が自身のチェーンを伸ばすには、どれ程の計算能力を持てば良いだろうか。ただしこれが成功しても、正当な量以上のコインを生成したり、扱ったことがないコインを他人から盗み出せるようになったりするわけではない。善良なノードは、不正な取引を受け付けず、また不正な取引が埋まったブロックも受け付けないからだ。攻撃者がなし得る詐欺行為は、他人に支払った過去の取引を無効にし、コインを奪い戻すことのみである。それも、取引から時間が経つほど困難になる。

善良なチェーンと攻撃者のチェーンとの闘いは、±1歩ずつのランダムウォークと見なせる。善良なチェーンが1ブロック伸びた場合は1歩進み、攻撃者のチェーンが1ブロック伸びた場合は1歩下がる。

攻撃者のチェーンが、より長い善良なチェーンに追いつく確率は、「ギャンブラー破産問題」の理論を使って計算できる。ギャンブラーは一定額の赤字から開始するが、無限の資金を持ち何回でも賭け続けられるとする。そして、一度でも損益無しの状態になれば勝ちである。その確率は、攻撃者が善良なチェーンに追いつく確率と同じで、次のような式になる[8]。

続きを読む »

STAP細胞論文についての数学的考察

※この投稿では、数式のためにMathJaXを使用しています。そのため、古いブラウザでは読めないかもしれません。

STAP細胞は世紀の大発見か、ねつ造か、はたまた実験ミスか。盛大に真贋論争が巻き起こっていますが、正面切ってそれに参加するのはちょっと気が引けます。

「過去に書いた論文で恣意的なデータの採用、強引な論理展開、他論文からの表現拝借などを手がけていない人だけが、理研に石を投げなさい」

とか言われるかと思うと、もう黙るしかないです。

ただ、検証ネタの中で、数学的に面白そうなものを見つけました。Natureに投稿されたARTICLEの方のSTAP論文で、Figure 2.cについて、独立な2つの実験なのに結果が酷似しているというものです。こんなことは確率的にあり得ないというのですが、本当でしょうか。

fig2.c

この図には、白丸の大きさが微妙に違うなどの疑惑もあり、あとから結果を修正したのではないかなどとも言われています。しかし今回それは置いておき、この類似がどの程度の確率で起こりうるかだけを、パズル的に考えてみたいと思います。

続きを読む »

ビットコインの原論文を読む 10節 プライバシー

10 プライバシー

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

fig7

続きを読む »

ビットコインの原論文を読む 9節 コインの融合と分離

9 コインの融合と分離

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

続きを読む »

ビットコインの原論文を読む 8節 取引の簡易検証法

8 取引の簡易検証法

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

fig5

続きを読む »

ビットコインの原論文を読む 7節 使用ディスクスペースの節約

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

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

fig4

続きを読む »

ビットコインの原論文を読む 6節 ネットワーク参加者への報酬

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

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

ブロックの最初には、特殊な取引が記述される。ここに書かれるのは、コインが新たに生まれ、それをブロックの生成者が所有したという情報である。ブロックの生成者にコインを与えることは、各ノードがネットワークを維持する動機となり、また中央機関が権力を使ってコインを配分する代わりの枠組みともなる。新たなコインが一定量ずつ生まれることは、金鉱採掘に例えれば、資金を投入して金を採掘し流通に乗せることに該当する。資金に当たるのは、本システムではCPU時間や電力である。

続きを読む »

博物ふぇすてぃばる!に出展します

博物ふぇすてぃばる!という、博物学に関連したイベントが8月に開催されます。これにピッチブレンドも参加させていただくことになりました。同人誌中心のサークルなので大丈夫だろうかとためらったのですが、主催者さんにも是非と言われたので、出展してみることにしました。が、参加する他サークルさんの情報を見て、正直ビビっています……。

ピッチブレンドが持って行くのは、

  • クルタ計算機開発者へのインタビュー本
  • 九元連立方程式求解機の解説本
  • ペルチェ素子霧箱のデモ(参考:ニコニコ動画の投稿

を予定しています。クルタ計算機の実物も持参したいですね。ブースの詳しい情報は、追ってお知らせします。

curtahyoushihyoushi

続きを読む »

ビットコインの原論文を読む 5節 ネットワーク

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

5 ネットワーク

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

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

続きを読む »

古い記事へ «

» 新しい記事へ