ブロックチェーン企業で働くエンジニアのブログ

ブロックチェーン領域のエンジニアとして働いています

MoneroのRingCTに使われる署名の基本となるLWWのLSAGについて

f:id:naomasabit:20201223003118p:plain

MoneroのRing Confidential Transactionによって利用された技術にMLSAGがありますが、元となった技術としてLWWのLSAG(Linkable Spontaneous Anonymous Group)があります。これはAdam Backが修正を加えることでRingCT利用可能だと伝えたものです。

MLSAGについてもまとめますが、まず基礎知識としてLWWのLSAGについてまとめます。元論文はMonero Research Labが出しているRing Confidential Transactionのペーパーです。

リング署名について

事前知識としてまずリング署名の基礎について触れます。リング署名をとても雑に表現すると、N人のメンバーがいる時、ランダムな値とダミーの公開鍵を用いて順番に署名していきます。

f:id:naomasabit:20201220224224p:plain
リング署名 - 順番に署名していく図

得られた最後の一人の署名を用い、自身の秘密鍵を用いて署名を行うと最初の値になるように値を調整することで循環するリングを作成します。この形を作成することで、第3者からはリング参加者の誰かが秘密鍵署名者であることはわかりつますが、誰かは特定することはできません。

f:id:naomasabit:20201220224058p:plain
リング署名図

これらの図は「How To Leak a Secret」というリング署名の提案がされた古典論文より引用しています。

LWW のLSAGの署名

LWWのLSAGはリング署名を基にした形です。利用される用語を以下にまとめています。

f:id:naomasabit:20201220230009p:plain
用語集

まず、最初にα、参加者n人全員のダミー公開鍵  P _ 1, ..., P _ n,ランダムな数値 s _ i,  i \in \{1,....,n \} , i \neq n を用意します。

jからスタートし、

  1.  L_j = αG ,  R_j = αH_p(P_j) を計算します。
  2. 次に L_j, R_jから c_{j+1} = h(m,L_j,R_j) を計算します
  3.  c _ {j+1} をもちいて  L _ {j+1} = s _ {j+1}G+c _ {j+1}P _ {j+1} ,  R _ {j+1}=s _ {j+1}{H _ p}P _ {j+1} + c _ {j+1}I を計算します
  4. 2同様に c _ {j+2} を計算します。
  5. 3同様に L _ {j+2}, R _ {j+2} を計算します。

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

そのように計算した結果が下図で  L _ j = αG ,  R _ j = α H _ p(P _ j) となり、 L _ j, R _ j がリング状になります。

 L_j, R_j の等式変換は図参照。

f:id:naomasabit:20210101182934p:plain
LWWのLSAG署名方法

最終的な署名セットは  σ = (I, c _ 1, s _ 1, ... , s _ n) となる。

LWW のLSAGの署名検証

検証者は、 L _ i, R _i, c _ i を用いて、 c _ (i+1) = h(m, L _ i, R _ i) を計算し、  c _ (n+1) = c _ 1 でリングになっていることを検証する。

キーイメージの利用方法

署名  σ = (I, c _ 1, s _ 1, ... , s _ n) のうち、  I はコインの二重使用を防ぐために利用します。署名者の鍵からキーイメージを計算することで、同一のキーイメージが利用されたらそれは秘密鍵の二重使用とみなす。Moneroはアドレスは使い捨てのため、秘密鍵を二回利用するすなわちコインの二重使用とみなし、不正送金とする。

これを前提にしてMLSAGを次の記事は解説していきます。

参考

techmedia-think.hatenablog.com