Develop with pleasure!

福岡でCloudとかBlockchainとか。

ECDSAとOP_CATを使ったコベナンツ

Covenants ECDSA Bitcoin

OP_CATとSchnorrのトリックを使ってBitcoinでコベナンツを実装するAndrew Poelstraの提案について以前書いたけど↓

techmedia-think.hatenablog.com

その後、Robin Linusが同様のことをECDSAで行う方法を公開してた↓

Emulate covenants using only OP_CAT and ECDSA signatures · GitHub

ECDSA

秘密鍵をx、対応する公開鍵をP = xGとした場合、メッセージmに対するECDSA署名を生成する通常の手順は↓

  1. シークレットnonce kをランダムに選択する。
  2. R = kGを計算する。
  3. r = R.x（RのX座標）とする。
  4. {\mathbb s = \frac{H(m) + r \times x}{k}}を計算する（Hはハッシュ関数）
  5. (r, s)がECDSA署名

トリック

Schnorrのトリックと同様に、ECDSAの場合もxとkを以下のような固定値にする。

  • k = 1とする（Schnorrのトリックと同様で、R = Gとなる（Gは楕円曲線のベースポイント））
  • x = 1/rとする

この2つの値が上記のように固定化されると、署名値sはs = H(m) + 1となる。つまり、sの値は署名対象のメッセージのハッシュ値に1を加算した値となり、Schnorrトリックと同様の署名が得られるというもの。

OP_CATとの組み合わせ

Bitcoinの場合、mの値は（witnessを含まない）トランザクションデータなので、H(m)の計算はBitcoin Script内で行える。RとPはそれぞれ固定値（R = G、P = xG = 1/r G）なので、実際にH(m)の計算で変動部分はm、つまりコベナンツのUTXOを使用する際のトランザクションデータになる。このトランザクションデータをスタック上の要素から取得して、最終的にdouble-SHA256してH(m)を求める。

この時、組み立てるトランザクションデータの配置場所は2つに分かれる：

前者はコベナンツとして強制する内容を定義するもので主にUTXOを使用するトランザクションのアウトプットのデータ（ロックスクリプトや金額）、後者はロックスクリプトで強制する必要のない（できない）データで、特にコベナンツのUTXO自体のOutPointの情報など。

この二種類のデータを、スタック上でOP_CATを使って連結してトランザクションデータを構築し、そのdouble-SHA256値を計算してH(m)とする。なお、OP_CATはBitcoinでは現状利用できないが、再度有効化されたとしてもスタック要素については520 byteの最大サイズ制限があるので、それを超えるトランザクションを構成することはできない*1。

検証スクリプト

ロックスクリプト内では、Schnorrトリックと同様に固定のPとRに対する署名検証を要求する。Schnorrトリックの場合はPもRと同じGだったけど、ECDSAトリックの場合はP = 1/r Gとなるのが異なる。↑の投稿では具体的な検証スクリプトは書かれてなかったけど、以下のようなスクリプトになると思われる。

OP_DUP <R> OP_SWAP OP_CAT <P> OP_CHECKSIGVERIFY

このスクリプトを、↑の仕組みで計算されたECDSAの署名値sがスタックにある状態で実行すると、（カッコ内はスタックの状態で、右が上位）：

  1. スクリプト実行前のスタックの状態（<s>）
  2. OP_DUPでスタックの最上位要素を複製（<s> <s>）
  3. スタックにRをプッシュ（<s> <s> <R>）
  4. OP_SWAPで、スタックの上位2つの要素を入れ替える（<s> <R> <s>）
  5. OP_CATでスタックの上位2つの要素を連結（<s> <R||s>）
  6. スタックにPをプッシュ（<s> <R||s> <P>）
  7. OP_CHECKSIGでスタック上の署名R||sと公開鍵Pに対して署名検証をする
  8. 最後にトランザクションデータ<s>のみがスタックに残る

7の署名検証をパスするためには、トランザクション自体が↑のように組み立てられたトランザクションになっていることが求められる。

+1の対応

sの値はH(m) + 1なので、実際には、スタック上で組み立てたトランザクションのハッシュ値に対して+1を加算する必要がある。これは、Schnorrのトリックでも同じ。

まず、H(m)の値の最下位バイトが0x01となるようにトランザクションデータを調整する。これはトランザクションを組み立てる際にデータ（トランザクションのロックタイムとかインプットのシーケンス番号とか）を変更しながら0x01で終わるデータを見つけることで実現できる。このようなデータは平均256回の試行で見つかる。トランザクションのハッシュが0x01で終わるのがわかっていれば、署名値sの値は0x02で終わることになる。

そこで、↑のようにスタック上でトランザクションのハッシュ値を計算はするのだけど、そのハッシュ値の最終バイトを削ったハッシュ値（31バイト値）を同じくwitnessとして提供させ、その値に01をOP_CATで付与したデータとスタック上で計算したハッシュ値が同じになることをOP_EQUALVERIFYでチェックしておく。そして、この31バイトのハッシュ値sに対して、OP_CATを使って02を付与して上記の署名検証をパスさせ、最終的にスタックに残るsに対してはOP_CATで01を付与する。

sの値を31バイト値として、この処理を行うよう↑の検証スクリプトを書き直すと、

OP_DUP 02 OP_CAT <R> OP_SWAP OP_CAT <P> OP_CHECKSIGVERIFY 01 OP_CAT

となる。

*1:こういうのもあって、Elementsではストリーミングハッシュ用opcodeとかを導入してるのかな？