BIP 340 — secp256k1 のためのシュノア署名

BIP: 340
  Title: Schnorr Signatures for secp256k1
  Authors: Pieter Wuille <pieter.wuille@gmail.com>
           Jonas Nick <jonasd.nick@gmail.com>
           Tim Ruffing <crypto@timruffing.de>
  Comments-Summary: No comments yet.
  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0340
  Status: Deployed
  Type: Specification
  Assigned: 2020-01-19
  License: BSD-2-Clause
  License-Code: BSD-2-Clause OR MIT OR CC0-1.0
  Discussion: 2018-07-06: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html [bitcoin-dev] Schnorr signatures BIP

はじめに

概要

本文書は楕円曲線 secp256k1 上の 64 バイトシュノア署名の標準を提案する。

著作権

本文書は 2 条項 BSD ライセンスの下で提供される。

動機

ビットコインは伝統的に、トランザクション認証のために secp256k1 曲線 (https://www.secg.org/sec2-v2.pdf)上の ECDSA (https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm) 署名と SHA256 (https://en.wikipedia.org/wiki/SHA-2) ハッシュを用いてきた。これらは標準化済み (https://www.secg.org/sec1-v2.pdf)であるが、同じ曲線上のシュノア署名 (http://publikationen.ub.uni-frankfurt.de/opus4/files/4280/schnorr.pdf)と比較すると複数の欠点がある。

• 証明可能安全性: シュノア署名は証明可能に安全である。より詳細には、シュノア署名は楕円曲線離散対数問題 (ECDLP) の困難性を仮定したランダムオラクルモデル (https://www.di.ens.fr/~pointche/Documents/Papers/2000_joc.pdf)において、また使用するハッシュ関数のプリイメージ耐性および第 2 プリイメージ耐性の変種を仮定した一般群モデル (http://www.neven.org/papers/schnorr.pdf)において、選択メッセージ攻撃下で強い偽造不可能性 (SUF-CMA)非形式的に述べれば、これは秘密鍵を知らない攻撃者が任意のメッセージに対する有効な署名を与えられても、別の有効な署名を作り出すことができないことを意味する。 をもつランダムオラクルモデルにおける詳細な安全性証明 — これは本質的に Pointcheval と Stern による元の安全性証明 (https://www.di.ens.fr/~pointche/Documents/Papers/2000_joc.pdf)をより明示的に再述したもの — が Kiltz、Masny、Pan による論文 (https://eprint.iacr.org/2016/191)にある。これらの安全性証明はいずれも (R,s) ではなく (e,s) を用いるシュノア署名の変種を仮定している (上記「設計」参照)。本提案では R に一意な符号化を用いるため、(R,s) を (e,s) に写す効率的に計算可能な全単射が存在する。これにより (e,s) 変種に対する成功的な SUF-CMA 攻撃者を (R,s) 変種に対する成功的な SUF-CMA 攻撃者に変換可能であり、逆方向の変換も可能である。さらに、これらの証明は鍵プレフィクスを用いないシュノア署名の変種を扱っているが (上記「設計」参照)、これらの証明が鍵プレフィクス付きの変種についても正しいことが確認できる。結果として、前述のすべての安全性証明が本文書で提案するシュノア署名の変種にも適用される。。一方、ECDSA の証明可能安全性に関する最良の既知結果 (https://nbn-resolving.de/urn:nbn:de:hbz:294-60803)はより強い仮定に依存する。
• 非展性: シュノア署名の SUF-CMA 安全性はその非展性を含意する。一方、ECDSA 署名は本質的に展性をもつあるメッセージと鍵に対して (r,s) が有効な ECDSA 署名であるとき、(r,n-s) も同じメッセージと鍵に対して有効である。ECDSA が二つの変種のうち一方のみを許容するように制限されている場合 (ビットコインがネットワークのポリシー規則により行っているように)、通常より強い仮定の下で非展性が証明可能 (https://nbn-resolving.de/urn:nbn:de:hbz:294-60803)である。。秘密鍵にアクセスできない第三者が、与えられた公開鍵とメッセージに対する既存の有効な署名を、同じ鍵とメッセージに対して有効な別の署名に書き換えることができる。この問題は BIP62 (https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki) および BIP146 (https://github.com/bitcoin/bips/blob/master/bip-0146.mediawiki) で議論されている。
• 線形性: シュノア署名は、複数の協調する当事者が各自の公開鍵の和に対して有効な署名を生成できる、単純かつ効率的な手法を提供する。これは効率性とプライバシーを向上させるさまざまな高位構成 — マルチシグやそのほか — の基本要素である (下記「応用」参照)。

これらすべての利点に対して、標準化されていないという点を除けば実質的に欠点はない。本文書はその標準化を目指す。新たな標準を提案するにあたり、シュノア署名に固有でない改良もいくつか加えることができる。

• 署名符号化: 可変長で最大 72 バイトとなる DER (https://en.wikipedia.org/wiki/X.690#DER_encoding) 符号化による署名の代わりに、単純で固定の 64 バイト形式を用いることができる。
• 公開鍵符号化: 今日のビットコインで一般的な楕円曲線点の 圧縮 (https://www.secg.org/sec1-v2.pdf) 33 バイト符号化の代わりに、本提案では公開鍵を 32 バイトとして符号化する。
• バッチ検証: 標準化されている形式の ECDSA 署名は、追加のウィットネスデータを付さない限り、個別検証と比較してバッチで効率的に検証することができない。署名方式の変更はこの点を改善する機会を与える。
• 完全な仕様化: コンセンサスシステムで安全に使用するためには、検証アルゴリズムをバイト単位で完全に仕様化しなければならない。これは、一部の検証者には有効でほかの検証者には無効となる署名を誰も構成できないことを保証する。これは伝統的にはデジタル署名方式の要件ではなかった。ECDSA 署名の DER 構文解析の正確な仕様が欠けていたことが過去にビットコインで問題 (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-July/009697.html)を引き起こし、その対処に BIP66 (https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki) を要した。本文書はこの性質を設計上満たすことを目指す。バッチ検証は検証者がバッチを選択できるため本質的に非決定的であるが、この性質はバッチ検証と個別検証の結果が無視可能な確率でしか異ならないことを意味する — これは意図的にバッチ検証と非バッチ検証の結果を相違させようとする攻撃者に対してさえ成り立つ。

ビットコインが ECDSA に用いるのと同じ曲線およびハッシュ関数を再利用することにより、秘密鍵および公開鍵の選択に関する既存の機構を維持でき、楕円曲線およびハッシュ関数の安全性に関する新たな仮定を導入することを避けられる。

説明

まず設計選択を順に追いながら、署名方式の代数的な定式化を組み立てる。その後、正確な符号化と演算を仕様化する。

設計

シュノア署名の変種 メッセージ m と公開鍵 P に対する楕円曲線シュノア署名は一般に、点 R、署名者が選ぶ整数 e と s、および基点 G を含み、e = hash(R || m) および s⋅G = R + e⋅P を満たす。署名者が e と R のどちらを公開するかにより二つの定式化が存在する。

1. 署名は e = hash(s⋅G - e⋅P || m) を満たす対 (e, s) である。この変種は署名内の点 R の符号化が引き起こす細かな複雑さを避ける (本節後段の「R と公開鍵点 P の符号化」および「暗黙の Y 座標」を参照)。さらに、R ではなく e を公開することは、より短い署名の余地を生む。R の符号化が本質的に約 32 バイトを必要とするのに対し、ハッシュ e は 32 バイトより短くなるよう調整可能で、わずか 16 バイトの短いハッシュで目標安全性水準 128 ビットの SUF-CMA 安全性を提供できる (http://www.neven.org/papers/schnorr.pdf)。しかしこの最適化の大きな欠点は、短いハッシュ関数で衝突を見つけるのが容易な点にある。互いに信頼しない署名者の集団が共同して単一の結合署名を生成する状況 (下記「応用」参照) では、これにより安全な署名プロトコルの実装が複雑化する。これらの状況は、単一の正直な署名者を仮定する SUF-CMA モデルでは捉えられない。悪意ある共同署名者の有力な攻撃戦略は、正直な共同署名者が署名するつもりのないメッセージに対する有効な署名を得るために、ハッシュ関数で衝突を見つけることである。
2. 署名は s⋅G = R + hash(R || m)⋅P を満たす対 (R, s) である。これは、ハッシュの内部に楕円曲線演算が存在しないため、バッチ検証をサポートする。バッチ検証は顕著な高速化をもたらす。バッチ検証による高速化は、暗号ライブラリ libsecp256k1 (https://github.com/jonasnick/secp256k1/blob/schnorrsig-batch-verify/doc/speedup-batch.md) で実証可能である。

短いハッシュに伴う脆弱性を避けたいため、e 変種は顕著な利点を提供しない。バッチ検証をサポートする R 選択肢を採用する。

鍵プレフィクス 上述の検証規則をそのまま用いると、シュノア署名は「関連鍵攻撃」に対して脆弱になる。これは第三者が、署名鍵に対する任意の加法的ツイーク a に対して、公開鍵 P に対する署名 (R, s) を公開鍵 P + a⋅G と同じメッセージ m に対する署名 (R, s + a⋅hash(R || m)) に変換できる攻撃である。これは [[bip-0032.mediawiki#public-parent-key—public-child-key|BIP32 の非ハードン化導出]] や、Taproot のような既存鍵への加法的ツイークに依存するその他の方式で鍵が生成される場合に、署名を安全でなくする。

これらの攻撃を防ぐため、鍵プレフィクス(短いハッシュではなく、あるいは全くコミットしないのではなく) 公開鍵にコミットすることの制約は、公開鍵復元や短い公開鍵ハッシュに対する署名検証の能力が失われる点である。これらの構成は一般にバッチ検証と両立しない。 付きのシュノア署名を採用する。これはチャレンジハッシュの入力でメッセージの前に公開鍵をプレフィクスとして付けることを意味する。これにより方程式は s⋅G = R + hash(R || P || m)⋅P に変わる。鍵プレフィクスが加法的ツイークに関連する関連鍵攻撃を防ぐことが示せる (https://eprint.iacr.org/2015/1135.pdf)。一般に鍵プレフィクスはマルチユーザー状況での頑健性を高める。たとえば、マルチパーティ署名プロトコル (MuSig、MuSig2、FROST など) の安全性を証明するための要件と思われる (下記「応用」参照)。

ビットコインで現在用いられているトランザクション署名については、署名済みトランザクションが既に公開鍵に間接的にコミットしているため (すなわち m は pk へのコミットメントを含む)、鍵プレフィクスは厳密には必須ではないことを付記する。しかしこの間接的コミットメントに依存すべきではない。なぜなら、SIGHASH_NOINPUT (BIP118 (https://github.com/bitcoin/bips/blob/master/bip-0118.mediawiki)) のような提案によって変わる可能性があり、また署名方式をトランザクション署名以外の用途、たとえば通常のメッセージ署名 (https://bitcoin.org/en/developer-reference#signmessage)に用いるには不適切となるからである。

R と公開鍵点 P の符号化 楕円曲線点の符号化にはいくつかの選択肢がある。

1. P と R の X 座標と Y 座標の完全な符号化。これは 64 バイトの公開鍵と 96 バイトの署名をもたらす。
2. 完全な X 座標と、二つの可能な Y 座標のうち一方を特定するための Y 座標 1 ビットの符号化。これは 33 バイトの公開鍵と 65 バイトの署名をもたらす。
3. X 座標のみの符号化。これは 32 バイトの公開鍵と 64 バイトの署名をもたらす。

最初の選択肢は検証で若干 (約 10%) 効率的であるが、コンパクトさを優先するため選択肢 3 を採用する。

暗黙の Y 座標 効率的な検証およびバッチ検証をサポートするには、P および R の Y 座標が曖昧であってはならない (有効な X 座標にはそれぞれ二つの可能な Y 座標がある)。対称性破りの選択肢としていくつかの選択がある。

1. 下半分にある Y 座標を暗黙的に選ぶ。
2. 偶数の Y 座標を暗黙的に選ぶp は奇数であるため、p を法とする否定は偶数を奇数に、その逆にも写す。これは、有効な X 座標に対して、対応する Y 座標のうち一方が偶数、他方が奇数となることを意味する。。
3. 平方剰余 (すなわち p を法とする平方根をもつ) である Y 座標を暗黙的に選ぶ。

第二の選択肢は既存の鍵生成システムとの最大の互換性を提供する。標準の 33 バイト圧縮公開鍵形式は、Y 座標の奇偶を示す 1 バイトと完全な X 座標から構成されるためである。不必要な非互換性を避けるため、P についてはこの選択肢を採用する。したがって本提案の X のみの公開鍵は、X のみの鍵の前にバイト 0x02 を付した圧縮公開鍵と等価になる。一貫性のため R についても同様とする本草案の以前の版では第三の選択肢を採用していた。これは一般に署名効率と検証効率のトレードオフになるとの信念に基づくものであった。楕円曲線暗号実装で一般的な最適化であるヤコビ座標を用いる場合、アフィン座標 (これは法逆元計算を要する) に変換することなく、ルジャンドル記号を計算することで Y 座標が平方剰余か否かを判定できる。実用上は法逆元とルジャンドル記号の性能 (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-August/018081.html)が同程度であるため、このトレードオフは見合わない。。

有効な公開鍵の集合の大きさを半分にするにもかかわらず、暗黙の Y 座標は安全性の低下をもたらさない。非形式的に述べれば、X のみの公開鍵の離散対数を計算する高速アルゴリズムが存在するなら、それは完全な公開鍵の離散対数の計算にも用いることができる。X 座標に適用し、その後必要なら結果を反転すればよい。これは X のみの公開鍵を破る計算量が、完全な公開鍵を破る計算量より高々小さな定数項だけ高速であることを示す。これは暗黙の Y 座標をもつシュノア署名への攻撃を明示の Y 座標をもつシュノア署名への攻撃に帰着させる単純な還元によって形式化できる。還元はチャレンジ公開鍵が明示の奇数 Y 座標をもつ場合に常に、公開鍵を再符号化し、ランダムオラクルとしてモデル化されるハッシュ関数の出力を反転することで機能する。証明の概略はこちら (https://medium.com/blockstream/reducing-bitcoin-transaction-sizes-with-x-only-pubkeys-f86476af05d7)にある。

タグ付きハッシュ 暗号学的ハッシュ関数は、下記の仕様内およびビットコイン一般において複数の用途に用いられる。ある文脈で用いるハッシュが別の文脈で再解釈されないようにするため、ハッシュ関数は文脈依存のタグ名でツイークすることができ、文脈横断の衝突は実行不能と仮定できるようになる。そうした衝突を完全に排除することはむろん不可能だが、一意な名前のタグを用いる方式同士の間に限られる。タグを用いないほかの方式同士の衝突に比べて、タグ付き方式の方が少なくとも衝突は起こりにくい。

たとえばタグ付きハッシュを用いなければ、BIP340 署名は、唯一の違いがハッシュ関数の引数順序のみであるような別の署名方式に対しても有効となりうる。さらに悪いことに、BIP340 のナンス導出関数が複製されたり独立に作成されたりした場合、ナンスが別方式で偶然再利用され、秘密鍵が漏洩しうる。

本提案ではハッシュ対象データの前に SHA256(tag) || SHA256(tag) をプレフィクスとして付けることでタグを含めることを提案する。これは 64 バイトの文脈固有定数であり、SHA256 のブロックサイズも 64 バイトであるため、最適化実装が可能である (SHA256 そのものと同じだが、初期状態を変更したもの)。タグ名自体の SHA256 を用いる方法は、この最適化を採用しない実装にとって十分に単純かつ効率的である。タグは一般に任意のバイト列でよいが、UTF-8 符号化のテキスト記述を推奨する。

最終方式 結果として、本提案の最終方式は、曲線上の点 P の X 座標であって Y 座標が偶数となる公開鍵 pk と、Y 座標が偶数となる点 R の X 座標 r を用いた署名 (r,s) を用いる。署名は s⋅G = R + tagged_hash(r || pk || m)⋅P を満たす。

仕様

secp256k1 (https://www.secg.org/sec2-v2.pdf) について定義された定数を用い、以下の表記規約を採用する。本仕様をほかの楕円曲線に適応させることは単純ではなく、安全でない方式に至る可能性があることを付記するとりわけ、その位数がナンス導出関数の値域の大きさに近くない曲線で本仕様を用いることは安全でない。。

• 小文字変数は整数またはバイト配列を表す。
  • 定数 p は体のサイズ 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F を指す。
  • 定数 n は曲線の位数 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 を指す。
• 大文字変数は、p を法とする整数上で方程式 y² = x³ + 7 を満たす曲線上の点を指す。
  • is_infinite(P) は P が無限遠点であるか否かを返す。
  • x(P) と y(P) は範囲 0..p-1 の整数で、(無限遠でないとして) 点 P の X 座標と Y 座標を指す。
  • 定数 G は基点を指し、x(G) = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 および y(G) = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 で定義される。
  • 点の加算は通常の楕円曲線群演算 (https://en.wikipedia.org/wiki/Elliptic_curve#The_group_law)を指す。
  • 整数と点の乗算 (⋅) (https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication) は群演算の繰り返し適用を指す。
• 関数と演算:
  • || はバイト配列の連結を指す。
  • 関数 x[i:j]、ここで x はバイト配列、i, j ≥ 0 は、x の i 番目のバイト (包含) から j 番目のバイト (排他) を写した (j - i) バイトの配列を返す。
  • 関数 bytes(x)、ここで x は整数は、x の上位バイトを先頭とする 32 バイト符号化を返す。
  • 関数 bytes(P)、ここで P は点は、bytes(x(P)) を返す。
  • 関数 int(x)、ここで x は 32 バイト配列は、x を上位バイトを先頭とする符号化として解釈した 256 ビット符号なし整数を返す。
  • 関数 has_even_y(P)、ここで P は not is_infinite(P) を満たす点は、y(P) mod 2 = 0 を返す。
  • 関数 lift_x(x)、ここで x は 256 ビット符号なし整数は、x(P) = x 範囲 0..p-1 の候補 X 座標 x が与えられたとき、有効な Y 座標はちょうど二つ存在するか、ちょうどゼロ個存在する。有効な Y 座標が存在しない場合、x は有効な X 座標ではない。すなわち x(P) = x となる点 P は存在しない。与えられた候補 x に対する有効な Y 座標は c = x³ + 7 mod p の平方根であり、存在するなら y = ±c^(p+1)/4 mod p として計算できる (平方剰余 (https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus)を参照)。存在の確認は二乗して c と比較することによって行える。 および has_even_y(P) を満たす点 P を返す。x が p-1 より大きい、またはそのような点が存在しない場合は失敗する。関数 lift_x(x) は以下の疑似コードと等価である。
    • x ≥ p なら失敗。
    • c = x³ + 7 mod p とする。
    • y = c^(p+1)/4 mod p とする。
    • c ≠ y² mod p なら失敗。
    • x(P) = x かつ、y mod 2 = 0 なら y(P) = y、そうでなければ y(P) = p-y となる一意な点 P を返す。
  • 関数 hash_name(x)、ここで x はバイト配列は、32 バイトハッシュ SHA256(SHA256(tag) || SHA256(tag) || x) を返す。ここで tag は name の UTF-8 符号化である。

公開鍵生成

入力:

• 秘密鍵 sk: 一様乱数で新たに生成された 32 バイト配列

アルゴリズム PubKey(sk) は以下のように定義される。

• d’ = int(sk) とする。
• d’ = 0 または d’ ≥ n なら失敗。
• bytes(d’⋅G) を返す。

既存システムが用いる公開鍵形式 (典型的には楕円曲線点を公開鍵として用いるか、その 33 バイトまたは 65 バイト符号化を用いる) とは大きく異なる形式 (32 バイト) を本提案が用いている点に注意する。副作用として PubKey(sk) = PubKey(bytes(n - int(sk)) となり、すべての公開鍵は対応する秘密鍵を二つもつ。

公開鍵変換

鍵をランダムに生成する代わりに、ECDSA 用の既存の鍵生成アルゴリズムを互換的に転用することも可能であり安全である。そうしたアルゴリズムで構成された秘密鍵はそのまま sk として使用できる。そうしたアルゴリズムで構成された公開鍵 (33 バイト圧縮符号化を用いると仮定する) は先頭バイトを取り除くことにより変換する必要がある。具体的には、BIP32 (https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki) およびそれを基盤とする方式は引き続き使用可能である。

既定の署名

入力:

• 秘密鍵 sk: 32 バイト配列
• メッセージ m: バイト配列
• 補助乱数 a: 32 バイト配列

アルゴリズム Sign(sk, m) は以下のように定義される。

• d’ = int(sk) とする。
• d’ = 0 または d’ ≥ n なら失敗。
• P = d’⋅G とする。
• has_even_y(P) なら d = d’ とし、そうでなければ d = n - d’ とする。
• t を bytes(d) と hash_BIP0340/aux(a) のバイト単位 xor とする補助乱数は、乱数が秘密鍵自体と相関しうる状況に対する予防として、(一意のタグ付きで) ハッシュされる。実際の秘密鍵に晒される演算回数を減らすため、(ハッシュで結合するのではなく) 秘密鍵と xor する。。
• rand = hash_{BIP0340/nonce}(t || bytes(P) || m) とする公開鍵をナンスハッシュの入力に含める (https://moderncrypto.org/mail-archive/curves/2020/001012.html)ことは、公開鍵 P の計算が誤って、あるいは悪意をもって行われた場合 (たとえば性能上の理由で呼び出し側に委ねられた場合) に秘密鍵の漏洩を防ぐことで、署名アルゴリズムの頑健性を高める。。
• k’ = int(rand) mod n とする一般に、256 ビット一様乱数整数を曲線の位数で剰余すると許容できない偏った結果を生むことに注意する。しかし secp256k1 曲線については、位数が 2²⁵⁶ に十分近いため (1 - n / 2²⁵⁶ は約 1.27 * 2^-128)、この偏りは観測できない。。
• k’ = 0 なら失敗。
• R = k’⋅G とする。
• has_even_y(R) なら k = k’ とし、そうでなければ k = n - k’ とする。
• e = int(hash_{BIP0340/challenge}(bytes(R) || bytes(P) || m)) mod n とする。
• sig = bytes(R) || bytes((k + ed) mod n) とする。
• Verify(bytes(P), m, sig) (下記参照) が失敗を返す場合は中止する署名者から署名を送出する前に署名を検証することは、乱数または攻撃者誘発の計算誤りを防ぐ。これにより、秘密鍵に関する情報を漏洩しうる無効な署名の公開を防ぐ。推奨されるが、計算コストが過大な場合は省略可能である。。
• 署名 sig を返す。

補助乱数は署名時に生成された新鮮な乱数に設定すべきであり、その結果得られるものを 合成ナンス と呼ぶ。32 バイトの乱数を用いるのが最適である。乱数取得のコストが高い場合は、16 バイトの乱数に 16 バイトのナルバイトを詰めて 32 バイト配列とすることもできる。署名時に乱数がまったく入手できない場合は、実用上繰り返さない程度に十分広い単純なカウンター (たとえば 64 ビット以上) にナルバイトを詰めて 32 バイト配列としたもの、あるいは 32 個のナルバイトからなる定数配列を用いることさえできる。任意の非反復値を用いることでフォールトインジェクション攻撃 (https://moderncrypto.org/mail-archive/curves/2017/000925.html)に対する保護が高まる。予測不能な乱数を用いることはさらにほかのサイドチャネル攻撃に対する保護を高めるため、入手可能な場合は常に推奨される。これは結果として得られるナンスが決定論的でないことを意味するが、乱数は安全性に対して補助的なものに過ぎないことに注意する。(サイドチャネル攻撃を除く) 通常の安全性は署名時 RNG の品質に依存しない。

代替の署名

等しく有効な署名を生成するために、さまざまな代替署名アルゴリズムを用いることができることを付記する。32 バイトの rand 値はほかの方法で生成することも可能で、別の (それでも有効な) 署名を生成しうる (言い換えれば、これは 一意な 署名方式ではない)。rand 値を生成するどの方法を用いる場合でも、その値は攻撃者にとって部分的にすら予測不能な、新鮮で一様乱数の 32 バイト文字列でなければならない。 乱数を含まないナンスについては、同じ入力を別の文脈で提示してはならないことを意味する。これは、異なる署名方式間で同じ秘密鍵を再利用しないことで最も確実に達成できる。たとえば、rand 値が RFC6979 に従って計算され、同じ秘密鍵が RFC6979 を用いる決定論的 ECDSA でも使われている場合、ナンス再利用を通じて署名が秘密鍵を漏洩しうる。

ナンス漏出防止 第二の機器を用いてナンス生成アルゴリズムを強化することも可能である。この場合、第二の機器が乱数を提供し、実際の署名者はそれを証明可能な形で自らのナンスに取り込む。これは署名者の機器が侵害され、ナンス選択を通じて意図的に秘密鍵を漏洩させようとする一定の攻撃を防ぐ。

マルチシグ 本署名方式は、MuSig2 (https://eprint.iacr.org/2020/1261.pdf) のような各種のマルチシグおよび閾値方式と互換である。これらの方式では単一の公開鍵に対して複数の秘密鍵の保持者が署名に参加する必要がある (下記「応用」参照)。 マルチシグ署名方式は一般に、上記の既定の署名アルゴリズム由来の rand 生成 (あるいはほかの決定論的方法) では安全でないことに留意することが重要である。

事前計算済み公開鍵データ 多くの用途では、秘密鍵に対応する公開鍵の 33 バイト圧縮符号化が既に既知の場合があり、has_even_y(P) および bytes(P) の評価が容易になる。このため、署名者にこれを直接提供させる方が秘密鍵から公開鍵を再計算するより効率的でありうる。ただしこの最適化を用い、加えて効率向上のため署名アルゴリズム末尾の署名検証を省略する場合、署名者は公開鍵が正しく計算され、信頼できない情報源から取得されていないことを確かめなければならない。

検証

入力:

• 公開鍵 pk: 32 バイト配列
• メッセージ m: バイト配列
• 署名 sig: 64 バイト配列

アルゴリズム Verify(pk, m, sig) は以下のように定義される。

• P = lift_x(int(pk)) とする。それが失敗するなら失敗。
• r = int(sig[0:32]) とする。r ≥ p なら失敗。
• s = int(sig[32:64]) とする。s ≥ n なら失敗。
• e = int(hash_{BIP0340/challenge}(bytes(r) || bytes(P) || m)) mod n とする。
• R = s⋅G - e⋅P とする。
• is_infinite(R) なら失敗。
• not has_even_y(R) なら失敗。
• x(R) ≠ r なら失敗。
• ここに到達するまでに失敗が発生していなければ成功を返す。

任意の有効な秘密鍵 sk とメッセージ m に対して、Verify(PubKey(sk),m,Sign(sk,m)) は成功する。

検証の正しさは、lift_x が常に Y 座標が偶数の点を返すという事実に依拠する点に注意する。点をそのまま公開鍵として扱い、点 P を直接入力に取る仮想的な検証アルゴリズムは、Y が奇数の点が用いられるたびに失敗する。さらに進める前に奇数 Y 座標の点を反転することで補正することは可能であるが、その結果として、すべての (メッセージ、署名) 対が二つの公開鍵に対して有効となる方式に至る (これは ECDSA にも存在する展性の一種であり、本提案ではこれを引き継ぎたくない)。これらの問題は、X 座標のみを公開鍵として扱うことで回避する。

バッチ検証

入力:

• 署名の個数 u
• 公開鍵 pk_1..u: u 個の 32 バイト配列
• メッセージ m_1..u: u 個のバイト配列
• 署名 sig_1..u: u 個の 64 バイト配列

アルゴリズム BatchVerify(pk_1..u, m_1..u, sig_1..u) は以下のように定義される。

• 範囲 1…n-1 の u-1 個の乱数整数 a_2…u を生成する。これらは、アルゴリズムのすべての入力の暗号学的ハッシュ、すなわち seed = seed_hash(pk₁..pk_u || m₁..m_u || sig₁..sig_u ) を種とする CSPRNG (https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator) を用いて決定論的に生成される。安全な選択は、seed_hash を SHA256 で実装し、鍵 seed を伴う ChaCha20 (https://tools.ietf.org/html/rfc8439) を CSPRNG として用いて 256 ビット整数を生成し、範囲 1…n-1 に含まれない整数を読み飛ばすことである。
• i = 1 .. u について:
  • P_i = lift_x(int(pk_i)) とする。失敗するなら失敗。
  • r_i = int(sig_i[0:32]) とする。r_i ≥ p なら失敗。
  • s_i = int(sig_i[32:64]) とする。s_i ≥ n なら失敗。
  • e_i = int(hash_{BIP0340/challenge}(bytes(r_i) || bytes(P_i) || m_i)) mod n とする。
  • R_i = lift_x(r_i) とする。lift_x(r_i) が失敗するなら失敗。
• (s₁ + a₂s₂ + … + a_us_u)⋅G ≠ R₁ + a₂⋅R₂ + … + a_u⋅R_u + e₁⋅P₁ + (a₂e₂)⋅P₂ + … + (a_ue_u)⋅P_u なら失敗。
• ここに到達するまでに失敗が発生していなければ成功を返す。

個々の署名がすべて有効である場合 (すなわち Verify がそれらに対して成功を返す場合)、BatchVerify は常に成功を返す。少なくとも一つの署名が無効である場合、BatchVerify は高々無視可能な確率でしか成功を返さない。

利用上の考慮事項

任意サイズのメッセージ

本 BIP で仕様化される署名方式は、入力メッセージとして任意サイズのバイト列を受け付ける。理論上は、SHA256 が 2^61-1 バイトまでのバイト列しか受け付けないため、メッセージサイズには制約がある。 実装が自身の環境やアプリケーション文脈において過大なメッセージ — たとえば事前定義のバッファを超えるメッセージや、その他の形で資源枯渇を引き起こすメッセージ — を拒否しうることは了解されている。

本 BIP の初期版ではメッセージが正確に 32 バイトであることを要求していた。 この制約は呼び出し側に負担を強いるもので、 呼び出し側は典型的には、署名や検証に渡せる 32 バイトのダイジェストを作成するために、 実際の入力メッセージを SHA256 (またはほかの衝突耐性のある暗号学的ハッシュ関数) に通して事前ハッシュを行う必要があった (たとえば BIP341 (https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki) で行われている通りである)。

事前ハッシュが必ずしも望ましいとは限らないため、 たとえば実際のメッセージが 32 バイト未満の場合、事前ハッシュを省略するもう一つの理由は、事前ハッシュに用いるハッシュ関数に対する一定の暗号解析的進歩への保護である。事前ハッシュを用いる場合、事前ハッシュ関数に衝突を見いだせる攻撃者は、選択メッセージ攻撃下で必ず署名を偽造できる。事前ハッシュを用いない場合、SHA256 (これは署名方式の内部で使われる) に衝突を見いだせる攻撃者でも署名を偽造できない可能性がある。ただしこの一見した利点は、ビットコインの文脈ではほとんど無関係である。ビットコインは既にトランザクションハッシュなどほかの場所で SHA256 の衝突耐性に依存しているからである。 32 バイトメッセージへの制限は撤廃された。 大きなメッセージを扱うアプリケーションでは、性能上の理由から事前ハッシュを推奨する。 大きなメッセージが事前ハッシュされない場合、 署名方式のアルゴリズムは内部でより多くのハッシュ計算を行う。 特に署名アルゴリズムはメッセージを 2 回逐次的にハッシュする必要があり、 これは署名中に全メッセージを必ずメモリーに保持しなければならないことを意味し、 大きなメッセージは実行時のペナルティを伴う。呼び出し側アプリケーションが行う事前ハッシュの速度が、署名アルゴリズム内部の SHA256 の速度と一致すると仮定すれば、典型的には 56 バイト以上のメッセージは事前ハッシュにより性能上の利益を享受する。

ドメイン分離

鍵ペアは単一の目的にのみ用いるのが優れた暗号学的慣行である。 それでもなお、同じ鍵ペアを複数の文脈で用いることが望ましい場合がある。 すなわち、同じアプリケーション内で異なる種類のメッセージに署名する場合、 あるいはまったく異なるアプリケーション間でメッセージに署名する場合さえある (たとえばある秘密鍵が、ビットコイントランザクションへの署名と平文メッセージへの署名の両方に使われうる)。

その結果、アプリケーションはある文脈用に署名されたアプリケーションメッセージが別の文脈で有効と判定されないようにしなければならない (たとえば、署名された平文メッセージが署名済みビットコイントランザクションと誤解釈されてはならない。意図しない資金損失を引き起こしうるからである)。 これは「ドメイン分離」と呼ばれ、典型的にはメッセージ空間を分割することで実現される。 鍵ペアが単一の文脈内のみで用いられる想定であっても、 ドメイン分離は後から文脈を追加しやすくするため良い考えである。

ベストプラクティスとして、署名方式に渡す前にアプリケーションメッセージを前処理するには、以下のいずれか一つの方法を正確に用いることを推奨する。

• 文脈を一意に識別する name (たとえば “foo-app/signed-bar”) を用いて、hash_name でアプリケーションメッセージを事前ハッシュする、
• あるいは文脈を一意に識別する 33 バイトの文字列 (たとえば “foo-app/signed-bar” の UTF-8 符号化を 33 バイトにナルバイトで詰めたもの) を実際のメッセージの前にプレフィクスとして付ける。

二つの前処理方法は異なるメッセージサイズ (32 バイト対 33 バイト以上) を生むため、両者間の衝突の危険はない。

応用

単純な署名を越えるいくつかの興味深い応用がある。 近年の学術論文はそれらが ECDSA でも可能であると主張するが、シュノア署名検証へのコンセンサスでの対応はそれらの構成を大きく単純化する。

マルチシグと閾値署名

MuSig2 (https://eprint.iacr.org/2020/1261.pdf) (BIP327 (https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki)) のような対話的方式により、参加者は各自の公開鍵を単一の公開鍵に集約し、共同で署名できる。これにより n-of-n のマルチシグが可能となり、検証者から見れば通常の署名と何ら変わらないため、CHECKMULTISIG やその他の手段に対してプライバシーと効率の向上をもたらす。

さらに、シュノア署名は分散鍵生成 (https://en.wikipedia.org/wiki/Distributed_key_generation)と互換である。これは対話的閾値署名方式を可能にする — たとえば Stinson と Strobl (2001) (http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps) による方式、Gennaro、Jarecki、Krawczyk、Rabin (2007) (https://link.springer.com/content/pdf/10.1007/s00145-006-0347-3.pdf) による方式、あるいは FROST (https://eprint.iacr.org/2020/852.pdf) 方式とその変種 (たとえば FROST3 (https://eprint.iacr.org/2023/899.pdf)) である。これらのプロトコルは k-of-n 閾値署名の実現を可能にし、n 人の署名者集合のうち大きさ k の任意の部分集合が署名できるが、大きさ k 未満の部分集合は有効なシュノア署名を生成できないことを保証する。

アダプター署名

アダプター署名 (https://download.wpsoftware.net/bitcoin/wizardry/mw-slides/2018-05-18-l2/slides.pdf)は、署名者が自身の公開ナンス R を既知の点 T = t⋅G でオフセットしつつ、署名の s 値はオフセットしないことで生成できる。 同じメッセージかつ同じナンスに対する正しい署名 (またはマルチシグ中の個々の署名者の寄与は部分署名と呼ばれる) は、t でオフセットされたアダプター署名と等しくなる。すなわち、t を知ることは正しい署名を知ることと等価である。 これはアトミックスワップを可能にするのに用いることができ、さらには汎用ペイメントチャンネル (https://eprint.iacr.org/2018/472) — 互いに独立なトランザクションのアトミック性をビットコインスクリプト対応ではなく署名そのものによって保証するもの — を可能にすることさえできる。結果として得られるトランザクションは、ロックタイム返金ロジックの含有を除けば、検証者には通常の単一署名者トランザクションと何ら変わらないように見える。

アダプター署名は、スクリプト意味論を定数サイズの署名に符号化する効率性とプライバシーの利点に加えて、伝統的なハッシュベースのペイメントチャンネルに対する追加の利点をもつ。具体的には、秘密値 t はホップ間で再ブラインド化できるため、参加者でさえどのトランザクションがチェーンの一部かを識別できないまま、長いトランザクション連鎖をアトミックにできる。また、秘密値が鍵生成時ではなく署名時に選ばれるため、既存の出力をブロックチェーンに頼ることなく別の応用に再利用でき、それを複数回行うことさえできる。

ブラインド署名

ブラインド署名プロトコルとは、署名者が署名対象メッセージや署名に関する情報を一切学習せずに、他者の依頼でメッセージに署名することを可能にする対話型プロトコルである。シュノア署名は非常に単純なブラインド署名方式 (http://publikationen.ub.uni-frankfurt.de/files/4292/schnorr.blind_sigs_attack.2001.pdf)を許容するが、これは Wagner の攻撃 (https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf)に対して脆弱であるため安全ではない。既知の緩和策は、署名者が一定確率で署名セッションを中止することを許容するもの — これは非標準の暗号学的仮定の下で安全と証明可能 (https://eprint.iacr.org/2019/877)である — や、ゼロ知識証明を用いる (https://eprint.iacr.org/2022/1676.pdf)ものである。

ブラインドシュノア署名はたとえば部分ブラインドアトミックスワップ (https://github.com/ElementsProject/scriptless-scripts/blob/master/md/partially-blind-swap.md)で用いることができる。これは信頼されないエスクロー代理人を介して、取引当事者を公開ブロックチェーントランザクショングラフ上で結びつけることなくコインを移転可能にする構成である。

テストベクトルと参照コード

開発とテストの目的で、CSV 形式の [[bip-0340/test-vectors.csv|テストベクトル集]]、 署名と検証アルゴリズムの素朴で著しく非効率的かつ非定数時間の [[bip-0340/reference.py|純粋な Python 3.7 参照実装]]、 および [[bip-0340/test-vectors.py|テストベクトル生成に用いたスクリプト]] を提供する。 これらは BSD-2-Clause ライセンス、MIT ライセンス、または CC0 1.0 のいずれか — 利用者の選択 — のもとで提供される。 参照実装はデモ目的のみであり、本番環境での使用は想定していない。

変更履歴

実装者が本 BIP の更新を理解するための助けとして、実質的な変更の一覧を維持する。

• 2022-08: 参照コードの lift_x の関数シグネチャを修正
• 2023-04: 任意サイズのメッセージを許可
• 2024-05: 「応用」節をより最近の参照文献で更新
• 2025-04: テストベクトルとコードのライセンス変更

脚注

謝辞

本文書はシュノアベースの署名を巡る長年にわたる多くの議論の成果であり、ジョンソン・ラウ、グレゴリー・マクスウェル、Andrew Poelstra、Rusty Russell、アンソニー・タウンズからの意見を得た。著者らはさらに、体系的レビュー (https://github.com/ajtowns/taproot-review)の参加者を含め、貴重なフィードバックとレビューを提供してくださったすべての方々に謝意を表する。