Stanford Blockchain Conference 2019のGrinのセッションで、Grinの構成要素として挙げられていたSwitch Commitmentについて↓
https://eprint.iacr.org/2017/237.pdf
Bitcoinなどの多くの暗号通貨では楕円曲線暗号を導入しており、楕円曲線暗号の安全性は離散対数仮定の下に成立している。これは離散対数問題を解くのに現時点で効率的な方法がなく、総当りの計算をする必要があり計算量的に困難であるというもの。
しかし将来的に量子コンピュータなどの登場により離散対数問題が効率的に解かれる時代が来るかもしれない。そうなった場合に既存の暗号通貨は鍵長の変更や、暗号アルゴリズムの変更を求められるようになる。これは通貨によってソフトフォーク/ハードフォークによって切り替えが行われるだろうが、切り替えのタイミングを決めて、それ以降では新しい暗号アルゴリズムを使用できるようにし、既存のUTXOを新しいアルゴリズムでロックする新しいUTXOに移す必要がある。移さずにずっと据え置かれるUTXOは、その離散対数を解いた者に資金を奪われる可能性が高い。
このようにBitcoinなどであれば新しい暗号アルゴリズムもしくはパラメータに移行することで対処が可能だ。問題がより深刻なのはConfidential Transactionを導入しているチェーンである。BlockstreamのElementsやLiquid、Mimblewimbleを実装したGrinやBEAMなどが対象だ。
Confidential Transaction
コインの量はBitcoinの場合はトランザクションのアウトプットに明示的に正数値で記録されるが、Confidential Transactionではコインの量を以下のような準同型コミットメントであるPedersen Commitmentで管理している。
commitment = rG + vH
GおよびHは楕円曲線上の生成点で、rはブラインディングファクターでvを隠すためのランダムな値、vがコインの値。ランダム値はコインの受信者が決める値で、このコミットメントにいくらのコインがあるのかはrとxの値を知らないと分からない。つまり取引の当事者以外、第三者はこのコミットメントにいくらのコインがあるのか知りようが無い。こうやってコインの量を秘匿するのがConfidential Commitmentだ。検証方法など詳細が知りたい場合は↓
techmedia-think.hatenablog.com
離散対数仮定が成立しなくなった場合にどうなる？
量子コンピューターの登場などにより離散対数問題を解くことができるようになるとPedersen Commitmentを使用しているConfidential TransactionはBitcoinなどよりも大きな問題を抱える。
Confidential Transactionのチェーンを破壊するには１つの離散対数の値が分かればいい。上記Pedersen CommitmentのHの離散対数だ。 H = xGとなるようなxの値を攻撃者に知られるとまずい。
例えば攻撃者が既にConfidential Transactionを使っているチェーン上で誰かからコインを貰っておく＝自分がブラインディングファクターrを選択したCommitmentを入手する。
この状態でH = xGとなるxの値が分かると
r' = r + x(v - v')
を計算する。v'はv' > vとなる（コインを増やす）新しいコインの量である。この新しい(r', v')のペアを使うと
r'G + v'H = (r + x(v - v'))G + v' xG
= rG + x(v - v')G + v' xG
= rG + xvG
= rG + vH
= commitment
が成立し、コインの量を自由に制御可能になる。こうやって無からコインを生み出すことができる(r', v')のペアを計算できる。
Bitcoinの場合、離散対数の値が計算できるようになったとしても個人のコインが盗まれるだけで、コインを無から生み出すようなことはできない。また個人のコインが盗まれないよう暗号アルゴリズム・パラメータを変更することでこれに対処できる。Confidential Transactionの場合は、その性質上、上記のように無からコインを生み出すことができてしまい、チェーンに対する攻撃が可能になる。こういったリスクを回避するための仕組みがSwitch Commitmentだ。
Switch Commitment
上記のPedersen Commitmentは離散対数仮定に依存しているが、たとえ無制限の計算能力があったとしても性質を破ることが不可能であるコミットメントを追加し、検証処理をそのコミットメントに切り替えることでこの問題に対応する。Pedersen Commitmentに代わるコミットメント方式としてElGamal Commitmentを採用する。
ElGamal Commitment
ElGamal CommitmentはPedersen Commitmentとほとんど同じだが、Pedersen Commitmentの要素にもう１つ同じブラインディングファクター r と生成点Hを使って計算した点をコミットメントのデータとして持つ。
commitment = rG + vH, rH
rHのデータを追加することで、このコミットメントを開くには、rGとｒHのrが同じなければならない。このようなrのルールがある場合、いくら計算量があってHの離散対数がわかったとしてもvを変更することはできない。このようなElGamal Commitmentの特性により、コインを無から生成するような攻撃を回避することができるようになる。
またElGamal Commitmentが都合が良いのは、rHの部分を無視すると、今まで通りのPedersen Commitmentとして扱うことができるという点だ。
Confidential Transactoinではvの値がオーバーフローしない値の範囲内であることを保証するために別途、範囲証明をする必要があるが、現在CT用に設計されている範囲証明はいずれもPedersen Commitmentには最適化されているが、ElGamal Commitmentの範囲証明はそのような最適化はされておらず効率が悪い。
そのためコミットメントのデータ自体はElGamal Commitmentとして作成するが、検証の方法を2つ用意する。
- 部分検証 = Pedersen Commitmentによる検証
- 完全検証 = ElGamal Commitmentによる検証
離散対数仮定が崩れるようなおそれがあるまでは、今まで通り部分検証によりPedersen Commitmentを検証する。その後実際に脅威が訪れた際に完全検証に切り替えるソフトフォークを行う。そうすることで、チェーン上で無制限にコインが発行されチェーン自体を攻撃するといったリスクは回避することができるようになる。これがSwitch Commitmentだ。
※ ただ、注意が必要なのは、これはConfidential Transactionを構成するチェーンにおいて、無からコインを生成するようなことをできなくするための対応方法であって、離散対数問題が解かれた際にコミットメント内のコインの量のプライバシーを引き続き提供するものではない。つまり離散対数問題が解けているということは、そのコミットメントのコインの量が計算可能であるということだ。そのような状況になった場合は、秘匿系の仕組みは別途新しく考える必要があるだろう。
Grinの実装
mainnetがリリースされる前のバージョンのGrinでは上記方法でElGamal Commitmentが実装されており、トランザクションのアウトプットにrHのハッシュ値（switch commit hash：32バイト）が追加されていた。
その後、上記のElGamal Commitmentでアウトプット毎に追加の32バイトのデータスペースを消費することなく同様のことが可能なアイディアをTim Ruffingが提案され以下のように変更されたみたい。
通常のPedersen Commitmentではブラインディングファクターであるrの値はランダムに選択されるが、r自体はランダムにせず、別のランダムな値r'を使ってPedersen Commitmentを作る。
commitment = rG + vH r = r' + hash(vH + r'G, r'J)
JはHに次ぐ3つめの生成点。ハッシュ関数に渡すデータの部分がElGamal Commitmentになっていることが分かる。
検証の仕組みについてはまだよく見てないけど、基本的には初期はPedersen Commitmentで検証し、その後脅威が訪れた際にrの導出元となっているElGamal Commitmentを検証するように変更するといったアプローチか？ この辺はまたElGamal Commitmentの範囲証明のやり方含めて調べてみたい。
