知识库 / 零知识证明基础：从 Sigma 协议到 zk-SNARK

零知识证明基础：从 Sigma 协议到 zk-SNARK

密码学概念 · 2026-06-03

概述

零知识证明（Zero-Knowledge Proof, ZKP）是密码学中最优雅的概念之一。它由 Goldwasser、Micali 和 Rackoff 在 1985 年提出，核心思想是：

证明者（Prover）可以在不泄露任何秘密信息的前提下，让验证者（Verifier）相信某个陈述为真。
一个经典的类比：你想向朋友证明你知道一个迷宫的出口路径，但不想让他知道具体路径。你可以让迷宫外的人随机指定入口，你从出口走出来——重复多次后，他相信你确实知道路径，但仍然不知道路径是什么。

零知识证明的三个核心性质：

  • 完备性（Completeness）：如果陈述为真，诚实的证明者总能说服诚实的验证者
  • 可靠性（Soundness）：如果陈述为假，欺骗性的证明者无法说服诚实的验证者（概率可忽略）
  • 零知识性（Zero-Knowledge）：验证者除了知道陈述为真外，不获得任何额外信息

交互式零知识证明

基本框架

交互式零知识证明由多轮"挑战-响应"组成：

CODE
证明者 P（知道秘密 x）          验证者 V
        |                           |
        |--- 承诺（Commitment） --->|
        |                           |
        |<--- 挑战（Challenge） ----|
        |                           |
        |--- 响应（Response） ----->|
        |                           |
        |<--- 接受/拒绝 -----------|

每一轮中：

  • 证明者发送一个承诺（隐藏了秘密的随机值）
  • 验证者发送一个随机挑战
  • 证明者根据秘密和承诺计算响应
  • 验证者检查响应是否合法

示例：离散对数的零知识证明

假设证明者知道 x 使得 g^x ≡ y (mod p)，想向验证者证明这一点而不泄露 x。

协议流程：

  • 承诺：证明者选择随机数 r，发送 t = g^r mod p
  • 挑战：验证者发送随机数 c
  • 响应：证明者发送 s = r + c·x mod (p-1)
  • 验证：验证者检查 g^s ≡ t · y^c (mod p)
正确性验证：

CODE
g^s = g^(r+cx) = g^r · g^(cx) = t · (g^x)^c = t · y^c  ✓

零知识性：验证者看到的 (t, c, s) 中，t 是随机的，s 也是随机的（因为 r 是随机的），所以验证者无法从中提取 x 的任何信息。

Sigma 协议

定义

Sigma 协议（Σ-protocol）是最基本的零知识证明协议框架，因流程形状类似希腊字母 Σ 而得名。它是一个三步协议：

CODE
P                              V
|                              |
|--- a（第一消息/承诺） ------->|
|                              |
|<--- e（挑战，随机） ---------|
|                              |
|--- z（响应） --------------->|
|                              |
|        验证 (a, e, z)        |

形式化性质

Sigma 协议需要满足：

  • 特殊可靠性（Special Soundness）：给定同一个承诺 a 下的两个不同挑战 e ≠ e' 及其有效响应 z, z'，可以高效提取出秘密（见证）
  • 特殊诚实验证者零知识（Special HVZK）：存在一个模拟器，给定挑战 e，可以生成不可接受的 (a, e, z) 三元组

Schnorr 协议

Schnorr 协议是最著名的 Sigma 协议实例，用于证明离散对数的知识：

公共参数：循环群 G，生成元 g，阶 q 陈述：y = g^x（证明者知道 x）

CODE
1. P 选择随机 r ∈ Z_q，发送 a = g^r
2. V 选择随机挑战 e ∈ Z_q
3. P 发送 z = r + e·x mod q
4. V 验证 g^z = a · y^e

特殊可靠性证明：

如果有两对 (e, z) 和 (e', z') 都通过验证：

CODE
g^z = a · y^e
g^z' = a · y^e'

g^(z-z') = y^(e-e') = g^(x(e-e'))

z - z' = x(e - e') mod q

x = (z - z') · (e - e')^(-1) mod q

这说明从两个不同的挑战-响应对中可以提取出秘密 x。

Fiat-Shamir 变换：从交互式到非交互式

动机

交互式协议需要证明者和验证者同时在线，且每轮都需要新鲜随机数。这在很多实际场景中不现实（如区块链、数字证书）。

变换方法

Fiat-Shamir 变换（1986）将交互式 Sigma 协议转换为非交互式零知识证明（NIZK）：

核心思想：用哈希函数替代验证者的随机挑战。

CODE
交互式：                   非交互式：
V 发送随机 e      →       e = H(a || 陈述 || 公共参数)

Schnorr 签名的推导：

将 Schnorr 协议应用 Fiat-Shamir 变换：

CODE
1. 选择随机 r，计算 a = g^r
2. 计算挑战 e = H(a || m)    （m 是消息）
3. 计算响应 z = r + e·x
4. 签名 σ = (e, z)

验证时：

CODE
计算 a' = g^z · y^(-e)
检查 e = H(a' || m)

这正是 Schnorr 签名方案！这说明 Schnorr 签名本质上是"用私钥对消息的零知识证明"。

安全性

Fiat-Shamir 变换在随机预言模型（ROM）下是安全的，即假设哈希函数 H 是真正的随机函数。

非交互式零知识证明（NIZK）

定义

NIZK 允许证明者生成一个单一的证明字符串 π，验证者可以独立验证，无需任何交互。

形式化定义：

一个 NIZK 系统由三个算法组成：

  • Setup(1^λ) → crs：生成公共参考串（Common Reference String）
  • Prove(crs, x, w) → π：证明者用见证 w 生成证明 π
  • Verify(crs, x, π) → {0, 1}：验证者验证证明
其中 x 是陈述，w 是见证（秘密）。

公共参考串模型

大多数 NIZK 系统需要 CRS，这引入了一个信任假设：CRS 的生成者不能知道"有毒废物"（toxic waste）——即用于模拟的陷门信息。

多方计算（MPC）仪式：为了降低信任假设，可以使用多方计算来生成 CRS。只要有一个参与者是诚实的，CRS 就是安全的。Zcash 的"可信设置仪式"就是这种方法的典型应用。

zk-SNARK：简洁非交互式零知识证明

定义

zk-SNARK（Zero-Knowledge Succinct Non-interactive ARgument of Knowledge）是目前最高效的零知识证明系统：

  • Zero-Knowledge：不泄露任何秘密信息
  • Succinct：证明大小极小（通常几百字节），验证时间极快（毫秒级）
  • Non-Interactive：单次通信
  • Argument of Knowledge：计算可靠性（对计算能力有限的证明者可靠）

核心思想

zk-SNARK 的构造基于以下技术栈：

CODE
算术电路 → R1CS → QAP → 多项式承诺 → 配对友好椭圆曲线

步骤 1：算术电路

将计算问题转化为算术电路（加法门和乘法门）。

例如，证明知道 x 使得 x³ + x + 5 = 35：

CODE
v1 = x * x        (x²)
v2 = v1 * x       (x³)
v3 = v2 + x       (x³ + x)
out = v3 + 5      (x³ + x + 5)

步骤 2：R1CS（Rank-1 Constraint System）

将电路转化为一系列约束：

CODE
(a₁ · s) · (b₁ · s) = (c₁ · s)
(a₂ · s) · (b₂ · s) = (c₂ · s)
...

其中 s 是变量向量，a_i, b_i, c_i 是系数向量。

步骤 3：QAP（Quadratic Arithmetic Program）

将 R1CS 转化为多项式形式：

CODE
A(x) · B(x) - C(x) = H(x) · Z(x)

其中 Z(x) 是目标多项式。如果约束满足，则 A(x)·B(x) - C(x) 能被 Z(x) 整除。

步骤 4：多项式承诺

证明者承诺于多项式 A(x), B(x), C(x)，而不泄露多项式本身。使用KZG 承诺（Kate-Zaverucha-Goldberg）或FRI 承诺（Fast Reed-Solomon Interactive Oracle Proof）。

步骤 5：椭圆曲线配对

使用配对友好椭圆曲线（如 BN128、BLS12-381）实现高效验证：

CODE
e(g^a, g^b) = e(g, g)^(ab)

配对允许验证者在不知道秘密值的情况下检查多项式等式。

性能特征

证明系统证明大小验证时间证明时间可信设置
Groth16~200 B~1.5 ms~3-10 s需要
PLONK~400 B~3 ms~5-15 s通用设置
STARK~50 KB~10 ms~1-5 s不需要

国密场景的适配

在国密体系中，zk-SNARK 可以进行以下适配：

  • 椭圆曲线替换：将 BN128/BLS12-381 替换为 SM2 曲线（但 SM2 曲线不支持高效配对，需要寻找配对友好的国密曲线）
  • 哈希函数替换：将 SHA-256/Poseidon 替换为 SM3
  • 多项式承诺：FRI 承诺不依赖椭圆曲线配对，更适合国密场景
目前，国密适配的零知识证明系统仍在研究阶段，主要挑战是 SM2 曲线不支持高效的配对运算。

零知识证明的应用

1. 区块链与加密货币

  • Zcash：使用 zk-SNARK 实现完全匿名的加密货币交易
  • 以太坊 Layer 2：zk-Rollup 使用 zk-SNARK/STARK 将大量交易压缩为单个证明
  • Filecoin：使用 zk-SNARK 证明存储的正确性

2. 身份认证

  • 匿名凭证：证明你满足某些属性（如年龄 > 18）而不泄露具体信息
  • 去中心化身份（DID）：使用零知识证明验证身份声明

3. 隐私计算

  • 安全多方计算（MPC）：零知识证明用于验证各方计算的正确性
  • 联邦学习：证明模型更新符合预期而不泄露训练数据
  • 隐私保护数据库查询：证明查询结果的正确性而不泄露查询条件

4. 合规与审计

  • 监管合规：证明交易符合监管要求而不泄露交易细节
  • 审计证明：证明财务报表的正确性而不泄露具体数据

常见误区

误区 1：零知识证明 = 完全匿名

零知识证明保护的是证明过程中的信息泄露，但不一定保证端到端的匿名性。例如，在区块链中，交易的发送者和接收者地址仍然是公开的，零知识证明只是隐藏了交易金额。

误区 2：zk-SNARK 总是最好的选择

zk-SNARK 虽然高效，但需要可信设置。如果可信设置被破坏，整个系统的安全性将崩溃。在某些场景中，STARK（无需可信设置）或 Bulletproofs（无需可信设置，证明更小）可能是更好的选择。

误区 3：零知识证明可以证明任何陈述

零知识证明只能证明NP 类问题（可以在多项式时间内验证的问题）。对于 NP 完全问题，需要先将问题转化为合适的电路形式。

总结

零知识证明从理论概念到实际应用经历了近 40 年的发展：

  • 1985 年：Goldwasser、Micali、Rackoff 提出零知识证明概念
  • 1986 年：Fiat-Shamir 变换实现非交互式证明
  • 2012 年：GGPR13 论文奠定 zk-SNARK 的理论基础
  • 2016 年：Groth16 提出最高效的 zk-SNARK 构造
  • 2018 年：Zcash 实现大规模部署
  • 2020 年至今：zk-Rollup 成为区块链扩容的主流方案
零知识证明正在从密码学理论走向工程实践，成为隐私计算和区块链领域的核心技术。在国密体系中，零知识证明的适配仍面临配对友好曲线缺失等挑战，但随着研究的深入，国密版的零知识证明系统有望在未来几年内实现。

参考来源

  • Goldwasser S, Micali S, Rackoff C. "The Knowledge Complexity of Interactive Proof Systems." SIAM Journal on Computing, 1989.
  • Fiat A, Shamir A. "How to Prove Yourself: Practical Solutions to Identification and Signature Problems." CRYPTO 1986.
  • Groth J. "On the Size of Pairing-based Non-interactive Arguments." EUROCRYPT 2016.
  • Ben-Sasson E, Bentov I, Horesh Y, Riabzev M. "Scalable, transparent, and post-quantum secure computational integrity." IACR Cryptology ePrint Archive, 2018.
  • Bünz B, Bootle J, Boneh D, et al. "Bulletproofs: Short Proofs for Confidential Transactions and More." S&P 2018.
  • Gabizon A, Williamson ZJ, Ciobotaru O. "PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge." IACR Cryptology ePrint Archive, 2019.

相关实践

← 返回知识库