Develop with pleasure!

福岡でCloudとかBlockchainとか。

Compact Block Filter(BIP-158)をRubyで実装してみた

Bitcoinの軽量クライアント向けに自身に関連するトランザクションを判別する仕組みとしては、Bloom Filterを利用するBIP-37がベースだが、軽量ノード側のプライバシーの改善とフルノードの負荷を軽減するためCompact Block Filterという新しい仕組みが提案されている↓

techmedia-think.hatenablog.com

Bitcoin Coreのmasterブランチにもマージされていたので、それをbitcoinrbにも移植してみた。

Compact Block Filterの仕組み

BIP-37のBloom Filterを利用したフィルタリングでは、各軽量クライアントがフルノードと接続する際に、クライアント毎にフィルタが作成されフルノードは接続されたクライアント毎に、トランザクションやブロックを伝播すべきかフィルタを通して検証していたが、Compact Block Filterは、各ブロック毎に生成されるようになる。そのため、そのブロックに自身に関連するトランザクションがあるかどうかは、各クライアントがブロック毎のフィルタをダウンロードし検証するようになり、フィルタを作成するエンティティとフィルタを使って検証するエンティティの関係が変わる。

フィルタの作成

Compact Block Filterでは上述の通り、ブロック毎にフィルタを作成する。BIP-158で定義されているフィルタタイプはBasic(フィルタタイプ=0x00)の1つのみで、このフィルタにはブロック内の以下のデータがセットされる。

なので、ブロック内の↑の全てのscriptPubkeyのペイロードをフィルタに登録する。

bitcoinrbではフィルタを作成する対象のブロックと、そのブロックの各インプットが参照するUTXOのscriptPubkeyのペイロードのセットを使って以下のようにフィルタを作成する。

# block はBitcoin::Block、prev_out_scriptsはUTXOのscriptPubkeyのバイナリの配列
block_filter = Bitcoin::BlockFilter.build_from_block(Bitcoin::BlockFilter::TYPE[:basic], block, prev_out_scripts)

実際に中身でやってることは、まず、blockとprev_out_scriptsから要素をピックアップする。

elements = []
block.transactions.each do |tx|
  elements += tx.outputs.select{|o|!o.script_pubkey.empty? && !o.script_pubkey.op_return?}.map{|o| o.script_pubkey.to_payload}
end
elements += prev_out_scripts.select{|s|!s.empty? && !s.op_return?}.map(&:to_payload)
elements.uniq

OP_RETURN及び空のscriptPubkeyを除外し、重複するscriptPubkeyは除外する。

ここまでで要素の準備ができたので、続いて実際にフィルタを作成する。BIP-158ではBloom Filterに代わって、フィルタサイズを削減するためGolomb-coded set(GCS)が使われる。GCSの確率構造では、セット内に存在する要素を問い合わせた場合必ずマッチし、セット内に存在しない要素を問い合わせた場合にそれがマッチする確率は1/Mとなる。つまりBloom Filterと同様、偽陽性が存在する。この偽陽性率は整数のパラメータMで制御され、↑のBasicタイプのフィルタではM = 784931と設定されている。

↑のようにブロック内の要素をピックアップしたら、その要素を使って以下のステップでGCSを構成する。

1. 各要素をハッシュし整数にマッピングする

続いて各要素を、要素の数をN個とするとフィルタの偽陽性パラメータMと合わせた0〜N*Mの数値の範囲内にマッピングする。

まず最初に要素のバイナリのSipHash*1を使ってハッシュ値を計算する(使用するSipHashのパラメータはc = 2, d = 4)。BasicフィルタではSipHashの128 bitの鍵には、ブロックハッシュの先頭16バイトを使用する。これにより鍵はブロックごとに決定論的に導出され、かつブロック毎にランダムになる(先頭16バイトというのはビッグエンディアンでなので、リトルエンディアンとは違い0が続くのは先頭ではなく後方である)。

ruby ではsiphash gemを利用することで、SipHash-24のハッシュ値が得られる。

key = ブロックハッシュの先頭16バイト(バイナリ)
element = フィルタに登録する要素のバイナリ
hash = SipHash.digest(key, element)

SipHash#digestによりハッシュ値が整数で返ってくるので、この整数に F = M * N を乗算し、その上位64 bitを取得する。

(hash * f) >> 64

モジュロ演算は高価なので、結果がある範囲内に一様に分布しかつ高速に計算できるよう↑の計算が採用されている。

↑のように全要素を64 bitのハッシュ値に変換し、その結果を昇順にソートしたセットを用意する。

hashed_set = elements.map{|e| hash_to_range(e) }.sort
2. フィルタへの登録

↑までで、各要素をハッシュし、結果をソートした整数のセットが準備できた。

肝心なのはここからで、要素のハッシュをそのままフィルタに登録するととても巨大なフィルタになってしまうので、圧縮してフィルタに登録する。この時、圧縮に使われるのがゴロム・ライス符号だ。

現在、昇順にソートされた整数のセットを持っているので、この連続する整数の差分をフィルタに登録する。各整数値は↑の計算により一様に分布しているため、その差分は幾何分布に似るとされており、ゴロム・ライス符号はその幾何分布の値を最適に圧縮するための方法になる。ソートされた順番で連続する2つのアイテムの差分を算出し、その差分をゴロム・ライスでエンコードする(先頭の要素の差分は0との差)。ゴロム・ライス符号では、差分の値は2P*2を法とする商と剰余に分割され、別々にエンコードされ(商は単項としてエンコードされ、その後に1 bit0が続き、その後余りがP bitの値としてエンコードされる)、順次BitStreamに追記される。尚、値が幾何分布を形成するため、商は0もしくは1のケースが多い。

  bit_writer = Bitcoin::BitStreamWriter.new
  last_value = 0
  hashed_set.each do |v|
    delta = v - last_value # 連続する要素の差分がdelta
    golomb_rice_encode(bit_writer, p, delta) # deltaをゴロムライスでエンコード
    last_value = v
  end
  bit_writer.flush
  filter = bit_writer.stream
  ...

def golomb_rice_encode(bit_writer, p, x)
  q = x >> p
  while q > 0
    nbits = q <= 64 ? q : 64
    bit_writer.write(-1, nbits) 
    q -= nbits
  end
  bit_writer.write(0, 1)
  bit_writer.write(x, p)
end

BitStreamは追記型のbit型のストリームで、指定bit分データをバッファに書き込み、書き込まれたデータが8 bitになったら、それをストリームに書き込むという、bit単位の書き込み/読み込みが可能なストリームである。 今回Rubyで実装したものが↓

https://github.com/chaintope/bitcoinrb/blob/master/lib/bitcoin/bit_stream.rb

Rubyの場合、整数は無限多倍長整数に自動拡張されていくので仕様でデータ長の制限がある場合は、そのデータ長に合うよう計算時に桁溢れの対応を逆に自前でする必要がある。

上記のように、ソート済みの要素のハッシュのセットの各差分を順次、ゴロム・ライス符号でエンコードしたデータをストリームに追記していく。全データ分エンコードしたら最後にBitStreamのバッファについて最も境界に近い値に0でパディングし、ストリームをビット列に変換する。こうやって出来たビット列の先頭に要素数をCompactSizeでエンコードしたデータを付加したデータがBasicタイプのフィルタデータになる。

フィルタの検索

↑でブロック毎のフィルタが作成され、ブロックチェーンとは別にこのフィルタデータがP2Pネットワークで配信されるので、軽量クライアントはそのフィルタをダウンロードし、自身に関連するトランザクションがそのブロックに含まれるか検証する必要がある。

クライアントはまずエンコードされたフィルタから、要素数とフィルタのペイロードをロードする。

n, payload = Bitcoin.unpack_var_int(エンコードされたフィルタのバイナリデータ)
bit_reader = Bitcoin::BitStreamReader.new(payload)

nがフィルタに登録されている要素の数。

続いて、フィルタに検索をかけるデータを用意する。これは自身が持つUTXOのscriptPubkeyなどで、フィルタに登録した時と同様、SipHashを使って整数値に変換し、要素が複数ある場合は昇順にソートしておく。

あとは要素の数分n回、ゴロム・ライス符号でエンコードされたデータをデコードし、その差分を加算していき、検索対象のデータと一致するか順番に検証していく。一つでも一致するデータがあれば偽陽性Mの下で、フィルタに合致するデータが存在したことになる。

  hashes = 昇順にソートした要素の整数値の配列
  size = hashes.size
  value = 0
  hashes_index = 0
  n.times do
    delta = golomb_rice_decode(bit_reader, p)
    value += delta
    loop do
      return false if hashes_index == size
      return true if hashes[hashes_index] == value
      break if hashes[hashes_index] > value
      hashes_index += 1
    end
  end
  return false

...

def golomb_rice_decode(bit_reader, p)
  q = 0
  while bit_reader.read(1) == 1
    q +=1
  end
  r = bit_reader.read(p)
  (q << p) + r
end

bitcoinrbでは、GCSFilter#match?,match_any?でそれぞれ上記の検索をしている。

フィルタに合致した場合、そのブロック内に自身に関係するトランザクションがある可能性が高いので、軽量クライアントは別途そのブロックをダウンロードし、対象のトランザクションを特定する必要がある。BIP-37のBloom Filterを利用した既存のフィルタではmerkeleblockメッセージの他txメッセージで関連するトランザクション情報をフルノードが送ってくれるが、BIP-157,158のCompact Block Filterでは軽量クライアントがフルブロックデータをダウンロードする必要がある。このため、BIP-37のプライバシーの課題は解消されるが、使用する帯域幅は増加するため、ビッグブロックを掲げるチェーンでは採用し辛いだろう。

Rubyでの実装

ほぼ↑で説明したけど、Bitcoin Coreから移植したRuby実装は主に以下のコンポーネントになる。

テストは

*1:SipHashは鍵付きハッシュ関数の一種で、128 bitの鍵と可変長データを入力に取り、64 bitのダンダムな値を出力する。各プログラミング言語連想配列ハッシュ関数によく採用されている。

*2:Pはゴロム・ライスのパラメータで今回のBasicフィルタの場合は19

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が数パターンの使われ方がされているので、もう少し詳しいプロトコル解説がほしいところ。