区块链中的数学 – Kate承诺batch opening
本文介绍了Kate承诺在多点披露验证的情况,当然还有一种就是多个多项式在多个不同点打开验证,相信如果本文理解的话,是可以自己推出来的,不在详述了。
## 写在前面 上一篇介绍了[Kate承诺完整流程](https://learnblockchain.cn/article/2194),以单个承诺打开为例说明,还有一种情况,如果需要在多个点值打开和验证,这时候需要批量打开(披露)【Batch Opening】和验证了. 本文介绍批量验证的两种情况:一个多项式多点验证和多个多项式同一点打开验证 本文在[上一篇](https://learnblockchain.cn/article/2194)基础上推进,所有符号含义均与之相同。 ## 同一多项式多点验证 假定要打开的多个点集合记为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,见证$w_B$ 验证: $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)},w_B) * 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)^{\psi_B(\alpha)\prod_{i \in B}(\alpha \ i)+r(\alpha)}$ $= e(g,g)^{\phi(\alpha)}$ $= e(C, g)$ 其中用到了方法2,变形得到: $φ(x) = \psi_B(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承诺](https://learnblockchain.cn/article/2194) Kate承诺完整流程 [区块链中的数学 - 多项式承诺](https://learnblockchain.cn/article/2165) 多项式知识和承诺 [区块链中的数学 - Pedersen密钥共享](https://learnblockchain.cn/article/2164) Pedersen 密钥分享 [区块链中的数学 - Pedersen承诺](https://learnblockchain.cn/article/2096) 密码学承诺--Pedersen承诺 [区块链中的数学 - 哈希承诺](https://learnblockchain.cn/article/2085) 密码学承诺--hash承诺 [区块链中的数学 - 不经意传输](https://learnblockchain.cn/article/2022) 不经意传输协议 [区块链中的数学- BLS 基石(双线性函数)和配对](https://learnblockchain.cn/article/1963) 双线性映射(配对) [区块链中的数学 - BLS门限签名](https://learnblockchain.cn/article/1962) BLS m of n门限签名 [区块链中的数学 - BLS密钥聚合](https://learnblockchain.cn/article/1912) BLS密钥聚合 [区块链中的数学 - BLS数字签名](https://learnblockchain.cn/article/1905) BLS签名及验证 [区块链中的数学 - Feldman的可验证的密钥分享](https://learnblockchain.cn/article/1789) Feldman可验证密钥分享方案 [区块链中的数学 - Ed25519签名](https://learnblockchain.cn/article/1663) Ed25519签名 [Schorr签名与椭圆曲线](https://learnblockchain.cn/article/2450) Schorr签名与椭圆曲线 [区块链中的数学-Uniwap自动化做市商核心算法解析](https://learnblockchain.cn/article/1494) Uniwap核心算法解析(中)
写在前面
上一篇介绍了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
- 阅读 ( 878 )
- 学分 ( 3 )
- 分类:入门/理论
评论