概述

Zerocash是Zerocoin团队开发的新的加密货币，在Zerocoin的基础上进一步增强了隐私性

比特币作为第一个广泛使用的加密货币，尽管其支付过程是匿名的，但是无法提供强大的隐私保障，因为所有的交易记录在公共分布式账本中，从中可以推断出很多信息

2013年Miers等人提出了Zerocoin，通过断开交易与支付来源的链接来解决一些隐私问题，但是zerocoin仍然会现实目的地址和交易金额，且功能有限

因此Zerocoin的团队利用zk-SNARKs的最新进展构建了一个完整的基于分布式账本的数字货币，并制定和构建了分布式匿名支付方案（Decentralized Anonymous Payment Schemes，DAP），DAP允许用户直接或私下支付，同时可以隐藏交易的源地址、目的地址和交易金额

此外该团队还基于构建了DAP的实例zerocash，交易块和验证时间比zerocoin提高了几个数量级

背景介绍

比特币升值的原因是其无需中央银行（无需可信方），而是采用区块链作为分布式账本来存储用户之间的交易

因为区块链被相互不信任的对等方大量复制，这意味着区块链上的信息是公开的，尽管用户可能会使用多个身份（伪造身份）来增强其个人隐私，但是部分工作$[RM11,BBSU12,RS12MPJ+13]$表明，任何人都可以使用区块链上的信息来去除比特币的匿名性，如分析交易区块的结构和交易日期，以至于比特币难以做到隐私（传统支付用纸币交易都可以保持匿名性）

尽管比特币本身不匿名，但是部分有动机的用户可以通过mixes（或称为laundries或tumblers）操作来混淆他们的交易历史，因为mix允许用户将一组币委托给一个由中心运营的币池，一段时间后用户再从币池中取回等价的币

不过mix操作由一些限制，如

  • 取回币这个行为的延迟必须很大，若延迟很小，则混合的币太少，达不到需要的隐私性
  • 进行mix的操作员可以追踪混合的币
  • 中心可能会在混合过程中偷币（CoinJoin$[Max13]$给出了关于偷币问题的一些解决方案）

虽然说对于有需要隐藏信息的用户，这些问题也都还行，但是对于那些正常的合法用户，他们希望隐藏自己的消费习惯，避免让同行知道，同时还不希望有持续的投入（比如花钱等开销）来保护自己的隐私，而且大多数情况下用户并没有充分的意识到自己的隐私已受侵害

基于此，用户需要一种即时的、无风险的，而且需要自动保证隐私的方案，确保其他人无法从公开的信息中获取到用户数据

匿名交易还需要确保币的市场价值独立于历史，从而确保合法用户的硬币仍然可以替换

Zerocoin：分布式混合

Miers等人$[MGGR13]$在2013年提出了Zerocoin，通过扩展比特币来提供匿名性，并使用零知识证明来防止对交易的分析

区别于其他加密货币，Zerocoin不以数字签名来验证币的合法性，也不需要中央银行来防止双花，而是通过零知识证明的方式证明某个币属于有效的币的列表（该列表可在区块链上维护）

不过Zerocoin还不是一个成熟的匿名货币，而是一种分散的混合货币，用户可通过Zerocoin协议定期清洗他们的比特币

出于下列原因，日常的交易需要通过比特币进行

  1. 性能：Zerocoin交易大小超过45KB，在安全级别为128位时需要超过450ms的验证时间，代价过高以至于会对正常的比特币网络造成影响
  2. 功能性：缺乏成熟的匿名支付需要的关键功能，Zerocoin采用固定面值的币，无法做到精确支付，也无法在交易后进行兑换（如分割币），而且Zerocoin也没有可以使得用户再Zerocoin中支付给另一个用户的机制
  3. Zerocoin仅隐藏了交易的源地址，目的地址和交易金额还是可以看到

本文贡献

主要有两个

  1. 引入去中心化匿名支付方案的概念，该方案具有强大匿名性保证的完整去中心化电子货币的功能和安全保证，此外给出了该原语的构造，利用了ZKP的最新进展zk-SNARKs
  2. 实现了Zerocash，安全性为128位，将Zerocoin的交易量和事物的验证时间进一步减少，并且允许金额可变的匿名交易，允许隐藏交易金额和用户持有的币的价值，允许用户直接向固定地址付款（无需交互

1.1 zk-SNARKs

一种简洁的非交互式零知识知识证明，具体可以看之前的系列文章，这里给出论文里面的精确定义

设$\mathcal L$为NP语言，$C$为$L$上大小为$n$的非确定性判断回路，此时zk-SNARK可用于证明和验证$L$中的成员关系

将$C$作为输入后，可信方执行一次初始设置，并生成一对公钥$(pk,vk)$，证明密钥$pk$使得任何（包括不可信的）Prover都能够为其选择的$x$（大小为$n$）生成一个证明$\pi$，满足$x\in \mathcal L$，而证明$\pi$是零知识的且是知识证明

任何人都可以用验证密钥$vk$来验证$\pi$，无需与生成$\pi$的Prover进行交互

简洁性要求$\pi$具有恒定的大小，也即要求$\pi$是关于$|x|$的线性阶，而不是关于$|C|$的线性阶

1.2 Centralized anonymous payment systems

回顾一下两种方案，两种方案都依赖于中央可信方

Anonymous e-cash

1982年Chaum$[Cha82]$提出，该方案中币的铸造涉及用户Alice和银行，若需要铸造价值为$v$的币，首先由Alice选择一个币序列号$sn$（银行不知道），之后银行从Alice账户余额中扣除$v$后，通过盲签名对$sn$进行签名

若Alice希望把币转给Bob，则Alice需要向Bob透露$sn$并证明$sn$是由中央银行签名的，该过程中Bob和银行都无法通过透露的信息推断Alice的身份

此外银行不会兑现已经出现的$sn$的币，从而避免了双花

Unforgeable e-cash

Chaum的方案存在一个问题，若银行密钥泄露了，则敌手可以利用银行密钥伪造硬币

Sander和TaShma$[ST99]$对此进行了改进，该方案中，银行维护一个币承诺（Coin Commitment，CM）的 公共Merkle Tree，用户会定期检查其树根$rt$，此时银行无需保存任何秘密

该方案中，当Alice请求一枚币（单位值）时，其选择一个随机序列号$sn$和辅助字符串$r$，计算$cm=CRH(sn||r)$并发送到银行（CRH表示抗碰撞哈希函数），银行从Alice账户中扣除对应的余额后，将$cm$作为Merkle Tree的一个叶节点

之后若Alice希望向Bob付款，此时Alice会向Bob发送$sn$一个NP语句的零知识证明$\pi$：存在一个$r$，满足$cm=CRH(sn||r)$是以rt为根的Merkle Tree的一个叶节点，也即Alice通过零知识让Bob相信$sn$是对应的Merkle Tree中某个币承诺中包含的序列号

由于采用的是零知识证明，因此Bob不会知晓到底哪个硬币是Alice的，从而保护了Alice的身份

可替代的匿名分布式系统

对于本文的方案，与$[ST99]$一样将币的序列号进行散列，并采用Merkle Tree表示铸币集

与$[ST99]$不同的是，本文的方案还确保币值的隐私，同时支持拆分和合并币的事务，从而实现（并实施）完全可替代的和可分割的支付方案

本文的方案与比特币一样不依赖于中央银行（上述两个都需要），因此需要一套新的定义和协议来保护Alice的匿名性，同时防止在增强隐私保护下打破平衡性

1.3 分布式匿名支付方案

Decentralized Anonymous Payment schemes，DAP，允许任意金额的直接匿名支付的分布式电子现金方案，正式定义在第三章

该方案基于任意分类帐的基础货币而构建，在任意时刻，所有用户都可以使用分类账的唯一有效快照

本文的方案中的事务支持基础的货币交易，同时引入了新的事务，具体可以看一下附录A的比特币和Zerocoin，接下来简单介绍一下大概的方案框架

步骤1：固定价值硬币的用户匿名性

首先描述一个简化的结构，假设所有币的价值都相同（比如都是1 BTC），这个结构和Zerocoin类似，接下来展示如何隐藏支付源地址，具体采用了zk-SNARKs和承诺方案

记$COMM$为一个统计隐藏的非交互式承诺方案（给定消息m和随机性r，承诺值为$c=COMM_r(m)$，通过揭示m和r可以验证$COMM_r(m)=c$）

简化构造中，新币c铸造方式如下

  1. 用户$u$选择一个随机序列号$sn$和陷门$r$，计算币承诺$cm=COMM_r(sn)$，令$c=(r,sn,cm)$
  2. 当$u$向托管币池支付了1 BTC时（可以通过$tx_{Mint}$编码的明文信息支付），$cm$会被包含到铸币事务$tx_{Mint}$中（不包含$sn$和$r$）并记录到账本

此时交易的存单即为$tx_{Mint}$，价值来源于支持池（backing pool）

之后记$CMList$为账本中所有币承诺的列表，用户$u$可能会发布一个事务$tx_{Spend}$来花费币$c$，事务$tx_{Spend}$包含下列内容

  • 币的序列号$sn$
  • NP语句的zk-SNARKs证明$\pi$，用于证明其知道一个$r$，满足$COMM_r(sn)$出现在$CMList$的承诺列表中

假设$sn$没有出现在账本中（作为过去交易的一部分），用户$u$可以赎回1 BTC的币，此时可以保留、转账给他人或铸造新币，若$sn$已经出现在账本上，则会被视为双花，则该交易被丢弃

上述过程中对用户的匿名实际上是由零知识证明$\pi$实现的，由于$sn$揭示时并没有关于$r$的信息，且在$CMList$中找到与特定支出事务$tx_{Spend}$，等价于找到函数$f(x)=COMM_x(sn)$，根据承诺方案的性质，这是不可能的，从而该笔交易的来源是匿名的

步骤2：压缩币承诺列表

在上述NP陈述中，$CMList$作为币的承诺列表，但是由于大多数协议算法（如证明与验证算法）的时空复杂性会随着$CMList$的增大而线性增长，从而导致其扩展性较差，此外对于已使用的币，其对应的币承诺不能从$CMList$中删除，导致$CMList$会不断增大，若将币承诺删除了就无法被正确识别

因此本文和$[ST99]$中一样，依赖一个抗碰撞函数$CRH$来避免$CMList$的显式表示，本文的方案是在CMList上维护一个高效可更新的、仅附加的基于CRH的Merkle Tree，记为$Tree(CMList)$，并记其树根为$rt$

根据Merkle Tree的特性，$rt$是可更新的，从而插入新的叶节点的时空复杂性仅与Merkle Tree的深度相关，这样就可以把维护CMList的时空代价从线性阶降低到对数阶

不过此时为了确保协议的完备性，需要修改一下之前的NP语句为：我知道r，满足$COMM_r(sn)$是根为$rt$的$Tree(CMList)$上的一个叶节点

与$CMList$的原始数据结构相比，这种修改成倍地增加了给定zk-SNARK实现可以支持的$CMList$的大小（比如说，若采用深度为64的Merkle Tree，则Zerocash可以支持$2^{64}$枚硬币）

步骤3：将币扩展至可直接匿名支付

根据上面两步提到的，对币c的承诺实际上是对币序列号sn的承诺

接下来思考一个问题，若用户$u_A$创建了一个币$c$并发送给了另一个用户$u_B$，由于$u_A$知道$sn$，且$u_B$花费$c$不是匿名的（因为$u_A$通过识别Merkle Tree上的$sn$看到$c$何时被花费），也存在很大的风险（尽管$u_A$将c发送给了$u_B$，但是$u_A$仍然可以先花费$c$）

不难看出，上述的方案存在下列问题

  1. 为了防止这种情况，$u_B$必须立即花费$c$并铸造一枚新币$c'$来防止这种情况发生
  2. 若$u_A$希望转账更多的币（比如100 BTC）给$u_B$，这么做的话既不方便（需要操作100次），也不匿名（因为转账的数量不受隐私保护）
  3. 不支持金额不是1 BTC的整数倍的转账，比如$u_A$希望转账给$u_B$0.5 BTC，上述方案不支持

为了解决这个问题，继续修改币承诺，采用伪随机函数来定位交易和推导序列号$sn$，记伪随机函数的种子为x，然后引入三个伪随机函数$PRF^{addr}_x(\cdot)$、$PRF^{sn}_x(\cdot )$和$PRF^{pk}_x(\cdot )$，同时假设$PRF^{sn}$还具有抗碰撞性

此外，为了指定支付的目标，引入地址密钥对$(a_{pk},a_{sk})$，分别表示用户的地址公钥和地址私钥，此时用户u的硬币会包含$a_{pk}$，而只有了解$a_{sk}$的用户才有权力使用这个币

地址密钥对的数量：通过选择随机种子询问并设置$a_{pk}=PRF^{addr}_{a_{sk}}(0)$，用户可以生成和使用任意数量的地址密钥对

为了解决第三个问题，需要重新设计铸币协议来实现更强大的功能

若用户希望造出价值为$v$的币$c$，用户$u$首先随机选择一个值$\rho$（该值保密），然后$u$利用来计算币的序列号$sn=PRF^{sn}_{a_{sk}}(\rho)$，之后$u$以下列两种方式对$(a_{pk},v,\rho)$这三个值进行承诺

  1. $u$选择一个随机值$r$，计算$k=COMM_r(a_{pk}||\rho)$
  2. $u$选择随机值$s$，计算$cm=COMM_s(v||k)$

此时铸币的结果为一个币$c=(a_{pk},v,\rho,r,s,cm)$与一个铸币事务$tx_{Mint}=(v,k,s,cm)$

由于币承诺$cm$是嵌套承诺，任何人都可以验证$tx_{Mint}$中的$cm$对应的币的价值为$v$（验证$COMM_s(v||k)=cm$），但由于币序列号$sn$来源于$u$选择的随机值$\rho$，且$sn$与$u$的地址公钥一同隐藏在承诺值$k$中，因此任何人都无法识别这个币的所有者

和之前一样，只有存入正确的金额时，账本才会接受$tx_{Mint}$事务，此时生成的币的价值为$v$
铸币完成后，币会通过$pour$操作进行消耗，该操作会将一组币作为输入并将它们消费，同时将这些币的价值"pour"到一组新的币中，这样一来可以确保输出的币的总值等于输入币的总值

比如，假设有地址密钥对$(a^{old}_{pk},a^{old}_{sk})$，$u$希望花费他的硬币$\boldsymbol c^{old}=(a^{old}_{pk},v^{old}, \rho^ {old},r^{old},s^{old},cm^{old})$，同时生产出两个新的硬币$(c^{new}_1,c^{new}_2)$，且满足$v^{old}=v^{new}_1+v^{new}_2$（新的币值分别对应密钥$a^{new}_{pk,1},a^{new}_{pk,2}$，这两个密钥可能属于$u$，也可能属于其他用户）

接下来$u$对$i\in \{1,2\}$，进行如下操作

  1. 生成一个随机数$\rho^{new}_i$
  2. 利用随机值$r^{new}_i$，计算$k_i^{new}=COMM_{r_i^{new}}(a^{new}_{pk,i}||\rho^{new}_i)$
  3. 利用随机值$s_i^{new}$计算承诺值$cm_i^{new}=COMM_{s_i^{new}}(v_i^{new}||k_i^{new})$

然后$u$可以得到新币$c_1^{new}=(a^{new}_{pk,1},v^{new}_1,\rho_1^{new},r_1^{new},s_1^{new},cm_1^{new})$和$c_2^{new}=(a^{new}_{pk,2},v^{new}_2\rho_2^{new},r_2^{new},s_2^{new},cm_2^{new})$
之后$u$为下列NP语句生成一个zk-SNARKs证明$\pi_{\mathtt {POUR}}$，称之为$\mathtt {POUR}$

给定Merkle Tree的树根$rt$，序列值$sn^{old}$和币承诺值$cm_1^{new},cm_2^{new}$，我知道币$c^{old},c_1^{new},c_2^{new}$和地址私钥$a_{sk}^{old}$，满足

  • 币满足特定的格式：对于$c^{old}$，满足$k^{old}=COMM_{r^{old}}(a^{old}_{pk}||\rho^{old}),cm^{old}=COMM_{s^{old}}(v^{old}||k^{old})$，$c_1^{new},c_2^{new}$同理
  • 地址私钥$a^{old}_{pk}$：满足$a^{old}_{pk}=PRF^{addr}_{a^{old}_{sk}}(0)$
  • 序列号正确：满足$sn^{old}=PRF^{sn}_{a^{old}_{sk}}(\rho^{old})$
  • 币承诺$cm^{old}$出现在根为$rt$的Merkle Tree的叶节点上
  • 满足$v^{old}=v^{new}_1+v^{new}_2$

此时会生成一个pour事务$tx_{Pour}=(rt,sn^{old},cm_1^{new},cm_2^{new},\pi_{\mathtt {POUR}})$并附加到账本中（和之前一样，如果序列号$sn$出现在前一笔交易中，交易将被拒绝）

现在假设$u$不知道与地址公钥$a^{new}_{pk,1}$关联的地址私钥$a^{new}_{sk,1}$，此时$u$不可以花费$c_1^{new}$，因为她不能提供地址私钥$a^{new}_{sk,1}$作为后续pour操作的证据，此外若知道地址私钥$a^{new}_{sk,1}$的用户花费了$c_1^{new}$这个币，$u$也无法追踪该用户，因为$u$不知道该币的序列号（$sn_1^{new}=PRF^{sn}_{a^{new}_{sk,1}}(\rho_1^{new})$，u不知道$a^{new}_{sk,1}$，意味着其不能得到正确的序列号）

还需要注意的是，$tx_{Pour}$没有显示有关被消费的硬币的价值如何在两个新硬币之间分配的信息，也没有显示与被消费硬币的对应的硬币承诺，也没有显示两个新硬币的目标地址公钥，整个操作完全匿名进行

更一般地说，一个用户可能会pour$N^{old}\geq 0$个币至$N^{new}\geq 0$个币中，假设$N^{old}=N^{new}=2$，不失一般性，对于$N^{old}< 2$而言，用户可以铸一个新的币值为0的币并将其作为空输入，而对于$N^{new}< 2$而言，用户可以创建（并丢弃）一枚值为0的币，对于$N^{old}\geq 0$或$N^{new}\geq 0$而言，用户可以组合$\log N^{old}+\log N^{new}$作为两个输入/两个输出的pour

步骤4：发送币

假设$a^{new}_{pk,1}$为用户$u_1$的地址公钥，为了使得$u_1$可以正确的花费$c_1^{new}$，$u$必须以某种方式将$c_1^{new}$中的秘密值发送给$u_1$

一种方式是$u$给$u_1$发送一条私密消息，但这需要隐秘信道（意味着需要额外的基础设施或假设），为了避免这种带外信道，而是通过利用分类账将这种能力直接构建到我们的构建中，如下所示

修改一下地址密钥对的结构，现在每个用户有一个密钥对$(addr_{pk},addr_{sk})$，其中$addr_{pk}=(a_{pk},pk_{enc}),addr_{sk}=(a_{sk},sk_{enc})$，其中$(a_{pk},a_{sk})$和上面提到的一样，而$(pk_{enc},sk_{enc})$为私有密钥加密方案的密钥对$[BBDP01]$

接下来$u$计算密文$\boldsymbol C_1$，$\boldsymbol C_1$是对明文$(v_1^{new},\rho_1^{new},r_1^{new},s_1^{new})$在密钥$pk^{new}_{enc,1}$下的加密，同时将$\boldsymbol C_1$包含至pour事务$tx_{Pour}$，用户$u_1$可以在公共账本上扫描pour交易并利用密钥$sk^{new}_{enc,1}$解密该消息，根据私有密钥加密方案的性质，将$\boldsymbol C_1$包含至pour交易$tx_{Pour}$时没有泄露交易的额度和目标地址（$u$对$c_2^{new}$的操作同理）

步骤5：公共输出

到目前为止的方案允许用户铸造、合并和分割硬币，为了支持用户兑换一枚币（也即将其兑换回基础货币，如比特币等），继续修改pour操作以包含公共输出

当花费币时，用户$u$同样可以指定一个非负的值$v_{pub}$和一个交易串$info\in \{0,1\}^*$，此时NP语句中的的等式变为$v^{old}=v^{new}_1+v^{new}_2+v_{pub}$，此时在输入值$v^{old}$中，一部分$v^{pub}$被公开声明，$v^{pub}$的目标以某种方式由字符串$info$指定，字符串信息可用于指定这些赎回资金的目的地址（例如，比特币钱包公钥）

$v_{pub}$和$info$可以作为pour事务的信息包含在事务$tx_{Pour}$中（公共输出是可选的，因为用户可以设置$v_{pub}=0$）

步骤6：非延展安全性

为了防止对pour事务$tx_{Pour}$的延展性攻击（通过修改信息来重新定位pour的公共输出而盗用币）

具体而言，在pour操作中，用户$u$进行如下操作

  1. 生成一个一次性签名方案的密钥对$(pk_{sig},sk_{sig})$
  2. 计算$h_{sig}=CRH(pk_{sig})$
  3. 计算$h_1=PRF^{pk}_{a^{old}_{sk,1}}(h_{sig}),h_2=PRF^{pk}_{a^{old}_{sk,2}}(h_{sig})$，这两个值作为MAC，将$h_{sig}$绑定至两个地址私钥
  4. 修改$\mathtt{POUR}$，加入$h_{sig},h_1,h_2$三个值，并证明后两个值被正确计算
  5. 利用签名私钥$sk_{sig}$对于pour相关的每个操作签名，得到一个签名值$\sigma$，该签名与$pk_{sig}$一起包含到$tx_{Pour}$中

注意到$a^{old}_{sk,i}$保密，且对于pour事务而言，$h_{sig}$的变化是高概率的，因此$h_1,h_2$是不可预测的，更进一步的，对于该NP陈述（以及其他值）的签名将所有的这些信息绑定在一起，（具体看附录C和D）

小结

综上，结构的概述到此为止，下图对上述内容进行了一个总结

最后，注意到由于利用了zk-SNARK，这个构造需要一次性的trusted setup作为公共参数，证明的合理性取决于这个trust，即便是恶意的敌手破坏了trusted setup，匿名性仍然成立

1.4 Zerocash

接下来的内容会概述DAP方案构造的一个具体实现，称为Zerocash，其安全性为128位（详见论文第五章）

尽管zk-SNARK是渐近有效的，但它的具体效率取决于用于确定NP语句的算术电路$C$来验证NP语句的实例

本文的方法是基于SHA256实例化所有必要的密码成分（承诺方案、伪随机函数和抗冲突哈希），我们首先设计一个手动优化的电路，用于验证SHA256计算，然后使用这个电路来构造$C_{\mathtt {POUR}}$，该电路验证满足NP语句$C_{\mathtt {POUR}}$的所有必要检查

通过合适的参数选择，以及用于算术电路$[BCTV14]$的zk-SNARK最先进的实现（具体见论文第2.4节），使得zk-SNARK验证程序的运行时间为几分钟，zk-SNARK验证程序的运行时间可以降低至几毫秒

后记

有点长，慢慢看吧，感觉零知识证明还是挺有意思的

本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正

参考文章

$[1]$[Zerocash: Decentralized Anonymous Payments from Bitcoin
(extended version)](http://zerocash-project.org/media/pdf/zerocash-extended-20140518.pdf)