最近Bitcoin-Devメーリングリストに、OP_CATを使ってBitcoinに量子耐性をもたせる方法について投稿されてたのが興味深かったので見てみる↓
[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]
アイディアは量子耐性のあるランポート署名をBitcoin Scriptで検証するというもので、その仕組みはJeremy Rubinの↓のブログから来てる
https://rubin.io/blog/2021/07/02/signing-5-bytes/
ランポート署名
量子耐性のある署名アルゴリズムの１つがランポート署名で、一方向性関数（通常、暗号学的ハッシュ関数）を利用しており、アルゴリズム自体はとてもシンプル。
秘密鍵の生成
秘密鍵として、n個のランダム値のペアを生成する（nは署名対象のメッセージのビット数に依存する）。ここではn=256とし、各ランダム値のサイズも256 bitであると仮定すると、秘密鍵のサイズは、2 ✕ 256 ✕ 256 = 16 KBになる。
公開鍵の生成
公開鍵の作成は、秘密鍵のハッシュ値になる。つまり↑の2✕256 = 512個の乱数をハッシュしたもの。このハッシュ関数も256 bitとすると秘密鍵と同様サイズは16 KB。
この公開鍵のリストを公開鍵として公開する。
ハッシュ関数にもよるけど、楕円曲線暗号の秘密鍵が32 B、公開鍵が（圧縮版で）33 Bであることを考えると鍵長は大きい。
署名の生成
メッセージに署名する手順は↓
- メッセージmをハッシュする→H(m)
- H(m)を２進展開する。
- 2の各bit値に基づいて、対応する秘密鍵をピックアップする。bit = 0の場合はペアの最初の数値を、bit = 1の場合はペアの２つめの値を選択する。
- 3をメッセージのハッシュ値分行うと256個の数値のリストが生成され、これが署名データになる。サイズは256✕256 bit = 8 KB。
つまり、秘密鍵はn個の乱数値のペアで、署名対象のメッセージのビット値によって、そのペアのいずれかをピックアップしたものが署名データになる。
こういうアルゴリズムなので（署名を提供する＝秘密鍵の一部の提供になるので）、署名に使用した秘密鍵は2回以上再利用してはならない。
署名の検証
↑で生成した署名を検証する手順は↓
- メッセージmのハッシュ値を計算する→H(m)
- H(m)を２進展開する。
- 2の各bit値に基づいて、対応する公開鍵をピックアップする。bit = 0の場合はペアの最初の数値を、bit = 1の場合はペアの２つめの値を選択する。
- 署名値の256個の値のハッシュ値を計算する。
- 3と4のハッシュ値がすべて一致した場合、署名は正しい。一致しなければ間違った署名データになる。
Bitcoin Scriptでランポート署名を検証
Bitcoinで↑のランポート署名を検証するにはどうしたらいいか？当然、Bitcoin Scriptにはランポート署名を直接検証できるopcodeは存在しないので、↑のブログ記事では、Bitcoin Scriptを使ってランポート署名の検証をしている。ここで検証しているのはトランザクションインプットのnSequenceを署名対象のメッセージとして見立てて、それに対して有効なランポート署名が提供されているかチェックするスクリプト↓
ここでは、nSequenceの値が53593（2進展開すると1101000101011001）であることを要求している。この場合、メッセージの長さは16 bitなので、n = 16。
<pk> CHECKSIGVERIFY 0 SWAP sha256 DUP <H(K_0_1)> EQUAL IF DROP <1> ADD ELSE <H(K_0_0)> EQUALVERIFY ENDIF SWAP sha256 DUP <H(K_1_1)> EQUAL IF DROP <1<<1> ADD ELSE <H(K_1_0)> EQUALVERIFY ENDIF SWAP sha256 DUP <H(K_2_1)> EQUAL IF DROP <1<<2> ADD ELSE <H(K_2_0)> EQUALVERIFY ENDIF SWAP sha256 DUP <H(K_3_1)> EQUAL IF DROP <1<<3> ADD ELSE <H(K_3_0)> EQUALVERIFY ENDIF SWAP sha256 DUP <H(K_4_1)> EQUAL IF DROP <1<<4> ADD ELSE <H(K_4_0)> EQUALVERIFY ENDIF SWAP sha256 DUP <H(K_5_1)> EQUAL IF DROP <1<<5> ADD ELSE <H(K_5_0)> EQUALVERIFY ENDIF SWAP sha256 DUP <H(K_6_1)> EQUAL IF DROP <1<<6> ADD ELSE <H(K_6_0)> EQUALVERIFY ENDIF SWAP sha256 DUP <H(K_7_1)> EQUAL IF DROP <1<<7> ADD ELSE <H(K_7_0)> EQUALVERIFY ENDIF SWAP sha256 DUP <H(K_8_1)> EQUAL IF DROP <1<<8> ADD ELSE <H(K_8_0)> EQUALVERIFY ENDIF SWAP sha256 DUP <H(K_9_1)> EQUAL IF DROP <1<<9> ADD ELSE <H(K_9_0)> EQUALVERIFY ENDIF SWAP sha256 DUP <H(K_10_1)> EQUAL IF DROP <1<<10> ADD ELSE <H(K_10_0)> EQUALVERIFY ENDIF SWAP sha256 DUP <H(K_11_1)> EQUAL IF DROP <1<<11> ADD ELSE <H(K_11_0)> EQUALVERIFY ENDIF SWAP sha256 DUP <H(K_12_1)> EQUAL IF DROP <1<<12> ADD ELSE <H(K_12_0)> EQUALVERIFY ENDIF SWAP sha256 DUP <H(K_13_1)> EQUAL IF DROP <1<<13> ADD ELSE <H(K_13_0)> EQUALVERIFY ENDIF SWAP sha256 DUP <H(K_14_1)> EQUAL IF DROP <1<<14> ADD ELSE <H(K_14_0)> EQUALVERIFY ENDIF SWAP sha256 DUP <H(K_15_1)> EQUAL IF DROP <1<<15> ADD ELSE <H(K_15_0)> EQUALVERIFY ENDIF CHECKSEQUENCEVERIFY
先頭の<pk> CHECKSIGVERIFYは単純に既存のECDSA署名検証の仕組みで、これはランポート署名とは無関係。
H(K_0_0)やH(K_0_1)、…H(K_15_0)、H(K_15_1)の値は、ランポート署名に用いる公開鍵の値。H()はハッシュ関数で、中身のK_0_0が対応する秘密鍵の値。
このスクリプトをアンロックするために必要なscriptSigは、CHECKSIGVERIFYで評価される通常のECDSA署名と、16個のランポート署名のデータ↓
K_15_1 K_14_1 K_13_0 K_12_1 K_11_0 K_10_0 K_9_0 K_8_1 K_7_0 K_6_1 K_5_0 K_4_1 K_3_1 K_2_0 K_1_0 K_0_1 <sig>
ランポート署名の検証ロジックである↓の部分は、
SWAP sha256 DUP <H(K_0_1)> EQUAL IF DROP <1> ADD ELSE <H(K_0_0)> EQUALVERIFY ENDIF
（CHECKSIGVERIFYの検証が終わったとして）次のように評価される
| No | 実行処理 | 実行後のスタック |
|---|---|---|
| 1 | スタックの先頭２つの順番を入れ替える。最初に評価する時点ではスタックの先頭２つは0 K_0_1なのでこれが入れ替わってK_0_1 0になる。 |
K_0_1 0... |
| 2 | 続いて先頭の要素がSHA-256される。 | H(K_0_1) 0 K_1_0 K_2_0... |
| 3 | DUPを実行すると先頭の要素が複製される。 |
H(K_0_1) H(K_0_1) 0 K_1_0 K_2_0... |
| 4 | <H(K_0_1)>がプッシュされる。 |
H(K_0_1) H(K_0_1) H(K_0_1) 0 K_1_0 K_2_0... |
| 5 | EQUALによりスタックの先頭２つが比較される。ここでは、scriptSigで提供された秘密鍵と、対応する公開鍵のペアの２つめを比較している。先頭２つはH(K_0_1) H(K_0_1)で等しいのでTRUEがプッシュされる |
TRUE H(K_0_1) 0 K_1_0 K_2_0... |
| 6 | IFが評価されスタックの先頭はTRUEであるため、IF分岐に入る。 |
H(K_0_1) 0 K_1_0 K_2_0... |
| 7 | DROPにより、H(K_0_1)が削除される。 |
0 K_1_0 K_2_0... |
| 8 | <1>がスタックにプッシュされ、ADDによりスタックの先頭２要素が加算される。つまり1 + 0 = 1。 |
1 K_1_0 K_2_0... |
5の分岐でFalseになった場合は、scriptSigの秘密鍵のハッシュともう１つの公開鍵（ペアのうちの１つめ）を比較する。この場合、メッセージの該当bitは0であるため、8の加算は発生しない。
これを繰り返すと、最終的にスタックにはメッセージ53593が残ることになり、それをCHECKSEQUENCEVERIFYで評価する。
というスクリプトにより、やろうと思えば今でもスクリプトを使ってランポート署名の検証は可能。
量子耐性
↑の仕組みを使って量子耐性を持つビットコインを作ろうというのが、続きのブログ記事↓
https://rubin.io/blog/2021/07/06/quantum-bitcoin/
量子コンピューターにより楕円曲線暗号の離散対数仮定が破られたとしても（つまりP = xGとなる公開鍵Pから秘密鍵xを逆算できるようになっても）コインを安全に保つためには、従来の署名データの検証に加えて（ここは量子コンピューターにより侵害可能）、署名データのHash160値を↑のランポート署名で検証すればいいというアイディア。
Hash160だと署名されるメッセージダイジェストの長さは20Bになるので、↑の検証を4バイトずつ実行して、その結果をOP_CATで結合する処理を5回実行した結果が、Hash160(ECDSA署名)と等しければコインを使用できるようするということみたい。ただ、これを実現するためにはOP_CATをBitcoinで再度使えるようにする必要がある。
あと前述したように、ランポート署名の鍵や署名データのデータ長は大きいので、トランザクションサイズはこれまでよりも大幅に大きくなる。
