KZG Commitment
101
1. 検証者が評価対象の多項式とx座標を送信する。
2. 証明者は、多項式に対するコミットメント、多項式の評価、評価の証明を計算する。
3. 証明者は、すべての情報を検証者に送る。
4. 検証者は、証明者が多項式を正しく評価し、正しい多項式にコミットしているかどうかをチェックする。
検証者が多項式を評価することはない
Variables
$ p\left(x\right): $ p\left(x\right) = {\sum_{{i}=0}^{n} c_{i} x^{{i}}}という形の評価したい多項式
$ (x,y): $ pによって評価される点
$ C: $ p(x)のコミットメント表現
$ π: 評価の証明
Functions
Setup: プロトコルの残りの部分で使用するパラメータを設定する
Commit: 多項式が与えられたときにCommitmentを作成する
CreateWitness: p上のxの評価の証明を生成する
VerifyPoly: コミットされた多項式と多項式が一致するかどうかをチェックする
VerifyEval: Commitされた多項式が正しく評価されたかどうかをチェックする
https://scrapbox.io/files/62f7a5c75e747a001dcfb61d.png
1. Trusted Setup
Common Reference String (CRS)、つまりtrusted Setup によって
よくある公開鍵暗号のように鍵の持ち主が自分の秘密鍵と公開鍵$ (α,g^α)を知っているのとは異なり、KZG10では「未知」の秘密鍵を持つ公開鍵の束が存在することになる。
証明者、検証者はこれらの公開鍵を作るためにどんな整数$ αが使われたか分からないが、それぞれの連続した公開鍵は$ αの別の連続したべき乗で以下の用に定義されていることは分かっている
$ g,g^α,g^(α^2),…,g^(α^t)
2.は省略
3.1 Commit
$ Commit(p)
$ g^{p(a)}=
$ g^{\sum_{i=0}^nα^ic_i}=
$ g^{α^nc_n+...+α^2c_2+α^1c_1+c_0}=
$ ∏_{i=0}^n(g^{α^i})c_i=
αが分からないので、まず$ p(α)-p(x),α-xの多項式分割を行い、得られた多項式をCRSで評価する必要がある
また、$ p(α)-p(x)の全ての項は$ (α^i-x^i)c_iの形式であるので、この分割による余りはないはずであると信頼することができる。
3.2Create Witness
あるxにおけるcommitがyであることを証明するには$ p(α)-y=0であることを証明すれば良い
$ π=CreateWitness(p,x,y)
$ =g^{ ϕ_α(x)}
$ =g^\frac{p(α)−p(x)}{α−x}
剰余の定理及び、「多項式a(x)を多項式b(x)で除算した場合の商をq(x)、余りをr(x)とした場合、a(x)=q(x)b(x)+r(x)と定義できる」性質を利用すると、因数定理によって多項式p(x)が(x−α)で割り切れる場合p(α)=0が成立するので、p(α)-p(x)を一つの多項式とみると$ p(α)-p(x)=0つまり$ p(α)-y=0が成立する 4.Verify Eval
ペアリングを使った計算により、以下のように等式検証する
$ VerifyEval(C,π,x,y)
$ e(π,g^{α−x})=e(Cg^{ −y} ,g)
$ e(g^\frac{p(α)−p(x)}{α−x},g^{α−x})=e(g^{−y+p(α)},g)
$ e(g,g)^{p(α)−p(x)}=e(g,g)^{−y+p(α)}
$ e(g,g)^{−y+p(α)}=e(g,g) ^{−y+p(α)}
簡単に言うと、2つのターゲットグループの点が等しいかどうか を確認している。
攻撃
不正なTrsuted Setupによって作成されるα
g^αでαを解くことになるので安全性はECDLPに依拠している
q-SDH, q-SBDH
これらの仮定は、ある数cとEC点$ g^{\frac{1}{α + c}}and/or $ e(g_2, g_2)^{\frac{1}{α + c}}.を見つけようとすることに帰着する
例えば、$ α=3の時
二つの多項式$ p_1(x)=x^3+10x^2+8x+6,$ p_2(x)=7x^2+19x+27について
$ g^{α^3+10α^2 +8α+6 }=g^{7α^2+19α+27}
$ g^{147} =g^{147}
$ g^{p_1(α)} =g^{p_2(α)}となる。
よってTrusted Setupによって生成される$ αが明かされるような状態では証明者及び検証者の公平性が保たれない。
不正なwitnessの作成
Commitmentがもたらすセキュリティ特性として以下の二つが定義される。
Binding:2つの異なるステートメントが同じコミットメントをすることはできないこと
Hinding:コミットメントがある場合、そのステートメントについて何も知られることがないこと
https://scrapbox.io/files/62fa6bdca97a36001fe9b81b.png
証明者として不正を行い、偽の $ y' を生成して$ VerifyEval をパスすることを考える。
https://scrapbox.io/files/62f7a5c75e747a001dcfb61d.png
そのためには、(C,y,π)を改ざんすることになるが、CはBindingの性質により不可能なので、残り二つについて考える。
yはπに含まれるのでyを変えればπが変わる。証明者が偽のy′の値を選びπのp(x)項をy'に変更してみると、Verify Evalにおいて検証者は$ -y'+p(α) を$ α-xで割るが、高い確率で余りが出てしまい、$ -y′+p(α)の再構成に失敗するため証明者が不正したことを認識できる。
正しい値であれば割り切ることができるが、それは唯一のものであり、不正に作成したものであれば多項式上にある無数の点をランダムに当てはめることと同義
言い換えると、証明者が$ -y'+p(α) が $ α-xで割り切れるような $ y'を見つけることができれば、ペアリング評価で検証者をだますことになり、$ -y'+p(α) の不正な再構築に成功する
しかしこれは、q-SDHを解くことに他ならない
q-SDHを解かずに騙すことはできないのか?
ここでwitnessの指数部の分子に注目し、以下のように展開してみると多項式$ p(α)-p(x)は必ず$ αに正の根($ p(α) = 0 を満たす値 α のこと)を持ち、$ α-xで割り切れることがわかる。 $ p(α)−p(x)=
$ =∑_{i=0}^nα^ ic_i− ∑_{i=0}^nc_ix^i
$ =∑_{i=0}^n−(α^i−x^i)c_i
検証者は$ -y'+p(α)=$ p(α)-p'(x)の形の多項式しか構成できないので因数定理により、$ y'から作れる多項式のうち、線形因子$ α-xで割れるものは、xの正しい評価値だけである. すなわち、そのような評価値を準備するためにq-SDHを解くしかない。
根や因数定理は高校数学の範囲なので理解しやすい
Batch proofs
根がある点$ (z_0,z_1,...,z_k)のセットで定義される多項式$ Z(x)= ∏_{i=0}^{k−1}x−z_iを以下の部分に導入する。
つまり複数存在した多項式を一つの(k-1)次多項式にまとめることでCommitmentをバッチすることができるという理屈
CreateWitnessBatch
$ g^\frac{p(α)−p(x)}{α−x}→ g^\frac{p(α)−L(x)}{Z(a)}
VerifyEvalBatch
$ e(π,g^{α−x})=e(Cg^{ −y} ,g)→e(π,g^{Z(α)})=e(Cg^{−L(α)} ,g)
πのサイズは元の単一の点と同じサイズ(1EC点)のままであるメリットが大きい。
また、通信オーバーヘッドが一定になる
しかしながら、CRSのサイズ=検証できる点の数なのでそのサイズがデメリットと言える
参考文献