効率的な二者間のECDSAプロトコル

以前、Andrew PoelstraがBitcoinスクリプトを書くことなくスマートコントラクトを実現するScriptless Scriptsについて紹介されていたが、これはいずれもSchnorr署名を必要とする仕組みだった。現在のBitcoinのプロトコルでサポートしているのはECDSAのみであるため、当然ながらSchnorrを必要とするScriptless Scriptsは現在のBitcoinでは使えない。ただ、Scriptless Script以外にもSchnorr署名の鍵や署名の集約機能によりトランザクションサイズを削減したり、さまざまなコントラクトへ応用が効くことからSchnorrの導入をしようという流れではある。

そんな中、先日LightningのMLにScriptless ScriptをSchnorrの代わりにECDSAを使って行う方法がポストされた。

[Lightning-dev] Scriptless Scripts with ECDSA

ホワイトペーパー「Scriptless Scripts with ECDSA」も添付されてる↓

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

このECDSAでScriptless Scriptを実現するためにベースとなったのが、イスラエルのバル＝イラン大学のYehuda Lindellが2017年に公開した以下のホワイトペーパーだ。

https://eprint.iacr.org/2017/552.pdf

この内容について「Scriptless Scripts with ECDSA」のペーパーで簡単に説明されてたので見てみる（本家のは長かったので時間ができたら読む）。

ECDSA署名について

まずECDSAの署名方式について。アリスが秘密鍵 x とそれに対応する公開鍵 ${g^{x}}$ を持ち、その鍵を使ってメッセージ m に署名したい場合、アリスはメッセージ m に対して以下のように署名を計算する。

ランダム値 k を選択する。
${R = g^{k}}$ を計算する。
計算したRの点を ${(r_x, r_y)}$ とし、 ${r = r_x}$ とする。つまりrは点Rのx座標。
署名 ${s = k^{-1} \cdot (LSB(H(m)) + r \cdot x)}$ を計算する。ここでLSBは最下位bitの関数を表し、Hはハッシュ関数を表す。
署名の出力は(r, s)

効率的な二者間のECDSAプロトコル

ECDSAの主な課題の１つは効率的な2-of-2の署名プロトコルを設計することだった。最近Yehuda Lindellがこのプロトコルの効率的な構成ついて論文を発表した。ECDSAベースのScriptless Scriptsの提案はLindellのプロトコルの延長にあたるので、ここでそれについて説明する。より詳細な説明とセキュリティ分析についてオリジナルの論文を読むことを勧める。

アリスは公開鍵 ${P_1 = g^{x_1}}$ とナンス ${R_1 = g^{r_1}}$ を、ボブは公開鍵 ${P_2 = g^{x_2}}$ とナンス ${R_2 = g^{r_2}}$ をそれぞれ持つ。最後にアリスはボブにckey = Enc ${pk_A}$ (x1)を提供する。これはアリスのみが解読可能なx1のPaillier暗号だ。このアリスとボブの2-of-2のマルチシグは以下のように動作する。

アリスとボブは、P1、P2、R1、R2とm'について合意する。ここでm'はLSB(H(m))。また、アリスとボブは安全のためP1、P2、R1、R2についてその秘密鍵を確かに持っていことを証明するための非対話型のゼロ知識を追加で交換する必要がある。これはこの後で提案されるプロトコルにおいても同様の基本的な手順として組み込まれているが、読みやすさを優先して省略する。
アリスは ${R \gets (R_2)^{r1}}$ を計算し、ボブは ${R \gets (R_1)^{r2}}$ を計算する。それぞれ計算したRから同じx座標 ${r = r_x}$ を計算することができる。
ボブは ${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})}$ を計算する。ここで ${\rho}$ は巨大な乱数を表し、qは暗号操作中に使用される剰余を表す。続いてボブは ${c_3 = c_1 \oplus c_2}$ を計算する。この ${\oplus}$ はPaillier暗号の加法準同型演算を表す。したがって

${c_3 = Enc_{pk_A} ((k_2)^{-1} \cdot m' + \rho q + x_1 \cdot x_2 \cdot r \cdot (k_2)^{-1})}$

となる。 ${c_3}$ は言わば、ボブからのpre-signatureを暗号化したものになる。最後にボブはアリスに ${c_3}$ を送る。

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

悪意あるボブはプロトコルから逸脱して任意の値を暗号化する可能性があるが、アリスはペア(r, s)が公開鍵Qのもとで有効なECDSA署名であることを検証することで、ボブが正しく振る舞ったかどうか判断することができる。正しくない場合アリスはプロトコルを中止することができる。

というのがホワイトペーパーに記載されている内容で、マルチシグスクリプトを構成することなくマルチシグ的なことができるようになってる。この二者間のECDSAプロトコルをベースにしているのがECDSA版のScriptless Scripts。（スクリプトレスなマルチシグという意味では↑もScriptless Scriptsと言えるだろう。）

途中で急にk1、k2が出てきてるけど、これは単なる書き間違いでr1、r2のことを指してるんだと思う。

ポイント

基本的にはECDSAの署名形式に沿ってないといけないので、アリスとボブによる署名データは乱数kから生成した点Rのx座標と、 ${s = k^{-1} \cdot (LSB(H(m)) + r \cdot x)}$ で計算される(r, s)のペアである必要がある。

通常は１人で作る署名だけど、２つの鍵を使った2-of-2のマルチシグ的な用途のECDSA署名を↑のプロトコルで可能にしているポイントは以下の２つだと思う。

Rの計算

↑のプロトコルではまず署名に使用する点Rの算出方法が変わっていて、アリスがランダムに生成した点R1とボブがランダムに生成した点R2をそれぞれ共有し、その点に自分の点の秘密鍵を乗算して新しい点を計算している。アリスの場合はk1 * R2、ボブの場合はk2 * R1。こうして出来た点Rは同じ点を指す。

この点をECDSAの署名に使う場合、計算した点Rのx座標が署名データの１つのrになり、sを計算する際は、 ${s = (k1 \cdot k2)^{-1} \cdot (LSB(H(m)) + r \cdot x)}$ となる。

秘密鍵を使ったsの計算

もう１つのポイントは、署名データ ${s = (k1 \cdot k2)^{-1} \cdot (LSB(H(m)) + r \cdot x)}$ を計算する際の秘密鍵xの部分だけど、ここがアリスの秘密鍵x1とボブの秘密鍵x2をそれぞれ使って計算するようになるので、結果的にsは、 ${s = (k1 \cdot k2)^{-1} \cdot (LSB(H(m)) + r \cdot x1 \cdot x2)}$ になる。

当然両者が自分の持つ秘密鍵x1とx2を明らかにすることはないので、お互い相手の秘密鍵を知らないままsを計算するために、加法準同型性のあるPaillier暗号を使ってるんだと思う。

アリスはPaillier暗号の鍵ペアを生成し、公開鍵をボブに送っておく。自分の秘密鍵x1を公開鍵を使って暗号化しボブに送る（これがckey）。その後ボブは送ってもらったアリスの公開鍵を使って↑c1を計算し暗号化する。さらにckeyを使ってc2を計算し、Pailier暗号の加法特性を利用してc3を導出し、アリスに送る。アリスはPaillier暗号の自分の秘密鍵を使ってc3を復号すると、