未使用のUTXOを所有していることをUTXOを明らかにせず証明するプロトコルPoDLE

BitcoinトランザクションのプライバシーやFungibilityの向上のためCoinJoinを実装しているJoinmarketで提案されているPoDLEというプロトコルが面白かったので見てみる↓

joinmarket.me

PoDLEプロトコル

PoDLEが解決するのは、自分があるUTXOを所有していて、別のユーザーにそのUTXOを所有しておりかつ未使用であることをUTXO自体を公開することなく証明したいという問題。

暗号コミットメントを使ったアプローチ

こういう問題への対応としてよく上げられるのが暗号コミットメントの利用。UTXOの情報とランダムに選択したnonceを使って

commitment = hash(UTXO || nonce)

を作成する。そしてプロトコルの後半でUTXOをnonceを明らかにすることで、commitmentを解くというもの。

UTXOだけでなくnonceを必要とするのは、例えば証明したいデータのセットが小さい場合、相手がどのUTXOか特定することが可能になるため。BitcoinのUTXOセットは有限で誰もが知っている情報なので、UTXOのみでcommitmentを作成すると、それがどのUTXOのものなのか計算できてしまう。

一方、nonceを加えた場合はまた別の問題が生じる。アリスがあるUTXO Aをcommitmentを作成し、それをボブとキャロルに渡す場合。UTXO Aはどちらか１人にしか使えないが、UTXO Aは同じままnonceだけ違う値を使って異なるcommitmentを作り両者に渡してしまうことが可能になる。

そのため単純なコミットメントスキームでは上記の問題を解決できない。

離散対数の等価性の証明を使ったアプローチ

そしてGreg Maxwellによって提案されたのが離散対数の等価性を証明するという方法。

まず楕円曲線のベースポイントGに加えてもう１つ別のNUMSポイント（誰もGに対してその点の離散対数を知らない点）Jを用意する。

1. アリスが所有しているUTXOに使われている公開鍵をとした場合、アリスは同じ秘密鍵xとJを使ってもう１つの点を計算する。
2. アリスはを使ってコミットメントを作成し、提供する。
3. 公開された使用済みの情報にCが存在しないければCが未使用であることが確認できるので、ボブはアリスに対してプロトコルを継続する。
4. アリスはランダムなnonce kを選択し、以下の計算を行う。
   • 
   • 
   • 
   • 
5. アリスは上記で計算したをボブに明らかにする。
6. ボブは受け取ったデータに対して以下の検証を行う。
   • 以前アリスから受け取ったCがと等しいかどうか。
   • チェーン上のUTXOにで構成されるUTXOがあるかどうか。
   • Schnorr署名が有効な署名かどうか
     • 
     • 
     • 

このプロトコルの特徴として、

• アリスが事前に公開するcommitmentのプリイメージはと同じ秘密鍵を使っているもののBitcoinのUTXOセットには存在しないので、nonce抜きにハッシュしたデータを共有してもアリスのUTXOがそれによって特定されることはない。
• Schnorr署名の検証により、UTXOを所有していることが確認できる。
• 同じ公開鍵から以外の異なるコミットメントを作成する（別の秘密鍵の公開鍵を作ってコミットメントとする）ことができない。これをすると最後の署名検証が失敗する。

↑のプロトコルでは２つめのベースポイントJについてJ = zGとなるような離散対数zを誰も知らない点であることが重要。

以上がPoDLEプロトコルの仕組み。

Joinmarketでの活用

JoinmarketではCoinJoinプロトコルを実行するにあたって、悪意あるユーザーがプロトコルを途中で止めることで、相手のUTXOセットの情報を学習し、最終的にチェーン上のミキシングトランザクションをアンミックスすることを可能にする攻撃が懸念されていた。

これに対応するために↑のPoDLEプロトコルを組み入れている。

1. ユーザー（マロリー）は、ミキシングのセッションを開始する前に、PoDLEプロトコルにしたがって自身のUTXOのコミットメントをJoinmarketのネットワークで公開する必要がある。
2. 別の参加者（ボブ）とその特定のUTXOを使用してCoinJoinを始めると、マロリーは同じコミットメントのUTXOを使って他のユーザーとはプロトコルを実行できなくなる。
3. ボブがマロリーにコミットメントのオープンを依頼すると、マロリーはUTXOの情報を明らかにする。
4. ボブはマロリーから受け取ったUTXOが事前に公開されていたコミットメントと一致すれば、自身のUTXOを開示しCoinJoinプロトコルを継続する。

マロリーが悪意あるユーザーであった場合、4でボブのUTXOセットを学習し、それ以降のプロセスを中止できる。ただ、同じUTXOを使って別のユーザーと同じことはできない。そのため、別のユーザーのUTXOセットを学習したい場合、UTXOを使用して別のUTXOにする必要がある。これにはコストが発生するので、こういうスパイ行為に対してコスト面での負担を強いるようにしているというわけみたい。

Lightning NetworkのFundingでも活用？

LNでは、現在Funding Txはチャネル参加者のどちらか一方の資金をファンドするようになっているが、これを両者の資金をファンドできるようDual Fundingをサポートしようという議論が進んでいる。

Dual Fundingの場合、両者がそれぞれUTXOを提供することになるが、この調整をする際に、↑のJoinmarketの悪意あるユーザーのようにプロトコルを途中で停止し、相手のUTXOセットを学習することでLNユーザー管理下のUTXO情報がリークされる可能性がある。これに対して、PoDLEのようなプロトコルを導入し、途中で停止した場合、UTXOやPoDLEのデータをゴシップすることでスパイ行為への対応としようという議論もある。

離散対数の等価性の証明は他にも適用可能なユースケースがあるかもなー。