Skip to content

Latest commit

 

History

History

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 

承诺方案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^𝜆$ , 𝑑) → image

    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)$ 进行承诺

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

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

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

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

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

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

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

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

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

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