去中心化场景下的一致性协议-一一网

作者：问勤

引言

分布式一致性是一个老生常谈的问题，即如何保证分布式节点中的数据一致性，或者就某个提议达成一致。大力智能服务端团队就分布式一致性算法进行了深入研究，本文主要聚焦于去中心化场景下的经典一致性算法，并对其进行深入介绍，旨在提升和强化大家对分布式一致性问题的认知，同时也为大家针对类似场景提供新的解决思路。

分布式一致性问题对很多技术同学而言，应该都不陌生，几乎在很多的框架或中间件上都会遇到。而比较经典的实现算法，类似于Paxos，Raft，ZAB，在很多技术框架中都有应用和实现。

当我们说分布式的时候，我们基本会把范围界定在一个具有同质网路结构和状况的范围内，甚至是同一个机房内，所以我们日常接触的分布式一致性协议也是局限于这样的同质条件下的解决方案，此时的分布式系统，其实对外界来说，仍然是一个中心系统，支付宝后台是一个中心化系统，抖音后台也是。

当我们把范围扩大到全网的时候，不管网络结构，不管地域分布，不管各种物理条件的情况下，分布式一致性协议会发生非常大的变化，以致于我们现有的传统协议完全不能work。

去中心化意味着，节点之间是平等的，但网络环境的复杂性，人的复杂性导致节点之间也是不可信的，在这种场景下，一致性协议变得更有挑战。

挑战

分布式一致性问题主要有两类挑战：

故障错误（Crash Fault）

节点随时可能宕机，然后又可能随时恢复
节点硬件可能会坏掉
网络随时可能中断
网络消息可能会丢失，或延迟
消息可能出现乱序
网络可能分化或隔离，形成1个以上的子网络

这些都是由于分布式系统中的物理硬件的不可靠，不稳定带来的风险，是我们系统设计中必须考虑的问题。

拜占庭错误（Byzantine Fault）

上面的错误，都是由于客观因素引起的，节点要么不能正常工作，要么就会按照预期的工作。节点不会做坏事。简单的说，你让我传递一个消息A，我要么传不了，要么一定是传的A，我不会改成消息B传递。但是当去中心化了以后，作恶这件事是极大概率的。任何人都可能作恶，任何人都可能假传消息。一旦有人做坏事，那系统如何正确工作，如何保证数据的一致性，这将是一个很大的挑战。这就会产生拜占庭错误。

拜占庭的称呼源于古代的一个故事。简而言之，n个将军准备一起进攻某个城堡，每个将军都可以选择进攻或是撤退，但所有将军必须行动一致才能成功。各个将军之间相隔很远，不能直接通讯，必须通过信使来传递消息。但是信使并不可靠，信使可能过了很久才送到消息、可能一直也没有把消息送到、甚至可能会故意篡改消息；而将军也并不可靠，里面可能存在叛徒，并不按照提案来行动。显然，这个故事中的信使用来代表分布式网络中的不可靠信道，而将军就是各个不可靠的节点。

图片源于网络

在中心化的环境中，机房，机器，网络都在公司内部，整体是一个安全可靠的环境，我们只需要考虑故障错误即可，这也是Paxos和Raft等协议已经解决的问题。在去中心化场景下，在充满风险和不确定性的网络中，除了故障错误，如何解决拜占庭错误，需要引入新的机制。需要一直回答，为何相信你，如何证明你等问题。综合起来就是，必须要考虑机器的因素和人的因素。

解决方案

PBFT(Practical Byzantine Fault Tolerance)

图片源于网络

假设有3个将军ABC，他们在做出决策前会互相投票。假设General C为叛徒，他给A和B发了不同的消息，此时A收到的消息为进攻：撤退=1：2，于是A会执行撤退，B收到的消息为进攻：撤退=2：1，于是B会执行进攻，结果只有B发起了进攻，最后攻城失败。事实上，对于3个将军中存在叛徒的场景，想要总你能达成一致的行动方案是不可能的，详细的可参考论文《The Byzantine Generals Problem》。此外，在论文中有一个更加普适的结论：如果存在m个叛徒，那么至少需要3m+1个将军，才能最终达成一致的行动方案（其实就是叛徒不能大于1/3)。

图片源于网络

当有4个将军时，我们定义发起命令的为主将，其余为副官。仔细分析可见，情况会变得不一样，不管将军是叛徒，还是任意一个副官为叛徒，最终一定能达成一致的行动方案。

概念定义

在介绍PBFT算法前，先对其中的一些名词做下定义和解释。

签名

PBFT算法的前提，是采用密码学算法保证节点之间的消息传送是不可篡改的，常见的密码学签名算法有RSA，DSA，ELGamal，ECDSA（椭圆曲线算法）等。实际上，在任何去中心化体系中，都必须使用密码学算法去保证消息的不可篡改。

每个节点保存自己的私钥，在发送消息时带上自己的公钥信息，对方可以根据公钥验证消息的合法性。

视图（View）

所有节点的一致性达成过程，都在一个视图中操作，一个PBFT系统则在不断的视图切换中运行。简单理解，就是每个共识轮次，即区块链系统中的高度。每完成一个高度，就是完成一个视图的切换。

主节点

每一次视图过程，必须有一个启动共识的节点，这个就是主节点。

主节点的选择相对随意，而且每轮次都会更换，简单的选择算法：

主节点p = 视图编号v mod 节点总数n。

每个节点都有可能成为主节点，其余节点为副节点。

算法过程

Request

客户端发送消息到主节点。这里可以扩展为，可能有若干个客户端同时向主节点发送消息。

消息内容<d,h,s,pk>，对应以下struct：

type Request struct {
    Data     \[\]byte    // 消息内容
    Hash     \[\]byte    // 消息摘要
    Sign     \[\]byte    // 消息签名
    PubKey   \[\]byte    // 公钥，公钥可以生成client的地址（唯一标识符）
}
复制代码

Pre-Prepare

主节点收集客户端的request，对每个request会进行如下判断：

信息摘要是否正确，确保内容和摘要对的上
签名是否正确，确保信息确实是被该客户端签名的，并且没有被篡改。
非法Request将被丢弃
给所有合法request的消息分配序号n（消息排序），v是本次视图编号，再对消息签名生成pre-prepare消息，消息结构：

type PrePrepare struct {
    SortedReqs     \[\]Request    // 客户端请求列表，排好序
    Hash     \[\]byte    // 本消息摘要
    Sign     \[\]byte    // 本消息签名
    PubKey   \[\]byte    // 公钥，公钥可以生成client的地址（唯一标识符）
    V        int64       // 视图编号，即轮次，在很多区块链系统中，也叫高度Height
}
复制代码

PrePrepare消息，其实就是一个提案Proposal。

Prepare

副节点收到主节点的PrePrepare消息后，进行如下操作：

信息摘要是否正确，确保内容和摘要对得上
签名是否正确
视图V是否正确
通过V确认发送者是否真的属于本视图主节点。防止恶意节点冒充主节点发送消息。在一个特定的视图中，主节点是确定的。
Request的顺序是否正确
若校验合法后，副节点则生成Prepare消息，并签名发送给所有节点（包括主副节点）
然后把PrePrepare消息以kv形式记录到本地账本，状态为未Commit。

type Prepare struct {
    PrePreare   PrePrepare    // pre-prepare消息
    Hash     \[\]byte    // 本消息摘要
    Sign     \[\]byte    // 本消息签名
    PubKey   \[\]byte    // 公钥，公钥可以生成client的地址（唯一标识符）
}
复制代码

Commit

每个主副节点都会收到其他节点发送的Prepare消息，在收到Prepare消息后，需要进行以下校验：

信息摘要是否正确，确保内容和摘要对得上
签名是否正确
视图V是否正确
根据PrePrepareHash查看本地是否存储了相应的PrePrepare消息（Proposal是否存在）
非法消息丢弃。若节点在一定时间内收集到2n/3+1（参考拜占庭问题的普适结论）个合法的Prepare消息后，则向其他节点发送Commit消息。

type Commit struct {
    PrePrepareHash \[\]byte // 主节点发送的PrePrepare消息hash
    Hash     \[\]byte    // 本消息摘要
    Sign     \[\]byte    // 本消息签名
    PubKey   \[\]byte    // 公钥，公钥可以生成client的地址（唯一标识符）
}
复制代码

Reply

主副节点收到Commit消息，需要进行以下校验：

信息摘要是否正确，确保内容和摘要对得上
签名是否正确
PrePrepare消息是否本地存在
非法消息将丢弃。当收集超过2n/3+1节点的Commit消息后，说明网络中大部分节点硬件达成共识，则标记本次PrePrepare消息为Commit状态。同时如果原始request中有逻辑操作，则执行操作，并把最终结果返回给client。当然，对client来说，他们也需要收到超过一半的reply才认为请求成功。

异常控制

上面描述的过程中，每一轮都需要收集超过2/3的反馈后才认为达成共识，因此收集过程必须有一个时间窗口或timeout机制。若在时间窗口内未收集到足够的反馈，则该节点会认为本次共识失败。

在复杂的网络环境中，很有可能并非所有节点都能收齐2/3的反馈，对于未收齐节点，如果本视图是最终能达成共识的话，最终会通过数据同步和分叉处理机制，使得本地数据和其他达成共识的节点数据一致。

实际上，上述的算法过程，保证的是大部分节点（超过2/3）在一个视图中，能对本视图数据达成一致的过程。而对于少部分（少于1/3)未达成一致的节点来说，他们可能在本视图中和其他节点无法达成，甚至不感知到其他节点以及达成共识。这些节点则可以通过数据同步和分叉处理机制，使得自身数据最终和其他节点一致。

局限性和适用场景

由上述算法过程分析，整个达成共识的过程涉及3轮，PrePrepare（Proposal）-》Prepare -》Commit。第一轮由主节点给副节点发送提案消息，复杂度为n（节点规模数），第二第三轮则为所有节点直接两两通讯，消息复杂度为n^2。

节点必须两两连接
消息复杂度为n^2
- 随着节点规模的扩大，PBFT的效率严重下降，甚至无法工作
超时时间窗口的取值到底是多少？长了可能导致共识时间较长，性能较差，短了可能导致无法完成共识，这里需要根据网络状况和节点数量做出一个平衡
在一个视图中，如果主节点作恶，是有可能导致在此视图下无法达成共识的。
- 比如主节点卡在timeout时间点，才发送PrePrepare消息，导致下一轮没有足够时间完成信息收集
- 主节点给不同副节点发送不同消息
- 不过随着视图推进，本视图到期后，下一个视图将换成其他节点为主节点。

相对于Raft，Paxos算法，PBFT算法对网络环境的要求不再苛刻，只要网络中存在不超过1/3的恶意节点，整个系统是安全的。但是在一个开放网络中，到底网络中有多少节点？作恶比例有多高？如何限制？这些问题也是不确定的。这就决定了PBFT无法在一个完全开放的网络中运行。

实际上，PBFT只有在有权限控制的网络中，才能很好的运行。所有节点必须经过权限审核才能才能接入网络。权限审核可以控制节点的数量，节点的资质，甚至节点的作恶追踪等，从而可以很好的保证系统的安全性。在联盟链如fabric，quorum中有比较多的应用。

POW(Proof of Work)

完全去中心化

PBFT无法在一个完全开放的网络中运行，决定了PBFT系统不是一个完全意义上的去中心化系统。一个完全去中心化的系统，应该是无准入门槛的，任何人可以随意加入和退出，节点规模也是不受控制，无法预知的。在这样一个去中心系统中，有可能在有限时间内达成一致吗？

在回答这个问题之前，也许会有人问：我们需要这样的网络吗？为什么一定要完全去中心化？这是不是一个伪需求？其实这个问题直接关系到区块链公有链存在的意义，答案也是仁者见仁智者见智，让我们回到分布式系统的初心和目的去看待这个问题。

强大的容错能力
天然无单点
强大的读能力
数据不可篡改

对于第4点，我们可以考虑一个问题：我们的钱存在银行，我们的余额是不可篡改的吗？当然我们不可篡改，这些数据存储在银行系统内部服务器，我们无法接触到，但是抛开法律和道德的因素，这些数据对银行来说是不是技术上不可改？我相信大家有自己的答案。但是我们相信，或者被迫相信，银行不会无缘无故改我们的余额。在我们的经济发展过程中，银行具有一种公信力，有一种背书，使得我们相信银行。因为一旦我们不相信银行，我们所有的商业活动将不可进行。这是一种被迫信任。有没有一种机制，能让我们不再被迫信任一个第三方，而且只要提供一种证明，就能确保我们的交易是可信的？你不需要相信我，你也不必相信我，你只要验证我。

一个完全开放的去中心系统中，任何人可自由参与，任何人都可以获得数据，但却不能篡改数据，人人是平等的，没有中心权威，但又极其安全。这也是去中心化，这个在区块链领域充满争议色彩的词汇，在现代越来越多的被提起和被研究。

共识机制

概念定义

交易（Transaction）

简单理解为一次往POW系统写数据的请求，可以是区块链中的一笔交易转账，或者是一笔合约调用。

数据块（Block）

数据由一个个的数据块构成，系统定期的产生且只产生一个数据块。每一轮共识产生一个数据块。

type BlockHeader struct {
    Number uint64    // 代表数据块的序号
    PreHash \[\]byte    // 前一个数据块hash
    Hash    \[\]byte    // 本数据块hash
    Difficulty \[\]byte // pow难度
    Nonce    uint64    // 随机盐
    Proposer    \[\]byte // 提案者，即生成此数据块的节点标识
    MerkleRoot    \[\]byte    // 此数据块包含的数据merkle tree根hash
}

type Block struct {
    Header \*BlockHeader    // 区块头部信息
    Trans    \[\]\*Transaction    // 交易信息
}
复制代码

每一个块头都有一个块Hash，它是对数据块所有信息的一个摘要，可以唯一表示一个数据块。

数据链（BlockChain）

所有数据块通过一个指向前一块的hash串连起来，形成一条数据链，就是区块链。在系统初始化时，自动生成一个创世区块，作为链的起点。

难度

PoW算法实质是让CPU提供算力在不断的进行运算，以取得最终的合法解。网络的算力会随着节点数变化，CPU硬件的变化而产生变化。为了保证系统稳定，不至于算力提高后，很轻易就能完成一次POW证明，或算力减少后，长时间无法完成证明，需要一种能恒定的机制，来抵抗网络算力的变化。难度就是一个工作量表征，代表了要生成该区块需要的工作量，即CPU的运算量。是一个动态值，每过一定周期，会根据一定算法更新该难度值，以适应当前网络算力的变化。

共识过程

POW系统是一个完全去中心化系统，所有节点都是对等的，所以每个节点都在做同样的事情。

构造区块头

type BlockHeader struct {
    Number         uint64    // 固定值：前一个区块序号+1
    PreHash        \[\]byte    // 固定值：前一个数据块hash
    Difficulty     \[\]byte // 固定值：pow难度
    Proposer       \[\]byte // 固定值：提案者，即生成此数据块的节点标识
    
    Hash           \[\]byte    // 本数据块hash
    Nonce          uint64    // 随机盐   
    MerkleRoot     \[\]byte    // 此数据块包含的数据merkle tree根hash
}
复制代码

其中：

前面四个字段是固定值
Hash值需要最后确定
MerkelRoot代表的是本块的交易数据存储完成后，整个系统的状态hash值，他包括交易的顺序，交易执行的最终结果等信息，参考www.javatpoint.com/blockchain-…
Nonce：随机数，也就是POW算法最终要寻找的值

Nonce计算

即是POW的计算过程：需要找到一个nonce，使得满足

sha256(BlockHeader) < target

其中target代表是每一块的目标阈值，与difficulty成反比，目标值越小，难度越大。难度和目标值的换算关系为：

difficulty = difficulty_1_target / current_target，其中difficulty_1_target代表的是系统的初始目标值，是一个常数。比特币初始目标值0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF，而当前比特币的目标值大约为：0000000000000000000143b553b553b2f8ecbd33617e683523ce0ccd3925f59ff

sha256的计算是不可逆的，换句话说，唯一得到有效解的方式就是暴力遍历nonce空间；若nonce空间已经遍历完毕，还得不到有效解，则改变交易顺序（MerkleRoot变化），再重新遍历nonce空间。

阈值会定期的动态调整，以适应全网算力的变化。比特币每2016个块(大约14天）调整一次目标值，调整公式为：

区块广播

当计算出合法的nonce后，把nonce和对应的hash填充到BlockHeader中，然后把新生成的区块通过p2p网络广播给其他节点。其他节点接收到区块后，只要把接收到的区块进行简单的验证，nonce以及hash是否满足当前难度即可。若区块合法，则立刻以此区块为基础，进行下一个区块的生成。

分叉

由上述共识过程可知，每个节点的工作都是独立进行的。也就是说，理论上极有可能会有多个节点同时得出合法的解，而把自己生成的区块广播出来，这时候网络上就会有多个不同的区块在广播，而由于网络的传播的不确定性，会导致不同的节点接受不同的区块，进而导致整个系统数据的不一致性。这种现象称之为分叉。

如图所示，由于网络时延的存在，可能会导致中国和美国的节点出现两种不同的区块。

从链的视图看：

出现了链的分叉，这时候需要有一种收敛机制，使得最终只有大家都公认的数据链（一致性）。

POW普遍采用的处理机制是最长链原则，即接受最长的链，丢弃短的。从经济学角度看，最长链累积了更多的计算，难度更大，更难被推翻。

概率最终一致性

最长链原则解决了出现分叉时，该如何收敛的问题。但是去中心化系统仍然不可能理论上达到最终一致性。主要两点原因：

理论上仍有可能存在两条链一直以相等的速度在不断延长，无法分出胜负。
区块链上的数据无法保证是最终不可推翻的。如果存在超级计算机，算出一个更长的链，则现有链会被PK掉，导致已经处理的数据回滚。

但是这两种情况的概率都非常非常低。事实上，对于1，比特币十几年的发展，分叉超过2块的情况非常非常少，当前的难度值太大了，以致于同时得出合法解的节点概率非常低。在很多的比特币交易所中，都以6块（约1个小时）为固化时间，即一般交易被处理1个小时后，就大概率达到了全网一致，交易不可再推翻了。

因此，在去中心化系统中，没有确定的最终一致性，只有概率性的最终一致性。

局限性

POW算法非常简单，简单到只有暴力计算才能得到最终的解。

为了保证足够的安全性，POW需要设置恒定的出块时间，即必须经过大约恒定时间的运算才能得出解。随着算力的不断提升，计算难度越来越大，消耗的CPU资源，电力资源也越来越高，据估算，比特币一年的用电量，相当于新西兰整个国家一年的用电量。而且这些电力消耗除了生产比特币，并没有发挥任何价值。

数据生产速度比较慢。比特币10分钟产生一个区块，每个区块大小2MB，能容纳的数据量也是非常有限的。当前比特币的交易处理速度约7笔每秒，和当前互联网动辄千万的TPS，有着巨大的差异。

随着ASIC和FPGA等特制挖矿芯片的出现，个人PC想挖到比特币简直是天方夜谭。因此，也容易造成算力掌握在某些制芯产业巨头身上，从而形成了中心化。

其他

为了解决POW算力消耗巨大，性能低下的问题，纵然很多类POW系统做了很多改进，如etherum把CPU计算成本降低，提升内存成本来达到同样的安全级别，但本质问题得不到解决。于是出现了更多其他的算法。

POW本质上是所有节点在竞争出块权，而最终只有一个节点胜出。这种方式简单粗暴，但却很公平安全。如果有某种机制，能直接选取出最终具有出块权的节点的话，消耗会低很多，性能也会高很多，核心在于，这种机制也必须是公平公正，且安全的。

POS(Proof of Stake)

一个典型的机制是，每一轮共识从所有节点中随机选择一个节点作为生产者，只需要他去执行出块任务即可，只要足够随机，则算法就是公平公正的。但随机性这本身也是一个需要解决的问题，随机算法必须首先满足是安全，不可篡改，不可预测的。

为了防止节点作恶，所有节点必须提供保证金(Stake)，才能成为能参与POS的节点。一旦节点作恶被发现，则保证金会被罚没，而诚实的工作会得到激励，这样只要作恶带来的收益不超过保证金，节点就会老实的工作。

另外，这里的随机选取并不能真的随机，因为每个人的Stake可能是不同的，因此需要被随机到的概率是和其Stake成正比的，这样才能保证公平。

不难发现，不管是POW还是POS，其实本质上是采用了经济和博弈的思想保证网络的安全可靠。

当前比较常见的区块链项目，如EOS（eos.io ），以太坊casper（casper.com ），Cardano（cardano.org/ ），Dfinity（dfinity.org ）都是采用了POS的思想，只是各自实现上有差异。

VRF(Verified Random Function)

POS有一个很大的问题，就是任何节点都能计算出下一轮被选中的节点是谁，即选取结果是具有先验性的。先验性可能会导致被选取节点遭受恶意的单点攻击，也可能导致其他未被选择的节点消极怠工，给系统增加不稳定风险。

VRF（medium.com/algorand/al… ）实质是一个密码学上的加密方式，对于固定的密钥对（PK，SK）和输入X，VRF产生唯一的伪随机的可验证输出Prove。

每个节点都拥有一对自己的VRF密钥对，在每一轮共识时，用自己的私钥对BlockHeader进行加密计算，当计算的值落在某个特定阈值空间内时，则满足出块条件，否则不允许出块，阈值越小，落在区间内的概率越低。当然，这个阈值空间必须和Stake成正比，才能保证公平性。

VRF算法更像是一个秘密抽签算法，在自己抽的签公布之前，没有人能知道你抽的是什么，而当你公布你的抽签结果时，别人可以简单的进行验证是否合法。这很好的解决了普通POS算法的先验性问题，从而更好地保证系统的安全和文档。

当前使用VRF的项目主要有Algrand（www.algorand.com/ ），而Dfinity声称会引入这个机制，改善其POS的一些弊端。

不可能三角

中心化的分布式一致性协议在CAP理论的指导下，基于各种场景去做一致性，可用性，分区容错性的权衡。在去中心化系统中，通用存在一个不可能的三角问题，即去中心化、性能、安全不可兼得。

去中心化程度越高，系统的开放性就越大，环境越复杂，全网达成共识的时间就越大，从而性能越低，反之，若要更快的达成共识，则需要从控制网络规模，网络复杂度，提高准入门槛等方面去解决，从而牺牲了去中心化的特性。

无论是POW还是POS，或者是以此衍生出来的种种去中心化的共识算法，都在寻找一种合适各自使用场景的最佳平衡。

参考：

比特币介绍，个人认为比较通俗易懂的文章，有兴趣可以阅读：
aquayi.gitbooks.io/master-bitc…

文章版权归作者所有，未经允许请勿转载。

THE END

后端

保障实时音视频服务体验，华为云原生媒体网络有 7 大秘籍

编程有路，开源为径

FFmpeg/Libav 拒绝服务漏洞

Blue River Interactive Mura CMS‘index.cfm’身份验证绕过漏洞

PHP 代码问题漏洞

Ant Design Vue项目（2）

去中心化场景下的一致性协议

引言

挑战

故障错误（Crash Fault）

拜占庭错误（Byzantine Fault）

解决方案

PBFT(Practical Byzantine Fault Tolerance)

概念定义

算法过程

异常控制

局限性和适用场景

POW(Proof of Work)

完全去中心化

共识机制

局限性

其他

POS(Proof of Stake)

VRF(Verified Random Function)

不可能三角