yasuokaの日記： Bitcoinパズルに勝つ確率 14
私(安岡孝一)が書いた『Bitcoinは計算量理論から見て「無限連鎖講」である』(日経ITpro、2014年4月2日)に対して、読者からいくつか質問をいただいたのだが、それらの質問の中に、計算量理論や制御工学はおろか、確率論すら理解していないものが複数あって、個人的にはガクゼンとした。あまりにガクゼンとしたので、あえて、この日記でお答えしておこうと思う。端的には、私の文章の以下の部分に関する補足ということになる。
取引記録は約10分ごとにまとめられて、複数の取引記録に1枚のパズルが貼りつけられる仕掛けになっており、そこに新規発行された25BTCと手数料がぶら下げられている。それを貰えるのは、パズルを最初に解いた人だけなので、ここで競争が起こる。SHA-256の効率的な解法は発見されていないので、とにかくコンピュータを回して大量の計算をした人の勝つ確率が高くなる。
Bitcoinパズルの参加者が、仮に、MarcとBenの二人だけだったとしよう。MarcはBenの1000倍、Bitcoinパズルに計算量を投入しているとする。Benの計算量を1とおくと、Marcの計算量が1000ということだ。ここで、Bitcoinパズルを2016回解く際に、MarcとBenは何回ずつ勝つ可能性があるか、という問題を考えてみよう。
先の質問者たちは、この問題に対し、「Marcの一人勝ちで2016回ともMarcが勝つ」と考えているらしい。しかし、それは誤りだ。実際には「Benが2回程度、Marcが2014回程度勝つ」というのが確率論の基本だし、Bitcoinパズルでは事実そうなる。小数第三位まで見るなら、Benが勝つ期待値は2.014回(2016×1÷1001)、Marcが勝つ期待値は2013.986回(2016×1000÷1001)、ということだ。すなわち、Bitcoinパズルでは、「参加者全員が投入する計算量全体に対し、自分が投入している計算量が何%にあたるか」が、そのまま、Bitcoinパズルに勝つ確率となる。これは、人数が増えても同様である。それゆえBitcoinパズルにおいては、参加者全員が投入する計算量全体が、パズルを解くための時間の逆数の平均に、ダイレクトに反映される結果となる。そして、それが難易度へと反映されるわけだ。
とはいえ、こういう確率論すら理解のおぼつかない読者が、いくつもの山を越えて「Vo/Vi = A / 1-Aβ」に辿りつくのは、かなりの苦行となることが予想される。うーむ、さて、どうしたらいいのやら…。
直感的に見ても (スコア:2)
「Benは2回くらいは勝つ」って思うんですが…
逆に、1000回勝負すれば、必ず一度はBenが勝つとかいう奴が出てくる方が多そうな…
Re:直感的に見ても (スコア:2)
Re:直感的に見ても (スコア:2)
このページを見て、彼らの考えが少し判りました。
「1/1000の確率で解けるパズルは先に1000回計算した奴が必ず勝つ」
なんですね。多分。
1-((n-1)/n)^nが1になっちゃうって意味では「逆に」の人です。きっと。
Re:直感的に見ても (スコア:1)
Re:直感的に見ても (スコア:2)
ふーむ、間違いに気づいて書き直したんでしょうかね。まあ、ウェブ魚拓 [megalodon.jp]もありますけど。
nonceをランダムに決定した場合はそうなりますが (スコア:1)
多くの採掘用ソフトウェアでは、単純にnonceを線形的に変化させているだけです。
(ランダムにnonceを決定すると使用済みのnonceを記憶するのに多くのメモリが必要になる)
よって、理論的にはともかく実際のBitcoinではBenが勝つ確率はもっと低いと考えられます。
Re:nonceをランダムに決定した場合はそうなりますが (スコア:2)
単純インクリメントでも、初期値をランダムにするだけで、確率かなり上がるんですけどね。ただ、↑の方々は、そもそもそういう議論に入る以前の段階なので…。
nonceをランダムにしなくてもいいみたい (スコア:2)
よくよく考えなおしてみたのですけど、nonceをランダムにしなくても、Benが約2回、Marcが約2014回勝つみたいです。
というのも、MarcとBenの場合は、二人とも同じminer.cppでnonceを0から順に増やしていったとしても、約1秒後にはnTimeが増えてしまうので、その後は、MarcとBenで別の解空間を探索しはじめることになります。言い換えると、同じnonceであっても、MarcとBenで異なるnTimeにそこを探しに行ってしまうので、SHA-256の結果が変わってくるのです。つまり、無駄になるのはBenの最初の約1秒だけだと思うのですが、うーん、さて、これで本当にいいのかしら…。
Re:nonceをランダムにしなくてもいいみたい (スコア:1)
基本的にnTimeがnonceの探索途中に頻繁に更新されるようなことはなく、たいていはブロック生成時のタイムスタンプのまま固定です。
つまりBenとMarcのブロック生成時刻がズレていた場合は別の解空間になります。
発散するんでしょうか (スコア:1)
すみません、日記の趣旨と少し異なりますが質問させて下さい。
「1BTCを得るのに必要な計算量が増加する以上、投入される計算量も必然的に増加する」
から正のフィードバックである、とのことですが、報酬として得られるコインの総計は、
現在25BTC/約10分と固定されていて、これは投入された計算量の総和がいくら多くとも、同じ額です。
したがってそれ以上のコストをかけて計算量を投入しようとするマイナーは、
いずれ収支が合わずに撤退させられることになるので、計算量は発散しないように思えます。
何を見落しているのでしょうか。
Re:発散するんでしょうか (スコア:1)
すでに絶賛発散中です (スコア:2)
あの、この日記は、あくまで確率の議論なのですけど…。
まあ、その「採算」とかいうものを全ての「採掘者」が共有していて、かつ、全ての「採掘者」が理知的に行動したのなら、発散しない可能性もあったと思いますよ。でも現実は
と書いた通りです。
確率 (スコア:1)
確率についてはまあそうですね。自分も確率の知識がアレですが、ふつうにそう取りますし。
ただ実際にはプールに計算量を入れるし、各プールの比率はそこまで極端に差がない、流通量とのバランスなんかもあるので、そこまで採算悪いってこともなさそうかなぁ、とは思います。
# 長期的な話はまだよくわからないので、とりあえずおいておきます
M-FalconSky (暑いか寒い)
Re:確率 (スコア:2)
「スピード競争」とか「スピード勝負」とかいう表現が、良くなかったのかなぁ。何か「3000メートル競走」みたいなイメージでとらえてしまった読者さんが、多数いるみたいで…。