在区块链五大特征中，去中心化始终是激辩的话题。狭义来讲，区块链是一种分布式账本，这意味着在区块链这一分布式系统中，是通过各个节点来识别、传播和记载信息。如何在分布式系统中高效地达成共识是分布式计算领域的重要研究问题。
拜占庭将军问题
1982年，Leslie Lamport提出一个故事模型：拥有巨大财富的拜占庭帝国被邻国垂涎已久，然而想要拿下拜占庭，周围邻邦必须同时进攻。然而彼此相距甚远，中间如果有叛徒必定无法完成进攻。这就相当于一个由非信任或半信任的邻国构成的分布式网络，在这一环境中，各邻邦如何达成正确的共识？这样就可以理解，区块链所在的无效区块或问题区块环境（拜占庭），其中多达三分之一的参与者可能是具有优势或控制网络的攻击者。如何确保各个节点得到一致的执行结果？共识算法共识算法解决的是对某个提案 (Proposal)，大家达成一致意见的过程。提案的含义在分布式系统中十分宽泛，如多个事件发生的顺序, 某个键对应的值, 谁是领导等。可以认为任何需要达成一致的信息都是一个提案。实践中，一致性的结果往往还需要客户端的特殊支持，典型地通过访问足够多个服务节点 (背书节点) 来验证确保获取共识后结果。实际上，如果分布式系统中各个节点都能保证以十分强大的性能 (瞬间响应，高吞吐) 无故障的运行，则实现共识过程并不复杂，简单通过多播过程投票即可。可惜的是，现实中这样 “完美” 的系统并不存在，如响应请求往往存在时延，网络会发生中断，节点会发生故障，甚至存在恶意节点故意要破坏系统。一般地，把故障 (不响应) 的情况称为 “非拜占庭错误”，恶意响应的情况称为 “拜占庭错误” (对应节点为拜占庭节点)。针对非拜占庭错误的情况，一般包括 Paxos、Raft算法及其变种。对于要能容忍拜占庭错误的情况，一般包括PBFT系列、PoW系列算法等。从概率角度，PBFT系列算法是确定的，一旦达成共识就不可逆转; 而PoW系列算法则是不确定的，随着时间推移，被推翻的概率越来越小。
PBFT算法
实用拜占庭容错算法（Practical Byzantine Fault Tolerance Algorithm，PBFT），是首个实用的在异步分布式网络中实现拜占庭容错的共识算法。分布式网络的异步是指不对节点的相对处理速度与消息递送时间延迟做任何设定。所谓拜占庭容错，是指在一个若干服务器的系统中，存在非拜占庭错误，即系统中存在少量拜占庭出错节点，仍然能形成共识，则称该系统是拜占庭容错的。PBFT采用三阶段的协议，分别是预准备、准备、确认。预准备和准备阶段保证发送请求的顺序执行；确认阶段保证确认请求的顺序。是保证所有正常节点按照相同的顺序执行所有有效的客户请求。
分布式一致性算法
传统静态拓扑主从模型分布式一致性算法存在严重负载不均及单点性能瓶颈效应，且崩溃节点大于集群规模的 50％ 时算法无法正常工作。针对上述问题，永旗链 (VBC) 提出基于动态拓扑及有限表决思想的分布式一致性算法 (YAC – Yet Another Consensus), 这种算法伴随模块化架构以及简易实现。算法动态生成参与一致性表决的成员子集及Leader节点并时分迁移，形成统计负载均衡；去除要求全体多数派成员参与表决的强约束，使算法具备更高的失效容忍性；并通过日志链机制重新建立算法安全性约束，同时证明了算法的正确性。分布式计算技术的发展平衡了13益膨胀的应用计算性能需求与单机性能瓶颈之间的矛盾，一致性问题是保证分布式系统正确性与可靠性的核心问题。
传统分布式一致性算法，无论幕于 P2P 模型还是主从模型，都存在必须要求半数以上节点存活并参加一致性表决的强约束，也称法定集约束。这是由于从集合论的角度，不可能存在两个多数派成员集合同时投票赞成两个不同议案，因此从数学角度确保一致性算法的正确性，这显著制约了算法的失效容忍性上限。
YAC算法
YAC 分布式系统针对上述传统主流分布式算法中存在的问题提出了改良方法。YAC 算法不采用固定Leader节点，而采用特定的策略动态生成决策成员集合，该集合在集群成员节点中随时域动态迁移，形成统计负载均衡，作为临时负载中心的Leader角色也采用共识机制随上述集合的产生动态生成。YAC 算法放弃采用传统分布式一致性算法中关于半数以上成员节点组成法定集参加表决的幄约束，而在特定时间片内由映射的角色成员集合参与一致性表决。该算法允许实现轻量级客户端，而不需要维护交易的完整历史。每个客户端都与一个用户相连，该用户持有区块链系统中注册的公钥。首先，客户端发送交易至排序服务，然后为交易排序和发出提议区块（一组将被节点验证的交易）。最后，排序服务与所有节点共享提议区块。
在收到排序服务的提议区块后，节点会对已验证的提议区块进行计算。当节点对区块哈希值进行投票时，它会生成当前回合的节点顺序。该顺序是节点的排列，用于在网络中传播选票。该顺序由一个取区块哈希值及初始节点列表为参数的函数生成。排序函数应为纯函数，并返回分布一致的列表。在这一过程中，客户端的角色是生成交易并将其发送给节点，网络中的每个客户端都将自己的交易传播到排序服务。排序服务收集所有交易，对其进行排序并生成提议区块。节点负责对提议区块中的交易达成一致，并在区块中存储已达成一致的交易。为验证提议区块，它需维护完整的交易历史。YAC 与已知的验证节点集合共同合作，主要受传统 PBFT 算法的影响，但在其基础上有显著的提高。传统的基于领导者的算法有一个明显的弱点: 领导者暴露在 DoS 攻击之下，可以审查交易或投票。YAC 算法不需要选举领导者，每个节点都可以收集协作信息。为确保算法安全性，即中间不含写操作的情形下，向集群任意 点发起的任意读请求序列读取到的状态值序列都一致，YAC 定义了下列安全性约束：约束 1:如果一个节点支持一个决议，那么本时间片内不再支持任何其他决议。
约束 2:表决团是原子的，当且仅当半数以上的成员支持一项决议，该决议才获得通过。
约束 3:一个时间片内仅执行一次表决，如果一个时间片内，节点未表决通过或被通知通过一个表决成功的议案，那么节点生成一个空的 Log Entry 链接到本地 Log Chain 副本中。
约束 4:如果同一时问片内，Log Chain的对应Log Entry在集群中同时存在空和非空版本，那么非空Log Entry对应正确的主分支版本。
读懂共识算法|区块链系统中如何高效地达成共识
扫一扫手机访问
