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

admin管理员组

文章数量:1530022

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(X) f(X)，其中 f ( 0 ) f(0) f(0)为其想要保护的私钥，当发送某message时，实际发送的是该多项式上的某个点。
若 f ( X ) f(X) f(X)为 n n n阶多相似，则所发送的message数量上限为 n n n，transmitter若发送多于 n n n个不同的message，则其私钥将会泄露。

实际使用zkSNARK来：

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

具体场景为：

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

承诺是指：

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

对某message的evaluation为：

• 计算message的哈希值： m m m
• RLN message为： m , f ( m ) , g ψ m ( α ) m,f(m),g^{\psi_m(\alpha)} m,f(m),gψm​(α)
• Verifier具有该epoch的多项式承诺值 g f ( α ) g^{f(\alpha)} gf(α)
• Verifier对message进行evaluate：
  e ( g f ( α ) , g ) = ? e ( g ψ m ( α ) , g α ⋅ g − m ) ⋅ e ( g , g ) f ( m ) e(g^{f(\alpha)},g)\overset{\text{?}}{=}e(g^{\psi_m(\alpha)},g^{\alpha}\cdot g^{-m})\cdot e(g,g)^{f(m)} e(gf(α),g)=?e(gψm​(α),gα⋅g−m)⋅e(g,g)f(m)

为此，设计了3个版本：

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

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

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

关键点为：

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

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

ZKP针对的场景为：

• public信息有： g f ( α ) , n g^{f(\alpha)},n gf(α),n
• private信息有： f ( x ) , p k f(x),pk f(x),pk
• 约束有：
  • f ( 0 ) = p k f(0)=pk f(0)=pk
  • membership proof of g f ( 0 ) g^{f(0)} gf(0)
  • f ( x ) = ∑ i = 0 k c i x i f(x)=\sum_{i=0}^{k}c_ix^i f(x)=∑i=0k​ci​xi，当 i > n i>n i>n时有 c i = 0 c_i=0 ci​=0

用户提供proof π \pi π和多项式承诺值 g f ( α ) g^{f(\alpha)} gf(α)。
Verifier检查proof：
verify ( π , g f ( α ) , root , n ) → t r u e \text{verify}(\pi, g^{f(\alpha)},\text{root},n)\to true verify(π,gf(α),root,n)→true

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

multiple多项式承诺方案为：

• 用户为 m m m个epoch创建 m m m个degree为 n n n的多项式，然后对这些多项式同时承诺。
• 对于某epoch，对应的 n n n-degree多项式为 f e ( x ) f_e(x) fe​(x)，将其表示为 f e ( x ) = ∑ i = 0 n c i ( e ) ⋅ x i f_e(x)=\sum_{i=0}^{n}c_i(e)\cdot x^i fe​(x)=∑i=0n​ci​(e)⋅xi，从而有：
  f 1 ( x ) = c 0 ( 1 ) + c 1 ( 1 ) x + c 2 ( 1 ) x 2 + ⋯ + c n ( 1 ) x n f_1(x)=c_0(1)+c_1(1)x+c_2(1)x^2+\cdots+c_n(1)x^n f1​(x)=c0​(1)+c1​(1)x+c2​(1)x2+⋯+cn​(1)xn
  f 2 ( x ) = c 0 ( 2 ) + c 1 ( 2 ) x + c 2 ( 2 ) x 2 + ⋯ + c n ( 2 ) x n f_2(x)=c_0(2)+c_1(2)x+c_2(2)x^2+\cdots+c_n(2)x^n f2​(x)=c0​(2)+c1​(2)x+c2​(2)x2+⋯+cn​(2)xn
  f 3 ( x ) = c 0 ( 3 ) + c 1 ( 3 ) x + c 2 ( 3 ) x 2 + ⋯ + c n ( 3 ) x n f_3(x)=c_0(3)+c_1(3)x+c_2(3)x^2+\cdots+c_n(3)x^n f3​(x)=c0​(3)+c1​(3)x+c2​(3)x2+⋯+cn​(3)xn
  ⋮ \vdots ⋮
  f m ( x ) = c 0 ( m ) + c 1 ( m ) x + c 2 ( m ) x 2 + ⋯ + c n ( m ) x n f_m(x)=c_0(m)+c_1(m)x+c_2(m)x^2+\cdots+c_n(m)x^n fm​(x)=c0​(m)+c1​(m)x+c2​(m)x2+⋯+cn​(m)xn
• 用户为每个 c i ( e ) c_i(e) ci​(e)创建多项式承诺

对应ZKP针对的场景为：

• public信息有： g c i ( α ) , n , m g^{c_i(\alpha)},n,m gci​(α),n,m
• private信息有： c i ( e ) , p k c_i(e),pk ci​(e),pk
• 约束有：
  • 对于每个 e ≤ m e\leq m e≤m，有 c 0 ( e ) = p k c_0(e)=pk c0​(e)=pk
  • f e ( x ) = ∑ i = 0 k c i ( e ) x i f_e(x)=\sum_{i=0}^{k}c_i(e)x^i fe​(x)=∑i=0k​ci​(e)xi，当 i > n i>n i>n，有 c i ( e ) = 0 c_i(e)=0 ci​(e)=0
  • membership proof of g f e ( 0 ) g^{f_e(0)} gfe​(0)
  • 多项式承诺值 g c i ( α ) g^{c_i(\alpha)} gci​(α)是正确的

验证过程为：

• 对于注册阶段：
  • Verifier检查proot：
    verify ( π , g c 0 ( α ) , ⋯   , g c n ( α ) , root , n , m ) → t r u e \text{verify}(\pi, g^{c_0(\alpha)},\cdots,g^{c_n(\alpha)},\text{root},n,m)\to true verify(π,gc0​(α),⋯,gcn​(α),root,n,m)→true
• 对于每个epoch e e e：
  • 用户提交：

    • { ( g c 0 ( e ) , g ϕ 0 , e ( α ) ) , ( g c 1 ( e ) , g ϕ 1 , e ( α ) ) , ⋯   , ( g c n ( e ) , g ϕ n , e ( α ) ) } \{(g^{c_0(e)},g^{\phi_{0,e}(\alpha)}),(g^{c_1(e)},g^{\phi_{1,e}(\alpha)}),\cdots,(g^{c_n(e)},g^{\phi_{n,e}(\alpha)})\} {(gc0​(e),gϕ0,e​(α)),(gc1​(e),gϕ1,e​(α)),⋯,(gcn​(e),gϕn,e​(α))}，其中 ϕ ( i , e ) ( x ) = c i ( x ) − c i ( e ) x − e \phi_{(i,e)}(x)=\frac{c_i(x)-c_i(e)}{x-e} ϕ(i,e)​(x)=x−eci​(x)−ci​(e)​

    • 为检查 g f e ( α ) = ∏ i = 0 n g c i ( e ) α i g^{f_e(\alpha)}=\prod_{i=0}^{n}g^{c_i(e)\alpha^i} gfe​(α)=∏i=0n​gci​(e)αi，Verifier检查：
      e ( g , g f e ( α ) ) = e ( g , ∏ i = 0 n g c i ( e ) α i ) = ? ∏ i = 0 n e ( g c i ( e ) , g α i ) e(g,g^{f_e(\alpha)})=e(g,\prod_{i=0}^{n}g^{c_i(e)\alpha^i})\overset{\text{?}}{=}\prod_{i=0}^{n}e(g^{c_i(e)},g^{\alpha^i}) e(g,gfe​(α))=e(g,∏i=0n​gci​(e)αi)=?∏i=0n​e(gci​(e),gαi)

      • 对于 i = 0 , ⋯   , n i=0,\cdots,n i=0,⋯,n，借助同态属性，Verifier检查用户在多项式承诺值中隐藏的系数：
        e ( g c i ( α ) , g ) = ? e ( g ϕ i , e ( α ) , g α ⋅ g − e ) ⋅ e ( g , g c i ( e ) ) e(g^{c_i(\alpha)},g)\overset{\text{?}}{=}e(g^{\phi_{i,e}(\alpha)},g^{\alpha}\cdot g^{-e})\cdot e(g,g^{c_i(e)}) e(gci​(α),g)=?e(gϕi,e​(α),gα⋅g−e)⋅e(g,gci​(e))
        其中 ϕ i , e ( x ) = c i ( x ) − c i ( e ) x − e \phi_{i,e}(x)=\frac{c_i(x)-c_i(e)}{x-e} ϕi,e​(x)=x−eci​(x)−ci​(e)​

    • 然后：

      • 计算message的哈希值： m m m
      • RLN message有： m , f ( m ) , g ψ m ( α ) m,f(m),g^{\psi_m(\alpha)} m,f(m),gψm​(α)
      • Verifier evaluate the message：
        e ( g f ( α ) , g ) = ? e ( g ψ m ( α ) , g α ⋅ g − m ) ⋅ e ( g , g ) f ( m ) e(g^{f(\alpha)},g)\overset{\text{?}}{=}e(g^{\psi_m(\alpha)},g^{\alpha}\cdot g^{-m})\cdot e(g,g)^{f(m)} e(gf(α),g)=?e(gψm​(α),gα⋅g−m)⋅e(g,g)f(m)

参考资料

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

本文标签： 多项式方案KZGRLN