Commitment Scheme
Table of Contents
1. 问题
在“猜拳”游戏中，可能某人故意慢那么一点点，看到对方的出拳后，自己才出拳。如何避免这种作弊情况呢？本文的主角“Commitment Scheme”可以解决这个问题。
Commitment Scheme 源于 Manuel Blum 的论文 Coin Flipping by Telephone ，Manuel Blum 构造了这么一个场景：“Alice 和 Bob 刚刚离婚，他们生成在不同的城市，想在电话中通过掷硬币的方式来决定谁可以获得小汽车。”
1.1. 思路（基于哈希函数）
假设有哈希函数满足条件：
- 从 \(x\) 计算 \(Hash(x)\) 容易，但很难反向计算；
- 很难找到两个不同的 \(x,y\) ，满足 \(Hash(x)=Hash(y)\) 。
那 Alice 和 Bob 可以使用下面方式进行猜拳游戏：
- Alice 选择自己的出拳方案（如 \(x1=0/1/2\) 分别表示石头/剪刀/布），另外再选择一个随机串 \(r1\) ，然后计算哈希 \(Hash(r1 || x1)\) ，并把哈希值发送给 Bob；
- Bob 选择自己的出拳方案 \(x2\) ，另外再选择一个随机串 \(r2\) ，然后计算哈希 \(Hash(r2 || x2)\) ，并把哈希值发送给 Alice；
- Alice 和 Bob 都收到对方的哈希值后，他们可以把各自的出拳方案和随机串公开给对方，这样，没有人可以作弊。
当然，如果有一个“公正的第三方”，则不用搞这么麻烦，直接 Alice/Bob 都把自己的出拳方案告诉“公正的第三方”即可。Commitment Scheme 的价值就在于：不需要公正的第三方，就可以解决这类问题。
前面例子中的 \(r1\) 和 \(r2\) 被称为“blinding factor”，它们存在的目的是“避免别人通过穷举算出原始的秘密”。 假设 Alice 不加入 blinding factor，直接对出拳方案（ \(x1=0/1/2\) ）计算哈希，则 Bob 可以先算出 3 种出拳方案的哈希，和 Alice 给出的哈希进行对比就可以知道 Alice 的出拳方案了，显然这不安全。
2. Commitment Scheme
从前面的介绍中，我们可以知道一个 Commitment Scheme 协议有两个步骤：
- Commit Phase. 把暂时不想公开的秘密（即前面的出拳方案）再加一个随机数，加密后（如前面的计算哈希）发送给对方；
- Reveal Phase. 公开秘密和随机数。
2.1. Hidingness and Bindingness
Commitment Scheme 的安全性可从两个方面来说明：
- Hidingness (or Confidentiality). 如果原始机密消息 \(x_1\) 和 \(x_2\) 不相同，那么 \(Commit(x_1)\) 和 \(Commit(x_2)\) 不可区分。换句话说，就是 \(Commit(x)\) 不会泄露关于 \(x\) 的任何信息。
- Bindingness. 对于某个 Commit，只有一种方式可以进行揭秘。换句话说，攻击者不可能找到一个不同的 \(x\) ，产生相同的 \(Commit(x)\) 。
一般使用“Perfectly/Computationally”来描述满足某个安全性的强弱：
- "Perfectly"：表示即使拥有无穷计算力的机器也不可能打破相关安全性。
- "Computationally"：表示目前的计算机在可忍受时间内不会打破相关安全性。
不过， 一个 Commitment Scheme 不可能同时满足 Perfectly Hiding 和 Perfectly Binding。 为什么呢？假设一个方案满足 Perfectly Hiding，那么一定存在多个 \(x\) ，对应同一个 \(Commit(x)\) 。否则，一个计算力无穷的机器通过穷举可以算出 \(Commit(x)\) 背后的那个 \(x\) 。而多个 \(x\) ，对应同一个 \(Commit(x)\) ，这显然违背了 Perfectly Binding。
从而，现实中我们有下面两类 Commitment：
- Perfectly hiding and computationally binding，如 Pedersen Commitment
- Perfectly binding but computationally hiding，如 ElGamal Commitment
3. Pedersen Commitment（Perfectly Hiding, Computationally Binding）
3.1. Pedersen Commitment（基于 Discrete Log）
在节 1.1 中是使用哈希函数来加密的，显然其它“很难反向计算”的方式也行，比如使用离散对数（Discrete Log）。
1991 年，Pedersen 在论文 Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing 提出了一种基于 Discrete Log 的 Commitment Scheme。
Pedersen Commitment 的两个阶段：
- Commit Phase，把 \(commit(x, r) = g^x h^r\) 给对方，其中 \(g,h\) 是参数， \(x\) 是暂时不想公开的秘密， \(r\) 是随机数；
- Reveal Phase，公开 \(x,r\) 。
3.1.1. Pedersen Commitment 优点：加同态特性
Pedersen Commitment 的一个优良特性是：具备加同态特性，即满足： \[commit(x_1, r_1) \cdot commit(x_2, r_2) = commit(x_1 + x_2, r_1 + r_2)\]
3.2. Pedersen Commitment（基于 ECC）
可以在椭圆曲线上使用 Pedersen Commitment，假设暂时不想公开的秘密是 \(x\) ，Pedersen Commitment 描述如下：
- 随机选择一个 blinding factor，记为 \(r\) ；
- 则 Commitment 就是 \(C = x * G + r * H\) ，其中 \(G, H\) 是参数，它们可以是椭圆曲线上随机选择的两个点；往往 \(G\) 选择为 Base Point，而 \(H\) 随机选择；
- Reveal 时，公开 \(x, r\)
下面验证一下它的加同态特性：
3.2.1. 加同态特性的应用（罗门币）
罗门币中使用 Pedersen Commitment 的“加同态特性”实现 Tx 中 Inputs/Outputs 中的 amount 的隐藏，从而达到更好的隐私。隐藏 amount 后，节点需要确保没有罗门币凭空产生，也就是不考虑手续费的情况下，Tx 的 Inputs 中 amount 之和与 Outputs 中 amount 之和相等。
大概思路是，把 Tx 中每个 Inputs/Outputs 的 amount 信息替换为 amount 的 Pedersen Commitment，即公开 \(C_{\text{amount_in_input}_1}, C_{\text{amount_in_input}_2}, \cdots, C_{\text{amount_in_output}_1}, C_{\text{amount_in_output}_2}, \cdots\) 。节点进行验证时，如果等式 \[C_{\text{amount_in_input}_1}, C_{\text{amount_in_input}_2}, \cdots = C_{\text{amount_in_output}_1}, C_{\text{amount_in_output}_2}, \cdots\] 成立，则说明这个 Tx Inputs 的金额之和与 Outputs 的金额之和是相等的，这样证明了“没有凭空产生出罗门币”。
不过，罗门币中还需要处理其它一些情况，如：amount 可能溢出为负数，要防止这样的情况发生： \(1 + 1 = -5 + 7\) ，解决办法是使用 Range Proof 来证明所有 amount 都在某个指定范围内，这里不进行介绍。前面考虑的是没有手续费的情况，引入手续费后的处理可参考：https://medium.com/coinmonks/zero-knowledge-proofs-um-what-a092f0ee9f28
4. ElGamal Commitment（Computational Hiding, Perfectly Binding）
假设 \(G\) 是阶为 \(q\) 的循环群，而 \(g,h\) 是 \(G\) 的两个随机生成元。
ElGamal Commitment 的两个阶段：
- Commit Phase：暂时不想公开的秘密为 \(m\) ，它是 \(G\) 中元素，即 \(m \in G\) ；在 \(\mathbb{Z}_q\) 中随机选择 \(r\) ，把 \(Commit = (g^r, m h^r)\) 给对方；
- Reveal Phase：公开 \((m,r)\) ，如果 \(Commit = (g^r, m h^r)\) 成立，则接受它。
为什么 ElGamal Commitment 是 Perfectly Binding 的呢？因为，公开 \(g^r\) 时， \(r\) 就唯一确定的了（只是没有 Reveal 前暂时不知道）； \(r\) 确定后，公开 \(m h^r\) 时， \(m\) 就唯一确定了。也就是当 \((m,r)\) 不同时，它的 Commitment 一定不一样。
5. Fujisaki-Okamoto Commitment（Statistically Hiding, Computationally Binding）
下面介绍 Eiichiro Fujisaki 和 Tatsuaki Okamoto 于 1997 年在论文 Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations 是提出了一种 Commitment Schema。
设 \(n\) 是一个很大的合数，但 Alice 和 Bob 都不知道它的因子分解， \(g \in \mathbb{Z}_n^{\star}, h \in \langle g \rangle\) ，记号 \(\langle g \rangle\) 表示由 \(g\) 生成的群，且 \(g,h\) 是大素数，Alice 不知道 \(\log_gh\) 和 \(\log_hg\) 。
- Commit Phase：Alice 计算 \(Commit(x,r) = g^x h^r \bmod n\) 发送给 Bob，其中 \(r\) 是随机数，满足 \(r \in [2^{-s}n + 1, 2^s n - 1]\) ，这里 \(s\) 是人为设置的参数，满足 \(2^{-s}\) 很小就行。
- Reveal Phase：Alice 公开 \(x,r\) ，Bob 验证 \(Commit(x,r) = g^x h^r \bmod n\) 是否成立。
5.1. Pedersen Commitment VS. Fujisaki-Okamoto Commitment
Fujisaki-Okamoto Commitment 和 Pedersen Commitment 的计算形式是一样的，都具体加同态特性，只是计算背后所定义的群不一样，它们所依赖的安全假设也不一样，表 1 是它们的一些异同。
| Assumption | Hiding | Binding | Additive Homomorphic | |
|---|---|---|---|---|
| Pedersen | Discrete Logarithm | Perfectly | Computationally | Yes |
| Fujisaki-Okamoto | Strong RSA Assumption | Statistically | Computationally | Yes |