🔐 Schnorr协议演示

交互式零知识证明 - 离散对数协议

📚 协议说明

Schnorr协议用于证明：Prover知道离散对数x（即知道x使得 y = gx mod p），但不泄露x的值。


协议流程：

💡 为什么选择原根？使用原根（q = p-1）时，g 能生成所有 Zp* 的元素，使得离散对数问题定义在整个乘法群上，协议的安全性基础更加稳固。

✅ 协议性质论证

1. 完备性（Completeness）

如果Prover确实知道x（即诚实的Prover），那么验证总是能通过。
证明：
• Verifier验证：gs ≟ t × yc (mod p)
• 因为 s = (r + c×x) mod q，其中 q = ordp(g) 是 g 的阶（满足 gq ≡ 1 (mod p)）
• 根据群论，对于阶为 q 的元素 g，指数运算在模 q 下是等价的
• 左边：gs = g(r + c×x) mod q = gr + c×x = gr × gc×x = gr × (gx)c (mod p)
• 右边：t × yc = gr × yc = gr × (gx)c (mod p)
• 两边相等 ✓
结论：诚实的Prover总能让验证通过。

2. 可靠性（Soundness）

如果Prover不知道x，那么Prover只能以很小的概率通过验证。
分析：
• Prover在不知道x的情况下，必须在发送承诺t之前"猜测"Verifier会发送什么挑战c
• 如果猜对了（概率1/C，C为挑战空间大小），可以构造合适的响应通过验证
• 如果猜错了，无法为不同的挑战值生成正确的响应
• 单轮成功作弊概率 ≤ 1/C
• 经过k轮交互，作弊成功概率 ≤ (1/C)k
结论：不知道x的Prover几乎不可能通过多轮验证（例如C=100, k=3时，作弊概率 < 0.0001%）。

💡 关键要点：完备性保证诚实的Prover能证明真实的陈述；可靠性保证撒谎的Prover无法证明虚假的陈述。这两个性质共同确保了零知识证明系统的正确性。

步骤1: 生成系统参数

🔑 关于原根（Primitive Root）

什么是阶？元素 g 在模 p 下的阶 q 是满足 gq ≡ 1 (mod p) 的最小正整数。
什么是原根？如果 g 的阶等于 p-1（即 q = φ(p) = p-1），则 g 是模 p 的原根。原根能生成整个乘法群 Zp* 的所有 p-1 个元素。
为什么使用原根？

  • 所有元素都可以表示为 gk 的形式（k = 0, 1, ..., p-2）
  • 使协议的数学结构更清晰：q = p-1
  • 对于素数 p，原根一定存在（欧拉定理）
为什么模 q：因为 gq ≡ 1 (mod p)，所以 ga = ga mod q，这保证了所有指数运算在模 q 下的正确性。

步骤2: 生成秘密x和公开值y

步骤3: 执行零知识证明协议

进行多轮交互以增强可靠性（每轮成功概率1/C，k轮成功概率 1 - 1/Ck）

步骤4: 零知识性质分析 - 真实协议View分布

🔍 理解零知识

零知识性质意味着：Verifier从交互中获得的信息（view）可以被模拟出来，无需知道秘密x。

真实协议中的View = <t, c, s>，其中：

  • t = gr mod p（承诺值）
  • c ∈ {0, 1, ..., C-1}（挑战值）
  • s = (r + c × x) mod q（响应值，在模 q 下）

下面的表格展示真实协议中所有可能的view及其概率分布。

步骤5: 零知识性质分析 - 模拟器View分布

🎭 模拟器（Simulator）

模拟器在不知道秘密x的情况下，也能生成与真实协议相同分布的view，这证明了零知识性质。

模拟器生成View的方法：

  • 1. 随机选择 c ∈ {0, 1, ..., C-1}（挑战值）
  • 2. 随机选择 s ∈ Zq（响应值，在模 q 下）
  • 3. 反向计算 t = gs × y-c mod p（承诺值）

注意：模拟器不需要知道x，就能生成看起来"真实"的view！

步骤6: 自定义知识度量函数对比

📊 知识度量测试

定义一个函数来"度量"每个view包含的"知识"。如果协议是零知识的，那么无论使用什么度量函数，真实协议和模拟器在该度量下的平均值应该相同。

函数签名： function measure(t, c, s) { return 数值; }

函数接收view的三个组成部分(t, c, s)，返回一个数值作为"知识度量"。

示例函数（点击使用）：