从零开始学习 zk-SNARK（五）—— Pinocchio 协议

我们的分析主要集中在运算的概念上。但是，协议实际上不是去做”计算“，而是检验输出值是否是操作数正确运算得到的结果。所以我们称之为约束，即一个 verifier 约束 prover 去为预定义的“程序”提供有效值，而无论这个“程序”是什么。多个约束组成的系统被称为“约束系统”（在我们的例子中这是一个一阶约束系统，或被称为R1CS）。

@Maksym（作者）：这里其实隐含了寻找所有正确答案的一个方法就是对所有可能的组合值进行一次暴力破解，然后只选择一个满足的约束，或者使用可满足约束的更精密的技术[con18]。

如果不能根据 verifier 的输入对其进行检查，那么证明的可用性将受到限制。也就是说，虽然知道 prover 将两个值相乘但是并不知道这些值和/或计算结果。尽管有可能在 proving key 中通过“硬编码”来进行验证一些特定的值（如，乘法运算的结果必须为12），但这就需要针对每一个想要的“verifier 的输入”生成单独的密钥对。

• Setup
• verifier 的 m+1 项：,对  和  也做同样的计算。这里对于索引0 保留值 
• prover 的 n-m 项：

  ，对  和  也做同样的计算。
• …将 n 个可变多项式全部分为两组：
• 设置 proving key：
• 添加到 verification key：
• Proving
• …为 verifier 的多项式计算 h(x)：，其中 ， ， 也通过同样的计算获得。
• 提供证明：
• Verification
• 为 verifier 的变量多项式赋值，并加 1：

  ，对  和  做同样的计算
• 变量多项式约束检查：

  ，对  和  做同样的计算
• 变量值一致性检查：
• 有效计算检查：

注意：根据协议（单个变量操作数多项式 的章节）的性质，由多项式 l₀(x),r₀(x),o₀(x) 表示的值 1 已在相应的运算中具备了合适的值，因此不需要再赋值了。

verifier 将不得不在验证步骤中做额外的工作，使得赋值的变量成比例。

• 其他人可以很容易得辨认出两个不同的多项式值是否相同，以此来获取一些知识，即：g^δL(s)=g^δR(s)

• L(s) 和 R(s) 的不同值之间潜在的微小关系可能会通过暴力破解来区分开来，例如如果 L(s) = 5R(s)，就可以对 i ∈ {1…N} 取值反复校验 g^L(s)=(g^R(s))ⁱ ，只需要执行 5 步就可以揭示出两者 5 倍区别的关系。同样的暴力破解也可以用在破解加密值的加法运算上，如：g^L(s) = g^R(s)+5

• 证明元素之间的其它关系也可能会被发现，例如，如果 e(g^δL(s),g^δR(s)) = e(g^δ2O(s),g)，那么也就表示 L(x) ⋅ R(x) = O(x)。

注意：一致性检查优化 使得挖掘数据关系变得更加困难了，但是依然能够发现一些关系 ，且不说 verifier 可以选择特定  ρ_l， ρ_r  来为揭示知识提供便利（只要这不是一个多样化的 setup）。

注意：这种方法和 verfier 的操作数也是一致的，即：g_l^L_p+δ_lt ·g_l^L_v = g^{L_p+L_v+δ_lt}。

因而当且仅当 prover 使用了 verifier 的值来构造证明(即， Δ = δ_r(L_p + L_v) + δ_l(R_p+ R_v ) + δ_lδ_rt – δ_o)，这个有效计算的检查依然是成立的，更多的细节看下一部分。

• 简明 (Succinctly) —— 独立于计算量，证明是恒定的，小尺寸的

• 非交互性 (Non-interactive) —— 证明只要一经计算就可以在不直接与 prover 交互的前提下使任意数量的 verifier 确信

• 可论证的知识 (with Argument of Knowledge) —— 对于陈述是正确的这点有不可忽略的概率，即无法构造假证据；并且 prover 知道正确陈述的对应值（即：证据），例如，如果陈述是 “B 是 sha256(a) 的结果” 那么就说明 prover 知道一些值 a 能够使得 B = sha256(a) 成立，因为 B 只能够通过 a 的知识计算出来，换句话说就是无法通过 B 来反算出 a（假定 a 的熵足够）。

• 陈述有不可忽略的概率是正确的 (even@安比实验室: 这里指Soundness可靠性)，即，构造假证据是不可行的

• 零知识( zero-knowledge)  —— 很“难”从证明中提取任何知识，即，它与随机数无法区分。