最近公開された、Fiat-Shamir変換を正しく適用できていないプロトコルや実装において、証明システムの偽造が可能になる脆弱性「Frozen Heart」について↓
Fiat-Shamir変換とは？
Fiat-Shamir変換は、証明システムを非対話型にするために使用される有名なスキームで、検証者がランダムに選択するチャレンジの値を（ランダムオラクルモデルとして）暗号学的ハッシュ関数を使って決定論的に導出することで、証明システムのプロトコルを非対話型にする。
シンプルな適用例としては、RFC8235として定義されているSchnorr署名を使って離散対数の知識を知っていることをゼロ知識で証明するプロトコルとか↓
techmedia-think.hatenablog.com
RFC8235の概要は↓（簡略化のため、modの計算や群内の存在確認などは省略）
アリスがP = aGとなる公開鍵Pに対する離散対数（a）の知識をボブに証明したい場合。以下のステップで非対話的に証明する：
- アリスはランダムな値vを選択し、V = vGを計算
- アリスは暗号学的ハッシュ関数（H）を使ってチャレンジ c = H(G || V || P || UserID || OtherInfo)を計算する。
- アリスはr = v - c * aを計算
- (P, V, r)をボブに送る。
これに対しボブは、渡された情報（P, V, r, UserID, OtherInfo）からcを計算してV = rG + cPが成立するか検証する。
チャレンジcの値をボブがランダムに作って渡すのではなく↑のようにルールに従って生成することで、チャレンジのやり取りの対話を省略することができる。
Fiat-Shamir変換のポイント
↑のレポートにかかれているけど、Fiat-Shamir変換を適用する際のポイントは、チャレンジのハッシュ計算の際の入力に、証明するステートメントに関するすべての公開値（ランダムなコミットメント値を含む）を含める必要があるということ（↑の例だと入力は、G、V、P、UserID、OtherInfo）。
Frozen Heart
Frozen Heartは、↑のFiat-Shamir変換のポイントを遵守していないプロトコルや実装による脆弱性。
↑のRFC8235の例で考えてみよう。例えばチャレンジの計算にVが含まれていないとどうなるか？
- チャレンジ c = H(G || P || UserID || OtherInfo)を計算する。
- rにランダムな値を設定する。
- V = rG + cPを計算する。
こうやって後付けで辻褄があうように算出したVを含む(P, V, r)を検証者に送ると、V = rG + cPのチェックをパスすることが分かる。この時、証明者はV = vGとなるVの離散対数vを知らず、Pの離散対数aも知ることなく、検証をパスする証明を作成できてしまう。
Vがチャレンジのハッシュ計算に含まれていれば、こういった偽造はできない。これが↑のFiat-Shamir変換をする際の重要なポイント。
Frozen Heartの影響を受けるプロトコル/実装
Frozen Heartの脆弱性があるのは、プロトコル自体やその実装が、↑Fiat-Shamir変換のポイントを正しく行っていないケース。
↑のレポートでは、Giraultの知識証明と、値の範囲証明によく使われているBulletproofs、zk-SNARKベースの証明システムPlonKにおける脆弱性が取り上げられている。中でも影響度が大きいのは、BulletproofsとPlonKだろう。
Bulletproofsは、元の論文の非対話型プロトコルに問題があり、楕円曲線の群の位数の範囲内の値に対して証明の偽造が可能で、対象としていた範囲外の値に対して有効な範囲証明が作れてしまう。対象のプロダクトとしては、 Adjoint, Inc.のbulletproofsが取り上げられている。ちなみにMoneroの実装では脆弱性は回避されてるっぽい（Grinはどうなんだろう？）。偽造方法の詳細について、後続のレポートで解説されてる。
PlonKは、論文でFiat-Shamir変換の計算方法を明示的に説明せず、transcriptをハッシュ化するよう記載しており、その内容を明示的に記載していないことから、Dusk Networkのplonk、iden3のSnarkJS、ConsensysのgnarkでFrozen Heartの脆弱性が報告されている。具体的には算術回路への入力値をFiat-Shamirの計算に含めなかったことで、証明の偽造が可能になっていた。つまり、プログラムが正しく実行されたことが保証されなくなってしまう。具体的な偽造手順は、後続のレポートで解説されてる。
PlonKに限らず他の論文でもメインの内容は証明システムの新しい発明であって、それを非対話型にするのにFiat-Shamir変換を使うことがおまけ的に書いてあることは多いので、論文だけ読んでプロダクト実装しても脆弱性が含まれるケースは十分考えられる。zkは機能面ばかりフィーチャーされる傾向にあるけど、透過的なプロトコルと比べて脆弱性やバグがあっても発見し辛いので、このあたりのトレードオフはちゃんと評価する必要がある。
