Develop with pleasure!

福岡でCloudとかBlockchainとか。

Schnorrの代わりにECDSAを使って実現するTaproot

Bitcoin Ruby ECDSA Taproot

techmedia-think.hatenablog.com

のECDSAの署名スキームを利用すると、

techmedia-think.hatenablog.com

コインのアンロック条件が、2-of-2のマルチシグ or その他の条件で構成されるTaprootをSchnorrを使わずにECDSAで実現できるのでは？と思い、プロトコルを考えてみた。

Taprootについて

Taprootの仕組みについてや↑の記事に書いたけど、基本的なコンセプトは、コインのアンロック条件がマルチシグ or 他の条件スクリプトで構成される場合、そのロックスクリプトをP2SHのようなスクリプトとして実現するのではなく、1つの公開鍵にして、ロックスクリプトの段階では、マルチシグやその他の条件の存在を隠すことができるというもの。

例えば以下のスクリプトは、アンロック条件が以下のいずれかになる。

  • アリスとボブの2人の署名があればアンロック可能
  • ロック時間経過したらボブの署名のみでアンロック可能
OP_IF
  2 <A> <B> 2 OP_CHECKMULTISIG
OP_ELSE
  <ロック時間> OP_CSV OP_DROP <B> OP_CHECKSIG
OP_END

通常こういった条件はスクリプトにしてP2SHにするが、Taprootの場合

  1. アリスの公開鍵とボブの公開鍵を集約した新しい公開鍵Cを作成する。
  2. その他の条件部分のスクリプトをS =<ロック時間> OP_CSV OP_DROP <B> OP_CHECKSIGとする。
  3. CとSを使って新しい公開鍵（楕円曲線上の点）P = C + H(C || S)Gを計算する。（Hはハッシュ関数で||は連結）
  4. scriptPubkey <taproot version> P宛にコインを送金する。

といった手順でロックスクリプトを構築しそこに送金する。

アンロックする方法は以下の2通りの方法がある。

アリスとボブの署名を使ってアンロックする場合

この場合、Pの公開鍵に対して有効な署名が提供すれば良い。Pはアリスとボブの公開鍵を集約して作った点Cに点H(C || S)Gを加算した点なので、アリスとボブの秘密鍵とH(C||S)を使ってSchnorr署名を作ればいい。

その他の条件（タイムロックされたスクリプト）を使ってアンロックする場合

この場合、CとSを明らかにして（スタックにプッシュして）、そこからPが計算できれば、Sのスクリプトを使ってコインをアンロックできるようになる。後はSの条件を満たす要素をスタックにプッシュしておけば良い。

ECDSAを使ったTaproot

Schnorrを使わずにECDSAを使って↑のTaprootを構築する場合、まずマルチシグを構成する公開鍵Cは、アリスの鍵ペアをP1 = x1 G、ボブの鍵ペアをP2 = x2 Gとし、両者それぞれ公開鍵P1、P2を相手に伝えている前提で、以下のようにCを求める。

  • アリスが算出する場合は、C = x1 * P2
  • ボブが算出する場合は、C = x2 * P1

こうやって計算したCは同じ楕円曲線上の点を指し、このCに対して有効な署名を作るには、アリスの秘密鍵x1とボブの秘密鍵x2を使った計算が必要になる。

この仕組み自体はYehuda Lindellが発表したプロトコルそのもの。

Cを算出したら、残りのロックスクリプトの作り方は↑のTaprootの作り方そのままで、スクリプトSとCを使ってP = C + H(C || S)Gを計算し、コインをロックする。

コインのアンロック方法

２つあるコインのアンロック方法の内、その他の条件（タイムロックされたスクリプト）を使ってコインをアンロックする場合、これも↑のTaprootと同じでOK。

マルチシグを使ってコインをアンロックする場合は、Yehuda Lindellのプロトコル↓

techmedia-think.hatenablog.com

に少し変更を加え、以下のようなプロトコルにする。

アリスとボブは上記の鍵ペアに加え、ランダムに選択したnonce （アリスは {R_1 = k1G}、ボブは {R_2 = k2G}）をそれぞれ持つ。最後にアリスはボブにckey = Enc {pk_A} (x1)を提供する。これはアリスのみが解読可能なx1のPaillier暗号。

  1. アリスとボブは、P1、P2、R1、R2とm'について合意する。ここでm'はLSB(H(m))。また、アリスとボブは安全のためP1、P2、R1、R2についてその秘密鍵を確かに持っていことを証明するための非対話型のゼロ知識を追加で交換する必要がある。
  2. アリスは {R \gets k_1 R_2}を計算し、ボブは {R \gets k_2 R_1}を計算する。それぞれ計算したRから同じx座標 {r = r_x}を計算することができる。
  3. ボブは {c_1 \gets Enc_{pk_A}(k_2^{-1} \cdot m' + \rho q)}と {c_2 = ckey \odot (x_2 \cdot r \cdot k_2^{-1}) \oplus (H(C || S) \cdot r \cdot k_2^{-1})}を計算する。ここで {\rho}は巨大な乱数を表し、qは暗号操作中に使用される剰余を表す。続いてボブは {c_3 = c_1 \oplus c_2}を計算する。この {\oplus}はPaillier暗号の加法準同型演算を表す。 こうやって計算した {c_3}は、
{c_3 = Enc_{pk_A} (k_2^{-1} \cdot m' + \rho q + (x_1 \cdot x_2 + H( C || S )) \cdot r \cdot k_2^{-1})}

となる。これをアリスに送る。

4.アリスは {c_3}を復号して、s'を得る。続いて {s \gets s' \cdot (k_1)^{-1}}を計算し、(r, s)をECDSA署名のアウトプットとする。

こうやってできたsは

{s = (k1 \cdot k2)^{-1} \cdot (m' + (x1 \cdot x2 + H(C || S)) \cdot r)}

となり、Taprootのコインのロック先Pに対して有効な署名になる。

Yehuda Lindellのプロトコルとの変更点は、ボブが {c_2}を計算する際に、 {(H(C || S) \cdot r) \cdot (k_2)^{-1}}を余計に加算している点で、これによりCではなくPに対して有効な署名を作成する。

実際に検証したコードが（bitcoinrbとpaillierのgemが必要）↓

gist.github.com

ECDSAの場合Schnorrのように鍵や署名自体に集約特性があるわけではなく、署名を構成するスキームを利用したアプローチなので、いずれにせよSchonrr導入のメリットは大きいと思うが、まぁECDSAでもできるんじゃない？と思い書いてみた。ちなみに同様のことをGraftrootで実現する場合は、Yehuda Lindellのプロトコルそのままでできるはず。