Develop with pleasure!

福岡でCloudとかBlockchainとか。

MimblewimbleとGrinのトランザクションフロー

Grinのトランザクショントランザクションフローを見てたら、オリジナルのMimblewimbleと署名プロセスが少し変わってたのでまとめてみた。

Mimblewimbleの基本機能

Pedersen Commitment

Gregory Maxwellが提案したConfidential Transactionで導入されたコインの量を秘匿する機能。コインの量をBitcoinのような整数値ではなく、以下のような準同型性のコミットメントとして管理することで取引の当事者以外はコインの量を知り得なくする仕組み。

Commitment = r * G + v * H

GHは同じ楕円曲線上の異なる生成点。rブランディングファクターで、vがコインの量。トランザクションのアウトプットは全てこのコミットメント持つ。MimblewimbleではConfidential Transactionを単純に量の秘匿に使うだけでなく、scriptPubkeyも無くしこのコミットメントに集約している(ブランディングファクターが秘密鍵の役割を果たす。後述)。

Confidential Transactionの仕組みの詳細については先日GBECで解説したスライド参照↓

www.youtube.com

Mimblewimbleのトランザクション

Mimblewimbleでは、Bitcoinのように各インプット毎にそれぞれ署名があるわけではなく、トランザクション毎に1つの署名が作られる。その際、署名に使用する秘密鍵は↑のPedersen Commitmentのブラインディングファクターの総計から作られる。

この辺が躓きがちなポイントなんだけど、Bitcoinの場合、アウトプットはコインの量を持つvalueとそのコインのロックスクリプトであるscriptPubkeyとセットで管理されているが、Mimblewimbleの場合は上述したようにscriptPubkeyのようなロックスクリプトはなく、上記のPedersen Commitmentのみが存在する。それ以外に、コインをロックするような公開鍵の情報などがセットされているわけではない。その状態でどうやってコインを取引するための署名を作るのか疑問に思うが、以下の手順で署名は作られる。

例えば、アリスが以下の2つのコミットメントを持っているとする。

  • c1 = 35G + 4H
  • c2 = 93G + 6H

それぞれブラインディングファクターが3593、コインの量が46で2つ合わせて10コイン持ってることになる。

この状態で、上記2つのコミットメントを使ってアリスからボブに7コイン送る場合、以下のような手順でトランザクションを構成することになる。手数料は1コインとする。

  1. アリスはお釣り用のコミットメントで使用するブラインディングファクターをランラムに選択する。これを47とする(※実際のブラインディングファクターはもっと巨大な値)。
  2. アリスはお釣り用のコミットメント c3 = 47G + 2H を作成する。
  3. アリスは自身が管理するブラインディングファクターの差分(インプットの全ブラインディングファクターからアウトプットの全ブラインディングファクターを差し引いたもの)を計算する。
    47 - (35 + 93) = −81
  4. アリスはトランザクションの雛形とブランディングファクターの総計(-81)をボブに送る。
  5. ボブはブラインディングファクターをランダムに選択する。これを153とする。
  6. ボブは選択したブラインディングファクターを使って、7コンを受け取るコミットメント c4 = 153G + 7H を作成する。
  7. ボブはアリスから受け取ったブランディングファクターの総計に自身のブランディングファクターを加味し、ブランディングファクターの超過値(excess)を算出する。
    153 - 81 = 72
  8. ボブは超過値(72)を秘密鍵として署名を生成しブロードキャストする。
  9. ネットワークのノードはトランザクションの全インプットとアウトプットのコミットメントを相殺して残った楕円曲線上の点=公開鍵(今回の場合は72 * G)に対して有効な署名があるか検証する。
    この時、有効な署名が作成できるということは、コミットメントの内、ブラインディングファクターについてはexcessが存在するが、コインの量についてはアウトプット−インプットで0Hになるということの証明にもなる。

というように、送信者のブラインディングファクターの総計を受け取った受信者が、自身が選択したブラインディングファクターを加味して受信者のみが知りうるexcessを秘密鍵としてしている。Bitcoinの場合はインプットの所有者=送信者が署名を作成するが、Mimblewimbleの場合は受信者が署名を作成することになる。

Mimblewimbleのトランザクションはインプットとアウトプットの他にトランザクションカーネルと呼ばれるデータを持ち、トランザクションカーネルは、

  • 手数料
  • 超過値(excess)
  • excessを使って作成した署名
  • lock_height

を持つ。署名は個々のCommitmentに対して存在するのではなく、トランザクション単位で有効になる。

Grinのトランザクション

GrinはMimblewimbleを実装したブロックチェーンだが、署名手順はMimblewimbleとは多少異なる。オリジナルのMimblewimbleの投稿では、送信者が自身に関連するブラインディングファクターの総計をそのまま受信者に渡すことで、受信者のみがexcess値を知り、それを使って署名を作成していたが、Grinの場合送信者はブラインディングファクターの総計をそのまま渡すのではなく、楕円曲線のベースポイントGに乗算して公開鍵として渡すようになっている。この場合、受信者は自身の受け取り用のアウトプットのコミットメントを作成し、そのブラインディングファクターを加味することで、excess * Gを算出することはできるが、その秘密鍵であるexcessの値を知ることはできない。そのため送信者と受信者は協力し、お互いが知るブラインディングファクターの情報から署名をそれぞれ作り、その署名を集約することでexcess * Gに対して有効な署名を完成させるというアプローチを採っている。

この時作成される署名は、集約特性のあるSchnorr署名が使われる。

Schnorr署名

秘密鍵x秘密鍵に対応する公開鍵をP = x * G、メッセージをMとする。尚、Bitcoinではトランザクションに署名をする際、署名対象のメッセージMトランザクションの各データ(バージョン、locktime、インプット、アウトプットなど)から生成されるが、Grin場合はトランザクションの手数料とlock heightの2つの要素で構成される。

GrinのSchnorr署名の作成手順は以下のとおり。

  1. ランダムにnonce値kを選択する。
  2. R = k * Gを計算する。
  3. e = SHA256(M | R | P)を計算する。
  4. s = k + e * xを計算する。
  5. 算出した(R, s)のペアが署名データ

そして署名の検証は、s * Gs * G = R + ePを満たすか検証する。

Grinの署名手順

Grinの詳細なトランザクションフローは↓にまとめられている。

https://raw.githubusercontent.com/mimblewimble/grin-wallet/master/doc/transaction/basic-transaction-wf.png

送信者は送金にあたって以下の作業をする(内部的な実装の手順は省略)。

  1. トランザクションカーネルに現在のチェーンの高さでlock_heightをセットする。
  2. インプットにするコミットメントを選択する。
  3. インプットのブラインディングファクターの合計x1を計算する。
  4. お釣り用のアウトプット用のブラインディングファクターxCを選択し、お釣り用のアウトプット(コミットメント)を作成する。
  5. トランザクション手数料を計算する。
  6. 全インプットとアウトプットから超過合計xS1 = xC - x1を計算する。
  7. ランダムなnonce値kSを選択する。
  8. xS1からランダムなカーネルオフセットoSを減算した、xS = xS1 - oSを計算する。
  9. 送信者側のブラインディングファクターの総計xSと署名に必要なnonceの値kSをGに乗算して、曲線上の点xS * GkS * Gを計算する。
  10. 相手インプット、アウトプットのコミット、手数料、lock_height、xS * GkS * Gを送る。

受信者は、送信者から受け取った情報を元に以下の作業をする。

  1. 受信用のブラインディングファクターxRを選択し、 受信用のアウトプット(コミットメント)を作成する。。
  2. 署名に用いるメッセージM= fee | lock_heightを作成する。
  3. 署名に使用するランダムなnonce値kRを選択する。
  4. xRとkRをそれぞれGに乗算して、曲線上の点xR * GkR * Gを計算。
  5. Schnorr署名用のチャレンジ e = SHA256(kR * G + kS * G | xR * G + xS * G | M)を計算
  6. 受信者側のSchnorr署名 sR = kR + e*xRを計算する。
  7. 送信者に受信者が計算した部分署名値sRと、xR * G, kR * Gを送る。

送信者は、受信者から受け取った情報を元に署名を完成させトランザクションをブロードキャストする。

  1. 署名に用いるメッセージM= fee | lock_heightを作成する。
  2. Schnorr署名用のチャレンジ e = SHA256(kR * G + kS * G | xR * G + xS * G | M)を計算
  3. 受信者から送られた部分署名であるsRについて、sR * G = kR * G + e * xR * Gが成立するか検証する。
  4. 送信者側のSchnorr署名 sS = kS + e * xS を計算する。
  5. Schnorr署名を完成させる。Schnorr署名のRの値はkS * G + kR * G、sの値はsR + sS
  6. sの値が公開鍵x*G = xS * G + xR * Gに対して有効な署名か検証する。

トランザクションに署名する際の秘密鍵は基本的にMimblewimbleのexcessの値であり、上記のケースであればexcess = xR + xS。このexcess値をお互い知ること無く、協力してSchnorr署名のsの値sR + sS = kR + kS + e * (xR + xS)を計算している。

↑のようにGrinの場合は、Mimblewimbleのオジリナルの投稿とは異なり、送信者と受信者が協力して署名を作成するようになってる。単純にexcess値をそのまま渡すより安全であるというのと、署名のメッセージにlock_heightが含まれることから送信者と受信者の両者がロックタイムに合意するという意味もあるのかもしれない。