既存のUTXOを量子コンピューター登場後でも安全に使用するための提案
- CTO Tech blog

Bitcoin Optechのニュースレター #348で紹介されていたTim Ruffingの以前の提案↓
https://gnusha.org/pi/bitcoindev/1518710367.3550.111.camel@mmci.uni-saarland.de/
は、量子コンピューター登場後でも既存のUTXOを安全に使用できるようにするスキームの提案。一般的には、Guy Fawkesの署名スキームとして知られてるみたい。
量子コンピューターの脅威
量子コンピューターで暗号解読が可能になるというのは、既存のブロックチェーンの暗号技術の中では主に楕円曲線暗号の安全性の仮定である離散対数問題が解かれてしまうことを指す。
秘密鍵をx
、楕円曲線のベースポイントをG
とした場合、公開鍵はG
をx
回加算したP = xG
となる。離散対数問題の困難さからP
からx
は逆算できないとされている。
これが1994年に、量子コンピューター上で実行可能な素因数分解のアルゴリズムとしてショアのアルゴリズムが発表された(楕円曲線の離散対数問題に対しても拡張適用が可能)。
※ ただ、現状の量子コンピューターはまだショアのアルゴリズムを実行してBitcoinの楕円曲線の離散対数問題を解くことができるレベルにはない。
Bitcoin界隈でも最近、量子コンピューターに対して脆弱なUTXOをどう扱うかの議論が段々と盛り上がっていて、脆弱なコインは破棄すべきという意見も多い。そんな中、Tim Ruffingの提案は、脆弱なUTXOを可能な限り保護できるという意味では有用な提案に思える。
耐量子のコミットメントスキーム
まず、前提としてショアのアルゴリズムの対象は、公開鍵が予め分かっているものに限定される。そのため、P2PKHや、P2WPKH、P2SH、P2WSHなど公開鍵がハッシュされている場合、それらをブロックチェーンで一度でも使っていない(アドレスの再利用をしていない)限り、その公開鍵は明らかになっていない。
今回保護される対象は、公開鍵が一度も公開されたことのないUTXO。そのようなUTXOも、使おうとすると、Txを作成し、そのインプット内に公開鍵がセットされるため、Txがブロックチェーンに格納される前に、ネットワークでTxが確認された段階で量子コンピューターによる攻撃を受ける可能性がある。まぁ実際にブロックに格納されるまでの間に量子コンピューターの攻撃が現実的に可能なレベルにいつなるのか?というのははあるけれど、攻撃タイミング自体は存在する。
このような攻撃を防ぐのが↑の提案。
まずプロトコル全体として、新しく鍵導出関数KDFと、認証付き対称暗号(Enc/Dec)を用意する必要がある。
コミットフェーズ
脆弱なUTXOを持つユーザーは、そのUTXOを使用する前に(使用すると攻撃の可能性があるので)、以下の手順で、UTXOへのコミットメントを作成する。
- UTXOのscriptPubkeyを生成するのに使用した公開鍵(
chal
とする)を入力として、鍵導出関数を実行し、対称鍵k = KDF(chal)
を導出する。 - UTXOを使用するトランザクションを
tx
を作成して署名する。ただし公開(ブロードキャスト)はしない - 対称暗号を使って導出した鍵
k
でtx
を暗号化し、コミットメントc = Enc(k, tx)
とする。 - コミットメント
c
を別の量子安全なUTXOを使用したトランザクションに含めて、ブロードキャストする。 - 4のトランザクションがチェーン内で深く承認されるまで待つ。
※ 同じscriptPubkeyを持つUTXOが複数ある場合、そのすべてを2で作成するトランザクションでインプットとする。
デコミットフェーズ
c
が再編成されないほど承認されたら、デコミット=脆弱なUTXOを使用する。デコミットメントはシンプルにd = chal
(要は公開鍵のデータ)で、これをブロックチェーンに公開する。
k = KDF(d=chal)
が導出され、Dec(k, c)
が正しく復号された場合、つまりtx = Dec(k, c)
であり、このtx
がUTXOの正しい所有者のトランザクションとしてチェーンに組み入れられる。
というコンセンサスの変更を行う。
流れとしては、コミットフェーズの段階で脆弱なUTXOを正規のユーザーが望むトランザクションにコミットすることで、デコミットフェーズで公開鍵が明らかになった後でも量子コンピューターを利用した敵対者に対して正規のユーザーのトランザクションが優先されるようにするというもの。
このような変更をソフトフォークとして導入すると、
- 量子コンピューターに対して脆弱なコインを破棄する決定がされたとしても、保護できるコインの裾野は広がるし、
- 予めすべてを量子安全なスキームに移行しなくても、実際に使用する際に↑のフローを実行すれば良い
というメリットがある。
ブログ元記事へのリンク
Chaintopeでブロックチェーンの未来を共に創りませんか?
Chaintopeは、独自のブロックチェーン「Tapyrus」と、開発プラットフォーム「Tapyrus Platform」を活用し、デジタル社会の信頼基盤を構築しています。
私たちは、ブロックチェーン技術の可能性を最大限に引き出し、社会に新しい価値を提供することを目指しています。
募集職種:
ブロックチェーンエンジニア
アプリケーションエンジニア
インフラ・保守エンジニア
プロジェクトマネージャー
フィールドセールス
Chaintopeで働く魅力:
最先端のブロックチェーン技術に触れる機会
リモートワークやフレックスタイム制による柔軟な働き方
専門性の高いチームとの協働
ブロックチェーン技術に情熱を持つあなたのスキルを、私たちのチームで活かしませんか?
詳細は、採用情報をご覧ください。
https://www.chaintope.com/recruit/