承诺方案

承诺方案Commitment

概念：承诺，是密码学中的概念，只有对于有界算力的参与者，才能提供可靠性和零知识，故而论证系统是基于承诺构建的。

IOP(Interactive Oracle Proof)：理想协议，是信息论里的概念，无界算力保证零知识和可靠性，证明者提供与挑战者与M相关联的函数，但验证者只能通过放一些值确认函数是否正确，以验证了证明在确实拥有什么信息，这个过程已经隐藏了关键信息。（通过证明，非论证，实现了完美零知识）

定义：承诺方案是 PPT 算法的元组 $τ$ = (𝑆𝑒𝑡𝑢𝑝, 𝐶𝑜𝑚𝑚𝑖𝑡, 𝑂𝑝𝑒𝑛)，其中：

分号";"后面表示的为非公开元素

1. 𝑆𝑒𝑡𝑢𝑝($1^𝜆$) → 𝑝𝑝： 采用安全参数 𝜆（一元）并生成公共参数 𝑝𝑝；
2. 𝐶𝑜𝑚𝑚𝑖𝑡(𝑝𝑝; 𝑚) → (𝐶; 𝑟)： 获取秘密消息 𝑚（信息域 𝑚 ∈ $M$） 并输出公开承诺 𝐶 和（可选）秘密打开提示 𝑟（可能为随机数）
3. 𝑂𝑝𝑒𝑛(𝑝𝑝, 𝐶; 𝑚, 𝑟) → 𝑏 ∈ {0,1}： 利用打开提示 𝑟，验证承诺 𝐶 对消息 𝑚 的打开，

一、Sigma协议

零知识证明过程中Prover一般通过承诺Commitment来论证，多采用sigma protocol的形式，包含两个阶段

1. Commitment承诺阶段（Setup & Commit）

   隐藏性hiding，该承诺不会泄露任何真实data，即拿到承诺本身，无法反猜回去信息（几率可忽略）

2. Response开启阶段 (Open)

   绑定性binding，承诺只能由真实的data开启以供检验，且一一对应（几率可忽略）。

二、例1：Pedersen承诺

[m]表示单独一个数字

Pedersen 承诺是一个在消息空间 $𝔽_𝑞$ 上具有绑定性和隐藏性的承诺方案。

对于一个秘密消息 𝑚 ∈ $𝔽_𝑞$：

1. 𝑆𝑒𝑡𝑢𝑝 ($1^𝜆$ , 𝑞) → 𝑝𝑝： 𝑝𝑝 = 𝐺, 𝐻 ∈ 𝔾，其中 𝔾 是一个阶为 q 的群。

2. 𝐶𝑜𝑚𝑚𝑖𝑡 (𝑝𝑝; 𝑚) → (𝐶; 𝑟)： 𝐶 = [𝑚]𝐺 + [𝑟]𝐻， 𝑟 ← $𝔽_𝑞$ 。

3. 𝑂𝑝𝑒𝑛 (𝑝𝑝, 𝐶; 𝑚, 𝑟) → {0,1}：证明者 P 揭示 m 和 r，验证者 V 检查 𝐶 → [𝑚]𝐺 + [𝑟]𝐻 是否成立。

   零知识过程，实际就是对open过程拆开，verify验证是否相等，prover提供m,r

特性：加法同态性

• 𝐶𝑜𝑚𝑚𝑖𝑡(𝑚, 𝑟) + 𝐶𝑜𝑚𝑚𝑖𝑡(𝑚′ , 𝑟′)

  = [𝑚]𝐺 + [𝑟]𝐻 + [𝑚′]𝐺 + [𝑟′]𝐻

  = [𝑚 + 𝑚′]𝐺 + [𝑟 + 𝑟′]𝐻

  = 𝐶𝑜𝑚𝑚𝑖𝑡(𝑚 + 𝑚′ , 𝑟 + 𝑟′)

三、例2：向量Pedersen承诺

实现了向量版本，很关键

将 Pedersen 承诺方案扩展到消息空间 $𝔽_𝑞^𝑘$ 中的向量。

对于一个消息 $\vec{𝑚}$ = ($𝑚_0$, … , $𝑚_{𝑘−1}$)：

1. 𝑆𝑒𝑡𝑢𝑝 ($1^𝜆$, 𝑞, 𝑘) → 𝑝𝑝：𝑝𝑝 = ($𝐺_0$, … , $𝐺_{𝑘−1}$), 𝐻 ∈ 𝔾，其中 𝔾 是一个阶 为 𝑞 的群。
2. 𝐶𝑜𝑚𝑚𝑖𝑡 (𝑝𝑝; $\vec{𝑚}$) → (𝐶; 𝑟)： 𝐶 = $\sum_{𝑖=0}^{𝑘−1}{[𝑚_𝑖]𝐺_𝑖}$，𝑟 ← $𝔽_𝑞$。
3. 𝑂𝑝𝑒𝑛 (𝑝𝑝, 𝐶; $\vec{𝑚}$, 𝑟) → {0,1}：
   • 证明者 Prover 揭示 $\vec{𝑚}$ 和 𝑟
   • 验证者 Verifier 检查 𝐶

四、例3：双线性映射

如基于双线性paring的bls12-381曲线（ETH beacon BLS签名用到该曲线，但不是一回事）

给定循环群 𝔾1, 𝔾2, 𝔾𝑇，所有的阶均为素数 𝑝，其映射关系是一个非退化的双线性映射 $𝑒：𝔾_1 × 𝔾_2 → 𝔾_𝑇$ 特性：

• 双线性:
  • $𝑒([𝑎]𝑃, 𝑄)$ = $[𝑎]𝑒(𝑃, 𝑄)$ = $𝑒(𝑃, [𝑎]𝑄)$
  • $𝑒([𝑎]𝑃, [𝑏]𝑄)$ = $[𝑎 · 𝑏]𝑒(𝑃, 𝑄)$ = $𝑒(𝑃, 𝑄)^{(𝑎⋅𝑏) }$
• 非退化:
  • 对于生成元 $𝐺_1$ ∈ $𝔾_1$ 和 $𝐺_2$ ∈ $𝔾_2$， $𝐺_𝑇 := 𝑒(𝐺_1, 𝐺_2) ∈ 𝔾_𝑇$ 是一个生成元

五、例4：KZG承诺

论证实现完美零知识证明

KZG承诺是一个密码学技术，大致原理如下：

• 对多项式 $f(x)$，证明者通过椭圆曲线密码学技术，对该多项式做出承诺 $C(f)$ ：对于这个多项式的任意值 $y = f(z)$，证明者可以计算出一个 "证明" $π(f,z)$
• 对于验证者，已知承诺 $C(f)$，给出证明 $π(f,z)$、变量z、取值y 三个数据，验证者可以证实 $f(z)= y$ ，即 $(z,y)$ 确实在这个多项式函数上
• 这个证明无需验证者知道这个多项式具体是什么，并且它的时间开销近似为常数，因此具备高度的实用性和可扩展性

过程：

单变量多项式承诺方案是针对消息空间 𝔽 ≤𝑑 [𝑋] 的一种承诺方案。

1. 𝑆𝑒𝑡𝑢𝑝 ($1^𝜆$ , 𝑑) →

   ck：Proving key；vk：verify key

   如 $[𝛼]_2$ : 表示在 $𝐺_2$ 上的坐标

   srs：Structured Referenced String，结构化引用字符串，如这里{ $[𝛼]_1$ , $[𝛼]_2$ ……}存的就是这样的string，并非相加等关系。

   • 𝛼 就是 $τ$，也是个随机数，相当于一个共识。是一个秘密元素，必须在 𝑆𝑒𝑡𝑢𝑝 后丢弃。KZG ceremony就是通过MPC安全多方计算在保护 𝛼 （只有提供随机数的人全部串通才有风险，任一诚实都无事）

     𝛼未知，但映射到点的坐标结果是有的，如 $[f(𝛼)]_1$

2. 𝐶𝑜𝑚𝑚𝑖𝑡 (𝑐𝑘; 𝑓(𝑋)) → 𝐶：对于 𝑓(𝑋) = $\sum_{𝑖=0}^{d−1}{𝑓_𝑖𝑋^𝑖}$ , 𝐶 = $\sum_{𝑖=0}^{d−1}{[𝑓_𝑖][𝛼^𝑖]_1 }$ = $[𝑓(𝛼)]_1$.

   $F(x)$， $x$ 为消息参数，实际为一对一的映射关系，表示为多项式。

   $C$ 相当于是个坐标，以前是直接知道一个算出的消息 $x$ 承诺，现在对多项式 $f(x)$ 进行承诺

   

3. 𝑂𝑝𝑒𝑛(𝑠𝑟𝑠, 𝐶, 𝑧, 𝑦; 𝑓(𝑋)) → {0,1}： 在评估点 𝑧 上打开对于 𝑦 的承诺

   • 𝑃𝑟𝑜𝑣𝑒 (𝑐𝑘, 𝐶, 𝑧, 𝑦; 𝑓(𝑋)) → $𝜋$

     $𝜋$ 为精简的证据，是一个点坐标，可以看到verify过程传入π而没传 $f(x)$ )

     零知识的点：利用ck与vk的双线性映射关系，ck产生的commit能通过vk验证

     • 商多项式 𝑞(𝑋) = $\frac{𝑓(𝑋)−𝑦}{ 𝑋−𝑧}$ , 𝜋 = 𝐶𝑜𝑚𝑚𝑖𝑡 (𝑐𝑘; 𝑞(𝑋)) = $[𝑞(𝛼)]_1$

       商多项式：多项式/多项式 仍 = 合法多项式（不含有余数等等）。即通过验证商多项式是有效的，论证已得到了正确解，例如：

• 𝑉𝑒𝑟𝑖𝑓𝑦 (𝑣𝑘, 𝐶, 𝑧, 𝑦, 𝜋) → {0,1}

  • 检查是否可以推出 𝑒(𝐶 − $[𝑦]_1$, $[1]_2$) ← 𝑒($𝜋$, $[𝛼]_2$ − $[𝑧]_2$).

    e：双线性映射，常数复杂度，所以验证是十分快速的

注：circom中的约束到上述这些公式中的参数，非直观一一对应，被打散到了多项式里，中间还包含算术化（详见算术化章节）的过程