visvirial/bip-schnorr_ja.mediawiki

## bip-schnorr_ja.mediawiki

      
    Raw
  

              bip-schnorr_ja.mediawiki
            
          
Table of Contents
導入アブストラクト
著作権
動機
説明設計
仕様検証
バッチ検証
署名作成
最適化
応用マルチシグネチャおよびスレッショルド署名
アダプタ署名
ブラインド署名
テストベクトル
付録 A: リファレンスコード
脚注
謝辞
導入


アブストラクト


このドキュメントでは、楕円曲線 secp256k1 上での 64 バイト Schnorr (シュノア) 署名の標準を提案します。


著作権


このドキュメントは 2 条項 BSD ライセンスで提供されます。


動機


Bitcoin では伝統的に secp256k1 曲線上の ECDSA 署名をトランザクションの認証に利用していました。これらは標準化されていますが、同一曲線上の Schnorr 署名 に比べていくつかの欠点があります:


セキュリティの証明: Schnorr 署名のセキュリティは、ランダムオラクルモデルにおいて楕円曲線の離散対数問題 (ECDLP) が難しいことを仮定することで、簡単に証明可能です。このような証明は ECDSA には存在しません。
非展性: ECDSA 署名は本質的に展性があります; 秘密鍵を知らない第三者が、与えられた公開鍵とメッセージに対する既存の有効な署名を、同一の鍵およびメッセージに対して有効な新たな署名に変換することが出来ます。この問題は BIP62 で議論されています。一方で、Scnorr 署名は証明可能な非展性をもちます。^[1]
線形性: Schnorr 署名は、複数人が協力することで彼らの公開鍵の総和に対して正しい署名を生成することができるという、注目すべき性質を持ちます。この性質は、マルチシグネチャーなどの（下記の応用をご覧ください）効率性やプライバシーを向上させるいくつもの高レベルな構造物の構成要素となっています。
こうした優位性にもかかわらず、標準化されていないという点を除いては事実上全く不利な点はありません。
この文書では標準化されていないという点を変えることを目指します。
これから新しい標準を提案しますが、この中には Schnorr 署名に特有ではない、いくつかの改善点が含まれています:


署名エンコーディング: 署名に対して DER エンコーディング（可変サイズで、最大 72 バイト）を用いるのではなく、単純で固定長の 64 バイトフォーマットを利用します。
バッチ検証: 標準化されている特定の形式の ECDSA 署名は、追加の証拠データが追加されていない限り、一括で検証しても個別に検証する場合に比べて効率化はできません。署名スキームを変更することで、これを避けることができる可能性があります。
このグラフは、n 個の署名を個別に検証する場合と、n 個の署名を一括で検証した場合にかかった時間の間の比を表しています。この比は署名の個数に対して対数的に上がっていきます。別の言い方をすると、n 個の署名を検証する合計時間は O(n / log n) で成長することを表しています。

Bitcoin が ECDSA で利用していたのと同じ曲線を再利用することで、秘密鍵および公開鍵は Schnorr 署名においても同一のままとなり、また楕円曲線群のセキュリティに関して新しい仮定を導入せずに済むようになります。


説明


まずはじめに設計の選択を見ていくことで、署名スキームの代数的な定式化を作り上げます。
その後で、正確なエンコーディングや演算を指定します。


設計


Schnorr 署名の亜種 メッセージ m および公開鍵 P に対する楕円曲線 Schnorr 署名は、一般的に点 R および整数 e と s を含み、これらは e = H(R || m) および sG = R + eP を満たします。e を含めるか R を含めるかによって、二つの定式化が存在します:


署名は e = H(sG - eP || m) を満たす (e, s) です。これは署名に含まれる点 R をどのようにエンコードするかの困難を排除します。
署名は sG = R + H(R || m)P を満たす (R, s) です。ハッシュの中に楕円曲線演算がないため、これはバッチ検証をサポートします。
バッチ検証をサポートするために、我々は R のオプションを選択します。

鍵プレフィクシング 上記の検証ルールを直接利用すると、第三者が任意の整数 a に対して、鍵 P に対する署名 (R, s) を、鍵 P + aG および同一のメッセージに対する署名 (R, s + aH(R || m)) に変換できてしまいます。現在のところ Bitcoin では、すべてのシグネチャハッシュは間接的に公開鍵に対してコミットしているため、これは懸念点とはなりません。しかしながらこれは SIGHASH_NOINPUT (BIP 118) のような提案や、署名スキームが他の目的で利用された場合—特に BIP32 の非硬化派生のようなスキームと組み合わせた場合では状況が変わります。これを防ぐため、我々は鍵プレフィックスされた^[2] Schnorr 署名を選択します; 公式を sG = R + H(R || P || m)P と変更することによって。

R の符号のエンコーディング 我々は R オプションを選択したので、点 R を署名にエンコードする必要があります。これにはいくつかの可能性が存在します:


R の完全な X および Y 座標をエンコーディングする。署名は 96 バイトになる。
完全な X 座標、および Y が偶数か奇数かだけをエンコードする（圧縮公開鍵のように）。これにより署名は 65 バイトになる。
X 座標だけをエンコードし、署名としては 64 バイトだけが残る。
一番目のオプションを用いれば、検証は少しだけ効率的になります（約5%）が、署名サイズを最優先とすることで 3 番目のオプションを選択することにします。

暗黙な Y 座標 バッチ検証をサポートするためには、R の Y 座標は曖昧ではいけません（どの有効な X 座標も二つの可能な Y 座標を持ちます）。対称性を破るためにはいくつかのオプションから一つを選択しなければいけません:


Y 座標を暗黙に（取りうる値全体の）前半のものとする。
Y 座標を暗黙に偶数であると選択する^[3]。
Y 座標を暗黙に平方剰余（体の大きさを法として、平方根が存在すること）であると選択する^[4]。
三番目のオプションは署名作成時間は遅くなりますが、検証は少しだけ速くなります。なぜならヤコビアン座標（楕円曲線演算の逆乗計算を避けるための一般的な最適化）で表された点に対して Y 座標の平方剰余は直接的に計算できるからです。その他の二つのオプションは高価と思われるアフィン座標への変換が必要となります。もし符号や偶奇性があらわにコードされていた（上の設計の選択におけるオプション 2）としてもこれは必要となります。

最終的なスキーム この結果、我々の最終的なスキームは (r, s) を署名として用いるものとなります。ここで r は曲線上の点 R の X 座標で、その Y 座標は平方剰余であり、sG = R + H(r || P || m)P を満たします。


仕様


まずはじめに検証アルゴリズムを説明します。その後で署名作成アルゴリズムを説明します。

以下の慣例を用います:


小文字の変数は、整数またはバイト配列を表します。定数 p は体のサイズ 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F を表します。
定数 n は曲線の位数 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 を表します。
大文字の変数は p を法とする方程式 y² = x³ + 7 を満たす整数が表す、曲線上の点を表します。infinite(P) は P が無限遠点にあるかどうかを返却します。
x(P) および y(P) は点 P（無限遠点ではないと仮定）の X および Y 座標を表します。
定数 G は生成元を表します。ここで x(G) = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 および y(G) = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
oncurve(P) は点 P が曲線上にあり、かつ、無限遠点ではないかどうかを返却します。
点の加算は通常の楕円曲線群の演算を表します。
整数と点の積は群演算の繰り返し適用を表します。
関数および演算:|| はバイト配列の結合を表します。
x を整数としたとき、関数 bytes(x) は x の 32 バイトエンコーディングを表します（ビッグエンディアン）。
P を点としたとき、関数 bytes(P) は byte(0x02 + (y(P) & 1)) || bytes(x(P)) を表します^[5]。
x を 32 バイトの配列としたとき、関数 int(x) は 256 ビットの符号なし整数を表します（ビッグエンディアン）。
x を 32 バイトの配列としたとき、関数 x[i:j] は i 番目のバイト（含む）から j 番目のバイト（含まない）のコピーからなる、j - i バイトの配列を表します。
x をバイト配列としたとき、関数 hash(x) は x の 32 バイトの SHA256 ハッシュを表します。
x を整数としたとき、関数 jacobi(x) は x / p のヤコビ記号を表します。これは x^(p-1)/2 mod p に等しくなります(Euler の規準)^[6]。
検証


入力:


公開鍵 P: 点
メッセージ m: 32 バイト配列
署名 sig: 64 バイト配列
署名は、下記のアルゴリズムが失敗しない時に限り有効です。


not oncurve(P) のとき失敗。
r = int(sig[0:32]) とする; r ≥ p のとき失敗。
s = int(sig[32:64]) とする; s ≥ n のとき失敗。
e = int(hash(bytes(r) || bytes(P) || m)) mod n とする。
R = sG - eP とする
infinite(R) または jacobi(y(R)) ≠ 1 または x(R) ≠ r のとき失敗。
バッチ検証


入力:


署名の数を u とする。
P_1...u を公開鍵とする: u 個の点
m_1...u をメッセージとする: u 個の 32 バイト配列。
sig_1...u を署名とする: u 個の 64 バイト配列。
a_2...u を 1...n-1 の範囲の乱数とする: u-1 個の整数。CSPRNG をすべての入力を用いて初期化したものを用いて決定的に生成されたものでも、それぞれのバッチ検証時に独立にランダムに生成されたものでも構わない。
すべての与えられた署名は、下記のアルゴリズムが失敗しない限り有効です。


For i = 1 .. u:not oncurve(P) のとき失敗。
r = int(sig_i[0:32]) とする; r ≥ p のとき失敗。
s_i = int(sig_i[32:64]) とする; s_i ≥ n のとき失敗。
e_i = int(hash(bytes(r) || bytes(P_i) || m_i)) mod n とする。
c = r³ + 7 mod p とする。
y = c^(p+1)/4 mod p とする^[7]。
y² ≠ c のとき失敗。
R_i = (r, y) とする。
(s₁ + a₂s₂ + ... + a_us_u)G ≠ R₁ + a₂R₂ + ... + a_uR_u + e₁P₁ + (a₂e₂)P₂ + ... + (a_ue_u)P_u のとき失敗。
署名作成


入力:


秘密鍵 d: 1..n-1 の範囲内の整数。
メッセージ m: 32 バイト配列
署名を作成するためには:


k = int(hash(bytes(d) || m)) mod n とします^[8]。
R = kG とします。
jacobi(y(R)) ≠ 1 の場合 k = n - k とします。
e = int(hash(bytes(x(R)) || bytes(dG) || m)) mod n とします。
署名は bytes(x(R)) || bytes(k + ed mod n) となります。
これは 唯一の署名 スキームではないことに注意してください: このアルゴリズムは与えられたメッセージおよび公開鍵に対して常に同じ署名を生成しますが、k（すなわち R）は他の方法（例えば CSPRNG）で生成されても構わず、これにより有効ではあるものの異なる署名が生成されます。


最適化


楕円曲線の実装の最適化に対して、いくつかの方法が知られています。それらの内いくつかはここで適用可能ですが、この文書の範囲を越えています。しかしながら、設計の決定に関連する二つを下記に記載します:

ヤコビ記号 関数 jacobi(x) は上記のように定義されているものですが、拡張 GCD アルゴリズムにより、もっと効率的に計算できます。

ヤコビアン座標 ヤコビアン座標を用いることで、楕円曲線演算は、より効率的に実装できます。このように実装された楕円曲線演算は、中間で発生するいくつもの逆乗演算（これらは計算的に高価です）を回避します。また、この文書で提案されているスキームは実のところ、検証の際には逆乗を一切必要としないように設計されています。点 P のヤコビアン座標を (x, y, z) とすると、x(P) は x / z² と定義され、y(P) は y / z³ と定義されます:


oncurve(P) は y² = x³ + 7z⁶ mod p と実装できます。
jacobi(y(P)) は jacobi(yz mod p) と実装できます。
x(P) ≠ r は x ≠ z²r mod p と実装できます。
応用


Schnorr 署名のコンセンサスレベルでのサポートは、単純な署名以上にいくつかの応用を可能とします。


マルチシグネチャおよびスレッショルド署名


MuSig のような対話的スキームを用いることで、参加者は連帯して署名を行える、結合公開鍵を生成することができます。これにより、検証者から見た場合に通常の署名と何ら違いのない形で n-of-n のマルチシグネチャを実現することができます。これは CHECKMULTISIG やその他の方法と比べるとプライバシーや効率性が改善している方法となります。

さらに、Schnorr 署名を Pedersen 秘密共有と組み合わせることで、対話的なスレッショルド署名スキームを作ることができ、これにより予め決められた署名者の組のうち、任意の組からのみ署名を生成できることを保証できます。例えば、k-of-n スレッショルド署名は、このように実現できます。さらに、このスキームの参加者の鍵の組み合わせを MuSig に置き換えることもできますが、このような組み合わせのセキュリティについては解析が必要でしょう。


アダプタ署名


アダプタ署名は公開ナンスを既知の点 T = tG だけ署名者がずらしますが、秘密ナンスはずらさないことで生成できます。
同一のメッセージかつ同一のナンスに対する正しい署名（または、部分署名。個別の署名者のマルチシグネチャに対する貢献をこのように呼びます）は t だけアダプタ署名をずらしたものと等しくなります。これは t の値を知ることは、正しい署名を知ることに等しくなります。
これにより、アトミックスワップまたは一般的な支払チャネルが利用できるようになります。これは、ビットコインのスクリプトの支援ではなく、署名自体を利用して互いに異なるトランザクションのアトミック性が保証されるからです。その結果トランザクションは、検証者にとっては通常の単一署名者のトランザクションと、ロックタイム返金ロジックがおそらく入っていることを除けば、区別できなくなります。

アダプタ署名は、スクリプトの役割を固定サイズの署名にエンコードすることによる効率性やプライバシ的な有用性を越えて、伝統的なハッシュベースの支払チャネルに関して追加の有用性を持ちます。特に、秘密の値 t をホップ間で再度隠されることで、トランザクションの長いチェインを、参加者でさえどのトランザクションがチェインの一部であるのかを同定できないようにしながら、アトミックにすることができます。また、秘密の値は鍵生成時ではなく、署名作成時に選択されるため、既存の出力は、ブロックチェーンの助けを借りることなく、また複数回に渡って、異なった応用に対して再利用できるようになります。


ブラインド署名


Schnorr 署名は非常に簡単なブラインド署名の構成を持ちます。この署名は、署名者が何に対して署名したかを知ることなく、第三者の依頼に基づいて署名を生成することができます。
これらは例えば部分的なブラインドアトミックスワップに利用することができます。これは公開ブロックチェーンのトランザクショングラフにおいて参加者を結びつけることなく、信頼できないエスクロー提供者による仲介でコインを転送することを可能とする構造です。

伝統的な Schnorr ブラインド署名は Wagner の攻撃に対して脆弱ではありますが、実用的に利用可能で既知の攻撃の存在しないいくつかの緩和策があります。それでもやはり、ブラインド署名スキームのセキュリティを信頼するためには、より多くの解析が必要とされています。


テストベクトル


以下のすべてのデータフィールドはバイト配列として 16 進数で与えられています。

以下の (公開鍵、メッセージ、署名) の組は検証を合格します。さらに、本文書の仕様に準拠する署名者は、与えられた（秘密鍵、メッセージ）のペアに対して指定された署名を生成しなければなりません^[9]:


テストベクトル 1秘密鍵: 0000000000000000000000000000000000000000000000000000000000000001
公開鍵: 0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
メッセージ: 0000000000000000000000000000000000000000000000000000000000000000
署名: 787A848E71043D280C50470E8E1532B2DD5D20EE912A45DBDD2BD1DFBF187EF67031A98831859DC34DFFEEDDA86831842CCD0079E1F92AF177F7F22CC1DCED05
テストベクトル 2秘密鍵: B7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF
公開鍵: 02DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659
メッセージ: 243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89
署名: 2A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D1E51A22CCEC35599B8F266912281F8365FFC2D035A230434A1A64DC59F7013FD
テストベクトル 3秘密鍵: C90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B14E5C7
公開鍵: 03FAC2114C2FBB091527EB7C64ECB11F8021CB45E8E7809D3C0938E4B8C0E5F84B
メッセージ: 5E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C
署名: 00DA9B08172A9B6F0466A2DEFD817F2D7AB437E0D253CB5395A963866B3574BE00880371D01766935B92D2AB4CD5C8A2A5837EC57FED7660773A05F0DE142380
以下の（公開鍵、メッセージ、署名）の組は、検証に合格します:


テストベクトル 4公開鍵: 03DEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34
メッセージ: 4DF3C3F68FCC83B27E9D42C90431A72499F17875C81A599B566C9889B9696703
署名: 00000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C6302A8DC32E64E86A333F20EF56EAC9BA30B7246D6D25E22ADB8C6BE1AEB08D49D
以下の（公開鍵、メッセージ、署名）の組は、検証に合格しません:


テストベクトル 5公開鍵: 02DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659
メッセージ: 243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89
署名: 2A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1DFA16AEE06609280A19B67A24E1977E4697712B5FD2943914ECD5F730901B4AB7
理由: 不正な R の範囲
テストベクトル 6公開鍵: 03FAC2114C2FBB091527EB7C64ECB11F8021CB45E8E7809D3C0938E4B8C0E5F84B
メッセージ: 5E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C
署名: 00DA9B08172A9B6F0466A2DEFD817F2D7AB437E0D253CB5395A963866B3574BED092F9D860F1776A1F7412AD8A1EB50DACCC222BC8C0E26B2056DF2F273EFDEC
理由: メッセージハッシュが不正
テストベクトル 7公開鍵: 0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
メッセージ: 0000000000000000000000000000000000000000000000000000000000000000
署名: 787A848E71043D280C50470E8E1532B2DD5D20EE912A45DBDD2BD1DFBF187EF68FCE5677CE7A623CB20011225797CE7A8DE1DC6CCD4F754A47DA6C600E59543C
理由: s の値が不正
テストベクトル 8公開鍵: 03DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659
メッセージ: 243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89
署名: 2A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D1E51A22CCEC35599B8F266912281F8365FFC2D035A230434A1A64DC59F7013FD
理由: 公開鍵が不正
付録 A: リファレンスコード


素朴でとても非効率的で非定数時間の、純粋な Python 3.2 による署名作成および検証アルゴリズムの実装は以下です。

import hashlib
import binascii

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

def point_add(p1, p2):
    if (p1 is None):
        return p2
    if (p2 is None):
        return p1
    if (p1[0] == p2[0] and p1[1] != p2[1]):
        return None
    if (p1 == p2):
        lam = (3 * p1[0] * p1[0] * pow(2 * p1[1], p - 2, p)) % p
    else:
        lam = ((p2[1] - p1[1]) * pow(p2[0] - p1[0], p - 2, p)) % p
    x3 = (lam * lam - p1[0] - p2[0]) % p
    return (x3, (lam * (p1[0] - x3) - p1[1]) % p)

def point_mul(p, n):
    r = None
    for i in range(256):
        if ((n >> i) & 1):
            r = point_add(r, p)
        p = point_add(p, p)
    return r

def bytes_point(p):
    return (b'\x03' if p[1] & 1 else b'\x02') + p[0].to_bytes(32, byteorder="big")

def sha256(b):
    return int.from_bytes(hashlib.sha256(b).digest(), byteorder="big")

def on_curve(point):
    return (pow(point[1], 2, p) - pow(point[0], 3, p)) % p == 7

def jacobi(x):
    return pow(x, (p - 1) // 2, p)

def schnorr_sign(msg, seckey):
    k = sha256(seckey.to_bytes(32, byteorder="big") + msg)
    R = point_mul(G, k)
    if jacobi(R[1]) != 1:
        k = n - k
    e = sha256(R[0].to_bytes(32, byteorder="big") + bytes_point(point_mul(G, seckey)) + msg)
    return R[0].to_bytes(32, byteorder="big") + ((k + e * seckey) % n).to_bytes(32, byteorder="big")

def schnorr_verify(msg, pubkey, sig):
    if (not on_curve(pubkey)):
        return False
    r = int.from_bytes(sig[0:32], byteorder="big")
    s = int.from_bytes(sig[32:64], byteorder="big")
    if r >= p or s >= n:
        return False
    e = sha256(sig[0:32] + bytes_point(pubkey) + msg)
    R = point_add(point_mul(G, s), point_mul(pubkey, n - e))
    if R is None or jacobi(R[1]) != 1 or R[0] != r:
        return False
    return True


脚注


^  より正確には選択メッセージ攻撃において強偽造不可能 (SUF-CMA) であり、これは平たく言うと、秘密鍵の知識がない場合にはメッセージに対する有効な署名だけが与えられた場合には、同一のメッセージに対するふたつ目の有効な署名を思いつくことが不可能であることを表しています。ランダムオラクルモデルにおけるセキュリティの証明は例えば Kiltz, Masny および Pan らによる論文で見つけることができますが、これは本質的には Pointcheval および Stern による Schnorr 署名のオリジナルのセキュリティ証明をより明確に言い直しているにすぎません。これらの証明は (R, s) ではなく (e, s) を使った Schnorr 署名の亜種に対するものです（下記の設計をご覧ください）。我々は R の固有なエンコーディングを用いているため、(R, s) を (e, s) にマップする効率的に計算可能な全単射が存在します。これにより、(e, s) 亜種に対する成功的な SUF-CMA 攻撃者を (r, s) 亜種に対する成功的な SUF-CMA 攻撃者に変換することが出来ます（逆も同様）。もっというと、前述の証明は鍵プレフィクシングのない Schnorr 署名の亜種に対して考えられていますが（下記の設計をご覧ください）、鍵プレフィクシングのある亜種に対しても証明は正しいことを確認することが出来ます。その結果、前述のセキュリティの証明はこのドキュメントで提案されている Schnorr 署名の亜種に対しても適用できるのです。
^  公開鍵をコミットする（短いハッシュ値や全く行わない場合に比べて）ことによる制約は、公開鍵のリカバリーができなくなってしまうことや、短い公開鍵ハッシュに対して署名を検証できなくなってしまうことです。こうした構成は一般的にバッチ検証と互換性がありません。
^  p は奇数なので、p を法とする -1 倍は偶数を奇数へ、奇数を偶数へマップします。これは有効な X 座標に対しては、一つの対応する Y 座標は偶数であり、もう一方は奇数であることを意味します。
^  二つの数字の積が平方剰余であるためには、数字の双方が平方剰余であるか、もしくはどちらも平方剰余でない必要があります。-1 は平方剰余ではなく、与えられた X 座標に対応する二つの Y 座標はそれぞれ互いの -1 倍なので、二つのうちちょうどひとつだけが平方剰余でなくてはならないことが分かります。
^  これは Bitcoin で既に用いられている、楕円曲線上の点の圧縮エンコーディングに一致します。これは SEC 1 標準の 2.3.3 節に従っています。
^  secp256k1 曲線の点 P に対しては、jacobi(y(P)) ≠ 0 が成り立ちます。
^  Y 座標は c の平方根であり、存在するなら y = ±c^(p+1)/4 mod p として計算できます（平方剰余を参照ください）。存在は、平方を計算し c と比較することで確かめられます。Euler の規準により、c^(p-1)/2 = 1 mod p が満たされます。同じ基準を y に適用すると y^(p-1)/2 mod p= ±c^{(p+1)/4^(p-1)/2} mod p = ±1 mod p となります。従って、y = +c^(p+1)/4 mod p は平方剰余であり、-y mod p は平方非剰余です。
^  一般的に、ハッシュ関数の出力に対して曲線の位数を法として割ったものは受け入れられないような偏りのある結果を出力することに注意してください。しかしながら secp256k1 曲線では、位数は十分に 2²⁵⁶ に近いため、この偏りは観測できません（1 - n / 2²⁵⁶ はおおよそ 1.27 * 2^-128 です）。
^  しかしながら、準拠しない署名者は検証者にとっては有効ですが異なる署名を生成することもできます。


謝辞


この文書は数年に渡る Schnorr ベースの署名に関するいくつもの議論の結果であり、Johnson Lau, Greg Maxwell, Jonas Nick, Andrew Poelstra, Tim Ruffing, Rusty Russell および Anthony Towns からの意見をもらったものです。