Zerocoin: Anonymous Distributed E-Cash from Bitcoin

比特币交易日志是完全公开的，仅通过使用假名来保护用户的隐私，在隐私方面却存在重大限制。Zerocoin，增强了协议是实现了完全匿名的货币交易。

简介

比特币是完全去中心化的，不需要中央银行或权威机构，它的安全性取决于分布式体系结构和两个假设：其大多数节点是诚实的和实质性的工作量证明可以阻止Sybil攻击。 分散的设计是比特币成功的原因，但付出一定的代价：所有交易都是公开的，并在密码绑定的假名之间进行。

解决办法是使用洗衣服务 (a\ laundry \ service ) 来交换不同用户的比特币。 但是，这些服务具有严重的局限性：运营商可以窃取比特币，追踪比特币，或者干脆倒闭，将用户的比特币带走。认识到这些风险，许多服务提供了较短的洗涤时间，这导致最小的交易量并因此限制了匿名性。

贡献

描述了Zerocoin，这是一种分布式电子现金系统 decentralized\ e-cash \ scheme，该系统使用加密技术来中断单个比特币交易之间的链接，而无需添加可信方。 为此,首先定义一个称为 decentralized\ e-cash \ scheme 的新原语的抽象功能和安全要求。 接下来，我们提出一个具体的实例，并证明它在标准密码假设下是安全的。 最后，将协议集成到比特币系统中。

背后的直觉

“铅笔和纸”协议 (pencil\ and\ paper\ protocol)。 想象所有用户共享对物理公告板的访问权限。 为了铸造固定面额 $1 的零币，用户 Alice 首先生成一个随机的硬币序列号 S ，然后使用安全的数字承诺方案对 S 进行承诺。 最终的承诺是一个硬币，表示为 C，它只能用随机数 r 打开以显示序列号 S。Alice将 C 以及1美元的实物货币固定在公共公告板上。 只要结构正确且携带正确的货币金额，所有用户都将接受 C。为了兑换她的硬币C，Alice 首先扫描公告板，以获取到目前为止系统中所有用户都张贴的一组有效承诺 (C_1,...,C_N)。 接下来，她针对以下两个语句生成非交互式零知识证明 \pi：（1）她知道 C\in(C_1,...,C_N)，并且（2）她知道一个隐藏值 r，使得承诺 C 对 S 开放。Alice 伪装掩盖了自己的身份（匿名网络中进行，比如: Tor），发布了包含 (S,\pi) 的“支出” (“spend")交易。 其余用户验证证明 \pi 并检查 S 先前是否未出现在任何其他支出交易中。如果满足这些条件，则用户允许 Alice 从公告板上的任何位置收取 $1； 否则，他们拒绝她的交易并阻止她收取货币。

这个简单的协议实现了一些重要的目标。 首先，Alice 铸造的硬币不能与她的取款资金联系起来：为了将硬币 C 与取款时使用的序列号 S 相链接，一个人必须知道 r 或直接知道爱丽丝证明过的哪个硬币，而这两个都不可能实现。 同时，如果承诺和零知识证明是安全的，那么Alice 只有在重新使用序列号 S 的情况下花费任何硬币两次，这样被其他节点检测到。

去中心化电子现金

我们对比特币网络进行匿名处理的方法使用了一种加密的电子现金。 因为不需要中央硬币发行者，我们将其称为分散式电子现金方案 (decentralized\ e-cash \ scheme)。 在本节中，定义了构成分散式电子现金方案的算法，并描述了这种系统所需的正确性( correctness)和安全性 ( security)。

有关的符号定义

令 \lambda 表示可调整的安全参数，令 poly(.) 表示多项式函数，而 v(.) 表示可忽略的函数，用 \mathcal{C} 表示允许的硬币值集。

定义3.1 (Decentralized E-Cash Scheme):由随机算法(Setup, Mint, Spend, Verify) 构成的元组。

• Setup(1^\lambda)\rightarrow params. 输入安全参数 \lambda 后，输出一组全局公共参数 params 和对硬币集合 \mathcal{C} 的描述。
• Mint(params)\rightarrow (c,skc). 输入参数 params，输出硬币 c\in \mathcal{C} 以及陷门 skc。
• Spend(params,c,skc,R,C)\rightarrow (\pi,S). 给定 params，一个硬币 c，以及其陷门 skc，一些交易字符串 R\in\{0,1\}^*，和任意一组硬币 C，如果 c\in C\in \mathcal{C} 则输出由证明 \pi 和序列号 S 组成的硬币消费交易。否则输出 ⊥。
• Verify(params,\pi,S,R,C)\rightarrow \{0,1\}. 给定 params，证明 \pi，序列号 S，交易信息 R 和一组硬币 C，如果 C\in \mathcal{C} 和 (\pi,S,R) 有效，则输出 1。 否则输出 0。

我们注意到，Setup 可以由受信方执行。 由于此设置仅发生一次并且不会产生任何相应的秘密值，因此我们认为这种放松对于实际应用是可以接受的。 一些具体的实例可能使用不同的假设。

每个硬币都是使用随机铸造算法生成的。 序列号 S 是在花费比特币过程中释放的唯一值，旨在防止任何用户花费两次相同的比特币。 每次对 Spend 算法的调用都可以包含任意字符串 R，该字符串旨在存储特定于交易的信息（例如，交易接收者的身份）。

Correctness

每个分散式电子现金方案(Decentralized E-Cash Scheme)都必须满足以下正确性要求。 令 params\leftarrow Setup(1^\lambda)和 (c,skc)\leftarrow Mint(params)。令 C\in \mathcal{C} 是任何有效的硬币集，其中 |c|\leq poly(\lambda) 。并且 (\pi,S) \leftarrow Spend(params,c,skc,R,C) . 在上述算法中使用的所有 C，R 和随机硬币上，以下等式均以 1 −ν（λ） 的概率成立，则该方案是正确的： Verify(params, π, S, R, C ∪ \{c\})=1 。

Security

分散式电子现金方案(Decentralized E-Cash Scheme)的安全性由以下两个 games 定义：Anonymity and Balance。

Anonymity 实验

该实验可确保即使攻击者提供了许多用于生成支出(spend)交易的硬币，敌手也无法将给定的货币支出交易 (\pi,S) 与与交易对应的硬币关联起来。

定义3.2 (Anonymity)：如果每个概率多项式时间 （p.p.t.)敌手 \mathcal{A}=(\mathcal{A_1},\mathcal{A_2}) 在以下实验中的优势可以忽略不计，那么 Decentralized E-Cash Scheme Π= (Setup,Mint,Spqnd,Verify) 将满足匿名性要求。

Anonymity(Π, A, λ) :

params ← Setup(1^\lambda)

For\ \ i ∈ \{0,1\}: (c_i, skc_i) ← Mint(params)

(C, R, z) ← \mathcal{A_1}(params, c_0, c_1); b ← \{0, 1\}

(\pi,S)\leftarrow Spend(params,c_b,skc_b,R,C∪\{c_0,c_1\})

Output:b'\leftarrow \mathcal{A_2}(z,\pi,S)

定义在上述实验中 A’s advantage 为 |Pr [ b = b'] -1/2|.

Balance 实验

balance 属性确保了即使攻击者可以使用由诚实方产生的硬币和花费交易(spend transactions)，也不会花费比铸造更多的硬币。 攻击者也具有可以更改有效硬币的能力，例如，通过修改其交易信息字符串 R。我们为攻击者提供了有效硬币的集合以及他可能用来花费其中任何一个硬币的 oracle \mathcal{O}_{spend}。最终， \mathcal{A} 必须产生 m 个硬币和 m+1 个有效支出交易，以使任何交易都不能重复序列号或修改诚实的 oracle 产生的交易。

定义3.3 (Balance):如果 ∀N ≤ poly(λ) ，每个 p.p.t. 敌手 \mathcal{A} 在以下实验中的优势微不足道，那么 Decentralized E-Cash Scheme Π=(Setup,Mint,Spqnd,Verify) 将满足balance属性要求。

Balance(Π,\mathcal{A},N,\lambda) :

params ← Setup(1^\lambda)

For\ \ i = 1\ to\ N: (c_i, skc_i) ← Mint(params)

Output:(c_1',...,c_m',S_1,...,S_m,S_{m+1})\leftarrow \mathcal{A}^{\mathcal{O}_{spend(.,.,.)}}(params,c_1,...,c_N)

oracle\ \mathcal{O}_{spend} 操作如下：在 j_{th} 询问 \mathcal{O}_{spend(c_j,C_j,R_j)} ,如果 c_j \notin\{c_1,...,c_N\} ,输出 ⊥ 。否则，返回 (\pi_j,S_j)\leftarrow Spend(params,c_j,skc_j,R_j,C_j) 给 \mathcal{A} 并在集合 \mathcal{T} 中记录 (S_j,R_j) 。

我们说 \mathcal{A} 赢 (\mathcal{A} 花费了比铸造更多的硬币) 如果 ∀ \mathcal{s}\in\{S1,..., Sm, Sm+1\} 其中 s=(\pi',S',R',C') :

• Verify(params,\pi',S',R',C')=1
• C'\in\{c_1,...,c_N,c_1',...,c_m'\}
• (S',R')\notin \mathcal{T}
• S'仅出现在 \{S_1,...,S_m,S_{m+1}\} 中的一个元组中。

\mathcal{A} 的优势为 \mathcal{A} 赢得上面的游戏。

利用Strong RSA 构造 Decentralized E-CASH

密码学构造模块

零知识证明和知识签名

Schnorr 协议

累加器(Accumulators)

• 我们使用以下算法描述累加器：
• AccumSetup(\lambda)\rightarrow params. 输入安全性参数后，对素数p，q（与安全性参数多项式相关）进行采样，计算N = pq，并对种子值 u\in QR_N,u \neq 1 进行采样。输出(N,u)作为参数。
• Accumulate(params,C)\rightarrow A. 输入 params (N,u) 和一组质数 C=\{c_1,...,c_i|c\in[\mathcal{A},\mathcal{B}]\} ,计算累加器 A 等于 u^{c_1c_2...c_n}\ mod\ N 。
• GenWitness(params,v,C)\rightarrow \mathcal{w}. 输入 params (N,u) ，以及如上所述的一组质数 C 和值 v∈C ，见证人 w 是除 v之外 C 中所有值的累加，即 w = Accumulate(params ,c\backslash\{v\})。
• AccVerify(params,A,v,w)\rightarrow\{0,1\}. 输入 params (N,u)，元素 v 和见证 w，计算 A'≡ω^v\ mod\ N 。当且仅当A' = A，v 为素数且 v\in[\mathcal{A},\mathcal{B}] 如定义时，输出 1 。

如果Strong RSA假设很难，则累加器满足强的抗碰撞性能。 非正式地，这确保没有 p.p.t. 敌手可以产生一对 v(v,w) 使得 v\notin C 并且满足 AccVerify。 此外，它描述了一种有效的零知识证明，即承诺值存在于累加器中。 我们使用Fiat-Shamir变换将其转换为非交互式证明，并使用以下表示法引用生成的证明：

构造

现在描述一个具体的分散式电子现金方案(Decentralized E-Cash Scheme)。在Strong RSA和离散对数假设的困难性有效下，我们的方案是安全的，并且存在零知识证明系统。

算法描述如下：

• Setup(1^\lambda)\rightarrow params. 输入一个安全参数，运行 AccumSetup(1^\lambda) 获得值 (N,u) 。接下来生成素数 p,q 使得 w≥1 时 p = 2^wq + 1 。选择随机生成元 g,h 使得 \mathbb{G}=<g>=<h> 并且 \mathbb{G} 是 \mathbb{Z}_q^* 的子群。输出 params=(N,u,p,q,g,h) 。
• Mint(params)\rightarrow (c,skc). 选择 S,r \leftarrow \mathbb{Z}_q^* 并且计算 c \leftarrow g^Sh^r\ mod\ p 使得 \{c\ prime|c\in[\mathcal{A},\mathcal{B}]\} 。计算 skc=(S,r) ,输出 (c,skc) 。
• Spend(params,c,skc,R,C)\rightarrow (\pi,S). 如果 c\notin C 输出 ⊥ 。否则计算 A\leftarrow Accumulate((N,u),C) 和 w\leftarrow GenWitness((N,u),c,C) 。输出 (\pi,S) ，其中 π 包含以下知识的签名：

• Verify(params,\pi,S,R,C)\rightarrow \{0,1\}. 给定证明 π，序列号 S 和一组硬币 C，首先计算 A\leftarrow Accumulate((N,u),C) 。接下来，使用已知的公共值验证 π 是 R 上的知识签名。 如果证明成功验证，则输出1，否则输出0。

协议假定使用可信的设置过程来生成参数。 我们强调，在设置程序之后不再使用累加器陷门 (p,q)，因此在生成参数后可立即将其销毁。

安全性分析

定理4.1：如果知识的零知识签名在随机预言模型中在计算上为零知识，则 Π=(Setup,Mint,Spqnd,Verify) 满足匿名属性。

直觉上，结构的安全性源于以下事实：硬币承诺 C 是完全隐藏的承诺，签名证明 π 至少在计算上为零知识。 这两个事实确保了敌手在猜测花了哪枚硬币时的优势至多可以忽略不计。

定理4.2：如果在随机预言模型中的签名证明 π 是安全可靠的，强RSA问题很难解决，\mathbb{G} 上的离散对数问题很难解决，则 Π=(Setup,Mint,Spqnd,Verify) 满足Balance属性。

简而言之，该证明依赖于硬币承诺的绑定特性，以及 ZKSoK 的稳健性和不可伪造性以及累加器的抗碰撞性。我们表明，以不容忽视的优势赢得 Balance 游戏的对手也可以用来在承诺方案中找到冲突（允许我们解决离散对数问题）或在累加器中找到冲突（解决强RSA）。

与比特币整合

解决将分散式电子现金方案与比特币协议结合在一起时所面临的具体挑战。

为了铸造面额为 d 的零币 c，Alice 运行 Mint(params)→(c,skc) 并安全地存储 skc 。然后，她将 c 嵌入到花费d +fees 的经典比特币的比特币交易的输出中。一旦 mint 交易被接受到区块链中，c 就被包含在全局累加器 A 中，除非通过Zerocoin支出（即基本上将其存入托管账户），否则无法访问该货币。(注：在实现中，所有比特币都有一个固定值。 但是，我们可以通过同时运行不同的Zerocoin实例来支持多个值，所有实例共享同一组公共参数)

为了与 Bob 花费 c，Alice 首先构造了一个部分交易 ptx，该交易以无人认领的 mint 交易作为输入，并包含 Bob 的公钥作为输出。 然后，她遍历区块链中所有有效的 mint 交易，组装一组铸造硬币 C，然后运行 Spend(params,c,skc,hash(ptx),C)\rightarrow(\pi,S)。 最后，她通过将 (π,S) 嵌入 ptx 输入的 scriptSig(输入脚本) 中来完成事务。 此交易的输出也可以是另一个Zerocoin薄荷交易-此功能对于在同一区块链中运行的多个Zerocoin实例（即，具有不同面额）之间的价值转移很有用。

当此事务出现在网络上时，节点检查 Verify(params,π,S,hash(ptx),C)= 1，并检查 S 是否未出现在任何先前的事务中。 如果这些条件成立并且所引用的 mint 交易未声明为另一笔交易的输入，则网络将其视为有效，并允许 Alice 兑换比特币。

计算累加器

上面的结构实现要求验证程序在每次调用 Verify(...) 时重新计算累加器 A。 实际上，并不需要这么做。

首先，回想一下我们构造中的累加器可以增量计算，因此节点可以在到达时将新硬币添加到累加中。 为了利用这一点，我们要求任何节点挖掘一个新块，以将该块中的零硬币添加到前一个块的累加器中，并将所得的新累加器值存储在新块开始时的 coinbase\ transaction 中。我们称其为累加器检查点 (accumulator\ checkpoint) 。 其他节点在接受新区块进入区块链之前验证此计算。 如果在将块添加到链中时定期进行此验证，则某些客户端可以选择信任较旧（已确认）的块中累加器，而不是从头开始重新计算。

通过这种优化，Alice 不再需要为 c 计算累加器 A 和完整见证 w。 相反，她只能参考当前块的累加器检查点 (accumulator\ checkpoint) 并从其 mint 之前的检查点开始计算见证（而不是从T0开始），因为计算见证相当于累积 C \backslash \{c\}。

新交易类型

通过添加一条新指令来扩展比特币：ZERO-COIN\_MINT。 铸造零币会构造一个带有输出的事务，其输出的 scriptPubKey包含此指令和硬币 c。 收到此交易的节点应验证 c 是格式正确的硬币。 为了花费零币，Alice 构造了一个新的交易，该交易声称一些零币的 mint 交易作为输入，并具有一个包含（π，S）的 scriptSig 字段和一个对包含 π 中使用的累加器的块的引用。 验证者从引用的块中提取累加器，并使用它来验证支出，如前所述。

最后，我们注意到必须对交易进行签名，以防止攻击者简单地更改向谁付款。 正常的比特币交易包括 ECDSA签名，该签名由引用的输入的 scriptPubKey 中指定的密钥组成。 但是，对于任意零币上的一个支出交易，没有 ECDSA公钥。 相反，我们使用ZKSoK\ π 来签名交易哈希,要求我们将交易摘要包括在针对 Fiat-Shamir proofs 的挑战的哈希计算中。

Statekeeping and side effects

验证零币会改变比特币的语义：目前，比特币的状态保持仅根据交易和交易区块进行定义。 此外，通过散列的显式引用来完成对该状态的访问。另一方面，Zerocoin出于对匿名性的强烈要求，它处理存在的问题：该代币在如此铸造的代币集中，而其序列号尚未在已用序列号集中。我们在比特币交易处理中引入了 side effects。 处理一个 mint 交易会导致硬币被累积为 side effects。 处理 spend 交易会导致将硬币序列号添加到客户持有的支出序列号列表中。

对于硬币序列号，只能为每个客户保留完整的序列表，并且会产生存储该列表的（较小）开销，以及处理交易进入客户的所有可能方式的较大工程开销。累加器状态保持在累加器检查点内，客户端对每个接收到的块进行验证。