Σ 舞步：承诺、挑战、响应

有没有想过 Σ-protocol 是什么？

有趣的事实：“Sigma”这个名字来源于希腊字母 Σ，它看起来有点像锯齿形，就像这个协议执行的三步过程 😊

Sigma 可能是最基本的 “零知识知识证明” 😁 协议：证明你知道一些秘密，但不泄露秘密本身。

你，证明者，知道一些满足关系式的私有值，并希望使验证者相信这是真的，而不泄露 x。

Sigma 舞步三部曲

1. 承诺（Commitment）： 证明者向验证者发送初始承诺

2. 挑战（Challenge）： 验证者回复一个随机挑战

3. 响应（Response）： 证明者使用秘密和挑战来回答

从响应中，验证者确信证明者一定知道一个满足关系式的有效证人(witness)，而无需看到它。

稍后，我们将看到如何使用 Fiat-Shamir 使步骤 2 变为非交互式的。

符号

密码学家经常使用乘法符号（例如 $g^x \cdot h^r$）来书写，但由于大多数实际实现都使用椭圆曲线，因此我将使用加法符号（$x \cdot G + r \cdot H$）。

相同的数学，不同的风格。

在本文中，我们将使用：

• G：椭圆曲线生成器
• H：另一个独立的生成器

Schnorr 协议

Schnorr 协议是 Σ-protocol 最简单的例子，是零知识证明的 “hello world” 😉

设置如下：

你，证明者，想要证明你知道一个证人 $x$，使得

$Y = x \cdot G$

其中 $x$ 是一个标量，因此 $Y$ 是一个公共曲线点。

在实践中，这就像证明你知道与公钥 Y 对应的私钥 x。

一步一步：

1. 承诺

你选择一个随机标量 $r$，并将一个承诺 $T$ 发送到该随机数

$T = r \cdot G$

2. 挑战

验证者发回一个随机挑战 $c$，一个随机的标量（域中的一个数字，而不是一个椭圆曲线点）。

3. 响应

你用

$s = r + c \cdot x$

最后，验证者检查

$s \cdot G =? T + c \cdot Y$

如果成立则接受。

为什么它有效？

让我们代入一下：

$s \cdot G = T + c \cdot Y = (r + x \cdot c) \cdot G = r \cdot G + c \cdot x \cdot G = T + c \cdot Y$

因此，如果验证者的检查通过，则表示你一定知道正确的 $x$。

与此同时，$r$ 保持 $x$ 隐藏，记录揭示了关于它的任何信息。

让我们看看使用 SageMath 的整个过程。

我们将使用一个小型玩具椭圆曲线来保持数字的可管理性，但其逻辑与现实世界的密码学相同。

p = 929
Fp = GF(p)
E = EllipticCurve(Fp, [5, 15])
G = E.gens()[0]
Fr = GF(G.order())

现在让我们逐步完成 Schnorr Sigma 协议：

x = Fr(123)
Y = x * G

r = Fr.random_element()
T = r * G

print("Sending commitment T to the verifier")

print("challenge should be computed as: c = hash(G, Y, T)")
c = Fr.random_element()

s = r + c * x

print("Sending s to the verifier")
assert s * G == T + c * Y
print("Proof is valid")

证人提取 (又名 可靠性)

那么，我们如何知道证明者真的知道证人 $x$ 呢？

这就是知识可靠性的用武之地：这意味着如果有人可以成功地说服验证者两次（使用相同的承诺），那么我们可以从这两个运行中提取证人。

以下是它在 Schnorr 协议中的工作方式：

我们知道承诺是

$T = r \cdot G$

并且对于具有相同 $r$ 但挑战 $c$ 和 $c'$ 不同的两个成功记录，我们得到：

$s = r + x \cdot c$ $s' = r + x \cdot c'$

如果我们减去这两个方程式，则随机数 $r$ 消失：

$s - s' = (c - c') \cdot x$

由此我们可以恢复证人：

$x = \frac{s - s'}{c - c'}$

就是这样：证人提取！

此属性称为特殊可靠性，它是 Σ-protocol 的定义特征之一。

它保证了没有人可以在不实际知道 $x$ 的情况下“伪造”证明。 换句话说：如果你可以使用相同的承诺来响应两个不同的挑战，那么你必须知道证人。

H = E.random_point()

## known commitment
v = Fr(123)
r = Fr.random_element()
print(f"v: {v}, r: {r}")
C = v * G + r * H

v_prime = Fr.random_element()
r_prime = Fr.random_element()
A = v_prime * G + r_prime * H

print("Sending commitments C and A to verifier")

print("challenge should be computed as: hash(G, H, C, A)")
c = Fr.random_element()

s1 = v_prime + c * v
s2 = r_prime + c * r

print("Sending (c, s1, s2) to the verifier")
assert s1 * G + s2 * H == A + c * C
print("Proof is valid")

c_prime = Fr.random_element()
s1_prime = v_prime + c_prime * v
s2_prime = r_prime + c_prime * r

print("Sending (c_prime, s1_prime, s2_prime) to the verifier")
assert s1_prime * G + s2_prime * H == A + c_prime * C
print("Proof is valid")

print("\nLet's try to recover v and r")
assert s1_prime * G + s2_prime * H - c_prime * C == s1 * G + s2 * H - c * C
assert (s1_prime - s1) * G + (s2_prime - s2) * H + (c - c_prime) * C == 0

## s1 G + s2 H + cv G + cr H = 0
## (s1 + cv) G + (s2 + cr) H = 0
## so we have:
## . s1_prime - s1 + (c - c_prime) * v = 0 -> v = (s1 - s1_prime) / (c - c_prime)
## . s2_prime - s2 + (c - c_prime) * r = 0 -> r = (s2 - s2_prime) / (c - c_prime)

print("\nRecovered v and r:")
recovered_v = (s1 - s1_prime) / (c - c_prime)
recovered_r = (s2 - s2_prime) / (c - c_prime)
print(f"recovered_v: {recovered_v}, recovered_r: {recovered_r}")
assert recovered_v == v
assert recovered_r == r

组合 Σ-proof

现在我们已经掌握了基础知识，我们可以开始做一些有趣的事情：组合 Sigma 证明！ 🥳

相等证明：两个值共享相同的秘密

假设你有一个秘密 $x$，以及两个公共值 $Y$ 和 $Z$：

$Y = x \cdot G$ $Z = x \cdot H$

你的目标：使验证者相信 $Y$ 和 $Z$ 都来自相同的秘密 $x$，你是该秘密的拥有者。

1. 承诺

选择一个随机数 $r$：

$T_g = r \cdot G$ $T_h = r \cdot H$

2. 挑战

验证者发送一个随机挑战 $c$

3. 响应

$s = r + c \cdot x$

4. 验证

$s \cdot G =? T_g + c \cdot Y$ $s \cdot H =? T_h + c \cdot Z$

如果两个等式都成立，那么你已经成功证明了相同的秘密 $x$ 被用于两个公共值中，而没有泄露它。

AND 证明：你知道两个秘密

现在让我们说有两个独立的秘密 $a$ 和 $b$：

$Y = a \cdot G$ $Z = b \cdot H$

你想证明你知道这两个秘密。

选择一个随机数 $r$，然后发送：

$T_g = r \cdot G$ $T_h = r \cdot H$

接收 $c$ 并发送最终响应：

$s_a = r + c \cdot a$ $s_b = r + c \cdot b$

验证者检查

$s_a \cdot G =? T_g + c \cdot Y$ $s_b \cdot H =? T_h + c \cdot Z$

如果两个检查都通过，那么你已经证明你同时知道 $a$ 和 $b$。

OR 证明：你知道两个秘密之一

这个有点棘手，但更有趣！

我们有相同的设置：

$Y = a \cdot G$ $Z = b \cdot H$

但现在你只知道其中一个秘密（比如 $a$），并且你想证明你知道 a 或 b，而不透露是哪个。

你怎么做到的？

这个想法很聪明：我们将并行运行两个证明，每个关系式一个，但我们将模拟其中一个（我们不知道的那个）。

为了使模拟与实际证明无法区分，我们将使用两个挑战 $c_1$ 和 $c_2$，由证明者选择。

唯一的规则：它们加起来必须等于验证者的挑战 $c$：

$c_1 + c_2 = c$

这确保了整个证明仍然符合 Σ-protocol 结构：验证者只发送一个挑战，但在内部它在两个子证明之间“拆分”。

这是诀窍：

• 对于你不知道的秘密，你将伪造一个看起来有效的虚假记录。
• 对于你知道的秘密，你将使用 $a$ 和验证者的挑战 $c$ 诚实地计算响应。

这样，验证者会看到两个看起来有效的证明，但无法判断哪个是被模拟的。

1. 承诺

像往常一样，选择一个随机数 $r$ 并计算：

$T_1 = r \cdot G$

对于你_不知道_的秘密（这里是 $b$）：

• 选择随机值 $s_2$ 和 $c_2$
• 以强制最终检查通过的方式计算相应的承诺：

$T_2 = s_2 \cdot H - c_2 \cdot Z$

将两个承诺（$T_1$, $T_2$）发送给验证者。

请注意，$T_2$ 仅使用公共点 $Z$，而不使用秘密标量 $b$，因为我们不知道它。

2. 挑战

现在，验证者发送一个挑战 $c$

3. 响应

我们不会直接使用 $c$，而是将其拆分：

$c_1 = c - c_2$

然后计算你所知道的一方的真实响应：

$s_1 = r + c_1 \cdot a$

请记住，我们已经有了 $s_2$，之前是随机生成的。

发送 ($s_1, s_2, c_1, c_2$) 作为你的响应。

4. 验证

$s_1 \cdot G =? T_1 + c_1 \cdot Y$ $s_2 \cdot H =? T_2 + c_2 \cdot Z$ $c =? c_1 + c_2$

为什么它有效

• 第一个等式是你所知道的秘密（$a$）的真实 Σ-proof
• 第二个等式是假的，但仍然是一致的，因为你构建了 $T_2$，因此它通过了你选择的 $s_2$, $c_2$ 的检查
• 验证者无法分辨哪个部分是被模拟的

所以验证者只学到了一件事：你知道 a 或 b， 仅此而已。

这是一个 OR 证明，是许多 ZK 系统中 “选择性披露” 的基础。

现在让我们看看 Sigma 协议如何与 Pedersen 承诺 一起工作。

H = E.random_point()

## known commitment
x = Fr(123)
P1 = x * G

## unknown commitment
P2 = E.random_point()

print("Sending P1 and P2 to the verifier")

r = Fr.random_element()
T1 = r * G

c2 = Fr.random_element()
s2 = Fr.random_element()
T2 = s2 * H - c2 * P2

print("Sending T1 and T2 to the verifier")
print("Verifier sends challenge c")
c = Fr.random_element()

c1 = c - c2

s1 = r + c1 * x

print("Sending (c1, s1, s2) to the verifier")
assert s1 * G == T1 + c1 * P1
assert s2 * H == T2 + c2 * P2
assert c1 + c2 == c
print("Proof is valid")

Pedersen 承诺

Pedersen 承诺在零知识证明中随处可见。 它们简单、强大，并且像密码保险库一样隐藏秘密。

$P = x \cdot G + r \cdot H$

其中：

• $x$ 是你承诺的证人
• $r$ 是一个随机的致盲因子
• $G$ 和 $H$，你已经知道了

由于随机数 $r$，Pedersen 承诺是隐藏的，没有人可以从 $P$ 中猜出 $x$，并且是绑定的，一旦你发布了 $P$，你就不能再改变你对 $x$ 的想法了（除非你能解决离散对数问题）。

加法 ➕ 魔术

Pedersen 承诺也是加法同态的，这意味着承诺会很好地加起来：

$P_1 = x_1 \cdot G + r_1 \cdot H$ $P_2 = x_2 \cdot G + r_2 \cdot H$ $P_1 + P_2 = (x_1 + x_2) \cdot G + (r_1 + r_2) \cdot H$

换句话说，添加两个承诺会给你一个对底层值之和的承诺。

此属性使 Pedersen 承诺在更大的 ZK 系统中非常灵活。

要打开承诺，你只需显示 $x$ 和 $r$。

Pedersen + Σ

现在事情变得有趣了。

假设有一个公共 Pedersen 承诺 $P$，其中隐藏了你的私钥 $x$。

有人 आपसे 要求证明你确实知道 $x$，但当然，你不想泄露它。 如果你只是发送你的密钥，那将适得其反！

因此，相反，你使用 Σ -protocol 来证明对承诺的 opening 的了解。

证明对 opening (x,r) 的了解

这是它的工作原理：

1. 承诺

选择随机值 $r_x$ 和 $r_r$，然后发送：

$T = r_x \cdot G + r_r \cdot H$

2. 挑战：验证者选择一个随机挑战 $c$

3. 响应：

计算你的响应：

$s_x = r_x + c \cdot x$ $s_r = r_r + c \cdot r$

4. 验证

验证者检查：

$s_x \cdot G + s_r \cdot H =? T + c \cdot P$

如果这成立，他相信你知道证人（$x$, $r$），而无需透露它们。

H = E.random_point()

x = Fr(123)
r = Fr.random_element()
C = x * G + r * H

print("Sending commitment C to verifier")

r1 = Fr.random_element()
r2 = Fr.random_element()
T = r1 * G + r2 * H

print("Sending T to the verifier")

print("challenge should be computed as: c = hash(G, H, C, T)")
c = Fr.random_element()

s1 = r1 + c * x
s2 = r2 + c * r

print("Sending (s1, s2) to the verifier")
assert s1 * G + s2 * H == T + c * C
print("Proof is valid")

将证明与 Pedersen 承诺相结合

就像我们之前根据椭圆曲线点组合 Sigma 证明一样，我们可以在使用 Pedersen 承诺时做同样的事情。

这次我们会快一点。 模式是相同的，只是有更多的移动部件。

两个承诺，一个秘密

假设我们有两个 Pedersen 承诺，它们都应该隐藏相同的秘密值 $x$。

我们想要证明这是真的，并且我们实际上知道 $x$。

为了清楚起见：

• $b_1$, $b_2$ 将是每个承诺中的致盲因子
• $r$ 值是 Σ 协议本身使用的随机数

这两个承诺是：

$P_1 = x \cdot G + b_1 \cdot H$ $P_2 = x \cdot G + b_2 \cdot H$

选择三个随机值 $rx$, $r{b1}$, $r_{b2}$，然后发送：

$T_1 = rx \cdot G + r{b1} \cdot H$ $T_2 = rx \cdot G + r{b2} \cdot H$

我们从验证者那里收到挑战 $c$，并发送响应：

$s_1 = r_x + c \cdot x$ $s2 = r{b1} + c \cdot b_1$ $s3 = r{b2} + c \cdot b_2$

验证者检查

$s_1 \cdot G + s_2 \cdot H =? T_1 + c \cdot P_1$ $s_1 \cdot G + s_3 \cdot H =? T_2 + c \cdot P_2$

H = E.random_point()

print("Here we prove that the same value is encoded in 2 Pedersen commitments")

x = Fr(123)
b1 = Fr.random_element()
b2 = Fr.random_element()
P1 = x * G + b1 * H
P2 = x * G + b2 * H

print("Sending commitments P1 and P2 to the verifier")

r_x = Fr.random_element()
r_b1 = Fr.random_element()
r_b2 = Fr.random_element()

T1 = r_x * G + r_b1 * H
T2 = r_x * G + r_b2 * H

print("Sending T1 and T2 to the verifier")

print("challenge should be computed as: hash(G, H, P1, P2, T1, T2)")
c = Fr.random_element()

s1 = r_x + c * x
s2 = r_b1 + c * b1
s3 = r_b2 + c * b2

print("Sending (c, s1, s2) to the verifier")
assert s1 * G + s2 * H == T1 + c * P1
assert s1 * G + s3 * H == T2 + c * P2
print("Proof is valid")

就像以前一样，你也可以在 Pedersen 承诺之上构建 AND 或 OR 证明，证明你知道两个 opening，或者你知道至少一个承诺的 opening。

作为礼物，这里是 Pedersen OR 证明的代码：

H = E.random_point()

## known commitment
x = Fr(123)
blinding = Fr.random_element()
P1 = x * G + blinding * H

## unknown commitment
P2 = E.random_point()

print("Sending P1 and P2 to the verifier")

r_x = Fr.random_element()
r_r = Fr.random_element()
T1 = r_x * G + r_r * H

c2 = Fr.random_element()
s2_x = Fr.random_element()
s2_r = Fr.random_element()
T2 = s2_x * G + s2_r * H - c2 * P2

print("Sending T1 and T2 to the verifier")
print("Verifier sends challenge c")
c = Fr.random_element()

c1 = c - c2

s1_x = r_x + c1 * x
s1_r = r_r + c1 * blinding

print("Sending (c1, s1_x, s1_r), (c2, s2_x, s2_r) to the verifier")
assert s1_x * G + s1_r * H == T1 + c1 * P1
assert s2_x * G + s2_r * H == T2 + c2 * P2
assert c1 + c2 == c
print("Proof is valid")

Fiat-Shamir：使其成为非交互式的

到目前为止，我们所有的协议都是交互式的。 证明者需要在承诺某些值之后从验证者那里收到随机挑战。

但在许多现实世界的设置中（例如数字签名或区块链证明），没有实时的验证者。

这就是 Fiat-Shamir 可以发挥作用的地方。

我们计算它，而不是让验证者发送 $c$，而是使用哈希函数确定性地计算它。

$c = H(\text{transcript})$

哈希充当验证者的角色：它生成一个在承诺之前不可预测，但在承诺之后是确定性的挑战。

但我们必须非常小心将什么内容放入记录中。

• 如果你忘记了某些内容，则证明者可以在看到挑战后更改其承诺
• 如果你包含太多内容，例如私有数据，则验证者将无法重新计算哈希并验证证明

哈希中包含什么？

通常，记录应包括：

• 协议的公共参数：$G$ 和 $H$
• 公共输入（例如 Pedersen 承诺 $P$）
• 证明者的初始承诺 $t$
• 可选的域分隔符，以避免跨协议冲突

这些确保了挑战 $c$ 绑定到正确的上下文，并且无法提前预测。

不可预测的挑战

为什么证明者无法预测挑战至关重要？

如果证明者可以在选择 $t$ 之前猜出挑战 $c$，那么他可以伪造有效的证明，而无需实际知道秘密 $x$。

让我们看看如何：

证明者生成一个随机 $s$（通常在步骤 3 中发送的值），并计算：

$T = s \cdot G - c \cdot Y$

验证者无法区分正确构造的 ($T$, $s$) 和 “伪造” 的 ($T$, $s$)。

验证者检查：

$T + c \cdot Y =? s \cdot G$

它完美地成立：

$T + c \cdot Y = (s \cdot G - c \cdot Y) + c \cdot Y = s \cdot G$

Boom 💥 验证者被愚弄了，即使证明者从未知道 $x$。

这就是为什么从证明者的角度来看，Fiat-Shamir 挑战必须是真正不可预测的。

他们必须首先做出承诺，然后才能从公共记录中推导出挑战。 绝不是之前。

Schnorr 签名

在我们结束之前，让我们看看如何构建 Schnorr 签名。

现在我们了解了挑战是如何来自 Fiat-Shamir 变换 的，你将看到 Schnorr 签名实际上只是一个非交互式的 Sigma 协议，带有一个附加的消息。

与之前相同的设置：

• 私钥 $x$
• 公钥 $Y = x \cdot G$
• 随机 nonce $r$ 及其承诺 $T = r \cdot G$

但这一次，我们正在签署消息 $m$。

计算挑战

我们使用哈希函数推导出挑战。

通常，它将是：

$c = H(G, Y, T)$

但由于我们正在签署某些内容，因此我们将消息包含在哈希中：

$c = H(G, Y, T, m)$

这使得签名绑定到该特定消息。

计算最终值

这就是我们之前所说的 “响应”。 但由于该协议不再是交互式的，因此称其为 “响应” 感觉很奇怪。

$s = r + c \cdot x$

最终签名是对 ($c$, $s$)。

请注意，我们不需要发送 $T$：验证者可以重新计算它。

验证

为了验证，验证者使用接收到的值 $s$ 和公钥 $Y$ 重建 $T$：

$T' = s \cdot G - c \cdot Y = (r + c \cdot x) \cdot G - c \cdot Y = r \cdot G$

然后检查：

$c =? H(G, Y, T', m)$

如果匹配，则签名有效。

就是这样。 Schnorr 签名 实际上只是 Schnorr Σ-protocol，其中将签名消息添加到了记录中。

泛化：证明对同态原像的了解

到目前为止，我们已经看到 Sigma 协议在特定情况下起作用：

• 使用简单的椭圆曲线点 $Y = x \cdot G$，我们证明了对 $x$ 的了解
• 使用 Pedersen 承诺 $P = x \cdot G + r \cdot H$，我们证明了对 ($x$, $r$) 的了解

如果你注意到这两个都符合相同的模式，那么你是对的！

它们共同之处在于同态：一个保留群运算的函数。

让我们看看如何将 Sigma 协议推广到任何同态函数。

同态

让我们定义一个通用的同态：

$\phi:(G_1, +) \rightarrow (G_2, +)$

这仅仅意味着函数 $\phi$ “尊重” 加法：

$\phi(u + v) = \phi(u) + \phi(v)$

例如，椭圆曲线就是这样：

$(3 + 4) \cdot G = 3 \cdot G + 4 \cdot G$

其中：

$\phi(x) = x \cdot G$

如果我们以乘法方式工作（例如 $g^a$，其中 $g$ 是乘法群中的生成器，而不是椭圆曲线点），它将如下所示：

$\phi(u + v) = \phi(u) \cdot \phi(v)$

并且该函数将被定义为：

$\phi:(G_1, +) \rightarrow (G_2, \times)$

直觉

这个想法是 Sigma 协议实际上并不关心 $\phi$ 是什么。 只要它是同态的，相同的逻辑就适用。

你正在尝试证明你知道一些秘密输入 x 使得

$Y = \phi(x)$

而不透露 $x$

通用 Σ-protocol

以下是通用协议的外观，抽象于任何同态 $\phi$。

你想要证明对秘密 $x \in G_1$ 的了解

1. 承诺

证明者选择一个随机数 $r \in G_1$ 并发送：

$T = \phi(r) \in G_2$

2. 挑战

验证者发回一个随机标量

$c \in G_1$

（字段中的一个数字，而不是群元素）。

3. 响应

证明者计算

$s = r + c \cdot x \in G_1$

4. 验证

验证者检查

$\phi(s) =? T + c \cdot Y$

如果相等，则验证者确信证明者必须知道一些满足 $Y = \phi(x) \in G_2$ 的 $x$

例子

椭圆曲线离散对数

$\phi:(Z_q, +) \rightarrow (G_2, +)$ $\phi(x) = x \cdot G$

然后你运行你已经知道的 Schnorr 协议。

Pedersen 承诺

$\phi:(Z_q^2, +) \rightarrow (G_2, +)$ $\phi(x, r) = x \cdot G + r \cdot H$

证明者的秘密是 $(x, r)$，承诺是 $P = \phi(x, r)$。

求幂

$\phi:(Z_q, +) \rightarrow (G_2, \times)$ $\phi(x) = g^x$

相同的结构，只是更改了群运算。 给出：

$y = \phi(x) = g^x$ $t = \phi(r) = g^r$ $s = r + c \cdot x$ $\phi(s) =? \phi(r) \cdot y^c$ $g^s =? g^r \cdot y^c$

为什么这很重要？

这种泛化表明 Sigma 协议从根本上是对同态下的原像的知识证明。

只要该函数保留群运算，该证明就有效。

这就是 Sigma 协议如此灵活的原因：它们不与特定的用例相关联，而与数学结构相关联。

Dan Boneh 在他的讲座中使用了这种完全相同的抽象，以展示 Σ-protocol 如何成为更高级的 ZK 系统的强大基础。

你可以在我的 GitHub 上找到本文中使用的所有 SageMath 脚本：sigma-proofs

zkSecurity 为包括零知识证明、MPC、FHE 和共识协议在内的密码系统提供审计、研究和开发服务。

了解更多 →

• 原文链接： blog.zksecurity.xyz/post...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～