Coconut 签名方案

2024-04-10 本文已影响0人雪落无留痕

最近研究Nym 区块链项目，提到 Coconut 签名方案，顺便看一下论文。

Coconut 是一种选择性展示凭证属性的分布式门限盲化签名分发方案，具有公开和私有的属性，重新随机化和多个不可链接的属性展示。

Coconut 签名可以用在匿名支付，匿名投票和去中心化代理等应用中。

Coconut 架构如上图所示，首先由用户向授权者发送凭证生成请求，然后由由授权者颁发凭证，由用户将凭证聚合后，生成完整的凭证，然后用户可以对凭进进行重新随机化，并可以选择性展示其私有的属性，实现认证或授权的目的。

形式化定义

Coconut 签名的形式化定义为：

$\mathbf{Setup(1^{\lambda})} \rightarrow (params)$ : 定义关于安全参数 $\lambda$ 的系统参数params ；
$\mathbf{KeyGen(params)} \rightarrow (sk, vk)$ : 由授权者运行，生成各自的私钥sk 和验证密钥 vk;
$\mathbf{AggKey(vk_1, \cdots, vk_t)} \rightarrow (vk)$ : 由验证者聚合 $t$ 个授权者的验证密钥，合成完整的验证密钥 $vk$ ;
$\mathbf{IssueCred(m, \phi)} \rightarrow (\sigma)$ : 通过用户与授权者之间交互完成，由授权者给用户颁发一个凭证，其中私有属性 $m$ 满足 $\phi$ 定义的约束；
$\mathbf{AggCred(\sigma_1, \cdots, \sigma_t)}\rightarrow (\sigma)$ : 通过聚合 $t$ 个部分凭证 $\sigma_i$ 生成一个完整的凭证；
$\mathbf{ProveCred(vk, m, \phi')} \rightarrow (\pi, \phi')$ : 由用户生成证明 $\pi$ , 证明私有的属性 m 满足 $\phi'$ 的约束；
$\mathbf{VerifyCred(vk, \pi, \phi')} \rightarrow (true/false)$ : 由验证者通过 $vk$ 验证证明，验证凭证的的有效性。

Coconut 签名满足不可伪造性，盲化性，不可链接/零知道证明属性。

签名方案构造

Pointcheval 签名方案

$\mathbf{P.Setup(1^{\lambda})} \rightarrow (params)$ : 选择一个双线性群 $(\mathbb{G_1}, \mathbb{G_2}, \mathbb{G}_T)$ , 群的阶为 $p$ , $p$ 为 $\lambda$ 位长的素数。其中 $\mathbb{G}_1$ 的生成元为 $g_1$ , $\mathbb{G}_2$ 的生成元为 $g_2$ ，系统参数为： $(\mathbb{G_1}, \mathbb{G_2}, \mathbb{G}_T, p, g_1, g_2)$ .
$\mathbf{P.KeyGen(params)} \rightarrow (sk, vk)$ : 选择随机的密钥 $sk=(x,y) \in \mathbb{F}_p^2$ ，解析参数 $params = (\mathbb{G_1}, \mathbb{G_2}, \mathbb{G}_T, p, g_1, g_2)$ ，发布验证密钥 $vk=(g_2, \alpha, \beta)=(g_2, g_2^x, g_2^y)$ ；
$\mathbf{P.Sign}(params, sk, m) \rightarrow (\sigma)$ : 解析 $sk=(x,y)$ ，选择随机数 $r \in \mathbb{F}_p$ , 设置 $h=g_1^r$ , 输出签名为： $\sigma = (h, s)=(h, h^{x+y\cdot m})$ ；
$\mathbf{P.Verify}(params, vk, m, \sigma) \rightarrow (true/false)$ : 解析 $vk = (g_2, \alpha, \beta)$ , $\sigma = (h, s)$ , 验证 $e(h, \alpha\beta^m)=e(s, g_2)$ , 则签名有效，否则即失败。

可以对签名 $\sigma = (h, s)$ 进行随机化，选择一个随机数 $r' \in \mathbb{F}_p$ ，计算 $\sigma' = (h^{r'}, s^{r'})$ 。

也可以将其改获取具有私有属性的凭证，在 $\mathbf{IssueCred}$ 过程中，用户首先选择随机数 $r\in \mathbf{F}_p$ , 计算消息 $m$ 的承诺 $c_p = g_1^t Y^m$ ，其中 $Y = g_1^y$ , 并将承诺的证明发送给授权者，授权者验证证明之后，选择随机数 $u \in \mathbb{F}_p$ , 并给用户发送 $\tilde{\sigma}=(h, \tilde{s}) = (g^u, (Xc_p)^u)$ ，其中 $X=g_1^x$ . 用户通过计算 $\sigma = (h, \tilde{s}(h)^{-t})$ 进行去盲化签名， $\sigma$ 可以用作凭证。

该签名可以实现盲化，不可链接性，高效和短凭证的特征，但是不支付门限签发属性。为了克服这种限制， Coconut 引入BLS签名中的hash 函数： $H: \mathbb{F}_p \rightarrow \mathbb{G}_1$ , 以此计算群元素 $h=H(m)$ .

Coconut 门限签名方案

Coconut 门限签名方案 $(t, n)$ 需要满足： $n/2 < t < n$

$\mathbf{Setup(1^{\lambda})} \rightarrow (params)$ : 选择双线性群 $(\mathbb{G_1}, \mathbb{G_2}, \mathbb{G}_T)$ ，其阶为 $p$ , $p$ 为 $\lambda$ 位长的素数，其中 $\mathbf{G}_1$ 的生成元为 $g_1, h_1$ , $\mathbf{G}_2$ 的生成元为 $g_2$ , 系统的参数为： $(\mathbb{G_1}, \mathbb{G_2}, \mathbb{G}_T, p, g_1, g_2, h_1)$ ；
$\mathbf{TTPKeyGen}(params, t, n) \rightarrow (sk, vk)$ : 选择两个次数为 $t-1$ 的多项式 $v, w$ , 其系数在 $\mathbf{F}_p$ 上。设定 $(x,y)=(v(0),w(0))$ . 对于每个授权者 $i\in [1,\cdots, n]$ 的密钥 $sk_i = (x_i,y_i)=(v(i), w(i))$ ，并发布其验证密钥 $vk_i = (g_2, \alpha_i, \beta_i)=(g_2, g_2^{x_i}, g_2^{y_i})$ ；
$\mathbf{IssueCred}(m, \phi) \rightarrow (\sigma)$ : 凭证通过以下三个算法颁发：
- $PrepareBlindSign(m, \phi)\rightarrow (d, \Lambda , \phi)$ ：用户生成 El-Gamal 密钥对 $(d, \gamma = g_1^d)$ ，选一个随机数 $o \in \mathbb{F}_p$ ，计算承诺 $c_m$ 和群元素 $h \in \mathbf{G}_1$ :
```
     $c_m = g_1^mh_1^o$,    $h=H(m)$
```
  选择随机数 $k \in \mathbb{F}_p$ ，计算 $m$ 的El-Gamal 加密为：
```
     $c = Enc(h^m) = (g_1^k, \gamma^kh^m)$
```
  输出 $(d, \Lambda = (\gamma, c_m, c, \pi_s), \phi)$ ，其中 $\phi$ 是和应用相关的关于 $m$ 的约束， $\pi_s$ 定义为：
  
  $\pi_s = NIZK{(d,m,o,k): \gamma = g_1^d \wedge c_m = g_1^mh_1^o \wedge c= (g_1^k, \gamma^kh^m)\wedge \phi(m)=1}$
- $BlindSign(sk_i, \Lambda, \phi) \rightarrow (\tilde{\sigma}_i)$ ：授权者 $i$ 解析 $\Lambda = (\gamma, c_m, c, \pi_s)$ ， $sk_i = (x_i, y_i), c=(a,b)$ 。计算 $h = H(c_m)$ ，利用 $\gamma, c_m, \phi$ 验证证明 $\pi_s$ 。若证明有效，构建 $\tilde{c_i}=(a^y, h^{x_i}b^{y_i})$ ，输出 $\tilde{\sigma_i}=(h, \tilde{c_i})$ .
- $Unblind(\tilde{\sigma_i},d) \rightarrow(\sigma_i)$ ：用户解析 $\tilde{\sigma_i}=(h, \tilde{c_i})$ , $\tilde{c_i} = (\tilde{a},\tilde{b})$ , 计算 $\sigma_i = (h, \tilde{b}(\tilde{a})^{-d})$ , 然后输出 $\sigma_i$

$\mathbf{AggCred}(\sigma_1,\cdots, \sigma_t) \rightarrow (\sigma)$ : 对于 $i \in [1,\cdots, t]$ , 解析 $\sigma_i$ 为 $(h, s_i)$ , 输出 $(h, \prod_{i=1}^ts_i^{l_i})$ , $l_i$ 为Lagrange 系数：

          $l_i = \lgroup\prod_{j=1,j\neq 0}^t(0-j)\rgroup \lgroup \prod_{j=1,j\neq 0}^t(i-j)  \rgroup^{-1} mod\ p$

$\mathbf{ProveCred}(vk, m, \sigma, \phi') \rightarrow (\pi, \phi')$ : 解析 $\sigma = (h, s)$ ， $vk = (g_2, \alpha, \beta)$ ，挑选随机 $r', r \in \mathbb{F}_p^2$ ，设定 $\sigma' = (h', s')=(h^{r'}, s^{r'})$ ，构建 $k = \alpha\beta^m g_2^r$ ， $v = (h')^r$ . 输出 $(\pi = (k,v, \sigma', \pi_v), \phi')$ ，其中 $\phi'$ 是应用相关的关于 $m$ 的约束， $\pi_v$ 为：
```
           $\pi_v = NIZK{(m,r): k = \alpha\beta^m g_2^r \wedge=(h')^r \wedge\phi'(m) =  1}$
```
$\mathbf{VerifyCred(vk, \pi, \phi')} = (true/false)$ : 解析 $\pi = (k,v, \sigma', \pi_v)$ ， $\sigma' = (h', s')$ ，使用 $vk, \phi'$ 验证 $\pi_v$ ，若验证 $e(h', k) = e(s'v, g_2)$ 通过，则说明凭证有效。

多属性凭证

授权者的密钥对变成：

        $sk = (x, y_1, \cdots, y_q),  vk = (g_2, g_2^x, g_2^{y_1}, \cdots, g_2^{y_q})$

其中 $q$ 为属性的个数，多属性的凭证在 $c_m$ 中，群元素 $h$ 为：

        $c_m = g_1^o \prod_{j=1}^q h_j^{m_j},  h = H(c_m)$

广义的凭证即为：

        $\sigma = (h, h^{x+\sum_{j=1}^q m_j y_j})$

凭证总是由两个群元素组成，并不随着属性个数或授权者个数变化。

应用场景

Coin Tumbler

Coin Tumbler 可以用来实现匿名支付：

Coconut 签名用来实现Coin Tumbler 的流程为：

用户首先向合约进行存款，其中金额的数量 $v$ 作为公开属性，私钥 $k$ 和随机数 $s$ 作为私有属性；
授权者监控到请求，并分别给用户颁发凭证；
用户聚合部分的凭证，对其进行重新随机化，生成零知识证明，绑定到Merchant 的地址 $addr$ ；
Merchant 提交证明和凭证和群元素 $\zeta = g_1^s \in \mathbb{G}_1$ ，其中 $\zeta$ 用来防止双花；
合约验证证明和凭证后，若有效，则将 $v$ 代币转给 Merchant.

在上述过程中，Merchant 并不知道用户的地址身份，实现匿名性。

Privacy-perserving petition

Coconut 签名实现匿名投票的流程为：

用户首先向授权者 proof of identity，授权者检查其身份，对用户私有属性 k 发布一个盲签名，签名只需要生成一次，作为用户长期的身份凭证；
任意第三方可以创建一个新的投票的实例，通过标识符 $g_s \in \mathbb{G}_1$ ;
为了进行投票，用户计算值 $\zeta = g_s^k$ ，并生成零知识证明，以确定 $\zeta$ 是由 $k$ 计算得到， $\zeta$ 用来防止重复投票；
合约对用户的证明验证通过后，执行用户的投票结果。

Censorship-resistat distribution of proxies

代理常常用来绕过审查，但是却总是成为审查的目标，可以基于Coconut 签名方案实现抗审查的分布式代理方案。

代理者 V 首先通过获取一个临时公钥 $pk'$ ，并向授权者提供身份证明，获取关于私有属性 $pk'$ 和有效期 $\delta$ 的凭证；
V 将凭证注册到代理合约中，并提供零知识证明验证凭证的有效性；
用户监控区块链上的注册合约，当发现某个注册时，可以发布请求信息；
代理监控到链上的请求信息时，可以和用户发起连接，同时提供关于自身身份的零知识证明；
用户验证证明后，获取代理的IP地址和有效期，然后可以通过代理转发数据。

上述方案中，用户无法将代理的IP地址和长期使用的公钥关联在一起，实现代理的匿名性。

限制

对于授权者重新加入或退出需要重新进行密钥生成，来源于Shamir 秘密分享方案的限制，可以通过 Herzberg 方案解决；
若恶意授权者数量超过 $t$ ， Coconut 面临被攻击风险；
用以太坊合约实现Coconut 方案代价较大，因为EVM没有 $\mathbb{G}_2$ 实现的预编译合约，可以通过交换 $\mathbb{G}_1$ 和 $\mathbb{G}_2$ 的位置实现。