干货 | 比特币的学术谱系，Part-1
如果你读过比特币的新闻报道，并且熟悉密码学领域的学术研究的话，你应当会留下这样的印象：自 David Chaum 10,12 起，学术界对数字货币展开了长达数十年的研究，却未能取得商业上的成功，因为整个数字货币系统需要一个类似银行的中心化服务机构加以控制，事实上没有一家银行对此感兴趣。比特币则另辟蹊径，提出了创建无需银行的去中心化加密货币的想法，数字货币终于迎来了成功。人们普遍认为，神秘的比特币之父中本聪并非学术界人士，比特币与之前的学术设想毫无相似之处。
为反对上述观点，本文特别列出了图 1，显示比特币用到的所有技术几乎都源自 20 世纪 80 和 90 年代。笔者并非有意贬低中本聪的贡献，而是要指出他也是站在巨人的肩膀上。通过对比特币概念的溯源，我们可以专注于中本聪在洞察力上的真正飞跃——他是如何通过某种准确且复杂的方式将这些技术结合起来的。这有助于解释为什么比特币这么晚才诞生。已经熟悉了比特币运作原理的读者或许能从这些历史回顾中获得更深刻的理解。（请参见 Arvind Narayanan 等人所著的《比特币和加密货币技术》作为入门读物36。）比特币的学术史也作为一项案例研究，展示了学术界人士、外部研究人员和相关从业人士之间的关系，并分享了三方如何互相受益的经验之谈。
账本
如果你有一个安全的账本，将它应用于数字支付系统的过程很简单。举例来说，如果 Alice 通过 PayPal 发送 100 美元给 Bob ，PayPal 会从 Alice 的账户取出 100 美元，并记入 Bob 的账户。传统的银行业大致上也是这么操作的，只不过因为银行之间的没有一个统一的账本而变得复杂了。
账本的概念是理解比特币的基础。账本可以记录系统中发生的所有交易，向系统中所有参与者公开，并且受到他们的信任。比特币将这种记录支付情况的系统转化成了一种货币。然而在银行业中，账户结余代表户主可以从银行取出的现金，那么一单位的比特币代表什么？暂且将它理解为具有内在价值的交易物。
如何在一个类似于参与者不信任彼此的互联网环境中构建一个账本？让我们先从简单的部分开始：如何选择数据结构。我们期望这个账本能满足几个属性。这个账本应该是不可更改的，或者更确切来说，是只能 添加 ：只能添加新的交易，不能删除、修改或重新排序已有的交易。此外，还应该有方法随时获取账本状态的简洁化 加密摘要 。摘要是避免存储整个账本的短字符串，如果账本遭到任何篡改，摘要也会随之改变，因此篡改会被发觉。之所以要满足上述属性，是因为这个账本不同于存储在单一机器上的普通数据结构，而是由一组互不信任的参与者共同维护的 全球 数据结构。另一种实现去中心化数字账本的方法 7,13,21 是由多位参与者维护本地账本，并由查询这组账本的用户解决账本间的冲突。
链接型时间戳
比特币的账本数据结构借鉴自 Stuart Haber 和 Scott Stornetta 于 1990 年至 1997 年间撰写的一系列论文（其中 1991 年的论文是与 Dave Bayer 合著的）5,22,23 ，只做了少数改动。这是中本聪在比特币的白皮书中亲口所述 34。 Haber 和 Stornetta 解决了文件时间戳的问题——他们旨在创建一个“数字公证”服务。对于专利、商务合同等文件来说，所有者想要确保文件创建于特定时间点，而不是后来才创建的。他们定义的文件概念很广，而且可以是任何类型的数据。顺带一提，他们在论文中确实提及金融交易是一种潜在应用，不过并未当作重点。
概述一下 Haber 和 Stornetta 的论文可得，文件是处于不断创建并广播中的。每份文件的创建者确认创建时间并签署文件、文件的时间戳以及上一个被广播的文件。上一个文件已经由之前的创建者签署了，因此这些文件形成了一条带有时间指针的长链。外部用户无法改变带有时间戳的消息，因为该消息是由创建者签署过的，就算创建者想要改动它，必须连同后面链接的消息一起改动。因此，如果一个可信的来源（例如，另一个用户或某个专门的时间戳服务）将某个东西添加到了链上，到这个东西为止的整条链会被锁住，无法进行更改，并且暂时定下顺序。此外，假设这个系统会拒绝带有不正确的创建时间的文件，按理可知这些文件的创建时间至少不会晚于其时间戳所示的时间。无论如何，比特币只是借鉴了 Haber 和 Stornetta 的研究成果中的数据结构部分，在此基础上新增了工作量证明机制，重新设计了数据结构的安全属性。关于工作量证明机制，我们会在后文中讲解。
在后续论文中，Haber 和 Stornetta 引入了能提高数据结构的效率的想法（其中一些想法在第一篇论文中已有提及）。第一，文件之间的链接可以通过哈希值而非签名创建；哈希值计算起来更加简单迅速。这类链接称为哈希指针。第二，不同于将文件一个个连接起来——如果同一时间创建出了很多文件，这种方式会变得很低效——可以将这些文件打包进不同的批量或数据块，每个数据块里的文件都共享同一个时间戳。第三，每个数据块中的文件可以由哈希指针创建的二叉树（即默克尔树），而非一条线性链相连接。顺带提一下，在 Haber 和 Stornetta 的第一篇论文发表之后不久， Josh Benaloh 和 Michael de Mare 分别于 1991 年引入了上述 3 个想法 6。
默克尔树
比特币本质上使用的是 Haber 和 Stornetta 于 1991 和 1997 的论文中撰写的数据结构，如简化版的图 2 所示 （中本聪当时可能不知道 Benaloh 和 de Mare 的研究成果）。当然，比特币用交易代替了文件。在每个区块（实质即上文所说的数据块）的默克尔树中，叶节点都是交易，且每个内部节点都包含两个指针。这种数据结构有两大重要属性。第一，最新区块的哈希值充当摘要。对任意交易（叶节点）的改变都必然将变化传导至交易所在区块的根节点，以及后续区块的根节点。因此，如果你知道了最新区块的哈希值，就可以从你并不信任的数据源下载剩余账本，并验证它是否有过变化。一个类似的观点确立了数据结构的另一大重要属性——任何人都可以高效地向你证明某个交易是否包含在账本中。这个用户只需向你发送这个交易所在区块中的少量节点（这就是默克尔树的意义），以及后续每个区块所需的少量信息。性能和可扩展性的提高非常需要高效证明交易是否包含在区块内的能力。
顺便一提，默克尔树是以非对称密码学先锋 Ralph Merkle 命名的，他在 1980 年的论文中提出了这一想法 33。 他当初预期的应用是为公共的数字证书目录生成一个摘要。 例如，如果一个网站向你出示证书，它还会出示一个简短的证明，证明这个证书确实存在于全球目录。只要你知道目录中证书的默克尔树的根哈希值，你就可以高效地验证这个证明。按照密码学领域的标准来看，这个想法已经算不上新颖了，不过它的力量直至最近才得到重视。它处于近期实现的证书透明化系统的核心 30。 一篇 2015 年的论文提出了 CONIKS ，将公钥目录的想法应用于端到端的加密邮件 32。 新型加密货币以太坊提供的主要账本功能之一就是高效地验证部分全球状态。
比特币可能是 Haber 和 Stornetta 提出的数据结构在现实世界中最著名的实例，不过不是第一例。至少有两家公司提供文件时间戳服务 —— Surety 始于 20 世纪 90 年代中期，而 Guardtime 始于 2007 年。这两种服务发生了有趣的转变，因为 Bayer、Haber 和 Stornetta 5 提出了一个想法，即腾出报纸上的一个广告位定期发布默克尔根。图 3 显示了 Guardtime 在报纸上发布的默克尔根。
拜占庭容错
当然，不受中心权威实体控制的互联网货币需要满足更严格的要求。分布式账本不可避免会出现分叉，这意味着一些节点会认为区块 A 是最新的，另一些节点会认为区块 B 是最新的。一个原因可能是有作恶者试图扰乱账本的运作，另一个原因可能仅仅是网络延迟，导致不同的节点在无意识的情况下近乎同时生成区块。正如 Mike Just 在 1998 年的论文 26 中所述，仅仅依靠链接型时间戳不足以解决分叉问题。
另一个研究领域容错型分布式计算已经研究过这一问题，不过用的名称不同，其中包括 状态复制 。一种解决方案是允许一组节点按照相同的顺序应用相同的状态转换——通常来说，确切的顺序并不重要，只要所有节点保持一致就好。对于数字货币来说，要复制的状态是一组余额表，交易代表的是状态转移。图灵奖得主 Leslie Lamport 在 1989 年发表的论文 28,29 中提出了包括 Paxos 在内的早期解决方案 。他提出使用状态复制的方法避免通信信道不可靠或是少数节点可能出现某些“现实”故障——如永久离线或是首次离线后重启并发送过时消息——的问题。后续的文献讨论了更加不利的环境和效率权衡关系。
一项相关工作研究了网络可靠性高的情况（消息发送延时不超过一定范围），然而其对“错误”的定义扩大成了 任何 背离协议的情况。这类拜占庭错误包括自然发生的错误和恶意设计的行为。早在 1982 年，Lamport 与 Robert Shostak 和 Marshall Pease 就在其合著的论文 27 中首次研究了这类错误。 之后直到 1999 年，Miguel Castro 和 Barbara Liskov 发表了一篇具有里程碑意义的论文，介绍了 PBFT （实用拜占庭容错算法）的概念，同时解决了拜占庭错误和不可靠网络的问题 8 。与链接型时间戳相比，关于容错的学术文献数量庞大，而且囊括了数以百计的 Paxos 和 PBFT 等开创性协议的变体和优化版本。
在最初的白皮书中，中本聪并没有引用这类文献或是使用相关术语。他使用了一些概念，作为他的协议中共识机制的参考，并考虑了攻击者以及加入和离开网络的节点的故障问题。相比之下，他明显依赖于链接型时间戳（以及下文将要论述的工作量证明）的文献。在邮件列表讨论中被问及比特币与拜占庭将军问题的关系（需要拜占庭容错来解决的思维实验）之时，中本聪坚称采用工作量证明模式的区块链可以解决这一问题 35。
在接下来的几年，其他学者已经从分布式系统的角度研究了中本聪的共识机制。这些研究仍在推进中。一些学者表示比特币的属性非常脆弱 43 ，而另一些学者认为拜占庭容错视角无法公正评价比特币的一致性 40。另一种方法是定义已经过充分研究的属性的变型，并证明比特币满足这些变型 19。这些定义最近经过了大幅改进，在更为现实的消息传递假设下，变成了一种更为标准的一致性定义 37。然而，所有这些研究成果都建立在参与者行为“诚实”（即符合协议）的前提之下，然而中本聪建议诚实的行为是通过经济激励来实现的，无需对此进行盲目假设。关于中本聪的共识算法可以起到激励作用的分析不适用于过去的容错系统模型。
注解：
[5]：Bayer,D.,Haber,S.,Stornetta,W.S.Improvingthe efficiency and reliability of digital time-stamping. Proceedings of Sequences 1991; https://link.springer.com/chapter/10.1007/978-1-4613-9323-8_24.
[6]：Benaloh,J.,deMare,M.1991.Efficientbroadcast timestamping; http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.9199.
[7]：Boyle,T.F.1997.GLTandGLR:Componentarchitecture for general ledgers; https://linas.org/mirrors/www.gldialtone.com/2001.07.14/GLT-GLR.htm.
[8]：Castro,M.,Liskov,B.1999.PracticalByzantinefault tolerance. Proceedings of the Third Symposium on Operating Systems Design and Implementation; http://pmg.csail.mit.edu/papers/osdi99.pdf.
[10]：Chaum, D. 1983. Blind signatures for untraceable payments. Advances in Cryptology: 199-203.
[12]：Chaum, D., et al. 1988. Untraceable electronic cash. Advances in Cryptology: 319-327; https://dl.acm.org/citation.cfm?id=88969.
[13]：Dai, W. 1998; http://www.weidai.com/bmoney.txt.
[19]：Garay, J. A., et al. 2015. The bitcoin backbone protocol: analysis and applications. Advances in Cryptology: 281- 310; https://eprint.iacr.org/2014/765.pdf.
[21]：Grigg, I. 2005. Triple entry accounting; http://iang.org/papers/triple_entry.html.
[22]：Haber, S., Stornetta, W. S. 1991. How to timestamp a digital document. Advances in Cryptology- CRYPT0’ 90 3(2): 99-111; https://link.springer.com/chapter/10.1007/3-540-38424-3_32.
[23]：Haber, S., Stornetta, W. S. 1997. Secure names for bit- strings. In Proceedings of the 4th ACM Conference on Computer and Communications Security: 28-35; http://dl.acm.org/citation.cfm?id=266430.
[26]：Just, M. 1998. Some timestamping protocol failures; http://www.isoc.org/isoc/conferences/ndss/98/just.pdf.
[27]：Lamport, L., et al. 1982. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems 4(3): 382-401; https://dl.acm.org/citation.cfm?id=357176.
[28]：Lamport, L. 1989. The part-time parliament. Digital Equipment Corporation; https://computerarchive.org/files/mirror/www.bitsavers.org/pdf/dec/tech_reports/SRC-RR-49.pdf.
[29]：Lamport, L. 2001. Paxos made simple; http://lamport.azurewebsites.net/pubs/paxos-simple.pdf.
[30]：Laurie, B. 2014. Certificate Transparency. acmqueue 12(8); https://queue.acm.org/detail.cfm?id=2668154.
[32]：Melara, M., et al. 2015. CONIKS: bringing key transparency to end users. Proceedings of the 24th Usenix Security Symposium; https://www.usenix.org/system/files/conference/usenixsecurity15/sec15-paper-melara.pdf.
[33]：Merkle, R. C. 1980. Protocols for public key cryptosystems. IEEE Symposium on Security and Privacy; http://www.merkle.com/papers/Protocols.pdf.
[34]：Nakamoto, S. 2008. Bitcoin: a peer-to-peer electronic cash system; https://bitcoin.org/bitcoin.pdf.
[35]：Nakamoto, S. 2008. Re: Bitcoin P2P e-cash paper; http://satoshi.nakamotoinstitute.org/emails/cryptography/11/.
[36]：Narayanan, A., et al. 2016. Bitcoin and Cryptocurrency Technologies. Princeton University Press; http://bitcoinbook.cs.princeton.edu/.
[37]：Pass, R., et al. 2017. Analysis of the blockchain protocol in asynchronous networks. Annual International Conference on the Theory and Applications of Cryptographic Techniques; https://link.springer.com/chapter/10.1007/978-3-319-56614-6_22.
[40]：Sirer, E. G. 2016. Bitcoin guarantees strong, not eventual, consistency. Hacking, Distributed; http://hackingdistributed.com/2016/03/01/bitcoin-guarantees-strong-not-eventual-consistency/.
[43]：Wattenhofer, R. 2016. The Science of the Blockchain. Inverted Forest Publishing.
原文链接:
https://queue.acm.org/detail.cfm?id=3136559
作者: Arvind Narayanan & Jeremy Clark
翻译&校对: & Elisa
你可能还会喜欢：
干货 | 代币工程学系列，Part3：比特币分析、海洋协议设计