# RLN on KZG Version A Vulnerabilities

## 问题描述

在 RLN on KZG协议中，证明者需要提交一个多项式 $f$ 的承诺以及公钥 $g^{f(0)}$。我们发现了一个漏洞，攻击者可以在不知道私钥的情况下伪造公钥。为了解决这个问题，我们提出了一个解决方案，使用 Schnorr 签名来验证公钥，可以有效地防止这种攻击。

## 漏洞详细信息

在原始的 RLN 协议中，证明者提交多项式承诺 $g^{f(\alpha)}$、公钥 $g^{f(0)}$ 和开放证明 $g^{\psi_{0}(\alpha)}$。验证者检查用户的公钥是否在提交的多项式上，通过验证开放证明 $g^{\psi_{0}(\alpha)}$：

$$
e(g^{\psi_{0}(\alpha)},g^\alpha)\cdot e(g,g^{f(0)}) \stackrel{?}{=} e(g, g^{f(\alpha)})
$$

然而，攻击者可以在不知道私钥的情况下伪造公钥。攻击者可以选择一个随机数 $\gamma$，然后修改公钥和开放证明，使它们满足以下等式：

$$
e(g^{\psi_{0}(\alpha)}\cdot g^\gamma,g^\alpha)\cdot e(g,g^{f(0)}\cdot g^{\alpha \cdot -\gamma}) \stackrel{?}{=} e(g, g^{f(\alpha)})
$$

1. 将等式左边展开:

$$
e(g^{\psi_{0}(\alpha)} \cdot g^\gamma, g^\alpha) \cdot e(g, g^{f(0)} \cdot g^{\alpha \cdot -\gamma}) = e(g^{\psi_{0}(\alpha)}, g^\alpha) \cdot e(g^\gamma, g^\alpha) \cdot e(g, g^{f(0)}) \cdot e(g, g^{\alpha \cdot -\gamma})
$$

2. 使用Pairing的性质 $e(g^a, g^b) = e(g, g)^{ab}$ 将等式做如下变换:

$$
= e(g, g)^{\psi_{0}(\alpha) \cdot \alpha} \cdot e(g, g)^{\gamma \cdot \alpha} \cdot e(g, g)^{f(0)} \cdot e(g, g)^{-\gamma \cdot \alpha}
$$

3. 合并指数:

$$
= e(g, g)^{\psi_{0}(\alpha) \cdot \alpha + \gamma \cdot \alpha + f(0) - \gamma \cdot \alpha}
$$

4. 已知$\psi_{0}(\alpha) \cdot \alpha = f(\alpha) - f(0)$, 替换到等式中:

$$
= e(g, g)^{f(\alpha) - f(0) + \gamma \cdot \alpha + f(0) - \gamma \cdot \alpha}
$$

5. 消除 $f(0)$ 和 $\gamma \cdot \alpha$:

$$
= e(g, g)^{f(\alpha)}
$$

通过这种方式，攻击者可以使验证者相信他们提交了一个有效的公钥，但实际上这个公钥并不与他们的私钥相匹配。

## 解决方案

我们提出了一个解决方案，使用 Schnorr 签名来证明证明者确实拥有与公钥匹配的私钥。这是有效的，因为攻击者无法获取私钥，因为他们没有办法计算 $g^{\alpha}$，因为 $\alpha$ 是从 SRS 中获得的，而没有人知道 $\alpha$ 的值。这意味着攻击者不能制作满足配对检查的 $\gamma$，除非他们知道私钥。

当证明者提交其公钥 $g^{f(0)}$ 时，他们还需要提交一个 Schnorr 签名作为知识证明，证明他们知道公钥对应的私钥。验证者可以通过验证该 Schnorr 签名来确保证明者确实知道与其公钥对应的私钥。这个步骤在 RLN 协议的设置步骤中进行，可以有效地防止攻击者提交伪造的公钥。

Schnorr签名是一种数字签名方案。它们具有可以证明安全性的优点，假设离散对数问题是难解的，并且相对简单且高效。

Schnorr签名算法涉及以下步骤：

1. **密钥生成**:
- 从小于预定质数$q$的整数集中随机选择私钥$x$。
- 然后计算相应的公钥$y$，$y = g^x \mod p$，其中$g$是一个循环群$G$的生成器，$G$的阶为$q$，$p$是模数。

2. **签名**:
- 从小于$q$的整数集中随机选择$k$。
- 计算$r = g^k \mod p$。
- 计算$e = H(M || r)$，其中$H$是一个密码学哈希函数，$M$是信息，$||$表示连接。
- 计算$s = k - xe \mod q$。
- 签名是对$(s, e)$。

3. **验证**:
- 计算$r' = (g^s * y^e) \mod p$。
- 计算$e' = H(M || r')$。
- 如果$e' = e$，则签名已验证。

在RLN的上下文中，可以使用Schnorr签名来证明证明者知道与公钥$g^{f(0)}$对应的私钥。证明者使用他们的私钥$f(0)$签名一条信息（可以是随机挑战或已知值），验证者检查Schnorr签名。如果签名验证，这意味着证明者知道与$g^{f(0)}$对应的私钥，所以公钥没有被伪造。

在RLN中，使用KZG承诺和Schnorr签名，需要知道$g^α$并面临离散对数(DL)问题的步骤包括：

1. **承诺**：
- 用户使用参考字符串计算KZG多项式承诺$C = g^{f(α)}$。这里，用户需要知道$g^α$来创建承诺。

2. **开放证明**：
- 为了发送消息，用户共享$(f(m), g^{ψ_m(α)})$，其中$m$是消息值的哈希，$g^{ψ_m(α)}$是开放证明。用户需要知道$g^α$来创建开放证明。

离散对数(DL)问题在Schnorr签名和RLN协议的安全性中起着关键作用。假设在给定$g^x \mod p$的情况下，计算离散对数$x$在计算上是不可行的。在RLN的情况下，未知的离散对数是$α$，而$g^α$是共享参考字符串的一部分。

当攻击者尝试通过使用随机$γ$来伪造公钥$g^{f(0)}$时，他将需要知道$α$的值来操作等式$g^{f(0) + α * γ}$。然而，由于DL问题的困难性，攻击者无法从参考字符串计算$α$，因此在不知道相应私钥的情况下无法伪造公钥。

## 结论
在 RLN 协议中，存在一个漏洞，攻击者可以在不知道私钥的情况下伪造公钥。为了解决这个问题，我们提出了一个解决方案，使用 Schnorr 签名来验证公钥。这个解决方案有效地防止了攻击者提交伪造的公钥。然而，需要注意的是，这个解决方案需要修改 RLN 协议的设置步骤，使得证明者需要提交更多的信息，并且验证者需要进行更多的验证步骤。我们希望这个解决方案可以帮助 RLN 协议的开发者修复这个漏洞，进一步提高 RLN 协议的安全性。