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

blocksight
更新于 2021-03-11 13:28
阅读 4325

本文介绍了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点值聚合也需要添加相同因子。

## 小结

好了，下一篇继续当前区块链中用到最多的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点值聚合也需要添加相同因子。