区块链中的数学（六十七）–多项式承诺
写在前面
上一篇介绍了Pedersen 密钥分享， 本文继续讲密码学承诺中重要的成员–多项式承诺诺！
多项式承诺诺在零知识证明中应用比较广泛，且有多种形式。本文介绍Kate版本的多项式承诺。
何为多项式
多项式
首先我们需要知道什么是多项式？这个比较简单，以单变量多项式为例说明：
以上是系数表示形式，系数序列确定多项式也就确定了。
还有一种表示方法是使用n+1点值对表示n次多项式。
同样，这种方法也能唯一确定多项式。
两种表示方法，各有其应用场景，比如系数表示法在计算多项式相加的场合效率高，而点值表示法则应用在多项式相乘计算场合。
由于两种表示法本质是同一个东西，所以二者可以相互转化，其中FFT就是实现系数表达到点值表示的转换方法，而IFFT正好相反。关于FFT和IFFT深入解读超出本文范围，可自行查阅。
多项式承诺
多项式承诺有多种方式，比如最直接的就是把多项式系数承诺出去，这样多项式在承诺后就不能再改变了。 这种方式在系数较少即多项式度数较低时适用。
当系数比较多（比如超过10万）承诺结果就会比较大，增加存储与传输的代价。
能不能用点值方式做承诺呢？最好适用一个点的值，因为点值用的多了同样也会有上述问题。
一个原始的点值承诺方法浮出水面：
点值承诺
-
承诺生成（Commit）阶段：
承诺方选择一个暂不公开的多项式，在某一点r处，计算出对应的承诺c并公开。c = f(r), 将（r，c）公开给验证方
-
承诺披露（Reveal）阶段：
承诺方公布多项式，验证方根据多项式计算r处值c’ = f(r)，比较c’= c，一致则表示验证成功，否则失败。
这种原始承诺方式有问题吗？仔细想想容易发现有以下问题：
在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承诺的余下部分！
欢迎关注&在看， 疑问请留言！
About The Author
