Commitment Scheme

1. 问题
- 1.1. 思路（基于哈希函数）
2. Commitment Scheme
- 2.1. Hidingness and Bindingness
3. Pedersen Commitment（Perfectly Hiding, Computationally Binding）
- 3.1. Pedersen Commitment（基于 Discrete Log）
  - 3.1.1. Pedersen Commitment 优点：加同态特性
- 3.2. Pedersen Commitment（基于 ECC）
  - 3.2.1. 加同态特性的应用（Monero）
4. ElGamal Commitment（Computational Hiding, Perfectly Binding）
5. Fujisaki-Okamoto Commitment（Statistically Hiding, Computationally Binding）
- 5.1. Pedersen Commitment VS. Fujisaki-Okamoto Commitment
6. 参考

1. 问题

在“猜拳”游戏中，可能某人故意慢那么一点点，看到对方的出拳后，自己才出拳。如何避免这种作弊情况呢？本文的主角“Commitment Scheme”可以解决这个问题。

Commitment Scheme 源于 Manuel Blum 的论文 Coin Flipping by Telephone ，Manuel Blum 构造了这么一个场景：“Alice 和 Bob 刚刚离婚，他们生成在不同的城市，想在电话中通过掷硬币的方式来决定谁可以获得小汽车。”

1.1. 思路（基于哈希函数）

下面的思路可以解决“猜拳”游戏中的作弊问题。

假设有哈希函数满足条件：

从 $x$ 计算 $H a s h (x)$ 容易，但很难反向计算；
很难找到两个不同的 $x, y$ ，满足 $H a s h (x) = H a s h (y)$ 。

那 Alice 和 Bob 可以使用下面方式进行猜拳游戏：

Alice 选择自己的出拳方案（如 $x 1 = 0 / 1 / 2$ 分别表示石头/剪刀/布），另外再选择一个随机串 $r 1$ ，然后计算哈希 $H a s h (r 1 | | x 1)$ ，并把哈希值发送给 Bob；
Bob 选择自己的出拳方案 $x 2$ ，另外再选择一个随机串 $r 2$ ，然后计算哈希 $H a s h (r 2 | | x 2)$ ，并把哈希值发送给 Alice；
Alice 和 Bob 都收到对方的哈希值后，他们可以把各自的出拳方案和随机串公开给对方，这样，没有人可以作弊。

当然，如果有一个“公正的第三方”，则不用搞这么麻烦，直接 Alice/Bob 都把自己的出拳方案告诉“公正的第三方”即可。Commitment Scheme 的价值就在于：不需要公正的第三方，就可以解决这类问题。

前面例子中的 $r 1$ 和 $r 2$ 被称为“blinding factor”，它们存在的目的是“避免别人通过穷举算出原始的秘密”。 假设 Alice 不加入 blinding factor，直接对出拳方案（ $x 1 = 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}$ 不相同，那么 $C o m m i t (x_{1})$ 和 $C o m m i t (x_{2})$ 不可区分。换句话说，就是 $C o m m i t (x)$ 不会泄露关于 $x$ 的任何信息。
Bindingness. 对于某个 Commit，只有一种方式可以进行揭秘。换句话说，攻击者不可能找到一个不同的 $x$ ，产生相同的 $C o m m i t (x)$ 。

一般使用“Perfectly/Computationally”来描述满足某个安全性的强弱：

"Perfectly"：表示即使拥有无穷计算力的机器也不可能打破相关安全性。
"Computationally"：表示目前的计算机在可忍受时间内不会打破相关安全性。

不过， 一个 Commitment Scheme 不可能同时满足 Perfectly Hiding 和 Perfectly Binding。 为什么呢？假设一个方案满足 Perfectly Hiding，那么一定存在多个 $x$ ，对应同一个 $C o m m i t (x)$ 。否则，一个计算力无穷的机器通过穷举可以算出 $C o m m i t (x)$ 背后的那个 $x$ 。而多个 $x$ ，对应同一个 $C o m m i t (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，把 $c o m m i t (x, r) = g^{x} h^{r}$ 给对方，其中 $g, h$ 是参数， $x$ 是暂时不想公开的秘密， $r$ 是随机数；
Reveal Phase，公开 $x, r$ 。

3.1.1. Pedersen Commitment 优点：加同态特性

Pedersen Commitment 的一个优良特性是：具备加同态特性，即满足： $c o m m i t (x_{1}, r_{1}) \cdot c o m m i t (x_{2}, r_{2}) = c o m m i t (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$

下面验证一下它的加同态特性：

\begin{aligned} C_{x_{1}, r_{1}} + C_{x_{2}, r_{2}} & = (x_{1} * G + r_{1} * H) + (x_{2} * G + r_{2} * H) \\ = (x_{1} + x_{2}) * G + (r_{1} + r_{2}) * H \\ = C_{x_{1} + x_{2}, r_{1} + r_{2}} \end{aligned}

3.2.1. 加同态特性的应用（Monero）

门罗币（Monero）中使用 Pedersen Commitment 的“加同态特性”实现 Tx 中 Inputs/Outputs 中的 amount 的隐藏，从而达到更好的隐私。隐藏 amount 后，节点需要确保没有门罗币凭空产生，也就是不考虑手续费的情况下，Tx 的 Inputs 中 amount 之和与 Outputs 中 amount 之和相等。

大概思路是，把 Tx 中每个 Inputs/Outputs 的 amount 信息替换为 amount 的 Pedersen Commitment，即公开 $C_{{amount_in_input}_{1}}, C_{{amount_in_input}_{2}}, \dots, C_{{amount_in_output}_{1}}, C_{{amount_in_output}_{2}}, \dots$ 。节点进行验证时，如果等式 $C_{{amount_in_input}_{1}}, C_{{amount_in_input}_{2}}, \dots = C_{{amount_in_output}_{1}}, C_{{amount_in_output}_{2}}, \dots$ 成立，则说明这个 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$ ；在 $Z_{q}$ 中随机选择 $r$ ，把 $C o m m i t = (g^{r}, m h^{r})$ 给对方；
Reveal Phase：公开 $(m, r)$ ，如果 $C o m m i t = (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 Z_{n}^{⋆}, h \in ⟨ g ⟩$ ，记号 $⟨ g ⟩$ 表示由 $g$ 生成的群，且 $g, h$ 是大素数，Alice 不知道 $\log_{g} h$ 和 $\log_{h} g$ 。

Commit Phase：Alice 计算 $C o m m i t (x, r) = g^{x} h^{r} mod n$ 发送给 Bob，其中 $r$ 是随机数，满足 $r \in [2^{- s} n + 1, 2^{s} n - 1]$ ，这里 $s$ 是人为设置的参数，满足 $2^{- s}$ 很小就行。
Reveal Phase：Alice 公开 $x, r$ ，Bob 验证 $C o m m i t (x, r) = g^{x} h^{r} mod n$ 是否成立。

5.1. Pedersen Commitment VS. Fujisaki-Okamoto Commitment

Fujisaki-Okamoto Commitment 和 Pedersen Commitment 的计算形式是一样的，都具体加同态特性，只是计算背后所定义的群不一样，它们所依赖的安全假设也不一样，表 1 是它们的一些异同。

Table 1: Pedersen Commitment VS. Fujisaki-Okamoto Commitment
	Assumption	Hiding	Binding	Additive Homomorphic
Pedersen	Discrete Logarithm	Perfectly	Computationally	Yes
Fujisaki-Okamoto	Strong RSA Assumption	Statistically	Computationally	Yes

6. 参考

https://en.wikipedia.org/wiki/Commitment_scheme
Coin Flipping by Telephone
Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing
https://asecuritysite.com/encryption/ped