区块链核心算法解析

本书主要介绍区块链中超级重要的概念：共识在各种应用场景中的实现机制。本书是目前已面世书籍中对共识概念解析中至**、至全面的一本。目标读者为区块链学习及研究人员，以及实际开发区块链系统的工程人员。在原著基础上，翻译版将增加解读及部分代码实现。

　　RogerWattenhofer博士是瑞士苏黎世联邦理工学院（ETHZurich）的一名教授。在这之前，他曾在美国布朗大学（BrownUniversity）及微软研究院工作。他的研究兴趣主要包括容错分布式系统、高效的网络算法，以及加密货币。截至本书出版，他已发表了250多篇学术论文。

　　译者简介：

　　陈晋川，香港理工大学博士，中国人民大学信息学院副教授，硕士生导师，曾作为访问学者先后在微软亚洲研究院和德国乌尔姆大学工作。目前研究方向为大数据管理、区块链。

　　薛云志，中国科学院软件研究所博士，清华大学MBA，中国科学院软件研究所副研究员，硕士生导师，研究方向为人工智能、软件工程。

　　林强，律师、专利代理人，中国科学院软件研究所计算机应用硕士。执业领域为知识产权法，尤其是专利咨询、申请、管理和权利行使。于2004年加入北京东方亿思，一直致力于帮助许多财富500强跨国公司管理他们在中国的专利组合。近年来，还帮助一些互联网巨头和国内初创企业建立、管理全球专利组合。

　　祝庆，计算机科学硕士研究生，毕业于中国科学院研究生院。现任职于中国工商银行总行，之前在甲骨文Oracle、IBM、Teradata等公司担任首席企业架构师、项目总监等职位，在金融电信媒体行业有多年行业经验。

除原稿翻译之外，译者还特别增加了自己的注释，对书中的算法、公式进行注解。另外，书中还单独增加了两章新的内容。一章是介绍Paxos算法的发展史和在工业界的应用情况，另一章是对比分析当前主流的两个共识机制，比特币的PoW和私有链的PBFT。

　　推荐序I

　　毫无疑问，互联网是20世纪最伟大的发明之一。随着信息、通信技术的蓬勃发展，互联网已渗透到生产、贸易、通信、学习、娱乐等人们生活的几乎所有方面，更使很多方面产生了革命性的变化。近十年

　　来，在互联网的基础上，移动互联网、物联网，乃至智能互联网得到了新的发展。人工智能、深度学习、机器学习等一系列技术和理论的新发展，又促使互联网应用面临更加蓬勃发展的新局面。在众多的互联网新应用中，不得不提及区块链。

　　仿佛一夜之间，互联网创业圈和金融圈都在谈论区块链。坚信者认为，去中心化的、不可篡改的分布式账本，能够重构金融体系，甚至重塑整个社会。不知区块链之父当初是否曾预见到如今区块链的热度？

　　如今，比特币及其他虚拟货币已广泛流行，并且引起了监管当局的关注；政府、巨头和创业公司，也都积极参与到区块链的各种应用的探索中。然而，在互联网土壤上生长出的各种技术和应用中，区块链及其应用还很年轻。自2009年比特币诞生至今，也才仅7年，更不要说区块链在互联网金融领域和其他领域的应用。

　　作为一个一直关注新技术发展的互联网“老兵”，我曾数次应邀参加中关村区块链产业联盟的活动，和互联网领域的年轻创业者、专家、学者一起，探讨、推动区块链的发展和应用。我们的年轻人，尤其是年

　　轻的创业者，他们的大胆探索和勇于创新，令我感到欢欣鼓舞。

　　目前，介绍区块链应用的书籍非常多，而从理论、技术层面介绍区块链的书比较少。很高兴看到有这样一本从理论、技术层面介绍区块链的书籍出版。希望大家能耐心读读这本书，更深入地理解区块链技术，从而有助于推动区块链技术的发展和应用。

　　高卢麟博士

　　中国互联网协会副理事长

　　美国芝加哥马歇尔法学院客座教授

　　推荐序II

　　区块链（BlockChain）原本只是比特币网络的一种记账技术，近几年来却在金融、知识产权、数据交易、电子证照、慈善、新能源等领域引起了广泛的关注。为什么就突然“火”起来了？究其原因，我的理

　　解是：第一，区块链具有去中心化的特征，不以参与交易的任何一方为中心。去中心化可以带来效率的提升和成本的降低，直接增加了企业的利润。第二，区块链具有去信任的特征，也就是假定参与交易的任何一方都不是可信任的。我们通过记录交易的信息，而且是不可抵赖的，来迫使交易各方遵守诚信。因此也可以说，区块链技术很好地回应了目前互联网的痛点——诚信问题。第三，区块链作为互联网的一种基础设施，也可以看作是一种分布式数据库，其核心就是参与交易的多方如何达成共识。在分布式数据库中，为了处理并发事务，需要在不同的节点上维护一个全局一致的状态，传统的做法是通过两阶段锁协议来实现。

　　另一方面，通常大型应用会维护多个数据库副本，以实现数据库的恢复。在多个数据库副本之间维护一致的状态也是一个经典的难题，而解决这个难题的最佳算法实践正是本书中的重点内容——Paxos算法。这个算法在大数据管理时代更是大放异彩，在BigTable，Hadoop等多个大数据计算平台上得到应用。

　　目前市场上关于区块链的书籍很多，但大多偏于介绍区块链的基础知识及应用前景，纯技术的书籍相对较少。本书着眼于区块链的核心问题——拜占庭共识，针对不同的应用场景，介绍了适用的分布式共识算法。书中包含了很多算法及证明，深入剖析了共识算法的核心思想。本书详细介绍了在不同应用场景下的分布式共识算法，包括单纯宕机错误（节点只可能发生宕机，但不会恶意犯错），拜占庭式错误节点（可以认为是恶意的节点，呈现任何行为），允许消息签名，仲裁系统，弱一致条件下的共识等，并介绍了分布式存储的一些基础知识（如一致性哈希）。书中提到的很多算法，特别是PBFT，目前是区块链的重要分支——联盟链的核心算法。

　　对于从事区块链的研究者或工程技术人员来说，共识算法是需要认真弄清楚的内容。虽然存在不少开源的共识算法或区块链框架，但不同的应用对共识算法的要求是不一样的，应该根据应用的特点选择合

　　适的共识算法，甚至对已有的共识算法做必要的剪裁。要做到这一点，就必须理解基础的分布式共识算法。而这就是本书的最大价值。

　　本书译者之一，陈晋川博士，自2009年从香港理工大学毕业后加入中国人民大学，一直在我的研究团队里工作。在大数据、分布式数据管理等领域做出了不少优秀成果。晋川从去年开始关注区块链，他在查阅很多文献之后，发现关于区块链核心技术部分的资料很少，很难把握其精髓。在看到本书原著之后，他感觉这正是目前市场所缺少的干货，就决定将其翻译出来。本书内容艰深，为了准确、清晰地将内容译为中文，晋川投入了大量心血。作为一线科研工作者，能在背负巨大科研考核压力的情况下，投入如此多精力从事翻译工作，殊为不易。

　　其实，这本书不能算是严格意义上的翻译，译者除了原稿翻译之外，还增加了很多译者自己的注释，对书中的算法、公式进行注解（作者很多地方写得较为简略）。另外，书中还增加了两章新的内容。一章

　　是介绍Paxos算法的发展史和在工业界的应用情况，另一章是对比分析当前主流的两个共识机制，比特币的PoW和私有链的PBFT。现在都讲究“混搭”，这本译著也是一种形式的混搭。

　　杜小勇

　　中国计算机学会数据库专委会主任

　　教育部数据工程与知识工程重点实验室主任

　　推荐序III

　　“身为一个智能时代的潮人，谁的口袋里还不装着几块比特币？”

　　近年来，比特币作为第一种数字加密货币，受到了褒贬不一的评价；其价格一路飞涨，但走向主流货币之路却是“路漫漫其修远兮”。但是，作为比特币的核心底层技术，区块链技术的受关注程度却一路飙升。自2014年以来，国内外多家著名机构在这一研究方向上已经累计投入了数百亿美元。其研发范围已经远远超越单纯的数字加密货币，遍及银行、保险、物流、物联网、资产交易、公证与鉴别、社交通信等领域。甚至有人宣称，未来的社会及政府都可以架构于区块链之上。

　　区块链为何会受到如此广泛的关注？究其原因，其核心特征，去中心化、去信任化、智能合约等，正好满足未来互联网持续发展所要求的信息的高度自动化和高度程序化的安全流转需求。我们知道，互联网作为一个连接媒介，连接了世界上一部分的信息、数据、交互和交易；移动互联网更是将连接范围进一步扩大至几乎所有人类活动的范围，基本完成了人类活动的数字化。

　　在技术驱动下，人类生活方方面面的数据量开始激增，大规模计算出现了分布化和并行化的特点。在此基础上，人工智能第三次浪潮汹涌而来，进一步衍生了对高度自动化和高度程序化的信息流转的需求：非自动化环节必然被不断削减；信息的审核和控制将不再受限于任何一个权威性的中心节点，也不应该被任何一个参与节点伪造、篡改和否认。

　　对于上述需求，区块链技术可以相对完美地提供解决方案。因此，可以预见，区块链技术将会是智能时代数据存储、传输、分发最有竞争力的解决方案之一。

　　区块链作为一个分布式的数据存储、传输和分发解决方案，其核心在于如何在一个分布式、无受信节点的环境下，自动形成共识（consensus）的机制。所谓共识机制，是指分布式系统中全部节点（或者大部分节点）就某条数据的真实性或者某条交易的价值达成一致，并据此更新各节点记录的一种机制。不难看出，面对不同的场景、不同的应用需求，需要设计并实施不同的共识机制。这就需要对共识机制在理论层面、技术层面有深入的理解。在智能时代，区块链参与节点将可能是一个智能体，区块链系统也将可能是一个多智能体系统。系统中节点的数量和行为可能是基于人工智能技术自动产生和调整，而不是基于程序员所编写的固定规则。这种情况下，要想利用共识机制充分保证区块链的安全运行，需要对共识机制更为深刻的理解。

　　国内关于区块链的书籍已经有很多了，但大多都是在谈应用、谈理念或者在谈相关的投融资，真正涉及技术细节的书籍相对较少。《区块链核心算法解析》以共识机制为主体，系统介绍了区块链所涉及的各种关键定理和证明，也给出了相应算法。难能可贵的是，作者还结合实例讲述了不同场景下的共识机制的设计方法。这是一本关于区块链核心技术的系统论著，对于区块链科研和应用人员都具有很高的参考价值。

　　戴斌

　　国防科技大学机电工程与自动化学院副总工程师

　　前言

　　当你和从事金融科技（FinTech）的朋友在一起交谈时，不可避免地会注意到一个非常流行的词——区块链。听上去，它就像Internet那样重要。某些金融科技领域的朋友认为区块链是一段神奇的代码，它可以使一个分布式系统的参与者们就系统的状态达成共识，从而追踪系统的变化。区块链这个词语是从比特币借用的，然而，早在区块链或者比特币出现之前，共识技术（或协定技术）（AgreementTechniques）就已经在分布式系统领域中存在了。曾经出现过各种各样的概念和协议，各有其优点和缺点。

　　本书的目的是深入剖析这项当前最引人注目的技术——区块链。如果你是一名开发者（不管是否在金融科技领域），本书将帮助你更好地理解：在你研发的分布式系统中，什么是对的，什么是错的，什么是可能的，而什么是不可能的。

　　本书介绍了构建容错的分布式系统所需的基础技术，以及一系列允许容错的协议和算法，并且讨论一些实现了这些技术的实际系统。本书中的主要概念将独立成章。每一章都以一个小故事开始，从而引出该章节的内容。算法、协议和定义都将以形式化的方式描述，以便于读者理解如何实现。部分结论会在定理中予以证明，这样读者就可以明白为什么这些概念或算法是正确的，并且理解它们可以确保实现什

　　么。其他的大部分内容将以评论的方式出现。这些评论将讨论各种各样非正式的思考，并且为后续内容做好铺垫。就算不阅读这些评论，读者们也可以掌握章节的精髓。此外，为了便于读者寻根溯源，每一章也会讨论相关技术的发展历史。

　　本书将介绍不同的模型(以及模型的组合)，以适用于不同的场景。本书关注的是实用的协议和系统。换句话说，我们在选择概念时，不会根据这些概念是否看起来有意思，而是根据它们是否有实际的价值。

　　不管怎样，希望你在本书中找到乐趣！

第1章
1．1 分布式系统是什么． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 1
1．2 本书概览． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 2

第2章 容错问题和Paxos 算法
2．1 客户端/服务器． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 6
2．2 Paxos ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 11
延伸阅读：Paxos漫谈

第3章 共识机制
3．1 两个朋友约饭局． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 27
3．2 共识． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 28
3．3 共识的不可能性． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 29
3．4 随机共识． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 36
3．5 共享硬币． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 41

第4章 拜占庭协定
4．1 有效性． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 47
4．2 有多少个拜占庭节点． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 49
4．3 国王算法． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 52
4．4 “轮”数的下界． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 55
4．5 异步模式下的拜占庭协定算法． ． ． ． ． ． ． ． ． ． ． ． ． ． 56

第5章 认证的协定
5．1 利用认证的协定． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 62
5．2 Zyzzyva ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 65

第6章 仲裁系统
6．1 负载和工作量． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 82
6．2 网格仲裁系统． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 85
6．3 容错． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 88
6．4 拜占庭仲裁系统(Byzantine Quorum Systems) ． ． ． ． ． ． 92

第7章 最终一致性以及比特币
7．1 一致性、可用性，以及分区． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 102
7．2 比特币． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 104
7．3 智能合约(Smart Contracts) ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 113
7．4 弱一致性． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 117

延伸阅读：PoW vs． BFT

第8章 分布式系统
8．1 一致性哈希(Consistent Hashing) ． ． ． ． ． ． ． ． ． ． ． ． ． 128
8．2 超立方体网络(Hypercubic Networks) ． ． ． ． ． ． ． ． ． ． ． 131
8．3 DHT ＆ Churn ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 140

本书着眼于区块链的核心问题——拜占庭共识，针对不同的应用场景，介绍了适用的分布式共识算法。
书中包含了很多算法及证明，深入剖析了共识算法的核心思想。