区块链中的数学(六十七)–多项式承诺

写在前面

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

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

何为多项式

多项式

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

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

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

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

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

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

多项式承诺

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

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

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

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

点值承诺

  1. 承诺生成(Commit)阶段:

    承诺方选择一个暂不公开的多项式,在某一点r处,计算出对应的承诺c并公开。c = f(r), 将(r,c)公开给验证方

  2. 承诺披露(Reveal)阶段:

    承诺方公布多项式,验证方根据多项式计算r处值c’ = f(r),比较c’= c,一致则表示验证成功,否则失败。

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

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

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

  1. 承诺生成(Commit)阶段:

    承诺方选择一个暂不公开的多项式,在某一点r处,计算出对应的承诺c并公开。c = f(r), 将(r,c)公开给验证方

  2. 挑战(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)

  3. 验证阶段:

    验证方验证: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承诺的余下部分!

欢迎关注&在看, 疑问请留言!

blocksight
我还没有学会写个人说明!
上一篇

吉娜·卡拉诺称遭到迪士尼和卢卡斯影业“欺凌”

下一篇

[视频]英特尔Rocket Lake评测套装开箱:配微星Z590主板和水冷散热器

你也可能喜欢

评论已经被关闭。

插入图片