ECDSA署名のサイズに対するランポート署名

先月Bitcoin-Devメーリングリストに投稿されたBitcoinにランポート署名を導入する提案↓

Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

以前、OP_CATを利用した提案はあったけど↓、↑はOP_CATを必要とせず現状のBitcoinで動作するというもの。

ECDSA署名とDERエンコーディング

通常署名対象のメッセージは、Bitcoinであればトランザクションデータになるが、今回の提案ではトランザクション内のECDSA署名の長さに対してランポート署名しようというもの。

署名の長さに対するランポート署名ということは、そのランポート署名は直接トランザクションデータにはコミットしていないため、そのランポート署名をネットワーク上で確認したユーザーであれば誰でも同じ長さのECDSA署名を作ればランポート署名はそのまま再利用できることになってしまうので、長さに対する署名を作っても意味ないのでは？と思ったけど、攻撃者が署名を再利用する際に追加の計算量を課すようにする仕組みを含めてるみたい。具体的にその仕掛けを見ていく。

ECDSA署名

まず、前提となるECDSA署名について。公開鍵P = xG（x = 秘密鍵）と、署名対象のメッセージmに対するECDSA署名は以下のように作られる。

ランダムなnonce kを選択
Public nonce R = kGを計算し、r = R.x（点Rのx座標）とする
${s = \frac{H(m) + r \cdot x}{k}}$ を計算する。（H(m)はメッセージダイジェスト）
(r, s)がECDSA署名

DERエンコード

Bitcoinで使用している曲線secp256k1のECDSA署名(r, s)はそれぞれ256 bit（32バイト）の値になる。BitcoinではこれをDER形式でエンコードしており、その構造は↓

（rとsの複合構造を示す）ヘッダーバイト0x30
以降のデータ長を表す1バイトの値
整数を表すヘッダーバイト0x02
署名値のrの値の長さを表す1バイトの値
署名値r
整数を表すヘッダーバイト0x02
署名値のsの値の長さを表す1バイトの値
署名値s

↑から分かるように、rとsの値は可変長にできるので、例えば先頭に0x00が続く場合そのデータは省略される。そのため、ECDSA署名のサイズは可変となる。省略がない場合は、基本的にサイズは、6個のヘッダーバイトと2つの32バイト値で、6 + 32 * 2 = 70バイト*1。

小さなr

今回の提案で例示されている署名の長さは58〜59バイトと、↑の通常のECDSA署名と比べて小さなサイズになっている。これは、署名生成に使用するnonce kの値をk = 1/2と固定している点に起因したサイズになる。k = 1/2とした場合、Public nonce R = kGのx座標の値は、

0x3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63

という21バイトの値になり、32バイトに比べて11バイト小さい値になる。

DER形式の場合、rとsの値は固定長ではないので、r = 21バイトであれば、その合計サイズは、58〜59バイトとなる。

通常ECDSA署名の安全性を担保するためには、nonce kを毎回ランダムに選択する必要があり、↑のような固定のnonceを使用すると秘密鍵の漏洩に繋がるので絶対にやってはいけないこと。ただ、今回の提案は、量子コンピューターなどにより既に安全性の根拠とされる離散対数仮定が破られているという前提での話。

もし↑よりさらに1バイト小さいr（つまり20バイト）を計算しようとすると、k = 1/2のケースのような数学的なショートカットがなければ、 ${2^{256 - 160} = 2^{96}}$ という膨大な計算コストがかかる（256は曲線の位数）。つまりk = 1/2のrの値は、これ以上小さい値を見つけるのが困難な値

このr値を常に使用すると、ECDSA署名のサイズは59バイトになる。

sのサイズ

r値のサイズが固定されると、署名のデータ長に影響するのはsの値のみ。s値は↑にも書いたように、

$s = \frac{H(m) + r \cdot x}{k}$

であり、今回の場合kは既知であるため、この署名データを見た人は誰でも秘密鍵xの値を知ることができる。この状態で、s値のいじろうとするとH(m)がその調整パラメーターになる。つまりトランザクションデータを変更しながらs値のサイズを調整することになる。

s値の先頭が0になるような確率は1/256。その場合、s値は31バイトとなり、上記のr値と合わせてDER形式のECDSA署名のサイズは58バイトとなる。

ランポート署名

一般的に、署名は署名対象のメッセージにコミットする。Bitcoinであれば256 bitのメッセージダイジェストにコミットする。↑のOP_CATを利用したランポート署名は、ECDSA署名データをHash160した20バイトの値を署名対象のメッセージとしていたけど（つまり間接的にTxにコミットしている）、今回のスキームはECDSA署名のサイズがメッセージになる。

ECDSA署名のサイズは↑のrにより58バイトと59バイトのケースを想定し、それぞれのケースにおけるハッシュロックスクリプトを構成することで、1 bit値に対するランポート署名のように機能する。↓

OP_DUP <公開鍵> OP_CHECKSIGVERIFY OP_SIZE <59> OP_EQUAL
OP_IF
  # サイズが59バイトと等しい場合
  OP_SHA256 <ハッシュ値A> OP_CHECKEQUALVERIFY
OP_ELSE
  # サイズが<59>バイト以外の場合
  OP_SHA256 <ハッシュ値B> OP_CHECKEQUALVERIFY
OP_ENDIF

提供された署名のサイズが59バイトの場合は、ハッシュ値Aのプリイメージを公開し、59バイト以外の場合はハッシュ値Bのプリイメージの公開が必要になる。

署名対象がECDSA署名のサイズなので、ハッシュロックをアンロックしたサイズのECDSA署名を作れる攻撃者は、資金を自分に送るトランザクションを作ることができる。つまり、↑だけだと、攻撃者も1/256の確率で、s値が1バイト少ない58バイトの署名が作れてしまう。

そこで、↑のランポート署名の検証スクリプトを各ハッシュロックが異なるよう複数個用意する。その総数をn個とするとn bitのメッセージに対するランポート署名として機能する。

58バイトの署名の数をm個とすると、ハッシュロックのプリイメージを知っている実際の所有者がm個の58バイトの署名とn - m個の59バイトの署名を生成する確率は、

$(\frac{255}{256})^{n-m} \times (\frac{1}{256})^{m} \times {n \choose m}$

攻撃者が攻撃するためには、所有者による署名の内容（プリイメージ）を確認した上で同じ場所に同じサイズの署名を作成する必要があり、その生成の確率は、↑から二項係数を除いた↓

$(\frac{255}{256})^{n-m} \times (\frac{1}{256})^{m}$

例示されていたn = 800、m = 10の場合、正規の所有者は1,000回の試行で上記署名を生成できる一方、攻撃者は、 ${2^{84}}$ 回の試行が必要になる。

上記のように、正規の署名トランザクションでプリイメージを確認した後でも、それに対して有効なサイズの署名を計算するのに膨大な計算コストを課すことで、署名サイズに対する署名であっても不正利用できない仕組みを提案している。

確かに現状のBitcoin スクリプトで構成することは可能だけど、計算コストを課すために非常に多くの署名が必要になるので、現状実用的ではなさそう。また、Taprootで使用するSchnorr署名の方は署名サイズは64バイト固定なので、このトリックは使えない。

*1:ただ、2つとも符号付き正数なので最上位バイトが0x80〜0xffの場合、先頭に0x00が付加される。なので省略がない場合のサイズの範囲は70〜72バイト

Develop with pleasure!

福岡でCloudとかBlockchainとか。