fivebythree.net

イントロダクション

2023-07-19
Abstract
Nostr の Note に Schnorr 署名するための大まかな流れ

楕円曲線による Schnorr 署名

Nostr では楕円曲線暗号の方法に基づいたデジタル署名を各イベントで行うことによって、改ざんがあった際に検出が可能になっています。

楕円曲線暗号によるデジタル署名は強力な暗号であるにも関わらず、署名のデータを小さくすることができる利点があります。ビットコインのように大量のトランザクションが発生し膨大なデータが取引記録として残るような用途に適しています。

Nostr のデジタル署名は Bitcoin Improvement Proposals の #0340 (BIP0340) に基づいています。すでに多数存在する検証済みのライブラリを利用することができます。

本来であれば検証済みのライブラリを使えばいいわけですが、勉強のために署名のプログラムを自分で作ってみました。

https://github.com/jundow/nostrexamples/tree/main/ex5_schnorr_sign

その過程で調べたこと、勉強したことをメモとして残して置きたいと思いこの記事を書きました。

署名の大まかな流れ

  • 事前準備 秘密鍵を準備し公開鍵を生成する

  • ノートID、署名日時、ノート、秘密鍵から署名用のデータ（ハッシュ生成）

  • 乱数の生成

  • Schnorr 署名

  • 署名の検証

秘密鍵と公開鍵

Nostrの各ユーザーは秘密鍵と公開鍵のペアと結びついています。 秘密鍵は32バイトの整数です。推定が困難である必要があること、他のユーザーと重複を避ける必要があることから、素性の良い乱数生成器から生成されるべきです。

Random Number Generation

公開鍵は秘密鍵から生成されます。 公開鍵は楕円曲線 $x^3 = y^2 +7 \mod p_r$ の生成元$\mathbf{G}$ を 秘密鍵でスカラー倍することにより生成します。

Pubkey Generation Pubkey Generation

  • 楕円曲線 $ y^2 = x^3 + 7 \mod p_r $
  • $p_r$ = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
  • 生成元の楕円曲線上の位置座標
  • $\mathbf{G}.x$ = 0x 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
  • $\mathbf{G}.y$ = 0x 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

楕円曲線上の点の x 座標が Nostr の公開鍵となります。

注意点として、公開鍵として採用した x座標 とペアになりうる y座標の値は、上記の方程式上、ほぼ常に二つ解が存在します（偶数・奇数）。 Nostr x 座標のみ公開鍵にするとその情報は失われているのですが、署名する際にその点を考慮することになります。

ハッシュの生成

署名をするデータが必要です。Nostr では Note そのものに署名するのではなく、イベント情報をシリアライズしたユニコード文字列を sha256 にてハッシュにすることで生成したものを使います。

このハッシュは署名する際と署名検証する際に厳密に同一の内容を再現できる必要があります。その点が配慮された作りになっています。

Serialization

シリアライゼーションの仕様は Nostr Implementation Possibilities #01 (NIP-01)に記載があります。

nonce (署名用乱数) の生成

nonce とは署名の際に一度切り用いる数です (nonce = number at once)。 nonceの生成には乱数とともに、公開鍵、署名するメッセージ本体が用いられます。

Schnorr 署名では、署名の偽造不可能性のために乱数を使います。乱数を使うことは本質的に必要です。2つの署名に全く同じ乱数が使われていた場合、そこから署名に用いられた秘密鍵を推測する方法が存在します。よって素性の良い乱数を使う必要があります。

Nostrで採用されている乱数はビットコインの Schnorr 署名に用いられているものと同じです。仕様は Bitcoin Improvement Proposal #0340 (BIP0340) に記載があります。

注意として、乱数の生成方法は乱数から判別することができないことです。この処理を端折っていい加減な乱数生成をしたとしても署名は通ってしまいます。可能であれば乱数生成が適切に行われていることを確認すべきでしょう。

署名に使う乱数は以下の情報に基づいて生成されます。

  • aux_rand 外部生成された乱数
  • sk 秘密鍵
  • pk 公開鍵
  • msg 署名するメッセージ本体

Aux rnd

署名

署名に必要な情報以下の通りです。

  • sk 秘密鍵 ($d$ as 整数値)
  • $k$ 前述にて計算した nonce
  • msg メッセージ

計算家庭で出現する変数の意味や位置づけです。

  • $n$ 楕円曲線 secp256k1 の位数
  • $\mathbf{P}$ 公開鍵(ただし楕円曲線上の点)
  • $e$ BIP0340 のハッシュ関数によって計算される整数値。

署名は以下のように計算されます。

  • $\mathbf{R} = \pm k \cdot \mathbf{G}$
    • $k\cdot\mathbf{G}が偶数の場合 + ,奇数の場合 - とする$
  • $r[32] = bytes(\mathbf{R}.x)$
  • $e = int (Hash_{BIP0340/challenge}(r || pk || msg)) \mod n $
    • “||” はバイト配列の結合（Concate）を意味する。
    • Hash() は BIP0340 の定義による
  • $s[32] = bytes(\pm k + e(\pm d) \mod n)$
    • $d$ の複合は、$\mathbf{P}.y$ が偶数の場合、$+k$とし、奇数の場合$-k$とする。
  • $sig[64] = r || s$ を署名とする

ハッシュ e の計算方法の詳細は BIP0340 に基づきます。図解すると以下のようになります。

Signature

検証

検証のために必要な情報以下の通りです。

  • pk 公開鍵。32バイトのバイト配列
  • sig 署名 64バイトのバイト配列
    • r = sig[0:31] 署名の先頭32バイト文
    • s = sig[32:63] 署名の後半32バイト分
  • msg[] 署名するメッセージ本体

前節の $sig[64]$ はノートなどのイベントをポストする際に添付されています。 また、リレーサーバーなどイベントを受けるプログラム側では公開鍵 pk[32] が既知であり、またハッシュは $r=sig[0:31]$と受け取ったイベントの内容から再計算が可能です。

署名の検証以下の手順です。署名した際に用いた nonce や秘密鍵がなくても、署名が公開鍵の情報さえあれば、ペアとなる秘密鍵で行われていることが検証可能なことがわかると思います。

  • 公開鍵 pk[32] から 公開鍵の楕円曲線上の点を再計算する
    • $\mathbf{P}_v.x = int(pk[32])$
    • $\mathbf{P}_v.y$ を方程式 $y^2 = (\mathbf{P}_v.x)^2 + 7 \mod n$ から y の偶数解として求める。
  • ハッシュ $e$ を署名の際と同じ方法で計算する。
    • $e = int (Hash_{BIP0340/challenge}(r || pk || msg) \mod n$
  • $\mathbf{R}_v = s \cdot \mathbf{G} - e \cdot \mathbf{P}_v$ を計算する。
  • 署名が正しければ、$\mathbf{R}_v.x$ と $r$ が一致する。
    • $\mathbf{R}_v = s\cdot\mathbf{G} - e\cdot\mathbf{P}_v = (\pm k + e(\pm d))\cdot\mathbf{G} - e\cdot\mathbf{P}_v = k \cdot \mathbf{G}$
    • $d$ に付随する複合は $d\cdot\mathbf{G}$ の偶奇で設定されていたことに注意。$\pm d\cdot\mathbf{G}$ は常に偶である。 $\mathbf{P}_v$は偶になるように解を選んだので、 $e\cdot(\pm d\cdot\mathbf{G}) - e\cdot\mathbf{P}_v = \mathbf{O}$ である。
    • よって、もし Schnorr 署名が正しいなら、 $R = \pm k\cdot\mathbf{G}$ と $\mathbf{R}_v.x=r$ は一致する。一致していれば署名が正しく行われており、改ざんが無いことを確認できる。

以下、署名検証のフローを図式的に書き下したものです。

Vxerification

結論

Nostr のイベントに署名する方法に関して概観しました。上記の記事により、Schnorr 署名のスキームに基づけば、リレーサーバー側での検証段階で、秘密鍵の情報がなくても、公開鍵のみで、署名がペアとなっている秘密鍵が使われていることを検証できることがわかると思います。

上記計算を実行するには、整数（素数を法とする有限体）上での楕円曲線上で加減算・スカラー倍の計算を行う必要がありますが、その計算方法には触れていません。

また、計算を現実的な時間で実行するための工夫を施す必要があるなど、述べるべき要素がまだまだあります。

以降の解説では計算方法にフォーカスしたいと思います。

Reference