Develop with pleasure!

福岡でCloudとかBlockchainとか。

ECDSA版Adaptor Signatureを書いてみた

ECDSA版 Scriptless ScriptsのベースになっているECDSAの署名スキーム

techmedia-think.hatenablog.com

と、それを利用したマルチシグの実装方法

techmedia-think.hatenablog.com

について理解したので、続いてECDSAをベースにしたAdaptor Signatureの作り方について見てみる。

https://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180426/fe978423/attachment-0001.pdf

ECDSAを使ったAdaptor Signature

Adaptor Signatureのコンセプトは、ある秘密の値を知っているボブが取引相手のアリスに対し、秘密の値の知識をアリスが得た場合にのみ有効な署名を作成できる仕組みを提供するものだ。元々Andrew PoelstraがSchnorro署名を使って実現する仕組みとして紹介された。このAdaptor Signatureの仕組みを利用するとスクリプトコントラクトを構成することなく、コインのAtomic Swapなどが可能になる。実際にSchnorrベースのScriptless ScriptsでAtomic Swapするプロトコルが↓

techmedia-think.hatenablog.com

今回は、これをECDSAを使って実現する仕組みについて理解する。

まず前提としてLindellのECDSA版のスクリプトレスなマルチシグの場合と同様、アリスは公開鍵P1=gx1とナンスから生成した点R1=gr1を、ボブは公開鍵P2=gx2とナンスR2=gr2をそれぞれ持ち、最後にアリスはボブに {ckey = Enc_{pkA} (x1)}(アリスのみが解読可能なx1のPaillier暗号)を提供する。

これに加えてボブは秘密の値αを作成し、αに対する {g^{α}}(αを秘密鍵とした際の公開鍵)をアリスに共有する。

ホワイトペーパーに記載されている、こららを使ったAdaptor Signatureを構成するプロコトルの動作が↓

  1. アリスとボブはP1, P2, R1, R2, m'について同意し、 {Q = g^{x1 \cdot x2}}を計算する。
  2. ボブはr2とαを明らかにすることなく、 {R_3 = (g^{α})^{r2}} {R_2 = g^{r2} \wedge R_3 = (g^{α})^{r2}}のゼロ知識証明と一緒にアリスに送る。
  3. アリスは {R \gets (R_3)^{r1}}を計算し、ボブは {R \gets (R_1)^{r2 \cdot α}}を計算する。両者が計算したRは同じ値なので、そのx座標 {r = r_x}を抽出する。
  4. ボブは {c_1 \gets Enc_{pk_A}((k2)^{-1} \cdot m' + \rho q)} {c_2 = (ckey)^{x2 \cdot r \cdot (k2)^{-1}}}を計算する。続いて {c_3 = c_1 \oplus c_2}を計算する。この {\oplus}はPaillier暗号の加法準同型演算を表す。すなわち {c_3 = EncpkA((k2)^{-1} \cdot m' + \rho q + x1 \cdot x2 \cdot r \cdot (k2)^{-1})}。計算した {c_3}をアリスに送る。
  5. アリスは {c_3}を復号し、s'を入手する。ここでボブが暗号化の実行中に不正行為をしていないか確認する必要がある。これは、 {(R_2)^{s' mod q} = Q^{r} \cdot g^{m'}}が成立するか検証すればいい。問題なければ、 {s'' \gets s' \cdot (k1)^{-1}}を計算しs''をボブに送る。
  6. ボブは {s \gets (α)^{-1} \cdot s''}を計算し、そのアウトプットが署名(r, s)になる。
  7. ボブが作成した署名が公開されると、アリスは {α \gets (s \cdot (s'')^{-1})^{-1}}を計算する。

ポイント

スクリプトレスなマルチシグの場合、ECDSA署名に使用するRの計算は、アリスとボブがそれぞれ選択したnonce(r1r2)から計算した点R1R2から算出 {R = (R_2)^{r1} = (R_1)^{r2} }していたけど、Adaptor Signatureの場合、秘密の値αを知っているボブが {R_3 = (g^{α})^{r2}}を計算し、アリスのR1とαを使って計算したこのR3から署名に使用するRを計算している {R = (R3)^{r1} = (R1)^{r2 \cdot α}}

このため、スクリプトレスなマルチシグであれば、↑のステップ5でアリスがボブから受け取ったc3を復号して、 {s'' \gets s' \cdot (k1)^{-1}}を計算した値が署名データsになっていたが、今回計算したデータにはαが含まれており、これを取り除かないと有効な署名にならない。

そのため計算結果のs''をボブに送って、ボブがそこからαを除いた署名データsを計算する。この署名データがブロードキャストされると、アリスはそのsとアリスが計算したs''を使ってαを算出することができる( {α \gets (s \cdot (s'')^{-1})^{-1}})。

こうしてシークレットと交換にコインを入手する有効な署名を作れる仕組みを利用することで、スクリプトレスなAtomic Swapを実現できると。よく考えるなー。

サンプルコード

↑のプロトコルを実際にRubyで書いたのが↓のコード(bitcoinrbpaillierのgemが必要)。

gist.github.com