Develop with pleasure!

福岡でCloudとかBlockchainとか。

Bulletproofのrange proofに任意のデータを埋め込む方法と復元する(rewind)方法

先日、Grinがウォレットリストアの際に自身のUTXOを識別するのにBulletproofsのrange proofにヒントを隠している記事を書いたけど、↓

techmedia-think.hatenablog.com

今回の記事では、リストアという限定的な利用方法だけでなく任意のデータをrange proofに埋め込む方法としてまとめてみる。

range proof生成時のメッセージの埋め込み

Grin自体はRustで実装されているが、range proofの生成や検証はlibsecp256k1にBulletproofの拡張を加えたsecp256k1-zkpを使っている。range proofの生成処理はこちら

埋め込み可能なメッセージは今のところ20バイトなので、RIPEMD160とかのハッシュ値とかが向いてる。

関係するところだけ抜き出すと、

  1. 生成者はnonceを生成する。
  2. chacha20ストリーム暗号を使ってnonceから、シークレット値alpharhoを生成する。
  3. コミットメントのvalue値を32バイトのバイト列に変換する。ここでvalue値が取る範囲は8バイトなので、上位24バイトは空いている状態になる。
  4. 3のバイト列の[4〜23]バイト列に20バイトのメッセージを埋め込む。
  5. 4のバイト列をスカラー値に変換する。この値をvalsとする。
  6. mu = alpha - vals + rho * x を計算する。
  7. -mu を計算し、range proofにセットする。

上記のように、muを計算する要素の中にメッセージを組み込んでいる。実は↑のウォレットのリストアの際に使っている付加情報(flags|path)は、このメッセージとして埋め込まれている。

proofからメッセージの復元

↑の生成時に使われたnonceを知っていれば、proofからメッセージを復元できる。この復元処理の実装はこちら

  1. nonceからchacha20ストリーム暗号を使ってnonceから、シークレット値alpharhoを生成する。
  2. proofには-muがセットされているので、-mu + alpha + rho * x = valsを計算する。
  3. vals[4-23]がメッセージとなる。

とメッセージが復元できる。これはproof生成時に使用したalpharhoの知識があるため復元できるが、その知識がない場合、メッセージは復元できない。

ウォレットのリストアの記事↑も基本的にはこの仕組みを利用したもの。

非対話型トランザクション作成

ウォレットのリストア以外にもrange proofにデータを埋め込むことで可能になるプロトコルもある。Grinで提案されているMimblewimbleで非対話でトランザクションを作成するためのプロトコル案もそのうちの1つだ。

Mimblewimbleで送金トランザクションを作成する際は、トランザクションカーネルに有効な署名をセットするため、送信者と受信者が協力する必要がある。具体的な仕組みについてはGBECでの解説動画参照↓

goblockchain.network

有効なSchnorr署名を作成するには送信者と受信者両方のブラインドファクターの知識が必要となるため、Mimblewimbleでは非対話型のトランザクションを作るのは難しいとされてきたが、これをDiffie-Hellmanの鍵共有を活用して非対話型にしようという提案が最近出てきた↓

https://gist.github.com/DavidBurkett/32e33835b03f9101666690b7d6185203

仕組みは簡単で、

  1. 送信者が一時鍵ペアを生成する。
  2. 送信者は自身の秘密鍵と受信者の公開鍵とでECDHを実行し共有シークレットを生成する。この共有シークレットは受信者が受け取るコイン=コミットメントのブラインドファクターになる。
  3. 送信者は送信トランザクションを作成し、受信者のアウトプットをセットし、有効な署名を生成しトランザクションカーネルにセットする。

これで有効なトランザクションができるので後はブロードキャストするだけ。ベースの仕組みはステルスアドレスなんかでも使われているよくある仕組みだ。

この手順で問題になるのが、

  • 受信者がブラインドファクターを知るためには、送信者がECDHを実行する際に使用した鍵ペアの公開鍵を知る必要がある。
  • 送信者が受信者のコミットメントのブラインドファクターを知ってしまっている。

という2点。

前者はともかく、後者はコインを送ってもらってもブラインドファクターを送信者が知ってしまっている状態では、そのコインを元の送信者も利用可能な状態になってしまうのでまずい。

コンセンサスルールの変更

↑の2つの問題に対応するため、以下のコンセンサスルールを追加する。

  • 各アウトプットはコミットメントの他にoutput_dataを含むようになる。このoutput_dataには以下が含まれる。
    • 送信者の一時公開鍵(送信者の公開鍵を含めることで受信者はECDHにより共有鍵を生成でき暗号化されたデータを復号することができる)
    • 受信者の公開鍵
    • 暗号化されたデータ。以下の2つのデータがECDHの共有鍵で暗号化されている。
      • アウトプットのコインの量
      • アウトプットのブラインドファクター
  • 各ノードはコミットメントと一緒にoutput_dataを保存する。
  • output_dataを持つコミットメントを使用する場合、トランザクションのインプットにはそのコミットメントと一緒に、output_dataの受信者の公開鍵に対して有効な署名がセットされなければならない。このルールにより送信者と受信者の両者がコインの所有権を持つことを回避する。

range proofの利用

↑ルールにより、2つの問題は解消する。ただ、このルールだけではまだ十分ではない。各アウトプットには現状Commitmentとrange proofがあるが、これにoutput_dataを単純に加えただけでは、このデータはどこにもコミットされていないので、output_dataだけ改竄して別のデータにしてしまうことができてしまう(Bitcoinの場合と違って、Grinの場合、署名対象のメッセージはトランザクションカーネルのデータから作られるため)。

この問題に対処するために、追加のデータ(output_data)にコミットするのに↑のrange proofを使う。このユースケースでは、nonceは既知のデータとして扱われる。

プルーフの生成者は、

  • nonceをblake2b(Commitment)として計算し、
  • output_dataハッシュ値ripemd160(blake2b(output_data))として計算し、これをメッセージとして↑のnonceを使ってrange proofに埋め込む。

その上で、以下のルールをコンセンサスルールにさらに追加する。

  • Commitmentからnonce = blake2b(Commitment)を計算する。
  • 計算したnonceを元にrange proof内のメッセージを復元し、その20バイトの値が、アウトプットのripemd160(blake2b(output_data))と一致するか検証する。

上記の仕組みを追加することで、output_dataを変更できなくすることができる。ただ↑の計算ができると取引量も計算できるようになるので、muの計算にvalue値は含めずにoutput_data内のもののみとする必要があるんじゃないかと思う。

↑はあくまでまだ提案の段階なので実際にどうなるかはまだ不明。特定のrange proofの実装に依存しない方が良いのでトランザクションカーネルを利用する提案もある。個人的には量がCommitment以外に暗号化された状態でセットされるようになるので、将来AESの暗号仮定が崩れた場合にCommitmentだけであれば過去含め取引量は不明なままだったのに、暗号化されたデータであれば復号化されてしまうと過去の取引量も分かってしまうのが微妙に思う。