区块链中的数学 - Kate承诺

与上一篇初步方案相比,Kate承诺实现了多项式的隐藏和部分打开验证,实际上方法1生成的结果在zk-snark项目中称为SRS(structure reference string)或者CRS(common reference string),是承诺方P和验证方V所共有,实际选择曲线配对不是对称的,而是非对称两个群,以后说到具体的项目代码可以看得比较清楚。

写在前面

上一篇介绍了多项式知识和承诺, 本文继续讲述完整的Kate承诺。

Kate承诺

Kate承诺是Kate,Zaverucha,Goldberg等人在2010年提出的多项式承诺方案。 该方案包含以下六个方法:

1. Setup

选择适当的椭圆曲线,选择对称双线性映射的子群,生成元G, 配对函数$e: G * G = G_T$, 随机选择秘密 $\alpha$(作用类似于私钥)。 假设目标多项式最大的度是t, 产生t+1 个元组${g,g^{\alpha},g^{{\alpha}^2},...,g^{{\alpha}^t}}$,该元组公开(作用类似于公钥),并销毁(或者遗忘)$\alpha$值。

2. Commit

令要承诺的多项式是$φ(x)= \sum^d_{j=0} ajx^j$,其中d是φ(x)的度且小于等于t,计算承诺$C = \prod^d{j=0}(g^{\alpha^j})$,注意区分$\alpha$与系数a的表示区别.

3. Open(Reveal)

输出初始原始多项式φ(x)

4.VerifyPoly

根据已知承诺C,和多项式φ(x),验证承诺,直接代入方法2中即可验证。

5.CreateWitness

给定特定多项式输入i,计算i处多项式的值,令$ψ_i(x)=\frac{φ(x)\ φ(i)}{x\ i}$, 计算$w_i=g^{ψ_i(α)},(ψ_i(x),w_i)$是i处多项式的值的见证

6.VerifyEval

输入:i处多项式的值$φ(i)$, 多项式承诺C,见证$w_i$ 验证: $e(C, g) = e(w_i,g^α/g^i)*e(g,g)^{φ(i)}$ 等式成立,则多项式承诺为真。

知其然知其所以然,看看为什么成立? 推导过程: $e(w_i,g^α/g^i)e(g,g)^{φ(i)}$ $=e(g^{ψ_i(\alpha)},g^{\alpha -i}) e(g,g)^{φ(i)}$ $=e(g,g)^{ψ_i(\alpha)(\alpha \ i)+φ(i)}$ $=e(g,g)^{φ(\alpha)}$ $= e(C, g)$

其中用到了方法5,变形得到:$ψ_i(x)(x-i)+φ(i)=φ(x)$

分析比较

方法1是创建了一个密文空间,使得多项式的输入被隐藏,承诺者P在不知道输入的情况下是难以伪造的,这一点在前一篇文章末尾分析过。

方法2在密文空间中计算多项式承诺。

方法3属于完全打开(披露)多项式,供验证者验证,这种方式不具有零知识的性质。

方法4用来检验承诺对应的多项式。

方法5用在部分打开(披露)的场景,在需要零知识性质的场景下,验证者不能知晓完整的多项式信息,取而代之,是随机选择输入挑战i,由承诺者P生成i处的多项式值和见证。

方法5检验在输入i处的部分打开(披露),如果通过,则认可承诺C所表示的多项式在i处求值φ(i)是正确的,

上一篇初步方案相比,Kate承诺实现了多项式的隐藏和部分打开验证,实际上方法1生成的结果在zk-snark项目中称为SRS(structure reference string)或者CRS(common reference string),是承诺方P和验证方V所共有,实际选择曲线配对不是对称的,而是非对称两个群,以后说到具体的项目代码可以看得比较清楚。 通常setup过程采用MPC安全多方计算来保证安全。

小结

Kate承诺方案还有一种变种形式,详细可以参考其paper,本文讲述的是最常用的形式。

多项式承诺的方案不止Kate方案一种,常用的还有基于FRI的承诺方案,以后如果用到再说吧。

本文参考: Polynomial Commitments:http://cacr.uwaterloo.ca/techreports/2010/cacr2010-10.pdf

零知识算法解析3--多项式承诺

好了,有了这些铺垫,下一篇可以继续零知识证明的整体介绍了!


原文链接:https://mp.weixin.qq.com/s/W1Q4VijtEpDIgHX2NiCYrA 欢迎关注公众号:blocksight


相关阅读

区块链中的数学 - 多项式承诺 多项式知识和承诺

区块链中的数学 - Pedersen密钥共享 Pedersen 密钥分享

区块链中的数学 - Pedersen承诺 密码学承诺--Pedersen承诺

区块链中的数学 - 哈希承诺 密码学承诺--hash承诺

区块链中的数学 - 不经意传输 不经意传输协议

区块链中的数学- BLS 基石(双线性函数)和配对 双线性映射(配对)

区块链中的数学 - BLS门限签名 BLS m of n门限签名

区块链中的数学 - BLS密钥聚合 BLS密钥聚合

区块链中的数学 - BLS数字签名 BLS签名及验证

区块链中的数学 - 参与者 < 门限值t的密钥更新Amir Herzberg方案 Amir Herzberg改进方案

区块链中的数学 - Feldman的可验证的密钥分享 Feldman可验证密钥分享方案

区块链中的数学 - Ed25519签名 Ed25519签名

Schorr签名与椭圆曲线 Schorr签名与椭圆曲线

区块链中的数学-Uniwap自动化做市商核心算法解析 Uniwap核心算法解析(中)

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

  • 发表于 2021-02-28 17:58
  • 阅读 ( 342 )
  • 学分 ( 3 )
  • 分类:入门/理论

0 条评论

请先 登录 后评论
blocksight
blocksight

72 篇文章, 1660 学分