通过一天的交流学习大概弄清了KZG10 与 Pairing 的勾迹关系，对PCS也有了更进一步认识，这里详细梳理了一下它们之间的逻辑关系。

Thanks

• 感谢@Kurt Pan 博和@miles 的热心交流讨论，让我重新认识了“椭圆曲线group 上的标量乘法” 与 “椭圆曲线group 上的元素乘法”。

• 感谢@郭宇 老师的点睛之语，让我重新审视两个多项式乘积的commit 

Takeaways

• commit 的本质是把一个多项式或者一串多项式系数通过椭圆曲线group上大量的加法操作给封印在某个点上，基于DL 是一个困难问题，由这个点无法倒推出相应的多项式，但又能保证bind 特性，因而起到加密的作用

$$ [a] = G^{a} = b \

a \overset{\textcolor{red} {\text{Hard}}}\Longleftarrow \log_G(b) $$ <br />

• 如果想把两个多项式的乘积封印在某个点上，又想保留这两个多项式的bind 特性，这是一个困难问题，pairing 提供了一个思路，它的特性保证了两个多项式的bind 特性

$$ [a*b] = e([a], [b]) = c $$

简单地说就是，pairing 能够保证$c$是由$ a b$得来的，而不是$e f$得来的。例如：

$$ x^4 * x^2 = x^6 $$

给定$x^6$我们可以有多个两两相乘的组合，但pairing 可以把$x^6$ 的由来$x^4$ 和$x^2$ 封印在一个点上

<br />

• pairing 的特性拟合出了两个多项式乘积的commit

$$ e([a], [b]) = e(G^{a}, H^{b}) = e(G, H)^{ab} $$

大家都在说

【因为椭圆曲线没有乘法定义，所以才引入pairing】但不一定都能把这里面的逻辑理清楚。

<br />

了解KZG10 协议的可能真看不出来其中“椭圆曲线乘法”说法的由来，那这个由头是否还站得住脚？是否有更充足或者直观的由头来勾出Pairing？

KZG10 的目标

<br />

KZG10 要证明的等式

$$ \text{opening}: f(u) = v \Longrightarrow f(u) - v = 0 \

\exists q(x) \text{ s.t.}

f(x) - v = q(x)(x - u), \text{if } x = u \ $$

<br />

Prover 需要做一些工作，来证明上面的scalar 等式成立，由scalar 等式转换到 commit 等式

$$ \begin{aligned} f(x) - v &= q(x)(x - u) \

\textcolor{red} \Updownarrow \

[f(x) - v] &= [q(x)(x - u)] \

\end{aligned} $$

commit 等式左边好拆解

$$ [f(x) - v] = [f(x)] - [v] $$

<br />

但等式右边有两个多项式因子$q(x)$ 和$ (x−u)$，对它们乘积做commit 其实是件比较困难的事情

$$ g^{z} \textcolor{red} {\overset{Hard} =} g^{a*b} $$

First Try

<br />

比如，如果按照正常逻辑，即椭圆曲线群上的标量乘法，来拆解的话就是：

$$ [q(x)(x - u)] = [q(x)](x - u) $$

<br />

最终拆解得到的是一个scalar mul，但Verifier 又拿不到scalar 部分 $(x−u)$ 的值，所以这么拆解是徒劳无功的。

Second Try

<br />

但Verifier 可以拿到$[x] 、[q(x)]$，那么是不是可以拆解成下面这个样子：

$$ \begin{aligned}

[q(x)(x - u)] &= [xq(x) - uq(x)] \

&= [xq(x)] - [u q(x)] \

&= [xq(x)] - u[q(x)] \

&\textcolor{red} {\overset{?} =} [x] [q(x)] - u[q(x)] \

\end{aligned} $$

<br />

因为$[q(x)] $可以轻松拿到，也就是说$u [q(x)]$也完全没问题。但是，需要重点关注$[x q(x)] \textcolor{red} {\overset{?}=} [q(x)] * [x]$，这是一个假想中的“椭圆曲线群上的元素乘法”(也就是点的乘法)的拆解结果，也就是说假定在拿到$ [x]、[q(x)]$ 的情况下可以证明原等式成立？

<br />

$$ [f(x)] - [v] = [x] [q(x)] - u[q(x)] \

\textcolor{red} {\overset{?} \Downarrow} \

f(x) - v = q(x) (x - u) \

\Updownarrow \

f(x) - v + uq(x) = q(x) x \ $$

<br />

即使这个假设成立，但是椭圆曲线没有点的乘法，也是说算不出来 $[x]∗[q(x)]$，所以此路仍然行不通。

Another Try

<br />

基于Verifier 可以拿到的$[x]、[q(x)]$ ，引入bilinear mapping，把两个polynomial 乘积$q(x)∗x$ 的commit 通过pairing 的形式给拟合出来：

$$ \begin{aligned}

[q(x) * x]_{T} &= e([q(x)], [x]) \

&= e(G^{q(\tau)}, H^{\tau}) \

&= e(G, H)^{q(\tau) * \tau}

\end{aligned} $$

<br />

$G^{q(\tau)} $和$H^{\tau}$分别为两个polynomial 分别在椭圆曲线$E_G $和 $E_T$上的commit，那么$ e(G^{q(\tau)}, H^{\tau})$ 就表示这两个commit 点映射到目标椭圆曲线$E_T$后相乘得到的点。 <br />

$e(G, H) $ 就是两个generator 映射到目标椭圆曲线$E_T$后相乘得到的点，那么$e(G, H)^{q(\tau) * \tau}$ 就是*两个polynomial 乘积$q(\tau) \tau$ 在目标椭圆曲线上的commit 点**。​ <br />

从这里能看到什么？对，椭圆曲线乘法 和 多项式乘积的commit。 <br />

整合一下就是:

$$ \begin{aligned}

f(x) - v &= q(x) * (x - u) \

\Updownarrow \

f(x) - v + u q(x) &= q(x) x \

\Updownarrow \

[f(x) - v + u q(x)] &= [q(x) x] \

\Updownarrow \

e([f(x) - v + u * q(x)], [1]) &= e([q(x)], [x]) \

\Updownarrow \

e(G^{(f(\tau) - v + u * q(\tau))}, H^{1}) &= e(G^{q(\tau)}, H^{\tau}) \

\Updownarrow \

e(G^{f(\tau) + u* q(\tau) - v}, H^{1}) &= e(G^{q(\tau)}, H^{\tau}) \

\Updownarrow \

e(\frac{G^{f(\tau)} * (G^{q(\tau)})^u}{G^v}, H^1) &= e(G^{q(\tau)}, H^{\tau}) \

\end{aligned} $$

其中 $H1$ 和 $H^{\tau}$ 在setup 阶段就拿到了，$G^{f(\tau)}、G^{q(\tau)}、(G^{q(\tau)})^u、G^{v}$都是需要prover 在收到opening 请求$u$ 后计算的。​

Suboptimal Try

对于两个多项式乘法的commitment $[q(x) * x] $ 有没有不用binlinear mapping的方案呢？有，但proof size会更长，验证的成本也会更大，细节部分就不再展开了

最后

所以更intuitive 的解释是：Verifier 拿不到 $\tau$ ，算不出$\tau q(\tau)$ 的commit $[\tau q(\tau)]$，通过bilinear maping 的形式实现了$[\tau * q(\tau)]$，且满足binding 特性。