比特币的学术谱系，Part-2

Part-1：时间戳、默克尔树、拜占庭容错

工作量证明

实际上，所有容错系统都假设系统中绝大多数（例如，超过 2/3 的）节点都是诚实且可靠的。在一个开放式的点对点网络中，节点无需注册，而且可以自由加入退出。因此，作恶者可以发起 女巫攻击 ，创建多个马甲节点、破坏整个系统的共识保障。 John Douceur ¹⁴ 于 2002 年正式提出了 “女巫攻击（Sybil attack）” 的概念，并指出可以利用 工作量证明 的密码学模型来缓解这一问题。

起源

要了解工作量证明，先得从源头讲起。Cynthia Dwork 和 Moni Naor ¹⁵ 在 1992 年最先提出了工作量证明的雏形。其目的是阻止垃圾邮件。要注意的是，垃圾邮件、女巫攻击和拒绝服务这些问题都是大同小异的，作恶者会将普通用户所造成的影响在网络中放大数倍。工作量证明能够同时抵御这三种攻击。根据 Dwork 和 Naor 的工作量证明设计，发件人在发送邮件的同时只有附上已完成适量计算的证明（即，工作量证明），收件人才会处理这封邮件。一台普通的计算机大概需要几秒钟的时间来完成工作量证明。因此，这不会给普通用户造成困难，然而想要发送 100 万封垃圾邮件的人如果使用相同的硬件设备，则需要几周时间。

要注意的是，工作量证明 实例（也称作 难题 ）应该针对不同的邮件和收件人有所区别。否则，垃圾邮件发送者会向同一个收件人发送不同的邮件（或者向不同的收件人发送同一封邮件），其成本等同于向一个收件人发送一封邮件。第二个重要的属性是，收件人只需承担极少的计算量，即，无论这些难题计算起来有多难，验证计算结果正确与否应该很容易。此外，Dwork 和 Naor 提出了带有陷门（trapdoor）的函数，陷门由中心实体掌握，可以免去解决难题所需的工作量。一种可行的陷门应用是让中心实体无需成本就可以批准邮件的发送。 Dwork 和 Naor 提出了三种满足上述属性的候选难题，它引入了一个全新的领域，我们之后会提到。

Hashcash

还有一种非常类似的想法叫作 hashcash，是由博士后研究员 Adam Back 于 1997 年提出的，那时他是密码朋克社区的一员。密码朋克聚集了一群激进分子，他们反对政府和中心化机构集权，力图通过密码学推动社会和政治改革。Back 方向感很强：他先是发布了 hashcash 软件 ²，在 5 年之后的 2002 年又发布了 hashcash 的互联网草案（标准化文档）和一篇论文 ⁴。

Hashcash 比 Dwork 和 Naor 的想法要简单得多：它没有陷门和中心机构，而且仅使用哈希函数而非数字签名。它基于一则简单的原理：哈希函数是一种为了达成某些实用目的的随机函数，这意味着如果要找到一个能让哈希函数得出特定输出值的输入值，唯一的方法是尝试多个输入值，直到得出期望的输出值为止。进一步来说，要找到对应任意一组输出值的输入值，唯一的方法是将不同的输入值依次代入哈希函数进行运算。因此，如果我让你找到一个输入值，它对应的（二进制）哈希值是 10 个零开头的，你必须尝试很多输入值；然后你会发现，每个输入值满足条件的概率是 1/2¹⁰ ，这意味着你平均需要尝试 2¹⁰ 个输入值，约等于 1000 次哈希计算。

从 hashcash 的字面意义可知，Back 将工作量证明视作一种货币形式。 他在个人主页上将其定位为 DigiCash 的替代方案。DigiCash 是 David Chaum 提出的一种银行向用户发行不可追踪的数字货币的系统 ³ 。为了更加突出数字货币的货币特征，Back 甚至在技术设计上做出了妥协。后来，他发表评论称比特币是由 hashcash 衍生而来。不过，Hashcash 根本算不上是货币， 因为它无法抵御双花攻击。Hashcash 代币无法进行点对点交易。

于此同时，从学术角度来看，研究人员发现除了防止垃圾邮件之外，工作量证明还有很多应用场景，如抵御拒绝服务攻击 ²⁵、确保网站分析的完整性 ¹⁷、及对口令猜测实行网络限速等 ³⁸。顺带一提，工作量证明 这一术语首次出现于 Markus Jakobsson 和 Ari Juels 在 1999 年撰写的一篇论文里，该文还详细总结了到那时为止的工作量形式 ²⁴ 。要注意的是这些研究人员似乎没听说过 hashcash ，而是独立地开始探讨基于哈希的工作量证明，这在 Eran Gabber 等人 ¹⁸ 以及 Juels 和 Brainard ²⁵ 所著的论文中有所介绍。（直到这些论文发表很久之后，本段提到的许多名词才成为标准术语。）

工作量证明和数字货币：两难困境

你或许知道工作量证明最初作为抵御垃圾邮件的手段并不成功。一个可能的原因是不同设备的解题速度差异显著。这意味着垃圾邮件制造者只需小小地投资一把定制硬件，垃圾邮件的制造速度就能提升几个数量级。从经济学角度来说，生产成本的不对称会自然而言地带动贸易的发展，即工作量证明解决方案的市场。然而，这是一种两难困境，因为需要一种有效的数字货币。而事实上，产生这样一种货币正是工作量证明被发明的主要动机。一种原始的解决方案是将难题的解作为货币，正如 hashcash 所做的那样。

在比特币的白皮书发表之前，有两篇文章提出了更加符合上述思路的解决方案，分别是 b-money ¹³ 和 bit gold ⁴² 这两种概念。上述两种方案在货币创造时（通过工作量证明）提供时间戳服务；并且，在货币创造出来之后、转装之时，也可得到时间戳。然而，如果各服务器或节点对账本存在分歧，没有明确的解决之法。这两篇文章似乎都暗示了采取多数决的机制，不过由于女巫攻击的存在，这些机制的安全性都不高，除非针对网络入口设置一个把关人（gatekeeper）或是通过工作量证明抵御女巫攻击。（见下方注解）

抗女巫攻击的网络

在 John Douceur 关于女巫攻击的论文中，他提出的解决方案是要求所有加入拜占庭容错协议的节点解决哈希难题。如果一个节点伪装成 N 个节点，是不可能及时解决 N 个难题的，假身份会被清除。不过，恶意节点依然比没有伪造身份的诚实节点有优势。John 后续在 2005 年 ¹ 又写了一篇论文，指出诚实节点可以模仿恶意节点的行为，根据自己的算力尽可能多地虚报身份。如果这些虚拟身份都实行拜占庭容错协议，“故障节点的占比不能超过 f % ”的假设可以替换成“故障节点的算力占比不能超过总算力的 f % ”的假设。因此，不再需要对身份进行验证，而且开放的点对点网络可以运行拜占庭容错协议。比特币采用的也是同样的想法。然而，中本聪提出了一个更深层次的问题：什么能够激励节点花费大量算力进行工作量证明？解决这一问题需要再一次的飞跃：数字货币。

集大成者

理解了这些包含比特币设计内容的项目，就能真正欣赏中本聪的天才之处。比特币出现之后，首次将难题的解与数字货币分离开来，难题的解并不直接构成货币，仅仅用于维护账本。解决工作量证明难题的专业化实体叫做“矿工”（不过中本聪没有想到挖矿的专业化程度会变得这么高）。

矿工一直在竞争寻找下一个难题的解；每次面对的都是一个略有不同的难题，因此一个矿工成功的概率与 TA 的算力占全球算力的比例成正比。解出难题的矿工可以向账本贡献下一组交易（区块）；这些区块根据时间戳串联起来便成了账本。作为提供账本维护服务的奖励，贡献区块的矿工会得到新铸造的货币。如果有矿工贡献的交易或区块是无效的，则会遭到多数矿工的抵制（不在其后继续创建区块），导致不良块得不到有效的区块奖励。这样一来，在货币激励之下，矿工会确保彼此都遵守协议。

比特币巧妙地避免了 “工作量即货币” 方案的多重花费问题（double-spending problem），因为它不为难题的解本身赋予价值。实际上，难题的解与经济价值的关系被 双重 解耦了：出块所需的工作量是一个浮动的参数（与全球算力成正比），而且每个块发行的比特币数量也不是固定的。区块奖励（铸造新比特币的方式）被设置成每 4 年减半（2017 年，比特币的区块奖励从最开始的 50 个比特币降到了 12.5 个比特币）。比特币还纳入了另一个奖励机制 —— 交易的发送者要给矿工支付将自己的交易打包到区块内的服务费。交易费和矿工奖励预期将由市场决定。

中本聪的天才之处不在于比特币使用的任何一个组件，而是在于将这些组件巧妙地结合起来为整个系统注入活力。时间戳和拜占庭容错协议的研究者没有想出激励节点诚实的机制，直到 2005 年才想到使用工作量证明来代替身份。相反，提出 hashcash、b-money 和 bit gold 构想的研究人员没有融入共识算法来防止多重花费问题。在比特币系统中，安全的账本是防止多重花费并保障比特币的货币价值的必要条件。有价值的货币是奖励矿工的必要条件。反过来，强大的算力又是保障账本的安全性的必要条件。否则，作恶者可以聚集 50 % 以上的全球算力，使其生成区块的速度超过剩余网络，从而发动多重花费攻击，有效覆写历史，倾覆整个系统。因此，比特币是一个自举（bootstrapped）的系统，循环依靠上述三个组件。中本聪面对的挑战不仅在于设计，还在于说服最初的用户和矿工社区一起跨入未知领域 —— 最初，一份披萨价值 1万个比特币，全网的算力还不到如今的万亿分之一。

Part-3：区块链、智能合约及其它

注解：

[1]: Aspnes,J.,etal.2005.Exposingcomputationally challenged Byzantine imposters. Yale University Department of Computer Science; http://cs.yale.edu/publications/techreports/tr1332.pdf.

[2]: Back,A.1997.Apartialhashcollisionbasedpostage scheme; http://www.hashcash.org/papers/announce.txt.

[3]: Back,A.2001.Hashcash;https://web.archive.org/web/20010614013848/http://cypherspace.org/hashcash/.

[4]: Back,A.2002.Hashcash—adenialofservicecounter measure; http://www.hashcash.org/papers/hashcash.pdf.

[13]: Dai, W. 1998; http://www.weidai.com/bmoney.txt.

[14]: Douceur, J. R. 2002. The Sybil attack; https://dl.acm.org/citation.cfm?id=687813.

[15]: Dwork, C., Naor, M. 1992. Pricing via processing or combatting junk mail; https://dl.acm.org/citation.cfm?id=705669.

[17]; Franklin, M. K., Malkhi, D. 1997. Auditable metering and lightweight security; http://www.hashcash.org/papers/auditable-metering.pdf.

[18]: Gabber, E., et al. 1998. Curbing Junk E-Mail via Secure Classiffication. http://www.hashcash.org/papers/secure-classification.pdf.

[24]: Jakobsson, M., Juels, A. 1999. Proofs of work and bread pudding protocols; http://www.hashcash.org/papers/bread-pudding.pdf.

[25]: Juels, A., Brainard, J. 1999. Client puzzles: a cryptographic countermeasure against connection completion attacks. Proceedings of Networks and Distributed Security Systems: 151-165; https://www.isoc.org/isoc/conferences/ndss/99/proceedings/papers/juels.pdf.

[38]: Pinkas, B., Sander, T. 2002. Securing passwords against dictionary attacks. Proceedings of the Ninth ACM Conference on Computer and Communications Security: 161-170; https://dl.acm.org/citation.cfm?id=586133.

[42]: Szabo, N. 2008. Bit gold. Unenumerated; https://unenumerated.blogspot.com/2005/12/bit-gold.html.

原文链接: https://queue.acm.org/detail.cfm?id=3136559
作者: Arvind Narayanan & Jeremy Clark
翻译&校对: 闵敏 & 阿剑

你可能还会喜欢：

观点 | 剖析工作量证明
观点 | PoW 本质上是个去中心化的时钟
观点 | 经济关系的发展空间