基于KZG多项式承诺方案的RLN

1. 引言

RLN——Rate-Limiting Nullifier为PSE团队主导的项目，源自：

• Barry White Hat 2019年博客 Semaphore RLN, rate limiting nullifier for spam prevention in anonymous p2p setting

RLN（Rate-Limiting Nullifier）是一种zk小工具/协议，可为匿名环境启用垃圾邮件预防机制。旨在：

• 在每个epoch使用KZG多项式承诺
• 为每个message使用KZG opening
• 为单个message生成proof的时间应小于1ms，几乎改进约1000倍
• 使用RLN作为垃圾邮件保护层（spam protection layer），从而具有网络层面的隐私，可用于Tor网络和以太坊validator网路

从技术层面上来说，transmitter选中某多项式$f(X)$，其中$f(0)$为其想要保护的私钥，当发送某message时，实际发送的是该多项式上的某个点。
若$f(X)$为$n$阶多相似，则所发送的message数量上限为$n$，transmitter若发送多于$n$个不同的message，则其私钥将会泄露。

实际使用zkSNARK来：

• 使用membership proof，来确保transmitter对某proof of stake进行了承诺
• 使用message proof，来证明其包含了多项式上的某个点。
  当前的问题在于，为单个message来生成proof需约1s，在很多场景下并不实用——如Tor网路、Validator网络、手机环境等。需要利用KZG多项式承诺和KZG opening方案，将单个message证明时间由1s提高到1ms。

具体场景为：

• 某指定epoch $e$和message数量上限（message limit）$n$，用户创建某degree为$n$的多项式，满足$f(0)$为该用户的私钥$pk$。
• 可信设置（trusted setup）：
  • 对于message数量上限为$n$的场景，需要shared common reference：$g,g^{\alpha },g^{{\alpha }^2},\cdots ,g^{{\alpha }^n}$
    • 对于非匿名版本：需为每个message limit执行可信设置。
    • 对于匿名版本：可使用现有的reference。

承诺是指：

• 用户为某epoch选中某$n$-degree多项式，最多可发送$n$个message，其中$f(0)$为用户私钥$pk$。
• 使用reference string用户计算KZG多项式承诺$C=g^{f(\alpha )}$。
• 在特定epcoh，用户分享该多项式承诺$C$。
• 为发送某message，用户分享$(f(m),g^{{\psi }_m(\alpha )})$，其中$m$为message的哈希值，$g^{{\psi }_m(\alpha )}$为相应的opening proof，其中${\psi }_m(x)=\frac{f(x)-f(m)}{x-m}$。

对某message的evaluation为：

• 计算message的哈希值：$m$
• RLN message为：$m,f(m),g^{{\psi }_m(\alpha )}$
• Verifier具有该epoch的多项式承诺值$g^{f(\alpha )}$
• Verifier对message进行evaluate：
  $e(g^{f(\alpha )},g)\stackrel{\text{?}}{=}e(g^{{\psi }_m(\alpha )},g^{\alpha }\cdot g^{-m})\cdot e(g,g{)}^{f(m)}$

为此，设计了3个版本：

• Version A：具体的原型设计见：
  https://github.com/Rate-Limiting-Nullifier/kzg-rln/blob/main/versionA/src/main.rs（Rust）
• Version B
• Version C

这3个版本的性能对比为：【可在epoch之初缓存$e(g^{f(\alpha )},g)$以供之后的message verification过程中使用，因此，每个message verification仅需2次pairing运算。】

2. Version A：非匿名的最简单方案

关键点为：

• 用户的公钥为：$g^{f(0)}$
• 用户提供多项式承诺值、用户公钥以及opening proof：$g^{f(\alpha )},g^{{\psi }_0(\alpha )},g^{f(0)}$
• Verifier：通过验证KZG commitment的opening，检查用户公钥$g^{f(0)}$在所承诺的多项式上。
  $e(g^{{\psi }_0(\alpha )},g^{\alpha })\cdot e(g,g^{f(0)})\stackrel{\text{?}}{=}e(g,g^{f(\alpha )})$

3. Version B：借助ZKP实现的匿名方案

ZKP针对的场景为：

• public信息有：$g^{f(\alpha )},n$
• private信息有：$f(x),pk$
• 约束有：
  • $f(0)=pk$
  • membership proof of $g^{f(0)}$
  • $f(x)={\sum }_{i=0}^k{c}_i{x}^i$，当$i>n$时有$c_i=0$

用户提供proof $\pi$和多项式承诺值$g^{f(\alpha )}$。
Verifier检查proof：
$\text{verify}(\pi ,g^{f(\alpha )},\text{root},n)\to true$

4. Version C：为多个epoch承诺 使用multiple多项式承诺 的匿名方案

multiple多项式承诺方案为：

• 用户为$m$个epoch创建 $m$个degree为$n$的多项式，然后对这些多项式同时承诺。
• 对于某epoch，对应的$n$-degree多项式为$f_e(x)$，将其表示为$f_e(x)={\sum }_{i=0}^n{c}_i(e)\cdot x^i$，从而有：
  $f_1(x)=c_0(1)+c_1(1)x+c_2(1)x^2+\cdots +c_n(1)x^n$
  $f_2(x)=c_0(2)+c_1(2)x+c_2(2)x^2+\cdots +c_n(2)x^n$
  $f_3(x)=c_0(3)+c_1(3)x+c_2(3)x^2+\cdots +c_n(3)x^n$
  $⋮$
  $f_m(x)=c_0(m)+c_1(m)x+c_2(m)x^2+\cdots +c_n(m)x^n$
• 用户为每个$c_i(e)$创建多项式承诺

对应ZKP针对的场景为：

• public信息有：$g^{c_i(\alpha )},n,m$
• private信息有：$c_i(e),pk$
• 约束有：
  • 对于每个$e\le m$，有$c_0(e)=pk$
  • $f_e(x)={\sum }_{i=0}^k{c}_i(e)x^i$，当$i>n$，有$c_i(e)=0$
  • membership proof of $g^{f_e(0)}$
  • 多项式承诺值$g^{c_i(\alpha )}$是正确的

验证过程为：

• 对于注册阶段：
  • Verifier检查proot：
    $\text{verify}(\pi ,g^{c_0(\alpha )},\cdots ,g^{c_n(\alpha )},\text{root},n,m)\to true$
• 对于每个epoch $e$：
  • 用户提交：

    • $\{(g^{c_0(e)},g^{{\varphi }_{0,e}(\alpha )}),(g^{c_1(e)},g^{{\varphi }_{1,e}(\alpha )}),\cdots ,(g^{c_n(e)},g^{{\varphi }_{n,e}(\alpha )})\}$，其中${\varphi }_{(i,e)}(x)=\frac{c_i(x)-c_i(e)}{x-e}$

    • 为检查$g^{f_e(\alpha )}={\prod }_{i=0}^n{g}^{c_i(e){\alpha }^i}$，Verifier检查：
      $e(g,g^{f_e(\alpha )})=e(g,{\prod }_{i=0}^n{g}^{c_i(e){\alpha }^i})\stackrel{\text{?}}{=}{\prod }_{i=0}^{n}e(g^{c_i(e)},g^{{\alpha }^i})$

      • 对于$i=0,\cdots ,n$，借助同态属性，Verifier检查用户在多项式承诺值中隐藏的系数：
        $e(g^{c_i(\alpha )},g)\stackrel{\text{?}}{=}e(g^{{\varphi }_{i,e}(\alpha )},g^{\alpha }\cdot g^{-e})\cdot e(g,g^{c_i(e)})$
        其中${\varphi }_{i,e}(x)=\frac{c_i(x)-c_i(e)}{x-e}$

    • 然后：

      • 计算message的哈希值：$m$
      • RLN message有：$m,f(m),g^{{\psi }_m(\alpha )}$
      • Verifier evaluate the message：
        $e(g^{f(\alpha )},g)\stackrel{\text{?}}{=}e(g^{{\psi }_m(\alpha )},g^{\alpha }\cdot g^{-m})\cdot e(g,g{)}^{f(m)}$

参考资料

[1] 2023年4月 ethresearch和zkresearch联合发布 RLN on KZG polynomial commitment scheme [cross-posted]