零知识证明 Schnorr

证明什么东西？

零知识证明证明的是知道某个东西，而不是证明各自知道某个椭圆曲线

零知识证明（Zero-Knowledge Proof, ZKP）的核心目的是证明知识的存在而不泄露具体的信息，而不是证明知道某个椭圆曲线。在数字签名和密码学的上下文中，零知识证明通常用来证明某人知道一个秘密（如一个私钥），但又不泄露这个秘密本身。

零知识证明在数字签名中的应用

在共同数字签名的场景中，比如使用 Ed25519 签名方案，Alice 和 Bob 各自持有私钥的一部分，他们需要证明他们各自知道自己的私钥份额，而无需向对方透露这些份额。这里的零知识证明可以用来：

1. 证明私钥份额的知识：

   • Alice 和 Bob 可以使用零知识证明来证明他们各自知道如何正确地执行与其私钥份额相关的计算，比如计算 $R_1 = r_1 \cdot G$ 和 $R_2 = r_2 \cdot G$ ，而无需透露 $r_1$ 或 $r_2$ 。

2. 确保随机数的正确生成和使用：

   • 在签名过程中，他们还需要证明他们生成的随机数 $r_1$ 和 $r_2$ 是正确地用于计算点 $R_1$ 和 $R_2$ 的，这一点也可以通过零知识证明来确保。

零知识证明的具体实现

在实际应用中，零知识证明可以通过多种方式实现，其中一种常见的方法是使用 Schnorr 签名协议，这是一种基于椭圆曲线的零知识证明技术：

• Schnorr 证明：
  • Alice 选择一个随机数 $k$ ，计算 $K = k \cdot G$ 并将 $K$ 发送给 Bob。
  • Alice 接收到来自 Bob 的一个挑战 $e$ ，然后计算响应 $s = k + e \cdot r_1$ 并将其发送给 Bob。
  • Bob 可以验证 $s \cdot G$ 是否等于 $K + e \cdot R_1$ ，如果等式成立，那么 Bob 可以确信 Alice 知道 $r_1$ ，但 Alice 并没有透露 $r_1$ 。

通过这种方式，Alice 和 Bob 可以在不泄露各自私钥份额的情况下，相互验证对方已正确执行了与私钥相关的计算。这种方法在保护隐私的同时，确保了签名过程的安全性和完整性。

Schnorr 证明

$s \cdot G = (k + e \cdot r_1 ) \cdot G = (k \cdot G) + e \cdot (r_1 \cdot G) = K + e \cdot R_1$

在 Schnorr 签名或证明中，各个字段和计算步骤具有特定的意义和作用。这里是对上述证明式中各个字段的详细解释：

字段解释

1. $s$：

   • $s$ 是 Alice 的响应，它是一个由私钥 $r_1$、随机数 $k$ 和挑战 $e$ 计算得到的值。
   • 计算公式为 $s = k + e \cdot r_1$。

2. $G$：

   • $G$ 是椭圆曲线加密中使用的基点（或生成元），它是公开已知的。
   • $G$ 的阶（即最小正整数 $n$，使得 $nG = 0$）是一个大素数，确保了群的安全性。

3. $k$：

   • $k$ 是 Alice 为每次操作随机选择的一个数，称为随机数或临时私钥。

4. $e$：

   • $e$ 是来自 Bob 的挑战，它是一个随机生成的数，用于确保证明的正确性和防止重放攻击。

5. $r_1$：

   • $r_1$ 是 Alice 的私钥，是一个秘密的值，只有 Alice 知道。

6. $K$：

   • $K$ 是提交到 Bob 的值，计算为 $K = k \cdot G$。它是使用随机数 $k$ 和基点 $G$ 计算的椭圆曲线上的点。

7. $R_1$：

   • $R_1$ 是公钥，计算为 $R_1 = r_1 \cdot G$。它是使用 Alice 的私钥 $r_1$ 和基点 $G$ 计算的椭圆曲线上的点。

证明式解释

• $s \cdot G$：

  • 这是将 Alice 的响应 $s$ 与基点 $G$ 相乘的结果。

• $(k + e \cdot r_1) \cdot G$：

  • 这是将 $s$ 的定义 $k + e \cdot r_1$ 代入并与 $G$ 相乘。

• $k \cdot G + e \cdot (r_1 \cdot G)$：

  • 这是将 $k \cdot G$ 和 $e \cdot r_1 \cdot G$ 相加的结果。这里 $k \cdot G$ 是 $K$，而 $r_1 \cdot G$ 是 $R_1$。

• $K + e \cdot R_1$：

  • 这是用 $K$ 和 $e \cdot R_1$ 表示的式子，是验证步骤中 Bob 用来确认 Alice 确实知道 $r_1$ 的表达式。

总结

这个证明过程展示了 Alice 如何使用她的私钥 $r_1$ 和一个随机数 $k$ 来生成一个响应 $s$，这个响应可以让 Bob 在不知道 $r_1$ 的情况下验证 Alice 确实持有 $r_1$。这是一个典型的零知识证明，它允许 Alice 证明她知道一个秘密而不需要透露这个秘密本身。

Alice Bob 双向证明

在零知识证明中，我们可以通过 Schnorr 协议来展示如何进行这样的双向验证。首先，让我们回顾一下 Alice 如何向 Bob 证明她知道某个秘密 $r_1$，然后我们将推导 Bob 如何使用类似的方法向 Alice 证明他的知识。

Alice 向 Bob 证明她知道 $r_1$

1. 提交阶段:

   • Alice 选择一个随机数 $k$。
   • 计算 $K = k \cdot G$，其中 $G$ 是群的生成元。
   • Alice 将 $K$ 发送给 Bob。

2. 挑战阶段:

   • Bob 向 Alice 发送一个随机生成的挑战 $e$。

3. 响应阶段:

   • Alice 计算响应 $s = k + e \cdot r_1$。
   • Alice 将 $s$ 发送给 Bob。

4. 验证阶段:

   • Bob 收到 $s$，验证等式 $s \cdot G \overset{?}{=} K + e \cdot R_1$，其中 $R_1 = r_1 \cdot G$。

如果验证成功，Bob 确信 Alice 知道 $r_1$。

Bob 向 Alice 证明他知道 $r_2$

我们可以假设 Bob 想要证明他知道另一个秘密 $r_2$，过程类似：

1. 提交阶段:

   • Bob 选择一个随机数 $k'$。
   • 计算 $K' = k' \cdot G$。
   • Bob 将 $K'$ 发送给 Alice。

2. 挑战阶段:

   • Alice 向 Bob 发送一个随机生成的挑战 $e'$。

3. 响应阶段:

   • Bob 计算响应 $s' = k' + e' \cdot r_2$。
   • Bob 将 $s'$ 发送给 Alice。

4. 验证阶段:

   • Alice 收到 $s'$，验证等式 $s' \cdot G \overset{?}{=} K' + e' \cdot R_2$，其中 $R_2 = r_2 \cdot G$。

如果验证成功，Alice 确信 Bob 知道 $r_2$。

结论

通过这种方式，Alice 和 Bob 可以互相验证对方知道各自的秘密，而无需暴露这些秘密。这种方法是对称的，即双方都使用相同的数学结构和步骤，只是角色互换。这就是如何在 Schnorr 证明框架中实现双向验证。

k 是私钥 K 是公钥 随机挑战 e 如何生成？

在 Schnorr 证明框架中，随机挑战 $e$ 的生成是一个关键步骤，它确保了证明的安全性和有效性。以下是几种在实践中生成随机挑战 $e$ 的方法：

1. 随机数生成器

最直接的方法是使用加密安全的随机数生成器（Cryptographically Secure Random Number Generator, CSRNG）。这种生成器设计为产生不可预测的输出，适用于安全敏感的应用，如加密协议。

2. 基于哈希函数

另一种常见的方法是使用哈希函数生成挑战。这种方法可以通过以下步骤实现：

• 将 Alice 发送给 Bob 的公钥 $K$、Bob 的一些公开信息以及可能的其他随机或固定数据作为输入。
• 使用一个安全的哈希函数（如 SHA-256）处理这些输入数据。
• 将哈希输出转换为一个适当大小的整数，用作挑战 $e$。

这种方法的优势在于它的确定性和重复性，即相同的输入总是产生相同的输出。这可以帮助防止重放攻击，因为每次交互的上下文都会略有不同。

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

在非交互式零知识证明中，挑战 $e$ 可以通过一个“公共随机串”或“公共参考字符串”预先固定下来。这允许证明过程在没有交互的情况下进行。这通常涉及到复杂的密码学技术，如 Fiat-Shamir 启发式，将交互式协议转换为非交互式协议。

4. 双方协商

在一些协议中，挑战 $e$ 可能由双方协商产生。例如，双方可以各自贡献随机数，然后将这些随机数合并（例如，通过哈希它们的组合）来生成 $e$。这样可以确保挑战的公平性，并防止任何一方操纵结果。

实际应用

在实际应用中，选择哪种方法生成 $e$ 取决于具体的应用场景、安全需求以及是否需要交互。对于大多数实际应用，使用哈希函数来生成 $e$ 是一个既安全又方便的方法，因为它简化了协议的实现，并提供了一定程度的安全保障。