KZG10 与 Pairing

发布于 2023-08-03 16:36

阅读 2000

通过一天的交流学习大概弄清了KZG10与Pairing的勾迹关系，对PCS也有了更进一步认识，这里记录一下它们之间的逻辑关系。Thanks感谢@KurtPan博和@miles的热心交流讨论，让我重新认识了“椭圆曲线group上的标量乘法”与“椭圆曲线group上的元素乘法

通过一天的交流学习大概弄清了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)
$$

- 如果想把两个多项式的乘积封印在某个点上，又想保留这两个多项式的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$ 封印在一个点上

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

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

# 大家都在说

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

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

# KZG10 的目标

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 \\
$$

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]
$$

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

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

# First Try

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

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

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

# Second Try

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

$$
\begin{aligned}

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

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

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

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

\end{aligned}
$$

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

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

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

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

\Updownarrow \\

f(x) - v + u*q(x) = q(x) * x  \\
$$

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

# Another Try

基于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}
$$

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

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

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

整合一下就是:

$$
\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会更长，验证的成本也会更大，细节部分就不再展开了

![image.png](https://img.learnblockchain.cn/attachments/2023/08/RZ08Jwso64cb654da860d.png)

# 最后

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

通过一天的交流学习大概弄清了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)

如果想把两个多项式的乘积封印在某个点上，又想保留这两个多项式的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$ 封印在一个点上

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

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

大家都在说

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

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

KZG10 的目标

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 \\

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]

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

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

First Try

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

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

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

Second Try

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

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

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