承诺机制

承诺机制 Commitment scheme，顾名思义就是一个人一旦做出了承诺，那么这个人就不能随意改变这个承诺。这个想法最初由 Blum 在 [Blum81] 中提出，这篇论文的标题也很有意思叫做：通过电话抛硬币（Coin Flipping by Telephone）。

Blum 在论文中提出这样一个场景：Alice 和 Bob 离婚了，他们决定通过抛硬币来解决车子归谁的问题。约定如果是两个人抛结果相同（都是 HEAD 或者都是 TAIL）那么车子归 Alice；如果两个人抛的结果不相同（一个是 HEAD 一个是 TAIL）那么车子归 Bob。（我知道这很扯，但原文就是这么个设定）。可是现在的问题是，离婚后他们就居住在不同的城市，只能通过电话联系。显然在这个情景中两个人互不信任甚至有作弊的可能。任何一个人先说自己抛硬币的结果都是不利的。怎么去解决这个问题呢？

如何通过电话抛硬币

为了解决通过电话抛硬币问题，我们需要设计一个协议（现实中协议是双方经过协商后同意的双方要遵守的规则，而计算机世界中协议特指那些有交互的双方收发消息应该遵循的规则）。考虑到这个场景中，无法实现同步的通信，也就是说，一定会有一方（我们假设是 Alice）先说出自己抛硬币的结果。Alice 肯定不会同意直接将自己的结果直白地告诉 Bob。为了让 Alice 和 Bob 都接受我们给出的协议方案，显然这个协议应该满足：

1. Alice 发送的信息中隐含她抛硬币的结果，但 Bob 通过这条消息看不出 Alice 抛硬币的结果到底是什么。
2. Alice 发送的信息中隐含的抛硬币的结果不能被 Alice 篡改。也就是说，如果一开始发送的信息中隐含的结果其实是 HEAD，Alice 不能抵赖说自己抛的结果是 TAIL。反之亦然。

如果协议满足上述条件，那么 Alice 发出的这条隐含抛硬币结果的信息实际上可以看作是她对自己抛硬币结果的承诺。等到 Bob 发送他的结果（这个时候 Bob 完全可以直白地告诉 Alice 自己的结果到底是 HEAD 还是 TAIL）后，Alice 就可以打开这个承诺，告诉 Bob 自己的结果。这样一来问题就可以很好的解决了。可以看出来，承诺机制使得即使在没有可信第三方的情况下，最后的结果依然是公平的。

有一个我很喜欢的例子，用保险箱来类比承诺机制。假设 Alice 有保险箱的钥匙。

1. Alice 把自己的要承诺的内容放在保险箱中，上锁后将保险箱交给 Bob。
2. 如有需要，过后 Alice 可以将钥匙交给 Bob，这样 Bob 就可以验证 Alice 的承诺。

保险箱的存在保证了 Bob 无法得知承诺的具体内容，也保证了 Alice 无法篡改自己的真实承诺内容。

承诺机制的定义

从抛硬币和保险箱的两个例子中，我们可以抽象出承诺机制共有的两个性质：

1. 隐藏性（Hiding）：承诺接收方（Reciever）无法得知承诺的具体内容；
2. 绑定性（Binding）：承诺发送方（Sender）无法篡改被承诺的内容。

进一步，我们可以得到承诺机制的形式化表达：

---

（定义：承诺机制） 一个承诺机制定义为算法三元组 $(Gen，Commit，Reveal)$ ：

• $Gen(1^l) \to Commit$ 参数生成算法（Generator）通过系统安全参数 $l$ 得到一个承诺生成算法 $Commit$，该承诺算法定义为 $Commit: \{0, 1\}^l \times \{0, 1\} \to \{0, 1\}^l$，并将该算法公开。

• $Commit(r, m) \to C$：为简便起见，设待承诺的内容仅包含一个比特 $m \in \{0, 1\}$。每当 Sender 要对比特 $m$ 做承诺时，都会从 $\{0, 1\}^l$ 中随机地选一个值 $r$，计算承诺 $C := Commit(r, m)$，并将 $C$ 发送给 Receiver。

• $Reveal(r, m, C) \to \{0, 1\}$：Sender 准备打开承诺时，会给 Receiver 发送 $(r, m)$，这称为承诺 $C$ 的一个打开（open），Receiver 验证 $(r, m, C)$ 是否满足 $C = Commit(r, m)$，若满足则 $Reveal(r, m, C) = 1$ 。

---

按照隐藏性的安全级别和绑定性安全级别的不同，这里的安全级别指的是针对不同计算能力（一般计算能力分为无限的和多项式限制的）的攻击者的攻击依然能提供的安全性，可以将承诺机制分为两类：

Type1：Unconditional binding + Computational hiding

• Unconditional binding： 是指即使 Sender 有无限的计算能力，也不能够事后反悔而篡改它一开始发出的承诺。即无法找到一个承诺 $C$，它既可以被某个 $r$ 打开成关于 0 的承诺，又可以被另外一个 $s$ 打开成关于 1 的承诺。

  $$\forall \ r, s \in \{0, 1\}^l, \ Commit(r, 0) \ne Commit(s, 1)$$

• Computational hiding：是指对于有着多项式限制的计算能力的 Receiver 来说，很难从承诺 $C$ 中得知被承诺内容到底是什么。即在这样的 Receiver 看来，关于 0 的承诺和关于 1 的承诺是计算不可区分的（computational indistinguishable）。

  $$Commit(r, 0) \simeq ^c Commit(s, 1)$$

Type2：Computational binding + Unconditional hiding

• Computational binding：是指对于有着多项式限制的计算能力的 Sender，它事后篡改成功它一开始发出的承诺的概率是极小的（negligible）。即它能找到可以被打开成不同内容的承诺 $C$ 的概率极小。

  $$Pr \ [\mbox{ Sender outputs } (C, (r, 0), (s, 1)) \mbox{ s.t. } Commit(r, 0) = C = Commit(s, 1) \ ] < negl(l)$$

• Unconditional hiding：是指即使 Receiver 有无限的计算能力，也不能从承诺 $C$ 中得知被承诺的内容到底是什么。即关于 0 的承诺和关于 1 的承诺的分布是统计不可区分的的（statistically indistinguishable），甚至是相等的（perfect indistinguishable）。

  $$Commit(r, 0) \simeq ^s (\mbox{or even } \simeq ^p) \ Commit(s, 1)$$

为什么不能有 Unconditional binding + Unconditional hiding 呢？

从表述中可以看出来，针对计算能力无限的攻击者的 unconditionally 安全级别是最高的，那为什么不能让绑定性（binding）和隐藏性（hiding）同时达到最高的安全级别呢？

答案是：这样的承诺机制是不存在的！证明如下：

如果一个承诺机制是 unconditional binding 的，那么就说明关于 0 的承诺和关于 1 的承诺是没有交集的。因此如果给定一个承诺 $C$，通过穷举 $\{0, 1\}^l$ 中的所有值（这对于计算力无限的 Receiver 来说是可行的）去计算 $Commit(r, 0)$ 与 $Commit(r, 1)$，一定就可以唯一地找到承诺 $C$ 的有效打开（open），也就是说计算力无限的 Reciver 可以从承诺中得知被承诺的内容。这与 unconditional hiding 的要求矛盾。

如果一个承诺机制是 unconditional hiding 的，那么就说明任何承诺既可以被打开成关于 0 的承诺，也可以被打开成关于 1 的承诺。因此如果给定一个承诺 $C$，计算力无限的 Sender 就可以通过穷举 $\{0, 1\}^l$ 中所有的值找到 $r, s$ 满足 $Commit(r, 0) = C = Commit(s, 1)$，这与 unconditional binding 矛盾。

这有点像那个矛和盾的故事。一个人同时夸耀自己所卖的矛是最锋利的矛，自己所卖的盾是最坚固的盾，那么他就无法自圆其说，从而产生悖论。

Pedersen 承诺机制

现在介绍一个承诺机制的具体例子：Pedersen 承诺机制。它于 [Pedersen91] 中被提出，是承诺机制的一个具体构造（construction）。

---

Pedersen Commitment Scheme

• $Gen$：设 $p$，$q$ 为两个素数，满足 $p=2q+1$，且在阶为 $q$ 的群 $(G, \cdot)$ 上离散对数问题是困难的。随机选择两个群中的生成元 $g$，$h$，输出 $(p, q, G, g, h)$。

• $Commit$：当要对 $m$ 做承诺时，随机地选取整数群 $\mathbb{Z}_q^*$ 中的元素 $r$，输出：

  $$C = Commit(r, m) := g^m h^r \mod{q}$$

• $Reveal$：得到一个承诺的打开 $(r, m)$ 后，验证 $(r, m, C)$ 是否满足 $C = g^m h^r \mod q$，若满足则输出 1。

---

注意到按照定义 $Gen$ 应该输出一个算法，但其实输出这些 $(p, q, G, g, h)$ 公共参数后，算法也就唯一确定了。因此可以认为这两个输出是等价的。

可以证明 Pedersen 承诺机制是 Type2：Computational binding + Unconditional hiding。

• Computational binding：可以通过到离散对数困难问题的归约来证明。假设 Pedersen 承诺机制不是 Computational binding 的，那么就说明多项式计算能力的 Sender 能（以大于 $negl(l)$ 的概率）成功找到同一个承诺的不同打开。即找到

  $$(r, m), (r', m') \ \mbox{ s.t. } \ m \ne m' \mbox{ 且 } \ g^m h^r = C = g^{m'} h^{r'} \mod q$$

  化简可得，

  $$g = h^{\frac{r-r'}{m'-m}} \mod q$$

  这说明 Sender 可以计算出 $g$ 关于 $h$ 的离散对数，而这与离散对数困难问题的假设是矛盾的。

• Unconditional hiding：分析承诺 $C = g^m h^r \mod q$ 会发现，因为 $r$ 的随机性，得到的 $C$ 也完全是 $(G, \cdot)$ 中的一个随机元素，因此从承诺 $C$ 中得不出任何关于 $m$ 的信息。

承诺机制在 ZKP 中的应用

在 GI 的零知识证明 中，证明者 P 首先发送给验证者 V 的消息 $H=\pi (G_0)$，可以看作是 P 对于“$H$ 是 $G_0$ 的同构”的一个承诺。而这个承诺在 V 选择 $b=0$ 时被打开，在 V 选择 $b=1$ 时则不会被打开。

我们可以设想一下，如果没有这个承诺被打开的过程，即 P 只给 V 发送 $H$ 和 $\phi$，然后 V 验证 $H = \phi(G_1)$ 是否成立。这就会产生一个很大的安全漏洞：

假设一个恶意的 P* 知道 V 验证的仅仅只是 $H = \phi(G_1)$，那么它就没有必要给 V 发送真正的$H = \pi(G_0)$ 和 $\phi = \pi \circ \omega$，它完全可以给 V 发送 $H’ = \pi(G_1)$ 且 $\phi’ = \pi$，这样 V 的验证也一定会通过。也就是说，一个没有秘密输入（secret value $\omega$）的恶意攻击者 P*，甚至在 $G_0$ 与 $G_1$ 并不真正同构的情况下，都可以通过 V 的验证！这显然是不安全的协议！

然而，加上承诺机制后，这个协议就变得安全了。分析后会发现，这是因为 V 的随机选取值 $b$，使得 P 需要有一半的概率去打开这个承诺。也就是说 P 想要通过验证，他就必须要有具备打开承诺的能力，这就迫使 P 发送真实的 $G_0$ 的同构给 V 完成验证。

参考资料

[Blum81]: Manuel Blum. “Coin Flipping by Telephone.” international cryptology conference (1981): 11-15. pdf: https://www.cs.cmu.edu/~mblum/research/pdf/coin/

[Pedersen91]: Torben P Pedersen. “Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing.” international cryptology conference (1991): 129-140. pdf: https://link.springer.com/chapter/10.1007%2F3-540-46766-1_9

Note on Commitment Schemes and Zero-Knowledge Protocols by Damgard et al. pdf: https://users-cs.au.dk/~ivan/ComZK08.pdf

Slides on Zero knowledge and some applications by Helger Lipmaa. pdf: http://kodu.ut.ee/~lipmaa/teaching/Bergen2004.pdf