Develop with pleasure!

福岡でCloudとかBlockchainとか。

DLCでオラクルが公開した署名からシークレットを生成するコードを書いてみた

去年発表されたDiscreet Log Contractsについて↓

https://adiabat.github.io/dlc.pdf techmedia-think.hatenablog.com

オラクルが作成するのがSchnorr署名だったので、最初読んだとき現状のBitcoinでは実装できないと勘違いしてたんだけど、オラクルが公開する署名はブロックチェーン上に出てくる必要はなく、公開方法は著者曰く

てことだったので、オラクルが管理するWebサイトなんかで公開されればOKで、それを利用したコントラクトやシークレットの復元は既存のBitcoinのECDSAで対応できる。

ということで実際にRubyDLCを実現するコードを書いてみた(DLCの仕組みについてはここでは記載しないので、↑のブログかホワイトペーパー参照)。

オラクルのセットアップ

事前にgem bitcoinrbをインストールしておく。

オラクルはまず自身の公開鍵を共有する。ECDSAの鍵で良いので

require 'bitcoin'

o_key = Bitcoin::Key.generate

とかして生成する。

この時ランダムな秘密鍵v、対応する公開鍵(=楕円曲線状の点)をV = vGとする。

V = o_key.to_point
v = o_key.priv_key.to_i(16)

↑のVはオラクルを識別するための公開鍵に当たり、再利用可能。

Vとは別に、DLCコントラクト毎に鍵ペアを生成する。R = kG

tmp_key = Bitcoin::Key.generate
R = tmp_key.to_point
k = tmp_key.priv_key.to_i(16)

○月△日のマーケットの終わり値を公開するオラクルとかだとRはある日の終わり値を公開するのに使われる。別の日は別の鍵ペアから生成したRを使用する。

オラクルは事前にVRを公開しておく。

DLC参加者のセットアップ

DLC参加者のアリスとボブは資金を両者のマルチシグにロックするFunding Txを作成しブローキャストする。

Funding TxでロックされたマルチシグアウトプットをインプットにしたDLCのContract Execution Transactionsを大量に作成する。このトランザクションは基本的に2つのアウトプットを持ち、1つは通常のP2PKHで、もう1つは以下のような条件のスクリプトになる。

OP_IF
  <PubAi>
OP_ELSE
  <ロックタイム> OP_CSV OP_DROP <PubB>
OP_ENDIF
OP_CHECKSIG

このコインをアンロックできる条件は以下のいずれか

  • このトランザクションがブロックに入ってからロックタイムで指定された期間が経過した後に、ボブの公開鍵に対して有効な署名を作成する。
  • PubAiに対して有効な署名を作成する。

一見タイムロックのコントラクトだが、ELSE分岐のPubBは通常のボブの公開鍵に対して、タイムロックが設定されていないIF分岐のPubAiの方は通常のアリスの公開鍵ではなく、アリスの公開鍵 + siGとなる公開鍵になる。アリスが資金を償還する際は自身の秘密鍵に加えてsiの値を知らないと有効な署名を作成できない。アリスはこの時点でsiの値は知らないが、siGについてはsiG = R - h(i, R)Vで計算できる。iの部分は署名のメッセージで、DLCではオラクルが公開する値。マーケットの終値が100だったら、オラクルが公開するのはi == 100のデータ。

このPubAiを計算するのが↓のコード
h(i, R)で使うハッシュ関数や計算ルールは詳細に記載されていないので適当)

# アリスが鍵ペアを作成
alice_key = Bitcoin::Key.new.gerate

# 考えられるスコープでi分のsiGを計算する。
# とりあえずi == 100の場合、h(100, R)は
R_str = ECDSA::Format::PointOctetString.encode(R, compression: true)
R_hash_value = Bitcoin.sha256((100.to_s(16) + R_str).htb).to_i(16)

# siG = R - h(100, R)V
s100_G = R + V.multiply_by_scalar(R_hash_value).negate 

# Alice's pubkey + siGは
alice_100_pubkey = alice_key.to_point + s100_G

同様のことを条件を逆にしてボブも行い、作成したそれぞれの公開鍵を使ってContract Execution Transactionsを作成し、自分の署名を付与して、相手とそのトランザクションを交換する。

作成したiのデータが異なる大量のContract Execution Transactionsのいずれかが、チェーンにブロードキャストされるトランザクションになる。実際にブロードキャストされるトランザクションは不正をしない限り、オラクルが公開したiに対応するトランザクションである(不正をした場合は、LNのペイメントチャネルと同様、不正をした側の資金が全部没収される)。

オラクルによる署名の公開

マーケットが閉じたらオラクルは、その終値をもとに署名データを作成する。署名に使用するRは事前に公開してあるので、必要なのはsの値。具体的にはオラクルが持つ秘密鍵を使ってs = k - h(i, R)vを計算する。ここではi == 100だったと仮定する。

# h(100, R)vを計算
hash_value = R_hash_value * v % ECDSA::Group::Secp256k1.order

# s = k - h(100, R)vを計算
s100 = (k - hash_value) % ECDSA::Group::Secp256k1.order

と生成したs100を公開する。

公開された署名から必要な秘密鍵を計算

アリスとボブは、オラクルが公開したsの値を使って、アンロックに必要な秘密鍵を計算する。

alice_unlock_key = Bitcoin::Key.new(priv_key: ((alice_key.priv_key.to_i(16) + s100) % ECDSA::Group::Secp256k1.order).to_s(16))

この計算結果がPubA100秘密鍵になる。この秘密鍵を使ってブロードキャストされたContract Execution Transactionのアウトプットをアンロックできる。 scriptPubkeyのアンロック自体は計算した秘密鍵を元にECDSAで行われるので、Schnorrの署名検証がブロックチェーンスクリプトとして実行される必要はない。

※実際は手数料を考えると二人が協力し、Contract Execution Transactionはブロードキャストせず、Funding Txのアウトプットをインプットとしたクロージングトランザクションを作成する方が良い。

新しいSIGHASHフラグ「SIGHASH_NOINPUT」を定義したBIP-118

現在BitcoinにはSIGHASH_ALLSIGHASH_SINGLESIGHASH_NONEの3つにSIGHASH_ANYONECANPAYを組み合わせた系6バターンのSIGHASHの組み合わせがあるが↓

techmedia-think.hatenablog.com

これにSIGHASH_NOINPUTという新しいSIGHASHフラグを追加しようというBIP-118が提案された↓

https://github.com/bitcoin/bips/blob/master/bip-0118.mediawiki

これまでのSIGHASHフラグの署名はいずれもインプットのデータにコミットしてきた。インプットのデータは↓

  • OutPoint
    (使用するUTXOの参照先のデータ(32バイトのTXIDとそのアウトプットのインデックス4バイト))
  • nSequence
  • scriptSig

この内scriptSigは署名自体を格納するデータ領域なので除外して、OutPointとnSequenceにコミットしてきた。またこれに加えて、OutPointの参照先であるアウトプットのスクリプトにもコミットしている。(コミットしているというのは、署名を生成する際の署名対象のデータ(トランザクションダイジェスト)に、これらの値が含まれているということ。)

そのため、署名済みのトランザクションについて、そのインプットが参照するOutPointの値を変更すると、署名が無効になり、無効なトランザクションになっていた。

BIP-118で提案されているSIGHASH_NOINPUTは、このインプットの参照へのコミットメントを外せるようにしようというもので、今後のSegwitのwitness versionを更新するタイミング(バージョン1以降のSegwitスクリプト)での導入を提案している。

具体的には、Segwitトランザクションで署名を生成する際のトランザクションダイジェストは現在BIP-143のルールに従って生成されているが↓

techmedia-think.hatenablog.com

SIGHASH_NOINPUTが指定されていた場合は、このトランザクションダイジェストの生成アルゴリズムを変更して、hashPrevoutshashSequencescriptCodeを全部空にする(詳細は下記仕様参照)。

こうすると、署名済みトランザクションのインプットの参照先のOutPointを別のものに変更しても、署名は有効なままになる。この参照先を変更することをリバインディングと呼んでいる。

ただ、当然参照先をどんなアウトプットにでも変更できるという訳ではない。トランザクションwitnessにはリバインディング前のアウトプットのscriptPubkey(witness program)をアンロックするための要素がセットされているので、同じwitnessのアイテムでアンロック可能なアウトプットのみリバインディングが可能となる。

SIGHASH_NOINPUTは、通常のオンチェーンでビットコインを送金する際には使うことはないが、先日Blockstreamが発表した新しいLNのプロトコル「eltoo」などが実装できるようになる↓

techmedia-think.hatenablog.com

現状はまだBIPのドラフトが公開されたばかりで、デプロイ時期は次のSegwitバージョンに合わせるということで未定、参照実装もまだ無いので、導入に向けては今後の反応を待つ感じかな?

また、SIGHASH_NOINPUTのフラグの値が0x40と、フォークコインのリプレイ保護で導入されたFORK_IDのSIGHASHフラグと値が被ってるが、MLのポストみた感じだと適用するのはSegiwtトランザクションだから影響はないってことでそのまま採用の流れか?

以下BIPの仕様の意訳↓

仕様

SIGHASH_NOINPUTは値0x40のフラグで、署名がインプットのいずれにもコミットしない(=使用されるアウトプットにコミットしない)。このフラグは単一の署名検証にのみ適用される。

SIGHASH_NOINPUTはバージョン1以上のSegwitスクリプトに対してのみ有効で、このフラグが非Segwitスクリプトもしくはバージョン0のSegwitスクリプトに対して使用された場合、現在の動作はそのままでスクリプトの実行は失敗して中断しなければならない。

SIGHASH_NOINPUTの署名を検証する際は、BIP-143のトランザクションダイジェストアルゴリズムが使われるが、以下の点が異なる。

2. hashPrevouts (32バイトのハッシュ) は32バイトの0x00になる。
3. hashSequence (32バイトのハッシュ) は32バイトの0x00になる。
4. outpoint (32バイトのハッシュ + 4バイトのリトルエンディアン)には36バイトの0x00がセットされる。
5. インプットのscriptCodeには空のスクリプト0x00がセットされる。

前のアウトプットのvalue(Bitcoinの量)は、トランザクションダイジェストの一部としてそのまま残っているので、署名にもコミットされる。

NOINPUTフラグはSINGLEフラグと組み合わせて使ってもよく、この場合hashOutputsはBIP-143に従って変更され、インプットと同じインデックス以外のアウトプットについてはuint256 0x0000......0000になる。

ダイジェストアルゴリズムの変更になるため、NOINPUTフラグは全てのSegwitの署名検証opcodeに適用される。具体的には以下のopcodeに適用される。

  • OP_CHECKSIG
  • OP_CHECKSIGVERIFY
  • OP_CHECKMULTISIG
  • OP_CHECKMULTISIGVERIFY

スクリプトによるバインド

NOINPUTを使うとその署名が含まれているインプットは特定のアウトプットを参照しなくなる。参加者はトランザクションを受け取り、セットされている署名を無効にすることなくインプットが参照する前のアウトプットのハッシュリファレンスを書き換えることができる。これにより、トランザクションは、インプットの参照先をwitnesswitnessProgramにコミットされた値とマッチする任意のアウトプットにバインドすることができ、新しいバインド先のアウトプットと組み合わせたトランザクションwitnessの結果はtrueを返す。

以前は、トランザクション内の全ての情報が署名自体にコミットされていたが、これからはトランザクションと使われるアウトプットの関係は、witnessProgramwitnessの互換性にのみ基づくようになる。

これはまた、このリバインディングの仕組みを誤って有効にしないように、特別な注意を払わないといけないことを意味する。NOINPUTはアプリケーションに明示的に必要とされない限り有効にしてはならない。つまりウォレットの実装でデフォルトの署名フラグにしてはならない。リバインディングは、トランザクションにバインドできるアウトプットがすべて同じ公開鍵を使っている場合のみ可能だ。NOINPUTで使用されている公開鍵は、インプットがバインド可能なアウトプットにのみ使用する必要があり、インプットがバインド出来ないトランザクションには使用しないこと。例えば、アプリケーションはNOINPUT署名を使用するアプリケーション用に新しいキーペアを生成し、後でそれを再利用してはならない。

デプロイメント

NOINPUT SIGHASHフラグは通常のSegwitスクリプトの更新中にデプロイされる。

後方互換

ソフトフォークなので、旧ソフトウェアは変更することなく引き続き動作する。ただしアップグレードされていないノードでは、新しいSIGHASHフラグは検証されず、デフォルトでトランザクションは有効と判断される。Segwitトランザクションにのみ適用可能であるため、非Segwitノードには誰でも使用可能なスクリプトととして表示され、有効と判断される。

LNのオフチェーンコントラクトの更新をシンプルにするプロトコル「eltoo」

Lightning Networkのコア機能は、二者間のオフチェーンでの決済時に新しい残高について合意し、(古い状態のコミットメントトランザクションをブロードキャストすると資金を失うというペナルティを与えることで)古い状態がオンチェーン上に展開できないようにする、オフチェーンのコントラクトの更新の仕組みにある。

このオフチェーンのコントラクトの更新をシンプルにする新しいeltooという仕組みを、先日Blockstreamが発表した↓

blockstream.com

注意点として、eltooは、既存のLNのシークレットの交換とタイムロックを使ったペナルティ付きのコントラクトとは全く別のプロトコルになるので、既存のLNとの互換性はない。また、SIGHASH_NOINPUTという新しいSIGHASHフラグの導入が前提であるため、現時点のBitcoinでは利用できない。

ホワイトペーパー↓

https://blockstream.com/eltoo.pdf

プロトコルの詳細が紹介されているので見てみた。

eltooのオンチェーンプロトコル

eltooのホワイトペーパーにはベースとなるオンチェーンプロトコルとオフチェーンプロトコル両方が記載されており、まずベースとなるオンチェーンのプロコトルから見ていく。

eltooのプロトコルは以下の3つのフェーズからなる。

  1. セットアップフェーズ
    資金を取引の参加者のマルチシグにロックしてチャネルを開設するフェーズ。
  2. ネゴシエーションフェーズ
    決済の状態を更新するフェーズ。
  3. セトルメントフェーズ
    決済を終え、チャネルをクローズするフェーズ。

基本的には既存のLNと同じフェーズがそれぞれあり、主にネゴシエーションフェーズとセットアップフェーズで作成・更新される仕組みが異なる。また、既存のLNでは、各決済の状態(残高)をチャネルに参加している両者が、新しい残高に更新したCommitment Txを作成し、自分の署名を加えて相手に渡し、古いCommitment Txで使っていたシークレットを相手に明かすことで決済の状態を更新している。

一方eltooでは、以下の2つのトランザクションのペアで各決済の状態を管理する。

  • Update Tx
    Funding Txのアウトプットもしくは、前のUpdate Txのアウトプットをインプットとして、新しいアウトプットを作成するトランザクション。決済の更新を表現する。
  • Settlement Tx
    Update Txのアウトプットをインプットとして、その決済によって新しくなったアリスとボブの残高のアウトプットを2つ持つトランザクション。Update Txによる決済の更新の結果、両者の残高を反映する。

トランザクションがどのように構成されるのか、各フェーズ毎に見ていこう。

セットアップフェーズ

チャネルを開設するセトルメントフェーズでは以下の処理が行われる。(アリスとボブ間でオフチェーン決済する前提で記載)

最初にアリスとボブはオフチェーン決済に使用する以下の2つの鍵ペアを生成し、公開鍵を相手に伝える。

  • セトルメント鍵ペア( {A_s と B_s}
    チャネルをクローズする際に作成するSettlement Tx(後述)で使用する鍵
  • アップデート鍵ペア( {A_u と B_u}
    チャネルの状態を更新する際に作成するUpdate Tx(後述)で使用する鍵

続いてセットアップに必要なトランザクションを作っていく。(アリスが資金を提供するとして)アリスは自分の資金をインプットとして、アリスとボブが協力しないとコインをアンロックできないアウトプット( {A_s と B_s}の署名か、 {A_u と B_u}の署名が必要)に資金を送る未署名のFunding Txを作成する。

この時作られるアウトプットのスクリプトが↓(オフチェーンで利用する場合、実際はELSE分岐の条件にもう1つ条件が加わるが、それについては後述)

OP_IF
  <タイムアウト> OP_CSV
  2 As Bs 2 OP_CHECKMULTISIGVERIFY
OP_ELSE
  2 Au Bu 2 OP_CHECKMULTISIGVERIFY
OP_ENDIF

セトルメント鍵ペア( {A_s と B_s})を使ってコインをアンロックするためには、このFunding Txがブロックに入れられて、<タイムアウト>で設定された期間過ぎるのを待つ必要がある。アップデート鍵ペア( {A_u と B_u})を使ってコインをアンロックする場合、時間の制約はなくすぐにアンロックできる。

続いて、Funding Txに署名&ブロードキャストする前に、払い戻し用のトランザクションを作っておく必要があり、これが最初のSettlement Txになる(最初のSettlement TxのみFunding Txのアウトプットをインプットとし、アウトプットも返却用の1つのみ)。Funding Txのアウトプットをインプットとして、全額をアリスに送るSettlement Txを作成し、ボブに署名をしてもらう。

ボブの署名が正しい署名であると検証できたら、アリスはFunding Txをブロードキャストする。

ネゴシエーションフェーズとセトルメントフェーズ

セットアップフェーズのFunding Txをブロードキャストしてチャネルを開設した後は、オフチェーン決済が可能になる。オフチェーンでの決済=新しいUpdate TxとSettlement Txを作成して、決済の状態(残高)を更新すること。

オフチェーンで決済し、状態を更新したい場合、まず新しいUpdate Txを作成する。この新しく作成するUpdate Txのインプットは前のUpdate Txのアウトプットを参照する。また新しく作成するUpdate Txのアウトプットのスクリプトはインプットが参照する前のUpdate Txのスクリプトそのまま。つまり↓

OP_IF
  <タイムアウト> OP_CSV
  2 As Bs 2 OP_CHECKMULTISIGVERIFY
OP_ELSE
  2 Au Bu 2 OP_CHECKMULTISIGVERIFY
OP_ENDIF

続いて、新しく作成したUpdate TxのアウトプットをインプットとするSettlement Txを作成し、そのアウトプットは決済後のアリスとボブの残高を適用した2つのアウトプットを持つ。

つまりUpdate Txは決済のチャネルの状態の更新を表すTxで、それ自体では決済後のアリスとボブの残高は管理されておらず必ずインプットと同じスクリプトを1つ持つだけのトランザクションで、そのアウトプットをインプットとするSettlement Txで決済後のアリスとボブの残高を管理するようになっている。

eltooで定義されているオンチェーンのプロトコルでは、↑のIF分岐のOP_CSVによるタイムアウトが経過する前までであれば、新しいUpdate Txを作成しブロードキャストすることで決済の更新をする。この新しいUpdate Txがブロードキャストされると、前のUpdate Txと対で作っていたSettlement Txは使えなくなる(新しく作ったUpdate Txのインプットと同じインプットを参照しているため)。そして、OP_CSVによるタイムアウトが経過したら、アリスとボブの最終の段高を反映したSettlement Txをブロードキャストして決済を完了することになる。

このオンチェーンのアプローチは、結局Update Txを決済の都度ブロードキャストする必要があるので、スケール効果はない。そのため、オフチェーン決済では、Update Txをブロードキャストせずに決済の状態を更新する仕組みが必要になる。

eltooのオフチェーンプロトコル

続いて、↑のオンチェーンプロトコルをオフチェーンプロトコルにする仕組みについて見ていく。

SIGHASH_NOINPUTを使った中間トランザクションのスキップ

オンチェーンのプロトコルでは、Update Txは前のUpdate Txのアウトプットを参照しているため、前のUpdate Txがチェーン上にブロードキャストされている必要があるが、オフチェーンにする場合、この参照を前のUpdate Txではなく、さらにその前であったり、最終的にはFunding Txのアウトプットを参照できるようにできれば中間のUpdate Txをスキップして、最終残高を表す最新のUpdate TxとSettlement Txが管理できれば効率的になる。

この仕組みを実現するのに、eltooでは新しいSIGHASHフラグSIGHASH_NOINPUTの導入を提案している。もともとSIGHASHはトランザクションに署名する際に、署名対象となるトランザクションのデータを指定するための仕組みだ。

techmedia-think.hatenablog.com

ほとんどのトランザクションSIGHASH_ALLで署名されているが、それ以外に

  • SIGHASH_SINGLEを使うと、署名をセットするインプットとそのインプットと同じインデックスのアウトプットは署名対象になるが、その他のインプットやアウトプットは署名対象にはならないので、それ以外のインプットやアウトプットを自由に追加できる。
  • SIGHASH_NONEを使うと、インプットは全て署名対象になるが、アウトプットは署名対象にならないのでアウトプットのデータを自由に変更・追加・削除できる。
  • さらにSIGHASH_ANYONECANPAYフラグをSIGHASH_ALLSIGHASH_SINGLESIGHASH_NONEと組み合わせることで、自由にインプットを追加できるようになる。

という機能を持つSIGHASHを利用することができる。

Floating Transaction

SIGHASH_NOINPUTは、SIGHASH_ANYONECANPAYのような位置付けのフラグで、インプット内の前のOutPoint(UTXOを参照するフィールド)の値を空白にし署名対象から外すようになる。このフラグが適用されると、署名データはインプットが参照する前のアウトプットに対してコミットしなくなり、異なるUTXOを参照するようトランザクションを書き換えることができるようになる。

具体的には署名済みのトランザクションがあって、そのトランザクションのバージョンやロックタイム、インプット or witnessにある署名スクリプト、アウトプットの量やscriptPubkeyが同じであれば、インプット内のOutPointの値を変更しても、インプット or witness内にある署名は有効な署名のままという訳だ。

このように任意の前のトランザクションアウトプットに接続し、中間トランザクションをスキップするトランザクションFloating Transactionと呼び、インプットの参照先を書き換えることをバインディングと呼んでいる。

Funding Txを作成してチャネル開設後、いくつか決済をした後、最新のUpdate Txのインプットの参照先をFunding Txのアウトプットに変更すると、その中間のトランザクションをスキップして最新のUpdate Txとそれに対応するSettlement Txによりチャネルはクローズされ、その間に作ったUpdate TxとSettlement Txはチェーン上には現れない。

古い決済状態の無効化の仕組み

相手が裏切って自分の残高の方が多い、中間状態の古いUpdate Txをブロードキャストした場合、そのUpdate Txに対応するSettlement Txで資金を奪おうとしても、OP_CSVでロックされている間、そのSettlement Txは使えないので、その間に最新のUpdate Txのインプットの参照先をブロードキャストされたUpdate Txのアウトプットに変更してブロードキャストすることで、古いSettlement Txのブロードキャストを阻止でき、最終的に最新のUpdate Txに対応したSettlement Txを使ってチャネルをクローズできる。

Locktimeを利用したUpdate Txのバージョン管理

SIGHASH_NOINPUTにより中間トランザクションをスキップでき、効率的なオフチェーン決済が可能になったかのように思えるが、1つ問題がある。オフチェーン決済によりUpdate Txの更新をTu,1Tu,2Tu,3Tu,4Tu,5Tu,iは各決済のUpdate Tx)と続けた場合、Tu,5がブロードキャスされた後に、それより前のTu,2がブロードキャストされる可能性がある。つまり最新の状態を古い状態に置き換えることができてしまう。

これは、オンチェーンではUpdate Txは必ず前のUpdate Txのアウトプットを参照していたので順序が保証されていたのが、Floating Transactionにより参照するOutPointを自由に変更できるようにしてしまったため、作成したUpdate Txから順序情報が無くなってしまったことに起因する。

この問題に対応するためオフチェーンのUpdate Txのスクリプトは以下のような形式に変更する(Siはステートナンバーで、決済回数を意味する)。

OP_IF
  <タイムアウト> OP_CSV
  2 As,i Bs,i 2 OP_CHECKMULTISIGVERIFY
OP_ELSE
  <Si + 1> OP_CHECKLOCKTIMEVERIFY
  2 Au Bu 2 OP_CHECKMULTISIGVERIFY
OP_ENDIF

オンチェーンのUpdate Txとの違いは、ELSE分岐に<Si + 1> OP_CHECKLOCKTIMEVERIFYが追加されていて、次のステートナンバー<Si + 1>にコミットしているのと、セトルメント鍵ペアが決済毎に変わる仕組みになっている(これに関しては後述)。ステートナンバーはUpdate TxのnLocktimeフィールドに格納される。

このため、Update Txのアウトプットを使用する場合、スクリプト内に定義されているステートナンバー以上のステートナンバーを持つUpdate Txのみが、そのUpdate Txのアウトプットを利用できる。nLocktimeを含めてもう少し詳細に書くと、

Tu,5のUpdate Txのアウトプットスクリプトには6 OP_CHECKLOCKTIMEVERIFYという条件が含まれる。つまりこのアウトプットを使用するUpdate TxのnLocktimeには6以上がセットされていなければ、スクリプトの評価時にエラーとなる。Tu,2トランザクションnLocktimeには2がセットされているので、この結果エラーになり、Tu,5がブロードキャストされた後に、Tu,2のインプットの参照をTu,5に変更しても、そのトランザクションは無効でブロードキャストできない。

※ もともとnLocktimeはある時間までトランザクションをブロックに入れられないよう絶対時間(UNIXタイムスタンプ or ブロック高)で制限するopcodeだが、これをステートナンバーの格納先に利用しようという仕掛け。実際nLocktimeは値が5億以上だとUNIXタイムスタンプとして利用するので、現在のUNIXタイムスタンプが約15億なのでロックされない過去分の値が10億分使えることになる。このため実際のステートナンバーは500,000,001とかから始まるんだと思う。

ステートナンバー導入を考慮したSIGHASH_NOINPUTの挙動

↑でSIGHASH_NOINPUTは署名のダイジェストデータ作成時にOutPointを空にすることで、別のUTXOへの切り替えを可能にすると書いたけど、アウトプットにステートナンバーが含まれるようになると、これだけではまずい。署名のダイジェストデータを作成する際の要素として、インプットが参照するアウトプットのスクリプト(scriptCode)にコミットするようになっているためだ。ダイジェストに含まれる要素はBIP-143で定義されている↓

techmedia-think.hatenablog.com

何が問題かというと、ステートナンバーがアウトプットに含まれている状態で、インプットの参照を変更すると元々の署名時のステートナンバーと異なるステートナンバーがscriptCodeにセットされるので署名検証に失敗してしまう。このため、SIGHASH_NOINPUTが変更するのはOutPointのデータだけではなくscriptCodeも含まれる。↓にSIGHASH_NOINPUTのBIPドラフトが公開されており↓

https://github.com/cdecker/bips/blob/noinput/bip-xyz.mediawiki

BIP-143からの変更点は↓

2. hashPrevouts (32-byte hash) is 32 0x00 bytes
3. hashSequence (32-byte hash) is 32 0x00 bytes
4. outpoint (32-byte hash + 4-byte little endian) is set to 36 0x00 bytes
5. scriptCode of the input is set to an empty script 0x00

OutPointのデータ(2,3,4)に加えて、scriptCodeも空になるようになっている。これにより、署名がインプットが参照するアウトプットのスクリプトにコミットしなくなるので、参照先を変更してそのアウトプットスクリプト内に定義されている次のステートナンバーが異なる場合でも署名は有効なままになる。

Settlement TxのUpdate Txへのバインド

Update Txはステートナンバーの導入によりUpdate Txの新旧を逆行するようなブロードキャストはできなくなったが、Settlement TxもSIGHASH_NOINPUTによりインプットが参照するUpdate Txのアウトプットへの参照を変更できてしまうと、自分に有利なSettlement TxをブロードキャストされたUpdate Txにバインドして使われてしまうリスクがあり、こちらも対応が必要になる。

このため各決済毎にそれぞれ固有の新しいセトルメント鍵ペアのセットAs,iBs,iを導出する。これが適用されるのが、↑のUpdate Txのアウトプットの2 As,i Bs,i 2 OP_CHECKMULTISIGVERIFYの部分。鍵ペアの導出自体はHDウォレットなどと同様に決定論的に導出する。これによりSettlement Txは一致するUpdate Txにのみバインドすることができる。最新の状態に対応した鍵ペアのみ覚えておけばいいので、これにより参加者のストレージも増加しない。

ステートナンバー導入を考慮した署名の作成

アウトプットのスクリプトnLocktimeが全て同じなら、SIGHASH_NOINPUTでインプットの参照先を変更しても、署名は最初に作った署名だけあれば済むが、ステートナンバーがnLocktimeに格納され次のステートナンバーがアウトプットのスクリプトに記載されるようになったので、基本的にUpdate Txを作成する度に署名は作成する必要がある。

Update Txに対応するSettlement Txも、決済毎に使用するセトルメント鍵ペアが変わるので、Settlement Tx毎に署名を作成する必要がある。

ただ、どちらも最新のTxの署名だけ管理してればOK。

トリガーフェーズの導入

残る問題が1つ。最初のFunding Txを作成したとき、そのアウトプットのIF分岐のタイムロック条件がセットされており、このタイムアウトを過ぎると最初に作成したアリスに全額返金するSettlement Txがブロードキャストできるようになる。つまりFunding Txに設定されてあるタイムアウトの期間がペイメントチャネルのライフタイムになる。これを既存のLNのようにチャネルのライフタイムの制限を外すために、セットアップフェーズの後にトリガーフェーズを導入する。

まずセットアップフェーズのFunding Txのアウトプットについて、eltooのオンチェーンプロトコルではUpdate Txと同じスクリプトを使用していたが、これをアリスとボブの単純な2-of-2のマルチシグに変更する。

そして、Funding TxのマルチシグをインプットとしたTrigger Txを作成する。このTxのアウトプットは、元々のFunding Txにセットしていたスクリプトにする。そしてUpdate TxはFunding Txではなく、Trigger Txのアウトプットをインプットとする。

こうするとFunding Txがオンチェーンで承認されても、Trigger Txは手元にあるのでタイムロックの計測はスタートしない。オフチェーン決済を繰り返し、最終的にチャネルをクローズする際に、Trigger Txと最新のUpdate Tx、Settlement Txをブロードキャストすれば良い。

SIGHASH_SINGLEで手数料を追加

今まで手数料については触れなかったが、Update Txを使用する際の署名について、署名作成時のSIGHASHタイプをSIGHASH_SINGLEにする。Update Txは1つのインプットと1つのアウトプットを持つトランザクションなので、SIGHASH_INPUTで署名をしておけば、ブロードキャスト時にインプットとアウトプットを任意に追加できる。これによりブロードキャスト時に手数料分のインプットを追加し、インプットから手数料を引いたお釣り用のアウトプットを追加することができ、そのタイミングで適切な手数料を任意に設定することができるようになる。

複数の参加者への拡張

↑はアリスとボブの2人だけだったけど、参加者を増やす場合は、

  • Update Txのマルチシグを参加者数分のマルチシグにする
  • Update Txに対応したSettlement Txはそれぞれの参加者数分の残高を管理するアウトプットにする

ことで簡単に実現できる。参加者が増えると、その分ネゴシエーションフェーズでの調整コストは上がるけど、それは他の方法でも同じ。

所感

オフチェーンプロトコルで作成されるトランザクションと無効化の仕組みを簡単に表すと↓のようになる。

f:id:techmedia-think:20180517110519j:plain (各Update Txのインプットは差し替えられるのでどこを参照してても良いと思うので、とりあえずTrigger Txにしてる)

  • オフチェーンプロトコルを理解するためのキーは、SIGHASH_NOINPUTと署名ダイジェストの仕組みの理解が必要。
  • 作成するコントラクトとかはシンプルで、チャネルの参加者間で管理するトランザクションも全く同じトランザクションになるので、既存のLNに比べてコントラクトはシンプルになるかも。
  • チャネルのオープン/クローズで、Funding, Trigger, Update, Settlementという4つのトランザクションがオンチェーンに乗るので、既存のLNより2つ余計にトランザクションをブロードキャストすることになるんじゃ?と思ったけど、協力してクローズする場合はFundingをインプットにして最終残高を反映したクロージング用のTxを作成すればいいだけなので変わらないな。
  • SIGHASH_NOINPUTが導入されると、こういったインプットをすげ替える特性を活かしたコントラクトとかできそう。柔軟になる一方、リスクにもなる可能性はありそう。

Schnorrの代わりに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. CSを使って新しい公開鍵(楕円曲線上の点)P = C + H(C || S)Gを計算する。(Hはハッシュ関数で||は連結)
  4. scriptPubkey <taproot version> P宛にコインを送金する。

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

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

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

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

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

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

ECDSAを使ったTaproot

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

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

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

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

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

コインのアンロック方法

2つあるコインのアンロック方法の内、その他の条件(タイムロックされたスクリプト)を使ってコインをアンロックする場合、これも↑の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に対して有効な署名を作成する。

実際に検証したコードが(bitcoinrbpaillierのgemが必要)↓

gist.github.com

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

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