MoneroのRingCTに使われるMLSAGについて - SaaS企業で働くプロダクトマネージャーのブログ

f:id:naomasabit:20210101195416j:plain

前回はLWWのLSAGについて記事を書きました。こちらの知識を元にして、MLSAGはどのようなものかをこの記事では述べていきます。

MLSAGはRingCTの導入時にMultilayered Linkable Spontaneous Anonymous Group signaturesとして提唱された署名方法です。

元論文はMonero Research Labが出しているRing Confidential Transactionのペーパーです。

www.blockchainengineer.tokyo

LWWのLSAGについて
MLSAGの用語集と前提条件
MLSAGの署名方法
キーイメージの利用方法
まとめ
関連記事

LWWのLSAGについて

まず、LWWのLSAGは、ランダムな値 $α, s _ (j+1) , ... , s _ (j-1)$ から $L _ j , ... , L _ (j-1) , R _ j , ... , R _ (j-1)$ を各メンバーについて計算し、最後に署名者の $s _ j$ を計算して調整することで、署名者が署名鍵を持っていることを証明する方法でした。

f:id:naomasabit:20210101182934p:image — LWWのLSAG

MLSAGは、LWWのLSAGを改良した方法で、各参加者がダミーの公開鍵を $m$ 個ずつ持つパターンです。

MLSAGの用語集と前提条件

MLSAGは登場人物がLWWのLSAG以上に多いので、ここに図でまとめておきます。

参加者が $n$ 人、 $m$ 個のデコイ（ダミー）鍵をそれぞれ持つとします。
このうち $π$ 番目の参加者が署名者で、その持っている鍵のいずれかが署名鍵 $x$ です。
キーイメージは、 $I _ j = x _ j H(P ^ j _ π) ( j =1,...,m)$ によって、各鍵について写像を計算し、結果 $(I _ 1, ... , I _ m)$ の集合になります。
ランダムな値として $α _ j , s ^ j _ i (j = 1,...,m, i = 1,...,\hat{π},...n)$ はLWWのLSAG同様に割り振る

LWWのLSAGの図と照らし合わせると、各メンバーが複数の鍵を持つことが特徴です。

MLSAGの署名方法

f:id:naomasabit:20210101191553p:plain — MLSAGの署名方法

LWWのLSAG同様に、ランダムな値 $α _ j , s ^ j _ i (j = 1,...,m, i = 1,...,\hat{π},...n)$ から始めます。

※LWWのLSAGの解説では署名者は $j$ で表されていましたが、以下MLSAGの解説では $π$ で署名者を表しています。RingCTのペーパーに準拠しています。

$π$ からスタートし、

$L ^ j _ π = α _ j G$ , $R ^ j _ π = α _ j H(P ^ j _ π) (1 \leq j \leq m)$ を計算し、m個の鍵それぞれに $L, R$ を計算します。
次に $L ^ j _ π, R ^ j _ π$ から $c_{π+1} = H(m,L ^ 1 _ π, R ^ 1 _ π, ... , L ^ m _ π, R ^ m _ π)$ を計算します
$c _ {π+1}$ をもちいて $π + 1$ 番目について、 $L ^ j _ {π+1} = s ^ j _ {π+1}G+c _ {π+1}P ^ j _ {π+1}$ , $R ^ j _ {π+1}=s ^ j _ {π+1}H{P ^ j _ {π+1}} + c _ {π+1}I _ j$ を計算します
2同様に $c _ {π+2}$ を計算します。
3同様に $L ^ j _ {π+2}, R _ {π+2}$ を計算します。

4,5を繰り返して $π-1$ まで計算したら、 $s ^ j _ π$ を $s ^ j _ π = α _ j - c _ π x _ π modl$ となるように調整します。 $l$ はed25519の定数である素数。 $l=2^ {252}+27742317777372353535851937790883648493$

そうすると、 $L ^ j _ π, R ^ j _ π$ が1で計算した内容と合致します。このように $s ^ j _ π$ を調整できるのは、署名鍵 $x$ を知っているものだけです。

すなわち、LWWのLSAGは $L,R$ について1つだけでしたが、MLSAGは $L , R$ について $m$ 個分のリングを作成することになります。

最終的な署名内容は $(I _ 1, ..., I _ m, c _ 1, s ^ 1 _ 1 , ... , s ^ m _ 1, ..., s ^ 1 _ n , ... , s ^ m _ n)$ の集合となります。

キーイメージの利用方法

LWWのLSAG同様に、キーイメージ $I _ j$ はコインの二重使用を防ぐために利用します。既に出現している $I _ j$ を持つ署名 $(I _ 1, ..., I _ m, c _ 1, s ^ 1 _ 1 , ... , s ^ m _ 1, ..., s ^ 1 _ n , ... , s ^ m _ n)$ はネットワークから拒否されます。

Moneroはアドレスは使い捨てのため、このキーイメージが利用可能です。

まとめ

この記事ではMLSAGについて検討しましたが、前回のLWWのLSAGは $m$ が1つの場合のMLSAGと見なすこともできるでしょう。

さて、MLSAGについては、金額を秘匿するConfidential Transactionを利用するタイミングで導入されました。Confidential Transactionとどのように絡み合うのか、また次の記事で解説します。

LWWのLSAGについて

MLSAGの用語集と前提条件

MLSAGの署名方法

キーイメージの利用方法

まとめ

関連記事