区块链中的数学 - Kate承诺batch opening

本文介绍了Kate承诺在多点披露验证的情况,当然还有一种就是多个多项式在多个不同点打开验证,相信如果本文理解的话,是可以自己推出来的,不在详述了。

写在前面

上一篇介绍了Kate承诺完整流程,以单个承诺打开为例说明,还有一种情况,如果需要在多个点值打开和验证,这时候需要批量打开(披露)【Batch Opening】和验证了.

本文介绍批量验证的两种情况:一个多项式多点验证和多个多项式同一点打开验证 本文在上一篇基础上推进,所有符号含义均与之相同。

同一多项式多点验证

假定要打开的多个点集合记为B,不采用每个点依次验证,批量需要实现:

1. CreateRemainderPoly

计算商余项多项式: $r(x) = \phi(x)/ \prod_{i\in B}(x-i)$

2.CreateWitnessBatch

令$\psi B(x)= \frac{\phi(x)r(x)}{\prod{i \in B}(x\ i)}$, 计算$w_B=g^{ψ_B(α)}$, $(B,r(x),w_B)$是点集合B多项式的值的见证

可得,$\phi(x) = ψB(x)\prod{i \in B}(x \ i)+r(x)$

对于 i ∈ B, φ(i) = r(i).

3.VerifyEvalBatch

输入:检查点集合B,r(x), 多项式承诺C,见证$wB$ 验证: $e(C, g) = e(g^{\prod{i \in B}(\alpha - i)},w_B) * e(g,g)^{r(\alpha)}$ 等式成立,则多项式承诺为真。

推导过程: $e(g^{\prod_{i \in B}(\alpha - i)},wB) * e(g,g)^{r(\alpha)}$ $=e(g^{\prod{i \in B}(\alpha - i)},g^{\psi _B(\alpha )}) * e(g,g)^{r(\alpha)}$ $=e(g,g)^{\psiB(\alpha)\prod{i \in B}(\alpha \ i)+r(\alpha)}$ $= e(g,g)^{\phi(\alpha)}$ $= e(C, g)$

其中用到了方法2,变形得到: $φ(x) = \psiB(x)\prod{i \in B}(x \ i)+r(x)$

多个多项式同点验证

假设有t个不同的多项式,$φ_1,φ2,...,φ{t'}$, 在同一个点z处打开验证,可直接使用单点承诺打开验证聚合。

2.CreateWitnessBatch

令$h(x)=\sum _{i=1}^t(φ_i(x)-φ_i(z))/(x-z)$

输出$w=g^{h(α)}$

3.VerifyEvalBatch

输入:检查点z, 多项式承诺C,见证w 注意这里 $C =\sum_{i=1}^tcm( φi(x))$ 即t个多项式承诺和 $V = \sum{i=1}^tφ_i(z)$ 验证: $e(C, g) = e(g^{\alpha}/g^z,w)*e(g,g)^V$ 等式成立,则多个多项式z处值为真。

原理如下: $e(g^{\alpha}/g^z,w)e(g,g)^V$ $=e(g^{\alpha -z},w)e(g,g)^{\sum_{i=1}^tφi(z)}$ $=e(g,g)^{\sum{i=1}^tφ_i(\alpha)-φi(z)+\sum{i=1}^tφi(z)}$ $=e(g,g)^{\sum{i=1}^tφ_i(\alpha)}$ $=e(C, g)$ 实际实现中,多项式承诺之和计算过程,可以加上随机系数因子,来提高安全性,相应地,z点值聚合也需要添加相同因子。

小结

本文介绍了Kate承诺在多点披露验证的情况,当然还有一种就是多个多项式在多个不同点打开验证,相信如果本文理解的话,是可以自己推出来的,不在详述了。

好了,下一篇继续当前区块链中用到最多的merkle tree承诺(证明)!


首发于:https://mp.weixin.qq.com/s/KngWef331IP3Rudwb6351g 欢迎关注公众号:blocksight


相关阅读

区块链中的数学 - Kate承诺 Kate承诺完整流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 发表于 2021-03-11 13:28
  • 阅读 ( 305 )
  • 学分 ( 3 )
  • 分类:入门/理论

0 条评论

请先 登录 后评论
blocksight
blocksight

72 篇文章, 1660 学分