量子コンピューターはビットコインの脅威とされている。2人の科学者が計算しました。量子採掘機は古典採掘機に比べて本当に有利なのでしょうか？もしそうだとしたら、これはビットコインにとって脅威となるのでしょうか？
ビットコインと量子コンピューター：この話題は一度や二度ではありませんが、実は当初からビットコインにつきまとっていました。
量子コンピューターはビットコインを脅かすか？いつの日か量子コンピュータが登場し、その優れた計算能力によって、すべての財布を空にし、すべてのビットコインを採掘するのだろうか。長い目で見ればそうなるかもしれないと言う人もいれば、そうではなく、長い間、一片の心配もないだろうと言う人もいる。
これまでにも、量子コンピュータやビットコイン、ECDSA署名アルゴリズムについて書いてきました。今日は、カナダのコンピュータサイエンスの教授2人が、量子採掘機が危険かどうか、危険だとしたらどのような危険なのかを分析した論文を紹介します。
このテーマは、特に数学の素人にとっては些細なことではありません。しかし、ビットコインやコンピューティングの未来に興味がある人にとってはエキサイティングな内容なので、できるだけシンプルに論文を紹介したいと思います。
The Leaping Progress
著者が疑問を構築する基本的な枠組みは、次のような理論である：あるマイナーが強力になりすぎると、ネットワークを脅かす可能性がある。絶対的な多数派であれば、51％の攻撃を仕掛けることができますが、それ以下でも「攻撃的」「わがまま」な採掘でダメージを与えることができます。
では、もしあるマイナーが量子コンピューティングによって優位に立ち、ハッシュレートのシェアが不均衡になったとしたら？
基本的には、これまでも経験してきたことですが、技術の進歩が採掘を加速させるという極めて些細なことです。それは徐々にではなく、しばしば飛躍的に起こります。2011年からはグラフィックカードがメインプロセッサーを駆逐し、2013年からはアシックスがグラフィックカードを駆逐しました。そのような時、効率はもはや直線的にではなく、二次関数的または指数関数的に増加します。Ascisが古典的なチップの可能性をほとんど使い果たしたと思われる今、量子コンピューターは次の大きな飛躍のきっかけになるかもしれません。
それ自体は問題ありません。ビットコインのゲーム理論的な仕組みは、合理的なプレーヤーが正直になり、お互いに牽制し合うよう動機付けます。しかし、技術的な飛躍には波があり、もしかしたら、非合理的な行動をとる敵対勢力がビットコインに危害を加えるゲートウェイになってしまうかもしれません。
そのため、いつ起こるかわからないことを知っておくことは意味があります。量子コンピューターがクラシックアシックスをビットコイン採掘から追い出すためには何が必要なのでしょうか？
ソートされていないデータベースを検索する
ビットコインのマイニングは、マイナーがその計算能力でロットを生成していると考えることができます。マイナーはランダムなハッシュを生成し、そのハッシュが非常に稀な条件を満たせば、ブロックを見つけることができます。また、SHA256ハッシュ関数に対するブルートフォースアタックとも言えます。
2人の教授は、「マイナーは、暗号ハッシュ関数を部分的に反転させようとする」と言います。この「ハッシュ関数の部分反転」は、「順序付けされていないアイテムのリストの中からマークされたアイテムを探すこと（構造化されていない検索）と同等」です。些細なことのように聞こえますが、すべてのことの基本です。
というのも、量子コンピューターができると証明されていることはあまりないからだ。量子コンピュータが古典コンピュータよりも優れていると言われている数少ないタスクの1つが、順序のないリストの中から特定の項目を検索することです。
古典的なコンピュータでは、ソートされていないデータベースを検索する場合、つまりブルートフォースアタックの場合、一度に1つのエントリーを処理しなければなりません。アイテムからアイテムへと移動する2次元のポインターと考えることができます。エントリーの半分を見た時点で、ヒットする確率は50％を超えます。したがって、古典的なコンピュータは、平均してN/2回の演算を必要とし、Nは可能なアイテムの総数です。
量子コンピュータには、量子ビットが0と1を同時に表すことができるという利点があり、一連の量子ビットが考えられるすべてのバリエーションを同時に表すことができるのです。N次元を指し示すポインターと考えればよい。量子ビットがこの「重ね合わせ」の状態にあるとき、解決策はすでに彼らの中にあるのです。それがある。
しかし、測定した途端に解決策が崩れてしまいます。これは有名な量子のジレンマで、測定すると量子があるランダムな状態を強制的に取ることになる。つまり、量子コンピューターは解答を知っているのですが、悲劇的なことに、あなたがそれを拾いに行ったときに解答の価値が下がってしまうのです。
Grover’s algorithm: square practically accelerated
ここでGrover’s algorithmの出番です。1996年にLov Grover氏によって開発されたGrover’s algorithmは、結果を確認するための手法です。この量子ビットは、異なる「量子ゲート」（量子コンピューターの演算）を組み合わせることで、誤った結果を検出し、それを抑制します。繰り返すごとに、いわゆるグローバーイテレーションで、正しい結果が得られる確率が高くなります。
全体的に細部がめちゃくちゃ複雑です。しかし、ひとつはっきりしているのは、適切な回数の反復を行えば、Groverアルゴリズムはこのような検索を劇的に高速化できるということです。なぜなら、ソートされていないリストの中からアイテムを見つけるために、Groverは√n回の試行を行うだけだからです。つまり、ほぼ二次関数的に速くなるわけです。
2つの例 4つのアイテムがある場合、古典コンピュータと量子コンピュータは2回の試行が必要です。一方、5,198,400個のアイテムでは、従来のコンピュータが200万回以上操作しなければならないのに対し、量子コンピュータは2280回の試行で発見されます。
特に、ビットコインのマイニングのように、難易度が極めて高い、あるいはNが極めて高いタスクでは、この差、いわゆる量子アドバンテージが非常に大きくなります。それは、生態系全体を揺るがすような飛躍の一つです。少なくとも理論上は。
The quantum advantage is melting
実際には、量子採掘者は非常に特殊な問題に遭遇します：結果を測定したときにしかブロックを見つけることができず、プロセスを中断してしまうのです。そのため、何回反復するかを事前に知っておく必要があります。
この質問は厄介だ。多すぎても少なすぎてもデメリットがあるからです。反復回数が増えると、正しい解が得られる可能性が高くなりますが、同時に他のマイナーの方が速いという危険性もあります。一方、反復回数が少ないと、有効な結果が得られる確率が低くなり、その結果、量子的な優位性が損なわれます。
もし、量子コンピューターに無限の時間があれば、量子の利点を最大限に生かすことができます。しかし、マイニングではそれができません。繰り返す回数が少なすぎても多すぎても、妥協点を見つけなければなりません。
最適なトレードオフを計算するために、研究者たちは可能なシナリオでマルコフ連鎖を形成しました。マルコフ連鎖とは、通常はランダムまたは部分的にランダムな事象の可能性を示すシーケンスを数学的に定式化したものです。このような連鎖は、確率のジャングルの中で、どのような経路が平均的に最良の結果につながるのか、つまりGroverアルゴリズムのどの設定が理想的なのかを示しています。
驚くべきことに、これは16分である。
2つの注目すべき発見
量子採掘機がグローバーのアルゴリズムの結果を読むのに16分待つ場合、古典的な採掘機に対する優位性は、長いタイムスパンから生じる不利な点に対して最大になります。科学者によると、この利点は難易度に関係なく存在するそうです。
その結果、実践に移すことができるので、非常に注目されています。ここでは、2つの深刻な結果を見ることができます。
まず、このような戦術を持つ鉱夫は、約80％のブロックで失格となる。これらは16分以内に見つかるからです。残りの20％で成功の可能性を最大限に高める。これは、量子コンピュータが効率を犠牲にすることなく達成できる最大の総採掘力であるはずです。
次に、ほとんどの暗号通貨はブロックの間隔が短い。DogecoinやLitecoinは数分程度、EthereumやRippleは数秒程度です。量子マイナーは、このようなブロックチェーンでは鼻血を出してしまいます。少なくともマイニングにおいては、すでに量子的な安全性が確保されています。
また、量子コンピュータの並列化も行き詰まりを感じます。これはGroverアルゴリズムでは可能ですが、著者らの計算によると、√m倍の性能向上にしかなりません。古典的なコンピュータでは、この係数はm、つまり二次関数的に大きくなります。そのため、量子コンピューターがマイニングに適したものになるかどうかは疑問です。
78 Megahashes
この計算は、量子コンピュータの危険性をかなり回避している。しかし、決定的な問題はまだ解決されていない。量子採掘機が古典採掘機よりも優位に立つためには、何が必要なのでしょうか？量子コンピュータを搭載したブロックを探すのが安くなるとしたら、どの時点だろうか。
これには2つの要因があります。1つはグルーバーの反復ごとのコスト、もう1つはブロックに必要なハッシュの数と必要なグルーバーの反復数の比率です。著者らは、現在一般的な量子コンピューターの「ゲートスピード」が66.7メガヘルツであることを例に挙げて計算している。ゲートとは、量子演算のことです。科学者たちは、この量子コンピューターが1秒間に224グルーバーの反復を行うと計算しています。
意味は？224回のグローバー反復は、1秒間に78メガハッシュのハッシュレートに相当する。これは、ビットコインのハッシュレートの中では絶対的に微々たる割合であり、実際、現代のアシックスが達成していることのほんの一部でしかありません。ここで危険を察知するのは馬鹿げている。
Likely to be more power efficient in the future
しかし、もし量子マイナーが脅威にならないとしたら、少なくともより効率的なのだろうか？では、少なくとも徐々にではありますが、量子採掘への転換が可能なのでしょうか？そして、どの時点で？
より効率的にするためには、Groverの反復のエネルギーコストは、最大でも古典的なハッシュのコストの3.49×105倍でなければなりません。ハッシュあたり10-10ジュールのエネルギー効率を持つ古典的なマイナーと比較すると、量子コンピューターは3.49×105×10-10よりも優れた効率、つまりグローバーの反復あたり約10μJが必要となる。あるいは1秒間に2240μJ。
それは非常に低いと思います。しかし、量子コンピューターは非常にエネルギー効率が良い。システムを15ミリカルビン（絶対零度）まで冷やすと、量子ビットは超伝導体となり、電気も熱もほとんど必要ありません。現時点では、電力に対して冷却が必要なため、量子コンピュータは不経済です。しかし、技術の進歩に伴い、これも変わっていくでしょう。
結局のところ、ビットコイン主義者としては、量子コンピューターの未来を恐れることなく、熟睡して少し賢くなり、夢を見ることができるのです。
