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以外でも利用可能。

署名の生成

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

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

d = １：
- ${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とする。

生成するキーイメージは以下の２つ。
- ${I_1 = x_{1, 2}\mathbb H(P_{1, 2})}$
- ${I_2 = x_{2, 2}\mathbb H(P_{2, 2})}$
続いてランダムな数値 ${α_1, α_2}$ を生成する。
デコイの数＝２つ分のnonceをdの数分生成する。
- ${r_{1, 1}, r_{1, 3}}$
- ${r_{2, 1}, r_{2, 3}}$
最初のチャレンジ ${e_3 = H(m || α_1G || α_1 \mathbb H(P_{1, 2}) || α_2G || α_2 \mathbb H(P_{2, 2}))}$ を計算する。
残りのチャレンジを計算する。
- ${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 )}$
最後に、 ${r_{1, 2} = α_{1} - e_2x_{1, 2}}$ と ${r_{2, 2} = α_{2} - e_2x_{2, 2}}$ を計算する。
署名値は $σ(m) = (e_1, r_{1, 1}, r_{1, 2}, r_{1, 3}, r_{2, 1}, r_{2, 2}, r_{2, 3})$ となる。

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

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

となり、これを使って手順４の ${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と同じで、違いは、チャレンジの入力となる各データの計算方法だけ。

キーイメージが楕円曲線のベースポイントの群内の点が検証する。
${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)}$ を計算する。
最終的に計算した ${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では、

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

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

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

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

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

Develop with pleasure!

福岡でCloudとかBlockchainとか。