#schnorr #elliptic-curve #signature #zk-po-k #proof-of-knowledge

no-std schnorr_pok

用于证明一个或多个离散对数知识的 Schnorr 协议。在椭圆曲线和配对群中工作

19 个重大版本发布

0.20.0 2024 年 7 月 18 日
0.18.0 2024 年 5 月 10 日
0.17.0 2024 年 3 月 4 日
0.16.0 2023 年 10 月 10 日
0.5.0 2021 年 11 月 5 日

#410密码学

Download history 20/week @ 2024-04-29 164/week @ 2024-05-06 44/week @ 2024-05-13 41/week @ 2024-05-20 61/week @ 2024-05-27 30/week @ 2024-06-03 22/week @ 2024-06-10 187/week @ 2024-06-17 44/week @ 2024-06-24 9/week @ 2024-07-08 168/week @ 2024-07-15 38/week @ 2024-07-22 260/week @ 2024-07-29 249/week @ 2024-08-05 286/week @ 2024-08-12

每月下载 839 次
11 包(直接使用 10 个)中使用

Apache-2.0

205KB
4.5K SLoC

Schnorr 的知识证明

Schnorr 协议用于在零知识中证明 1 个或多个离散对数的知识。有关 Schnorr 协议的更多详细信息,请参阅

还实现了配对群中离散对数知识的证明,即给定证明者和验证者都知道(A1Y1),并且证明者还知道 B1,证明 e(A1, B1) = Y1。同样,当只有证明者知道 A2 但两者都知道(B2Y2)时,证明 e(A2, B2) = Y2。请参阅 discrete_log_pairing

还实现了离散对数不等式的证明(在 Pedersen 承诺中提交的值),可以是公开值或使用 Inequality 中的另一个离散对数。例如,给定消息 m,其承诺 C = g * m + h * r 和公开值 v,证明 mv。或者给定 2 个消息 m1m2 及其承诺 C1 = g * m1 + h * r1C2 = g * m2 + h * r2,证明 m1m2

还实现了在只有离散对数中一个为证明者所知时,离散对数不等式的证明。即,给定 y = g * xz = h * k,证明者和验证者知道 ghyz,而证明者还知道 x 但不知道 k

还实现了部分Schnorr证明,其中某些证据的响应没有生成。这在多个Schnorr协议一起执行且它们共享一些证据时很有用。这些证据的响应将在一个Schnorr证明中生成,而其他协议将生成部分Schnorr证明,其中将缺少这些证据的响应。

我们概述了Schnorr协议的步骤。证明者想要证明在 y = g * xx 的知识(yg 是公共知识)步骤1:证明者生成随机数 r,并将 t = g * r 发送给验证者。 步骤2:验证者生成随机挑战 c 并发送给证明者。 步骤3:证明者产生 s = r + x*c,并将 s 发送给验证者。 步骤4:验证者检查 g * s = (y * c) + t

为了证明多个消息(如 x_1x_2)在 y = g_1*x_1 + g_2*x_2 中的知识: 步骤1:证明者生成随机数 r_1r_2,并将 t = g_1*r_1 + g_2*r_2 发送给验证者 步骤2:验证者生成随机挑战 c 并发送给证明者 步骤3:证明者产生 s_1 = r_1 + x_1*cs_2 = r_2 + x_2*c,并将 s_1s_2 发送给验证者 步骤4:验证者检查 g_1*s_1 + g_2*s_2 = y*c + t

以上可以推广到超过2个 x 的情况

还有一个Schnorr的变体,它给出了更短的证明,但尚未实现

  1. 证明者创建 r,然后 T = r * G
  2. 证明者计算挑战值 c = Hash(G||Y||T)
  3. 证明者创建响应 s = r + c*x 并将 cs 作为证明发送给验证者。
  4. 验证器创建 T' 作为 T' = s * G - c * Y 并计算 c' 作为 c' = Hash(G||Y||T')
  5. 如果有效,则证明 c == c'

这个变体的问题是它导致更差的失败报告,因为在失败的情况下,无法指出哪个关系未能验证。例如,假设有2个关系正在被证明,导致2个 T T1T2 以及2个响应 s1s2。如果只发送响应和挑战,则在失败的情况下,验证器只会知道其计算的挑战 c' 与证明者提供的挑战 c 不匹配,但不会知道哪个响应 s1s2 或两者都是错误的。这与实现变体的情况不同,因为验证器检查2个方程 s1 = r1 + x1*cs2 = r2 + x2*c

依赖项

~7–17MB
~195K SLoC