SaaSベンチャーで働くエンタープライズ部長のブログ

SaaSベンチャーでエンジニア→プロダクトマネージャー→エンタープライズ部長として働いています。

MoneroのRingCTに使われるMLSAGについて

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について

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

[:large]
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のペーパーに準拠しています。

 π からスタートし、

  1.  L ^ j _ π = α _ j G, R ^ j _ π = α _ j H(P ^ j _ π) (1 \leq j \leq m) を計算し、m個の鍵それぞれに  L, R を計算します。
  2. 次に L ^ j _ π, R ^ j _ πから c_{π+1} = H(m,L ^ 1 _ π, R ^ 1 _ π, ... , L ^ m _ π, R ^ m _ π) を計算します
  3.  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 を計算します
  4. 2同様に c _ {π+2} を計算します。
  5. 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のLSAGmが1つの場合のMLSAGと見なすこともできるでしょう。

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

関連記事

www.blockchainengineer.tokyo

www.blockchainengineer.tokyo

www.blockchainengineer.tokyo

www.blockchainengineer.tokyo