2018-06-18

ECDSAベースのScriptless Lightning Network

少し時間が空いたけど、Scriptless Scripts with ECDSAのホワイトペーパーについて

techmedia-think.hatenablog.com

と見てきたので、最後のLightning Networkへの適用について見てみる。

Lightning NetworkのベースとなるのはPayment Channelで、このPayment ChannelはBitcoinスクリプトで

タイムロック
ハッシュプリイメージのチャレンジ

を組み合わせて実装されているコントラクトだ。

↑のホワイトペーパーでは、LNの後者のハッシュプリイメージのチャレンジをマルチホップを意識してECDSAでスクリプトレスに実装するプロトコルについて説明している。基本的なハッシュプリイメージのチャレンジは↑のAdaptor Signatureのプロトコルでも利用されているが、第三者を経由するマルチホップ決済をするため、このプロトコルとは若干異なったものになる。

Scriptless Lightning Network with ECDSA

第三者を経由した決済をするHTLCを考える。この基本的な動作は↓

techmedia-think.hatenablog.com

ここでアリスがボブを経由してキャロルに送金する場合、キャロルが作成したシークレットを使ってトラストレスに三者間の決済が行われる。

（タイムロックの部分は置いといて）このハッシュプリイメージのチャレンジを3者間で行うのを、Scriptless Scriptでどう実現するかというのが課題になる。

ベースは↑のAdaptor Signatureのプロトコルで、シークレットαの取り扱いだけ変更する必要がある。Adaptor Signatureではシークレットαの値をボブが生成していたけど、これを生成するのがキャロルになり、アリスとボブは最初αの値を知らない。

アリスとボブの両者がαの値について知らない場合、Adaptor Signatureのプロトコルの手順3でRを計算できないという問題が出てくる。この問題を解決すれば残りのプロトコルはそのままで良い。

解決策を簡単に言うと、αを生成したキャロルは、楕円曲線上の点（＝公開鍵） A = g^αをアリスとボブに公開して、そのAを使ってRを計算することでこの問題を解決する。

修正されたプロトコルは以下のようになる。

アリスとボブはP1, P2, R1 = g^k1, R2 = g^k2, m', ${Q = g^{x1 \cdot x2}}$ について同意する。
ボブは ${R3 := (A)^{k2}}$ を計算し、k2の値を明らかにすることなく ${R2 = g^{k2} \land R3 = (A)^{k2} }$ のゼロ知識証明と一緒にアリスに送る。アリスも同様に ${R'3 := (g^{α})^{k1}}$ を計算し、k1の値を明らかにすることなく ${R1 = g^{k1} \land R'3 = (g^{α})^{k1} }$ のゼロ知識証明と一緒にボブに送る。
アリスは ${R \gets (R3)^{k1}}$ でRを計算し、ボブは ${R \gets (R'3)^{k2}}$ でRを計算する。計算した同じ楕円曲線上の点Rのx座標をrとする。
ボブは ${c1 \gets Enc_{pkA}((k2)^{-1} \cdot m' + pq)}$ と ${c2 \gets (ckey) \odot (x2 \cdot r \cdot (k2)^{-1})}$ を計算する。続いてボブは ${c_3 = c_1 \oplus c_2}$ を計算する。この ${\oplus}$ はPaillier暗号の加法準同型演算を表す。結果、 ${c3 = EncpkA((k2)^{-1} \cdot m' + pq + x1 \cdot x2 \cdot r \cdot (k2)^{-1})}$ となるc3をアリスに送る。
アリスはc3を復号しs'を取得する。ここでアリスはボブが暗号化中に不正行為をしていないか確認する必要がある。これは、 ${(R_2)^{s' mod q} = Q^{r} \cdot g^{m'}}$ が成立するか検証すればいい。問題なければ、 ${s'' \gets s' \cdot (k1)^{-1}}$ を計算しs''をボブに送る。
少ししてボブはペイメントパス上のキャロルから値αを得る（キャロルがボブからの送金と引き換えにαをボブに公開する）。ボブは ${s \gets (α)^{-1} \cdot s''}$ を計算し、署名(r, s)を出力する。
ボブが作成した署名が公開されると、アリスは ${α \gets (s \cdot (s'')^{-1})^{-1}}$ を計算する。

という形で、ECDSAベースでもHTLCを利用した中間者決済をするScriptless Scriptが実装できると。
（ほとんどAdaptor Signatureのプロトコルと同じなのでサンプルコードは割愛）

タイムロックの取り扱い

Payment Channelを構成するもう１つの要素がタイムロックだが、こちらはおそらくScriptless Scriptとして実装するのは難しいので、スクリプトとは別にタイムロックを担保する仕組みが必要になるだろう。

ちなみに、MimbleWimbleの最小実装をするGrinではトランザクションのタイムロックを実現するのに以下のような変更を提案している。

https://github.com/mimblewimble/grin/blob/master/doc/contracts.md

署名対象のメッセージMについて、そのトランザクションが使用可能になるブロック高をhとし手数料と結合してM = fee | hとする。
ロックするブロック高はトランザクションカーネルに含まれる。
現在のブロック高より大きいブロック高が設定されているカーネルを含むブロックはリジェクトされる。

2018-06-16

Schnorrの非対話型ゼロ知識証明（NIZKP）について定義しているrfc8235を読んでみた

Schnorr

Schnorrにおいて、ある離散対数の知識を知っていることをゼロ知識で証明するプロトコル（Schnorr NIZK proof）が2017年に~~rfc2835~~rfc8235として登録されていたので読んでみた。

RFC 8235: Schnorr Non-interactive Zero-Knowledge Proof

簡単に概要を説明すると、

証明者と検証者がいる中で、証明者がもつ離散対数の知識を検証者にその知識を明かすことなく証明するプロトコルがゼロ知識証明で、二者間で↓のようなやりとりをする。

通常は証明者が自身が証明したい離散対数に対応した公開鍵と、それとは別にランダムに選択した離散対数に対応する公開鍵を検証者に公開する。
検証者はチャレンジを生成し、それを証明者に送る。
証明者が2つの離散対数とそのチャレンジを使ってある計算をし、その計算結果を検証者に送る。
検証者はその値がと証明者から送られた公開鍵を使って証明者が離散対数の知識を知っていることを確認する。

↑は検証者が生成したチャレンジをベースに計算するので対話的な証明プロセスになってるけど、このチャレンジの生成を決定論的に行うことで（Fiat-Shamir変換）、2,3の対話が不要になり非対話型にできる。

Schnorrベースでこの非対話型のゼロ知識証明のプロトコル仕様を定義してるのがrfc2835で、有限体および楕円曲線を利用した定義がそれぞれされている↓
（でもこれSchnorr限定というものではなく、使われてる計算はそのままECDSAでも成立するよね。）

以下RFCの定義内容の意訳。

1. イントロダクション

堅牢な公開鍵プロトコルを設計するためのよく知られている法則は

「チェックが出来ない場合、受け取ったメッセージが特定の形式（例えば既知のrに対するg^rのように）を持っていると仮定しないこと。」

これはCrypto '95でRoss AndersonとRoger Needhamによって定義された８つの原則の６つめの原則で、「sixth principle」として知られている。過去３０年の間に、多くの公開鍵プロトコルが、この原則に違反によって、攻撃を防ぐことができなかった。

「sixth principle」を満たすのにいくつか方法があるが、ここでは値を明らかにすることなく、その離散対数の知識を知っていことを証明する１つの技法について説明する。この技法はSchnorr NIZK proofと呼ばれ、three-pass Schnorr identification schemeを非対話型に変形したものだ。安全な暗号学的ハッシュ関数が存在する仮定のもと、オリジナルのSchnorr identification schemeはFiat-Shamir変換によって非対話型になる。

Schnorr NIZK proofは有限体もしくは楕円曲線で実装できる。基底の巡回群が異なることを除いて、技術仕様は基本的に同じだ。完全性を期すため、この文書では有限体と楕円曲線両方のSchnorr NIZK proofについて説明する。

2. 有限体上のSchnorr NIZK proof

2.1 グループパラメータ

有限体上で実装された場合、Schnorr NIZK proofはDSAと同じグループ設定を使用できる。pとqを2つの大きな素数とする（q | p - 1）。Gqを素位数qのZqの部分群とし、gを部分群の生成元とする。異なるセキュリティレベルを提供する(p, q, r)の値については、NIST Cryptographic Toolkitのサンプルを参照。128 bit以上のセキュリティレベルが推奨される。ここではDSAグループは例としてのみ使用されている。離散対数問題（DLP）が扱いにくい他の乗法群もSchnorr NIZK proofの実装に適している。

2.2 Schnorr Identification Scheme

Schnorr identification schemeのルールはアリス（証明者）とボブ（検証者）の間で対話的に実行される。スキームのセットアップにおいて、アリスは自身の公開鍵A = g^a mod pを公開する。ここでaは[0, q-1]からランダムに一様に選択された秘密鍵。

プロトコルは以下の3つをパスすることで動作する。

アリスは[1, q-1]の中からランダムに一様にvを選択し、V = g^v mod pを計算する。そして計算したVをボブに送る。
ボブは[1, t-1]からランダムに一様にチャレンジcを選択する。ここでtはチャレンジのビット長（例えば t = 160）。ボブは選択したcをアリスに送る。
アリスはr = v - c * a mod nを計算し、結果をボブに送る。

ボブはプロトコルに最後に以下のチェックを行う。いずれかのチェックが失敗すると、同定は失敗する。

Aが[1, p-1]内にあり、A^q = 1 mod pであることを検証する。
V = g^r * A^c mod pを検証する。

最初のチェックは、Aが有効な公開鍵であることを保証するので、基底gに対するAの離散対数は実在する。一部のアプリケーションでは、アイデンティティ要素を有効な公開鍵として明確に除外することがある点については注意する価値がある。その場合、Aが[1, p-1]内にあるかの代わりに[2, p-1]内にあるかチェックする必要がある。

プロセスは以下の図のようにまとめられる。

2.3 非対話型ゼロ知識証明

Schnorr NIZK proofは、Fiat-Shamir変換を介して非対話型のSchnorr identification schemeが得られる。この変換には、チャレンジを発行する代わりに安全な暗号学的ハッシュ関数の使用が含まれる。より具体的には、チャレンジはc = H(g || V || A || UserID || OtherInfo)として再定義される。ここでUserIDは証明者の一意の識別子でOtherInfoはOPTIONALデータである。ここでハッシュ関数HはSHA-256、SHA-384、SHA-512、SHA3-256、SHA3-384、またはSHA3-512などの安全な暗号ハッシュ関数とする。ハッシュのアウトプットのビット長は少なくともサブグループの位数qのビット長と同じでなければならない。

OtherInfoは、Schnorr NIZK proofにコンテキスト情報を柔軟に含めることができるよう定義されているため、このドキュメントで定義されている手法は一般的に有用だ。例えば、 Schnorr NIZK proof上に構築されたいくつかのプロトコルの中には、プロトコル名やタイムスタンプなどより多くのコンテキスト情報を含めるものもある。OtherInfoの正確な項目は、定義する特定のプロトコルに任されなければならない。ただし、特定のプロトコルにおいてOtherinfoは固定され、プロトコルで明示的に定義されていなければならない。

ハッシュ関数内では、連結される2つの項目の間に明確な境界が存在する必要がある。その項目のバイト長を表す4バイトの整数を常に項目の先頭に付与することが推奨される。OtherInfoには複数の副項目が含まれる場合がある。その場合、隣接する副項目間の明確な境界を保証するため同じルールが適用されるものとする。

2.4 計算コスト

要約すると、A = g^aの指数の知識を証明するため、アリスは{UserID, OtherInfo, V = g^v mod p, r = v - a*c mod q}を含むSchnorr NIZK proofを生成する。ここでcはc = H(g || V || A || UserID || OtherInfo)。

Schnorr NIZK proofを計算するコストは、およそ1つのモジュロ累乗、すなわちg^v mod pの計算だ。実際には、この冪乗は効率を最適化するためオフラインで事前にされてもいい。残りの演算（乱数生成、剰余乗算、ハッシュ計算）コストは冪乗剰余と比較して無視できる。

Schnorr NIZK proofを検証するコストは、およそ2つの累乗で、1つはA^q mod pの計算で、もう1つはg^r * A^c mod pの計算。

3. 楕円曲線を利用したSchnorr NIZK proof

3.1 グループパラメータ

楕円曲線上に実装すると、Schnorr NIZK proofはECDSAと同じ楕円曲線の設定を使うことがある。説明目的のため、プライムフィールド上の曲線のみ（NIST P-256など）をここで説明する。Schnorr NIZK proofの実装には、ECDSAに適したバイナリフィールド以外の曲線を使うことも可能だ。E(Fp)を有限体Fp上で定義される楕円曲線とする。ここでpは巨大な素数。続いてGを素数位数nのE(Fp)に対する部分群のジェネレータとして機能する曲線上の基点とする。部分群の余因子（cofactor）はhで示され、通常は４以下の小さな値。加算やマイナス、スカラ乗算などの楕円曲線の演算の詳細については、Handbook of Applied Cryptographyを参照。 elliptic-curve-point-to-octet-stringを含むデータ型の変換は、SEC1の2.3節参照。ここではNISTの曲線を一例として使う。楕円曲線の離散対数問題が簡単に解けない限り、Curve25519などの他の安全な曲線も実装に適している。

3.2 Schnorr Identification Scheme

スキームのセットアップにあたり、アリスは秘密鍵aを[1, n-1]の中からランダムに選択し、公開鍵A = G × [a]を公開する。

プロトコルは以下の３つのやりとりで動作する。

アリスは[1, n-1]の中からランダムな数値vを選択し、V = G × [v]を計算し、Vをボブに送る。
ボブはチャレンジcを[1, t-1]からランダムに選択する。ここでtはチャレンジのビット長（例えば t = 80）。ボブは選択したcをアリスに送る。
アリスはr = v - c * a mod nを計算し、結果をボブに送る。

プロトコルの最後に、ボブは以下のチェックを行う。いずれかのチェックに失敗した場合、検証は失敗する。

Aが楕円曲線上の有効な点であり、A × [h]が無限遠点でないことを検証する。
V = G x [r] + A x [c]が成立するか検証する。

最初のチェックは、基底Gに対するAの離散対数が実際に存在することの確認＝Aが有効な公開鍵であることを保証する。ECDSAのような設定は、公開鍵の検証に完全な冪剰余が必要なDSAのようなグループ設定と異なり、公開鍵の検証コストは余因子が小さいため（1,２もしくは４など）ほとんど無視できる。

プロセスをまとめると以下のようになる。

3.2 非対話型ゼロ知識証明

これまでと同様、チャレンジを発行する代わりに安全な暗号学的ハッシュ関数を使用することで、Fiat-Shamir変換により非対話型になる。チャレンジcはc = H(G || V || A || UserID || OtherInfo)として定義され、UserIDは証明者の一意な識別子で、OtherInfoは前述したようにOPTIONALデータである。

3.3 計算コスト

まとめると、楕円曲線上の基底Gにに関してA = G × [a]の離散対数の知識を証明するため、アリスは{UserID, OtherInfo, V = G x [v], r = v - a*c mod n}を含むSchnorr NIZK proofを生成する。cはc = H(G || V || A || UserID || OtherInfo)。

Schnorr NIZK proofを生成するためのコストは、１つのスカラ乗算G x [v]をするコストになる。

楕円曲線の設定でSchnorr NIZK proofの検証をするコストは、楕円曲線に対して１つの乗算、つまりG x [r] + A x [c]を計算するコストになる。楕円曲線の設定において、公開鍵検証のコストは本質的にフリーだ。

4. Schnorr NIZK proofのバリエーション

有限体の設定では、証明者は（UserIDとOtherInfoと一緒に）(V, r)を送信し、検証者は最初にcを計算し、続いてV = g^r * A^c mod pをチェックする。これは2048〜3072 bitのサイズのZpの要素Vと、224〜256 bitのサイズのZpの要素rの伝送を必要とする。以下のように、Zpの２つの要素に送信するデータを以下のように削減することができる。

修正版は、証明者が(V, r)の代わりに(c, r)を送信すること以外は同じように動作する。検証者はV = g^r * A^c mod pを計算し、H(g || V || A || UserID || OtherInfo) = cが成立するかチェックする。この変形例のセキュリティは、(c, r)からVを、(V, r)からcを計算することができるという事実に従う。したがって、(c, r)を送信することは(V, c, r)を送信することと同じで、それは(V, r)を送信することと同じだ。このためSchnorr NIZK proofのサイズは大幅に削減でき、証明者と検証者の計算コストは同じままである。

(V, r)の送信を(c, r)の送信に置き換えることで、同様の最適化手法を楕円曲線を使った設定にも適用できるが、利点は限定的になる。Vが圧縮形式でエンコードされると、この最適化により削減できるサイズは1 bit分のみであるためで、ゼロ知識証明の生成および検証の計算コストは以前と同じだ。

5. Schnorr NIZK proofの応用

J-PAKEやYAKのようないくつかの主要な交換プロトコルでは、参加者が離散対数の知識を持っていることを保証するためにSchnorr NIZK proofに依存している。このドキュメントに記載されている技法は、それらのプロトコルに直接適用することができる。

OtherInfoを含めることで、 Schnorr NIZK proofは幅広い応用に対応するため一般に便利で柔軟性がある。例えば記載されている技術は、ユーザーが公開鍵登録期間中、秘密鍵の証明を証明期間に示すのに使うことができる。ハッシュにはある鍵の登録手順にリンクされているデータが含まれていることが保証されなければならない（OtherInfo内に、CA名、有効期間、申請者の電子メールの連絡先など）。この場合Schnorr NIZK proofは、DSAもしくはECDSAを使って生成されたCSRと機能的に同等だ。

6. セキュリティに関する考慮事項

Schnorrの同定プロトコルは、検証者が正直で離散対数問題の困難性という仮定のもと、以下の特性を満たすことが証明されている。

完全性
離散対数を知っている証明者は常に検証チャレンジに合格できる。
健全性
離散対数を知らない敵対者が、検証チャレンジに合格する確率は無視できるレベルしかない（2^-t）。
正直な検証者のゼロ知識性
証明者は正直な検証者に、自身が離散対数を知っているかどうか1 bitも情報を漏らさない。

Fiat-Shamir変換はセキュアな暗号学的ハッシュ関数が存在すると仮定した上で、three-pass対話型のゼロ知識証明プロトコルを（検証者がランダムにチャレンジを選択する）非対話型プロトコルに変換する標準的な手法だ。ハッシュ関数は公に定義されているので、証明者は単独でチャレンジを計算することができ、プロトコルを非対話型にすることができる。この場合、証明者が送信した各コミットメント（g^v もしくは G x [v]）に、一様にランダムにチャレンジcを割り当てるため、ハッシュ関数（正確にはセキュリティ証明のランダムオラクル）は正直な検証者を実装する。これはまさに正直な検証者がやることだ。

Schnorrの同定スキームと非対話型の要素には、安全な乱数生成器が必要なことに注意することが重要だ。特に、vのランダム精度が低いと秘密の離散対数が明らかになる。例えば、（ランダム値の生成に失敗して）同じランダム値 V = g^v mod p が証明者によって2回使われたとする。そして検証者が異なるチャレンジ c と c' を選択する（もしくは、2つの異なるOtherInfo dataにハッシュ関数が使われ、2つの異なるチャレンジ c と c' を生成する）。敵対者は2つの証明トランスクリプト（V, c, r）と（V, c', r'）を観察して、以下のように秘密鍵を計算する。

(r-r')/(c'-c) = (v-a*c-v+a*c')/(c'-c) = a mod q.

より一般的には、このような攻撃は、同じvが生成されることはないが敵対者にとって既知の値wに対してv' = v + wという関係が成り立つvとv'を生成するような、やや精度の良い（でも安全ではない）乱数生成器でも機能する。敵対者が2つの証明トランスクリプト（V, c, r）と（V, c', r'）を観察すると仮定すると、敵対者は以下のように秘密鍵を計算することができる。

(r-r'+w)/(c'-c) = (v-a*c-v-w+a*c'+w)/(c'-c) = a mod q

この例は、Schnorrのスキームで一時的なシークレットvを生成するのに安全な乱数生成器を使用することの重要性を強調している。

最後に、セキュリティプロトコルが非対話的な方法で離散対数の知識を証明するSchnorr NIZK proofに依存する場合、リプレイ攻撃の脅威が考慮される。例えばSchnorr NIZK proofは（暗号プロトコルで項目間に好ましくない相関関係を導入するため）証明者自身にリプレイバックされる可能性がある。この特定の攻撃はハッシュに一意のUserIDを含めることで防止される。検証者は証明者のUserIDが有効なアイデンティティで自身のものと異なることを確認しなければならない。特定のプロトコルのコンテキストによって、他の形式のリプレイ攻撃について考慮し、必要に応じてOtherinfoに適切なコンテキスト情報を含める必要がある。

2018-06-09

再利用可能なペイメントコードを使った二者間の決済アドレスの導出方法を定義したBIP-47

BIP Bitcoin

BIP-47の記事無いですよね？と突っ込まれたので書いてみた。
（結構前に書かれたBIPでメジャーでないものとか導入されなかったコンセンサスのBIPについては書けてない。今BIPとして登録されてるのが115個くらいで、ブログに投稿したのは、そのうち50個くらい）

Bitcoinではブロックチェーン上に個人を特定する情報が記録されることは無いが、外的要因によりアドレスと個人の関連が分かると、個人がどのような決済をしているのかが分かるようになりプライバシー上好ましくない。このため決済毎に異なるアドレスの使用が推奨されている。ただこの場合プライバシーという点では好ましいが、例えば対外的に自分のアドレスを公開したい場合には不便だ。こういうケースにおいて、代表アドレスは公開するがそのアドレス宛の送金を送金者本人は分かるが第三者はそこにいくらの送金がされたのか分からなくするステルスアドレスという仕組みが2014年くらいに提案された。

BIP-47のペイメントコードはこのステルスアドレスに似たコンセプトのBIPで、2015年に公開された。

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

概要

このBIPは、P2PKHアドレスの再利用において固有のセキュリティまたプライバシーの損失を発生させることなく、現実世界のアイデンティティと関連付けられ公に公開されるペイメントコードを作成するための方法を定義している。このBIPはBIP-43の応用で、BIP-44を実装しているHDウォレットを補完することを目的としている。

動機

ペイメントコードとは売り手と顧客の対話において有用で、顧客のプライバシーを保護しながらトランザクションに識別情報を追加する。ペイメントコードは、信頼できるフルノードなしにダークウォレットスタイルのステルスアドレスのプライバシー上の利点をSPVクライアントに提供し、ブロックチェーンストレージへの依存度を大幅に削減する。

パス階層

BIP-32のパスについて以下の３つの階層を定義する。

m / purpose' / coin_type' / identity'

identityから導出した子鍵はいろんな方法で使われる。

m / purpose' / coin_type' / identity' / 0

（非強化鍵の）0番めの子鍵は通知鍵になる。

m / purpose' / coin_type' / identity' / 0 から 2147483647

これらの（非強化鍵）鍵ペアはECDHのためのデポジットアドレスを生成するのに使われる。

m / purpose' / coin_type' / identity' / 0' through 2147483647'

これらの（強化鍵）鍵ペアは一時的なペイメントコード。

パスのアポストロフィー（'）はBIP-32の強化導出が使われていることを示している。

各階層には以下で説明する特別な意味がある。

purpose

purposeはBIP-43のルールに従い、47 '（0x8000002F）が設定される。これはこのノードのサブツリーがこの仕様に従って使用されることを示す。

coin_type

coin_typeフィールドはBIP-44と同じフィールド。

この階層では強化導出が使われる。

identity

identityの導出階層では、拡張公開鍵およびそれに関連する拡張秘密鍵を生成する。

この階層の拡張公開鍵が以下の表現セクションで指定されたメタデータと組み合わされた結果がペイメントコードになる。

この導出階層はBIP-44のアカウントと同じ階層だ。ウォレットはペイメントコードを同じインデックスのBIP-44のアカウントの一部として扱い、ペイメントコードとアカウントをペアで作成すべきである。

例えば(m / 47' / 0' / 0')で表されるペイメントコードは、(m / 44' / 0' / 0')で表されるアカウントの一部になる。

ウォレット内の２つめのアカウントは、index 1を使って作成される新しいアカウント/ペイメントコードのペアで構成される。

この仕様を介して受け取った入金は、BIP-44で受信した支払いと同等で、両方のタイプのアドレスの未使用アウトプットを同じ送金トランザクションのインプットとして使用できる。

この階層では強化導出が使われる。

特に明記されていない限り、ペイメントコードから導出された全ての鍵は、公開導出メソッドを使用する。

バージョン

ペイメントコードには特定の動作セットを識別するバージョンバイトが含まれている。

他に指定されていない限り、異なるバージョンのペイメントコードは相互運用可能だ。アリスがバージョンxのペイメントコードを使い、ボブがバージョンyのペイメントコードを使っている場合でも、お互いの間でトランザクションを送受信できる。

現在、以下のバージョンが定義されている。

バージョン１
- アドレスタイプ：P2PKH
- 通知タイプ：アドレス
バージョン2
- アドレスタイプ：P2PKH
- 通知タイプ：bloom-multisig

推奨されるバージョン

ブルームフィルタリング機能を備えたウォレットは、バージョン１のペイメントコードの代わりにパージョン２のペイメントコードを使用すべき。
バージョン１のペイメントコードはブルームフィルタリング機能にアクセスできないウォレットにのみ推奨される。

バージョン１

表現

バイナリシリアライゼーション

ペイメントコードには以下の要素が含まれる。

Byte 0：バージョン。必須値：0x01
Byte 1：feature bitフィールド。この仕様の他の箇所で指定されていない限り全てのbitは０。
- Bit 0: Bitmessageの通知
- Bit 1-7: 予約値
Byte 2: 符号。必須値で0x02 or 0x03
Byte 3-34: x値。secp256k1グループのメンバーであること。
Byte 35-66: chain code
Byte 67-79: 将来の拡張用の予約値。特に明記されていない限り０埋め。

Base58シリアライゼーション

ペイメントコードがユーザーに提示される時は、Base58Check形式でエンコードされて提示される必要がある。

バージョンバイトは、0x47（シリアライズされた最初の文字はPになる）
ペイロードはペイメントコードをシリアライゼーションしたバイナリ

プロトコル

以下の例では、アリスとボブは対応ペイメントコードを持つアイデンティティで、アリスがBitcoinトランザクションの送信者でボブが受信者である。

アリスはペイメントコードのプロトコルの範囲外で、適切な方法でボブのペイメントコードを容易に入手できるものと仮定する。

定義

ペイメントコード：特定のidentity/accountに関連付けられた拡張公開鍵およびメタデータ
通知アドレス：ペイメントコードから導出された0番目の公開鍵に関連付けられたP2PKHアドレス
通知トランザクション：埋め込まれたペイメントコードを含む通知アドレスに送金するトランザクション
指定インプット：通知トランザクションの最初のインプットで、そのインプットが参照するアウトプットのpubkey scriptもしくはインプット内のredeem script、signature scriptのいずれかにあるsecp256k1の公開鍵を公開する。
指定公開鍵：指定インプットのスクリプトの評価中にスタックにプッシュされる最初のsecp256k1公開鍵
Outpoint：消費される前のトランザクションの特定のアウトプット。バイナリのシリアライゼーションについてはReferenceセクション参照。

通知トランザクション

アリスが最初にボブと取引を開始する前に、アリスは以下の手順でボブにペイメントコードを通知しなければならない。

※ この手順は（アリスのペイメントコードのバージョンに関係なく）ボブがバージョン1のペイメントコードを使用する場合に使われる。ボブのペイメントコードがバージョン1でない場合は、別の適切なセクションを参照。

アリスは少量のコインをボブの通知アドレスに送金するトランザクション（通知トランザクション）を構築する。
1. このトランザクションのインプットは、アリスの通知トランザクションと簡単に関連付けられないアドレスにしなければならない。
アリスはECDHを使ってユニークな共有シークレットを作成する。
1. アリスは指定公開鍵に対応する秘密鍵を選択する。
  a
2. アリスはボブの通知アドレスに関連付けられた公開鍵を選択する。
  B, ここでBはB = bG
3. アリスはシークレットポイントを計算する。
  S = aB
4. アリスは64バイトのblinding factorを計算する。
  s = HMAC-SHA512(x, o)
  - xはシークレットポイントSのx座標
  - oは指定インプットが指すOutpoint
アリスは自身のペイメントコードをバイナリ形式でシリアライズする。
アリスは自身のペイメントコード（P）をボブ以外誰も読めないようにする。
1. xをx'に置き換える
  x' = x XOR (sの先頭32バイト)
2. chain codeをc'に置き換える
  c' = c XOR (sの最後32バイト)
アリスはPを構成するOP_RETURNアウトプットをトランザクションに追加する。

ここからボブのターン。

ボブは通知アドレス宛の送金トランザクションを監視する。
トランザクションを受信すると、クライアントは80バイトのペイロード（通知トランザクション）を持つ標準のOP_RETURNが含まれるかチェックする。
通知トランザクションのペイロードの最初のバイトが0x01の場合
1. ボブは指定公開鍵を選択する。
  A、ここでAは A = aG
2. ボブは通知アドレスに関連する秘密鍵を選択する。
  b
3. ボブはシークレットポイントを計算する。
  S = bA
4. ボブはblinding factorｗを計算する。
  s = HMAC-SHA512(x, o)
  - xはシークレットポイントSのx座標
  - oは指定インプットが指すOutpoint
5. ボブは80バイトのペイロードをペイメントコードとして解釈する。以下の除いて
  1. xをx'に置き換える
    x' = x XOR (sの先頭32バイト)
  2. chain codeをc'に置き換える
    c' = c XOR (sの最後32バイト)
6. 更新されたx値がsecp256k1グループのメンバーである場合、ペイメントコードは有効。
7. 更新されたx値がsecp256k1グループのメンバーでない場合、ペイメントコードは無視される。

ボブのクライアントがアリスのペイメントコードを受け取ったので、アリスはボブに支払いができる（最大2³²回）。

アリスはボブに再度通知トランザクションを送る必要はない。

通知トランザクションを介して受信したビットコインは、プライバシー漏洩を避けるため特別な処理が必要になる。

通知アドレス宛に受信されたアウトプットの値は、消費可能な残高の一部としてユーザーに表示されてはならない。
通知アドレス宛に受信されたアウトプットはユーザーのペイメントコードのいずれかを使ってECDH計算をするトランザクションのインプットとして使ってはならない。
通知アドレス宛に受信されたアウトプットは、ユーザーの消費可能残高に追加される前に、ミキシングサービスを通貨することもできる。
通知アドレス宛に受信されたアウトプットは、dust-b-goneもしくは同等の手順でマイナーに寄付することができる。

通知トランザクションの標準スクリプト

アリスは公開鍵を公開するのに以下のいずれかの形式のインプットスクリプトを使用する必要があり、準拠するアプリケーションはこれらの全ての形式を認識すべきだ。

P2PK
P2PKH
マルチシグ（P2SHではない素の）
上記スクリプト形式のいずれかをP2SH形式で使うスクリプト

互換性のあるウォレットは、非標準の通知トランザクションを介して送信されたペイメントコードをリカバリするために、通知トランザクションに関連付けられた公開鍵をユーザーが手動で設定する方法を提供してもいい。

通知後のプライバシーに関する考慮事項

通知トランザクションのお釣りアウトプットの軽率な処理は、意図しないプライバシーの損失を引き起こす可能性がある。

前の通知トランザクションのお釣りのアウトプットを消費するトランザクションの受信者は、通知トランザクションの送信者と受信者間の潜在的な接続について学習する。

このリスクを軽減するために、以下の処理を推奨する。

ミキシングをサポートするウォレットは、そのお釣りを使用する前にミキシングすべきだ。
ミキシングをサポートしていないウォレットでは、お釣りのアウトプットを次のBIP-44の外部アドレスに送信するトランザクションを作成することでミキシングをシミュレートできる。

送金

アリスはボブへの送金の度に、以下のようにECDHを使って一意のP2PKHアドレスを導出する。
1. アリスは自分のペイメントコードから導出した0番目の秘密鍵を選択する。
  a
2. アリスはボブのペイメントコードから導出した（0から順に導出）次の未使用の公開鍵を選択する。
  B、ここでBは B = bG
  1. 次の未使用の公開鍵は、アリスまたはボブのいずれにもグローバルなものでなく、アリス−ボブ間のコンテキスト固有のもの。
3. アリスはシークレットポイントを計算する。
  S = aB
4. アリスはSのx座標を使ってスカラー共有シークレットを計算する。
  s = SHA256(Sx)
  1. sの値がsecp256k1グループに無い場合、アリスはボブの公開鍵を取得するために使用されたインデックスをインクリメントして再試行する必要がある。
5. アリスはスカラー共有シークレットを使って、このトランザクションのP2PKHアドレスを生成するために使われる一時的な公開鍵を計算する。
  B' = B + sG

ここからボブのターン

ボブはアリスから通知トランザクションを受け取って以降、B'への入金を監視している。
1. ボブはアリスのペイメントコードから導出された0番目の公開鍵と、ボブのペイメントコードから導出された秘密鍵0〜n（nは希望する先読みの幅）を使ってアリストのn個の共有シークレットを計算する。
2. ボブはアリスと同様の手順で、一時的な入金アドレスを計算する。
  B' = B + sG
3. ボブは各一時アドレスの秘密鍵を以下のように計算する。
  b' = b + s

払い戻し

ボブは決済の過程でアリスのペイメントコードを知っているので、ボブはアリスに払い戻しを行うのに必要な情報をすべて持っている。

払い戻しのトランザクションは支払いのトランザクションと同じだが、参加者の役割だけが切り替わる。

たとえボブが過去にアリスから通知トランザクションを受け取っていたとしても、ボブはアリスに資金を送る前にアリスに通知トランザクションを送らなければならない。

匿名支払い

アリスが自分のアイデンティティと関連付けられることになるボブへの支払いを行いたくない場合は、アリスは取引に使用する一時的なペイメントコードを作成することができる。

一時的なペイメントコードは、インデックス0から始まるペイメントコードの強化された子鍵である。
一時的なペイメントコードは、単一の支払いに対してのみ使われるべきである。
一時的なペイメントコードの通知アドレスは、払い戻しを検知するため監視されなければならない。
BIP-44のアカウントと一時的なペイメントコードの対応は1対多になる。

コールドストレージ

従来の監視専用のウォレットと違い、ペイメントコードと関連付けられたコールドストレージに保管されているウォレットは、入金をすぐに検知することはできない。
監視専用のウォレットは通知トランザクションを検知すると、そのトランザクションをオフラインデバイスへの転送に適した実装固有の形式にパッケージする。
オフラインデバイスはペイメントコードをリカバリし、エアギャップのラウンドトリップの必要性を最小限に抑えるため、多数の関連するキーペア（例えば1000個）を事前に生成する。
オフラインデバイスは関連する公開鍵をオンラインデバイスへの転送に適した実装固有のフォーマットでパッケージする。
オンラインデバイスは適切なlookahead幅で入金を監視することができる。
lookahead幅が予め生成された公開鍵の終わりに達すると、ユーザーはオフラインデバイス上でさらに多くの鍵を生成し、それらをオンラインデバイスに転送する必要がある。

ウォレットのリカバリ

ペイメントコード対応のウォレットの通常操作はSPVクライアントで実行でき、ブロックチェーンの完全なコピーへのアクセスは必要ない。

ただしシードからウォレットをリカバリするには、フルインデックスのブロックチェーンにアクセスする必要がある。

必要なデータは、ユーザーの制御下にあるブロックチェーンのコピーか、または公開されているブロックチェーンエクスプローラを介して取得できる。

公開されているブロックチェーンエクスプローラを使用する場合、ウォレットはTorを介してエクスプローラに接続し、一時的なアドレスを互いに関連付けるようなクエリをグルーピングするのを避けること。

以前の使用可能な資金は一般的にシードからリカバリした後、アクセス不能になることはないが、以前の出金に関する情報は全て失われる。

シードから受け取った資金をリカバリするには、通知アドレス宛に送られたトランザクションを（使用済みのもの含めて）全て入手する必要がある。ユーザーが指定した数分未使用の通知アドレスが連続して登場するまで、各導出アドレスを順次走査することで、各サブチェーンのlookahead幅を再確立する。

ウォレットが送信するトランザクションを適切に処理するため格納する必要があるメタデータは以下のように構成される。

identityが通知トランザクションを送信したすべてのペイメントコードのリスト
1. ウォレットがシードからリカバリされた場合、このリストは失われる。
2. リカバリされたウォレットは、新しく作成されたウォレットであるかのように通知トランザクションを送信しなければならない。
前のリストの各ペイメントコードの次の未使用公開鍵に対応するインデックス値
1. このインデックス値は、順番に一時的なデポジットアドレスをチェックすることをリカバリ可能。
2. ウォレットはこのリカバリ操作中にギャップを検出できるlookahead幅を使ってもいい。
未使用の一時的なペイメントコードのインデックス値
1. 一時的なペイメントコードに関連するすべての入金を100%確実にリカバリするためには、潜在的な一時的なペイメントコードのアドレス空間2³²を使い果たす必要がある。
  1. ほとんどの場合、フォールバックディープスキャンがオプションで利用可能である限り100%未満の確実性が許容される。
2. ウォレットは関連する資金をリカバリするために、通知トランザクションの各一時ペイメントコードの通知アドレスをチェックする。
3. ほとんどの一時ペイメントコードは払い戻しトランザクションを受け取らないので、ウォレットはこのリカバリのために大きなlookahead幅を使うべきだ。
4. リカバリされた値は、通知トランザクションで受信した任意の一時ペイメントコードよりも高い値が選択されてなければならない。

ウォレットの共有

ペイメントコードを使用するウォレットは、通常各インスタンス間でメタデータを同期する必要があるため、複数のデバイス間で共有するべきではない。

ウォレットが同期メカニズムなしでデバイス間で共有される場合、望ましくないアドレスの再利用が発生する可能性がある。

ウォレットはトランザクションを送信する前に一時的なデポジットアドレスのトランザクションが既にないか、ブロックチェーンのローカルコピーをチェックするか、Torまたは同等の機能を介してパブリックブロックチェーンエクスプローラに問い合わせることでチェックすることがある。

別の通知方法

受信者がシードからウォレットをリカバリしないといけない場合に、資金が失われないことを保証するために、送信者は最初に特定の受信者とやりとりをする時に通知トランザクションを送信しなければならない。

受信者は通知トランザクション以外に送信者が使用できる代替の方法を指定することもできる。

受信者が別の通知方法を指定する場合、準拠している実装では、通知アドレスを継続的に監視することを控えてもいい。ただ代替方法を使用できないユーザーからの支払いを検出する必要があるため通知アドレスは定期的にチェックする必要がある。

受信者はfeature byte内のビットを適切にセットすることで、代替通知の優先度を指定する。

Bitmessageの通知

Bitmessage経由で通知を受け取ることを希望する受信者は、以下の設定をする。

feature byteのビット0を1に設定する。
シリアライズされたペイメントコードの67バイトめを希望するBitmessageのアドレスバージョンに設定する。
シリアライズされたペイメントコードの68バイトめを希望するBitmessageのストリーム番号に設定する。

送信者はこれらの情報を使って有効な通知Bitmessageアドレスを構築する。

Bitmessageの署名鍵を以下のように導出する。

B = payment code / 0 / 0

カウンターを1に初期化する

候補暗号鍵を導出する。

B' = payment code / 0 / n

BとB'を組み合わせて有効なBitmessageアドレスを形成出来ない場合は、nをインクリメントして再度試みる。
Bitmessageプロトコル毎にBitmessageアドレスを構成するために、アドレスバージョン、署名鍵、暗号鍵、ストリーム番号を使用する。

送信者はbase58形式の自分のペイメントコードをBitmessageアドレスに送信する。

Bitmessage通知を使用するには、送信者が導出したBitmessageアドレスを見てるBitmessageクライアントを受信者が持ち、受信したペイメントコードをBitcoinウォレットにリレーできる必要がある。

バージョン2

バージョン2のペイメントコードは下記の変更を除いてバージョン1と同じように動作する。

表現

バイナリシリアライゼーション

Byte 0：バージョン。必須値：0x02

プロトコル

定義

通知のお釣り用アウトプット：通知トランザクションのお釣り用のアウトプットは送信者のウォレットにあるが、意図された受信者によって自動的に配置される。
ペイメントコード識別子：バイナリシリアライゼーションしたペイメントコードのSHA-256ハッシュに0x02を付与して構成されたペイメントコードの33バイト表現

通知トランザクション

※ この手順は、（アリスのペイメントコードに関わらず）ボブがバージョン2のペイメントコードを使っている場合に使用される。ボブのペイメントコードがバージョン2でない場合はこの仕様の別のセクションを参照。

ボブの通知アドレスを作成しないことを除いて、バージョン1と同様に通知トランザクションを構築する。
以下のように通知のお釣り用アドレスを作成する。
1. 次のお釣り用アドレスに対応する公開鍵を入手する。
2. 以下の形式のマルチシグアウトプットを作成する。
  OP_1 <ボブのペイメントコード識別子> <お釣り用アドレスの公開鍵> OP_2 OP_CHECKMULTISIG

上記スクリプトにおけるペイメントコード識別子とお釣り用アドレスの公開鍵の相対的な順序はランダム化されてもいい。

ボブはブルームフィルタに自身のペイメントコード識別子を追加することで、通知トランザクションを検知する。

フィルタが通知トランザクションを返すと、バージョン1の通知トランザクションと同様の手順で、送信者のペイメントコードがアンブラインドされる。

アリスのウォレットは次の適切な機会に通知トランザクションのお釣り用アウトプットを消費する必要がある。

Test Vector

BIP47 Reusable Payment Codes Test Vectors

参照

まとめ＆所感

BIP-47は相手のペイメントコードと自分のペイメントコードを使ってECDHで各決済用のアドレスを導出するプロトコルと、ペイメントコードの交換プロトコルを定義したものになってる。

BIP-47ではBIP-32のHDウォレットでまずペイメントコードを作成するための拡張公開鍵を導出する。ペイメントコードとはこの拡張公開鍵にメタデータ（↑のバイナリシリアライゼーション参照）を組み合わせたコードのこと。この拡張公開鍵の直下の階層の0番目の導出鍵を使って生成したP2PKHアドレスが通知アドレスで相手とBIP-47を利用した決済をする際に最初の1回だけこの通知アドレス宛に通知トランザクションを送信する際に使われる。

BIP-47準拠のウォレットを持つユーザー間は、相手が公開している通知アドレス宛に通知トランザクションを送信する（送信者はすでに何らかの外的要因により相手のペイメントコードを知っている状態から始まる）。この通知トランザクションで、送信者自分のペイメントコードをOP_RETURNにセットして送るが、このとき自分のペイメントコードはblinding factorと、自分の秘密鍵と相手の公開鍵を利用してECDHで導出した共有シークレット用いて受信者にしか分からないようになっている。

通知トランザクションで一度、送信者と受信者の間でペイメントコードが交換されたら、後はそれを使って各決済毎にアドレスを導出することができる。なので通知トランザクションを送るのは最初の1回だけ。各決済の際は、相手のペイメントコードから導出した両者の間で未使用の公開鍵を導出し、自分のペイメントコードから新しい秘密鍵を導出してECDHで共有シークレットを導出する。共有シークレットから生成した楕円曲線上の点を未使用の公開鍵と加算してできた点を公開鍵として、その公開鍵から導出したP2PKHアドレス宛に送金をする。

所感

決済毎にアドレスを変更する前提で、同じ相手と複数回決済するケースであれば、一度相手とペイメントコードを交換してしまえば後は決済の度に相手からアドレスを提供してもらう必要がないので、そこのインタラクションは必要なくなって決済毎のアドレスが簡単に導出できる。逆に一度だけの決済であれば通知トランザクションを送信する分手数料が無駄になるので意味は無さそう。
通常のHDウォレットはシードからウォレットをリカバリするけど、BIP-47で同様のリカバリをする場合SPVノードであってもフルノードのチェーンへのアクセスして通知トランザクションの走査が必須になる。リカバリ処理が少し複雑なのでウォレットの実装は面倒くさそう。
ステルスアドレスの仕様は結局BIPにはならなかったけど、BIP-47はBIPとしてSamourai WalletやBilioon appとかStashとか対応するウォレットもちらほらある。

あと、以下のような懸念の声もあるみたいね。

[bitcoin-dev] [Bitcoin-development] Reusable payment codes

通知アドレスの再利用により少量コインが乗ったUTXOが大量に集まり放置されることで、UTXOセットの膨張になる可能性があるため、通知アドレスを再利用するのではなくOP_RETURNに相手のペイメントコードのハッシュと自分のペイメントコードを暗号化したデータを入れた方が良いという内容。受信者は前者によりブルームフィルタによりトランザクションが検知可能。この場合OP_RETURNなのでUTXOセットが膨張することも無いと。

2018-06-02

秘密鍵が対応するBitcoinアドレスの種類を指定する拡張WIFフォーマットを定義したBIP-178

BIP Bitcoin

Bitcoinアドレスは秘密鍵から計算した公開鍵を使って生成されるが、そのアドレスの種類は複数（P2PKH、P2WPKH、P2SHでネストしたP2WPKH）ある。いずれも同じ秘密鍵から生成可能なアドレスだが、実際にウォレットで使ってるアドレスはそのうちのどれか1つ。ただ、現在のWIF（Wallet Import Format）形式の秘密鍵では、どの種類のアドレスに関連付けられた秘密鍵なのか示すデータが存在しないので、それをわかるようにWIFフォーマットを拡張しようとBIP-178が提案された。

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

ただほとんどのユーザーはHDウォレットを使っており、どのアドレスを導出するかはその導出仕様（BIP-44、BIP-49、BIP-84）で定義されているため、ユーザーが個別の秘密鍵を管理するようなことは無いので、実際のユーザーが利用することはないと思うが、まぁ開発やテストなんかで秘密鍵単位でインポート・エクスポートする際には管理しやすくなるといったところか。

参照実装のプルリクがBitcoin Coreに投げられているけど、マージはされないままクローズされているので、今後どうなるか様子見かな。

以下、BIPの定義内容。

動機

1つの秘密鍵に対して、（1から始まるレガシーな）P2PKH、（P2WPKHのP2SHネスト版）P2SH-P2WPKH、P2WPKHなど対応するBitcoinアドレスは複数ある。

秘密鍵には対応する公開鍵が圧縮されているか（0x01）、非圧縮か（suffixなし）を示す1バイトのsuffixがあるが、秘密鍵に関連付けられているアドレスの種類を知る方法はない。その結果、秘密鍵をインポートする際に、ウォレットは全種類のアドレスを想定し、それぞれのアドレスを追跡する必要がある。

siffixを拡張することで、秘密鍵にどの種類のアドレスが関連付けられているのか指定できるようになる。

仕様

現在、秘密鍵はunit256の秘密鍵のデータの後にオプションでuint8のcompressed flagが付与される形で保存されている。この後者のフラグをアドレスタイプを指定できるよう拡張する。

値	タイプ	圧縮	定義
suffixなし	P2PKH_UNCOMPRESSED	No	非圧縮のレガシーな公開鍵。公開鍵フォーマットは不明
`0x01`	P2PKH_COMPRESSED	Yes	圧縮されたレガシーな公開鍵。公開鍵フォーマットは不明
`0x10`	P2PKH	Yes	圧縮されたレガシーな公開鍵。1から始まるレガシーな公開鍵フォーマットを使用。
`0x11`	P2WPKH	Yes	Bech32フォーマット（ネイティブSegwit）
`0x12`	P2WPKH_P2SH	Yes	3から始まるP2SHでネストされたSegwitアドレス

ウォレットが秘密鍵をインポートすると、以下の２つの事がわかる。

鍵はレガシータイプの１つを使っており、この場合すべてのタイプを考慮する必要がある。
鍵は拡張タイプを使っており、この場合ウォレットは特定の対応するアドレスのみを追跡すればいい。

※ 0x01と0x10の違いは、前者は上記いずれのタイプにも対応でき、後者は（従来の非Segwitの）P2PKHのみに対応していること。

互換性

この提案には後方互換性はなく、新しいタイプを認識しないソフトウェアはcompressed flagを理解できない。ただ、少しの変更で対応が可能で、uncompressedは（suffixがない）現在のまま、compressedを0以外のなんらかの値として解釈すればいい。

この提案は、新しいウォレットソフトウェアが古いWIFフォーマットを常に理解するという点で後方互換性がある。しかしそのフォーマットの秘密鍵をインポートした場合、そのアドレスの候補は複数あるためその全てを追跡する必要がある。

謝辞

このBIPはBitcoin DevメーリングリストのThomas Voegtlinの最初の提案と、Electrum 3.0の実装に基づいている。

参照実装

github.com

2018-05-23

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

Bitcoin Ruby Cryptography DLC

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

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

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

The oracle's signatures don't need to show up on the blockchain, and can just be on a website.
— Tadge Dryja (@tdryja) 2018年4月5日

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

ということで実際にRubyでDLCを実現するコードを書いてみた（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を使用する。

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

DLC参加者のセットアップ

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

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

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のアウトプットをインプットとしたクロージングトランザクションを作成する方が良い。