多项式承诺

一、密码学中的承诺

承诺（Commitment）是密码学中的一种基础原语，它为安全协议提供了先锁后公开的机制。参与者可以先生成一个承诺，把自己的选择锁定并公开承诺值，但不泄露具体内容；在需要时再揭示原始值，供他人验证其确实与当初的承诺一致。一个安全的承诺方案既要保证隐藏性（承诺前的内容在揭示前无法被推测），又要保证绑定性（承诺一旦生成就无法事后修改）。承诺是零知识证明、安全多方计算、电子投票、区块链等密码协议的核心基础组件。

1.1 什么是承诺

密码学承诺方案是一个涉及承诺方和验证方的二段式交互协议，该协议共分为三个步骤：

第一阶段为承诺阶段，此阶段承诺方通过 $C \leftarrow Com(x)$ 计算声明x的承诺C并发送给验证方。
第二阶段为打开承诺阶段，此阶段中、承诺方会发送 “承诺C所对应的声明x的证明 $\pi$ ” 给验证方，该证明也可以称为 “打开承诺”。此步骤是承诺方想揭示承诺的值给验证方。
第三阶段为打开承诺验证阶段，此阶段验证方验证证明 $\pi$ 的合法性。如果 $\pi$ 合法，则认为承诺C 确实是声明x对应的承诺。

承诺方案需要满足的三个基本性质：

正确性：按照上述三个过程生成的承诺和打开承诺一定能通过成员验证。
绑定性(Binding)：对于任意PPT敌手，找到两个声明 $x_1 \neq x_2$ ,使得 $C_1=C_2$ 的概率可以忽略。即在有限的计算能力和时间之内，难以找到两个不同的声明，使得其对应的承诺相同。
隐藏性(Hiding):对于任意PPT敌手，声明 $x_1$ 和声明 $x_2$ 的承诺 $C_1,C_2$ 不可区分。该性质保证承诺 C 不泄露声明的额外信息，使得敌手不能从承诺中获得任何声明的信息。

1.2. 承诺有什么用

在生活中经常需要用到承诺，比如：

Alice和Bob想要玩一个猜数字游戏，游戏规则如下：
- Alice从集合A={0,1}中随机选择 $a\in_R\{x_0,x_1\}$ ，然后Bob输出对a的猜测b，如果b=a，则Bob获胜，否则Alice获胜。
- 在这个游戏当中，如果没有任何限制，那么即使Bob猜出了正确的a，Alice也可以声称Bob猜错了，从而保证自己总是赢得游戏。如：Alice选择 $a=x_1$ ，Bob在游戏中猜测 $b=x_1$ ，此时本应Bob获得游戏胜利，但是Alice可以告诉Bob自己选择的 $a=x_0$ ，从而赢得游戏。导致上述结果的原因是Alice可以随意更改a的值，我们可以使用承诺解决上述问题。
- 我们更改游戏规则为：Alice首先选择 $a \in_R \{x_0,x_1\}$ 并计算承诺 $C=Com(a)$ 并将其发送给Bob，Bob输出对a的猜测b。
- 在上述游戏中，假如Alice选择了 $a=x_1$ 并计算了 $C=Com(a)$ 给Bob，此时如果Alice在上述游戏中想通过修改 $a=x_0$ 来获得游戏胜利的方式是不可行的。因为Bob可以计算 $C'=Com(a)$ ，然后通过验证 $C'=C$ 是否相等验证Alice是否修改了声明a。
- 由于承诺的隐藏性，Bob不能从C中获得任何声明a的信息，因此Bob得到C并不会增加游戏获胜的概率。承诺的绑定性则保证 Alice 不能选择两个不同的 $x_0,x_1$ 使得他们的承诺值相等，即 $C=Com(x_0)=Com(x_1)$ ，因此Alice不能作弊。
信息科学中也有类似的承诺技术存在。例如，某些网站在提供下载文件时，也会提供对应文件的单向哈希值。这里，单向哈希值便是一种对文件数据的承诺（承诺阶段）。用户将文件数据下载好之后（打开承诺），检测接收到的文件数据是否有丢失或变化，如果校验通过，相当于网站兑现了关于文件数据完整性的承诺（打开承诺验证）。
Sigma协议(零知识证明中的使用) 承诺在非交互式零知识证明中发挥着关键性作用，可以保证没有秘密的敌手无法伪造合法的证明。比如在Schnoor协议中，Alice想要向Bob证明自己拥有一个公钥 $PK=sk\cdot G$ 对应的私钥 $sk$ 而不暴露 $sk$ 的其他信息就用到了承诺。(具体参见附录1)
秘密共享中的承诺在一个(t,n)秘密共享中，一个dealer(秘密分发者)给n个participator(参与者)分发秘密s的share(秘密份额) $s_i$ 。传统的秘密共享中、dealer知晓完整的密钥s，有作恶的可能。例如对部分 $P_i$ 发放错误的share。参与者 $P_i$ 也可能提供非真实的share去扰乱正常的reconstruct(秘密重构)过程。使用多项式承诺则可以避免上述问题。（参见Feldman承诺）
zk-SNARK中的承诺听说在zk-SNARK中，多项式承诺扮演着重要角色，不过我没看过这个。。

1.3. 常见的承诺

关于承诺，有非常多种类，这里简单列举几个常见的承诺方式。

哈希承诺

承诺阶段对于一个声明 $x$ ，承诺者计算 $C=H(x)$ 作为承诺发给验证者

承诺打开承诺者将声明x发送给验证者

打开承诺验证验证者计算 $C'=H(x)$ ，然后判断等式 $C'=C$ 是否成立，如果成立，则验证者认为承诺 $C$ 对应的声明确实是 $x$

基于加密算法的承诺

承诺阶段对于一个声明 $x$ ，承诺者计算 $C=E_K(x)$ 作为承诺发给验证者

承诺打开承诺者将声明x发送给验证者

打开承诺验证验证者计算 $C'=E_K(x)$ ，然后判断等式 $C'=C$ 是否成立，如果成立，则验证者认为承诺 $C$ 对应的声明确实是 $x$

Pederson承诺

公共参数：选择乘法群 $G=Z_q^*$ ,生成元为 $g,h$ ,公开三元组 $(g,h,q)$

承诺阶段对于一个声明 $x$ ，承诺者选择一个随机数 $r\in_RZ_q$ 计算 $C=g^xh^r\ mod\ q$ 作为承诺发给验证者

承诺打开承诺者将声明 $x$ 和随机数 $r$ 发送给验证者

打开承诺验证验证者计算 $C'=g^xh^r\ mod\ q$ ，然后判断等式 $C'=C$ 是否成立，如果成立，则验证者认为承诺 $C$ 对应的声明确实是 $x$

上述承诺满足正确性、隐藏性和绑定性，这些性质的证明可以在晚上很容易找到。这里不在给出。

二、KZG多项式承诺

多项式承诺 $C$ 的承诺对象是一个多项式 $f(x)$ 。验证者如果对打开承诺的验证通过了，则说明承诺者确实知道声明 $f(x)$ 。 KZG 多项式承诺也被称为卡特多项式承诺,由Kate，Zaverucha和Goldberg在2010年提出 $^{[1]}$ 。KZG多项式承诺的承诺值是椭圆曲线上的一个点，且打开承诺只需要发送一个固定大小的椭圆曲线上的点，而不必将整个多项式发送给验证者。

2.2 KZG预备知识

为了学习KGZ承诺需要一些必备的预备知识。列举如下：

椭圆曲线相关知识
双线性映射相关知识
因式定理 $^{[2]}$ ，代数基本定理
拉格朗日插值公式参考视频: KZG的数学原理

2.3 KZG单点承诺

KZG多项式承诺分为多个阶段，这里首先对承诺的全过程进行综述，然后再解释为什么要这么做。

可信设置阶段：生成一个随机数 $\alpha$ ，然后计算 $PK=(P,\alpha P,\alpha^2P,...,\alpha^nP)$ 作为公钥发布。随后将 $\alpha$ 永久销毁。假设承诺者想要对多项式 $f(x)=a_0+a_1x+...+a_nx^n$ 进行承诺：

承诺阶段：
假设 $PK=(P,\alpha P,\alpha^2P,...,\alpha^nP)=(pk_0,pk_1,pk_2,...,pk_n)$ ，承诺者首先计算 $^{(1)}$ 承诺
$C=f(\alpha)P=a_0pk_0+a_1pk_1+...+a_npk_n$
并将其发送给验证者。(容易看出，承诺 $C$ 是椭圆曲线上的一个点)
打开承诺：
承诺者为了打开承诺，首先计算 $q(x)=\frac{f(x)-f(i)}{x-i}=b_0+b_1x+b_2x^2+...+b_nx^n$ ，然后计算 " $f(x)$ 在 $i$ 点取值为 $f(i)$ "的证明为
$\pi=q(\alpha)P=b_0pk_0+b_1pk_1+b_2pk_2+...+b_npk_n$
最后将打开承诺 $(i,y=f(i),\pi)$ 发送给验证者。
打开承诺验证：
验证者判断等式 $e(C,P)=e(\pi,pk_1-iP)e(P,P)^{f(i)}$ 是否成立，成立则接受承诺者的打开承诺 $C$ 。即相信承诺者确实知道承诺 $C$ 对应的多项式 $f(x)$ ，且 $f(x)$ 在 $i$ 处的取值为 $y=f(i)$ 。
说明：
传统的打开承诺是直接将多项式 $f(x)$ 的系数 $\{a_0,...a_n\}$ 发送给验证者，然后验证者重新计算 $C'=f(\alpha)P=a_0pk_0+a_1pk_1+a_2pk_2+...+a_npk_n$ 并比较等式 $C'=C$ 是否成立，如果成立则打开承诺验证成功。这种方式的缺点是打开承诺需要暴露多项式 $f(x)$ ，并且打开承诺需要将多项式的所有系数发送给验证者，导致通信开销与多项式的次数成正比。

2.4 KZG多点承诺

上面的介绍说明了如何证明一个多项式在某点 $i$ 的取值为 $f(i)$ ，它意味着你可以仅靠发送单个的群元素（可以是48字节大小，例如BLS12381)来证明任何次数的多项式在任意点的取值。下面我们讨论如何仅使用一个元素证明一个多项式在任意多个点处的取值。（可信设置阶段和上述单点承诺一样，不再赘述）

承诺阶段：
假设 $PK=(P,\alpha P,\alpha^2P,...,\alpha^nP)=(pk_0,pk_1,pk_2,...,pk_n)$ ，承诺者首先计算承诺 $C=f(\alpha)P=a_0pk_0+a_1pk_1+a_2pk_2+...+a_npk_n$ 并将其发送给验证者。
打开承诺：
假设承诺者想要证明自己知道多项式 $f(x)$ ，其中 $f(x)$ 在横坐标集合 $\{z_0,...,z_{k-1}\}$ 处的函数值分别为 $\{f(z_0),...,f(z_{k-1})\}$ ，他首先使用拉格朗日插值法计算过这 k 个点的多项式:
$I(x)=\sum_{i=0}^{k-1}f(z_i)\prod_{j=0,j\neq i}^{k-1} \frac{x-z_j}{z_i-z_j}$
承诺者计算零多项式 $Z(x)=(x-z_0)\cdot\cdot\cdot(x-z_{k-1})$ 并据此计算
$q(x)=\frac{f(x)-I(x)}{Z(x)}=c_0+c_1\cdot x+c_2\cdot x^2+...+c_n\cdot x^n$
然后承诺者计算 “ $f(x)$ 在k个点 $\{z_i\}$ 处的取值分别为 $\{f(z_0)\}$ ” 的证明
$\pi=q(\alpha)P=c_0\cdot pk_0+c_1\cdot pk_1+c_2\cdot pk_2+...+c_n\cdot pk_n$
并将打开承诺 $((z_i,f(z_i))_{i=0}^{k-1},\pi)$ 发送给验证者。
打开承诺验证验证者首先计算插值多项式 $I(x)$ 和零多项式 $Z(x)$ ，然后使用公钥 $PK$ 计算出 $Z(\alpha),I(\alpha)$ ，并判断等式
$e(C,P)=e(\pi,Z(\alpha)P)e(P,P)^{I(\alpha)}$
是否成立，如果成立，则接受承诺者的打开承诺 $C$ 。也就是相信承诺者确实知道承诺 $C$ 对应的多项式 $f(x)$ ，且 $f(x)$ 在k个点 $\{z_i\}$ 处的取值确实分别为 $\{f(z_0)\}$ 。

2.5 KZG承诺的解释

KZG单点承诺
KZG单点承诺的打开承诺实际上是"承诺者想向验证者证明其知道承诺 $C$ 对应的多项式 $f(x)$ "，为了不暴露 $f(x)$ 本身，承诺者证明 “自己知道 $f(x)$ 在横坐标 $i$ 处的取值 $y=f(i)$ ”。
1. 令 $g(x)=f(x)-f(i)$ ，则上述证明等价于证明 $g(x)$ 存在零点 $i$ ；
2. 由因式定理知， $g(x)$ 可分解为 $g(x)=(x-i)q(x)$ ，即 $q(x)=\frac{f(x)-f(i)}{x-i}$ ,显然，只有承诺者知道 $f(x)$ ，故只有他能计算出 $q(x)$ .
3. 承诺者计算横坐标 $i$ 处的打开承诺 $\pi=q(\alpha)$ P，并将其发送给验证者。
4. 根据等式 $q(x)=\frac{f(x)-f(i)}{x-i}$ 可得 $f(\alpha)=(\alpha-i)q(\alpha)+f(i)$ ，因此验证者可以通过检查等式 $e(f(\alpha)P,P)=e(((\alpha-i)q(\alpha)+f(i))P,P)$ 是否成立来决定是否接受打开承诺，即检查等式 $e(C,P)=e(\pi,(pk_1-iP)e(P,P))^{f(i)}$ 是否成立，成立则打开承诺验证通过。
KZG多点承诺
在KZG多点承诺中，承诺方想要向验证者证明自己知道 “ $f(x)$ 在k个点 $\{z_i\}$ 处的取值确实分别为 $\{f(z_i)\}$ ”，其中 $i = 1,2...,k-1$ 。这里的证明思路实际上上面的单点证明相同。
1. 首先使用拉格朗日插值公式计算出过k个点 $\{(z_i,f(z_i)\}$ 的插值多项式 $I(x)$ 【这意味着 $I(z_i)=f(z_i)$ 】。令 $g(x)=f(x)-I(x)$ ，则上述证明等价于证明 $g(x)$ 存在零点 $\{(z_i)_{i=0}^{k-1}\}$
2. 由因式定理知， $g(x)$ 可分解为
  $g(x)=q(x)\prod_{i=0}^{k-1}(x-i)$
  令 $Z(x)=\prod_{i=0}^{k-1}(x-i)$ ，则有 $q(x)=\frac{f(x)-I(x)}{Z(x)}$ ,故只有知道 $f(x)$ 的承诺者能计算 $q(x)$ .
3. 承诺者计算横坐标 $i$ 处的打开承诺 $\pi=q(\alpha)P$ ，并将其发送给验证者。
4. 后面的验证同理。
承诺的安全性
使用承诺 $C=f(\alpha)P$ 作为多项式 $f(x)$ 的承诺是安全的。
1. 假设敌手可以寻找一个多项式 $f'(x)\neq f(x)$ 使得 $f'(\alpha)P=C$ ，
2. 那么 $(f'(\alpha)-f(\alpha))P=0$ ，即函数 $r(x)=f'(x)-f(x)$ 存在零点 $\alpha$ 。
3. 由于敌手不知道 $\alpha$ 的值，因此它只能令多项式 $r(x)$ 有尽可能多的零点，从而使得 $r(x)$ 有更大的几率存在零点 $\alpha$ 。
4. 由代数基本定理可知，在实数域上的非零n次多项式至多只有n个零点。而 $f'(x)\neq f(x)$ ，故 $r(x)\neq 0$ 。所以 $r(x)$ 最多有n个零点。假设椭圆曲线群 $G$ 的阶为 $p=2^{128}$ ，那么攻击者求出满足条件的 $f'(x)$ 的概率为 $n/p=n/2^{128}$ 。这是一个可以忽略的概率，在现实中，可以认为攻击者不可能找到这个 $f'(x)$ 。
矢量承诺
尽管卡特承诺被设计成多项式承诺，但它作为矢量承诺来使用也大有用处。回忆一下，一个矢量承诺是针对矢量 $a_0,...,a_{n-1}$ 的承诺，并且允许你证明任意位置i对应 $a_i$ 。我们可以使用卡特承诺的方案来重现这一场景：使p(X)为对所有的计算 $p(i)=a_i$ 的一个多项式，我们知道这样一个多项式存在，并且可以通过拉格朗日插值来计算它：
$p(x)=\sum_{i=0}^{k-1}a_i\prod_{j=0,j\neq i}^{k-1} \frac{x-j}{i-j}$
使用这个多项式，我们可以就可以利用一个单一群元素来证明这个矢量中任意数量的元素！注意到比起默克尔树(在证明大小方面)这个方案更加高效：仅证明一个元素，默克尔证明就需要花费 log n 大小的哈希！

三、Feldman承诺

Feldman 承诺是由 Paul Feldman 在 1987 年提出的公开可验证秘密分享方案中的一部分。它通过在有限域上选择生成元 $g$ 并计算承诺值 $C = g^s$ 来实现承诺。验证者只需检查 $g^s$ 是否与承诺值匹配即可验证打开结果，具有计算绑定性和完美隐藏性。

3.1 Feldman承诺的过程

承诺阶段:
对于一个多项式 $f(x)=a_0+a_1x+a_2x^2+...+a_{k-1}x^{k-1}$ ，承诺者计算承诺 $C=(c_0,c_1,...,c_{k-1})=(g^{a_0},g^{a_1},...,g^{a_{k-1}})$ 并将其发送给验证者。
打开承诺:
假设承诺者想要证明自己知道多项式 $f(x)$ 在横坐标集合 $Z=\{z_0,z_1,...,z_{k-1}\}$ 处的函数值 $f(z)=\{f(z_0),f(z_1),...,f(z_{k-1})\}$ ，他可以直接将 $f(z)$ 发送给验证者。
打开承诺验证:
对于集合 $Z$ 任意一点 $z_i$ ，验证者验证
$g^{f(z_i)}=\prod_{j=0}^{k-1}(c_j)^{{z_i}^j} \bmod p$
是否成立，若成立，则接受承诺者的打开承诺 $C$ 。也就是相信承诺者确实知道承诺 $C$ 对应的多项式 $f(x)$ ，且 $f(x)$ 在k个点 $\{z_0,...,z_{k-1}\}$ 处的取值确实分别为 $\{f(z_0),...,f(z_{k-1})\}$ 。

3.2 基于Feldman承诺的VSS

在普通的Shamir(t,n)秘密共享之中，存在以下问题：

密钥分发者知晓完整的密钥，有作恶的可能，例如对部分秘密持有者发放错误的分片数据。
密钥分片的持有者可能提供非真实的分片数据

当考虑存在不诚实参与方时，对于一个秘密需要有相应的算法来验证其确实是秘密的有效份额，否则不存在秘密可言。本文将介绍基于Shamir密钥分享的改进机制：可验证的秘密共享（verifiable secret sharing, VSS）。关于VSS的方案有很多，这里直接介绍比较实用的Feldman VSS方案。【注：VSS概念由Benny Chor, Shafi Goldwasser, Silvio Micali等人在1985年首次提出】

Feldman方案：

实际工程中使用的密钥分享以有限域上、生成元为g的循环群为基础构造。为了使得分发的秘密碎片的数据可验证，秘密分发者除了给出秘密的分片数据外，还要提供对应的系数承诺(c0,c1,…)。

符号约定：
设 p 是一个大素数，q 为 p -1 的一个大素数因子，g 属于 $Z_p^*$ 且为 q 阶元素,(p, q, g) 是公幵可知的，n 是参与者的数目，s 为要共享的密钥，k 是门限值。
秘密份额分发：
- 选定多项式： $a(x)=a_0+a_1x+a_2x^2+...+a_{k-1}x^{k-1}$ ，其中 $a_0$ 代表秘密，
- 计算承诺（commitment）： $c_0=g^{a_0},c_1=g^{a_1},...,c_{k-1}=g^{a_{k-1}}$ 以上运算是在mod p基础上的。
- 将承诺 $c_i$ 和 $s_i$ 一同发送给参与者 $P_i$ 。【具体工程实现中，由于承诺对所以参与者都是一样的，也可先广播承诺给所有参与者，然后单独秘密发送分片，以减少消息传输量】。
秘密份额验证：
当第i个参与者收到数据碎片 $s_i$ 时，作如下验证：
$g^{s_i}=\prod_{j=0}^{k-1}(c_j)^{i^j} \bmod p \ \ (\text{其中}i=1,2,...,n)$
由于承诺绑定了系数，如果分发者给出承诺不是用多项式方程真实系数，会导致验证失败。

5. 参考文献：

[1]. Constant-size commitments to polynomials and their applications

[2]. 因式定理：设f(x)为一多项式，则x-a为f(x)的因式"等价于f(a)=0。 [3]. 代数基本定理：代数基本定理说明，任何复系数一元n次多项式方程在复数域上至少有一根。由此推出，n次复系数多项式方程在复数域内有且只有n个根（重根按重数计算）。

附录1

Schnoor协议的具体内容如下：

对上图进行解释如下：