Schnorr署名がビットコインファイナンスをどのように改善できるかを理解するための記事

原文(中文)Schnorr署名がビットコインファイナンスをどのように改善できるかを理解するための記事

※自動翻訳

元のタイトル：「乾物| Schnorrの署名を改善する方法ビットコイン“、ステパンによる

Blockstreamによって書かれたMuSigの論文を読んでいるとき、私はこれがビットコインユーザーとしての私にとって何を意味するのかを想像してきました。 Schnorr署名のいくつかの機能は本当に素晴らしくて便利だと思いますが、いくつかの機能は非常に煩わしいものです。この記事では、私の考えを皆さんと共有したいと思います。しかし、すぐに確認しましょう。

楕円曲線署名アルゴリズム
Schnorr署名
結論は

楕円曲線署名アルゴリズム

現在のビットコイン所有権システムは、ECDSA（楕円曲線署名アルゴリズム）を使用しています。メッセージmに署名するとき、最初にメッセージをハッシュしてハッシュ値、つまりz = hash（m）を取得します。また、乱数（または少なくとも一見乱数）kも必要です。ここでは、乱数ジェネレーターを信頼したくないので（修飾されていない乱数ジェネレーターに関連するエラーや脆弱性が多すぎる）、通常、既知の秘密の値とメッセージに署名する内容に基づいてRFC6979を使用します。決定論的k。

秘密鍵pkを使用して、メッセージmの署名を生成できます。署名は、r（ランダムポイントのx座標R = k * G）とs =（z + r * pk）/ kの2つの数値で構成されます。。

次に、公開鍵P = pk * Gを使用して、誰でも署名を検証できます。つまり、（z / s）×G +（r / s）×Pのx座標が実際にrであることを確認できます。

ECDSAアルゴリズム図。説明を簡単にするために、楕円曲線は実数フィールドに描かれています

このアルゴリズムは非常に一般的で、非常に使いやすいです。しかし、改善の余地があります。まず、署名の検証には除算（1 / s）と2点乗算が含まれ、これらの操作は非常に計算量が多くなります。ビットコインネットワークでは、すべてのノードがすべてのトランザクションを検証する必要があるため、ネットワークでトランザクションを送信する場合、ネットワーク全体の何千ものノードが署名を検証する必要があります。したがって、署名プロセスのコストが大きくなったとしても、署名の検証を容易にすることは非常に有益です。

次に、ノードが署名を検証するときに、各署名を個別に検証する必要があります。 mnのマルチシグニチャトランザクションでは、ノードは同じシグニチャを複数回検証する必要があります。たとえば、7-11マルチシグニチャトランザクションには7つのシグニチャが含まれており、ネットワーク内の各ノードは7つのシグニチャを個別に検証する必要があります。さらに、このタイプのトランザクションの量も非常に多く、ユーザーはこれに対してはるかに多くの費用を支払う必要があります。

Schnorr署名

Schnorr署名の生成方法は少し異なります。これは2つのスカラー（r、s）ではなく、点Rとスカラーsです。 ECDSA署名と同様に、Rは楕円曲線R = k * G上のランダムな点です。署名sの2番目の部分の計算プロセスも異なります：s = k + hash（P、R、m）・pk。ここで、pkは秘密鍵、P = pk * Gは公開鍵、mはメッセージです。検証プロセスは、s * G = R + hash（P、R、m）* Pをチェックすることです。

グラフィカルなSchnorr署名と検証

この方程式は線形であるため、複数の方程式を加算および減算することができ、等号は引き続き保持されます。これにより、Schnorr署名の多くの優れた機能がもたらされます。

1.バッチ検証

ブロックチェーン上のブロックを検証するときは、ブロック内のすべてのトランザクションの署名が有効であることを検証する必要があります。それらの1つが無効である場合、どちらに関係なく、ブロック全体を拒否する必要があります。

ECDSAの各署名は特別に検証する必要があります。つまり、ブロックに1000の署名が含まれている場合、1000の除算と2000のポイント乗算、合計で約3000の重い演算を計算する必要があります。

しかし、Schnorr署名を使用すると、すべての署名検証式を合計して、いくつかの計算を節約できます。 1000個のトランザクションを含むブロックで、次のことを確認できます。

（s1 + s2 +…+ s1000）×G =（R1 +…+ R1000）+（ハッシュ（P1、R1、m1）×P1 +ハッシュ（P2、R2、m2）×P2 +…+ハッシュ（P1000、R1000、m1000）× P1000）

これは、一連のポイントの追加（コンピューター操作の観点からは、単純に無料です）と1001ポイントの乗算です。すでにほぼ3倍のパフォーマンスの向上-検証中に署名ごとに1回の再計算のみが必要です。

2つの署名のバッチ検証。検証式は線形加算可能であるため、すべての署名が有効である限り、これらの式の合計も確立する必要があります。スカラーとポイントの加算はポイントの乗算よりもはるかに簡単に計算できるため、いくつかの計算を節約できます。

2.キーの生成

ビットコインを安全に保管したいので、ビットコインを制御するために少なくとも2つの異なる秘密鍵を使用したい場合があります。 1つはラップトップまたは携帯電話（オンラインウォレット、ホットウォレット）で使用され、もう1つはハードウェアウォレット/コールドウォレットに配置されます。それらの1つがリークされた場合でも、私たちはビットコインを管理しています。

現在、この種のウォレットを実装する方法は、2-2マルチシグニチャスクリプトを使用することです。つまり、トランザクションには2つの独立した署名が含まれている必要があります。

Schnorr署名では、鍵のペア（pk1、pk2）を使用し、共有公開鍵P = P1 + P2 = pk1 * G + pk2 * Gを使用して共通の署名を生成できます。署名を生成するときは、2つのデバイスで乱数（k1、k2）を生成し、2つのランダムな点Ri = ki * Gを生成し、hash（P、R1 + R2、m）を追加する必要があります。s1を取得できます。およびs2（si = ki + hash（P、R、m）* pkiであるため）。最後に、それらを合計して署名（R、s）=（R1 + R2、s1 + s2）を取得します。これは共有署名であり、共有公開鍵で検証できます。他の人は、これが集約された署名であるかどうかを判断できません。通常のSchnorr署名と何ら変わりはありません。

ただし、このアプローチには3つの問題があります。

最初の問題はUIにあります。トランザクションを開始するには、2つのデバイスで複数ラウンドの対話を開始する必要があります-共通のRを計算し、署名するためです。 2つの秘密鍵の場合、コールドウォレットにアクセスする必要があるのは1回だけです。ホットウォレットで署名するトランザクションを準備し、k1を選択してR1 = k1 * Gを生成し、署名するトランザクションを組み合わせることができます。これらのデータは、コールドウォレットに渡して署名します。 R1はすでに利用可能であるため、署名トランザクションはコールドウォレットで1ラウンドのみで完了できます。コールドウォレットからR2とs2を取得し、ホットウォレットに戻します。ホットウォレットは前述の（k1、R1）署名トランザクションを使用し、2つの署名が一緒に追加されてトランザクションをブロードキャストします。

この経験は、私たちが現在できることと何ら変わりはなく、秘密鍵を追加するたびに、問題はより複雑になります。 10個の秘密鍵で共同で管理されている富があり、世界中に10個の秘密鍵が保管されているとします。このとき、トランザクションを送信したいとします。なんて面倒なことでしょう。現在のECDSAアルゴリズムでは、各デバイスに1回アクセスするだけで済みますが、Schnorrのキー集約を使用する場合、すべてのRiと符号を取得するために2回必要です。この場合、集約は使用されない可能性があり、各秘密鍵を使用して個別に署名することをお勧めします。したがって、1回の対話のみが必要です。

記事が完成した後、Manu Drijversからフィードバックを受け取りました。証明可能安全性を持つマルチ署名スキームでは、3ラウンドの対話が必要です。

乱数kiと対応するランダムポイントRi = ki Gを選択し、各デバイスにRi ti = hash（Ri）のハッシュ値を伝えます。そうすれば、各デバイスは、他の乱数がわからないことを確認できます。人々。アイデアを変える*
すべての数Riを収集し、共通のRを計算します
サイン

2番目の問題は、既知の不正キー攻撃です。この論文は非常によく説明しているので、繰り返しません。これはおそらく、デバイスの1つがハッキングされ（たとえば、ホットウォレットがハイジャックされた）、公開鍵が（P1-P2）であると偽った場合、2つの秘密鍵の共有を秘密だけで制御できることを意味します。キーpk1ファンド。簡単な解決策は、デバイスをセットアップするときに、対応する公開鍵に署名するために秘密鍵を要求することです。

3番目の大きな問題があります。決定論的kを使用して署名することはできません。決定論的kを使用すると、ハッカーは単純な攻撃で秘密鍵を取得できます。攻撃は次のとおりです。ハッカーがラップトップをハッキングし、秘密鍵の1つ（pk1など）を完全に制御しました。私たちのビットコインの使用にはpk1とpk2の集約署名が必要であるため、資金はまだ安全であると感じています。したがって、通常どおりトランザクションを開始し、署名するトランザクションを準備してR1、ハードウェアウォレットに送信し、ハードウェアウォレットが署名した後、（R2、s2）をホットウォレットに送り返します…次に、ホットウォレットが実行されました間違っています。署名とブロードキャストを完了できません。そこで再試行しましたが、今回はハッキングされたコンピューターが別の乱数R1 ‘を使用しました。ハードウェアウォレットで同じトランザクションに署名し、ハッキングされたコンピューターに（R2、s2 ‘）を送り返しました。今回は、これ以上テキストはありません-すべてのビットコインがなくなっています。

この攻撃では、ハッカーは同じトランザクションに対して2つの有効な署名（（R1、s1、R2、s2）および（R1 ‘、s1’、R2、s2 ‘）を取得しました。このR2は同じですが、R = R1 + R2とR ‘= R1’ + R2は異なります。これは、ハッカーが2番目の秘密鍵を計算できることを意味します：s2-s2 ‘=（hash（P、R1 + R2、m）-hash（P、R1’ + R2、m））⋅pk2またはpk2 =（s2-s2 ‘）/（hash（P、R1 + R2、m）-hash（P、R1’ + R2、m））。これがキー集約の最も不便な側面であることがわかりました。安全に集約できるように、毎回優れた乱数ジェネレーターを使用する必要があります。

3.音楽

MuSigは、問題の1つを解決します。不正なキー攻撃は機能しなくなります。ここでの目標は、これらの公開鍵に対応する秘密鍵があることを証明する必要なしに、複数の関係者/複数の設定の署名と公開鍵を集約することです。

集約署名は、集約公開鍵に対応します。ただし、MuSigでは、すべての共同署名者の公開鍵を直接追加する代わりに、いくつかのパラメーターを掛けて、集約公開鍵P = hash（L、P1）×P1 +…+ hash（L、Pn）×Pnにします。ここで、L = hash（P1、…、Pn）-この公開番号はすべての公開鍵に基づいています。 Lの非線形性により、攻撃者は攻撃を開始するための特別な公開鍵を作成できません。攻撃者は自分のhash（L、Patk）×Patkがどうあるべきかを知っていても、そこからPatkを導出することはできません。これは、公開鍵から秘密鍵を導出する場合と同じです。

署名作成プロセスの残りの部分は、上記のプロセスと非常によく似ています。署名を生成するとき、各共同署名者は乱数kiを選択し、Ri = ki * Gを他の人と共有します。次に、すべてのランダムポイントを合計してR = R1 +…+ Rnを取得し、署名si = ki + hash（P、R、m）⋅hash（L、Pi）⋅pkiを生成します。したがって、集約署名は（R、s）=（R1 +…+ Rn、s1 +…+ sn）であり、署名の検証方法は以前と同じです。s×G = R + hash（P、R、m ）×P。

4.マーケルツリーマルチシグニチャ

また、MuSigとキーの集約には、*すべての署名者がトランザクションに署名する*必要があることに気付いたかもしれません。しかし、2〜3個のマルチシグニチャスクリプトを実行したい場合はどうでしょうか。この時点で署名の集約を使用できますか、それとも通常のOP_CHECKMULTISIGと個別の署名を使用する必要がありますか？（翻訳者注：OP_CHECKMULTISIGは、ビットコイン検証楕円曲線マルチシグニチャスクリプトの操作コードです）

最初に答えについて話させてください、はい、しかし合意は少し異なります。 OP_CHECKMULTISIGと同様のオペコードを開発できますが、集約署名が公開鍵Merkelツリーの要素に対応しているかどうかを確認します。

たとえば、公開鍵P1、P2、およびP3を使用して2〜3のマルチシグニチャスクリプトを形成する場合、これらの公開鍵（P1、P2）、（P2、P3）、のすべてのペアワイズの組み合わせを使用する必要があります。（P1、P3）Merkelツリーを構築し、Merkelツリーのルートをロックスクリプトで公開します。

ビットコインを使うときは、署名と、この署名に対応する公開鍵がツリーのルートでマークされたメルケルツリーにあることの証明を提出する必要があります。 2-3マルチシグニチャコントラクトの場合、ツリーには3つの要素しかなく、証拠に必要なハッシュは2つだけです。使用する公開鍵の組み合わせのハッシュ値とネイバーのハッシュ値です。 7-11マルチシグニチャスクリプトの場合、11！/ 7！/ 4！= 330種類の公開鍵の組み合わせがあり、証拠として8つのハッシュ値が必要です。一般的に、証拠に含まれる要素の数は、マルチシグニチャキーの数にほぼ比例します。これはlog2（n！/ m！/（nm））です。

しかし、Merkel公開鍵ツリーを使用すると、mn個のマルチシグニチャスクリプトに制限する必要はありません。公開鍵の任意の組み合わせを使用してツリーを作成できます。たとえば、ラップトップ、携帯電話、ハードウェアウォレット、ニーモニックがある場合、ラップトップ+ハードウェアウォレット、携帯電話+ハードウェアウォレット、または別のヘルパーを使用できるようにするメルケルツリーを構築できます。ビットコインを使用します。これは、現在のOP_CHECKMULTISIGでは実行できないことです。「IF-Else」スタイルのフロー制御を使用してより複雑なスクリプトを作成しない限りです。