{"content":{"title":"KZG10 与 Pairing","body":"通过一天的交流学习大概弄清了KZG10 与 Pairing 的勾迹关系，对PCS也有了更进一步认识，这里详细梳理了一下它们之间的逻辑关系。\r\n\r\n\r\n# Thanks\r\n\r\n\r\n- 感谢@Kurt Pan 博和@miles 的热心交流讨论，让我重新认识了“椭圆曲线group 上的标量乘法” 与 “椭圆曲线group 上的元素乘法”。\r\n\r\n\r\n- 感谢@郭宇 老师的点睛之语，让我重新审视两个多项式乘积的commit \r\n\r\n# Takeaways\r\n\r\n- commit 的本质是把一个多项式或者一串多项式系数通过椭圆曲线group上大量的加法操作给封印在某个点上，基于DL 是一个困难问题，由这个点无法倒推出相应的多项式，但又能保证bind 特性，因而起到加密的作用\r\n\r\n$$\r\n[a] = G^{a} = b \\\\\r\n\r\na \\overset{\\textcolor{red} {\\text{Hard}}}\\Longleftarrow \\log_G(b)\r\n$$\r\n
\r\n\r\n- 如果想把两个多项式的乘积封印在某个点上，又想保留这两个多项式的bind 特性，这是一个困难问题，pairing 提供了一个思路，它的特性保证了两个多项式的bind 特性\r\n\r\n$$\r\n[a*b] = e([a], [b]) = c\r\n$$\r\n\r\n 简单地说就是，pairing 能够保证$c$是由$ a * b$得来的，而不是$e * f$得来的。例如：\r\n\r\n $$\r\n x^4 * x^2 = x^6\r\n $$\r\n\r\n 给定$x^6$我们可以有多个两两相乘的组合，但pairing 可以把$x^6$ 的由来$x^4$ 和$x^2$ 封印在一个点上\r\n\r\n
\r\n\r\n- pairing 的特性**拟合**出了两个多项式乘积的commit\r\n\r\n\r\n$$\r\ne([a], [b]) = e(G^{a}, H^{b}) = e(G, H)^{ab}\r\n$$\r\n\r\n# 大家都在说\r\n\r\n【因为椭圆曲线没有乘法定义，所以才引入pairing】但不一定都能把这里面的逻辑理清楚。\r\n\r\n
\r\n\r\n了解KZG10 协议的可能真看不出来其中“椭圆曲线乘法”说法的由来，那这个由头是否还站得住脚？是否有更充足或者直观的由头来勾出Pairing？\r\n\r\n\r\n# KZG10 的目标\r\n\r\n
\r\n\r\nKZG10 要证明的等式\r\n\r\n$$\r\n\\text{opening}: f(u) = v \\Longrightarrow f(u) - v = 0 \\\\\r\n\r\n\\exists q(x) \\text{ s.t.} \r\n\r\nf(x) - v = q(x)(x - u), \\text{if } x = u \\\\\r\n$$\r\n\r\n
\r\n\r\nProver 需要做一些工作，来证明上面的scalar 等式成立，由scalar 等式转换到 commit 等式\r\n\r\n$$\r\n\\begin{aligned}\r\nf(x) - v &= q(x)(x - u) \\\\\r\n\r\n\\textcolor{red} \\Updownarrow \\\\\r\n\r\n[f(x) - v] &= [q(x)(x - u)] \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\ncommit 等式左边好拆解\r\n\r\n$$\r\n[f(x) - v] = [f(x)] - [v]\r\n$$\r\n\r\n
\r\n\r\n但等式右边有两个多项式因子$q(x)$ 和$ (x−u)$，对它们乘积做commit 其实是件**比较困难**的事情\r\n\r\n$$\r\ng^{z} \\textcolor{red} {\\overset{Hard} =} g^{a*b}\r\n$$\r\n\r\n\r\n# First Try\r\n\r\n
\r\n\r\n比如，如果按照正常逻辑，即**椭圆曲线群上的标量乘法**，来拆解的话就是：\r\n\r\n\r\n$$\r\n[q(x)(x - u)] = [q(x)](x - u)\r\n$$\r\n\r\n
\r\n\r\n最终拆解得到的是一个scalar mul，但Verifier 又拿不到scalar 部分 $(x−u)$ 的值，所以这么拆解是徒劳无功的。\r\n\r\n\r\n# Second Try\r\n\r\n
\r\n\r\n但Verifier 可以拿到$[x] 、[q(x)]$，那么是不是可以拆解成下面这个样子：\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n[q(x)(x - u)] &= [x*q(x) - u*q(x)] \\\\\r\n\r\n&= [x*q(x)] - [u * q(x)] \\\\\r\n\r\n&= [x*q(x)] - u*[q(x)] \\\\\r\n\r\n&\\textcolor{red} {\\overset{?} =} [x] * [q(x)] - u*[q(x)] \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n
\r\n\r\n因为$[q(x)] $可以轻松拿到，也就是说$u * [q(x)]$也完全没问题。但是，需要重点关注$[x * q(x)] \\textcolor{red} {\\overset{?}=} [q(x)] * [x]$，这是一个**假想中的“椭圆曲线群上的元素乘法”**(也就是点的乘法)的拆解结果，也就是说假定在拿到$ [x]、[q(x)]$ 的情况下可以证明原等式成立？\r\n\r\n
\r\n\r\n$$\r\n[f(x)] - [v] = [x] * [q(x)] - u*[q(x)] \\\\\r\n\r\n\\textcolor{red} {\\overset{?} \\Downarrow} \\\\\r\n\r\nf(x) - v = q(x) (x - u) \\\\\r\n\r\n\\Updownarrow \\\\\r\n\r\nf(x) - v + u*q(x) = q(x) * x \\\\\r\n$$\r\n\r\n
\r\n\r\n即使这个假设成立，但是**椭圆曲线没有点的乘法**，也是说算不出来 $[x]∗[q(x)]$，所以此路仍然行不通。\r\n\r\n# Another Try\r\n\r\n
\r\n\r\n基于Verifier 可以拿到的$[x]、[q(x)]$ ，引入bilinear mapping，把两个polynomial 乘积$q(x)∗x$ 的commit 通过pairing 的形式给拟合出来：\r\n\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\n[q(x) * x]_{T} &= e([q(x)], [x]) \\\\\r\n\r\n&= e(G^{q(\\tau)}, H^{\\tau}) \\\\\r\n\r\n&= e(G, H)^{q(\\tau) * \\tau}\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n
\r\n\r\n$G^{q(\\tau)} $和$H^{\\tau}$分别为两个polynomial 分别在椭圆曲线$E_G $和 $E_T$上的commit，那么$ e(G^{q(\\tau)}, H^{\\tau})$ 就表示这**两个commit 点映射到目标椭圆曲线$E_T$后相乘得到的点**。\r\n
\r\n\r\n$e(G, H) $ 就是两个generator 映射到目标椭圆曲线$E_T$后相乘得到的点，那么$e(G, H)^{q(\\tau) * \\tau}$ 就是**两个polynomial 乘积$q(\\tau) * \\tau$ 在目标椭圆曲线上的commit 点**。\r\n
\r\n\r\n从这里能看到什么？对，**椭圆曲线乘法** 和 **多项式乘积的commit**。\r\n
\r\n\r\n整合一下就是:\r\n\r\n$$\r\n\\begin{aligned}\r\n\r\nf(x) - v &= q(x) * (x - u) \\\\\r\n\r\n\\Updownarrow \\\\\r\n\r\nf(x) - v + u * q(x) &= q(x) * x \\\\\r\n\r\n\\Updownarrow \\\\\r\n\r\n[f(x) - v + u * q(x)] &= [q(x) * x] \\\\\r\n\r\n\\Updownarrow \\\\\r\n\r\ne([f(x) - v + u * q(x)], [1]) &= e([q(x)], [x]) \\\\\r\n\r\n\\Updownarrow \\\\\r\n\r\ne(G^{(f(\\tau) - v + u * q(\\tau))}, H^{1}) &= e(G^{q(\\tau)}, H^{\\tau}) \\\\\r\n\r\n\\Updownarrow \\\\\r\n\r\ne(G^{f(\\tau) + u* q(\\tau) - v}, H^{1}) &= e(G^{q(\\tau)}, H^{\\tau}) \\\\\r\n\r\n\\Updownarrow \\\\\r\n\r\ne(\\frac{G^{f(\\tau)} * (G^{q(\\tau)})^u}{G^v}, H^1) &= e(G^{q(\\tau)}, H^{\\tau}) \\\\\r\n\r\n\\end{aligned}\r\n$$\r\n\r\n其中 $H1$ 和 $H^{\\tau}$ 在setup 阶段就拿到了，$G^{f(\\tau)}、G^{q(\\tau)}、(G^{q(\\tau)})^u、G^{v}$都是需要prover 在收到opening 请求$u$ 后计算的。\r\n\r\n# Suboptimal Try\r\n\r\n对于两个多项式乘法的commitment $[q(x) * x] $ 有没有不用binlinear mapping的方案呢？有，但proof size会更长，验证的成本也会更大，细节部分就不再展开了\r\n\r\n\r\n\r\n# 最后\r\n\r\n所以更intuitive 的解释是：Verifier 拿不到 $\\tau$ ，算不出$\\tau * q(\\tau)$ 的commit $[\\tau * q(\\tau)]$，通过bilinear maping 的形式实现了$[\\tau * q(\\tau)]$，且满足binding 特性。"},"author":{"user":"https://learnblockchain.cn/people/15677","address":null},"history":"QmZUn3xxsXdyyNXD787BTutvy6zFXYHdi6X45axHhzdrLt","timestamp":1691071489,"version":1}