ビットコイン vs 量子コンピュータ
本記事では結局量子コンピュータはブロックチェーンに対してどのような影響があるのかをなるべく詳細に説明していきたいと思います。
今回記事を書いた理由は、新年にもビットコインがATHしてウハウハな皆さんに釘を指して売らせるためです。
というのは冗談で、今回この記事を書こうと思ったのは数多くの疑問があるにしてはあまり明確、かつ的確な回答をみたことがないと思ったためです。
基本的には仮想通貨だけでなくインターネット上の大部分を占めるHTTPSのトラフィックを取ってきて解読するというように大きな目で見れば全部やばいよねということですが、仮想通貨は仮想通貨で特有の影響があると思うので掘り下げていきます。
専門家の方にも少し聞いてみたりして、自分のメモとして残して置きたかったのですがどうせなら公開しようと思いました。
ブロックチェーンの仕組みの理解がある程度要求されるかもしれないので結果だけ知りたいという方はまとめだけ読んでみてください。
今回説明の対象となるブロックチェーンはビットコイン
話は量子コンピュータがビットコインにどのような影響を与えるかというところを掘り下げていきます。ビットコイン以外のブロックチェーンに関しては今回の対象とはなりませんが、チェーンによっては被る部分はあると思われます。差が大きく出るのは匿名通貨？？
以下はビットコインのブロックチェーンのことをビットコインと略します。
量子コンピュータの開発状況実際どうなの
自分の予想するクリプト界隈の全体的な認識としては、"2019年にGoogleが同社の開発した量子コンピュータにて量子超越性を発表したが、現段階で暗号技術は無事であるのは知っている"という感じかなと思います。
ちなみに去年(2020年)二件目の量子超越性が中国にて発表されました。これはガウシアンボソンサンプリングと呼ばれる確率分布を取り出すような問題で、Google同様暗号解読とは関係ありません。
上記の事実だけでもかなり進んでるのではという印象を覚えますが、実際かなり加速していってると思います。量子コンピュータは実機がすでに現実に存在しています。ですが、現実に存在してるとは言えど、まだ有用な規模までには進んでいません。（わかりやすいところで言うとビット数やエラー率がまだまだです。）
量子計算理論では2000年頃には計算量的に古典コンピュータより速いよねというアルゴリズムの議論はかなり進んでいました。計算量の話ですが、線形時間とまではいきませんが、多項式時間まで落とし込むことが証明済みのアルゴリズムも存在します。(準)指数時間を多項式時間まで落とし込むことができると、暗号解読にかかる時間が現実的な実行時間にまで減少させる可能性が出てきます。
※ちなみに、念のためですが量子コンピュータは暗号を解読するために存在するものではないです。
ここから本題となっていきます
ここから具体的に、ビットコインに及ぼす量子コンピュータの影響を話していきます。
主に考えるべき要素は二つです。
-
PoWにおけるハッシュパワー
-
署名に利用される暗号技術
そもそもなぜ今の段階でこんなことを考えなくてはならないのかと言いますと、一つは量子コンピュータができてからでは遅いというのと、情報分野において、攻撃側が防御側よりも有利であるという事があります。防御側はどこか一つでも破られると全体として致命傷を追う可能性があり365日完全でなければなりません、また攻撃側からするとどこか一点を一瞬でも隙をつければ良いよねということです。
1.PoWにおけるハッシュパワー
ビットコインにはコンセンサスアルゴリズムとしてPoWが採用されています。
PoWではマイニングという仕組みがとられます。マイニングとはトランザクションが入った新たなブロックを生成、その報酬としてBTCが貰えます。報酬としてBTCをもらうためにはブロックのナンス値を変更してそのハッシュ値が特定の条件を満たすようにしなければなりません。たくさん報酬をもらうためには、最適なナンスをいち早く他の人よりも探し当てるようなマイニングマシンが必要ということになります。
ビットコインに利用されるマイニングマシンは、2009年に初めのブロックをマイニングして以降技術的進歩とともに変遷しています。
CPU→GPU→FPGA→ASIC(2013〜現在)→??
可能性としては量子コンピュータの開発が進んでくると、上記の変遷から、application-specific integrated quantum ciricuit的なもの（便宜上以下QPU）が生まれるかもしれません。よく言われるのはGloverのアルゴリズムですが、計算量では二次的な加速が説明できるも、現在の遅いゲート(量子コンピュータでの一つ一つのオペレーション)速度では5~10年以内に総合的にASICを上回れるほどのスペックを実現するのは物理的にもかなり難しいようです。
移行されるケースを考えるとすると、コストとアルゴリズムの性能等を考え、ASICを上回るものが開発されれば良いということになります。移行すること自体は悪いことではありません。ですが一部のマイナーでハッシュパワーを独占する状況は好ましくないです。また、移行の際、BTCマイニング以外には用途が無い、QPUの使用者が一部に偏った状況が閾値を超えないなどの条件は必要になってくると思います。本質的には古典だろうが量子だろうがASICよりも上回るものが現れたら移行されるということだと思います。
2.署名に利用される暗号技術
2-1.量子コンピュータで現実的な時間で解読できるかもしれない暗号
去年(2020年)署名方式がECDSAからSchnorr署名に変更されました。大きなメリットは署名の加算が可能になり、マルチシグとの親和性が高まるといったところだと思います。ここではその仕組みまでは詳細には話せませんが、これらの署名が離散対数問題(以下DLP(ECDLP))の安全性が根拠になっているという点が重要です。
そのDLP仮定が量子コンピュータの台頭により崩れると公開鍵から秘密鍵が割り出される可能性が高まるということになります。
"量子コンピュータができたら暗号技術がやばい"という文脈でよく語られるのは素因数分解が解かれるというものですが、解像度低めでYes or Noと答えるならばYesです。(安心して欲しいのですが現在実行な規模ではせいぜい2桁数のレベルです。)
そして残念なことにDLPも多項式時間で解けてしまう事が証明されています（古典コンピュータであれば指数時間）。
解説は数学的な知識と量子の知識がある程度要求されるので詳しい話はここではできませんが、アルゴリズムの構造は素因数分解を解くshorのアルゴリズムを拡張させたような形です。準備段階では素因数分解を解くshorのアルゴリズムの一部を利用し、その後はDLPに合わせた出力関数とパラメータを設定します。そして求めたい解をqubit(bitの量子版)に格納する最後の手法も一致しています。DLPの構造と考えるパラメータ関係上、量子回路はより深く、また多くのレジスタを必要としそうです。
アルゴリズムの開発状況ですが、先月(2020年の12月)世界初？日本で実機にて求解に成功したリリースが出たようです。(こちらも安心して欲しいのですが2^x=1mod3程度のレベルです)
2-2.公開鍵は簡単に割り出せるものなのか
さて、公開鍵が判明するとDLP仮定であるSchnorr署名の安全性が揺らぐという事でしたが、秘密鍵から生成される公開鍵ですが、普段私たちが使っているbtcのアドレスとは異なります。以下に公開鍵からアドレスが生成されるまでを示します。
- sha-256でハッシュ化
- RIPEMD-160でハッシュ化
- プレフィックスの付加、チェックサムを生成、Base58エンコード
つまり普段私たちが使用しているアドレスから公開鍵を特定するためには1, 2で行われている二重ハッシュ化を破らなくてはなりません。このプロセスを量子コンピュータで解読するのは現段階の理論では困難と思われます。ハッシュ化を解読することに利用可能なアルゴリズムとして先ほど同様Gloverのアルゴリズムでの探索などの議論はありますが、計算量オーダーはN=2^k(k:bit数)とするとO(√N)で割り出す事が可能になるようです。(条件を入力する回路の構成の問題などもあると思います。)
これは致命的な問題にはならず、現実的な時間まで落とし込むことはできません。しかも別のアルゴリズムで二重ハッシュしているため、破られることはまずないと思われます。(仮に危険となったとしてもプロトコルの負荷を考えなければbit数を上げることで容易に安全性を保てます。)
さて、アドレスから秘密鍵を割り出すのは困難だという事がわかりましたが、安心はできません。
アドレスを生成し、誰かがそのアドレスにBTCを送った場合、その取引はブロックチェーン上に永遠に残ります。先ほど説明したようにアドレスには公開鍵のハッシュが含まれています。BTCを受け取った時にビットコイン上に公開されるデータは公開鍵のハッシュのみです。しかし、送られたBTCを使うと公開鍵がビットコイン上に公開されます。トランザクションに添付された署名を認証するためには、誰もが公開鍵を知らないと成立しないためです。
つまり、アドレスを再利用すると公開鍵はビットコイン上に公開されます。
視野を個人レベルにして考えると解決策は簡単で、アドレスを毎度変更すれば良いことになります。公開鍵のリスク以外にもプライバシーの観点からもアドレスの変更は推奨されています。
さて、個人レベルで考えればアドレスの再利用をしなければ良いということになりますが、これはあくまでも個人から個人への影響を考えただけであり、全体から個人を考えると影響は変わってきます。
2-3.ビットコイン全体の影響を考えてみる
この方の調べによると、2019年3月時点では、どうやら37%ものBTCの公開鍵が判明しているようです。(P2PKをはじめとするOutput)
37%ものBTCが危険にさらされるということは、たとえ自分のBTCがPKHで守られていてもビットコインの信頼が揺らいでしまうため、BTC自体の価値が下がってしまいます。
銀行を脳死で信頼し預けるのとは異なり、秘密鍵一つで管理できるというビットコインの良さが毀損されることになります。
2-4.ビットコインは無事か？その解決策は
解決策としては細かく考えれば様々あるかと思います。
①ハードフォーク（ソフトフォーク）にてDLP仮定以外のアルゴリズムの暗号を採用する。
②持っているBTCを新たな鍵に移動させる。
①に関してはDLP仮定以外のアルゴリズムは様々ありますが、現在、NISTでは耐量子計算機暗号が選考されています。そこでリリースされることとなった暗号などが候補となります。
②に関してはBTCをどこかへ預けていない限りは自分の秘密鍵が移動させる手段のため、来たるタイミングで移動させることになります。
まとめ
- マイニングマシンがASICから量子アルゴリズムを使えるマシンになる可能性はある。
- 現在のビットコインのままでは公開鍵から秘密鍵が割り出される。
- HF,SFして量子コンピュータに対しても安全な暗号を採用する。
- BTCを安全な暗号の鍵へ移動させる。
- もしかしたらあの人のアドレスに動きがあるかも！？
ポジトークにもなりますがDLP仮定を崩すほどの量子コンピュータはできて欲しいですしできると思っています。それと共にBTCも貧困学生ながら持ってるので応援してます。さらに詳細に議論された論文も見つけたので、時間ができたら頑張って読んでみます。
ビットコインのアップデートではここでの議論はもちろん話されているので特に不安になることもないと思います。私自身は今は量子コンピュータでの脆弱性ではなく、体の脆弱性に気を使おうと思います。
以上です！DYOR！
間違っている部分があれば教えていただけたら幸いです。さらに細かい話を知っているというのもありがたいです。投げ銭いただけたら喜びます！
(おまけと言ってはなんですが、以下ではなぜ量子コンピュータは速いのかの(半)直感的理解と量子が暗号を破るだけでなく量子を利用した暗号について触れたいと思います。)
