Develop with pleasure!

福岡でCloudとかBlockchainとか。

Bulletproofsを利用したGrinのウォレットのリストア

BitcoinのウォレットであればほぼBIP-32のHDウォレットをサポートしているため、マスターシードさえバックアップしておけば、いつでもウォレットをリストアすることができる。Bitcoinの受け取りに使用するアドレスは全てマスターシードから導出した鍵から作られるためだ。

一方、MimblewimbleのようにPedersen Commitmentにコインをロックしている通貨の場合、ウォレットのリストアはBitcoinほど単純ではない。

基本的にMimblewimbleをサポートしている場合、UTXOは以下のような形式のPedersen Commitmentになる。

Commitment = rG + vH

ここで、ブラインドファクターr秘密鍵に該当し、vがコインの量になる。

rBitcoinと同様マスターシードから導出可能だが、Commitmentはコインの量vを含んでいるため、vの情報が無いとCommitmentを見ただけでは自分が所有するUTXOなのかどうか判断ができない。このCommitmentで使われているブラインドファクターとコインの量、両方分かって初めて判断ができるが、そのためrvの組み合わせを全てバックアップしておくというのは効率がよくない。それだとシードの意味がなく、BIP-32登場以前の全ての秘密鍵をバックアップしておくのと変わらない。

そこでMimblewimbleをサポートしているGrinでは、Commitmentで使用されているrをマスターシードから導出するための導出パスと、コインの量をCommitmentに対応するBulletproofsのrange proofに隠し、ウォレットのリストア時にその情報を復元することでウォレットが自身のUTXOをスキャンできるようにしている。

Bulletproofのrange proofのパラメータ

以前↓でrange proofの生成と証明について書いたけど、

techmedia-think.hatenablog.com

range proofを生成する際、証明者は以下の4つのシークレット値を生成している。

  • alpha:コインの量vのバイナリ表現である {a_L}へのコミットメントAを作成する際に選択するシークレット値(↑ブログ内のα)。
  • rho:range proofでコインの量を秘匿するためのブラインドファクター {s_L, s_R}へのコミットメントSを作成するために選択するシークレット値(↑ブログ内のp)。
  • tau_1:range proof作成時の多項式の次数1の係数 {t_1}へのコミットメント {T_1}を作成する際に選択するシークレット値(↑ブログ内の {\tilde{t_1}})。
  • tau_2:range proof作成時の多項式の次数2の係数 {t_2}へのコミットメント {T_2}を作成する際に選択するシークレット値(↑ブログ内の {\tilde{t_2}})。

そして、これらの値を使ってrange proofを生成する際に、以下のパラメータの計算が行われる。

  •  {mu = alpha + rho*x}(xはランダムチャレンジの値)
  •  {tau_x = tau_2 * x^{2} + tau_1 * x + z^{2}*gamma}(gammaはコミットの秘密鍵で、zはランダムチャレンジ)

このmuは以下のようにmu'置き換えられる。

mu' = mu + flags|path|v

ここで

  • flags: 0|type|switch_commitment_scheme|derivation_depthで構成される4バイトのデータ。
    • 0: 予約データで、今後の拡張の際にインクリメントして使われる。
    • type:ウォレットのタイプを指定(通常、子ウォレット、マルチシグ)
    • switch_commitment_scheme:Switch Commitmentのタイプを指定(0:なし、1:現状のSwitch Commitmentタイプ)
    • derivation_depth:導出パスのレベル
  • path:コインのBFをを導出するための導出パス
  • v:コインの量

そしてmu'と {tau_x}はrange proofに含まれるデータとなる。

Grinでのシークレット値の導出

Grinでは↑の4つのシークレット値(alpha, rho, tau_1, tau_2)を以下の2つのnonceから決定論的に導出している。

  • rewind_nonce = H(H(pub_root_key), commit)
    このrewind_nonceからalphaとrhoを導出する。
  • private_nonce = H(H(root_key), commit)
    private_nonceからtau_1、tau_2を導出する。

つまり、range proofを作成する際のシークレット値を、マスターシードから導出したルート公開鍵、ルート秘密鍵と各UTXOのコミットメントから導出している。

ウォレットのリストア

↑のようにrange proof生成時のシークレット値が決定論的に導出されるため、ウォレットをリストアする際に、マスターシードを復元後、ウォレットはチェーン上の有効なUTXOに対して以下のスキャンを行うことで、そのUTXOが自分が所有するUTXOかどうか識別する。

  1. UTXOのCommitmentに対して、rewind_nonceとprivate_nonceを計算する。
  2. mu = alpha + rho*xを計算する。
  3. proof内のmu'からmuを引いて、flags|path|vの値を導出する。
  4. pathを使って、このCommitmentに使われているブラインドファクターを導出する。
  5. vをこのCommitmenのコインの量とする。
  6. 4,5の値を使ってCommitmentを計算し、それがUTXOの元のCommitmentと一致するか検証する。
    • 一致すればそのUTXOはこのウォレットが所有するUTXO
    • 一致しない場合、そのUTXOは自分とは関係ないUTXO

watch-onlyなウォレットを作りたい場合は、拡張公開鍵(pub_root_key)のみを共有すればいい。この場合4でブラインドファクター自体は導出できないが、ブラインドファクターを秘密鍵とした公開鍵rGはpathを使って導出できるので、その点とvHを加算して、Commitmentを計算すればいい。

というように、Grinではrange proof内にブラインドファクターの導出パスとコインの量を隠すことで、Bitcoinと同じようにマスターシードのみのバックアップでウォレットのリストアができるという仕組みが実装されている。

参考

このあたりの仕様はちゃんとドキュメントに記載されていないので、以下の情報を参考にした。