Develop with pleasure!

福岡でCloudとかBlockchainとか。

Grinで発見された脆弱性CVE-2020-6638の内容

ちょっと前にGrinで発表された脆弱性CVE-2020-6638↓の内容について見てみる。

https://github.com/mimblewimble/grin-security/blob/master/CVEs/CVE-2020-6638.md

Grinの構成要素

具体的な脆弱性の解説の前に、Grinの構成要素について抑えておく↓

Pedersen Commitment

GrinではMimblewimble実装のためトランザクションのアウトプットが以下のようなPedersen Commitmentになっている。

C = rG + vH

Gはベースポイント、Hは誰もその離散対数を知らない2つめのベースポイントで、rがブラインドファクター、vがコインの量。

このPedersen Comittmentは、加法準同型性を持っているので、以下のような加算が可能である。

C1 = r1G + v1H
C2 = r2G + v2H

C1 + C2 = (r1 + r2)G + (v1 + v2)H

そしてGrinでは、アウトプットの合算からインプットの合算を差し引くことで、vの合算値が0になることでコインの総量が増えていないことを証明し(正確にはrange proofと合わせて)、残ったrについて、それを秘密鍵とした有効な署名を作ることで有効なトランザクションを作成している。具体的な仕組みについては、GBECの解説動画参照↓

goblockchain.network

ノードの検証内容

各Grinノードは、以下のデータを持っている。

そしてこの3つそれぞれに対してMMR(後述)を持っている。Grinの完全なステートを維持していると、以下の検証が可能になる。

  1. トランザクションカーネルの署名が正しいか検証する。
  2. 全ブロックのカーネルコミットメントの合計が、全てのTXOコミットメントからコインの供給量を引いたものと等しい(全てのTXOコミットメント値からコインの供給量を引くとコミットメントのHの項が0Hとなり、ブラインドファクターのみが残り、その合計がカーネルコミットメントの合計となるため)。これにより、全てのカーネルとコミットメントが正しく、コインが予期せず生成されていないことが証明される。
  3. TXOセット、range proof、トランザクションカーネルに対してそれぞれMMRを維持しており、各ブロックヘッダーはこの各MMRにコミットしている。

3つのMMRの内、TXOセットのMMRは追記専用でジェネシスから全てのアウトプットのコミットメントで構成されている。

MMRとは?

MMRというのはMerkle Mountain Rangesの略で、マークルツリーを代替するもの。MMRは追記のみをサポートするツリーで、要素は左から右へと追加され、ペアができるとそれに親が構成させる。例えば11個の要素を追加したツリーは以下のようになる。

高さ

3              14
             /    \
            /      \
           /        \
          /          \
2        6            13
       /   \        /    \
1     2     5      9     12     17
     / \   / \    / \   /  \   /  \
0   0   1 3   4  7   8 10  11 15  16 18

各要素は全て左から順にツリーのリーフとして追加され、ペアができるとその上のノードができ、高さ3のツリーが1つと高さ1のツリーが1つ、高さ0のツリーが1つできた山になる。

また値をプルーニングをすることも可能で、例えば上記のMMRからリーフ0, 3, 4, 8, 16を削除するとツリーは以下のようになる。

高さ

3             14
            /    \
           /      \
          /        \
         /          \
2       6            13
       /            /   \
1     2            9     12     17
       \          /     /  \   /  
0       1        7     10  11 15     18

3, 4のように左右の要素が無くなった場合、その親要素も削除される。

UTXOセット、range proof、トランザクションカーネルのデータについて、それぞれこのMMRを構成し、そのルートハッシュをブロックヘッダーにコミットするようになっている。

UTXOの管理

↑でTXOセットのMMRは全てのコミットメントを含んでいると述べたが、ではあるコミットメントが使用された場合どうなるのか?と疑問が生じる。

実は、コミットメントが使用済みかどうかはMMR自体では管理されず、軽量なbitmapで維持されている。各ビットはUTXOセットのMMRの各リーフにマッピングされており、このbitmapを使ってツリー上のどのコミットメントが使用済み/未使用なのか判断するようになっている。

脆弱性の内容

↑のようなPedersen Commitmentの特性を利用すると次のようなことが可能になる。

2つのアウトプットを持つトランザクションのアウトプットが上記C1, C2の2つのPedersen Commitmentであった場合、トランザクションカーネルを作成し、有効な署名を作った後でアウトプットを以下の2つの異なるPedersen Commitmentに置き換えることが可能になる。

C3 = r2G + v1H
C4 = r1G + v2H

C3 + C4 = (r2 + r1)G + (v1 + v2)H

合算したコミットメントであるC1 + C2 = C3 + C4になるためだ。

署名はアウトプットの合計からインプットの合計を差し引いた結果の公開鍵rGに対して有効な署名が作られればいいのだが、Grinの実装ではトランザクションの署名を作成する際に使用する署名対象のメッセージはトランザクションカーネルから作られる。具体的にいうと、手数料、kernel feature、block heightのデータで構成される。つまりBitcoinなどと違ってトランザクションのインプットやアウトプットがメッセージに含まれていないので、トランザクションに署名後にトランザクションのアウトプットをC3とC4に変更してもトランザクションの署名は有効なままとなる。

ブロックへの拡張

さらにこれをブロックレベルに拡張することができる。↑と同じ方法を使って、ブロック内で使用されるアウトプットのセットが異なる2つの競合するブロックを作ることができる。これはPoWも署名も有効なブロックを作成した後に、使用するアウトプット(インプット)のペアのみを置き換えることで簡単に作成することができる。

  • Block A
    • Inputs:
      • C1
      • C2
  • Block B
    • inputs:
      • C3
      • C4

C1とC2を使用するブロックAを作成し、その後C1とC2をC3, C4に置き換えたブロックを作った場合(いずれも送信先は同じ)、ブロックAとブロックBはブロックヘッダーもPoWも同じで有効なままだ。これはMMRがTXOにコミットしているため、ブロックAもブロックBもそのMMRは同じになり、競合するブロックを作れてしまう。UTXO自体をMMRで管理していないためだ。こによりUTXOのbitmap自体のmalleabilityが発生する。

ブロックAとブロックBが同じタイミングで公開されると、ブロックAを受信したネットワークAはC1、C2を使用済みとし、ブロックBを受信したネットワークBはC3, C4を使用済みとマークする。次にC3を使用するトランザクションをブロードキャストすると、ネットワークAではそれを使用可能として受け入れ、ネットワークBではそれを既に使用済みであるとして受け入れないという状況が発生し、この段階でチェーンが分岐する。

このような状況が発生すると分岐したチェーンを復元するのは難しい。幸いにもそういった現象が発生していないのが救いだ。

解決方法

修正の方針はシンプルで、現在ブロックヘッダーは全TXOに対してコミットしているが、これを全UTXOに対してコミットするように変更するというもの。具体的には既存のアウトプットのPMMR(プルーニングしたMMR)と現在の未使用のUTXOを管理しているbitmapの状態を組み合わせたルートにコミットするようになる。これにより↑のような競合ブロックを作成するのができなくなる。

またブロックヘッダーがUTXOに対してコミットするようになるので、チェーンの初期同期の遅延のボトルネックが改善されるという副次的効果もある。