2P-ECDSA: Fungible 2-of-2 MultiSigs for Today's Bitcoin at Scaling Bitcoin 2018

Scaling Bitcoin 2018 復習シリーズ。今回はLightning LabsのConner Fromknechtによる「2P-ECDSA: Fungible 2-of-2 MultiSigs for Today's Bitcoin」の発表↓

youtu.be

書き起こしは↓ scriptless-ecdsa

前半はLindellベースの2者間のECDSA署名プロトコル↓の解説と、後半はそれを実際にLightning Networkに適用する際の考慮事項についてまとめた発表になってる。

techmedia-think.hatenablog.com

あとところどころPedroの話が引用されてるけど、それはこのセッションの前に発表されたMulti-Hop Locksの話↓

techmedia-think.hatenablog.com

2P-ECDSAの歴史

2016年にBlockstreamのAndrew PoelstraがSchnorrベースのScriptless Scriptを発表
これにより共有データ（通常ペイメントハッシュ）をブロックチェーン上で明らかにすることなく、クロスチェーンでコインのスワップすることが可能になった。チェーン間でトランザクションがリンクされることもない。彼はその後、LNのハッシュプリイメージのチャレンジをこれで置き換える公正を提案する。
2017年3月、PedroがMulti-Hop Locksの発表で言及したように、LNの各ホップで支払い情報がランダム化されることを保証するようになった。全ての決済は伝播された順に決済される。
- これによりプライバシーが向上
- Pedroの言うようなWormhole Attackへの防御になる
2017年末、Yehuda Lindellは、効率的な2p-ECDSA署名プロトコルを発表した。このプロトコルは現在のBitcoinのノードと完全な下位互換があり、どのノードもこの署名検証を行える。また現在存在するP2PKHやP2WPKHで利用可能。
2018年4月、PedroがLNのホップの無相関化のフレームワークを形式化したMulti Hop Locksをリリースした。これには2p-ECDSAに基づく、Scriptless Scriptの構築が含まれている。また経路内の各ホップはECDSAをベースにしてもいいし、Schnorrをベースにしてもいい。つまり経路内にECDSAとSchnorrが混在していても問題ない。そのため、現在のLNにECDSAベースのMulti Hop Locksを導入した後、後でSchnorrがBitcoinに導入されたら、LNのネットワークを断片化することなくスムーズに移行することができる。
現在、いくつかの2p-ECDSAを研究している。

2p-ECDSAの概要

アリスは秘密鍵aと対応する公開鍵A = aGを持っている。
ボブは秘密鍵bと対応する公開鍵B = bGを持っている。
お互い公開鍵は共有しており、公開鍵Q = (ab)G = aB = bAを計算する。Qの対応する秘密鍵はab。
- 二人ともabのデータは知らない。 *二人で協力してQに対して有効なECDSA署名を生成する。

有効なECDSA署名を生成するにあたって、２つのアルゴリズムが必要になる。

KeyGen（オフライン）
オンラインのSign プロトコルに参加するためのアリスとボブのセットアップ。コスト的に高価だが実行するのは１回だけ。
Sign（オンライン）
効率的だが２回の往復が発生するオンライン署名プロトコルで、Qに対して有効なECDSA署名を生成する。

KeyGen

基本的にアリスとボブはそれぞれが持つ公開鍵と、その公開鍵の離散対数（秘密鍵）を知っていることの証明を交換する。これは標準的なShcnorr署名のデータを確認することで、その公開鍵に対応する秘密鍵を持っていることを確認できる。
アリスはPaillier暗号用の鍵ペア（PSK, PPK）を生成する。またアリスがボブを騙すことが無いよう、鍵PPKが ${N= p_1 * p_2}$ の ${p_1}$ 、 ${p_2}$ で構成されていることを証明するゼロ知識証明を提供する。
アリスは公開鍵PPKで秘密鍵を暗号化し、暗号テキスト ${c = Enc_{PPK}(a)}$ を作成する。
アリスは（PPK, c）をボブに送る。
- ボブは暗号テキストを受け取るだけで、元の値のサイズを知ることができないため、アリスはそれが小さいことを証明する必要がある。この証明のため、一緒に暗号テキストcの値が ${ 0 ＜ Dec_{PSK}(c) ＜ q}$ の範囲内であることをゼロ知識証明を提供する（qは曲線secp256k1の位数）。実際、暗号テキストは元の値よりはるかに大きなデータになる。
- そしてcにアリスの秘密鍵を含まれていること = ${A = Dec_{PSK}(c) G}$ を証明する。
- Lindellはこれを証明するのに新しいゼロ知識証明を発明しなければならず、２つの異なる暗号システムを混在させていた。
ボブは、受信した証明全てを検証し、Q = bAを計算する。
アリスはQ = aBを計算する。

KeyGenの結果、

アリスは2p-ECDSAの公開鍵Q = abGと秘密鍵（a, PSK）を持つ。
ボブは2p-ECDSAの公開鍵Q = abGと秘密鍵（b, c, PPK）を持つ。

Sgin

Paillier暗号の特性

なぜ、KeyGenでPaillierを使っているのか?というと、主な理由は、ECDSAではScnorrのように公開鍵や署名の加算ができない（公開鍵や署名が線形性を持っていないため）。このため非対話型の集約に適していない。ただ、Palliler暗号データは以下のような部分的な準同型の性質を持っている。

加法準同型性（暗号化したデータ同士を加算できる）
D(E(m1) * E(m2) mod N²) = m1 + m2 mod N
暗号化したデータの元のメッセージに対してスカラ倍できるスカラ乗算
D(E(m1)^k mod N²) = k*m mod N

ボブはこれらをPPKを使って秘密鍵（PSK）の知識無しに計算することができる。

署名プロトコル

ECDSAの署名データは（r, s）。sは、 $s = \frac{H(m) + r * x}{k}$ で、rはR = kGのx座標。

このECDSAの署名をアリスとボブは以下のステップで計算する。

アリスとボブはそれぞれnonceを選択し、この公開鍵とそのnonceを持っていることのゼロ知識証明を共有する。アリス： ${K_a = k_aG}$ 、ボブ： ${K_b = k_bG}$ 。
ボブは暗号データ $c_1 = Enc_{PPK}(\frac{H(m)}{k_b})$ と ${v = \frac{r * b}{k_b}}$ を計算する。ここでrは ${R = k_a * k_b G}$ のx座標。
ボブは $c' = c_1 * c^{v} \mod N^{2} = Enc_{PPK}(\frac{H(m) + r * a * b}{k_b})$ を計算し、アリスに送る。
アリスはそれを復号化した ${s' = Dec_{PSK}(c')}$ を計算し、 ${s'' = \frac{s'}{k_a} \mod q}$
計算結果のs''は $s'' = \frac{H(m) + r * a * b}{k_a * k_b}$ となる。
最後にアリスは ${s = min(s'', q - s'' \mod q)}$ をセットし、（r, s）をSign アルゴリズムのアウトプットとする。

通常のECDSAプロトコルと比較すると、nonce kがアリスとボブのkに、秘密鍵もアリスとボブの秘密鍵に置き換わっている。

こうやって生成した署名はECDSA署名として機能する。最後のステップはLOW_Sルールの適用。

Scriptless Scriptの署名も同様のアプローチだが、シークレットの抽出で余分なラウンドを必要とする。詳細はPedroのペーパー参照。

ベンチマーク

	時間	割り当てられたメモリ	割り当て数	メッセージ数
KeyGen	1.07 秒	4.99 MB	13.31 K	7
Sign	28.66 ミリ秒	97 KB	746	4
Scriptless-Sign	29.40 ミリ秒	118 KB	1.12 K	5+1

KeyGenプロトコルの実際の暗号や複雑さを考慮するともっと遅くなると思われたが全体的に1.07秒で意外と速い結果になっている。おそらく1番遅い部分はgolangのbigintライブラリを使用している箇所で、これは時間が固定時間でなくメモリパフォーマンスに問題があることで有名だ。そのため、この時間は2倍 or 5倍 or 10倍に速くなる可能性がある。

署名は見ての通り30ミリ秒未満。結構大きい。オンラインプロトコルとしては上手く動作する。

Scriptless-Signには多くの最適化作業が残っている。

ベンチマークのコードは↓

github.com

LNへのデプロイの考慮事項

2P-ECDSA/Schnorrのデプロイの場合

Fundingアウトプット

現在は2-of-2のマルチシグにコインをロックしている部分。このコインをアンロックするには、協調してクローズする場合とCommitment Txをブロードキャストする場合の2ケースがあるが、いずれも2人の署名を必要とする。この部分をP2WPKHのロックスクリプトに置き換える。

通常の2-of-2のマルチシグ、Schnorr版、2P-ECDSA版、P2WPKHにおけるWitness Scriptとアンロックに必要なwitnessは以下のようになる。

	witness	witness script
通常	OP_0 <aGの署名> <bGの署名>	OP_2 <aGの公開鍵> <bGの公開鍵> OP_2 OP_CHECKMULTISIG
Schnorr	<(a+b)Gの署名>	<(a+b)Gの公開鍵> OP_CHECKSCHNORRSIG
2P-ECDSA	<abGの署名>	<abGの公開鍵> OP_CHECKSIG
P2WKH	<aGの署名>	<aGの公開鍵> OP_CHECKSIG

使用するスペースは約半分になる。2つの公開鍵は１つに、2つの署名は１つの署名になる。また、非広告チャネルのプライバシーを守るチャンスにもなる。LNのノードでチャネルを広告している場合は、プライバシーを諦めることになるが、プライベートチャネルの場合、Funding Txは通常のP2PKHもしくはP2WPKHのように見えるため、プライバシー上の大きなアドバンテージになる。特に、多くのモバイルデバイスやラップトップ上のノードが、ルーティングのためにノードを広告しないネットワークに移行するにつれて、大きな意味を持つ。また最後に、ゴシップレイヤーの帯域幅が少なくなる。署名が１つ少ないので一般的にネットワークの負荷状況が改善する。

HTLCアウトプット

非標準のHTLCスクリプトで（標準というのはBIP-199のこと？）、2-of-2のマルチシグを使っている。HTLCスクリプトには、offeredとreceivedの2種類のスクリプトがある。２つはほとんど似ているが、チャネル上のどの方向を向いているかが異なり、両方とも2-of-2のマルチシグを必要とする。スクリプト内のoffered-timeoutおよびreceived-successの条件でコインを使用する際に2-of-2のマルチシグを必要とし、その部分をよりシンプルになるよう置き換える。

例えば現在のReceived HTLCスクリプトは

# revocation clause
OP_DUP OP_HASH160 <RIPEMD160(SHA256(revocation pubkey))> OP_EQUAL
OP_IF
  OP_CHECKSIG
OP_ELSE
  <remote_htlcpubkey> OP_SWAP OP_SIZE 32 OP_EQUAL
  OP_IF
    # success clause
    OP_HASH160 <RIPEMD160(payment_hash)> OP_EQUALVERIFY 2 OP_SWAP <local_htlcpubkey> 2 OP_CHECKMULTISIG
  OP_ELSE
    # timeout clause
    OP_DROP <cltv_expire> OP_CLTV OP_DROP OP_CHECKSIG
  OP_ENDIF
OP_ENDIF

のようなスクリプトになっているが、2P-ECDSAを利用してより簡単なHTLCスクリプトにすることができる↓

OP_IF
  # revocation clause
  revocationpubkey
OP_ELSE
  OP_IF
    # timeout clause
    <cltv_expire> OP_CLTV OP_DROP <remote_delay_pubkey>
  OP_ELSE
    # success clause
    <2p_htlc_pubkey>
  OP_ENDIF
OP_ENDIF
OP_CHECKSIG

これにより、

スクリプトのサイズ自体が20%削減
スクリプトの可読性が向上
witnessのサイズ削減
- successの場合のwitnessサイズは78%削減される。
- revocationのケースでは30%ほど小さくなる。
- タイムアウトの場合のwitnessサイズは同じまま。

Offered-HTLCスクリプトでも同様の改善が期待できる。

Scriptlessな2P-ECDSA/Schnorrのデプロイの場合

HTLCアウトプット
Scriptlessな2P-ECDSA/Schnorrを使用すると、HTLCのスクリプトからペイメントハッシュを削除することができる。また拡張によってwitnessからプリイメージを削除できるので、witnessから52バイト削減できる。

スペースの削減という観点からは、手数料も安くなり、ブロックチェーンの負荷も軽減する。

双方向の2P-ECDSA

LNのチャネルは双方向なので、HTLCを更新したい場合、全ての更新とパラメータ（ペイメントハッシュや、タイムロック時間など）をチャネルの反対側に送信し、各チャネルはその更新を適用し、その後作成した署名のバッチを送信する。これを行うと片方の参加者のみが署名で終わる。

オンチェーン上に１つのFunding Outputがロックされていて、どちらの参加者もこれを使用するための署名を開始できる。どちらからでも更新を開始できるように、同じ鍵ペアの２つのインスタンスをセットアップし、それでFunding Output（もしくは同様のもの）のコインを使用するCommitment Txに署名できるようにする。

※ この部分の説明がイマイチよく分かってない。

オニオンパケット

BOLT 04で定義されている現在のonionパケットのデータ構造は以下のようになっている

サイズ	名称
1	version
33	public_key
20*65	hops_data
32	hmac

この内、hops_dataはメッセージ転送中に関連するホップによって使われる情報を含む20個の固定サイズのパケットで構成される。

hops_dataを構成する１つ１つのパケットのデータ構造は以下のようなもの↓

サイズ	名称
1	realm
32	per-hop
32	MAC
	filter

このうち2P-ECDSA/Schnorrのデプロイにあたって変更するのはホップ毎のペイロードのデータ（per-hop）。

現在のper-hopペイロードは以下の32バイト

サイズ	名称
8	short_channel_id
8	amt_to_forward
4	outgoing_cltv_value
12	padding

新しいペイロードは以下のような構成になる。サイズは161バイトで、トータルのパケットサイズは3880バイトとなり元の1300バイトから約3倍のデータ増になる。

サイズ	名称
8	short_channel_id
8	amt_to_forward
4	outgoing_cltv_value
33	incoming_lock_pubkey
64	incoming_lock_dlog_pok
32	hop_lock_secret
12	padding

これらを構築して解読する際のボトルネックの大半は、一時鍵導出やBlindng Factorなどの非対称暗号操作で、ホップ数の増加と共に線形スケールする。そのため、パケットサイズの増加は構築/解読にほとんど影響を及ぼさない可能性がある。

2P-ECDSAとScriptless Scriptのサマリ

メリット

現時点でデプロイ可能
スクリプトとwitnessが小さくなり、手数料が安くなる。
funding outputの匿名セットの向上によりオンチェーンプライバシーが向上
ホップ間の相関を無くすことでオフチェーンプライバシーが向上
2P-ECDSAは、既存のトラフィックに混在し、Schnorrが始まると初期は匿名セットが小さくなる。ただ時間の経過と共にSchnorrに移行すると思われる。
リアルなProof-of-Payment（Invoice Tunneling）
この分野で多くの研究されている。

デメリット

複雑である
- 正しく実装する決して簡単ではない。
- モバイルデバイスのリソース使用量はそれほど大きくないけど、プルーフを並行して処理するためのコアは少ない。
Commitment Txの更新の際により多くの情報の更新が必要で、より多くのラウンドトリップを必要とする（署名プロトコルをパイブライン化してラウンドトリップを削減することは可能かもしれない）。

Develop with pleasure!

福岡でCloudとかBlockchainとか。