Develop with pleasure!

福岡でCloudとかBlockchainとか。

異なる楕円曲線間の離散対数の等価性の証明

Bitcoin Monero Cryptography

MoneroからBitcoinとMoneroでAtomic Swapが利用可能になったというアナウンスが出ていて↓

https://www.getmonero.org/2021/08/20/atomic-swaps.html

そのプロトコルの一部で使用されているのが、異なる楕円曲線間の離散対数の等価性の証明。開発をしているのがCOMITというチームで、リポジトリは↓

https://github.com/comit-network/xmr-btc-swap

今回は、Atomic Swapプロトコル全体ではなく、異なる楕円曲線間の離散対数の等価性の証明方法についてみていく。

MoneroでAtomic Swapをする際の課題

チェーンをまたいで資金の交換を可能にするAtomic Swapは、いろんなブロックチェーンで可能になっているけど、MoneroでこのAtomic Swapを行うためには、次の課題がある。

  • スクリプト言語がない
    MoneroにはBitcoin Scriptのようなスクリプトが存在しないので、よくAtomic Swapで使用されているHTLCなどのロジックが利用できない。
  • 楕円曲線の違い
    スクリプトを使用せずにAtomic Swapをする方法の１つとしてAdaptor Signatureを利用したスクリプトレスな方法があり、BitcoinとLitecoin間のAtomic Swapでもこの方法が利用できる。ただ、これは2つのチェーンが同じ楕円曲線を使用している必要があり、Moneroで使用している楕円曲線（ed25519）とBitcoinで使用されている楕円曲線（secp256k1）は異なるため、Adaptor Signatureを利用するのは難しい。

今回のAtomic Swapは、後者のアプローチを可能にするもの。

異なる楕円曲線間のインターオペラビリティ

Adaptor Signatureを利用したAtomic Swapは、２つのチェーンで同じ補助ポイント（公開鍵：T = tG）を使って、その補助ポイントの離散対数（秘密鍵：t）の知識が片方のチェーンのトランザクションが公開されることで判明し、その値を使ってもう一方のチェーンのコインの支払いを可能するという仕組みで機能するようになっている。詳しくは、↓のGBEC動画参照。

goblockchain.network

ただ、これは両方のチェーンが、同じ楕円曲線を使用しているから成立する。そのためBitcoinではsecp256k1、Moneroではed25519のように異なる楕円曲線を採用しているチェーン間では成立しない。これはT = tGという１つの鍵ペアが両方のチェーンにおいて同時に成立することができないため。

この問題に対して、各チェーンの公開鍵XとYがそれぞれ異なるものながら、それが実際には同じ秘密鍵xを利用してできた公開鍵であることを、秘密鍵を明かすことなく証明できればクロースチェーンAtomic Swapができるのではないか？というのが今回BitcoinとMoneroでAtomic Swapを可能にしたアイディア。

※ さすがに秘密鍵の鍵長まで違う曲線だと使えないと思うけど。

異なる楕円曲線間の離散対数の等価性の証明

キーとなるのはsecp256k1とed25519という異なる楕円曲線間で離散対数の等価性（DLEQ）を証明するスキームで、↓のペーパーで発表されている

https://web.getmonero.org/resources/research-lab/pubs/MRL-0010.pdf

表記

詳しいプロトコルの前に、表記を定義↓

  • {\mathbb G}：secp256k1の群
  • {\mathbb H}：curve25519の（部分）群
  • {G, G'}：それぞれ {\mathbb G}のジェネレーター
  • {H, H'}：それぞれ {\mathbb H}のジェネレーター

証明プロトコル

秘密鍵をxとした場合、xGとxHが指す点は異なるが、それらの点の離散対数（x）は同じであることを証明する。ここでxの値は、両楕円曲線で取りうる秘密鍵の数値内であること。

ビットコミットメントの作成

まず、秘密鍵xをビット列に変換する、つまり {x = \sum_{i=0}^{n} b_i 2^{i}}

続いて、n -1個（0〜n-2）のランダムなブラインドファクター {r_i}と {s_i}を生成する。そしてn個（n-1）めのブラインドファクターはそれぞれ、

{r_{n-1} = -(2^{n-1})^{-1} \sum_{i=0}^{n-2} r_i 2^{i}}

{s_{n-1} = -(2^{n-1})^{-1} \sum_{i=0}^{n-2} s_i 2^{i}}

とする。つまり、 {\sum_{i=0}^{n-1} r_i2^{i} = \sum_{i=0}^{n-1}s_i2^{i} = 0}が成立するように、それぞれ最後のブラインドファクターを選択する。

生成したブラインドファクターと秘密鍵の各ビット値を使って以下のビットコミットメントを生成する。

{C^{G}_i = b_iG' + r_iG}（secp256k1用のコミットメント）

{C^{H}_i = b_iH' + s_iH}（ed25519用のコミットメント）

ブラインドファクターrとsについては、↑の関係があるため、各ビットコミットメントの合算値について、 {\sum_{i=0}^{n-1}2^{i} C_i^{G} = xG'}および {\sum^{n-1}_{i=0} 2^{i}C_i^{H} = xH'}が成立する。

リング署名の作成

続いて、ビットコミットメントの各ビット値が0か1であること、そして2つの群において同じ値であることを示すリング署名を作成する。

具体的には、各 {i \in \lbrack 1, n - 1 \rbrack}について、ビット値が0か1かで以下の計算をする。

{b_i = 0}の場合

ランダムな値 {j_i}と {k_i}を選択し、以下を計算する。

{e^{G}_{1, i} = H_{\mathbb G}(C^{G}_i, C^{H}_i, j_iG, k_iH)}

{e^{H}_{1, i} = H_{\mathbb H}(C^{G}_i, C^{H}_i, j_iG, k_iH)}

続いて、ランダム値 {a_{0, i}}と {b_{0, i}}を選択し、以下を計算する。

{e^{G}_{0, i} = H_{\mathbb G}(C^{G}_i, C^{H}_i, a_{0, i}G - e^{G}_{1, i}(C^{G}_i - G'), b_{0, i}H - e^{H}_{1, i}(C^{H}_i - H'))}

{e^{H}_{0, i} = H_{\mathbb H}(C^{G}_i, C^{H}_i, a_{0, i}G - e^{G}_{1, i}(C^{G}_i - G'), b_{0, i}H - e^{H}_{1, i}(C^{H}_i - H'))}

そして以下を定義する。

{a_{1, i} = j_i + e^{G}_{0, i} r_i}

{b_{1, i} = k_i + e^{H}_{0, i} s_i}

{b_i = 1}の場合

ランダムな値 {j_i}と {k_i}を選択し、以下を計算する。

{e^{G}_{0, i} = H_{\mathbb G}(C^{G}_i, C^{H}_i, j_iG, k_iH)}

{e^{H}_{0, i} = H_{\mathbb H}(C^{G}_i, C^{H}_i, j_iG, k_iH)}

続いて、ランダム値 {a_{1, i}}と {b_{1, i}}を選択し、以下を計算する。

{e^{G}_{1, i} = H_{\mathbb G}(C^{G}_i, C^{H}_i, a_{1, i}G - e^{G}_{0, i}C^{G}_i, b_{1, i}H - e^{H}_{0, i}C^{H}_i)}

{e^{H}_{1, i} = H_{\mathbb H}(C^{G}_i, C^{H}_i, a_{1, i}G - e^{G}_{0, i}C^{G}_i, b_{1, i}H - e^{H}_{0, i}C^{H}_i)}

そして以下を定義する。

{a_{0, i} = j_i + e^{G}_{1, i} r_i}

{b_{0, i} = k_i + e^{H}_{1, i} s_i}

そうして計算した以下のタプルがプルーフになる。

{(xG', xH', \lbrace C^{G}_i \rbrace, \lbrace C^{H}_i \rbrace, \lbrace e^{G}_{0, i} \rbrace, \lbrace e^{H}_{0, i} \rbrace, \lbrace a_{0, i} \rbrace, \lbrace a_{1, i} \rbrace, \lbrace b_{0, i} \rbrace, \lbrace b_{1, i} \rbrace)}

検証プロトコル

プルーフ {(xG', xH', \lbrace C^{G}_i \rbrace, \lbrace C^{H}_i \rbrace, \lbrace e^{G}_{0, i} \rbrace, \lbrace e^{H}_{0, i} \rbrace, \lbrace a_{0, i} \rbrace, \lbrace a_{1, i} \rbrace, \lbrace b_{0, i} \rbrace, \lbrace b_{1, i} \rbrace)}が与えられたら、以下の検証を行う。

まず、ビットコミットメントが両曲線の離散対数へコミットしているか以下を確認する。

{\sum_{i=0}^{n-1} 2^{i} C^{G}_i = xG'}

{\sum_{i=0}^{n-1} 2^{i} C^{H}_i = xH'}

続いて、各 {i \in \lbrack 1, n - 1 \rbrack}について、以下の計算を行う：

{e^{G}_{1, i} = H_{\mathbb G}(C^{G}_i, C^{H}_i, a_{1, i}G - e^{G}_{0, i} C^{G}_i, b_{1, i}H - e^{H}_{0, i} C^{H}_i)}

{e^{H}_{1, i} = H_{\mathbb H}(C^{G}_i, C^{H}_i, a_{1, i}G - e^{G}_{0, i} C^{G}_i, b_{1, i}H - e^{H}_{0, i} C^{H}_i)}

{(e^{G}_{0, i})' = H_{\mathbb G}(C^{G}_i, C^{H}_i, a_{0, i}G - e^{G}_{1, i} (C^{G}_i - G'), b_{0, i}H - e^{H}_{1, i} (C^{H}_i - H'))}

{(e^{H}_{0, i})' = H_{\mathbb H}(C^{G}_i, C^{H}_i, a_{0, i}G - e^{G}_{1, i} (C^{G}_i - G'), b_{0, i}H - e^{H}_{1, i} (C^{H}_i - H'))}

そして、 {(e^{G}_{0, i})'}と {(e^{H}_{0, i})' }が、プルーフの {e^{G}_{0, i}}と {e^{H}_{0, i} }それぞれ等しく、プルーフのデータが各群の要素であれば検証は成功する。

証明の仕組み

ぱっと↑の証明と検証をみても何をやってるのか分からないけど、基本的な仕組みはMoneroで最初に導入されていたリング署名スキーム（LSAG）↓を拡張した構造になってるっぽい。

techmedia-think.hatenablog.com

この場合のリングは２つで、ブラインドファクターを秘密鍵として、各ビットコミットメントが0か1へのコミットメントであることを確認するスキームになってるみたい。

COMITのスキーム

今回、Bitcoin - Monero間のAtomic Swapを行うソフトウェアを提供しているCOMITでは、↑のSarang Noetherのペーパーのプロトコルをそのまま使っているのではなく、簡略化して安全性を証明したものを使用してるっぽい。ただ、具体的なプロトコルの説明が見つけられなかった。