Develop with pleasure!

福岡でCloudとかBlockchainとか。

MoneroでスクリプトレスなPayment Channelを実現するためのDLSAGリング署名スキーム Part1

Monero Payment Channel Cryptography

ベースの考え方であるLSAGについて整理したので↓

techmedia-think.hatenablog.com

本丸のDLSAGとDLSAGを利用したPayment Channelの仕組みについて見ていく。

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

Moneroの課題

  • BitcoinがBitcoin ScriptをEthereumがSolidityなどで記述可能なコントラクトを記述出来るのに対し、Moneroにはそういったスクリプト機能が無く、コインをある秘密鍵宛に送信者を匿名化し、量を秘匿して送ることができるだけである。BitcoinやEthereumのようにどんな条件にコインがロックされ、ただどんな条件でアンロックされるのかという情報がオンチェーン上に記録され、これがFungibilityを損なう要因にもなりうる。これに対しホワイトペーパーでは、スクリプトを導入することなく、Fungibilityを担保し、インターオペラビリティを向上する仕組みを提案している。
  • BitcoinやEthereumなどのパブリックチェーンと同様、スケーラビリティの課題を抱えている。Moneroのブロックは2分毎に作成されるが、リング署名の仕組みによりBitcoinなどと比べてどうしてもトランザクションサイズが大きくなり、スケーラビリティの課題はBitcoinよりも深刻と言える。ホワイトペーパーでは、このスケーラビリティに課題に対して既にBitcoinでは実現されているが、Payment Channel Networkを利用したオフチェーンスケーリングを提案している。

上記のMoneroにおけるトランザクションの表現力の欠如とスケーラビリティという2つの問題を解決するために提案されているのが新しいリング署名方式＝Dual Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups (DLSAG)だ。

Dual-Key LSAG

現在のMoneroのトランザクションはインプットとアウトプットを持ち、その両者は {(pk, COM(γ), \Pi_{amt})}で定義される。pkは新しい公開鍵で、COM(γ)はコインの量γへの暗号学的コミットメントを示し、 {\Pi_{amt}}はγが範囲内の値であることを証明する範囲証明を表す。トランザクションインプットは、デコイを持つため１インプットあたり複数のタプルを持つ。トランザクションアウトプットは、1アウトプットあたり１つのタプルを持つ。

これに対し、Dual-Key LSAGでは、 {((pk_{A, 0}, pk_{B, 1}), COM(γ), \Pi_{amt}, t)}と定義される新しいdual-key タプルフォーマットがベースになる。このタプルには（それぞれ異なるユーザーの公開鍵である）2つの公開鍵が含まれ、フラグtに応じて使用できる。このDual-Keyタプルは現在のMoneroのタプルと比べて以下の点が異なる。

  1. このタプルのコインを使用する可能性がある2人のユーザーを識別するため１つではなく２つの公開鍵が含まれる。
  2. 公開鍵間のスイッチを示す（例えばtがMoneroのブロックチェーン内の現在のブロック高より小さい場合には {pk_{A, 0}}が使われる等）追加の要素tが含まれる。

Dual-Keyタプルフォーマットにより、払い戻し用トランザクションを作るためのロジックをエンコードできるようになる。

シグナルtが {pk_{A, 0}}を使わなければならいことを示す場合、アリスは {pk_{A, 0}}と {pk_{B, 1}}をそれぞれ含む２つの公開鍵のセットを選択し、公開鍵 {pk_{A, 0}}に対応する秘密鍵 {sk_{A}}でリンク可能なリング署名を生成する。

逆にtが {pk_{B, 1}}を使用する必要があると示す場合、ボブはこれまでと同じ方法でリングを選択し、 {sk_{B}}でリング署名を作ることでアウトプットを使用できる。

もちろん１人のユーザーが２つの公開鍵に対応する各秘密鍵を持っているのであれば、tの値に関係なくこの１人でそのDual-Keyタプルを使用できる。

Dual-Keyのリンク可能なリング署名

↑のDual-Keyのサポートにあたって必要になるのは、新しいリンク可能なリング署名の設計で、以下の課題がある。

キーイメージの仕組み

Moneroの現在のリング署名スキームでは、単一の公開鍵から構成されるキーイメージを公開することで、Linkabilityを実現している。例えばアリスは {sk_A}を使って署名する際は、合わせてキーイメージ {I = sk_Aℍ(pk_A)}を公開する（ℍは曲線上の点を出力するハッシュ関数）。アリスが二重使用しようとして再度 {sk_A}で署名しようとすると、同じキーイメージが計算され、ブロックチェーン上で既に使用済みであることを検出できる。

Dual-Keyで同様のLinkabilityをサポートする際の課題は、公開鍵のペア {(pk_0, pk_1)}を一意に識別し、署名鍵の内 {sk_b}１つだけで計算できる単一のキーイメージを定義する方法だ。

このホワイトペーパーでは、キーイメージをDual-Keyタプルの2つの公開鍵を使ってDiffie-Hellmanの鍵交換を使い、共有鍵を導出する方法提案している。つまり {J = sk_0 \cdot sk_1 \cdot G}として再定義している。これは以下の要件を満たす：

  1. {sk_b}の知識で {J = sk_b \cdot pk_{1-b}}を計算できる。
  2. {sk_b \cdot pk_{1-b} = sk_{1-b} \cdot pk_b}が成り立つので、 {(pk_0, pk_1)}を一意に識別できる。
キーイメージのLinkabilityの強化

↑の新しいキーイメージの定義は公開鍵のペアのリンクを可能にする。ただし、キーイメージを公開鍵のペアに一意になるだけでなく、それらを含むアウトプットも一意にするのが重要だ。そうしないと、ユーザーの１人が、同じ公開鍵のペアを使って別のDual-Keyタプルを作成し、それ（およびそのキーイメージ）を使って署名を作成すると、Moneroでは同じキーイメージは二度と使えないので、元々のタプルのコインは使用不可能になってしまう。

署名スキームの安全性とプライバシーの保証を損なうこと無く、各アウトプットに一意の識別子を追加することでこれを軽減できる。例えば、Moneroでは全てのアウトプットを、そのアウトプットが含まれるトランザクションとアウトプットのインデックスで構成する値 {m = H(txid || output_index)}で識別できる。

そのため、DLSAGで使われているリングを一意のトリプル {(pk_0, pk_1, m)_{［1,n］}}で構成されていると見なし、Dualキーイメージを {J = m_j \cdot sk_{j,0} \cdot sk_{j, 1} \cdot g}と定義する。jはリング内の本当の署名の位置を表す[1, n]の値。

以上を踏まえた、新しいDLSAG署名スキームは以下のようになる。

二者がそれぞれ保持する鍵ペアを {(sk_0, pk_0), (sk_1, pk_1)}とする。 そのDual-Keyタプルのコインがロックされたトランザクションアウトプットの識別子をmとする。

DLSAGの署名生成

Dual-Keyにロックされたコインを使用するトランザクションを作成し、そのインプットにはデコイと実際に使用するDual-Keyのタプルのリスト {( (pk_{0,1}, pk_{1,1}, m_1), ...., (pk_{n, 0}, pk_{n, 1}, m_n) )}がセットされている。

  1. n個ほどランダムな値をサンプリングする。 {s'_0, s_1, ..., s_{n-1}}
  2. 実際に使用する鍵と、その公開鍵とペアになる公会鍵を使ってキーイメージ {J = m_n \cdot sk_b \cdot pk_{n, 1-b}}を計算する。ここで {sk_b}は公開鍵 {pk_{n, b}}に対応する秘密鍵。
  3. {L_0 = s_0 \cdot G}および {R_0 = s'_0 \cdot ℍ(pk_n)}、 {h_0 = H(tx || L_0 || R_0)}を計算する。
  4. {i \in ｛1, ..., n-1｝}について以下の計算をする。
    • {L_i = s_i \cdot G + h_{i-1} \cdot pk_{i, b}}
    • {R_i = s_i \cdot m_i \cdot pk_{i, 1-b} + h_{i-1} /cdot J}
    • {H(tx || L_i || R_i)}
  5. {H(tx || s_0 \cdot G + h_{n-1} \cdot pk_{n, b} || s_0 \cdot m_n \cdot pk_{n, 1-b} + h_{n-1} \cdot J) = h_0}となるような {s_0 = s'_0 - h_{n-1} \cdot sk}を計算する。
  6. 結果、計算した {σ = (s_0, s_1, ..., s_{n-1}, h_0, J, b)}が署名となる。

ホワイトペーパーに合わせたので若干前回のブログと表記は違うが、基本的な署名の仕組みはLSAGと大きく変わっておらず、キーイメージおよび、キーイメージを計算に使っているRの計算式が異なるのと、どの公開鍵によるアンロックなのか示すbが署名に追加される。

DLSAGの署名検証

検証者は以下の手順で検証する。

  1. {i \in ｛1,..., n｝}について以下を計算する。
    • {L_i = s_i \cdot G + h_{i-1} \cdot pk_{i, b}}
    • {R_i = s_i \cdot m_i \cdot pk_{i, 1-b} + h_{i-1} /cdot J}
    • {H(tx || L_i || R_i)}
  2. 算出した {h_n}が {h_0}と一致すれば有効な署名。

これも基本的にLSAGの仕組みと大きく変わらない。

Moneroへの適用について

Dual Outputはもちろん現在のMoneroではサポートされないが、ハードフォークでMoneroに導入可能。現在の署名方式ととDLSAGを組み合わせたトランザクションを構成することが可能で、この混合トランザクションの場合、トランザクションは各インプット毎に通常にLSAGと、Dual-Key形式のDLSAGの署名が含まれる。どちらの形式でも公開鍵の数が異なり、Dual-Keyの場合追加のフィールド（フラグt）がある。このため、コミットメントおよび範囲証明に関する操作や検証についてはDLSAGとなっても互換性が残る。

Fungibility

２種類のアウトプット形式を共存させるとFungibilityが低下する可能性がある。例えばマイナーは選択したアウトプット形式によっては特定のトランザクションのマイニングを拒否するかもしれない。これを軽減するためには、シングルキーの場合も自分の鍵をもう１つ追加してDual-Key形式のトランザクションにするという方法がある。

タイムロック処理の拡張

Dual-Keyタプルにはフラグtが含まれており、このフラグはMoneroではブロック高として実装されると思われる。公開鍵のペア {(pk_0, pk_1)}が与えられた場合、 {pk_0}はブロックtがマイニングされる前に使うことができ、ブロックtがマイニングされた後は {pk_1}で使用できるようになる。

最近の論文に記載されているMoneroへの攻撃において、不明瞭だが、異なるtの値が敵対者にプライバシーを侵害する十分な情報を漏らす可能性がある（例えばtが現在に近い場合リングの１つめの鍵が使われる可能性が高いなど）。このため、この研究では、区別できないタイムアウトを持てるようにするタムロック処理スキームの拡張を提案している。このスキームは、Dual-KeyタプルフォーマットとDLSAG署名スキームの拡張として追加されたもので、MoneroのFungibilityを維持するのに役立つ。

提案されているタイムロック処理スキームは、tを平文のまま含めるのではなく、tの値へのPedersen Commitmentをその範囲証明と一緒に含めるというもの。tが有効期限切れになっていないかは以下のように証明できる。

  1. t < t' < Tとなるようなt'を選択する。Tはトランザクションをマイニングする必要があるブロックの高さ。
  2. 続いて、Pedersen Commitmentの準同型性を利用してコミットメント COM(t' - t) = COM(t') - COM(t)を計算する。
  3. t' - tが[0, 2k]の範囲あることを証明するために、範囲証明 {\Pi_{time}}を計算する。
  4. Pedersenタプル {(COM(t), t', COM(t' - t), \Pi_{time})}はタイムロックtが期限切れになっていないことを証明する。

この仕組みにより、ユーザーはtの実際の値を隠す任意の値t'を選択できる。MoneroはすでにPedersen Commitmentとその範囲証明をサポートしているので、この機能はシームレスにMoneroに追加できる。

以上がDLSAGの大枠。次回はDLSAGを利用してPayment Channel Networkを構成する方法について見ていきたい。