Develop with pleasure!

福岡でCloudとかBlockchainとか。

楕円曲線のスカラー倍算アルゴリズム Part 1

昨年9月にパテントロックが外れたことで、Bitcoin Coreでもスカラー倍算アルゴリズムの高速化オプションが有効化された↓

github.com

もともと、パテントの存在を知らずHal Finneyによって2013年にlibsecp256k1には実装されてたものの無効化されていたものが有効になったらしい↓

cointelegraph.com

楕円曲線暗号においては、楕円曲線スカラー倍算の計算をすることが多い。

秘密鍵から公開鍵を算出するのも、楕円曲線のベースポイントGに秘密鍵スカラー値としたスカラー倍算であるし、ECDSAの署名検証アルゴリズムや、ECDHで共有鍵を導出するといったケースでも。

このスカラー倍算は、素直に実装すると乗算するスカラー値分だけポイントを加算することで計算できる。例えば、xPを計算する場合、Pをx回加算することでxPを求めることができる。ただ、素直にこれを計算すると遅く効率が悪いので、スカラー倍算を高速にするためのアルゴリズムがいろいろある。ということで、実際にどんなアルゴリズムがあって、現在Bitcoin Coreではどんなアルゴリズムを実装しているのか調べてみよう(ボリューム的にBitcoin Coreのアルゴリズムは後日別の記事で)。

バイナリ法

楕円曲線スカラー倍算を多項式時間で実行するための有名なアルゴリズムがバイナリ法。乗算するスカラーxをバイナリ形式にし、

  • ビットが1の場合は、加算と2倍算を行う。
  • ビットが0の場合は、2倍算のみを行う。

ことで、計算をより高速に行う。

例えばx = 5とした場合、それをバイナリ展開すると101 {1  * 2^{2} + 0 * 2^{1} + 1 * 2^{0} })になる。5Pをバイナリ法で計算すると以下のようになる。

  1. 計算結果をQとし初期化(無限遠点Oと)する。計算中に加算する点の一時変数v = Pと初期化する。
  2. 最下位ビットは1なので、Qにvを加算し、vを2倍算しv = 2v(この時点でv = 2P)とし、ビットシフトする。
  3. 続く最下位ビットは0なので、vを2倍算しv = 2v(つまりこの時点でv = 4P)とし、ビットシフトする。
  4. 続く最下位ビットは1なので、Qにvを加算し、vを2倍算しv = 2v(この時点でv = 8P)し、ビットシフトする。
  5. 処理するビットが無いので、Qが計算結果。

手順2でQ = Pがセットされ、手順4でさらに4Pが加算されQ = 5Pになる。これがバイナリ法のアルゴリズムで、計算処理で実際に実行されるのは2倍算と加算。

Rubyecdsa gemでも楕円曲線スカラー倍算ではこのアルゴリズムを使用している。実装もシンプル↓

# Returns the point multiplied by a non-negative integer.
#
# @param i (Integer)
# @return (Point)
def multiply_by_scalar(i)
  raise ArgumentError, 'Scalar is not an integer.' if !i.is_a?(Integer)
  raise ArgumentError, 'Scalar is negative.' if i < 0
  result = group.infinity
  v = self
  while i > 0
    result = result.add_to_point(v) if i.odd?
    v = v.double
    i >>= 1
  end
  result
end

↑のコードのv.doubleが2倍算、result.add_to_point(v)が加算処理だが、これらは有限体上で計算され、具体的には以下の計算が行われている。

有限体上の加算

アフィン座標の楕円曲線の方程式を {y^{2} ≡ x^{3} + ax + b \mod p}とした場合、2つの座標点 {P = (x_1, y_1), Q = (x_2, y_2) }の加算 {P + Q = (x_1, y_1) + (x_2, y_2) = (x_3, y_3)}(P != Q)の計算は、以下の式で計算される。

  •  {\displaystyle x_{3} = \left( \frac{y_{2} - y_{1}}{x_{2} - x_{1}}  \right)^{2} - x_{1} - x_{2} \mod p}
  •  {\displaystyle y_{3} = \left( \frac{y_{2} - y_{1}}{x_{2} - x_{1}} \right) (x_{1} - x_{3}) -y_{1} \mod p}

ecdsa gemのadd_to_pointコードもこの計算をしてる。なお、 {\displaystyle \frac{y_{2} - y_{1}}{x_{2} - x_{1}}}は点Pと点Qを結ぶ直線の傾き。

有限体上の2倍算

P = Q、つまり2Pの計算は、以下の式になる。

  •  {\displaystyle x_{3} = \left( \frac{3x_{1}^{2} + a}{2y_{1}} \right)^{2} - 2x_{1} \mod p}
  •  {\displaystyle y_{3} = \left( \frac{3x_{1}^{2} + a}{2y_{1}} \right) (x_{1} - x_{3}) -y_{1} \mod p}

ecdsa gemのdoubleコードもこの計算をしてる。

ウィンドウ法

バイナリ法を少し変更したものがウィンドウ法で、ウィンドウ法ではまずウィンドウサイズwを決め、スカラーxをm進展開する。ここでmはm = 2wで、ウィンドウサイズw = 1の場合↑のバイナリ展開になる。

例えばw = 4とした場合のm進展開(16進展開)であれば、スカラーxは、

 {x = x_0 * 2^{4 * 0} + x_1 * 2^{4 * 1} + x_2 * 2^{4* 2} + ... + x_j * 2^{4 * j}}

と展開され、各 {x_i} {x_i \in{0, 1, ..., m-1(15)}}の値を取る。

例えばx = 515であれば、 {x = 3 * 2^{4 * 0}  + 0 * 2^{4 * 1}  + 2 * 2^{4* 2} = 3 + 0 + 512 = 515}と展開される。

事前準備

スカラー倍算を行う点をPとした場合、ウィンドウ法では事前に、i = 1, ..., m-1について {P_i = i * P}を計算する。m = 24であれば、i = {1,...,15}について、 {P_i = P_{i-1} + P}を計算する。つまりこの事前準備で2P, 3P, ..., 15Pが計算される。

計算
  1. 計算結果をQとし初期化(無限遠点Oと)する。
  2. i = j〜0について以下の計算をループする。
    1. Qの2倍算をw回実行し、結果をQにセットする。
    2.  {x_i > 0}の場合、事前計算したポイント {x_iP}をQに加算し、結果をQにセットする。

w = 4, x = 515の場合、実際以下の計算が行われる。

  1. 最初のループ(j = 2)
    1. Qの2倍算を4回実行し、結果をQにセット。この段階でQは無限遠点であるため、Qは無限遠点のまま。
    2. Qに2Pを加算しQにセット。この段階でQ = 2P。
  2. 2回目のループ(j = 1)
    1. Qの2倍算を4回実行し、結果をQにセット。この段階でQ = 32P。
  3. 3回目のループ(j = 0)
    1. Qの2倍算を4回実行し、結果をQにセット。この段階でQ = 512P。
    2. Qに3Pを加算しQにセット。この段階でQ = 515P。

ウィンドウ法もバイナリ法と同様、計算は2倍算と加算処理だが、点の加算回数はバイナリ法に比べて少なくなるという特徴があり、点の加算は2倍算に比べて遅いことからバイナリ法より計算コストが小さくなる。

射影座標を使った高速化

バイナリ法やウィンドウ法で計算される加算や2倍算の計算式を↑に記載したけど、どちらの計算でも逆元の計算( {\displaystyle \left( \frac{y_{2} - y_{1}}{x_{2} - x_{1}}  \right)}および {\displaystyle \left( \frac{3x_{1}^{2} + a}{2y_{1}} \right) }の部分)が登場する。この逆元の計算は拡張ユークリッド互助法などを使って行われるが、そのコストは他の加算や乗算と比べて非常に大きいので、逆元の計算を減らすことができれば計算速度も速くなる。

この逆元の計算を回避するために使われるのが射影座標になる。楕円曲線上の点は通常(x, y)座標で表すことが多く、これをアフィン座標と呼ぶ。この平面上の点の座標を、3つの要素(X, Y ,Z)で表現する射影座標と呼ばれる座標系に変換することで、計算コストの高い楕円曲線の除算の計算を回避でき、計算の高速化が可能になるという。

アフィン座標(x, y)は、射影座標(プロジェクティブ座標系)を使うと(x = X/Z mod p, Y/Z mod p)と表現でき、この変換を利用すると、アフィン座標系の楕円曲線の方程式

 {y^{2} ≡ x^{3} + ax + b \mod p}

を、射影座標系における楕円曲線の方程式

 {Y^{2}Z ≡ X^{3} + aXZ^{2} + bZ^{3} \mod p}

に変換できる。また射影座標においては以下が成立する。

  • 2つの点(X, Y, Z), (X', Y', Z')について、X' = cX, Y' = cY, Z' = cZが成立する場合、2点は等しいとみなされる。
  • 射影座標における無限遠点はX = 0かつZ = 0の点である(アフィン座標と違ってシェイ座標では無限遠点も座標表記ができる)。

プロジェクティブ座標系における加算

2つのプロジェクティブ座標系の点 {P = (X_1, Y_1, Z_1)}および {Q = (X_2, Y_2, Z_2)}の加算 {P + Q = (X_3, Y_3, Z_3)}(P != Q)の計算は、以下の式で計算される。

  •  {u = Y_{2}Z_{1} - Y_{1}Z_{2}}
  •  {v = X_{2}Z_{1} - X_{1}Z_{2}}
  •  {A = u^{2}Z_{1}Z_{2} - v^{3} -2v^{2}X_{1}Z_{2}}

として、

  •  {X_{3} = vA}
  •  {Y_{3} = u(v^{2}X_{1}Z_{2} - A) - v^{3}Y_{1}Z_{2}}
  •  {Z_{3} = v^{3} Z_{1}Z_{2}}

プロジェクティブ座標系における2倍算

P = Q、つまり2Pの計算は、以下の式になる。

  •  {w = aZ_{1}^{2} + 3X^{2}_{1}}
  •  {s = Y_{1}Z_{1}}
  •  {B = sX_{1}Y_{1}}
  •  {h = w^{2} - 8B}

として、

  •  {X_{3} = 2hs}
  •  {Y_{3} = w(4B - h) - 8Y^{2}_{1}s^{2}}
  •  {Z_{3} = 8s^{3}}

上記の計算式から逆元の計算が無くなっていることが分かる。そして算出した座標 {(X_3, Y_3, Z_3)}をアフィン座標に変換 {(x_3, y_3) = (X_3/Z_3, Y_3/Z_3)}する際に逆元の計算が発生するだけ。

ちなみに、 {(x, y) → (X/Z^{2} \mod p, Y/Z^{3} \mod p)}の変換を行うのがヤコビ座標系。座標系としては、加算はプロジェクティブ座標系が速く、2倍算はヤコビ座標系が速いという特性があり、楕円曲線スカラー倍算という意味ではヤコビ座標系を使った方が高速みたい。

参考

https://written.4403.biz/source/ecc_rev30r.pdf

と、長くなってきたので今回はここまで。

追記:

試しに射影座標を使ってスカラー倍算するコードをRubyで書いてみた↓

↑の同じバイナリ法でも、アフィン座標で計算するのに比べてかなり高速。逆元の計算が変換時以外発生いないだけでこうも違うのね。

Moneroに導入された新しいリング署名スキームCLSAG

MoneroでRingCT導入時に採用されたMLSAGについて書いた↓

techmedia-think.hatenablog.com

ので、続いて、2020年10月17日のアップグレードで新しく導入されたリング署名スキームCLSAGについて↓

https://eprint.iacr.org/2019/654.pdf

CLSAG

CLSAGはConcise Linkable Spontaneous Anonymous Groupの略で、機能としてはMLSAGと同じ機能を提供するが、署名サイズが小さくなり、署名検証も高速化する。

具体的には、インプット2つとアウトプット2つ持つ典型的なトランザクションについて、MLSAGを使ったトランザクションは約2.5KBだが、CLSAGを使うと1.9KBとなり約25%サイズが削減され、署名検証のスピードも20%の速度改善がみられるみたい。

署名の生成

↑のMLSAGの記事と同様に以下の表記を適用する(modの計算は省略)。

  • キーベクトルの個数をd
  • 各キーベクトルのリングメンバーの数をn
  • n * d個の公開鍵のセットを {L = P_{j, i}} {i \in 1, .., n}および {j \in 1, ..., d}
  • 署名に使用するリング内の鍵(1..n)のインデックスをπとする。
  • 楕円曲線上の点を出力するハッシュ関数 {\mathbb H}
  • 署名対象のメッセージをm
  • Rn * d個の全公開鍵の集約鍵

CLSAGで、d個のサイズnのキーベクトルを持つ場合(d ✕ nのマトリックスに対して)にd個の秘密鍵を使って有効な単一の署名を作る手順は↓

  1. d個分対応する秘密鍵 {x_{j, π}}を使ってキーイメージ {I_j = x_{j, π} \mathbb H(P_{j, π})}を生成する( {j \in 1, ..., d})。
  2. ランダムな数値αを生成する(MLSAGはd個生成したけどCLSAGでは1つのみ)。
  3.  {i \in 1, ..., n}からπを除いて(つまりデコイの数分)、ランダムな数値 {r_i}を生成する(MLSAGはd✕(n-1)個生成していたけど、CLSAGではn-1個)。
  4. n個の公開鍵( {i \in 1, ..., n})を使って集約公開鍵
     {W_i = \sum_{j=1}^d H(T_j || R || I_1 || ... || I_d) * P_{j, i}}
    を計算する( {T_j}はタグで、実際は”CLSAG_j”というデータのタグになる)。
    ここで、 {w_π = \sum_{j=1}^d H(T_j || R || I_1 || ... || I_d) * x_{j, π}} {W_π}に対応する集約秘密鍵となる。b
  5. d個のキーイメージを集約して集約キーイメージ
     {\tilde{W} = \sum_{j=1}^d H(T_j || R || I_1 || ... || I_d) * I_j}
    を計算する。
  6. 最初のチャレンジ {e_{π+1} = H(T_c || R || m || αG || α \mathbb H(P_{1, π}))}を計算する( {T_c}はタグで、実際は”CLSAG_c”というデータ)。
  7.  {e_{π+1}}以外のチャレンジとして、i = π+1, π+2, ..., n, 1, 2, ..., π-1について、それぞれチャレンジ {e_{i+1} = H(T_c || R || m || r_iG + e_iW_i || r_i \mathbb H(P_{1, i} + e_i \tilde{W}))} を計算する。
  8.  {r_π = α - e_πw_π}を計算する。
  9. 署名値は {σ(m) = e_1, r_1, ..., r_n}

そしてプライマリキーイメージが {I_1}で、補助イメージが {(I_2, ..., I_d)}

署名の検証

  1. キーイメージ {I_1, ..., I_d}楕円曲線のベースポイントの群内の点が検証する。
  2. n個分、集約公開鍵 {W_i}と集約キーイメージ {\tilde{W}_i}を計算する。
    •  {W_i = \sum_{j=1}^d H(T_j || R || I_1 || ... || I_d) * P_{j, i}}
    •  {\tilde{W} = \sum_{j=1}^d H(T_j || R || I_1 || ... || I_d) * I_j}
  3.  {e_1}と各rの値を使って
     {e'_{i+1} = H(T_c || R || m || r_iG + c_iW_i || r_i \mathbb H(P_{1, i} + c_i \tilde{W}))}
    を計算する。
  4. 最終的に計算した {e'_1}が署名値の {e_1}と一致すれば有効な署名。

MLSAGとの違い

↑のCLSAGの署名プロトコルとMLSAGの主な違いは、鍵の集約とLinkability。

鍵の集約

CLSAGでは、各チャレンジを生成する際にd個の鍵セットを単一の鍵として集約することで、元の鍵のマトリクスを一次元にしている。

MLSAGでは、チャレンジの入力値としてd個分 {\displaystyle (r_{j,i}G + e_iP_{j, i}, r_{j, i}\mathbb H(P_{j, i}) + e_iI_j)}のペア計算する必要があり、dの数が増えるにつれて、計算量も線形増加する。

この部分がCLSAGでは集約鍵 {W_i}と集約キーイメージ {\tilde{W}}を使った単一の {(r_iG + e_iW_i , r_i \mathbb H(P_{1, i} + e_i \tilde{W}))}のペアのみになっている(事前に鍵を集約するための計算はあるけど)。

Linkability

MLSAGの書名スキームではLinkabilityが全てのキーイメージに対して有効になるが、CLSAGの場合この部分に制限が入る。CLSAGではプライマリキーイメージと呼ばれる単一のキーイメージにのみLinkabilityが適用され、残りのキーイメージは補助キーという位置付けになる。

チャレンジの計算の部分で、 {r_i \mathbb H(P_{1, i} + c_i \tilde{W})} {P_{1, i}}に固定されているのもこのためと思われる。

↑のMLSAGの記事にも書いたが、MoneroのRingCTでは、ワンタイムアドレスによる所有権の証明と、疑似コミットメントの正しさの証明のために2次元の公開鍵セットに対してMLSAGを提供しているが、二重使用に関係するのは前者のみで、前者のキーイメージだけ二重使用のチェックに使われる。そのため、それがプライマリキーイメージとなれば、他のキーイメージにLinkabilityは不要なので、CLSAGの制限は受容可能な条件になる。

なので、各インプット毎にMLSAGやCLSAGを適用してるけど、これをインプット跨いでやろうとすると、CLSAGでは無理になる。

データスペースと計算コストの削減に

d ✕ nのセットに対してMLSAGとCLSAGで署名を生成した場合、

  • MLSAGの書名データのサイズ:1 + n * dのデータ
  • CLSAGの書名データのサイズ:1 + nのデータ

nonceとなるrの個数が鍵の集約に伴い✕d必要なくなったので、その分データを削減することができる。また前述したように一度集約鍵の計算をすれば各チャレンジでdセット発生していた楕円曲線の演算をしなくて済むので、その分計算コストが小さくなる。

RingCTでMLSAGを必要とした理由

Moneroでは、送信者の情報を秘匿するためにトランザクションインプットにデコイとなるUTXOを含めて、UTXOセットの中のいずれかが実際にトランザクションで使用されることを証明するためにリング署名を採用している。Moneroが以前採用していたSchnorr署名の変形でもあるリング署名のスキームLSAGの仕組みについては以前ブログに書いた↓

techmedia-think.hatenablog.com

そして、2020年10月17日のネットワークアップグレードで、新しいリング署名スキームConcise Linkable Spontaneous Anonymous Group (CLSAG) がサポートされた。CLSAGの仕組みについて調べようかと思ったけど、既存のMLSAGの仕組みについて書いてなかったので、まずその内容から。

表記

↑のLSAGの投稿と表記を合わせて(インデックスだけ0からではなく1からにしてある)、

  • キーベクトルの個数をdとする。
  • 各キーベクトルのリングメンバーの数をn
  • n * d個の公開鍵のセットを {L = P_{j, i}} {i \in 1, .., n}および {j \in 1, ..., d}
  • 署名に使用するリング内の鍵(1..n)のインデックスをπとする。
  • 楕円曲線上の点を出力するハッシュ関数 {\mathbb H}
  • 署名対象のメッセージをm

とする。

MLSAG

MoneroでRingCTを導入した際に導入されたリング署名スキームがMultilayer Linkable Spontaneous Anonymous Group (MLSAG)。

LSAGがあるn個の公開鍵セット(リングメンバー)について、その中のいずれかの秘密鍵で署名されたことを証明可能なリング署名スキームなのに対して、MLSAGはd個のサイズnのキーベクトルを持つ場合(d ✕ nのマトリックスに対して)にd個の秘密鍵を使って有効な単一の署名を作ることができる署名スキームとして拡張されたもの。d個分のLSAG署名を作るより、署名データがd - 1個分のサイズ分削減できる。

MoneroでRingCTを導入する際のリング署名スキームとして開発されたけど、Monero以外でも利用可能。

署名の生成

  1. d個分対応する秘密鍵 {x_{j, π}}を使ってキーイメージ {I_j = x_{j, π} \mathbb H (P_{j, π})}を生成する。LSAGだと1つだったけど、dが複数ある前提なのでその数分キーイメージも生成する。
  2. d個分ランダムな数値 {α_j}を生成する。
  3.  {i \in 1,..., n}からπを除いて(つまりデコイの数分)、 {j \in 1, ..., d}について、ランダムな数値 {r_{j, i}}を生成する。
  4. まず最初にπの次のインデックスπ + 1のチャレンジ {e_{π + 1} = H(m || α_1G || α_1 \mathbb H(P_{1, π}) || ... || α_dG ||α_d \mathbb H(P_{d, π}))}を計算する。
  5.  {e_{π + 1}}以外のチャレンジとして、i = π + 1, π +2, ..., n, 1, 2, .., π -1について、それぞれチャレンジ {e_{i + 1} = H(m || r_{1, i}G + e_iP_{1, i} || r_{1, i} \mathbb H(P_{1, i}) + e_iI_1 || ... || r_{d, i}G + e_iP_{d, i} || r_{d, 1} \mathbb H(P_{d, i}) + e_i I_d)} を生成する。
  6.  {r_{j, π} = α_j - e_πx_{j, π}}を計算する。
  7. 署名値は {σ(m) = (e_1, r_{1, 1}, ..., r_{d, n})}

理解しやすいよう具体的に、リングメンバーの数 n = 3でキーベクトルの個数 d = 2として、その公開鍵のマトリックス

  • d = 1:
    •  {P_{1, 1} = x_{1, 1}G}
    •  {P_{1, 2} = x_{1, 2}G}
    •  {P_{1, 3} = x_{1, 3}G}
  • d = 2:
    •  {P_{2, 1} = x_{2, 1}G}
    •  {P_{2, 2} = x_{2, 2}G}
    •  {P_{2, 3} = x_{2, 3}G}

とし、署名者の秘密鍵のインデックスをπ = 2とする。

  1. 生成するキーイメージは以下の2つ。
    •  {I_1 = x_{1, 2}\mathbb H(P_{1, 2})}
    •  {I_2 = x_{2, 2}\mathbb H(P_{2, 2})}
  2. 続いてランダムな数値 {α_1, α_2}を生成する。
  3. デコイの数=2つ分のnonceをdの数分生成する。
    •  {r_{1, 1}, r_{1, 3}}
    •  {r_{2, 1}, r_{2, 3}}
  4. 最初のチャレンジ {e_3 = H(m || α_1G || α_1 \mathbb H(P_{1, 2}) || α_2G || α_2 \mathbb H(P_{2, 2}))} を計算する。
  5. 残りのチャレンジを計算する。
    •  {e_1 = H(m || r_{1, 3}G + e_3P_{1, 3} || r_{1, 3} \mathbb H(P_{1, 3})  + e_3I_1 || r_{2, 3}G + e_3P_{2, 3} || r_{2, 3} \mathbb H(P_{2, 3})  + e_3I_2 )}
    •  {e_2 = H(m || r_{1, 1}G + e_1P_{1, 1} || r_{1, 1} \mathbb H(P_{1, 3})  + e_1I_1 || r_{2, 1}G + e_1P_{2, 1} || r_{2, 1} \mathbb H(P_{2, 1})  + e_1I_2 )}
  6. 最後に、 {r_{1, 2} = α_{1} - e_2x_{1, 2}} {r_{2, 2} = α_{2} - e_2x_{2, 2}}を計算する。
  7. 署名値は {\displaystyle σ(m) = (e_1, r_{1, 1}, r_{1, 2}, r_{1, 3}, r_{2, 1}, r_{2, 2}, r_{2, 3})} となる。

手順6よりαの値はそれぞれ、

  •  {α_1 = r_{1, 2} + e_2x_{1, 2}}
  •  {α_2 = r_{2, 2} + e_2x_{2, 2}}

となり、これを使って手順4の {e_3}を置き換えると、

 {e_3 = H(m || (r_{1, 2} + e_2x_{1, 2})G || (r_{1, 2} + e_2x_{1, 2}) \mathbb H(P_{1, 2}) || (r_{2, 2} + e_2x_{2, 2})G || (r_{2, 2} + e_2x_{2, 2}) \mathbb H(P_{2, 2}))}

つまり、

 {e_3 = H(m || r_{1, 2}G + e_2P_{1, 2} || r_{1, 2} \mathbb H(P_{1, 2})  + e_2I_1 || r_{2, 2}G + e_2P_{2, 2} || r_{2, 2} \mathbb H(P_{2, 2})  + e_2I_2 )}

となり、LSAGと同様、各チャレンジは循環したデータを含むようになる。

LSAGと比較すると
  • キーイメージと、nonceはdの数分増える。
  • 計算するチャレンジの数は、dが増えても変わらず、リングメンバーの数だけ。
  • ただチャレンジの入力に、全dの全リングメンバーのデータを含め循環するよう拡張してある。ここがポイント!

署名の検証

生成した署名の検証も手順はLSAGと同じで、違いは、チャレンジの入力となる各データの計算方法だけ。

  1. キーイメージが楕円曲線のベースポイントの群内の点が検証する。
  2.  {e_1}と各rの値を使って、 {e'_{i+1} = H(m || r_{1, i}G + e_iP_{1, i} || r_{1, i} \mathbb H(P_{1, i}) + e_iI_1 || ... || r_{d, i}G + e_iP_{d, i} || r_{d, 1} \mathbb H(P_{d, i}) + e_i I_d)}を計算する。
  3. 最終的に計算した {c'_1}が署名値の {e_1}と一致すれば有効な署名。

データスペースの節約に

↑のようにチャレンジの入力を多重化したのがMLSAGの仕組み。

d ✕ nのセットに対して、LSAGとMLSAGで署名を生成した場合、

  • LSAGの署名データのサイズ:(1 + n)* dのデータ
  • MLSAGの署名データのサイズ:1 + n * dのデータ

となる。nonceであるrの個数は変わらないけど、チャレンジはdの数によって変わらないので、 d - 1個で済む分データスペースを節約できる。

RingCTでMLSAGが必要な理由

2017年1月にMoneroに導入されたRingCTでは、このMLSAGが使われている。

最初は、Moneroで複数インプットがある場合に全インプットに渡って単一のMLSAG署名を作ればデータサイズを削減できるからか?と思ったけどどうもそうではなく、トランザクションの各インプットはそれぞれ個別のMLSAG署名を持っている。

RingCTからConfidential Transactionにより量をPedersen Commitmentとして表現されるようになったため、この機能の導入に伴いMLSAGが必要になっている。

CTの仕組みは

インプットのコミットメントの合計 − (アウトプットのコミットメントの合計 + 手数料へのコミットメント)= 0

が成立することでコインのインフレーションがされていないことを証明するようになっているが、Moneroでこれを単純に導入すると、デコイを含むインプットが参照するコミットメントのどれがゼロへのコミットメントかリンクできるとそもそもデコイにならないという問題が発生する。しかし、0へのコミットメントが計算できないと量が検証できない。

この問題に対処するため、実際に使用するインプットと同じ量を持つ疑似コミットメントを作成する。実際に使用するコミットメントを {c = rG + aH}とすると、疑似コミットメントは {c' = r'G + aH}となり、ブラインドファクターのみが異なる。そしてc - c' = (r - r')G + (a - a)H = (r - r')G は0へのコミットメントとなる。そしてそれが0へのコミットメントであることを証明するためc - c'に対して有効な署名を対応する秘密鍵(r - r')を使って生成できればいい。つまりこの疑似コミットメントはリングメンバーのいずれかのUTXOと同じ量を持つコミットメントであることが証明できる。

だが、単純に疑似コミットメントと署名をトランザクションインプットにセットしただけだと、リングメンバーのコミットメントと差し引いて計算してどれかが分かってしまうので、ここもリング署名にする必要がある。

RingCTでは、

  • コインの所有者であること
  • (どのコミットメントがリンクできないようにするための)疑似コミットメントが使用する実際のコミットメントと同じ量を持つこと

の2つを証明するのにリング署名を作成する。つまり、MLSAGの署名を作成するにあたって、

  • 公開鍵のセットは、
    • n個のワンタイムアドレスに対応する楕円曲線上の点
    • n個の各コミットメントから疑似コミットメントを差し引いた楕円曲線上の点
  • 対応する秘密鍵は、
    • ワンタイムアドレスに対応する秘密鍵
    • コミットメントのブラインドファクターから疑似コミットメントのブラインドファクターを差し引いた (r - r')の値

となる。なお、二重使用を防ぐために必要なキーイメージはワンタイムアドレスから作られたものだけで良いので、MoneroのRingCTのトランザクションに添付されるキーイメージはインプット毎に1つだけ。

これがRingCTの導入により、n ✕ 2のマトリックスにおけるリング署名を作らないといけない理由で、そのためにMLSAGが導入されたっぽい。

2ラウンドで安全なマルチシグを生成する署名スキームMuSig2

MuSigはもともとSchnorr署名の鍵の集約特性を活かして多重署名(マルチシグ)を単一のSchnorr署名で行う署名スキームで、Rogue-key攻撃に対して堅牢な署名スキーム↓

techmedia-think.hatenablog.com

ただ、署名の生成に以下の3ラウンドの通信が必要になる。

  1. nonce値のコミットメントの交換
  2. nonceの交換
  3. 部分署名の交換

そして、今回新しくMuSig2が公開された↓

https://eprint.iacr.org/2020/1261

MuSig2の署名方式

MuSig2では署名生成時の通信ラウンドも3→2に減らすことができる。↑のMuSigの3ラウンドの通信の内、1のnonceのコミットメントの交換プロセスを省略するみたい。省略してどう安全性を担保するのか?具体的な署名方式を見てみよう。

表記

  •  {x_1, x_2, ..., x_n}を署名プロセスに参加する各ユーザーの秘密鍵とし、対応する公開鍵を {X_1 = x_1G, X_2 = x_2G, ..., X_n = x_nG}とする。
  • すべての参加者の公開鍵を加算した集約公開鍵を {L = \sum_{i = 1}^n}X_iとする。
  • 署名対象のメッセージをmとする。

署名の生成

各署名者は以下の手順で署名を生成する。

  1. n人の署名者(署名者のインデックスをiとする)はv個のランダムな値(インデックスをjとする) {r_{i, j}}を生成する。
  2. 1で生成した値についてPublic nonce  {R_{i, j} = r_{i, j}G}を計算する。
  3. 署名者iは、2で導出したPublic nonceのリスト {R_{i, 1}, ..., R_{i, v}}を他の署名者にブロードキャストする。
  4. 署名者iは、各署名者の公開鍵から {a_i = H_{agg}(L, X_i)}を計算する。
  5. 署名者は4で計算した値を使って、集約公開鍵 {\displaystyle \tilde{X} = \sum_{i=1}^n a_i X_i}を計算する。
  6. 他の全参加者からPublic nonce のリストを受信したら、全参加者の同じインデックスjのPublic nonce  {\displaystyle R_j = \sum_{i=1}^n R_{i, j}}を集約する。
  7. 続いて、v個の係数のベクトル {(b_1, ..., b_v)}を計算する。 {b_1 = 1}で、それ以降のbの値は {\displaystyle b_j = H(j, \tilde{X}, (R_1, ..., R_v), m)}として計算する。つまりこのbは決定論的に生成される。
  8. ここでPublic nonceを集約して署名に使用する集約nonce  {\displaystyle R = \sum_{j=1}^v b_j R_j}を計算する。
  9. さらに署名に使用するチャレンジ {\displaystyle c = H_{sig}(\tilde{X}, R, m)}を計算する。
  10. そして自身の部分署名 {\displaystyle s_i = c a_i x_i + \sum_{j=1}^v r_{i, j} b_j \mod p}を計算し、他の署名者にブロードキャストする。
  11. すべての参加者の署名値を受け取ると、 {\displaystyle s = \sum_{i=1}^n s_i \mod p}を計算する。
  12. 最終的な署名値は(R, s)

署名の検証

署名者は以下を実行して署名が正しいか検証する。

  1. 各署名者の公開鍵から、 {a_i = H_{agg}(L, X_i)}を計算する。
  2. 1から集約公開鍵 {\displaystyle \tilde{X} = \sum_{i=1}^n a_i X_i}を計算する。
  3. 集約公開鍵と署名対象のメッセージおよび、署名データのRを使って、署名に使用するチャレンジ {c = H_{sig}(\tilde{X}, R, m)}を計算する。
  4. 最後に {\displaystyle sG = R  + c\tilde{X} = R + \sum_{i=1}^n a_icX_i}が成立するか検証する。成立していれば署名は有効。

集約公開鍵の算出と、チャレンジの作成方法の部分が通常とは異なるが、最後の検証式は通常のSchnorr署名の検証式と同じ。

MuSigとの違い

集約公開鍵 {\tilde{X}}の計算方法は、MuSigと同じでこれがRogue-key攻撃への耐性となるポイント。

MuSigと違うのは署名に使用するnonceの取り扱い。MuSigでは各参加者がPublic nonce  {R_i}を交換する前に、必ず {R_i}へのコミットメントを交換し、全員分のコミットメントが揃った上で {R_i}を交換する。

MuSigでnonceのコミットメントの交換が必要な理由

コミットメントの交換ラウンドを省略したり、事前にコミットメントおよびnonceの交換をした場合にどんな問題が起きるかは、Tim Ruffingの発表が分かりやすい。

問題になるのは、複数の署名セッションを並列して実行するケース。

攻撃にはWagnerのアルゴリズムを使用する。このアルゴリズムを利用すると、暗号学ハッシュ関数Hを使用した場合

  •  {H(m_0) = H(m_1)}となるような {m_0, m_1}を発見するのは困難だが、
  •  {H(m_0) = H(m_1) + H(m_2 + ... + H(m_n))}となるような {m_0, m_1, ..., m_n}を発見するのは簡単

になる(メッセージの数が増える程、必要な計算量は減る)。

被害者の鍵ペアを {X_1 = x_1G}、攻撃者の鍵ペアを {X_2 = x_2G}、両者の集約公開鍵を {X = X_1 + X_2 = (x_1 + x_2)G}とする。

  1. 攻撃者は被害者との間に、メッセージmの異なる署名セッションを複数、並列実行する。
  2. 被害者がセッションの数分、Public Nonce =  {R_1, R_2, ..., R_n}を送信する( {R = \sum_{i=1}^n R_i}とする)。
  3. 攻撃者は、ワグナーのアルゴリズムを使って {H(P, R, m) = H(P, R_1 + R'_1, m_1) + ... + H(P, R_n + R'_n, m_n)}となるPublic nonce  {R'_1, R'_2, ..., R'_n}を見つける。右辺が各署名セッションで使われるハッシュ値
  4. 攻撃者は3で見つけたPublic nonceのリストを被害者に送る。
  5. 被害者はこれらの値を使って部分的な署名 {s_1, ..., s_n}を計算する。
  6. 被害者の部分署名をすべて加算し、攻撃者が自身の部分的な署名を加えると、Public nonce Rとメッセージmについて有効な両者のSchnorr署名が完成する。

ここで、被害者は一度もメッセージmに対して部分署名を作ってはいない。にも関わらずmに対して有効な署名が作れてしまう。つまり、同じ鍵に対して複数の署名セッセションを実行することで(事前にnonceにコミットしていない場合)、偽のメッセージに署名させることができてしまう。

↑が可能なのは、攻撃者が被害者からPublic nonceを受信した後で自身のPublic nonceを細工可能であるからで、この攻撃を回避するためには、Public nonceを交換する前にそのコミットメントを交換する必要がある。これがMuSigでコミットメントの交換ラウンドが必要になっている理由。

尚、コミットメント自体は署名時ではなくても、事前に共有しておくことが可能で、MuSigを実装したBlockstreamが開発しているlibsecp-zkpでは、コミットメントの事前シェアが可能になっている。

MuSig2でコミットメントの交換を不要にしたポイント

MuSig2では、コミットメントの事前交換をせずに↑のWagnerのアルゴリズムを使った攻撃にどう対処しているのか?

↑の攻撃は、同時署名セッションのそれぞれの最初のラウンドで集約Public nonceを制御することで、署名ハッシュを制御する機能に依存している。

MuSigでは、各署名者が1回の署名セッションで生成するnonceが1つではなくv個になっている。そして部分署名を生成する際もnonce  {r_i}単体が単純な加算要素となる訳ではなく、

  • 両者のPublic nonceから係数ベクトル値bを決定論的に生成し、
  • 生成した各係数値をそれぞれのPublic nonceに乗算して集約Public nonceを生成している

この結果、↑のような集約Public nonceの制御が困難になるというのが、コミットメントラウンドを排除できた仕組みみたい。

実際にnonceの生成個数vの値については、ランダムオラクルモデル(ROM)においてv ≧ 4が推奨され、さらにROM + AGM(algebraic group model)の構成でv ≧ 2とされているので、そこまで大きい数値ではない。ただ、個数の根拠となってるセキュリティ証明あたりはまだよく理解できてない。

MuSig2のオーバーヘッド

MuSigと比べた場合のMuSig2のオーバーヘッドは、ブロードキャストするPublic nonceの値がv個に増えるのと、その個数分の操作の計算量。ただ↑のようにv値は小さいので、通信ラウンド1回分に比べたら小さなオーバーヘッドと言えそう。

決定性nonceの生成はNG

単体のSchnorr署名では問題ないが、MuSigやMuSig2などのSchnorrの多重署名スキームでは、決定性nonceの利用は攻撃による秘密鍵の漏洩に繋がるので、MuSig2でもnonceの生成(↑で各署名者がrを生成してる部分)では、安全な乱数生成器が必要になる。

現状、Schnorrの多重署名スキームで安全な決定性nonceを生成するスキームは、こないだ発表されたMuSig-DN↓のみ。

techmedia-think.hatenablog.com

※ ただ、MuSig-DNの場合、高価なゼロ知識証明の生成を必要とする。

lndが公開した2つの脆弱性CVE-2020-26895とCVE-2020-26896

先日lndに脆弱性が含まれているということで修正版のアナウンスがされていたけど、その内容が公開された↓

CVE-2020-26895

影響あるバージョン

影響を受けるのはv0.10.0-betaより前のバージョンのlnd。

脆弱性の内容

オフチェーン支払いにより状態を更新する際に、lndノードに対してhigh-ECDSA署名の受け入れが可能であるという内容。Bitcoin Coreのポリシーには、ECDSA署名値(r, s)の内、sの値が曲線の位数の半分以下の値でないといけないというルール(LOW_Sルール)があり、ECDSA署名固有のmalleabilityを解消するためのもの。high-ECDSA署名自体は有効なECDSA署名でコンセンサスルールでは受け入れられるが、Bitcoin Coreのリレーポリシーではhigh-ECDSAを受け入れていないのでトランザクションをリレーする際にはリジェクトされる。

これを悪用すると、例えばタイムロックが設定されているコントラクトを含んでいると、実際にそのトランザクションをブロードキャストしようても、接続先のノードからポリシー違反でリジェクトされ、資金の損失に繋がる可能性がある。

lndの以前のバージョンでは、LOW_Sへの変換がされていなかったため、生成された署名値sがhigh-sになっていてもそのまま受け入れていたという問題。

攻撃内容

チャネルの一方的クローズ中に、攻撃者が↑を悪用して、被害者のHTLC-successトランザクションがリレーされず、攻撃者によるHTLC-timeoutトランザクションがブロードキャストされると、HTLCにロックされている資金が攻撃者によって回収されるという攻撃が考えられる。

尚、強調クローズの場合作成されるトランザクションの署名はポリシー検証もされてるので、この問題は発生しない。

修正

ECDSA署名のLOW_Sルールがv0.10.0-betaで適用されている。ただLNの仕様を定義しているlightning-rfcで、ノードがオフチェーンで受け入れる署名の検証方法の指定が欠けているので、仕様の更新も計画されてる模様。

CVE-2020-26896

影響あるバージョン

影響を受けるのはv0.11.0-betaより前のバージョンのlnd。

脆弱性の内容

衝突するペイメントハッシュを使って転送されたHTLCインボイスのプリイメージが強制的に明かされるという脆弱性で、攻撃者に悪用されると、特定の状況下において、HTLC支払いが行われたと信じて資金を失う可能性がある。

HTLCの受信をオフチェーンではなくオンチェーンで解決する場合、転送ノードでは、HTLCを請求するためにwitnessを介して有効なプリイメージを提供することが期待される。

このプリイメージを知る方法は主に以下の2つ↓

  • 自分がインボイスを発行してプリイメージを生成する側である。
  • HTLCにより正常に支払いが転送された結果としてプリイメージを受信する。

lndではこれらを、インボイスデータベースとプリイメージデータベースの異なる2つのDBで管理している。

ノードがオフチェーンでHTLCを受信すると、ノードは自身が中間ホップか最終ホップかを判断する必要があり、

  • 最終ホップであればインボイスデータベースに対してプリイメージを照会
  • 中間ホップであればプリイメージデータベースに対してプリイメージを照会

する。

問題となったlndの挙動は、プリイメージデータベースにプリイメージが含まれていない場合、誤ってインボイスデータベースに対してもプリイメージを照会しにいくようになっていたというもの。この結果、ノードが支払い経路の最終ホップでない場合も、インボイスのプリイメージ明かす状況というのが発生する。

攻撃内容

↑の挙動を悪用すると以下のようにして、HTLCの資金を盗む攻撃が可能になる。

A -> M -> Bのような経路(Bがコインの受信者でMが攻撃者)のマルチホップ支払いのケースにおいて。

  1. BがAにインボイスを発行する。
  2. AがMを経由してBに支払う経路を選択しHTLCをオファーする。
  3. MはAのHTLC内のペイメントハッシュと同じ値のペイメントハッシュを持つM -> B -> M'の別のHTLCをBにオファーする。
  4. 3のHTLCを含むコミットメントトランザクションをオンチェーンにブロードキャストして、一方的にチャネルをクローズする。
  5. Bが4のブロードキャストを検知するとHTLC-successをブロードキャストを試みる。この時点で↑のバグのため、本来プリイメージデータベースからこのプリイメージを取得する必要があり、実際このプリイメージはそのDBには存在しないのだけど、フォールバックされインボイスデータベースへの照会が発生し、実際にオンチェーン上にプリイメージが公開され、A -> M -> Bのインボイスは既に決済済みとマークされる。
  6. Mは2と3の2つのHTLCを解決して資金を入手し、結果的にBがインボイスで請求していたコインは盗まれる。

尚、MPPを使ってる場合、他の並行MPPのHTLCがBに届いている場合は、安全チェックにより攻撃は失敗する。

修正

修正内容は、↑のインボイスデータベースとプリイメージデータベースの適切な分離で、v0.11.0-betaにおいて修正されている。