Develop with pleasure!

福岡でCloudとかBlockchainとか。

Bitcoin CoreはなぜECDSA署名にLOW Rを適用するようになったのか？

Bitcoin ECDSA

Bitcoinでは、送金時にトランザクションにセットする署名に、現在ECDSA署名を採用している。

秘密鍵をx、対応する公開鍵をP = xGとした場合、メッセージにｍに対するECDSA署名は以下のように作成する。

署名の作成

  1. ランダムな値kを選択する。
  2. 点R = kGを計算する（Rが楕円曲線上の有効な点でない場合ｋの選択からやり直す）。
  3. 点Rのx座標をrとする。
  4. {s = \frac{H(m) + rx}{k}} を計算する。
  5. 計算した(r, s)のペアが署名のデータとなる。

これは標準的なECDSAの署名ルールだが、Bitcoin Coreの場合、ECDSA署名作成時に以下のようにいくつかルールを加えている（コンセンサスルールではないが、標準トランザクションルールに該当するものはある）。

LOW Sルール

BitcoinではSegwitの導入によりTXIDに関するmalleabilityは排除されたが、ECDSAの署名自体にはmalleabilityが存在する。署名値(r, s)のsの値をマイナスにした -s mod nを使ってもsの値は異なるが正しい署名と判断される。このため、Segwitによりwitness領域に移動した署名データのs値を有効な書き換えることは可能になってしまうので、Bitcoin CoreではLOW_Sルールというのを設けている。

このルールでは、sの値は最大でも曲線の位数を2で割った値以下でなければならないというもので、これによりsを利用したmalleabilityを除外する。この仕様はBIP-146としても定義されている↓

techmedia-think.hatenablog.com

決定性署名

Bitcoin Core（libsecp256k1）では、トランザクションの署名を生成する際に、kの選択を決定論的に行うRFC 6979の決定性署名のルールが適用されている。このため、kはランダムに選択されるのではなく、トランザクションのデータから決定論的に導出される。

techmedia-think.hatenablog.com

この仕組みにより、実装の誤りによりkの生成に偏りが発生するようなことを防ぐことができる。

署名のフォーマット

計算した署名データをトランザクションにセットするわけだが、このときBitcoinではDERエンコードした値をセットする。フォーマットの詳細は

techmedia-think.hatenablog.com

に記載しているけど、簡単に言うと

0x30 データ長 0x02 rのデータ長 R 0x02 sのデータ長 S SIGHASH_TYPE

という構成のデータになる。

そして今回新しいルールが実装に追加され↓、Bitcoin Core 0.17.0でリリースされた。

LOW R

github.com

ECDSAの署名自体にmalleabilityの問題があり、それを解決するのにLOW Sルールを適用するのは理解できるが、このLOW Rのルールは何を意味するのか？

LOW Rの意図

まず署名データは↑のDERフォーマットであることから、

  • 0x03
  • データ長
  • 0x02
  • rデータ長
  • 0x02
  • sデータ長
  • SIGHASH_TYPE

で7バイト使い、残りはrとsの値になる。このrとsの値はそれぞれ256 bitの値＝32バイトのデータになるが、DERフォーマットではこれを符号付き整数として扱うため、最上位オクテットが0x80〜0xffの場合、そのままでは負の数として扱われてしまうので、先頭に0x00を付与して正の数とするため1バイト追加され33バイトになる。

sのデータについては↑のLOW Sルールがmalleabilityの解決のため導入された結果、32バイトが標準トランザクションルールとして強制されるが、rにはこのルールが無いため、選択されたkの値によって33バイトになったり32バイトになったりする。

まぁ、そもそもDERフォーマットが効率的でないというのもあるんだけど、既にSatoshiの時代から決まっているのでしょうがない。

今回の変更の目的は、rにも同様のLOW Rルールを適用することで、rのデータ長が常に32バイトになるようにし、データ容量を削減しようというものだ。データを削減すると言ってもrのDER形式の署名データが33バイトになるケースが1バイト分削減されるだけで、大して意味のある削減じゃないかとも思うが、実際Bitcoinの１日のトランザクションで考えると数千バイトの削減効果になるとされていて結構大きい（チリツモ的な）。

LOW Rの適用方法

基本的にrの値は、↑のECDSAのプロトコルからも分かるように、本来は乱数kを秘密鍵とした楕円曲線上の点であり、Bitcoin Coreはこれを乱数生成器の脆弱性を考慮し、トランザクションデータから決定論的にkを導出するようにしている。

R = kGで計算されるので、この結果がLOW Rでない場合、kの選択をやり直す必要があるんだけど、Bitcoinの場合トランザクションデータから決定論的にkを選択してるのにどうやってやり直すの？という疑問が生じるが、これはRFC 6979に答えがある。

RFC 6979は決定論的にnonce kを選択する仕様だが、追加のエントロピーを指定するオプションがあり、このオプションの値を期待するrを得るまでのカウンタとして利用することで、LOW Rを選択できるようにしようというもの。順番にインクリメントするカウンタなので、決定論的にnonceを生成するという特性も維持される。

RFC 6979のオプションというのはおそらく以下の3.6章の内容だと思われる。

 Additional data may be added to the input of HMAC, concatenated
after bits2octets(H(m)):

   K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) || k')

A use case may be a protocol that requires a non-deterministic
signature algorithm on a system that does not have access to a
high-quality random source.  It suffices that the additional data
k' is non-repeating (e.g., a signature counter or a monotonic
clock) to ensure "random-looking" signatures are
indistinguishable, in a cryptographic way, from plain (EC)DSA
signatures.  In [SP800-90A] terminology, k' is the "additional
input" that can be set as a parameter when generating pseudorandom
bits.  This variant can be thought of as a "strengthening" of the
randomness of the source of the additional data k'.

3.2.dのkの生成はもともと↓で

  K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))

3.6の記述では、追加のインプットとしてk'を付加しているのが分かる。

ということで、k'をカウンタとしてインクリメントしながらLOW Rになるまでnonceの選択を繰り返すよう実装すればいい。

まぁデメリットは、LOW Sルールは簡単にsの値を変換できるものの、rの方は↑のように署名の計算コストが高くなるという点かな。

また、今のところ標準トランザクションルールにはなってないようなので、LOW Rでなくともトランザクションはリレーされる。