区块链中的数学（六十七）--多项式承诺

写在前面

上一篇介绍了Pedersen 密钥分享，本文继续讲密码学承诺中重要的成员--多项式承诺诺！

多项式承诺诺在零知识证明中应用比较广泛，且有多种形式。本文介绍Kate版本的多项式承诺。

首先我们需要知道什么是多项式？这个比较简单，以单变量多项式为例说明：

以上是系数表示形式，系数序列确定多项式也就确定了。

还有一种表示方法是使用n+1点值对表示n次多项式。

同样，这种方法也能唯一确定多项式。

两种表示方法，各有其应用场景，比如系数表示法在计算多项式相加的场合效率高，而点值表示法则应用在多项式相乘计算场合。

由于两种表示法本质是同一个东西，所以二者可以相互转化，其中FFT就是实现系数表达到点值表示的转换方法，而IFFT正好相反。关于FFT和IFFT深入解读超出本文范围，可自行查阅。

多项式承诺有多种方式，比如最直接的就是把多项式系数承诺出去，这样多项式在承诺后就不能再改变了。这种方式在系数较少即多项式度数较低时适用。

当系数比较多（比如超过10万）承诺结果就会比较大，增加存储与传输的代价。

能不能用点值方式做承诺呢？最好适用一个点的值，因为点值用的多了同样也会有上述问题。

一个原始的点值承诺方法浮出水面：

这种原始承诺方式有问题吗？仔细想想容易发现有以下问题：

在r处取值为c的多项式存在多个，比如f(r) = c,g(r) = c ,那么承诺方就可以在承诺时候使用多项式f(x),而在打开验证阶段使用g(x)也能通过验证，这样就达不到承诺的目的了。

这种把多项式和盘托出的打开方式成为 全部打开 ，还有一种 部分打开 的方式：

承诺生成（Commit）阶段：

承诺方选择一个暂不公开的多项式，在某一点r处，计算出对应的承诺c并公开。c = f(r), 将（r，c）公开给验证方
挑战（challenge）与证明生成：

验证方V随机选择一个数z,发给承诺方P, P计算在z处值s = f(z)，同时计算出t(x) = f(x)-s / (x-z),计算t(x)在z处的值w = t(z)(w也称为见证witness)

返回给验证方V(s,w)
验证阶段：

验证方验证：s = f(z) --> f(z) - s = 0 --> 方程f(x)-s = 0 有根x=z, 即存在t(x) 使得f(x) - s = t(x)(x - z), 这个方程是恒等式，所以任意点都成立。

在r处自然也是成立的，所以可以检验f(r) - s = t(r)(r - z) = c - s = w(r - z )

通过则验证成功，否则失败。

流程图如下：

这种方法采用部分打开方式验证，使得多项式增加了隐私性，自始至终没有完全暴露最初的多项式。现在已经比较接近Kate承诺的方案了！

目前为止的方案中，承诺方造假的问题依然存在，仔细研究会发现 问题关键在于承诺方P知道计算的输入变量r，z , 这样就有机会构造出新的多项式在r,z处取特定的值。如果P不知道r，z,就不能这样作弊了。于是Kate承诺选择在密文空间中进行计算。

好了，下一篇继续Kate承诺的余下部分！

欢迎关注&在看，疑问请留言！