Quantum Proofing Bitcoin with a CAT
最近、Bitcoin Scriptとランポート署名を使って最大5バイトの値に署名する方法についてブログ記事を公開した。
それ自体は、正しく動作するが、少し制限がある。より長いメッセージに署名できるとしたらどうだろう？最大20バイトに署名できれば、量子安全である可能性が高いHASH160ダイジェストに署名できる。
署名のHASH160ダイジェストに署名するというのはどういう意味？何？なぜそうするの？
結論から言うと、仮に量子コンピューターがECDSAを破ることができたとしても、秘密鍵は明らかになるが、実際に署名された内容を改ざんすることはできない。私は友人の暗号学者Madars Virza に、自分の直感が正しいかどうか尋ねたところ、彼は十分であることを確認したが、これに頼る前にもっと詳しく分析する価値があることは間違いない。ECDSA署名は、別の形態に変えることができるが、署名を不変なものにした場合、コミットメントを開くことができる値は１つだけのはずだ。
ECDSA署名を量子証明署名アルゴリズムで署名すること要求すれば量子証明Bitcoinが出来上がる。そして、前回説明した5バイトの署名方式は量子的に安全であるランポート署名だ。残念ながら最低でも20バイトの連続したバイトが必要で、そのためOP_CATのような演算が必要だ。
OP_CATはスタックを変更するため、Segwit v0に直接ソフトフォークすることはできない。その代わり、検証セマンティクスを使用する新しいopcode、文字列のスプライスが等しいかどうかをチェックするOP_SUBSTRINGEQUALVERIFYの使用方法も紹介する。
面白い情報：OP_CATはSatoshiが密かに大量のopcodeをフォークした2010年までBitcoinに存在していた。したがって、理論的には、元のBitcoinの実装は、ポスト量子暗号をサポートしていた！
code: python
... FOR j in 0..=5
<0>
... FOR i in 0..=31
SWAP hash160 DUP <H(K_j_i_1)> EQUAL IF DROP <2**i> ADD ELSE <H(K_j_i_0)> EQUALVERIFY ENDIF
... END FOR
TOALTSTACK
... END FOR
DUP HASH160
... IF CAT AVAILABLE
FROMALTSTACK
... FOR j in 0..=5
FROMALTSTACK
CAT
... END FOR
EQUALVERIFY
... ELSE SUBSTRINGEQUALVERIFY AVAILABLE
... FOR j in 0..=5
FROMALTSTACK <0+j*4> <4+j*4> SUBSTRINGEQUALVERIFY DROP DROP DROP
... END FOR
DROP
... END IF
<pk> CHECKSIG
これは長いスクリプトだ。しかし、収まる？20バイトのメッセージを検証する必要があるが、各bitには約10バイトのスクリプト、１つの数字につき平均3.375バイト（プッシュを含む）、2つの21バイトの鍵で55.375バイトのプログラムスペースと1bit ごとに21バイトのwitness要素が必要になる。
ぴったり、20 * 8 * 55.375 = 8860となり、残りのロジックで必要な容量は制限値より1140バイトすくなくなり、十分な容量になる（残りのロジックに必要な容量は約15〜40バイトで、1100バイトはカスタム署名チェックのために残る）。ハッシュガジェットのスタックサイズは160要素で、3360バイト。
これは3進数表現に拡張することで、もう少し効率的にすることができる。
code: python
SWAP hash160 DUP <H(K_j_i_0)> EQUAL IF DROP ELSE <3**i> SWAP DUP <H(K_j_i_T)> EQUAL IF DROP SUB ELSE <H(K_j_i_1)> EQUALVERIFY ADD ENDIF ENDIF
これにより、tritあたり約85バイトで、101 trit（log(2**160)/log(3) == 100.94）になるはずなので、約8560バイトで、少し小さくなる。しかしwitnessスタックはたった2121バイトになる。
宿題として、誰かがこのプロトコルに最適な基数の選択を証明できるかもしれない。私の推測では基数4が最適。
Taproot?
Taprootについては？私の知る限り、コミットメント方式（Q = pG + hash(pG || m)G）は、量子コンピューターであっても、mに対して安全に開くことができる。qG = Qとなるようなqを見つけることは簡単かもしれないが、仮にkeypathを無効にした場合に、Taprotの方程式が成立するようなmとpを見つけることは難しいはずだが、その主張をよりよく証明する必要はある。したがって、この救いrぷとはTapscriptのパスの中に入れ子にすることができる。Tapscriptは長さの制限を設けてないので32バイトのハッシュも使用できる。
さらに鍵を再利用できるようにするため、1つのTaprootツリー内に多くのランポート鍵をコミットし、1つのアドレスが期限切れまでに何前回も使用できるようにすることもできる。これは偶然の仕様をサポートするのではなく、保護するための措置として使用できる。
さらに、SchnorrはECDSAよりも強力な非malleability特性を持っている。署名は承認されたトランザクションに高速され、一度ランポート署名が署名すれば量子コンピューターでも資金を盗むことはできない。