Coconut 签名方案

最近研究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$ 的位置实现。

参考

https://arxiv.org/pdf/1802.07344.pdf

https://github.com/asonnino/coconut

https://github.com/asonnino/coconut-chainspace

https://github.com/musalbas/coconut-ethereum

最后编辑于：2022.03.31 18:49:44

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 194,491评论 5赞 459
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 81,856评论 2赞 371
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 141,745评论 0赞 319
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,196评论 1赞 263
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,073评论 4赞 355
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,112评论 1赞 272
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,531评论 3赞 381
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,215评论 0赞 253
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,485评论 1赞 290
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,578评论 2赞 309
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,356评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,215评论 3赞 312
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,583评论 3赞 299
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 28,898评论 0赞 17
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,174评论 1赞 250
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,497评论 2赞 341
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,697评论 2赞 335