Develop with pleasure!

福岡でCloudとかBlockchainとか。

2017年に起きたMoneroのキーイメージを細工したコイン無限生成の脆弱性の内容

2017年2月に発覚したMonero(正確にはCryptoNoteのプロトコルを採用している暗号通貨)でコインを無限生成できる脆弱性について、原因が曲線の特性に起因するもので興味深かったので調べてみた。

ww.getmonero.org

この脆弱性自体は実際にMoneroでは悪用されることなく、表向き別の目的でパッチが当てられ、問題は回避されている。

脆弱性の内容

MoneroのベースとなっているCryptoNoteは匿名通貨を実装するプロトコルの1種で、中でも特徴的な技術がリング署名。トランザクションを作成する際に、自身が所有するUTXOの他に、そのUTXOと同じ量のコインを持つ他人のTXO*1ブロックチェーンから複数選択し(現在は最低10個)、それを実際に使用する自分のUTXOと一緒にインプットにセットする。この時点でインプットにセットしたTXOの内、自分が秘密鍵を知っているのは1つだけで、その秘密鍵とインプットにセットしたTXOの公開鍵のセットを使ってリング署名を生成する。こうすることで、インプット内のいずれかのTXOが使用されたのは分かるが、実際にどのTXOが使用されたのかは分からず、これによって送信元の匿名化を図る。

ただ、このままだとどのインプットが使われたか分からず、UTXOの二重使用が発生する可能性がある。そのため、インプットには実際に使用するUTXOに紐づく秘密鍵から生成したキーイメージがセットされ、リング署名のインプットの1つにもなる。トランザクションインプット内のキーイメージがこれまで使用されていないかどうかチェックをすることで、二重使用を防ぐ仕組みになっている。

キーイメージは、秘密鍵x、対応する公開鍵をP = xGとした場合、I = x * hashp(P)で計算される。hashp()は公開鍵から決定論的にランダムな公開鍵を生成するハッシュ関数

今回の脆弱性では、このキーイメージが特別な方法で変更することができたため、それによって二重使用が可能な状態だった模様。

では具体的にどうやってキーイメージを変更するのか?という点だが、これは↓のサイトが詳しい。

nickler.ninja

monero.stackexchange.com

曲線Ed25519の特性

CryptoNoteはEd25519の曲線を使用している。Ed25519の特性の1つは、曲線上の点の数(曲線の位数)がベースポイントGによって生成された群内の点(群の位数)より多いという点。群の位数は素数l = 2^252 + 27742317777372353535851937790883648493で、曲線の位数は8*lとなる。曲線の位数と群の位数の比はcofactorとして知られており、Ed25519の場合は8。ちなみにBitcoinで使われている曲線secp256k1のcofactorは1なので、群の位数と曲線の位数は等しい。

  • cofactor == 1の場合、部分群は曲線全体で、任意のゼロ以外の点が生成点となる。曲線の方程式を満たす点はすべて部分群の一部。
  • cofactor != 1の場合、素数位数の部分群は曲線の厳密なサブセットで、点を考慮すると、曲線の座標が方程式と一致するか検証するだけでは、点が適切な部分群にあることを保証するには不十分。さらに位数がrの倍数でない点が存在する。cofactor = 8の曲線25519で起こり、その場合それを使用するプロトコルでいくつかの注意が必要になる。例えば曲線25519でDiffie-Hellman鍵交換をする場合、Diffie-Hellman秘密鍵は8の倍数を選択する必要がある。これにより点が確実に部分群に格納される。

cofactorは曲線上に低位の群が存在すること示している。例えばPを26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05で表される点とし、Pから8*P = 0を意味する位数8の(ユニークな)群を生成する。低位数の曲線上にはわずかな点しか存在しない。その点を見つける1つの方法は、a*lの位数で曲線上にランダムな点を生成し、その点にIを乗算して位数1 <= a <= 8の点を得る。一方、CryptNoteでキーイメージを生成する際に使用するハッシュ関数hashpは結果を出力する前に8を乗算して、結果の点が素数位数群にあることを保証する。

攻撃と解決

攻撃者がコインを持っており、キーイメージI = x*hashp(P)を使ってそのコインを使用するための通常のワンタイムリング署名を作成できると仮定する。普通にIを使えば攻撃者が持っているコインを使用できるが、コインを使用後さらにIとは別のキーイメージI' = I + Lを生成して同じコインを使用できる。ここで、Lは位数oの下位の点である(曲線上には存在するが群の点ではない)。

キーイメージの検証は元々s*hashp(P) + e*Iを評価するようになっている。

  • eは(暗号学的ハッシュ関数によるランダムオラクル値なので)攻撃者には選択できない。
  • sは署名者が署名の所有権と一意性を証明するために使用する値。

なので細工するとしたらIの部分。oeで割れる場合(e = e'*o)、e*I' = e*I + e'*o*L = e*Iとなり、Iと同じ方法でI'を使って有効な署名を作成することができる(ただしメッセージmは今度はI'にコミットする必要がある)。つまり、曲線の方程式を満たす点は存在するが、Ed25519で指定された群には含まれない(部分群内にある)点を使用する。これらの点のいくつかは8で割り切れる位数の群にある。これらの点の1つがキーイメージとして選択されていて、ランダムオラクル値eが部分群の位数の倍数である場合、キーイメージの検証は約分のため正しい点に戻すようマップされるようになる。そのため有効なキーイメージに、群の位数が8で割り切れる点を加算すると1/8の確率で本当のキーイメージと同じ点に写像されるeを入手できる。

ちなみにByteCoinではこれをはるかに効果的な方法で悪用された模様。攻撃者は低位キーイメージIを生成するのに低位公開鍵Pを使用した。曲線上には8個の低位点しかないので(CryptoNoteでは同じ点の複数の表現を禁止しているため)、この攻撃は1つのブロックチェーン上で8回実行できる。

Moneroで実装された修正は、キーイメージが群内のに存在する点であることを保証するためにl*I = 0をチェックすることで、各キーイメージIが素数位数l群を生成することを検証する。実際に、l' != lを持ちl*I = 0ならば、ll'で割り切れなければならいが、これはl素数であるため矛盾する。この修正による追加コストは、トランザクションインプット毎に1回のスカラー演算ですむ。

というのが2017年の無限コイン生成の脆弱性の内容。

Bitcoinのsecp256k1と違い、cofactor > 1の場合、群の位数と曲線の位数が異なり、曲線上に低位の群が存在して↑のような考慮事項が発生すると。問題はEd25519自体の脆弱性とかではなく、キーイメージを生成する際にEd25519の場合は必要な位数の検証が抜けていたという点で、そういう安全性の評価までちゃんとする必要があるんだろうけど、中々難しいものもあるので、secp256k1のようなcofactor1の曲線を使用するの方が無難な気もする。

*1:TXOと記載しているのは、未使用でも使用済みでも良いため。参加ノードからは実際に使用済みかどうかは分からない(但し、今は不可能だがmixinするインプットが0の場合は使用されたインプットが明確になる)。

The GHOSTDAG Protocol at Scaling Bitcoin 2018

Scaling Bitcoin 2018 復習シリーズ。今回はヘブライ大学のYonatan Sompolinskyによる「The GHOSTDAG Protocol」の発表↓(30分あたりから)

youtu.be

書き起こしは↓

ghostdag

ホワイトペーパーは↓

https://eprint.iacr.org/2018/104.pdf

Bitcoinのオンチェーンスケーラビリティを向上させるプロトコル、GHOSTDAGの提案。

Bitcoinのコンセンサスプロトコル

基本的にBitcoinプロトコルでは、10分間隔でブロックが生成され、そのブロックサイズの上限は1MBと決められている。各ブロックは前のブロックを参照するハッシュチェーンを形成し、同じタイミングでブロックが作られチェーンが分岐すると、後ろにより多くのブロックが続いた方が正当なチェーンとなる最長チェーンのルールが適用され、チェーンが1つに収束するようになっている。

Bitcoinでは正直なマイナーが取る行動は、

  1. 最も長いチェーンの先頭のブロックをマイニングする。
  2. ブロックがマイニングできたらすぐに公開する。

安全性の仮定は、

  1. 51%以上が正直なマイナーであること。
  2. ブロックを作成する時間より、ブロックを伝播する時間の方が短いこと。

この仮定の下、ネットワークに参加している各ノードは最長のチェーンをピックアップし、最長チェーンのトランザクションが別のブロックに置き換わる確率は、後続にブロックが続くほど指数関数的に低くなる。

オンチェーンスケーラビリティを上げるのに問題となるのが、↑のブロック作成時間と伝播時間の関係。スケーリングさせる方法は大きく2つあって、1つはブロックサイズを大きくすることで、この場合ブロックの伝播時間は長くなる。もう1つはブロックの生成間隔を短くするというものだが、いずれも均衡を破ることになる。GHOSTDAGで実現しようとすることは、ブロック伝播の仮定を取り除く、もしくは何らかの方法でそれを弱めること。

プロトコル加える変更は最長チェーンの先頭を見るのではなく、有向非巡回グラフ(DAG)を使用するようにし、その構造でProof of Workでマイニングをする。Proof of Workをすることは変わらず、できるだけ早くブロックを公開するというのも変わらない。ただ最長チェーンを選択するのではなく、最も長いk-クラスター(後述)を選択するようになる。また、確率の高い取引セットを持つというのも変わらず、多くの承認を経ることで二重使用の確率は指数関数的に減少する。

プロトコルの変更によって得られるもの

正しく適用されれば安全性を損なうことなくハイスループットが得られるが、フリーライドではない。レイテンシーはもちろん増加する。コンセンサスプロトコルにおいてスループットレイテンシーは避けられないトレードオフであるため、それを回避するのは難しい。承認のため長時間待たないといけないが、安全性が損なわれるよりは良い。

ブロックチェーン全体を保存する方法や、検証時間の改善方法、起動してデータ全体を同期する方法など、他のコンセンサスの問題は解決しない。ここでターゲットにしているのはコンセンサスレイヤーのみ。

PHANTOMプロトコル

最長チェーンを正とする1つのチェーンを維持するデータ構造を、有向非巡回グラフ(DAG)をベースにしたデータ構造に変えたのがPHANTOMプロトコルになる。Bitcoinの場合、ブロックは1つのチェーンとしてリンクするのに対し、PHANTOMプロトコルではブロックはツリー構造でリンクされ、blockDAGと呼ばれる有向非巡回グラフを形成する。

各ブロックは前の単一のブロックのハッシュを参照するのではなく、前の複数のブロックのハッシュを参照するようになる。

f:id:techmedia-think:20181201133230p:plain
Figure 1: blockDAGのサンプル。各ブロックはそのブロックを作る際にマイナーが知っているすべてのブロックの参照を持つ。

表記

blockDAGの要素を指す際に使用する表記:

  • ブロックDAG:G = (C, E)
    Cはブロックを表し、Eは前のブロックのハッシュを指す。
  •  {past(B, G) \subset C}
    Bから到達可能なブロックのサブセット=Bの前に作られたブロックのセットを表す。
    Figure 1では、past(H) = {Genesis, C, D, E} となる。これはHが直接もしくは間接的に参照するブロックでHより先に作られたことが保証される。
  •  {future(B, G) \subset C}
    Bへ到達可能なブロックのサブセット=Bの後で作られたブロックのセットを表す。
    Figure 1では、future (H) = {J, K, M}となる。これはHを直接もしくは間接的に参照するブロックで、Hより後に作られたことが保証される。
  • anticone (B, G)
     {past(B, G) \subset C} {future(B, G) \subset C}に含まれないブロック=直接または間接的にBを参照せず、Bからも直接または間接的に参照されないDAG内のブロックのセット。
    Figure 1では、anticone (H) = {B, F, I, L}となる。これはHとの順序が曖昧なブロックで、この順序を決めるのがコンセンサスの課題(後述)。
  • tips(G)
    入次数が0のブロック=誰からも参照されていないブロック=最新のブロックのセット
    Figure 1では、tips(G) = {J, L, M}となる。リーフブロックで、次のブロックで参照されるようになる。

DAGのマイニングプロトコル

DAGの場合単一のチェーンを伸ばすのではなく、マイナーが作る新しいブロックはtips(G)のすべてのブロックを参照する(Gはブロック作成時にマイナーがローカルで観測しているDAG)。

新しいブロックを発見したら、マイナーはすぐにそのブロックを公開する(ここはBitcoinの場合と変わらない)。

DAGの順序付けプロトコル

DAGのマイニングプロトコルでは、チェーンのTIPを参照する複数のブロックが作られることになる。Bitcoinの場合、最長チェーンルールによりやがて1つになるが、DAGの場合複数のブロックのまま残る。残った際に問題となるのは順序の問題だ。例えば競合する2つのトランザクションがあった場合(二重使用)、どちらのトランザクションを正とするか?Bitcoinの場合最長チェーンルールにより順序が決まり、これを解決する。DAGの場合、2つのブロックができ、そのブロック内に競合するトランザクションがあった場合、どちらのトランザクションが正しいのか決定する必要がある。

PHANTOMプロトコルでは以下の2段階で順序付けを行う。

  1. 最初にブロックをブルーとレッドに分ける。ブルーのセットは協調ノードによってマイニングされたように見えるブロックを表し、レッドのセットは悪意あるノードもしくは戦略的なノードによってマイニングされた可能性が高い異常値のセット。
  2. 次に、ブルーブロックを優先し、レッドブロックにペナルティを与えるようDAGの順序付けをする。

重要なのは1のカラーリングで、これをどのように行うか?

PHANTOMプロトコルBitcoinと同様Proof of Workによりマイニングが行われ、正直なノードはタイムリーに周りのノードと最近のブロックについて連携する能力を持ち、そんな正直なノードがハッシュパワーの50%以上を保持しているという前提を元にしている。Bitcoinと異なるのは、Bitcoinがブロックの作成が通信(伝播)にかかる時間より遅く設計されているが、PHANTOMプロトコルではそのようなことはなく、フォークが自然的に発生する環境下でも正しいブロックのセットが認識されるよう設計される必要がある。

こういった前提の下、ネットワークの伝播遅延時間の上限をDとし、ブロックBが正直なマイナーによって時刻tでマイニングされた場合、t - Dより前に公開されたブロックは必ず時刻tより前にマイナーに届いており、それはpast(B)に含まれる。同様に正直なマイナーはすぐにBを公開するので、時刻 t + D 後にマイニングされたブロックにはBが過去のブロックとして含まれる。結果として、Bのanticoneになる正直なブロックのセットは、一般的に小さく、期間[t - D, t + D]の間に生成されたブロックのみで構成される。proof-of-workの仕組みは、長さ2・Dの間隔で作成されたブロックの数は通常あるk > 0未満であることを保証する。要するに、正直なノードによって作成されたブロックのセットは、well-connected = anticoneが少ないセットとなる。

つまり正直なノードが発見したブロックをすぐに公開し、かつ周りから受け取ったブロックを組み込んでマイニングしているのであれば、そうやって作られたブロックは多くのTIPへの参照を持ち、多くの後続ブロックから参照が行われるブロック=well-connectedなブロックになる。そのため、そうでないブロックは攻撃者によって作られたブロックであると。この時のセキュリティパラメータがkで、Figure 2はk=3とした場合、DAGのカラーリング結果になる。

f:id:techmedia-think:20180821153359p:plain
Figure 2:与えられたDAG( A, B, C, D, F, G, I, J ブルーカラー)内のブロックの最大3クラスターの例。

kはPHANTOMプロトコルの相互接続パラメータで、k = 3の場合、anticoneのサイズは3を超えてはならない。Figure 2を見てみると、このルールに違反しているのがレッドカラーのブロックで、ブロックEのanticoreは(B, C, D, F, G, I)で3を超えている。これらのブロックがEを参照しないのは、おそらくEを作成したマイナーによってEが保留されていたため。同様にブロックKのanticoreは(B, C, G, F, I, J)で、悪意あるマイナーは既に(B, C, D, G)を受け取っているにもかかわらず、その一部を参照していないという点でマイニングプロトコルに違反している。

ということで、blockDAGの順序付けは以下のように行う。

  1. DAGが与えられた場合に、上記k-クラスタルールを適用してブルーセットを決め、その補足セットとしてレッドセットを使う。
  2. いくつかのトポロジカルなソートに基づいてブルーブロック間の順序を決定する。次に任意のブルーブロックBについて、Bの直前の順序にまだ順序付けされていないpast(B)のレッドブロックを追加する。レッドブロックもトポロジー的に追加する必要がある。

そのため、Figure 2の小さなDAGの順序はA, D, C, G, B, F, I, E, J, H, Kとなる。

こうやってDAG構造の各ブロックの順序が決められるが、1つ大きな問題がある。成長し続けるDAGにおいて、DAG内の最大k-クラスターを見つけるのはNP困難な問題だということ(最良のセットを見つけるのに指数関数的な計算量がかかる)。このためPHANTOMプロトコルを適用するのは実用的ではなく、代わりにgreedyアルゴリズムを導入したPHANTOMプロトコルの変形であるGHOSTDAGプロトコルが提案されている。

k = 0 == Bitcoin

ちなみにk-クラスターの値を0に設定した場合、そのブロックはanticoneを持たないブロックとなり、この設定の下ではPHANTOMプロトコルやGHOSTDAGプロトコルはツリーではなくBitcoinのようにチェーンを形成するようになる。

そういう意味では、SatoshiのBitcoinはPHANTOMプロトコルにおけるk=0のクラスターであるとも言える。

GHOSTDAGプロトコル

PHANTOMと同様、GHOSTDAGプロトコルは(選択されたクラスタ内のブロックである)ブルーと(クラスタ外のブロックである)レッドのブロックのカラーリングを誘発するk-クラスターを選択する。ただし、GHOSTDAGプロトコルでは最大のk-クラスターを見つけるのではなく、greedyアルゴリズム=貪欲法を使って大きなk-クラスターを見つける。このアルゴリズムによって見つけたクラスターは最大のk-クラスターではないものの、十分に大きなものになる。基本的にk-クラスターは正直なノードであると考えられるグループで、最大のk-クラスターを探す場合、正直なマイナーがネットワークの過半数でブロックの大きなセットを生成しそれぞれのブロックのanticoneは小さいと仮定しているため、貪欲法はそれを検出するのにうまく作用する。

  • 各ブロックは前のブロックの中の1つから最もweightの重いk-クラスターを継承する。
  • ブロックを貪欲に追加する(k-クラスターの範囲内で)

ブロックを追加する際にその時点の最良のTIP=これまで最大のブルーセットを持つ  {B_{max}}を継承し、  {B_{max}}の過去に無いブルーセットのブロックに追加することで、DAGのブルーセットを構築する。これでk-クラスター特性は保持される。

GHOSTDAGの基本的な考え方は重いk-クラスターをブロック単位で継承しながら徐々にDAG構築していくことで、最大k-クラスターを発見するというNP困難な問題を回避している。この辺りは同じくGHOSTプロトコルを採用しているEthereumと似ている。

GHOSTDAGの順序付け

GHOSTDAGの各ブロックの最終的な順序付けは、カラーリングの手順と同様の経路に従う。最初にpast( {B_{max}})のブロックに対して  {B_{max}}の順序を継承し、次に  {B_{max}}自体をその順序に追加し、最後にpast( {B_{max}})にないブロックをトポロジカルな順序付けに従って追加することで、blockDAGを順序付けする。

マイニング報酬

マイニングの報酬については、k-クラスター内のすべてのブロックに報酬を与えるようになる。それがSelfish-Miningへの耐性となる。Selfish-Miningはブロックの1つをチェーンから外し、正直な参加者へ報酬を渡すのを拒否しようとする試みになるが、ブロックを隠し持つことで、そのブロックのanticoneは増えていくことになり、後からそのブロックをk-クラスター内に入れるためには、より多くの計算量が必要になる。

Bitcoin CoreはなぜECDSA署名にLOW Rを適用するようになったのか?

Bitcoinでは、送金時にトランザクションにセットする署名に、現在ECDSA署名を採用している。

秘密鍵x、対応する公開鍵をP = xGとした場合、メッセージにに対するECDSA署名は以下のように作成する。

署名の作成

  1. ランダムな値kを選択する。
  2. R = kGを計算する(Rが楕円曲線上の有効な点でない場合の選択からやり直す)。
  3. 点Rのx座標をrとする。
  4.  {s = \frac{H(m) + rx}{k}} を計算する。
  5. 計算した(r, s)のペアが署名のデータとなる。

これは標準的なECDSAの署名ルールだが、Bitcoin Coreの場合、ECDSA署名作成時に以下のようにいくつかルールを加えている(コンセンサスルールではないが、標準トランザクションルールに該当するものはある)。

LOW Sルール

BitcoinではSegwitの導入によりTXIDに関するmalleabilityは排除されたが、ECDSAの署名自体にはmalleabilityが存在する。署名値(r, s)のsの値をマイナスにした -s mod nを使ってもsの値は異なるが正しい署名と判断される。このため、Segwitによりwitness領域に移動した署名データのs値を有効な書き換えることは可能になってしまうので、Bitcoin CoreではLOW_Sルールというのを設けている。

このルールでは、sの値は最大でも曲線の位数を2で割った値以下でなければならないというもので、これによりsを利用したmalleabilityを除外する。この仕様はBIP-146としても定義されている↓

techmedia-think.hatenablog.com

決定性署名

Bitcoin Core(libsecp256k1)では、トランザクションの署名を生成する際に、kの選択を決定論的に行うRFC 6979の決定性署名のルールが適用されている。このため、kはランダムに選択されるのではなく、トランザクションのデータから決定論的に導出される。

techmedia-think.hatenablog.com

この仕組みにより、実装の誤りによりkの生成に偏りが発生するようなことを防ぐことができる。

署名のフォーマット

計算した署名データをトランザクションにセットするわけだが、このときBitcoinではDERエンコードした値をセットする。フォーマットの詳細は

techmedia-think.hatenablog.com

に記載しているけど、簡単に言うと

0x30 データ長 0x02 rのデータ長 R 0x02 sのデータ長 S SIGHASH_TYPE

という構成のデータになる。

そして今回新しいルールが実装に追加され↓、Bitcoin Core 0.17.0でリリースされた。

LOW R

github.com

ECDSAの署名自体にmalleabilityの問題があり、それを解決するのにLOW Sルールを適用するのは理解できるが、このLOW Rのルールは何を意味するのか?

LOW Rの意図

まず署名データは↑のDERフォーマットであることから、

  • 0x03
  • データ長
  • 0x02
  • rデータ長
  • 0x02
  • sデータ長
  • SIGHASH_TYPE

で7バイト使い、残りはrとsの値になる。このrとsの値はそれぞれ256 bitの値=32バイトのデータになるが、DERフォーマットではこれを符号付き整数として扱うため、最上位オクテットが0x80〜0xffの場合、そのままでは負の数として扱われてしまうので、先頭に0x00を付与して正の数とするため1バイト追加され33バイトになる。

sのデータについては↑のLOW Sルールがmalleabilityの解決のため導入された結果、32バイトが標準トランザクションルールとして強制されるが、rにはこのルールが無いため、選択されたkの値によって33バイトになったり32バイトになったりする。

まぁ、そもそもDERフォーマットが効率的でないというのもあるんだけど、既にSatoshiの時代から決まっているのでしょうがない。

今回の変更の目的は、rにも同様のLOW Rルールを適用することで、rのデータ長が常に32バイトになるようにし、データ容量を削減しようというものだ。データを削減すると言ってもrのDER形式の署名データが33バイトになるケースが1バイト分削減されるだけで、大して意味のある削減じゃないかとも思うが、実際Bitcoinの1日のトランザクションで考えると数千バイトの削減効果になるとされていて結構大きい(チリツモ的な)。

LOW Rの適用方法

基本的にrの値は、↑のECDSAのプロトコルからも分かるように、本来は乱数kを秘密鍵とした楕円曲線上の点であり、Bitcoin Coreはこれを乱数生成器の脆弱性を考慮し、トランザクションデータから決定論的にkを導出するようにしている。

R = kGで計算されるので、この結果がLOW Rでない場合、kの選択をやり直す必要があるんだけど、Bitcoinの場合トランザクションデータから決定論的にkを選択してるのにどうやってやり直すの?という疑問が生じるが、これはRFC 6979に答えがある。

RFC 6979は決定論的にnonce kを選択する仕様だが、追加のエントロピーを指定するオプションがあり、このオプションの値を期待するrを得るまでのカウンタとして利用することで、LOW Rを選択できるようにしようというもの。順番にインクリメントするカウンタなので、決定論的にnonceを生成するという特性も維持される。

RFC 6979のオプションというのはおそらく以下の3.6章の内容だと思われる。

 Additional data may be added to the input of HMAC, concatenated
after bits2octets(H(m)):

   K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) || k')

A use case may be a protocol that requires a non-deterministic
signature algorithm on a system that does not have access to a
high-quality random source.  It suffices that the additional data
k' is non-repeating (e.g., a signature counter or a monotonic
clock) to ensure "random-looking" signatures are
indistinguishable, in a cryptographic way, from plain (EC)DSA
signatures.  In [SP800-90A] terminology, k' is the "additional
input" that can be set as a parameter when generating pseudorandom
bits.  This variant can be thought of as a "strengthening" of the
randomness of the source of the additional data k'.

3.2.dのkの生成はもともと↓で

  K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))

3.6の記述では、追加のインプットとしてk'を付加しているのが分かる。

ということで、k'をカウンタとしてインクリメントしながらLOW Rになるまでnonceの選択を繰り返すよう実装すればいい。

まぁデメリットは、LOW Sルールは簡単にsの値を変換できるものの、rの方は↑のように署名の計算コストが高くなるという点かな。

また、今のところ標準トランザクションルールにはなってないようなので、LOW Rでなくともトランザクションはリレーされる。

Statechains: Off-chain Transfer of UTXOs at Scaling Bitcoin 2018

Scaling Bitcoin 2018復習シリーズ。今回はRuben Somsenによる「Statechains: Off-chain Transfer of UTXOs」の発表について見てみる。

youtu.be

書き起こしは↓

http://diyhpl.us/wiki/transcripts/scalingbitcoin/tokyo-2018/statechains/

ホワイトペーパー(7ページほどなので読みやすい)↓

https://onedrive.live.com/?authkey=%21AOKxfuPbcIsqQTk&cid=C6C37F8DDEF5BDF9&id=C6C37F8DDEF5BDF9%2136661&parId=C6C37F8DDEF5BDF9%2136660&o=OneUp

Statechainとは?

StatechainはPayment Channelとは異なるコンセプトのレイヤー2のスケーリングソリューションになる。Payment Channelの場合、マルチシグにデポジットした金額を上限として、参加者の残高をオフチェーントランザクションで更新していくモデルだが、Statechainは基本的にはUTXOの所有権をオフチェーンで譲渡していくモデルのソリューションになる。

そのため、UTXOの量が例えば1 BTCだった場合、転送できるのは1 BTCまるごとで、1 BTCを分割して0.5 BTC分だけ渡すといったことはできない。0.5 BTCを支払いたい場合は、事前に1 BTCと0.5 BTC×2のUTXOを交換する方法を取るが、適切な交換をするためにはStatechain上のコインの流動性が求められ、適切な交換は意外と難しいんじゃないかと思う。

Statechainを運営するエンティティ

StatechainはオフチェーンでUTXOの所有権を転々と移動させていくプロトコルだが、この台帳を維持し、Statechian上でのUTXOの所有権の移動をサポートする存在としてStatechainを運営するエンティティと呼ばれるものが存在する。Federated SidechainとかのFederationに近いが、Federated Sidechainの場合Federationが機能しなくなると、サイドチェーン上のコインが動かせなかったり、それをメインチェーンに戻したりできなくなるが、そういったリスクはなく、エンティティが機能しなくなっても、Statechain上のUTXOを最終所有者がオンチェーン上で償還できるようになっている。

Statechainを構成する技術要素

このStatechainは以下の技術要素を組み合わせて実装するプロトコルになっている。そのため、プロトコル理解のためには事前に各技術要素について知っておいた方が良い。

Statechainのプロトコル

以下の説明では、StatechainのエンティティをAとする。

Statechainへのコインの移動

ユーザーBがコインをStatechainに移動したい場合、BはエンティティAと協力して、eltooスタイルのチャネルを作成する。この時、Bは自身の鍵を使うのではなく、transitory keyと呼ばれる新しい鍵を生成する(この鍵をXと表記する)。このtransitory keyはこの後、Statechain上でコインの所有権を移動する際に、新しい所有者にも共有される鍵になる。Bは自身が持つUTXOのコインをAとXの秘密鍵の情報がないとアンロックできないスクリプト宛に送金する。

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

オンチェーン上にはAとX間でロックされたコインがあり(eltooのFunding Tx)、このUTXOをインプットとしたオフチェーントランザクション(eltooのTrigger Tx)が作成されるものと思われる。このセットアップ段階ではオフチェーントランザクションのアウトプットのアンロック条件はいかのいずれか。

  • AXでアンロック可能
  • タイムロック付きでBでアンロック可能

ホワイトペーパーには詳しいコントラクトのコードは掲載されてないけど、LNのように両者の残高を管理するのではなくUTXOの所有権を移動するだけなので、eltooで定義されているSettlement Txは不要と思われる。

また、Statechain上ではこの初期段階ではBがこのUTXOの所有者となる。

※ ここで従来のLNのコントラクトではなくeltooのコントラクトが使われるのは、Statechainの場合、UTXOの所有者がどんどん変わっていくので、参加者が2者だけでなく多数になり、不正が行われた際に誰にペナルティ分を支払うかというのが問題になる。eltooの場合ペナルティではなく最終状態が必ず適用される仕組みなので、Statechainの最終所有者にコインが渡るモデルと親和性が高い。

Statechainでコインを送付

Statechian上にコインをデポジットしたら、今度はStatechain上でコイン(UTXO)を送付する=UTXOの所有権の移動。ユーザーBはデポジットしたUTXOをユーザーCに送る。

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

Statechain上のUTXOの所有権がB→Cに移り、新しいオフチェーントランザクションが作成される。このオフチェーントランザクションのタイムロック条件のコインの所有者はCになる。

Statechain上でB→Cに所有権を移動する際は、Bの署名が必要となる。この署名がBがCへの所有権の移動を認めた証拠となる。またCがその移転を認めるという意味でCの署名も必要となる。この両者の署名の作成がアトミックに行われるのを保証するためにAdaptor Signatureを利用する。(この時使われるAdaptor Signatureは、A、B、Cそれぞれが共有シークレットを生成する変種のAdaptor Signature)またこの時作成したAdaptor SignatureからCがtransitory key Xの秘密鍵を知るようになる。

このようにStatechain上での所有権の移転は、エンティティAと現在の所有者B、次の所有者Cによってアトミックに行われる。この時所有権を更新したオフチェーントランザクションも新たに作成されるが、ここでもAdaptor Signatureが利用され、Statechian上で所有権の移転を認める署名が公開されると、その署名から所有権をCに更新したオフチェーントランザクションの有効な署名も作成されるようになるみたい。このためBitcoinサイドとStatechainサイドのトランザクションにもアトミック性が保証される。

Cへのコインの所有権が移動すると、transitory keyの値を知っているのはBとCとなり、Cは次のユーザーにUTXOの所有権を送付することができるようになる。

このようにStatechain上ではデポジットされたUTXO毎に、エンティティによって履歴の管理及び、所有権の移動がサポートれる。

エンティティのフェデレーション化

エンティティAについて1つの鍵のように記載されているが、これを複数人のフェデレーションにすることもできる。Schnorrの集約機能を利用して(おそらくプラス秘密分散)、実運用では8-of-10のようなフェデレーションによる合意の仕組みが用いられると思われる。

不正行為

Statechainを運営するエンティティは、すべての転送が記録される公開台帳を持つことが期待されていて、これは不正な引き出しに対する証拠として機能する。台帳上で不正な引き出しが競合するか、引き出しの際のStatechainのフォークが発生した場合、ユーザーはトランザクションがある時点でStatechainに含まれているという証拠を保存していれば、両方のケースで詐欺の証明ができる。従来のブロックチェーンと異なり、全てのUTXOはコインをマージしたり分割したりできないので、他のUTXOの履歴とは独立した履歴を持っている。そのため気になるUTXOの履歴だけを選択して検証し追跡できる。

コインの移動には常にStatechainのエンティティAの許可と、(UTXOを保有している)transitory key保有者の許可が必要になる。Statechainのエンティティは最後のtransitory keyの所有者と協力しなければならず、そうでない場合、詐欺の証拠を生成することになる。↑のようにAdaptor Signatureを利用しているのは、コインの移動に伴い参加者の署名が存在することを保証するため。

もし前の所有者と共謀して現在の所有者にだまって別の所有者にコインを送付しようとした場合、Statechain上でその証拠となる署名が残ることになり、現在の所有者はそれを詐欺の証拠として提出することができる。当然、そういった行為をしたエンティティのレピュテーションは下がる。

最悪のケース

最悪ケースは悪意あるエンティティが多くのUTXOのtransitory keyを何らかの方法で入手した場合で、この場合オンチェーン上のコインをエンティティAが盗むことができる。このような盗難が発生した場合、transitory keyを盗まれていないユーザーは、すぐにBitcoinのオフチェーントランザクションをブロードキャストして資金を償還することで被害を最小限に留める。

当然こういった行為を行ったエンティティのレピュテーションは著しく低下する。また実際に秘密鍵に該当する鍵はユーザー側が管理しているので、漏洩はユーザー側の管理次第になるが、Statechain上でのUTXOの移動が続くとそれだけtransitory keyを知るユーザーが増えるので、Statechain上での履歴がある程度長くなったら一度オンチェーンに戻す方が鍵管理の安全性上は良い。

逆にtransitory keyさえ漏洩しなければ、エンティティが勝手にコインを移動することはできない。たとえ裁判所からの押収命令があったとしても技術的に押収することは不可能。

Statechainの欠点

Statechainの欠点は良くも悪くも、UTXO単位の送金しかできないという点で、必要な金額にあわせてUTXOをマージしたり分割したりできないという点。また少額のUTXOの場合、そのUTXOをオンチェーンで償還しようとした場合の手数料の方が高くなるといったことも考えられることから、ある一定量以上のUTXOでないと受け入れられず、マイクロペイメントなどは無理だろう。

Lightning Network on Statechain

Statechain上のUTXOの送付先をボブへ送付するのではなく、ボブーキャロルのマルチシグに送付することで、Statechain上でLighting Networkをセットアップするが可能になる。

従来のLighting Networkと違うのが、チャネルはオフチェーンで開かれるので、チャネルのオープン/クローズ、Splicingを非常に安価に行うことができ、残高調整が行いやすいという点。

Graftrootの利用

Graftrootが利用できるチェーンであれば、資金をオンチェーンで償還する際の自由度が上がる。ハードフォークなどでチェーンが分岐した場合、StatechainにデポジットされたUTXOは2つのチェーンで同時に存在していることになる。Statechainのエンティティがどちらのチェーンを採択するのかという問題が浮上するが、エンティティは最新の所有者からの要求があれば、その所有者が望む条件のスクリプトへの署名を提供することで、別の条件を使ってオンチェーンでの償還を行うことができる。それがエンティティが運用すると決めたチェーンでなくても。

所感

  • UTXOの所有権の移転がベースのモデルなので実際の決済などには使いづらそう(ぴったり一致するUTXOはそうないと思うし、それを揃えるために交換が必要でその交換もちゃんとした額で成立するのは難しそう)。
  • LNをこういったオフチェーントランザクションをベースにチャネル構築することで、チャネル開閉やSplicingのコスト、時間を短縮できるようになるのは面白い。
  • Statechainを運営するエンティティのインセンティブはどこにあるんだろう?
  • Adaptor Signatureが数パターンの使われ方がされているので、もう少し詳しいプロトコル解説がほしいところ。

送信者−受信者間で簡単なコインジョインを行うBustapayプロトコルを定義したBIP-79

Bitcoinトランザクションはインプットに送信者のUTXOが、アウトプットに受信者のアドレスと送信者のお釣りがセットされる構成が一般的。ブロックチェーンの分析をする企業でよく採られるアプローチでは、こういうトランザクションの場合、インプットのUTXOは全て同じユーザーのものであるという仮定に基づいていて、その仮定の元、ブロックチェーン上のトランザクショングラフを解析し、ユーザーや企業の動向を分析しようとしている。

今回新しく提案されたBustapayプロトコルは、コインジョインといっても大量のインプット/アウトプットを集めてコインを撹拌しようという目的ではなく、トランザクションのインプットは全て同じユーザーのものという上記ブロックチェーンの分析の仮定を崩すための送信者−受信者間の簡単なコインジョインプロトコルを定義したもの↓

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

同様の目的で以前BlockstreamがPay to EndPoint(P2EP)というプロトコルを提案していた↓

techmedia-think.hatenablog.com

ただBlockstreamのP2EPの場合、受信者が所有するUTXOの情報に関するプライバシーを守るため、フルノードにアクセスしてダミーのUTXOををセットしたダミートランザクションを多数用意し、送信者との間で署名のやりとりをするなど、単一の決済プロトコルとしては重かった部分をBustapayでは削ぎ落としてシンプルになっている↓

Abstract

Bitcoinトランザクションを普通に作成すると、望ましくない情報が漏れることが多い。結果として、効果的なブロックチェーン分析技術により、有用な通貨に期待される重要な特性が危険にさらされる。

Bustapayは、支払いの送信者と受信者が、両者の直接的な利益を守るためいくつかの分析の仮定を破壊する方法で、両者がBitcoinトランザクションに協力して署名するための簡単で実用的なプロトコルだ。さらに、Bitcoin決済をする事業者にとって一定の問題であるUTXOセットのサイズを管理するのを手助けするため、受信者に重要な量の制御を与える方法を取る。

動機

最も強力なブロックチェーン分析のヒューリスティクスの1つは、トランザクションのインプットの全てが、(伝統的なコインジョイン独自の構造やマルチシグの使用など)別で知られている場合を除いて、単一のユーザーによって制御されているという仮定だ。他の手法(特にお釣り用のアウトプットの推測)と組み合わせることで、予想以上に正確な追跡が行われ、Bitcoinの参加者は容認できない個人的に、ビジネス上および財務上のリスクにされされ、Bitcoinの利便性と代替性を損ない、最終的に有用な通貨として機能する能力を損なうことになる。

しかし我々は、送信者と受信者のコインジョインでこれらの仮定を壊すことができる。コストのかからないスパイ/DoS攻撃を防ぐため、プロセスを開始する際に送信者に完全に有効な伝播準備のできたトランザクションの提供を求め、送信者がコインジョインを完了しない場合に受信者がそのトランザクションをブロードキャストできるようになっている。最も有望なことに、Bustapayのトランザクションは識別可能な構造を持たないため、任意のネットワーク分析は与えられたトランザクションがBustapayのトランザクションかどうか分からないため、分析のモデル全体の信頼性が損なわれ、Bitcoinのエコシステム全体に肯定的な外部性がもたらされる。

Bustapayのトランザクションは、受信者のUTXOの数を増やすことなく、実際に受信者に自分のUTXOセットを良いように管理する機会を与え、それは通常の支払い時の取引でのみ行われる。大規模なUTXOセットは、よく問題になり高価で、頻繁にプライバシーを破壊する統合を必要とする。Bustapayは、クラスタ化の仮定を破壊する以外に、送信量の難読化レイヤーも提供する。

この仕様では、導入を促進するにあたってシンプルさが1番重要であるとの前提で、複雑さと潜在的に有用な拡張を避けてきたことが注目に値する。

概要

Bustapayの支払いは送信者から受信者に対して行われる。

手順1:送信者は受信者に支払うBitcoinトランザクションを作成する

このトランザクションは全てのインプットに対してsegwitを使用し、完全に有効で署名済みである必要がある。トランザクションはネットワークに伝播できる状態であること(ただしこの段階ではブロードキャストされない)。

手順2:送信者は受信者にテンプレートトランザクションを送る

これはbustapay urlに対して、HTTPのPOSTリクエストで行われる。

手順3:受信者はトランザクションを処理し、部分的に署名されたコインジョインを返す

受信者はトランザクションを検証し、自身に支払うようにする。受信者は1つ以上のインプットを追加し(contributed inputs)、(オプションで)受信者自身に支払うアウトプットを増額する(一般的にcontributed inputsの合計分増額する)。こうして受信者が送信者に返す、部分的なトランザクションが作成される。これは送信者に自身のインプットに再署名してもらう際などに呼ばれる。

手順4:受信者は検証、再署名、Bitcoinネットワークへの伝播をする

受信者は部分的なトランザクションが正しくかつ悪意なく変更されていることを検証し(潜在的に信頼できない通信シャネルも使用できるため)、元の自分のインプットに最署名し最終的なトランザクションBitcoinネットワークにブロードキャストする。

手順5:受信者はBitcoinネットワーク上で最終トランザクションを確認する

受信者がネットワーク上で最終トランザクションを確認し(そして十分な承認数あるか)、送信された金額は通常の支払いのように見える(ネットワーク上で確認する金額と実際の送金額は異なるが)。タイムアウト後に受信者が最終トランザクションを確認できない場合は、支払いが確実に行われるように元のテンプレートトランザクションをブロードキャストし、強力なアンチDoSの仕組みを機能させる。

仕様

送信者にBustapayトランザクション送信先を知らせる標準的な方法は、BIP-21エンコードされたアドレスを使用する方法だ。この時パラメータとしてキー:bpu(BustaPayUrlの短縮表記)を使用する。アドレスの例は以下のようになる。

bitcoin:2NABbUr9yeRCp1oUCtVmgJF8HGRCo3ifpTT?bpu=https://bp.bustabit.com/submit

URLは短くしておくことを強く推奨する。

送信者がテンプレートトランザクションを作成するにあたっては、segwitインプットだけが使用できるという点を除いて、通常の送金トランザクションを作成するのと変わらない。送信者はBIP125(オプトインのFullRBFのシグナリング)と同様、通常よりやや積極的な手数料レートの使用を勧められるが、どちらも厳密には要求されない。

テンプレートトランザクションは、Bustapay URLにHTTP POSTでバイナリエンコードされたBODYとして受信者に送信する必要がある。

受信者はテンプレートトランザクションの検証で応答する。トランザクションに問題がある場合、もしくはトランザクションに不満がある場合(手数料が低すぎるなど)、HTTPレスポンスコード422を使って、拒否理由をユーザーに伝えるため人が読める形式の文字列と一緒にレスポンスを返す。

受信者がトランザクションを拒否した場合、それをネットワーク上に伝播してはならない。しかし、送信者は(どのエラーが出たかに関わらず)受信者がいつでもテンプレートトランザクションをブロードキャストできることを認識することが重要だ。クライアントはそのため受信者の意思に応じて行動する必要がある(再調整するか、トランザクションを伝播だけするか)。

Contributed Inputの選択

受信者はすくなくとも1つのインプット(=contributed input)をトランザクションに追加しなければならない。受信者のインプットがない場合、500 Internal Server Errorを使用する必要があり、クライアントは通常通りトランザクションを送信できる(もしくは後でやり直す)。一般的には、1つのcontributed inputのみを追加することを推奨するが、複数のインプットを追加するのが便利なケースもある。

受信者のUTXOセットを列挙させるために同じトランザクションのバリエーションを継続的に送信される攻撃を防ぐために、トランザクションに同じインプットがあった場合は、常に同じcontributed inputを返すのが重要だ。

可能であれば、できるだけ多くの他のトランザクションインプットと同じタイプのcontributed inputを選択する努力を受信者がすることが強く望まれる。

アウトプットの調整

トランザクションにインプットを加えた後、受信者はcontributed inputの合計量分、自身宛のアウトプットの合計(手数料を追加したい場合はその分を差し引いて)を追加するよう調整したい。しかし唯一の厳しい要件が、受信者は決してインプットを追加or削除してはならず、アウトプットの量を減らしてはならないという点だ。

部分的なトランザクションの返却

受信者は部分的なトランザクションの全てのcontributed inputに署名する必要がある。部分的なトランザクションはこの時点で有効なトランザクションではなく、送信者により再署名される必要があるため、元のテンプレートトランザクションから全てのwitnessを削除する。受信者は部分的なトランザクションをバイナリエンコードしたHTTPレスポンスとしてレスポンスコード200で返す。

送信者の検証

送信者は部分的なトランザクションについて重要な検証をしなければならない。送信者は以下を検証しなければならない。

最終トランザクションの作成

部分的なトランザクションの検証後、送信者は全てのトランザクションに署名し、最終トランザクションを作成する。送信者は受信者が送信者の別のインプットに署名するよう騙そうとしていないか慎重に注意することが重要だ。送信者はテンプレートトランザクションに存在するインプットにのみ署名する必要がある。送信者が慎重でない場合、受信者は送信者が実際に所有しているUTXOをcontribute inputに入れ、送信者が盲目的に全てに署名するという希望を持っているケースが考えられる。

トランザクションの公開

最終トランザクションが作成されると、送信者はそれを直接Bitcoinネットワークに送信する必要がある。送信者が妥当な時間内(例えば1分間)にトランザクションを送信しない場合、受信者は重要なアンチスパイ/アンチDoS戦略としてテンプレートトランザクションを公開すべきである。送信者はまた、受信者が不当にトランザクションの手数料を下げた(例:トランザクションサイズは増えたけど、手数料が十分でない)と判断した場合、最終トランザクションでなくテンプレートトランザクションを公開することもできる。最終トランザクションをネットワークに公開した後でも、最終トランザクションが承認されずテンプレートトランザクションの方が手数料が高い場合、(RBFのアドバンテージを取り)テンプレートトランザクションの公開を検討することができる。

実装の注意点

Bustapayの支払いを実装したいと思っている人のために、ここに受信者のためのいくつかの注意がある:

  • トランザクションがmempoolに適しているかどうかは、bitcoin core 0.17+でtestmempoolacceptを使うことで簡単にチェックできる。
  • TXIDによりトランザクションの追跡は不確か。正気を保つために全てのインプットが確実にsegwitであること。しかしトランザクションを検証しない限り、segwitはTXIDのmalleabilityを防げない。そのため、少なくともtestmempoolacceptを使っていることを確認すること。
  • Bustapayはあなたが入金アドレスを持っているかどうかを照会するのに悪意あるユーザーによって悪用される可能性がある。既に使用済みの入金アドレス宛に支払うBustapayトランザクションを受け入れないこと。
  • どのUTXOのユーザー、あなたのどのUTXOを明らかにしたのかマッピングを保持する必要がある。同じUTXOで照会があった場合、以前明らかにしたのと同じUTXOを返す必要がある。
  • BIP-69に基づいてトランザクションが既にソートされているかどうかチェックし、ソートされているのであればそのままにする。ソートされていない場合インプット/アウトプットをシャッフルする。
  • 参照実装はhttps://github.com/rhavar/bustapayで公開されており、bitcoin coreウォレットのRPC呼び出しのラッパーとして機能する。
  • 送信者は、受信者が送信者のコントロール下にあるインプットを追加し送信者が盲目的にそれに署名することを期待する攻撃に対して注意しなければならない。

後方互換

Bustapayはオプションのペイメントプロトコルで、後方互換性の問題はない。実際に、通常のトランザクション処理に加えてサポートできる。これは通常のBitcoinトランザクションに戻す必要があるため。

所感

P2EPでもBustapayでも上記仮定を崩すウォレットが1つでも利用可能になっているというのが重要で、実際にこれらのプロトコルが使われていないとしても(使われているかどうかはトランザクション見ても分からないので)、これらのプロトコルが使われている可能性があるということだけで上記の仮定を崩すことに繋がると思われる。

あと(P2PEも一緒だけど)副次的な効果として受信者のUTXOセットを減らせるというのも良いね。