Hyperledger实战之——分布式系统（3）

——本文是作者自己原创编写的电子书中的部分章节，在此分享给各位CSDN的读者。

接上篇

3.3.2 一些经典共识算法

Paxos 算法

分布式系统领域，最重要、最著名的共识算法首推 Paxos，是Lesile Lamport（莱斯利 兰波特）}提出的方案。

Lesile 是 2013年的图灵奖得主，LaTex 排版软件的发明人。1990年，Lesile 在一篇提交给 ACM TOCS Jnl. 的论文中，用神话故事的方式提出了 Paxos 共识算法\footnote{Lamport L. How to make a multiprocessor computer that correctly executes multiprocess progranm[J]. IEEE transactions on computers, 1979(9):690-691.}，但当时的评审委员会没有读懂他的算法，于是建议他用数学语言、而不是用神话故事来描述算法的核心。Lesile 很生气并拒绝修改论文，并且撤回了这篇论文。

后来，微软的 Butler Lampson 读懂了这篇论文，并在 1996年 的 WDAG 上提出了重新审核这篇文章。1997年，MIT 的 Nancy Lynch（又是FLP里面的那位L – Nancy Lynch）在 WDAG’97 \footnote{11th International Workshop on Distributed Algorithms. Saarbrücken, Germany, September 24-26, 1997}上改写了 Lesile 的论文并给出了 Paxos 的数学证明。于是直到 1998年 的 ACM TOCS 上，这篇对于分布式计算领域至关重要的论文才被接受了。

后来 2001年，Lesile Lamport 终于使用简单的语言而不是神话故事重新描述了 Paxos 算法 \footnote{Lamport, Leslie. “Paxos made simple.” ACM Sigact News 32.4(2001):18-25.}，但仍然拒绝使用数学语言来讲述 Paxos 。关于 Paxos 算法的原理和细节，各位读者可以参照各种专著，本节不做展开叙述。

PoW 共识

PoW 本来是一类共识机制的总称，并不是专指比特币网络使用的共识算法。但由于一些原因导致 PoW 几乎被升华到了比特币「灵魂」的高度，所以值得花一些篇幅来解释一下它的工作原理。

PoW 的本质是计算一个叫做 nonce 的数值，已知:

• 前一区块的 hash 值 previous_hash、当前区块的 Merkle树的根 hash 值 data_hash、时间戳 timestamp;
• 当前区块难度 difficulity;
• 求满足下列条件的 nonce 值:

一般说来，对于大部分第一次接触 PoW 的人来讲，最难理解的部分是* BeginZeroBits()* 方法，或者称作 * Difficulty()* 方法。实际上这个方法没什么神秘的，它做的事情就是数（shǔ）数（shù） – 计算从最高位开始的连续零的个数。

用自然语言来解释前面的公式就是：寻找一个合适的 nonce 值，使得四个字段（前区块 hash 、当前区块数据 hash、时间戳、 nonce）的 hash 值的最高 n 位都是零，而且 n 大于等于 difficulty 。如果用更简单的图片来描述的话，就是这个样子（见图\ref{fig:ds_008}）了:

由于 hash 算法的雪崩效应特性，即使输入数据发生最微小的变化，也会导致 block_hash 的值产生不可区分性的改变。要得到一个满足最高位连续几个零的 block_hash，除了穷举 nonce 值暴力计算之外，没有其他办法。

比如要为 Hello, world! 算一个高位连续16个零的 hash 值，从``0’'开始枚举 nonce 的话需要计算\textbf{4251}次才能得到一个满足要求的结果（见图\ref{fig:ds_009}）。

前面的核心算法如果用伪代码（见代码\ref{lst:ds_001}）来描述的话，大概是这个样子：

while true
	  blockHash = sha256（previousHash，dataHash，timeStamp，nonce）
	  zBits = countLeadingZeroBits（blockHash）
	  if zBits >= difficulty
	    return nonce
	  else
	    nonce++
           

这样一个算法，自从有了比特币的加持，你不点个赞膜拜一下的话都会被嘲笑``不懂区块链’'。

尽管 （计算依赖类）PoW 算法浪费了大量的宝贵能源，不过算法背后的思想堪称精妙绝伦，值得我们深入探究。知其所以然，之后才能真正理解它对于加密数字货币的重要性。

前文谈到比特币使用的区块链技术实际上脱胎于 Surety，而比特币使用的 PoW 是从哪儿来的呢？这就要从「垃圾邮件」谈起了。

PoW 的全称是 Proof of Work，这一机制最早是由Cynthia Dwork和 Moni Naor 提出来的算法。在当时的互联网上，由于批量发送电子邮件的低成本，导致电子邮件成为了常规营销手段，并造成了垃圾电子邮件的泛滥。为了解决这个的问题，Dwork 和 Naor 在文章\footnote{Dwork, Cynthia;Naor, Moni(1993). Pricing via Processing, Or, Combatting Junk Mail, Advances in Cryptology. CRYPTO’92: Lecture Notes in Computer Science No. 740. Springer: 139–147.} 中提出了 pricing function 的概念：在发送端需要计算一个「成本稍高、但并不棘手」的问题，才可以发送邮件。以此来大幅提高批量发送邮件的成本，同时又不会对于日常的发送普通邮件造成太大影响。

1997年，Adam Back 在 pricing function 的基础上设计了 hashcash 并将其应用于垃圾邮件治理和 DoS 攻击，并在 2002年将其以论文

\footnote{Adam Back, Hashcash - A Denial of Service Counter-Measure, technical report, August 2002.}的形式发表。其核心思想是:

• 发件方在邮件头部添加「邮件签名」，其中包含收件人地址，时间戳和一个 counter;
• 邮件签名的 SHA-1 哈希值的前\numfont{20}位全部为0。

这种情况下，除了穷举 counter 之外，发件方没有任何办法可以得出有效的邮件签名。这个 hashcash 就足以证明该邮件不太可能是垃圾邮件。而在邮件的接收端，只需要非常低的成本就可以验证 hashcash 的有效性。

鉴于其计算成本和时间成本，正常发送一两封邮件的时间成本并不明显，所以不会对普通用户有太大影响。但是批量发送邮件的成本就超出邮件推销员们的接受范围了。

细心的读者应该能看出来，比特币使用的 PoW 完全就是 hashcash 中的邮件签名。比特币白皮书中也明确提到了 ``To implement a distributed timestamp server on a peer-to-peer basis，we will need to use a proof-of-work system similar to Adam Back’s Hashcash，rather than newspaper or Usenet posts’’ 。所以从 PoW 的角度来看，比特币这么一个金蛋居然是从垃圾邮件治理的技术中孵化出来的，是不是有一点意外呢。

前面提到的这两篇论文是如此的伟大，一举奠定了后来的整个加密数字货币关于共识机制的思想基础。Pricing 一文作为思想的提出者当然居功至伟，其主要 focus 在定义和寻找适合用作 pricing function 的数学问题。而 Hashcash 一文则清晰地阐述了 PoW 的核心思想：1）只能暴力计算 counter 值;2）验证成本极低。

2004年，\namefont{Hal Finney} 借鉴了 hashcash 的工作原理搭建了 \abbrfont{RPoW} – resuable proof of work 系统。正因如此，2009年比特币上线之后，在中本聪本尊现身之前，Hal 一度被怀疑是 Satoshi 的真身。实际上这一猜测也并不离谱，Hal 是加密数字货币的积极提倡者和探索者之一，是比特币的早期贡献者之一，是第一笔比特币交易的接受方，是中本聪之后的第二位比特币矿工，是和 Satoshi 住在同一个小镇长达10年的邻居。不幸的是，Hal 患了肌萎缩性侧索硬化症（渐冻人症），于2014年8月28日离世。此外，他还是人体冷冻技术的首个采用者，他去世后遗体被空运到美国亚利桑那州的 Alcor 生命延续基金会，储存在零下 195 摄氏度的低温下，等待有一天被唤醒…好像有点八卦了，还是接着说 PoW 吧。

前面已经用自然语言、图片和伪代码把 PoW 的理念解释得很清晰了。实际上用生活的语言解释起来更容易理解：假设你是一个高中生，要熟练掌握一个物理公式，一般需要几个小时的认真学习、或者几十个小时的边走神儿边学习。但要检验你是不是掌握了这个公式就很简单：出两道题做一下。能把题做出来就证明你掌握了这个公式。

PoW 也是一样的原理：能给出满足要求的 counter/nonce 值，就证明你不是坏人，系统就会接受你提交的请求。在比特币白皮书中明确写了 PoW 是沿袭了 hashcash。这么看来，区块链是脱胎于 Surety，PoW 是借鉴了 hashcash，是不是这样就可以说比特币其实没有什么创新呢?

答案当然是否定的。虽然不是比特币发明了 PoW ，但比特币是第一次把 PoW 用做分布式系统的共识机制，然后才开启了加密数字货币的传奇历程。在结束关于 PoW 的介绍之前，还有一个小小的误解需要说明一下。受比特币的影响，很多程序员以为 PoW 就是以 hash 为基础的。但实际上 hash 只是实现 PoW 的一个选项，除了 hash 之外，卷积求导、大质数分解等运算都可以拿来实现 PoW 。此外，PoW是一个共识机制，是一类共识算法的总称，并不是特指以某一个共识算法。

pBFT共识算法

pBFT 的全称是 Practical Byzantine Fault Tolerance，是 Miguel Castro 和 Barbara Liskov 在1999年的文章中提出来的，它在一定程度上解决了原始 BFT 算法的效率问题，把算法复杂度从指数级降低到多项式级，是第一个在工程应用中可行的 BFT 类算法。它的发明人之一的 Barbara Liskov 是计算机领域的一位杰出的女性科学家，由于提出六大设计原则之一的著名的 Liskov Substitute Principle 2008年获得了图灵奖。从 pBFT 到 LSP，可以想象 Barbara Liskov 可不是只搞理论的学究，其工程能力也一定是顶级的存在。

接下来我们试图用最简单的方式来解释一下 pBFT 的工作过程。

如图\ref{fig:ds_010}所示，pBFT 算法的的共识过程中会有几个基本角色和概念:

• client（客户端）：客户端发起交易请求到主节点;
• primary（主节点）：主节点负责将来自客户端的请求排序，然后按顺序广播给备份节点;
• backup（备份节点）：除主节点之外的其他节点;
• view（视图）：某个节点担任主节点的网络快照，当一个主节点失效时，就要启动视图更换。算法中用到的是一个连续编号的整数。

pBFT 的各节点会轮流担任 primary 主节点。在运行 pBFT 共识的分布式系统中，网络的所有节点都是两两之间直接连通的，这一点也是 pBFT 和比特币网络的 PoW 共识不一样的地方。下面在介绍 pBFT 工作过程的时候会看到，为什么要求所有节点两两互通。

pBFT 的过程分为几个阶段:

• 1. request 阶段：客户端 c 向主节点 p 发起请求 REQUEST，其中包括客户端的签名信息。

     < R E Q U E S T , o , t , c > σ c \mathtt{<REQUEST, o, t, c>\sigma _{c}} <REQUEST,o,t,c>σc​

     • o：请求的操作；
     • t：时间戳；
     • c：客户端身份信息；
     • σ c \sigma_{c} σc​：客户端 c 在 REQUEST 消息上的签名。

• 1. pre-prepare 阶段：节点收到客户端的请求，进行一系列的校验。

     校验通过的话，为该请求分配一个序列号，然后向所有备份节点广播 PRE-PREPARE 消息，其中包含主节点的签名信息。

     < < P R E − P R E P A R E , v , n , d > σ p , m > \mathtt{<<PRE-PREPARE, v, n, d>\sigma _{p}, m>} <<PRE−PREPARE,v,n,d>σp​,m>

     • v：视图编号；
     • n：REQUEST 的序列号；
     • d：m的摘要；
     • σ p \sigma_{p} σp​：主节点 p 在 PRE-PREPARE 消息上的签名；
     • m：请求消息。

• 1. prepare 阶段：备份节点在收到 PRE-PREPARE 消息之后，进入准备阶段，并向所有节点发送准备消息 PREPARE。

     < P R E P A R E , v , n , d , i > σ i \mathtt{<PREPARE, v, n, d, i>\sigma _{i}} <PREPARE,v,n,d,i>σi​

     • v：视图编号；
     • n：REQUEST 的序列号；
     • d：消息m的摘要；
     • i：节点i的编号；
     • σ i \sigma_{i} σi​：节点 i 在 PREPARE 消息上的签名。

• 1. commit 阶段：每个节点收到\textbf{2f+1}个或以上一致的 PREPARE 消息，则向其他节点发送一条 COMMIT 消息。

     < C O M M I T , v , n , d , i > σ i \mathtt{<COMMIT, v, n, d, i>\sigma _{i}} <COMMIT,v,n,d,i>σi​

     • v：视图编号；
     • n：REQUEST 的序列号；
     • d：消息m的摘要；
     • i：节点i的编号；
     • σ i \sigma_{i} σi​：节点 i 在 COMMIT 消息上的签名。

• 1. reply 阶段：如果节点 i 收到了\textbf{2f+1}个 COMMIT 消息，则运行 REQUEST 请求中的操作 o，并返回 REPLY 消息。

     < R E P L Y , v , t , c , i , r > σ i \mathtt{<REPLY, v, t, c, i, r>\sigma _{i}} <REPLY,v,t,c,i,r>σi​

     • v：视图编号；
     • t：时间戳；
     • c：client；
     • i：节点i的编号；
     • r：对 REQUEST 操作的执行结果；
     • σ i \sigma_{i} σi​：节点 i 在 REPLY 消息上的签名。

前面讲到过，共识算法按照容错类别可以分为 CFT 和 BFT。CFT 类算法可以容忍网络中存在一定比例的故障节点，这种情况下仍然可以在保证 liveness 和 safety 的前提下达成共识。相比之下，BFT 类算法不仅可以容忍一定比例的故障节点，还可以容忍一定比例的拜占庭节点（恶意节点），并在保证 liveness 和 safety 的前提下达成共识。

有些区块链研发人员受比特币影响，以为区块链的容错能力都是 50 % 50\% 50%，其实不是这样的，每一种 BFT 的容错能力是不一样的。比如著名比特币使用的 PoW 的容错能力是：恶意节点不超过 50 % 50\% 50%。需要强调的是： 50 % 50\% 50% 是由 PoW 的``概率类算法’'特性决定的，而且只是一个不太靠谱的理论值。实际的情况是，如果有人能控制比特币网络 30 % 30\% 30%甚至更少的算力就可能威胁到比特币价值网络了。

而 pBFT 的容错能力和 PoW 是不一样的，这是由 pBFT 的工作原理决定的。假设网络中有 n 个节点的话，拜占庭节点的个数 f 的上限是:

f = n − 1 3 \mathtt{f = \frac{n - 1}{3}} f=3n−1​

也就是说，pBFT 能容忍的故障/恶意节点的个数必须小于节点总数的三分之一。

其他共识算法

后来，Paxos 算法又衍生出了 zab 和 raft算法。zookeeper 使用了 zab 算法，Fabric v1.4.1+ 版本支持 raft 算法。网络上关于这些算法的资料很多，为节省篇幅此处就不展开讲了。

3.3.3 数据同步

除了「共识」之外，还有一类「一致性协议」对于区块链或者其他的分布式系统都很重要。共识只是尽力保证每一笔交易的「一致性」，但并不是每一笔交易都达成一致了，整个系统的所有数据就一致。一些节点可能会故障重启，在重启期间的所有交易都没有参与共识。

还有一些节点可能是在系统运行了一段时间之后才加入的，在加入之前的所有交易都没有参与共识…类似的情况，就会导致单纯依靠「共识」在有些情况下不能保证系统的数据一致性的，还有一类专门用来处理数据的同步问题，其中最经典的就是 Gossip 协议。

Gossip 协议

Gossip 协议也称作 Epidemic Protocol，是1987年 Alan Demer 等人在 ACM 上发表的论文 《Epidemic algorithms for replicated database maintenance》中提出的。算法的初衷是解决分布式数据库中节点数据同步的问题，是基于流行病传播方式的节点或者进程之间信息交换的协议，目前在分布式系统中被广泛使用。

Gossip 的理论基础是\textbf{六度分隔理论}，简单来说就是一个人通过6中间人就可以认识世界上的任何一个人。假设每个人认识150个人，那么他的六度就是 15 0 6 = 11 , 390 , 625 , 000 , 000 150^6=11,390,625,000,000 1506=11,390,625,000,000（大约是11.4万亿），去掉重复认识的人，这个数字远远超过地球上的人口总数。

首先来看一下 Gossip 协议的执行流程：

• 种子节点在收到消息之后，周期性的将消息传递给自己可以连接到的节点;
• 接受到传递过来的消息的节点，随机选择 N 个与自己邻接的节点，然后将消息传递给这些邻接节点;
• 节点只接受消息，但是并不会反馈结果;
• 每次在寻找节点传递消息的时候，都会像没有发送过的节点进行传递消息;
• 收到消息的节点，不会向发送节点传送消息。

由 Gossip 协议的执行流程可以知道：

• Gossip 协议的消息传播需要一个种子节点，并且消息传输需要种子节点发起。
• 消息在整个网络中传输需要一定的时间，并不能保证某一个时刻所有的节点都会收到消息，但是理论上来说，最终所有的节点都会收到消息，所有 Gossip 协议是一个最终一致性的协议。

Gossip 协议的目标是将消息发送到网络中的每一个节点上。节点两两之间进行通信的时候有以下三种方式:

• push-gossip：节点 p 将数据 {\ttfamily <key,value,version>} 及对应的版本号推送给 q 节点，节点 q 更新 p 中比自己新的数据;
• pull-gossip：节点 p 仅将数据 {\ttfamily <key,version>} 推送给节点 q，节点 q 将本地比节点 p 新的数据 {\ttfamily <Key,value,version>} 推送给 节点 p，节点 p 更新本地
• push-pull-gossip：与 pull-gossip 类似，只是多了一步，节点 p 再将本地比节点 q 新的数据推送给节点 q，节点 q 更新本地数据。

直到数据同步完毕。

待续……