区块链共识算法导论

**章　区块链基本内容 1.1　区块链的基本概念及原理 1.1.1　区块链的起源与发展 20世纪90年代，诞生了**个使用密码保护的数据区块应用，它被用来实现一个不能篡改文档时间戳的系统，随后，发明者将其与默克尔树相结合，通过将多个文档证书形成一个区块来提高数据记录的效率。 直到2008年，区块链技术才**次出现在比特币系统中。2008年10月31日，一个自称中本聪的人在网站的密码学邮件列表中发表了题为《比特币：一种点对点的电子现金系统》（Bitcoin：A Peer-to-Peer Electronic Cash System）的论文，文中提出，希望可以创建一套“基于密码学原理而非基于信用”的电子交易系统，即任何人可以在不知道对方背景信息的情况下进行交易，且不需要第三方介入。 2008年11月9日，中本聪在SourceForge网站上注册了比特币（bitcoin）项目，并于英国时间2009年1月3日在芬兰赫尔辛基的一个小型服务器上挖出了序号为0的比特币区块——创世区块（上帝区块），如图1.1所示，同时获得了50个比特币的挖矿奖励。 在**个区块中没有交易记录，只有《泰晤士报》2009年1月3日的头版文章标题，即“Chancellor on brink of second bailout for banks”，意思是财政大臣将对银行进行第二次救助，如图1.2所示。 紧接着在2009年1月9日，序号为1的比特币区块被挖出，与序号为0的创世区块相连后形成了链，这标志着区块链的诞生。 要进一步了解区块链的起源，需要回到20世纪90年代末，从一个名为“B-money”的虚拟货币提案说起。 1.B-money 毕业于美国华盛顿大学的戴伟（Wei Dai）于1998年提出了匿名的分布式电子加密货币系统B-money。在这个系统中，参与者通过解决复杂的计算难题来产生资金，并通过匿名的方式使用分布式数据库来交换数字货币。典型的电子现金系统会使用一个中心账簿来追踪账户余额。不管是中央银行、商业银行、Visa或者任何其他的支付服务提供商，都需要一个由中心控制的数据库来追踪资金所有者。在B-money提案中，账簿不再由一个中心机构管理，而是由所有匿名参与者共同管理。账簿包含公钥，上面附着相应的金额，每个参与者都拥有一份账簿的副本，当一笔新交易产生时，参与者都将更新他们的副本。这种去中心化的手段使任何人都不能阻止交易，同时也保证了所有用户的隐私安全。B-money虽然在一定程度上实现了去中心化的加密货币系统（其核心思想与比特币非常相似），但在实践中还是存在很大的困难，包括货币初始化（要求所有参与者共同参与计算量成本的制定并就此达成一致）以及共识模型（不具备鲁棒性）等困难未被解决。尽管如此，中本聪还是在比特币的论文中引用了戴伟的工作，并且在比特币官网上将B-money视作比特币的思想来源，这足以证明B-money和其创始人戴伟的伟大。 2.HashCash 在区块链中，由谁获得打包区块的权利并将系统中进行的交易信息打包成块添加到链上是一个重要问题。在比特币的设计中，区块头部分包含一个难度值，所有节点都可以随机选取一个值，并采取某种算法将值和交易信息等进行计算使结果符合难度，比特币设计中采用的算法引用了HashCash。 英国埃克斯特大学的Adam Back于1997年提出了哈希现金（HashCash）技术，用于过滤垃圾邮件、抵抗针对邮件的DDoS（distributed denial of service，分布式拒绝服务）攻击。HashCash使用的是一种叫Hash的散列过程，用到的算法叫SHA（secure Hash algorithm，安全哈希算法）。输入任意长度的字符串经过SHA得到的输出是固定长度的，由结果猜测出原始输入几乎不可能。正是由于这个特点，HashCash被应用在区块链的创建过程时，会创建有效块并将它们添加到链中，虽然获得创建有效块的权利很难（要不断采用Hash算法计算出符合条件的难度值），但验证它们是否正确却很简单（只要将打包者采取的随机数进行Hash计算，观察所得的结果是否满足难度值要求）。这就是PoW（proof of work，工作量证明）机制，PoW*终也成为比特币的基石。HashCash也是中本聪论文中为数不多的引用之一。 3.拜占庭将军问题 区块链技术需要解决的问题之一就是如何达成共识，共识问题在比特币中也有出现，那么共识是什么？共识的起源又从哪里说起？这就需要提到拜占庭将军问题。 拜占庭将军问题（Byzantine failures）也被称为拜占庭容错问题，是由Leslie Lamport（2013年图灵奖得主）提出的一个在点对点通信中用来描述分布式系统一致性问题的著名例子，见图1.3。 这个例子讲的是拜占庭帝国派出10支军队去包围敌国，10支军队单独进攻都毫无胜算，至少需要6支军队（一半以上）同时进攻才能攻下敌国。这10支军队在分开包围的情况下，依靠通信兵骑马相互通信来协商进攻意向和进攻时间。 在拜占庭将军问题中并不考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道是绝无问题的（Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的，所以在研究拜占庭将军问题时已经假设了信道是没有问题的）。然而困扰这些将军的是，他们如何才能确定在通信中是否有叛徒擅自变更进攻意向或进攻时间？如何才能保证有多于（或等于）6支军队在同一时间一起发动进攻赢得战斗？ 首先假设没有叛徒，A将军提出一个进攻提议（如明日13:00进攻），由通信兵分别告诉其他将军，如果他收到了其余6位以上将军的同意，则发起进攻。但是，若其他将军也在此时发出不同的进攻提议（如明日14:00进攻），由于时间上的差异，不同的将军收到（并认可）的进攻提议可能是不一样的，这时可能就会出现A将军提议有3位支持者，B将军提议有4位支持者，C将军提议有2位支持者等情况。 我们继续增加分析的复杂性，在队伍中加入叛徒，有可能出现如图1.4所示的问题。那么在有叛徒的情况下，一个叛徒会向不同的将军发出不同的进攻提议（如通知A明日13:00进攻，通知B明日14:00进攻等），一个叛徒也可能同意多个进攻提议（如既同意13:00进攻，又同意14:00进攻等）。叛徒发送前后不一致的进攻提议，被称为拜占庭错误，能够处理拜占庭错误的容错性称为拜占庭容错（Byzantine fault tolerance，BFT）。 在比特币中，中本聪创造性地引入了PoW机制来解决一致性问题。在该机制中，增加了节点发送消息的成本，降低了节点发送消息的速率，保证了在一个时间点只有一个节点（或少量节点）在进行广播，同时在广播时会附上自己的签名。 回到拜占庭将军问题，工作量证明过程就是A将军在向其他将军发起一个进攻提议时，其他将军看到A将军签过名的进攻提议书，如果是诚实的将军，就会立刻同意进攻提议，而不再发起新的进攻提议。这就是比特币网络中某个区块达成共识的方法。 以上3种技术，是区块链起源的基石，也为区块链技术的发展应用奠定了基础。 1.1.2　区块链的基本概念及工作原理 区块链技术模型包括9大部分，其中包含7个基础技术层以及2个贯穿7个基础技术层的共用技术，7个基础技术层分别为数据存储层、网络通信层、数据安全与隐私保护层、共识层、智能合约引擎层、应用组件层和区块链应用层，区块链与现代技术融合以及区块链技术标准为共用技术，见图1.5。 1.数据存储层 数据存储层是区块链*底层的技术，是一切的基础。区块链可以抽象地理解成一个分布式账本，各个账本之间通过哈希值进行连接，构成一连串的账本链（即区块链）。每个节点都保存有账本中的数据副本，其存储形式需要借助于分布式文件系统或者分布式数据库来完成。数据存储层主要实现了两个功能，见图1.6。 2.网络通信层 网络通信层主要包括P2P（peer to peer）网络和共识算法两个组成部分。P2P网络也称为点对点网络或对等网络，其拓扑结构如图1.7所示。区块链的区块数据和交易数据需要通过P2P网络在不同的节点之间进行同步、验证。这就需要网络通信层实现数据同步、校验等消息传播机制和验证机制等。 3.数据安全与隐私保护层 数据安全与隐私保护层主要负责区块链安全。其中的技术包括密码学加密技术、哈希算法、数字签名技术、身份认证技术、授权鉴定技术、零知识证明等隐私保护技术、防范网络攻击技术、审计追溯技术以及抗量子安全算法等安全保障技术。与传统的中心化PKI（public key infrastructure，公钥基础设施）安全体系不一样，区块链上的安全技术强调采用“去中心化”的区块链安全技术体系和隐私保护体系。 4.共识层 基于区块链的各种应用，其实质是DApp，即去中心化应用（decentralized application）。去中心化应用在网络中的各个节点同时运行，其结果需要通过共识机制来实现共识，使得DApp应用状态在区块链网络中得到确认。比特币区块链和以太坊的共识层是使用工作量证明（PoW）共识机制，随着应用的不断丰富，通过工作量证明来达成共识已经不能满足应用的需求，特别是高并发需求的应用场景。因此，在不同的应用场景中需要构造能满足应用需求的共识机制，比如后来发展的权益证明（proot of stake，PoS）、委托权益证明（delegated proof of stake，DPoS）等，还有一些传统的强一致共识算法，像Paxos家族共识算法和拜占庭容错算法等，可以用来确保满足有强一致需求的应用场景。 5.智能合约引擎层 为了让各种基于区块链的交易能够通过机器自动化完成各种交易和交易验证，需要用到智能合约技术。智能合约本质上是一段程序，继承了区块链数据透明、不可篡改和永久运行的三个特性，见图1.8。 数据透明指的是智能合约的数据处理是公开透明的，运行的时候任何参与方都可以查看合约代码和数据。不可篡改指的是部署在区块链上的智能合约代码以及运行时产生的数据输出是不可篡改的，不用担心其他恶意节点修改代码和数据。支撑区块链网络的节点往往比较多，部分节点的失效并不会导致智能合约的停止，理论上接近于永久运行。