承诺方案Commitment
概念：承诺，是密码学中的概念，只有对于有界算力的参与者，才能提供可靠性和零知识，故而论证系统是基于承诺构建的。
IOP(Interactive Oracle Proof)：理想协议，是信息论里的概念，无界算力保证零知识和可靠性，证明者提供与挑战者与M相关联的函数，但验证者只能通过放一些值确认函数是否正确，以验证了证明在确实拥有什么信息，这个过程已经隐藏了关键信息。（通过证明，非论证，实现了完美零知识）
定义：承诺方案是 PPT 算法的元组 $τ$ = (𝑆𝑒𝑡𝑢𝑝, 𝐶𝑜𝑚𝑚𝑖𝑡, 𝑂𝑝𝑒𝑛)，其中：
分号";"后面表示的为非公开元素
𝑆𝑒𝑡𝑢𝑝($1^𝜆$) → 𝑝𝑝： 采用安全参数 𝜆（一元）并生成公共参数 𝑝𝑝；
𝐶𝑜𝑚𝑚𝑖𝑡(𝑝𝑝; 𝑚) → (𝐶; 𝑟)： 获取秘密消息 𝑚（信息域 𝑚 ∈ $M$） 并输出公开承诺 𝐶 和（可选）秘密打开提示 𝑟（可能为随机数）
𝑂𝑝𝑒𝑛(𝑝𝑝, 𝐶; 𝑚, 𝑟) → 𝑏 ∈ {0,1}： 利用打开提示 𝑟，验证承诺 𝐶 对消息 𝑚 的打开，
一、Sigma协议
零知识证明过程中Prover一般通过承诺Commitment来论证，多采用sigma protocol的形式，包含两个阶段
Commitment承诺阶段（Setup & Commit）
隐藏性hiding，该承诺不会泄露任何真实data，即拿到承诺本身，无法反猜回去信息（几率可忽略）
Response开启阶段 (Open)
绑定性binding，承诺只能由真实的data开启以供检验，且一一对应（几率可忽略）。
二、例1：Pedersen承诺
[m]表示单独一个数字
Pedersen 承诺是一个在消息空间 $𝔽_𝑞$ 上具有绑定性和隐藏性的承诺方案。
对于一个秘密消息 𝑚 ∈ $𝔽_𝑞$：
𝑆𝑒𝑡𝑢𝑝 ($1^𝜆$ , 𝑞) → 𝑝𝑝： 𝑝𝑝 = 𝐺, 𝐻 ∈ 𝔾，其中 𝔾 是一个阶为 q 的群。
𝐶𝑜𝑚𝑚𝑖𝑡 (𝑝𝑝; 𝑚) → (𝐶; 𝑟)： 𝐶 = [𝑚]𝐺 + [𝑟]𝐻， 𝑟 ← $𝔽_𝑞$ 。
𝑂𝑝𝑒𝑛 (𝑝𝑝, 𝐶; 𝑚, 𝑟) → {0,1}：证明者 P 揭示 m 和 r，验证者 V 检查 𝐶 → [𝑚]𝐺 + [𝑟]𝐻 是否成立。
零知识过程，实际就是对open过程拆开，verify验证是否相等，prover提供m,r
特性：加法同态性
𝐶𝑜𝑚𝑚𝑖𝑡(𝑚, 𝑟) + 𝐶𝑜𝑚𝑚𝑖𝑡(𝑚′ , 𝑟′)
= [𝑚]𝐺 + [𝑟]𝐻 + [𝑚′]𝐺 + [𝑟′]𝐻
= [𝑚 + 𝑚′]𝐺 + [𝑟 + 𝑟′]𝐻
= 𝐶𝑜𝑚𝑚𝑖𝑡(𝑚 + 𝑚′ , 𝑟 + 𝑟′)
三、例2：向量Pedersen承诺
实现了向量版本，很关键
将 Pedersen 承诺方案扩展到消息空间 $𝔽_𝑞^𝑘$ 中的向量。
对于一个消息 $\vec{𝑚}$ = ($𝑚_0$, … , $𝑚_{𝑘−1}$)：
𝑆𝑒𝑡𝑢𝑝 ($1^𝜆$, 𝑞, 𝑘) → 𝑝𝑝：𝑝𝑝 = ($𝐺_0$, … , $𝐺_{𝑘−1}$), 𝐻 ∈ 𝔾，其中 𝔾 是一个阶 为 𝑞 的群。
𝐶𝑜𝑚𝑚𝑖𝑡 (𝑝𝑝; $\vec{𝑚}$) → (𝐶; 𝑟)： 𝐶 = $\sum_{𝑖=0}^{𝑘−1}{[𝑚_𝑖]𝐺_𝑖}$，𝑟 ← $𝔽_𝑞$。
𝑂𝑝𝑒𝑛 (𝑝𝑝, 𝐶; $\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^𝜆$ , 𝑑) →
ck：Proving key；vk：verify key
如 $[𝛼]_2$ : 表示在 $𝐺_2$ 上的坐标
srs：Structured Referenced String，结构化引用字符串，如这里{ $[𝛼]_1$ , $[𝛼]_2$ ……}存的就是这样的string，并非相加等关系。
𝛼 就是 $τ$，也是个随机数，相当于一个共识。是一个秘密元素，必须在 𝑆𝑒𝑡𝑢𝑝 后丢弃。KZG ceremony就是通过MPC安全多方计算在保护 𝛼 （只有提供随机数的人全部串通才有风险，任一诚实都无事）
𝛼未知，但映射到点的坐标结果是有的，如 $[f(𝛼)]_1$
𝐶𝑜𝑚𝑚𝑖𝑡 (𝑐𝑘; 𝑓(𝑋)) → 𝐶：对于 𝑓(𝑋) = $\sum_{𝑖=0}^{d−1}{𝑓_𝑖𝑋^𝑖}$ , 𝐶 = $\sum_{𝑖=0}^{d−1}{[𝑓_𝑖][𝛼^𝑖]_1 }$ = $[𝑓(𝛼)]_1$.
$F(x)$， $x$ 为消息参数，实际为一对一的映射关系，表示为多项式。
$C$ 相当于是个坐标，以前是直接知道一个算出的消息 $x$ 承诺，现在对多项式 $f(x)$ 进行承诺
𝑂𝑝𝑒𝑛(𝑠𝑟𝑠, 𝐶, 𝑧, 𝑦; 𝑓(𝑋)) → {0,1}： 在评估点 𝑧 上打开对于 𝑦 的承诺
𝑃𝑟𝑜𝑣𝑒 (𝑐𝑘, 𝐶, 𝑧, 𝑦; 𝑓(𝑋)) → $𝜋$
$𝜋$ 为精简的证据，是一个点坐标，可以看到verify过程传入π而没传 $f(x)$ )
零知识的点：利用ck与vk的双线性映射关系，ck产生的commit能通过vk验证
商多项式 𝑞(𝑋) = $\frac{𝑓(𝑋)−𝑦}{ 𝑋−𝑧}$ , 𝜋 = 𝐶𝑜𝑚𝑚𝑖𝑡 (𝑐𝑘; 𝑞(𝑋)) = $[𝑞(𝛼)]_1$
商多项式：多项式/多项式 仍 = 合法多项式（不含有余数等等）。即通过验证商多项式是有效的，论证已得到了正确解，例如：
𝑉𝑒𝑟𝑖𝑓𝑦 (𝑣𝑘, 𝐶, 𝑧, 𝑦, 𝜋) → {0,1}
检查是否可以推出 𝑒(𝐶 − $[𝑦]_1$, $[1]_2$) ← 𝑒($𝜋$, $[𝛼]_2$ − $[𝑧]_2$).
e：双线性映射，常数复杂度，所以验证是十分快速的
注：circom中的约束到上述这些公式中的参数，非直观一一对应，被打散到了多项式里，中间还包含算术化（详见算术化章节）的过程
Last updated