Elements AlphaにおけるFederated Pegの仕組み

Blockstreamが開発しているサイドチェーン実装のElementsで実装されているFederated Pegの技術的な仕組みが↓で公開されてたので見てみる。（記事自体は2016/02/29に書かれたもの）

The Federated Peg in Elements Alpha — The Elements Project

メインチェーンとサイドチェーン間の資金の移動は以下のようなイメージで行われる↓

f:id:techmedia-think:20161108163001p:plain

各プロセスの具体的な仕組みを↑のドキュメントでおさえていく。

Federated Pegの仕組み

OP_WITHDRAWPROOFVERIFY (OP_WPV)

まずAlphaのgenesis blockから見てみる。Alphaのgenesis blockのcoinbase↓

{
    "hex" : "01000000010000000000000000000000000000000000000000000000000000000000000000ffffffff4d04ffff001d0104455468652054696d65732030332f4a616e2f32303039204368616e63656c6c6f72206f6e206272696e6b206f66207365636f6e64206261696c6f757420666f722062616e6b73ffffffff00000000000000000100000000000000000000000000000000000000000000000000000775f05a074000000037206fe28c0ab6f1b372c1a6a246ae63f74f931e8365e15a089c68d6190000000000149eac001049d5c38ece8996485418421f4a01e2d7b300000000",
    "txid" : "0377d218c36f5ee90244e660c387002296f3e4d5cac8fac8530b07e4d3241ccf",
    "version" : 1,
    "locktime" : 0,
    "fee" : 0.00000000,
    "vin" : [
        {
            "coinbase" : "04ffff001d0104455468652054696d65732030332f4a616e2f32303039204368616e63656c6c6f72206f6e206272696e6b206f66207365636f6e64206261696c6f757420666f722062616e6b73",
            "sequence" : 4294967295
        }
    ],
    "vout" : [
        {
            "value" : 21000000.00000000,
            "serValue" : "00000000000000000000000000000000000000000000000000000775f05a0740000000",
            "n" : 0,
            "scriptPubKey" : {
                "asm" : "6fe28c0ab6f1b372c1a6a246ae63f74f931e8365e15a089c68d6190000000000 9eac001049d5c38ece8996485418421f4a01e2d7 OP_WITHDRAWPROOFVERIFY",
                "hex" : "206fe28c0ab6f1b372c1a6a246ae63f74f931e8365e15a089c68d6190000000000149eac001049d5c38ece8996485418421f4a01e2d7b3",
                "type" : "withdraw"
            }
        }
    ],
    "blockhash" : "f7f0ca371b1003dc7346bab766b4a131f9e3a5d68820a364d70921cb15b95eaa",
    "confirmations" : 304446,
    "time" : 1296688602,
    "blocktime" : 1296688602
}

Bitcoinのgenesis blockとはだいぶ違って、１つの出力に2100万の値を持っており（Bitcoinの総発行量と同値）、そのscriptPubKeyも↓のように変わったスクリプトになっている（scriptPubKeyのタイプもwithdraw）。

6fe28c0ab6f1b372c1a6a246ae63f74f931e8365e15a089c68d6190000000000
9eac001049d5c38ece8996485418421f4a01e2d7
OP_WITHDRAWPROOFVERIFY

この出力はwithdraw lockと呼ばれている。OP_WITHDRAWPROOFVERIFY (OP_WPV) は新しいopcode。
Alphaにはマイニング報酬が無いため、Alphaのコインを入手するための唯一の手段は、このwithdraw lockを使うことになる。実際にwithdraw lockを使用するトランザクションwithdrawal transactionを作るケースを考えてみる。

OP_WPVはスタック上に以下の要素があることを想定している。

HASH160(secondScriptPubKey) 、secondScriptPubKeyのチェックのために使う
メインチェーンのgenesis blockのハッシュ
locking transactionが含まれているブロックのcoinbase tx
使用しようとしているlocking transactionの出力のインデックス
locking transaction
locking transactionが含まれているブロックのマークルブロック構造
コインを送信しようとしているコントラクト
secondScriptPubKeyを満たすscriptSig
secondScriptPubKey

最初の２つの引数（secondScriptPubKeyのハッシュと、genesis blockのハッシュ）はscriptPubKeyによって提供されている。これらにはチェーン固有の情報が追加されており、このケースでは後述するscripthashとbitcoinのgenesis blockハッシュになる。↑の

6fe28c0ab6f1b372c1a6a246ae63f74f931e8365e15a089c68d6190000000000

のエンディアンを変換すると

000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f

となり、Bitcoinのgenesis blockのハッシュと同じ値になる。

その次の要素はlocking transactionを提供している。これは、サイドチェーン上でコインを取り出すために、メインチェーン上のコインをロックするメインチェーンのトランザクションである。以下の図はこれまで出てきたトランザクションタイプの関係を表したものになる。

withdrawal transactionは、他のチェーン上のロックを参照して、OP_WPVでロックされたコインを使用する。メインチェーンにはOP_WPVというopcodeは無いので、OP_WPVを使う代わりにメインチェーンでは連合のコントロール下にあるマルチシグ出力でロックする。語彙の対称性に注意すること（メインチェーンで現在アンロックされているコインは、サイドチェーン側ではロックされている状態にある）。

スクリプトインタプリタはlocking transactionの宛先が本当に連合のマルチシグかどうかチェックする。さらに、locking txとcoinbase txがマークルブロック構造の中に含まれているかチェックし、コインベースからブロック高を読み取る。Elements Alphaは非対称ペグを使用しているため、Alphaのフルノードは親チェーンと同様完全なバリデータであることが期待される。locking transactionがBitcoinのブロックチェーン上に存在することを検証するために、AlphaはRPCを介してbitcoindに接続し、getblockをコールしてトランザクションがブロックチェーンに記録され10回承認されているかチェックする。将来的にOP_WPVは、bitcoindに依存することなくブロックが充分な承認がされているかどうかチェックするために、SPV証明を受け入れる。

次にOP_WPVは16バイトのnonceからなるcontractの宛先とwithdrawal transactionの受信者を表す20バイトのscript hashを検証する。インタプリタはpay-to-contract (P2C)プロトコルを使ってlocking transactionがコントラクトにコミットしているかどうかチェックする。P2Cを使うと、locking transactionの送信者は透過的に宛先のscript hashを指定することができ、バリデータはサイドチェーン側でコインを取り出す受信者をチェックできる。これはコントラクトのために新しいキーペアを導出することで動作する。

x: privkey = old_privkey + H(x), pubkey = old_pubkey + H(x)*G.

要約すると、OP_WPVでロックされた出力を使いたいユーザは、最初にサイドチェーン側でP2SHアドレスを作成し、サイドチェーンに移動する資金をメインチェーン上で連合に送るlocking transactionを組み立てる。続いて、（contract形式の）script hashをlocking transactionに埋め込みブロードキャストする。ブロードキャストしたトランザクションの確認期間（１０ブロック）が経過したら、locking transactionとコントラクトを使ってOP_WPVを使うことができる。

Withdraw output

OP_WPVは、それを使用するトランザクションの出力へのアクセス権を持つopcodeの新しいタイプである。OP_WPVは、トランザクションがwithdraw outputという出力と、おつりを表すOP_WPV-locked outputという２つの出力を持っているかチェックする。次にインタプリタは、出力の値を比較し、withdraw outputの資金の量がメインチェーンでロックされた資金より多くないか、残りのおつりがロックされた出力に戻るようになっているか検証する。このおつりは将来また↑のようにメインチェーンからサイドチェーンへ資金を移動する際のトランザクションで使われる。

withdraw outputには↓のscriptPubKeyが設定されている。

OP_IF
    <nLockHeight>
    <lockTxHash>
    <nLocktxOut>
    <fraudBounty>
    <HASH160(secondScriptPubKey)>
    <genesisHash>
    OP_REORGPROOFVERIFY
OP_ELSE
    144
    OP_CHECKSEQUENCEVERIFY
    OP_DROP
    OP_HASH160
    <HASH160(destinationScript)>
    OP_EQUAL
OP_ENDIF

まずELSEブランチを見てみる。OP_CHECKSEQUENCEVERIFYによりこのwithdraw outputがブロックに格納されてから144ブロック（24時間）経過するまで（contest period）、このブランチが実行できないようになっている。contest periodが過ぎたら、withdraw outputは通常のP2SHスクリプトになる。インタプリタはさらに、destination scriptHashがlocking transaction内でコミットされたcontractから作られたscript hashか確認する。

最初のブランチの実行を成功させるには、２つめの新しいopcode OP_REORGPROOFVERIFY (OP_RPV)に不正の証拠を提供する必要がある。そのため、contest periodの間、withdraw outputは任意のノードから不正の証拠を受け入れることができ、それによりこの出力をアンロックし、fraud bountyを収集する。

OP_REORGPROOFVERIFY (OP_RPV)

OP_RPVはメインチェーンのロックの二重使用と（チェーンが分岐し再収縮するケースなどによる）メインチェーンの再構成という２つの無効な状態を修正するためのopcodeである。同じメインチェーンのロックを参照したwithdrawal transactionsを作ることは可能で、以下の図はメインチェーン上のlocking transactionを使ってサイドチェーン側で二重使用しようとする例。

OP_RPVは、不正の証拠が提供された際、withdraw outputをアンロックできる（↑のscriptPubKeyの最初のブランチ）。メインチェーンのロックへの参照は既にwithdraw outputに与えられているため、インタプリタは実際に二重使用があるか、オリジナルのwithdraw transactionと二重使用のwithdraw transaction共にマークルブロックが有効で、二重使用のwithdraw transactionがオリジナルのwithdraw transactionより新しいかチェックする。Elements Alphaのブロックチェーンのコンセンサスは署名者の連合によって決定するため、インタプリタは唯一有効な署名を持つブロックを必要とする。もしAlphaのコンセンサスがPoWであれば、OP_RPVは（OP_WPVがブロック高の検証にSPV署名を使うのと同様）検証のためにSPV証明を必要とする。

OP_WPVと同様、OP_RPVもアンロックするトランザクションの出力を参照する。トランザクションはwithdraw outputの値からfraud bountyを差し引いた値を再ロックするため、OP_WPVを使った１つの出力を持つ。fraud bountyは不正の証明者によって請求される。

名前が示すようにOP_RPVは二重使用があるときだけでなく、メインチェーンが再構成された際にも使われる。そのような状況では、lockin transactionは他のブロックに含まれるか、チェーン上から完全に消えており、いずれの場合も再構成の証拠によってwithdraw outputは無効化される必要がある。これはまだAlphaでは実装されてないが、原則的に証明者が充分時間が経過した後、withdrawal transactionが含まれていたブロックからwithdrawal transactionが消えていること示すSPV証明を提供すると思われる。

alphadの起動オプションにtracksidechain=allを指定していると、二重使用が発生した際に不正の証拠を提供するため全てのメインチェーンのロック出力を保存する。

最後に、OP_WPVの９つめのsecondScriptPubKeyについて見てみよう。secondScriptPubKeyは、scriptSigの実行結果やwithdrawal transactionに関する情報を含むスタックで実行される。Elements Alphaでは、BitcoinをロックするsecondScriptPubKeyは

OP_DROP 144 OP_LESSTHANOREQUAL

で、これで効果的にcontest periodを経過したことを確認できる。secondScriptPubKeyはscriptSigの結果をチェックしないので、この場合のデフォルトのscriptSigはちょうど１バイトのプッシュになる。この仕組みは原則的にトランザクション手数料やfraud bounty、その他の複雑なルールにチェーン特有の制限を加えることができる。

サイドチェーンからメインチェーンへの移動

サイドチェーンからメインチェーンへ資金を移動する仕組みは比較的単純。以下の図は、メインチェーンへ資金を移動する際のトランザクションのシーケンスを表している。

メインチェーン上のfederated lockはm-of-nのマルチシグの出力である。ロックを保持する職員はサイドチェーン上でメインチェーンへの払い戻しのリクエストが来ると、RPCを介してalphadと通信しロックを解除するwatchmanというプログラムを実行する。

払い戻しのリクエストはロック出力の形式をとり、サイドチェーンからメインチェーンへの転送は以下のscriptPubKeyを持つ新しいトランザクションで始まる。

<HASH160(scriptDestination)>
OP_DROP
<genesisBlockHash>
<HASH160(secondScriptPubKey)>
OP_WITHDRAWPROOFVERIFY

このスクリプトはサイドチェーンのコインをロックし、メインチェーンのアドレスを伝える。これによりロックされたコインを意図した受信者に入金するよう職員に指示する。

この仕組みの裏側では、watchmanが別のネットワークを使用してround-basedの分散プロトコルに従い、round-leaderを選ぶ。round-leaderは、払い戻しのリクエストを集めて対応するメインチェーンのwithdrawal transactionを作成する。round-leader以外の他の職員は、そのトランザクションが払い戻しのリクエストに正しく対応しているか（宛先は正しいか、サイドチェーンのロックはn confirmされているかなど）チェックし、署名する。充分な署名が集まったらwithdrawal transactionは有効になり、Bitcoinネットワークにブロードキャストする。

この際、連合はトランザクション手数料を支払わなければならない。そのためユーザに寄付をしてもらう仕組みがいくつかある（サイドチェーンでOP_RETURNの出力を作るか、直接連合のアドレスにコインを送ってもらうか）。

まとめ＆所感

Elements AlphaにはBitcoinと違ってマイニング報酬はなく、genesis blockのコインベースにあるコインが全てで、このコインベースにはBitcoinの発行総量と同じ2100万のコインがセットされている。
Federated Pegを実現するため、AlphaにはOP_WITHDRAWPROOFVERIFYとOP_REORGPROOFVERIFYという２つの新しいopcodeが追加されている。
OP_WITHDRAWPROOFVERIFYはメインチェーンからサイドチェーンに移動した資金を入手する際に使われるopcode。
OP_REORGPROOFVERIFYは、メインチェーンでロックした資金をサイドチェーン側で二重使用しようとした場合や、メインチェーン側のブロックチェーンが再構成されlocking transactionが別のブロックになったり、チェーンから消えてしまった際の対応をするためのopcode。
AlphaではOP_WPVを使ってメインチェーン側のロック状況を参照した上でサイドチェーン側のコインのアンロックしている。
BitcoinにはOP_WPVといったopcodeは無いので、連合が管理するマルチシグで代替する。
サイドチェーン側で資金を入手する際はOP_WPVによる検証が行われ、ロックされたコインを入手する出力と、再度ロックされるおつり分の出力の２つの出力を持つトランザクションを作成する。
サイドチェーン側に移動する際の二重使用や、メインチェーン側の再構成を考慮して、メインチェーンからサイドチェーンに移動したコインは、使えるようになるまでに144ブロック（24時間）かかる。
AlphaのコンセンサスはPoWではなく、連合の署名によって決められる。
サイドチェーンからメインチェーンへの移動は、サイドチェーンのコインをwithdraw lockするトランザクションを作り、それが検証され、連合の職員によりメインチェーンのBitcoinのマルチシグをアンロックするトランザクションが署名＆ブロードキャストされる。
現時点でOP_WPVはロッキングトランザクションのブロックのconfirmationの確認にbitcoindを使ってて将来的にSPV証明を利用する形になるってあるので、現状はOP_WPVのスクリプトインタプリタ内でbitcoindにRPCしてるっぽい。
SPV証明使う機能は将来的に組み込むと書かれてるけどまだ組み込まれてない？
Pay-to-Contract（P2C）の内容がよく分かってないのでホワイトペーパー読む。
OP_REORGPROOFVERIFYを使って不正の証拠を提供するって具体的にどういうデータを提供すればいいのか？