多项式承诺通过 Pedersen 承诺实现

  • RareSkills
  • 发布于 2024-08-28 19:46
  • 阅读 234

本文详细介绍了多项式承诺机制的原理和实现,特别是如何使用Pedersen承诺和椭圆曲线来验证多项式在特定点的估值,而不泄露多项式本身。文章还讨论了验证步骤的工作原理和为什么验证者无法被欺骗。

一个多项式承诺是一种机制,证明者可以通过它说服验证者多项式 p(x) 在点 x 的评估 y=p(x),而不披露任何关于 p(x) 的信息。过程如下:

  1. 证明者向验证者发送一个承诺 C,"锁定"他们的多项式。
  2. 验证者回复一个他们希望对多项式进行评估的值 u。
  3. 证明者回复 y 和 π,其中 y 是 p(u) 的评估,而 π 是评估正确的证明。
  4. 验证者检查 C, u, y, π 并接受或拒绝该多项式的评估是否有效。

此承诺方案不需要可信设置。然而,通信开销为 O(n),因为证明者必须对其多项式中的每个系数发送一个承诺。

对多项式进行承诺

证明者可以通过为每个系数创建一个 Pedersen Commitment 来对多项式进行承诺。对于 Pedersen Commitment,证明者和验证者需要就两个具有未知离散对数的椭圆曲线点达成一致。我们将使用 G 和 B。

例如,如果我们有一个多项式

$$p(x) = c_0+c_1x+c_2x^2$$

我们可以为每个系数创建一个 Pedersen commitment。我们将需要三个混淆项 γ0, γ1, γ2。为了方便,任何用于混淆的标量将使用小写希腊字母。我们始终使用椭圆曲线点 B 作为混淆项。我们的承诺的生成方式如下: $$ \begin{align} C_0=c_0G+\gamma_0B \ C_1=c_1G+\gamma_1B \ C_2=c_2G+\gamma_2B \ \end{align} $$

证明者将元组 (C0, C1, C2) 发送给验证者。

验证者选择 u

验证者选择他们的 x 值并将其发送给证明者。我们称该值为 u。

证明者计算证明

证明者评估多项式

证明者计算原始多项式为:

$$ y = p(u) = c_0 + c_1u + c_2u^2 $$

证明者评估混淆项

评估正确的证明由以下多项式给出,该多项式使用混淆项乘以 u 的相应幂。原因将在后面解释。

$$ \pi = \gamma_0 + \gamma_1u+\gamma_2u^2 $$

证明者将 (y, π) 发送给验证者。请注意,证明者仅发送域元素(标量),而不是椭圆曲线点。

验证步骤

验证者进行以下检查:

$$ C_0+C_1u+C_2u^2\stackrel{?}{=}yG+\pi B $$

为什么验证步骤有效

如果我们将椭圆曲线点扩展到其底层值,我们看到这个方程是平衡的:

$$ \begin{align} C_0 + C_1u + C_2u^2 &= yG + \pi B \ (c_0G + \gamma_0B) + (c_1G + \gamma_1B)u + (c_2G + \gamma_2B)u^2 &= (c_0 + c_1u + c_2u^2)G + (\gamma_0 + \gamma_1u + \gamma_2u^2)B \ c_0G + \gamma_0B + c_1Gu + \gamma_1Bu + c_2Gu^2 + \gamma_2Bu^2 &= (c_0 + c_1u + c_2u^2)G + (\gamma_0 + \gamma_1u + \gamma_2u^2)B \ c_0G + c_1Gu + c_2Gu^2 + \gamma_0B + \gamma_1Bu + \gamma_2Bu^2 &= (c_0 + c_1u + c_2u^2)G + (\gamma_0 + \gamma_1u + \gamma_2u^2)B \ (c_0 + c_1u + c_2u^2)G + (\gamma_0 + \gamma_1u + \gamma_2u^2)B &= (c_0 + c_1u + c_2u^2)G + (\gamma_0 + \gamma_1u + \gamma_2u^2)B \ \end{align} $$

在某种意义上,证明者使用多项式的系数和他们选择的 u 评估多项式。这将产生原始多项式的评估以及多项式的混淆项。

正确评估的证明是,证明者可以将混淆项与多项式评估分开——即使证明者不知道 yG 和 πB 的离散对数。

证明有效性的替代说明

回顾一下 p(x)=c0+c1x+c2x^2。因此,对系数的承诺计算如下:

$$ \begin{matrix} &\space\space\space c_0G&\space\space\space c_1G&\space\space\space c_2G\ &+\gamma_0B&+\gamma_1B&+\gamma_2B\ &\vcenter{\hbox{|}} \vcenter{\hbox{|}}&\vcenter{\hbox{|}} \vcenter{\hbox{...

剩余50%的内容订阅专栏后可查看

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
RareSkills
RareSkills
https://www.rareskills.io/