Develop with pleasure!

福岡でCloudとかBlockchainとか。

Dual_EC_DRBGのバックドアの仕組み

japan.zdnet.com

こんなニュースもあり、バックドアと言えばエドワード・スノーデンの告発でも話題になったNSA(米国家安全保障局)のバックドアを思い出した。当時は仕組みについて調べてなかったけど、どんな仕組みのバックドアだったのか今になって気になったので調べてみた。

Dual_EC_DRBG

バックドアが仕込まれていたのは、NSAの推奨により一度は標準として採用された擬似乱数生成器のアルゴリズムDual Elliptic Curve Deterministic Random Bit Generator(Dual_EC_DRBG)。で、2006年にNIST SP800-90Aに組み込まれ、2013年に利用すべきではないと勧告されている。

Dual_EC_DRBGの仕様

Dual_EC_DRBGは、生成したシード値から、2つの楕円曲線上の点を使って、多数の乱数を生成する擬似乱数生成器で、楕円曲線上の離散対数問題の困難性がベースになっている。アルゴリズム自体はそんなに複雑ではない。

Dual_EC_DRBGでサポートされている楕円曲線は、NIST-p256およびNIST-p384とNIST-p521で、曲線の式はy2 = x3 - 3x + b (mod p)。

Dual_EC_DRBGでは、楕円曲線上の2つの点PとQを使用する。この内Pは楕円曲線のジェネレーターGと同じ点で、例えばNIST-p256であればそれぞれ以下のように定義されている。

P.x = 6b17d1f2 e12c4247 f8bce6e5 63a440f2 77037d81 2deb33a0 f4a13945 d898c296
P.y = 4fe342e2 fe1a7f9b 8ee7eb4a 7c0f9e16 2bce3357 6b315ece cbb64068 37bf51f5

Q.x = c97445f4 5cdef9f0 d3e05e1e 585fc297 235b82b5 be8ff3ef ca67c598 52018192
Q.y = b28ef557 ba31dfcb dd21ac46 e2a91e3c 304f44cb 87058ada 2cb81515 1e610046

そして、Dual_EC_DRBGは初期シードを使って、PとQの点を使ってスカラー倍算を実行して乱数を生成する。

  1. エントロピーソースから初期シード {s_0}を生成する。
  2.  {s_0}スカラー値として {s_0P}を計算し、そのx座標を {s_1}とする(つまり {s_1 = (s_0P).x})。
  3.  {s_1}スカラー値として {s_1Q}を計算し、そのx座標を {r_1}とする(つまり {r_0 = (s_1Q).x})。
  4. (NIST-p256の場合) {r_1}は32バイトであり、その内の上位16bitを削除した30バイトのデータが出力される。

データがさらに必要な場合、↑の計算値を使って次の乱数が生成される。次の乱数は、

  1.  {s_1}スカラー値として {s_1P}を計算し、そのx座標を {s_2}とする(つまり {s_2 = (s_1P).x})。
  2.  {s_2}スカラー値として {s_2Q}を計算し、そのx座標を {r_2}とする(つまり {r_1 = (s_2Q).x})。
  3.  {r_2}の下位30バイトが次の出力値。

これを要求されたビット数まで繰り返し、出力値を連結して返す(余ったバイトは破棄される)。つまり内部状態 {s_{i-1}}を使って次の内部状態を {s_i}を更新し、出力を生成している。

  •  {s_i = (s_{i-1}P).x}
  •  {r_i = (s_iQ).x}

このPRNGが安全であるためには、内部状態 {s_i}を誰も知り得ないことが重要で、 {s_i}が分かると、それ以降の全ての内部状態および出力を計算することができる。

バックドアの内容

Dual_EC_DRBGは上記のように2つの楕円曲線上の点を使って、決定論的に乱数を生成する仕組みだが、問題となるのはPとQの点の算出根拠が無い点にある。つまりNSAはPやQの離散対数を知っているのではないかということ。

攻撃者がP = dQとなるようなスカラー値を知っていて、(Public Nonceなどで)上記の {r_1}を知っていると仮定した場合、攻撃者は以下の計算が行える。

  1.  {r_1}楕円曲線上の点のx座標なので、楕円曲線の式を使えばy座標が計算でき点 {R = (r_1, y)}を復元できる。
  2. Rが復元できると、 {R = s_1Q}である。
  3. 両辺にdをスカラー倍算すると、 {dR = d s_1 Q = s_1P}が成立する。
  4.  {s_1P}のx座標は次の内部状態 {s_2}を計算する入力値であるため、攻撃者これ以降の内部状態および出力値を知ることができる。

つまり、P = dQスカラー値dの知識は攻撃者にとってバックドアになる。

 {r_1}は上位16 bitが削除されているので、厳密には欠落しているbitを復元するのに攻撃者は最大 {2^{16}}回の計算が必要。

↑のように、たった32バイト(正確には30バイト)の出力を入手すれば、NSAは完全な内部状態を学習できるというのがこのバックドアの怖いところ(実際に攻撃が適用できるかどうか、その難易度はこれが組み込まれているプロトコルや実装に依存する)。

参考

DoS攻撃を可能にする脆弱性CVE-2018-17145とBitcoin Coreの脆弱性の内容と対応

最近公開された、2018年のBitcoin Coreに存在していた脆弱性に関するペーパー↓

https://invdos.net/paper/CVE-2018-17145.pdf

この脆弱性はもともとJavaScriptで実装されたBitcoinのノード実装の1つであるBcoinで発見されたもので、攻撃方法は同じでも、BcoinとBitcoin Coreで脆弱性が現れるコードには違いがある。またホワイトペーパーの説明にも一部間違いがあるようなので、その辺りも含めてみてみよう。

尚、Bitcoin Coreの場合、脆弱性の影響を受けるのはv0.16.0とv0.16.1とされている。

CVE-2018-17145の内容

CVE-2018-17145はBitcoinP2Pメッセージの1つであるinvメッセージを使った攻撃になる。

invメッセージ

invメッセージは新しいブロックやトランザクションの存在を接続中のピアに通知する際に使用される。invメッセージにはブロックやトランザクションのハッシュのリストが含まれており、invを受信したノードは自身が対象のハッシュ値を持つブロックやトランザクションを持っていない場合、それをgetdataメッセージを使って要求する。

invメッセージは最大50,000個のアイテム(トランザクションハッシュ or ブロックハッシュ)を一度に送信できる。

攻撃方法

攻撃方法はシンプルで、インバウンド接続を許可しているノードに接続し、49,999個(ペーパーに49,999と書いてあるけど、上限が50,000なので別に50,000でも良いはず)のランダムなハッシュを生成し、それをinvメッセージにセットして送信し、getdata要求が来ても対応するトランザクションデータを返さない(元々ランダムに生成したハッシュなので、その元となる有効なトランザクションなど存在しない)。これを繰り返す。

ただ、この攻撃が成功するには、攻撃対象のノードがinvメッセージで受信したハッシュリストの内、未確認のハッシュをトラッキングしているノードである必要がある。未確認のトランザクションのハッシュをメモリ上に保持しているノード実装であれば、この攻撃の影響を受ける。1 Gbpsのネットワーク帯域を持つ環境であれば、125MB/秒のデータ送信が可能なため、49,999個の32バイトのハッシュ値を持つinvメッセージを秒間約83回送信できる。するとすぐにノードのメモリは膨れ上がり、Out-of-Memoryを引き起こさせノードを応答不能にすることができる。

ノードは対応するTxが確認されていない状態で受信したinvのTxのリストを他のピアにリレーすることはないので、この攻撃はターゲットノードを絞った上で個別に実行する必要がある。

Bcoinの脆弱性の原因

Bcoinでは、↑のように受信したinvのアイテムをトラッキングしていたため、この攻撃の影響を受ける。

このinvのアイテムをトラッキングしている理由は、未確認のトランザクションハッシュのトランザクションについてgetdataメッセージでデータを要求する際、既にgetdataを送信済みのデータについて再度getdataを送信しないために送信済みかどうかのチェックをするためで、BcoinではハッシュリストをMapで管理していた。

修正のコミットは↓で、

github.com

1つのピアからの未確認トランザクションハッシュの上限を10000とし、それを超えたらそのピアとの接続を切断するという対策を採っている。

Bitcoin Coreの脆弱性の原因

Bitcoin Coreの場合、Bcoinのように単純にトラッキングしているという訳ではなく、正確にはinvで受信したアイテムをウォレットに通知するためのコードが対象になる。

↑のペーパーで、Bitcoin Coreでもinvメッセージを処理する際の機能していない制限のチェックとして以下のsrc/net_processing.cppのコードをリストアップしているが、これは正しくない。このコードはinvメッセージ内のハッシュの数が50,000より大きくないかチェックしてるだけであって、invのトラッキングをするためのコードではない。

if (vInv.size() > MAX_INV_SZ)
{
  LOCK(cs_main);
  Misbehaving(pfrom->GetId(), 20,
  strprintf("message inv size() = %u",
  vInv.size()));
  return false;
}

実際にBitcoin Coreでチェックが動作しているのは、src/net.cppの以下のコードだ

if (mapAskFor.size() > MAPASKFOR_MAX_SZ || setAskFor.size() > SETASKFOR_MAX_SZ)
   return;

mapAskForは、未確認のトランザクションハッシュについて、getdataを要求するために確保されるMapで、MAPASKFOR_MAX_SZinvの上限となじ50,000なので、Bcoinと同じトラッキングの意味としては、対応がされている。

Bitcoin Coreで実際に問題となるのは、トラッキングではなくinvで受信したアイテムをウォレットに通知するためのコードになる。そのコードが、src/net_processing.cppinvメッセージを処理の最後の以下のコード↓

// Track requests for our stuff
GetMainSignals().Inventory(inv.hash);

ペーパーでは、その中身(src/validationinterface.cpp)がリストアップされている↓

void CMainSignals::Inventory(const uint256 &hash) {
    m_internals->m_schedulerClient.AddToProcessQueue([hash, this] {
        m_internals->Inventory(hash);
    });
}

このコードが導入されたのが↓のコミットで、

github.com

ウォレットへのinvのアイテムの通知処理を、バックグラウンドスレッドで動作するようキュー化したもの。この場合、攻撃はバックグラウンドで動作する通知処理のスピードを、invで送られてくるアイテムによるキューの成長が上回る場合に成功する。実際にどういうマシンスペック、ネットワーク帯域の下で成功するかについては、シミュレーション結果などはホワイトペーパーでは提供されていない。

問題のコードは以下のコミットで修正されている。

github.com

修正方法としては、Inventoryの通知自体を削除している。これはバックグラウンドのキュー化以前に戻してもmainスレッドでの処理は発生するからか?まぁ未確認のハッシュをそもそもウォレットに通知する必要もないのだろうけど。

Bitcoin Core以外にもLitecoinやbtcdなどにも影響があったようだが、↑でも分かるよう実装によって脆弱性のポイントは違う可能性はある。

決定性nonceを利用したMuSigの脆弱性に対処したMuSig-DN

Blockstreamは以前、Schnorr署名を利用したマルチシグを構成する際にKey-Rogue攻撃への耐性を持たせる署名スキームMuSigを発表していた。Key-Rogue攻撃やMuSigの内容について以前解説した↓を参照。

goblockchain.network

techmedia-think.hatenablog.com

そんなMuSigについて、決定性nonceを利用できるようにしたMuSigの変形であるMuSig-DN(MuSig with Deterministic Nonces)というSchnorr署名スキームをBlockstreamおよびYannick Seurinが発表した↓

medium.com

ペーパーは↓

https://eprint.iacr.org/2020/1057.pdf

決定性nonceの役割

Schnorr署名やECDSAでは、署名作成時に選択するnonceの値のランダム性がとても重要になる。例えば同じnonceを使って異なる2つのメッセージに署名すると、秘密鍵が漏洩してしまう。

具体的には、メッセージm1およびm2について、同じnonce kを使ってそれぞれ下記のデータを使って署名を生成すると、

Schnorr署名の署名値sの値は、それぞれ

  • s1 = k + H(P || R || m1) x
  • s2 = k + H(P || R || m2) x

となり、署名データは(R.x, s1)と(R.x, s2)となる。nonceが同じ値であることはR.xから分かる。この場合s1 - s2を計算すると、

s1 - s2 = (H(P || R || m1) - H(P || R || m2)) x

となり、P, R, m1, m2は公知であるため、

x = (s1 - s2) / (H(P || R || m1) - H(P || R || m2))

秘密鍵xを計算できる。

このようなことが起きないよう、RFC6979などでnonceを秘密鍵と署名対象のメッセージから決定論的に導出する仕様が定義され、決定性nonceを使用するのが主流になっている。この場合、署名対象のメッセージが異なれば必ず異なるnonceが導出されるため上記のような攻撃から保護される。

決定性nonceを利用したMuSig脆弱性とは?

単一の鍵を使ったSchnorrであれば決定性nonceを使用するのは特に問題ないが、MuSigのようにマルチシグを構成する場合、逆に秘密鍵漏洩のリスクになる。

  • 被害者の鍵ペア: P1 = x1G
  • 攻撃者の鍵ペア: P2 = x2G
  • 署名対象のメッセージ: m
  • 被害者のnonce: R1 = k1G
  • 攻撃者のnonce:
    • R2 = k2G(1回目のセッションで使用するnonce)
    • R3 = k2G(2回目のセッションで使用するnonce)

として、攻撃者が同じメッセージで2回署名セッションを実行した場合、MuSigスキームを実行すると、

  1. L = H(P1 || P2)を計算する。
  2. X = H(L || P1)P1 + H(L || P2)P2を計算する。
  3. Public nonceは
    • 1つめのセッションではR = R1 + R2
    • 2つめのセッションではR' = R1 + R3
  4. 署名値sを計算する。
    • 被害者の1つめのセッションではs1 = k1 + H(P || R || m) * H(L || P1)x1
    • 被害者の2つめのセッションでははs3 = k1 + H(P || R' || m) * H(L || P1)x1
    • 攻撃者の1つめのセッションでははs2 = k2 + H(P || R || m) * H(L || P2)x2
    • 攻撃者の2つめのセッションでははs4 = k3 + H(P || R' || m) * H(L || P2)x2

最終的な2つの署名値は(R.x, s1 + s2)と(R'.x, s3 + s4)になる。この内、被害者が計算したs1とs3について、s1 - s3を計算すると、

s1 - s3 = (H(P || R || m) - H(P || R' || m)) * H(L || P1)x1

となり、H(P || R || m)およびH(P || R' || m)H(L || P1)は攻撃者も知る値であるため、

x1 = (s1 - s3) / ((H(P || R || m) - H(P || R' || m)) * H(L || P1))

と被害者の秘密鍵x1を計算することができる。nonce kは署名値から秘密鍵を逆算できないようにするためのものなので、↑のように(異なるメッセージのパターンでも同様に)nonceを消せる計算が出来てしまうとまずい。

MuSigにおける決定性nonceの使用の問題は自分が決定性nonceを使っていても、他の参加者が同様の導出ルールで決定性nonceを導出しているか分からない点にある。RFC6979では秘密鍵と署名対象のメッセージからnonceを導出するが、相手の秘密鍵を知り得ないため、同じルールで導出されたかをプロトコルで検出することができない。そのため逆に決定性nonceを使わずに毎回ランダムに生成する方が安全になる。

MuSig-DNのアプローチ

MuSigでも決定性nonceを安全に利用するためMuSig-DNでは、nonceが決まったルールの下で導出された値であることをゼロ知識証明を使って検証できるようにしている。

  • 各署名者はnonce keyとよばれる秘密鍵を使って署名対象のメッセージと全署名者の公開鍵のセットを入力として擬似ランダム関数Fを実行してnonce kiを導出する。
  • Public nonce Ri = kiGとそれがFで指定通りに計算されたことを示す非対話型のゼロ知識証明を生成し、他の参加者に送信する。
  • ↑のゼロ知識証明はhost keyとよばれる公開鍵を使って他の署名者が検証できるようになっている。
  • もし署名者の誰かが2つの異なるnonceを送信しチートしようとした場合、その内の1つのゼロ知識証明は無効と判定される。
  • 無効なゼロ知識証明を持つnonceに対しては自身が担当する署名値sの計算はせずプロトコルを中止する。

↑のnonceを導出するために使われる関数FがPurifyという特殊関数で、SHA256などのハッシュ関数と比べてゼロ知識証明用に最適化されている模様。Purifyは演算回路で、secp256k1のような256 bitの楕円曲線に対応したものでは2030個の乗算ゲートを持つ。

MuSig2?

↑のブログだと現在ゼロ知識証明を必要とせず2ラウンドで実行可能、また最初のラウンドの前処理により1ラウンドの最適化も可能という後継のMuSig2に取り組んでいるようなので、その発表も期待したい。

EthashのPoWとLight Clientの検証コスト

最近、Geth v1.9.0で導入されたUltra Light ClientがブロックヘッダーのPoWの検証をスキップしているのを知った。Bitcoinとかだと軽量ノードはブロックヘッダーのみダウンロードし有効なPoWのチェックはしてるから何故そういうアプローチなのか、EthereumのPoWアルゴリズムであるDagger-HashimotoをベースにしたEthash↓の仕組みと検証アルゴリズムについて調べてみた。

https://eth.wiki/en/concepts/ethash/ethash

EthashのPoWの仕組み

EthashのPoWは大きく分けて初期化、マイニング、検証の3つの段階がある。

初期化

Ethereumでは30,000ブロック = 1エポックとして、エポック毎にマイニングに使用するためのデータセットを初期化する必要がある。初期化のステップは↓

  1. まずseedハッシュを計算する。これは32バイトの00をエポックの数分のKeccak-256ハッシュを計算することで得られる。つまり、あるエポックのseed値はその前のエポックのseed値のKeccak-256ハッシュ値になる。これによりエポック毎にseed値が変わる。
  2. 続いて計算したseedを使ってキャッシュを生成する(擬似コードこちら)。
    1. 各エポック毎のキャッシュサイズは2,048エポック分(=61,440,000ブロック)までハードコードされており、キャッシュサイズ / 64を計算する。
    2. seedのKeccak-512ハッシュ値を計算し、それをキャッシュサイズ/64回繰り返す。計算したハッシュ値は64バイトでそれぞれ配列に格納される。これでキャッシュサイズ分のメモリを埋める。
    3. 続いて2を初期キャッシュとしてSergio Demian LernerのRandMemoHashアルゴリズムを実行する。実行結果を初期キャッシュとしてこれを合計3回実行する。
  3. 生成したキャッシュからデータセットを生成する。データセットのサイズもキャッシュのサイズと同様エポック毎に線形に増えていく。またキャッシュサイズと同様2,048エポック分(=61,440,000ブロック)までハードコードされている。具体的にはデータサイズ / 64回ループを実行して、以下の手順でデータセット内のデータアイテムを生成する(ループのインデックスをiとし、生成するデータ変数をmixとする)。
    1. キャッシュデータのリストのi % ハッシュデータのサイズ 番目のデータをmixの初期値とする。
    2. mixの先頭バイトを先頭バイトとインデックスiのXOR値にする。
    3. mixを値をKeccak-512ハッシュした値にする。
    4. キャッシュデータからデータを擬似ランダムに選択し、それとmixを結合してFNVハッシュを計算し、それをmixとする。これを256回繰り返す。
    5. 最後にmixをKeccak-512ハッシュした値がデータアイテムになる。

データアイテムは要約すると、キャッシュデータから擬似ランダム(決定論的)に選択した値を結合してそのハッシュを256回計算してできたもの。キャッシュサイズよりデータセットの方が要素の数は多いので、↑のようにインデックスiをキャッシュデータのサイズでmodしてる。Ethereum wikiで公開されているPythonの擬似コードが参考になる。

こうやってエポック毎にマイニングに使用するデータセットを作成する必要がある。なお、データセットを必要とするのは、マイナーとfull syncをするフルノードのみ。Light Client(LESプロトコル)やフルノードでもfast syncの場合、キャッシュのみ保持していればいい。

キャッシュとデータセットのサイズについて
  • キャッシュサイズとデータセットサイズは厳密に線形増加せず、周期的に増加していくとそれに伴う偶発的な規則性のリスクを排除するため、線形増加する閾値を下回る1番近い素数が採用されるようになっている。
  • 最初のエポックのキャッシュサイズが16,776,896なので、初期のキャッシュサイズは約16MB。それが線形に増えていき、現在10671299ブロックのエポックは355なので、そのハッシュサイズは63,307,072で約60MBほど。
  • データサイズは最初のエポックで1,073,739,904で約1GBで、現在10671299ブロックのエポックは355なので、そのデータセットサイズは、4051695488で約3.7GBほどになる。

マイニング

マイニングは、生成したデータセットから以下の計算をして、目標のターゲット値を下回るハッシュ値を計算すること。

  1. 新しいブロックヘッダーについて、mixHashフィールドとnonceフィールド(8バイトの符号なし整数)を除いたRLP表現のヘッダーのKeccak-256ハッシュを計算する。
  2. 1のブロックヘッダーのハッシュとnonceを結合してKeccak-512ハッシュを計算する。これが64バイトのシード。
  3. 128バイトのデータmixを初期化する。具体的には128バイト満たすまで、2のシードデータを追加し、128バイトになるよう切り捨てる。
  4. データセットから順次128バイト読み出して、mixに結合してfnvハッシュ値を計算し、その値でmixを更新する。これを64回繰り返す。
  5. mixを圧縮して(この圧縮した値がブロックヘッダーにセットされるmixHash)、2のシードと結合してKeccak-256ハッシュ値を計算する。
  6. 5の値が目標のターゲット値を下回っていた場合、2で使ったnonceは有効と判断されPoWは成功する。ターゲット値を下回っていない場合、2のnonceをインクリメントして再度計算を実行する。

↑の擬似コードこちら

4のデータセットからのフェッチがシーケンシャルに実行されるため、データ・セットは基本的にRAMに配置する必要があり、これを持ってASIC耐性としている。

PoWの検証

EthashはのPoWの検証は、ターゲット値を下回るブロックヘッダーのハッシュが、正しいデータセットから生成されたものであることを証明することで、この証明の方法、具体的には検証に必要なデータセットのデータの取得方法が、Full ClientとLight Clientで異なる。

Full Clientの検証方法

Full Clientはデータセットを保持しているので、オンメモリに展開しているデータセットを使って検証を行う。つまり↑と同じ計算を実行する。

※ ただFull Clientといってもこれを実行してるのはfll syncの場合で、fast syncの場合はLight Clientと同様の検証をしてるっぽい。

Light Clientの検証方法

Light Clientの場合、キャッシュは持っているがデータセットは持っていない。そのためオンメモリのキャッシュデータを使って、必要となるデータセットのデータを都度計算するという方法を採っている。Gethのコードだとconsensus/ethash/algorithm.goの↓

// hashimotoLight aggregates data from the full dataset (using only a small
// in-memory cache) in order to produce our final value for a particular header
// hash and nonce.
func hashimotoLight(size uint64, cache []uint32, hash []byte, nonce uint64) ([]byte, []byte) {
    keccak512 := makeHasher(sha3.NewLegacyKeccak512())

    lookup := func(index uint32) []uint32 {
        rawData := generateDatasetItem(cache, index, keccak512)

        data := make([]uint32, len(rawData)/4)
        for i := 0; i < len(data); i++ {
            data[i] = binary.LittleEndian.Uint32(rawData[i*4:])
        }
        return data
    }
    return hashimoto(hash, nonce, size, lookup)
}

この違いのため、PoWの検証はFull Clientの方が高速で、Light Clientの検証はそれに比べて遅くなる。

Light Clientの検証コスト

Light Clientは巨大なデータセットを持たなくて済む反面、検証時に必要なデータセット内のアイテムを都度計算しないといけないトレードオフがあるのは分かった。Light Clientにとって具体的なPoWの検証コストは、以下のようになる。

初期化コスト

初期化はエポック毎に発生するので毎ブロックではないが、ブロックチェーンの成長と共にキャッシュサイズも成長する。初期16MBだったキャッシュのサイズは現在約60MBだ。

前述したキャッシュ計算の仕組みにより、線形に増加するキャッシュサイズと共に、Keccak-512のハッシュ計算の回数も増え計算コストが増加する。具体的には、エポック毎に(増加したキャッシュサイズ / 64) ✕ 2回の計算コストが増える。

PoWの検証コスト

Light Clientの検証方法では、1回のPoW検証につき

  • 256回のKeccak-256ハッシュ計算
  • 65664回のFNVハッシュ計算

のコストが発生する。こちらはキャッシュサイズやデータセットのサイズに関係なく一定だ。

Ultra Light Client

Bitcoinの場合PoWの検証はSHA-256ハッシュ計算を2回だけすれば済むのに比べると結構コスト高だ。このコストを削減するのに、Geth v1.9.0で導入されたUltra Light Clientでは(LESプロトコルのオプションという位置付けだが)、↑のPoWの検証ステップが削除され、代わりにTrusted LES Serverによる署名付き通知とCHTを利用したブロックヘッダーの有効性の検証に切り替わっている↓

hackmd.io

オプションだからというのもあるかもしれないけど、思い切ってPoW検証捨てるのは意外だった。まぁ信頼点ある方が効率的にはなる。

最初に成功し現在も攻撃コストが最も高くASIC耐性の無いBitcoinはともかく、後発のブロックチェーンにとってどういうPoWアルゴリズムを採用するかは悩みどころだと思う。ASIC耐性をどう捉えるか?PoWにおけるハッシュパワーの移動をどう考慮するか?検証コストが与える軽量ノードへの影響は?など現状を踏まえて考慮すべきことが増えてるなーという印象。

Lightning Networkの新しいチャネルコントラクトの提案「Generalized Channels」

少し前に発表されたLightning Networkの改善提案のペーパー「Generalized Bitcoin-Compatible Channels」↓

https://eprint.iacr.org/2020/476.pdf

簡単に言うと↓の特性を持つ、現在のLightning NetworkのPoon-DryjaスタイルのPayment Channelの改良

  • 共通のコミットメントトランザクションを構成する。
    Poon-DryjaスタイルのPayment Channelでは、チャネル参加者が保持するコミットメントトランザクションは非対称なもので、それぞれ異なるコミットメントトランザクションを管理するが、Generalized Channelsでは、両者が保持するコミットメントトランザクショントランザクションは同じものになる。これには以下のようなメリットがある。
    • チャネル更新の通信量がより小さくなり、シンプルになる。
    • コミットメントトランザクションがブロードキャストされた場合のオンチェーンフットプリントも小さくなる。
  • 現時点でデプロイ可能である。
    Generalized ChannelsはECDSA + Adaptor Signatureで構成可能なので、現時点でもデプロイが可能である。

相手が古いチャネル状態を公開しようとした場合、チャネル資金が全額没収されるペナルティタイプのPayment Channelである点はPoon-DryjaスタイルのPayment Channelと同じだ。一方で、eltooのように共通のコミットメントトランザクションを構成するようになっている。ただ、eltooの場合、新しいSIGHASH_TYPEの導入が必要で、それにはBitcoinのソフトフォークが必要になるが、Generalized Channelsは、既存のプロトコルで利用可能だ。eltooについて知りたい場合は↓参照。

goblockchain.network

Poon-DryjaスタイルのPayment Channel

Payment Channelを構成する際に登場する主なトランザクションは以下の2種類。

  1. ファンディングトランザクション
    チャネルを構成する際に、チャネル参加者の2-of-2マルチシグアウトプットにコインをロックするためのトランザクションで、オンチェーントランザクション
  2. コミットメントトランザクション
    ファンディングトランザクションのアウトプットを使用するトランザクションで、オフチェーンで支払いをするたびに更新される。基本的にはオフチェーントランザクションだが、相手が応答しないなどでチャネルの協調クローズができない場合に、チェーン上にブロードキャストされる。

2のコミットメントトランザクションは(HTLCを除いた場合、)チャネル参加者のそれぞれの残高を持つ2つのアウトプットを持つ。そのうち自分の残高のアウトプットは以下の2つのいずれかの条件でアンロックされる。

  • タイムロック期間が過ぎれば自分で使用できる。
  • あるシークレット値(per_commitment_secret)を知っていれば相手が使用できる。

オフチェーン支払いをする場合、残高を更新した新しいコミットメントトランザクションを作成し、前のコミットメントトランザクションのシークレット(per_commitment_secret)をお互い相手に通知する。

Generalized Channels

↑の構成だと、参加者はそれぞれ異なるコミットメントトランザクションを持つが、Generalized Channelsでは、両者が同じコミットメントトランザクションを持つ。このコミットメントトランザクションが持つアウトプットは1つのみで、チャネルの資金を全て保持している。このコミットメントトランザクションはタイムロックの後、後続のスプリットトランザクションで使用でき、このスプリットトランザクションは参加者のその時点の残高をそれぞれ保持する複数のアウトプットを持つ。

f:id:techmedia-think:20200807212037p:plain
Generalized Channelsの構成

チャネルのセットアップ

アリスとボブがGeneralized Channelsをセットアップする手順は以下の通り。

アリスの鍵ペアを  {P_{A} = x_{A} G}、ボブの鍵ペアを {P_{B} = x_{B} G}とする。

  1. 両者は最初にファンディングトランザクションを作成する。このトランザクションは、これまでと同様、チャネル資金を {P_{A}, P_{B}}の2-of-2のマルチシグアウトプットにロックするオンチェーントランザクション
  2. 続いてチャネルの初期状態にコミットするコミットメントトランザクションを構成する。
    1. 両者は取り消し用の鍵ペアを作成し、その公開鍵を相手に伝える。
      • アリスは {R_{A} = r_{A} G}を計算し、 {R_{A}}をボブに伝える。
      • ボブは {R_{B} = r_{B} G}を計算し、 {R_{B}}をアリスに伝える。
    2. 両者は公開用の鍵ペアを作成し、その公開鍵を相手に伝える。
      • アリスは {Y_{A} = y_{A} G}を計算し、 {Y_{A}}をボブに伝える。
      • ボブは {Y_{B} = y_{B} G}を計算し、 {Y_{B}}をアリスに伝える。
    3. ファンディングトランザクションをマルチシグアウトプットを使用するコミットメントトランザクションを作成する。アウトプットは1つのみで、このアウトプットを使用できる条件は以下の3つのいずれか。
      • タイムロック期間Δが経過したら、公開鍵 {P_{A}} {P_{B}}に対して有効な署名があれば使用可能(後続のスプリットトランザクション用のアンロック条件)
      •  {r_{A}} {y_{A}}が分かれば、公開鍵 {P_{B}}に対して有効な署名があれば使用可能(アリスが不正をした場合のペナルティ用)。
      •  {r_{B}} {y_{B}}が分かれば、公開鍵 {P_{A}}に対して有効な署名があれば使用可能(ボブが不正をした場合のペナルティ用)。
  3. コミットメントトランザクションのアウトプットを使用するスプリットトランザクションを作成する。
    • このトランザクションは、アリスの残高とボブの残高をそれぞれに送金する2つのアウトプットを持つ(一方の残高が0であれば1つになる)。
    • コミットメントトランザクションのアンロック条件はタイムロック+公開鍵 {P_{A}} {P_{B}}に対して有効な署名。
  4. スプリットトランザクションに対して、アリスは {x_{A}}を使って、ボブは {x_{B}}を使って署名を計算し、お互い交換する。
  5. アリスとボブはコミットメントトランザクションについてAdaptor Signatureをそれぞれ作成し、交換する。
    • アリスは秘密鍵 {x_{A}}とボブから受け取った {Y_{B}}を使ってAdaptor Signatureを作成し、ボブに送信する。この署名を完成させるためにはボブは {y_{B}}を加算する必要がある。
    • ボブは秘密鍵 {x_{B}}とアリスから受け取った {Y_{A}}を使ってAdaptor Signatureを作成し、アリスに送信する。この署名を完成させるためにはアリスは {y_{A}}を加算する必要がある。
  6. 最後に両者はファンディングトランザクションに署名し、ブロックチェーンネットワークにブロードキャストする。

チャネルの更新

チャネルを更新する(オフチェーン支払いを行う)際の手順は、

  1. ↑のように新しいコミットメントトランザクションを作成する。それぞれYとRの鍵は新しく生成したものになる。
  2. さらに新しいコミットメントトランザクションのコインを使用するスプリットトランザクションを作成する。アウトプットはそれぞれ支払いにより更新した残高を持つ。
  3. ↑と同様スプリットトランザクションの署名と、コミットメントトランザクションのAdaptor Signautreを交換する。
  4. 最後に古いコミットメントトランザクションを無効にするため、両者ともに前のコミットメントトランザクションの取り消し用のシークレット {r_{A}, r_{B}}を交換する。

チャネルのクローズ

チャネルのクローズは、既存のPayment Channelの実装と同様、2つの方法がある。

  • 協調クローズ
    両者が協力し、ファンディングトランザクションのアウトプットをチャネルの最終残高に応じてそれぞれに分配するクロージングトランザクションを作成し、ブロードキャストする。
  • 一方的なクローズ
    最新のコミットメントトランザクションをブロードキャストする。この場合コミットメントトランザクションがブロックに格納されてから指定されたタイムロック期間経過すればそれぞれチャネルの最終残高が手に入る。

不正をした場合の動作

どちらかが古いコミットメントトランザクショントランザクションをブロードキャストした場合(アリスが不正したと仮定すると)、その状態の残高が配分されるスプリットトランザクションをブロードキャストできるようになるまでタイムロックが設定されているので、その間に不正をされたボブは、

  • チャネル更新時に交換したそのコミットメントトランザクションの取消用の鍵 {r_{A}}
  • アリスがブロードキャストしたコミットメントトランザクションと、事前に受け取ったAdaptor Signatureの差分を計算し {y_{A}}を入手する。

の2つのデータ( {r_{A}, y_{A}})と自身の {x_{B}}を使って、ブロードキャストされたコミットメントトランザクションのアウトプットの資金=チャネルの全資金を自身に送金するパニッシュメントトランザクションを作成しブロードキャストする。

ポイント

Generalized Channelsのポイントはコミットメントトランザクショントランザクションの構成方法で、このアウトプットの使用条件に

  • 取消用のシークレットを組み入れる
  • コミットメントトランザクションが公開された時に初めて明らかになるシークレットを組み入れる

この2つの条件を組み入れたことだろう。これにより

  • 単純に最新のコミットメントトランザクションをブロードキャストする分には、取消用のシークレットは交換されていない=相手のシークレットを知らない状態なので、コミットメントトランザクションのペナルティ条件は使えない。
  • 古いコミットメントトランザクションをブロードキャストする=自身のが不正した証拠( {y_{A} もしくは y_{B}})を提供することになり、それを使ってペナルティ条件が利用可能になる。

を実現できる。

Generalized Channelsだと、冒頭に書いたように既存のコミットメントトランザクションの複雑さとトランザクションサイズも削減されるし、ペナルティをトランザクションを発行する際のトランザクションサイズも削減できメリットは大きい。Bitcoinの次のソフトフォーク(Schnorr + Taproot)にはSIGHASH_NOINPUTは導入されないので、当分eltooも導入できないだろうし。

実装方法と今後

↑のコミットメントトランザクションのアウトプットのスクリプトを実装する方法はいくつかあるが、すぐにデプロイするのであればECDSAのAdaptor Signatureに限定される。この場合、Lindellの2P-ECDSAをスクリプトレスに行うことも考えられるけど、Paillier暗号などの追加の暗号仮定の導入とかを考慮すると、少し前に提案されたOP_CHECKMULTISIGを使ったAdaptor Signature↓が現実的だと思う。

techmedia-think.hatenablog.com

もちろんSchnorrベースのAdaptor Sinatureの方が効率的ではあるので、実際のデプロイはSchnorrのアクティベートを待つという選択肢もある。