JS `Zero-Knowledge Proofs` (`ZK-SNARKs`) `Circuit Design` 与 `Prover/Verifier` `Interaction` - 智猿学院-前后端，数据库，人工智能，云计算等领域前沿技术讲座

大家好，欢迎来到“ZKP：别再懵圈了，咱们一起撸代码！”讲座！

今天咱们不谈高深的密码学理论，就用人话+代码，把零知识证明（特别是ZK-SNARKs）的电路设计和Prover/Verifier交互这俩硬骨头啃下来。保证你听完之后，不仅能吹牛，还能上手写代码！

啥是ZK-SNARKs？为啥它这么火？

ZK-SNARKs，全称Zero-Knowledge Succinct Non-Interactive Argument of Knowledge，翻译成人话就是：

Zero-Knowledge（零知识）： 我证明给你看我知道一个秘密，但你啥也学不到，就是这么任性！
Succinct（简洁）： 证明很短，验证很快，妈妈再也不用担心我的计算资源不够用了！
Non-Interactive（非交互）： 证明发给你，你就自己验证去吧，不用来回问我问题，省事！
Argument of Knowledge（知识论证）： 我不仅知道这个秘密，我还能证明我知道，不是瞎编的！

为啥它火？因为它能在保护隐私的同时，验证计算的正确性！这在区块链、隐私计算等领域简直是神器！

电路设计：把计算变成线路图

ZK-SNARKs的核心在于把你要证明的计算过程，转换成一个算术电路。这个电路就像一个复杂的线路图，每一个门电路都代表一个算术运算。

1. 从代码到算术电路：

咱们先来个简单的例子，证明你知道 x，并且满足 x * x + 5 == y，其中 y 是公开的。

代码 (Python)：

def prove_knowledge(x, y):
  return x * x + 5 == y

算术电路：

我们需要把这个计算过程拆解成加法和乘法运算。

a = x * x
b = a + 5
b == y (约束)

2. Representing电路 as R1CS (Rank-1 Constraint System)：

R1CS 是 ZK-SNARKs 中常用的一种电路表示形式。它将电路的约束表示成矩阵运算。

对于上面的例子，我们可以把R1CS表示如下：

步骤	A	B	C
1	(x)	(x)	(a)
2	(a, 1)	(1)	(b)
3	(b, y)	(1)	(0)

变量分配：

我们还需要定义变量的分配： s = (1, x, y, a, b)。其中 1 是 constant。

R1CS 矩阵表示：

我们可以把上面的表格转换成矩阵形式：

A = [[0, 1, 0, 0, 0],  # x
     [0, 0, 0, 1, 1],  # a + 5
     [0, 0, 1, 0, 1]]  # b - y

B = [[0, 1, 0, 0, 0],  # x
     [1, 0, 0, 0, 0],  # 1
     [1, 0, 0, 0, 0]]  # 1

C = [[0, 0, 0, 1, 0],  # a
     [0, 0, 0, 0, 1],  # b
     [0, 0, 0, 0, 0]]  # 0

验证：

对于每一行 i，我们需要验证 A[i] * s * B[i] * s == C[i] * s。如果所有行都满足，那么这个计算就是正确的。

代码 (Python)：

import numpy as np

def check_r1cs(A, B, C, s):
  """
  检查 R1CS 约束是否满足。

  Args:
    A: A 矩阵。
    B: B 矩阵。
    C: C 矩阵。
    s: 变量分配。

  Returns:
    如果所有约束都满足，返回 True，否则返回 False。
  """
  for i in range(len(A)):
    if np.dot(A[i], s) * np.dot(B[i], s) != np.dot(C[i], s):
      return False
  return True

# 示例数据
x = 5
y = x * x + 5
s = np.array([1, x, y, x * x, x * x + 5])

A = np.array([[0, 1, 0, 0, 0],
              [0, 0, 0, 1, 1],
              [0, 0, 1, 0, 1]])

B = np.array([[0, 1, 0, 0, 0],
              [1, 0, 0, 0, 0],
              [1, 0, 0, 0, 0]])

C = np.array([[0, 0, 0, 1, 0],
              [0, 0, 0, 0, 1],
              [0, 0, 0, 0, 0]])

# 检查 R1CS
if check_r1cs(A, B, C, s):
  print("R1CS 约束满足！")
else:
  print("R1CS 约束不满足！")

3. 电路设计原则：

分解： 将复杂的计算分解成简单的加法和乘法运算。
优化： 尽量减少约束的数量，提高效率。
标准化： 采用标准的R1CS或其他电路表示形式，方便后续处理。

复杂电路示例: 检查一个数是否是素数:

这个例子会更复杂，需要更多的constraints

输入: 需要检查的数字 n
目标: 证明Prover 知道 n 的所有因子(除了1和它自己)
电路:
- 循环遍历从 2 到 sqrt(n) 的所有数字 i
- 检查 n % i == 0. 这可以转化为 n = i * q 其中 q 是另一个因子.
- 如果 n % i == 0 那么 i 就是一个因子.
- 如果没有找到因子，则 n 是素数.

R1CS Representation:
对于每一个可能的因子 i 我们需要表达 n = i * q 这个约束。

A = (i)
B = (q)
C = (n)

我们需要确保电路不会泄漏关于因子的任何信息。
如果 i 不是一个因子, 我们仍然需要计算 i * q，但是我们需要确保这个结果不等于 n.

代码 (伪代码):

def is_prime(n):
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            q = n // i
            # R1CS constraints:
            # A = (i)
            # B = (q)
            # C = (n)
            return False # or add these constraints to R1CS representation
    return True

这个例子展示了即使是很简单的计算，转换为电路也可能变得相当复杂。我们需要仔细地设计电路，以确保计算的正确性和效率。

Prover/Verifier交互：变魔术的时刻

有了算术电路，接下来就是Prover和Verifier的交互了。别担心，这部分更像变魔术，不需要你精通高等数学。

1. Setup阶段：

在这个阶段，一个可信第三方（或者多方计算）会生成一些公开的参数，这些参数是Prover和Verifier都需要使用的。这个过程非常重要，如果参数被泄露，整个系统的安全性就完蛋了。这个过程我们不做详细解释，因为涉及到复杂的数学原理。

2. Prover的工作：

Prover拿到公开参数和自己的秘密（witness），开始生成证明。这个过程涉及到多项式运算、椭圆曲线加密等技术。简单来说，Prover会将自己的秘密编码成一些特殊的“承诺”，然后利用这些承诺来证明自己知道这个秘密。

代码 (伪代码):

def generate_proof(circuit, witness, params):
  """
  生成证明。

  Args:
    circuit: 算术电路。
    witness: Prover的秘密。
    params: 公开参数。

  Returns:
    证明。
  """
  # 1. 计算所有中间变量的值
  assignments = circuit.evaluate(witness)

  # 2. 将变量分配编码成多项式
  polynomials = encode_assignments_as_polynomials(assignments)

  # 3. 对多项式进行加密和承诺
  commitments = commit_to_polynomials(polynomials, params)

  # 4. 生成零知识证明
  proof = create_zk_proof(commitments, params)

  return proof

3. Verifier的工作：

Verifier拿到证明和公开参数，开始验证证明的有效性。这个过程涉及到一些简单的数学运算，例如点乘、哈希等。Verifier会检查证明是否满足一定的条件，如果满足，就认为Prover确实知道这个秘密。

代码 (伪代码):

def verify_proof(proof, public_input, params):
  """
  验证证明。

  Args:
    proof: 证明。
    public_input: 公开输入。
    params: 公开参数。

  Returns:
    如果证明有效，返回 True，否则返回 False。
  """
  # 1. 从证明中提取承诺
  commitments = extract_commitments_from_proof(proof)

  # 2. 检查承诺是否满足一定的关系
  if not check_commitment_relations(commitments, public_input, params):
    return False

  # 3. 验证零知识性
  if not verify_zk_property(proof, params):
    return False

  return True

4. 交互流程：

整个交互流程可以用下图表示：

+----------+     Setup     +----------+
|  可信第三方  | ----------> | 公开参数 |
+----------+               +----------+
     ^                      |
     |                      |
     |                      |
+----------+     秘密     +----------+
|  Prover  | ----------> |  证明    | --> Verifier
+----------+               +----------+
                                  |
                                  | 验证
                                  V
                           +----------+
                           |  结果    |
                           +----------+

代码实战：用libsnark撸一个简单的ZK-SNARKs

光说不练假把式，咱们来用libsnark撸一个简单的ZK-SNARKs。libsnark是一个流行的C++库，提供了ZK-SNARKs的各种功能。

1. 安装libsnark：

这个过程比较复杂，涉及到编译、依赖等问题。请参考libsnark的官方文档进行安装。

2. 编写电路代码：

#include <iostream>
#include <libsnark/algebra/curves/mnt4/mnt4p.hpp>
#include <libsnark/zk_proof_systems/ppzksnark/ppzksnark.hpp>

using namespace libsnark;

int main() {
  // 1. 定义电路类型
  typedef mnt4p_ppzksnark_proving_key proving_key_t;
  typedef mnt4p_ppzksnark_verifying_key verifying_key_t;

  // 2. 定义电路
  protoboard<Fr<mnt4p_affine_weierstrass_curve>> pb;

  // 定义输入变量
  pb_variable<Fr<mnt4p_affine_weierstrass_curve>> x(pb, "x");
  pb_variable<Fr<mnt4p_affine_weierstrass_curve>> y(pb, "y");
  pb_variable<Fr<mnt4p_affine_weierstrass_curve>> out(pb, "out");

  // 定义约束：x * x + 5 == y
  pb.add_constraint(equality_constraint<Fr<mnt4p_affine_weierstrass_curve>>(x * x + 5, y));

  // 3. 生成密钥
  auto keypair = ppzksnark_generator<mnt4p_affine_weierstrass_curve>(pb.get_constraint_system());

  // 4. 设置输入值
  Fr<mnt4p_affine_weierstrass_curve> x_val = 5;
  Fr<mnt4p_affine_weierstrass_curve> y_val = x_val * x_val + 5;

  pb.val(x) = x_val;
  pb.val(y) = y_val;
  pb.val(out) = 0; // Dummy value

  // 5. 生成证明
  auto proof = ppzksnark_prover<mnt4p_affine_weierstrass_curve>(keypair.pk, pb.primary_input(), pb.auxiliary_input());

  // 6. 验证证明
  bool verified = ppzksnark_verifier<mnt4p_affine_weierstrass_curve>(keypair.vk, pb.primary_input(), proof);

  std::cout << "Verification status: " << verified << std::endl;

  return 0;
}

3. 编译代码：

使用g++或其他C++编译器编译代码。

4. 运行代码：

运行编译后的程序，你会看到输出结果：Verification status: 1，表示证明验证成功！

代码解释：

libsnark/algebra/curves/mnt4/mnt4p.hpp: 包含了椭圆曲线的定义。
libsnark/zk_proof_systems/ppzksnark/ppzksnark.hpp: 包含了PPZK-SNARKs的实现。
protoboard: 用于定义算术电路。
pb_variable: 用于定义电路中的变量。
equality_constraint: 用于定义约束。
ppzksnark_generator: 用于生成密钥。
ppzksnark_prover: 用于生成证明。
ppzksnark_verifier: 用于验证证明。

总结：

今天咱们一起学习了ZK-SNARKs的电路设计和Prover/Verifier交互。虽然内容比较复杂，但希望通过人话+代码的方式，让你对ZK-SNARKs不再感到陌生。

记住：

电路设计是核心： 将计算转换成高效的算术电路是关键。
R1CS是常用的电路表示形式： 理解R1CS有助于你更好地设计电路。
Prover/Verifier交互是魔术： 了解交互流程，可以更好地理解ZK-SNARKs的工作原理。
代码实战是王道： 动手写代码，才能真正掌握ZK-SNARKs。

希望今天的讲座对你有所帮助！下次有机会再一起探索更深入的ZKP知识！现在，去用你新学到的知识，震惊你的朋友们吧！祝大家编程愉快，生活顺利！

大家好，欢迎来到“ZKP：别再懵圈了，咱们一起撸代码！”讲座！

啥是ZK-SNARKs？为啥它这么火？

电路设计：把计算变成线路图

Prover/Verifier交互：变魔术的时刻

代码实战：用libsnark撸一个简单的ZK-SNARKs

总结：

发表回复 取消回复

发表回复取消回复