> For the complete documentation index, see [llms.txt](https://dezso.gitbook.io/dive-into-blockchian/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dezso.gitbook.io/dive-into-blockchian/learnblockchain-8/learnzero_knowledge/cheng-nuo-fang-an.md).
# 承诺方案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：[双线性映射](https://www.bilibili.com/video/BV11M411m7Qq/?spm_id_from=333.337.search-card.all.click\&vd_source=0dd037413d496f35de84d58a72548d41)
> 如基于双线性paring的[bls12-381曲线](http://aandds.com/blog/bls.html)（ETH beacon BLS签名用到该曲线，**但不是一回事**）
给定循环群 𝔾1, 𝔾2, 𝔾𝑇，所有的阶均为素数 𝑝，其映射关系是一个非退化的双线性映射 $𝑒：𝔾\_1 × 𝔾\_2 → 𝔾\_𝑇$ **特性**：
* 双线性:
* $𝑒(\[𝑎]𝑃, 𝑄)$ = $\[𝑎]𝑒(𝑃, 𝑄)$ = $𝑒(𝑃, \[𝑎]𝑄)$
* $𝑒(\[𝑎]𝑃, \[𝑏]𝑄)$ = $\[𝑎 · 𝑏]𝑒(𝑃, 𝑄)$ = $𝑒(𝑃, 𝑄)^{(𝑎⋅𝑏) }$
* 非退化:
* 对于生成元 $𝐺\_1$ ∈ $𝔾\_1$ 和 $𝐺\_2$ ∈ $𝔾\_2$， $𝐺\_𝑇 := 𝑒(𝐺\_1, 𝐺\_2) ∈ 𝔾\_𝑇$ 是一个生成元
## 五、例4：[KZG承诺](https://dankradfeist.de/ethereum/2021/10/13/kate-polynomial-commitments-mandarin.html)
> 论证实现完美零知识证明
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中的约束到上述这些公式中的参数，非直观一一对应，被打散到了多项式里，中间还包含**算术化**（详见算术化章节）的过程*