本文主要讲 I.Miers, C.Garman, et al. "Zerocoin: Anonymous distributed e-cash from bitcoin."2013 IEEE Symposium on Security and Privacy. IEEE, 2013.

论文学习笔记总结请看：

Abstract

比特币是第一个被广泛采用的电子现金系统。虽然比特币提供了新型金融互动的潜力，但它在隐私方面存在重大限制。具体地说，由于比特币交易日志是完全公开的，用户的隐私只有通过使用化名才能得到保护。在这篇文章中，我们提出了零比特币（\(Zerocoin\)），这是比特币的一个加密扩展，它对协议进行了扩充，以允许完全匿名的货币交易。我们的系统使用标准的密码假设，不会引入新的可信方，也不会以其他方式改变比特币的安全模型。我们详细介绍了零币的密码结构，它与比特币的集成，并从计算和对比特币协议的影响两个方面检查了它的性能。

I. Introduction

与许多提议的数字货币不同，比特币是完全去中心化的，不需要中央银行或权威机构。相反，它的安全性依赖于分布式架构和两个假设：它的大多数节点都是诚实的，并且大量的工作证明可以阻止\(Sybil\)攻击。 因此，比特币既不需要法律机制来检测和惩罚重复支出，也不需要选择、监控或监管可信的各方。这种去中心化的设计可能是比特币成功的原因，但它是有代价的：所有交易都是公开的，都是在具有密码约束力的化名之间进行的。

在此类交易的基础上，人们可以建立机制，部分或明确地确定被授权方(例如执法部门)的参与者。然而，要将此信息限制在授权方，我们必须首先将基础公共交易匿名。

（我的理解是这样这门技术就不再是一门被排斥的非法技术，而是一门用于在去中心化交易中保护用户隐私的好技术，它可以通过授权的方式来接收政府等部门监管，而对于大多数的普通用户而言保护了交易隐私）。

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

Our Contribution

描述了\(Zerocoin\)，这是一种分布式电子现金系统（\(decentralized \ e-cash \ scheme\)）它使用密码技术来打破个人比特币交易之间的联系，而不需要添加可信的各方。要做到这一点，我们首先定义一个新原语的抽象功能和安全需求，我们称之为非集中式电子现金方案。接下来，我们提出了一个具体的实例，并证明了它在标准密码假设下是安全的。最后，我们描述了将我们的协议集成到比特币系统中所需的具体扩展，并评估了从原始开源比特币客户端派生的原型实现的性能。

我们并不是第一个提出电子现金技术来解决比特币隐私问题的人。然而，许多电子现金协议的一个共同问题是，它们基本上依赖于受信任的货币发行商或“银行”，使用盲签名方案创建电子“硬币”。而比特币网络模型由许多经常进出网络的不可信节点组成。此外，选择长期信任方的问题，尤其是在比特币运营的法律和监管灰色地带，似乎是采用比特币的主要障碍。\(Zerocoin\)通过允许个人比特币客户生成自己的硬币，从而消除了对此类硬币发行者的需求——前提是他们有足够的经典比特币来这么做。

Intuition Behind Our Construction

“铅笔和纸”协议（\(pencil\ and\ paper\ protocol\)）。

仅是该方案在现实生活中的形象化的例子。由此需求来引出，在现实生活中要想实现这个例子，最好的方法就是利用区块链比特币这门现成的技术。

First Contribution

我们工作的第一个也是最基本的贡献是认识到比特币解决了所有这些问题，为我们提供了支持货币、公告牌和有条件的货币兑换机制。事实上，比特币协议的核心是对块链的分散计算，它充当了一个可信的、仅限附加的公告牌，既可以存储信息，又可以处理金融交易。\(Alice\)可以添加她的承诺和托管资金，方法是将它们放在区块链中，同时确保严格的协议条件(而不是她的同事的顾虑)决定何时可以访问她承诺的资金。

Second Contribution

当然，即使与比特币区块链集成，上述协议还有另一个实际挑战。具体地说，很难有效地证明承诺\(C\)在集合\((C_1，…，C_n)\)中。

通过一笔交易将一个共享状态锁定在区块链上，从而在交易两方之间建立了一个状态通道。这被称为资金交易或锚点交易。这笔交易必须传送到网络并被挖矿以建立通道。在支付通道的示例中，锁定的状态即为通道的初始余额（以货币计）。随后双方交换已签名的交易，这被称为 “承诺交易(commitment transactions)”，承诺交易会改变初始状态。这些交易都是有效的，任何一方都可以提交结算的请求，不需要等到通道关闭再做结算。任何一方给对方创建、签名和发送交易时就会更新状态。当交换承诺交易时，双方同时废止之前的状态，如此一来最新的承诺交易总是唯一可以赎回的交易。这样可以防止任何一方在通道中某个先前状态比最新状态更有利于己方的时候通过单方面关闭通道来进行欺骗。我们将在本章的其余部分中检验可用于废止先前状态的各种机制。

这里主要讨论了挨个析取判断存在性（ \(OR\ proofs\) ）的时间复杂度是 \(O(n)\),而使用一个 “公共的”单向累加器 \(A\) ( \(“public” \ one-way\ accumulator\) )来减小这个证明的大小至 \(O(log \ N)\)，甚至常数级。

在第四节的具体建议中，我们使用基于Camenisch和Lysyanskaya的强RSA累加器( \(Strong \ RSA \ accumulator\) )的构造，而强RSA累加器又基于Baric和Pfitzmann的累加器以及Benaloh和de Mare的累加器。

Outline of This Work

在第二节中，我们将简要介绍比特币协议的技术概述。在第三节中，我们正式定义了分散式电子现金的概念，并提供了这种系统的正确性和安全性要求。在第四节中，我们给出了一个基于标准密码硬度假设的方案的具体实现，包括离散对数问题和强RSA。最后，在第五节、第六节和第七节中，我们描述了如何将我们的电子现金结构集成到比特币协议中，讨论了所提供的安全性和匿名性，并给出了详细的实验结果，表明我们的解决方案是可行的。

II. Overview of Bitcoin

在本节中，我们将简要概述比特币协议。有关更详细的解释，我们建议读者参考Nakamoto的原始规范或Barberet等人的摘要。

The Bitcoin Network

比特币是一个由分发和记录交易的节点以及用于与网络互动的客户端组成的点对点网络。比特币的核心是区块链，它是一个由比特币同行以分布式方式维护的仅限附加的公告牌。区块链由一系列以哈希链连接的区块组成。每个比特币区块都记录了从比特币广播网络收集的一组交易。

比特币为挖掘新区块的同行提供了两种不同的激励措施。首先，成功挖掘一个新的块(这需要大量的计算投资)使创建者有权获得奖励，目前设置为25BTC。其次，挖掘块的节点有权从它们包含的每个事务中收取交易费。特定交易支付的费用由其作者决定(尽管矿商可以排除费用不足的交易或优先处理高额费用的交易)。

比特币规范认为，挖出新区块的奖励应该每4年减少一次，最终完全取消。

Bitcoin Transactions

比特币交易由一组输出和输入组成。每个输出由元组 \((a，V)\) 描述，其中 \(a\) 是以 \(Satoshi(one\ bitcoin\ =\ 10^9\ Satoshi)\) 计价的金额，\(V\) 是谁被授权花费该输出的说明。此规范(表示为 \(scriptPubKey\) )是用比特币脚本( \(Bitcoin\ script\) )给出的，这是一种类似于 \(Forth\) 的基于堆栈的非图灵完成语言。

事务输入只是对前一个事务输出的引用，以及第二个脚本 \(scriptSig\)，其中包含代码和数据，当与 \(scriptPubKey\) 结合使用时，这些代码和数据的计算结果为 true。\(Coinbase\) 交易从每个区块开始，并向创建者支付费用，不包括交易输入。

为了向 \(Bob\) 发送 \(d\) 个比特币，\(Alice\) 将 \(Bob\) 的 \(ECDSA\) 公钥 \(pk_b\) 的散列、数量 \(d\) 和一些脚本指令嵌入 \(scriptPubKey\) 中，作为其引用的输入总共至少 \(d\) 个比特币的事务的一个输出。由于任何多余的输入都作为交易费支付给将其包含在块中的节点，因此 \(Alice\) 通常会添加第二个输出，将剩余的变化返还给她自己。一旦交易被广播到网络并包括在块中，比特币就属于 \(Bob\)。然而， \(Bob\) 应该只考虑硬币一次，他的至少五个后续块引用此块。\(Bob\) 可以在交易中使用这些硬币，方法是将其作为输入引用，并在 \(scriptSig\) 中包括 \(sk_b\) 和公钥 \(pk_b\) 下的认领交易上的签名。

Anonymity

匿名不是比特币的设计目标之一。比特币只通过使用比特币身份(公钥或其散列)提供假名，其中一个比特币用户可以产生无限数量。事实上，许多比特币客户经常会产生新的身份，以保护用户的隐私。
不管比特币的设计目标是什么，比特币的用户群似乎愿意付出相当大的努力来保持自己的匿名性，包括拿自己的钱冒险和支付交易费用。这方面的一个例子是，存在一些洗衣店(收取一定费用) ，它们将不同用户的资金混合在一起，希望通过洗钱使它们难以被追踪。因为这种系统要求用户信任洗衣房（ \(laundry\) ）：

• 不记录混合过程；
• 将用户投入的钱还给洗衣房，因此使用这些系统涉及相当大的风险。

III. Decentralized E-Cash

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

Notation

设 \(λ\) 表示一个可调安全参数，\(poly(·)\) 表示某个多项式函数，\(ν(·)\) 表示一个可忽略函数，用 \(\mathcal C\) 表示允许的硬币值集。

Definition 3.1

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

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

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

Correctness

Security

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

Anonymity Experiment

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

Definition 3.2

定义3.2( \(Anonymity\) )：

\(probabilistic \ polynomial \ time (\ p.p.t.)\) 概率多项式时间

Balance Experiment

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

Definition 3.3

定义3.3( \(Balance\) )：

IV. Decentralized E-Cash from Strong RSA

A. Cryptographic Building Blocks

Zero-knowledge proofs and signatures of knowledge

我们的协议使用零知识证明，这些证明可以使用 \(Schnorr\) 协议的技术实例化。
\(NIZKPoK \left\{(x, y) : h=g^x\ ∧\ c=g^y \right\}\) 表示满足 \(h=g^x\) 和 \(c=g^y\) 的元素 \(x\) 和 \(y\) 的知识的非交互式零知识证明。假设验证器知道没有包含在\((\ )\)中的所有值。
\(ZKSoK[m] \left\{(x, y) : h=g^x\ ∧\ c=g^y \right\}\) 表示消息 \(m\) 上的知识签名。

Accumulators

B. Our Construction

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

• 算法描述如下：
  

协议假定使用可信的设置过程来生成参数。 我们强调，在设置程序之后不再使用累加器陷门 \((p,q)\)，因此在生成参数后可立即将其销毁。或者，实施者可以使用 \(Sander\) 技术来为没有陷门的累加器参数生成所谓的 \(RSA \ \ UFOs\)。

陷门（trapdoor）函数即类似Hash函数的单向函数，正向计算容易而逆向计算十分困难（在获得某秘密值的情况下逆向计算也会变得简单）。

C. Security Analysis

Theorem 4.1

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

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

Theorem 4.2

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

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

V. Integrating with Bitcoin

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

为了铸造面额为 \(d\) 的 \(Zerocoin \ 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)→(π,S)\)。 最后，她通过将 \((π,S)\) 嵌入 \(ptx\) 输入的 \(scriptSig\)(输入脚本) 中来完成事务。 此交易的输出也可以是另一个\(Zerocoin\) \(Mint\)交易——此功能对于在同一区块链中运行的多个\(Zerocoin\)实例（即，具有不同面额）之间的价值转移很有用。

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

Computing the Accumulator

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

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

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

New Transaction Types

通过添加一条新指令来扩展比特币：\(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\) 交易会导致将硬币序列号添加到客户持有的支出序列号列表中。

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