平行区块链之共识篇：RPCA算法
瑞波网络
瑞波网络是由瑞波实验室推出的支付网络，是世界上第一个开放的支付网络，用户通过该网络可兑换任意货币，包括美元，人民币等法币及比特币等数字货币。该网络利用区块链技术去除传统货币兑换网络的中心化，使兑换流程无需任何第三方机构参与，从而节省了成本；因为该网络使用有别于传统区块链技术的PoW共识算法，采用独创的RPCA(Ripple Protocol Consensus Algorithm)，使交易可以在数秒内达成共识。
瑞波共识算法概念初识
让我们先简要认识一下瑞波共识算法里的概念：
● 服务器：服务器是运行Ripple Server软件的任何实体（与仅允许用户发送和接收资金的Ripple Client软件相反），它们参与了协商一致的过程。
● 分类帐：分类帐是每个用户帐户中的货币数量的记录，代表网络的“实质”。分类帐通过添加通过通过共识的交易反复更新。
● 最后关闭的分类账（Last-Closed Ledger）：最后关闭的分类账是已经通过协商一致程序批准的最新分类帐，因此代表了网络的当前状态。
● 唯一节点列表（UNL）：每个服务器s都维护一个唯一的节点列表，它是一组s在确定共识时进行查询的其他服务器。在确定共识时，只考虑UNL的其他成员的投票（而不是网络上的每个节点）。这里唯一的意思是不是由同一个组或个人运行的节点，因此，UNL是一个在整体上是不会相互串通来欺骗网络的网络子集。请注意，“信任”的定义不是要求UNL的每个成员都被信任。
瑞波共识算法共识流程
共识过程是迭代过程，每一轮共识流程大致如下：
1）最初，每个服务器在共同回合开始之前已经看到的所有有效的交易尚未被应用（这些交易可能包括由服务器的终端用户发起的新交易，从先前的协商一致过程持有的交易），并以被称为“候选集”的名单形式公开。
2）然后，每个服务器合并其UNL上的所有服务器的候选集，并对所有交易的真实性进行投票。
3）收到超过最低百分比“是”票的交易将转交给下一轮，没有得到足够投票的交易将被丢弃，或者包含在候选人集合中下一个分类账的共识程序。
4）最后一轮的共识要求服务器UNL的80％的最低百分比达成交易协议。满足此要求的所有交易均采纳进分类帐，该分类帐已封闭，成为新的最后封闭的分类帐。下一轮共识过程开启。
瑞波共识算法技术挑战
近年来，分布式共识系统成为了研究热门，由于该类系统没有唯一控制中心来控制系统的运转，因此一些技术难题随之而来，在这里我们把它们分为三大类：正确性，一致性和高效性。
1
正确性
正确性意味着分布式系统必须能够辨别正确和欺诈交易之间的差异。瑞波共识协议要通过一笔交易必须最终获得80%节点的赞同。因此要保证系统正常运行，要保证80%以上节点为可信节点，即该协议的容错率为20%((n-1)/5),但是超过20%的不可信节点不会导致虚假交易被确认（因为虚假交易想要通过共识也需要80%一上节点的认同）。
假设任何节点决定勾结并加入恶意卡特尔的概率是pc那么正确性的概率为p*给出，其中：
下图描绘了正确性概率如何作为UNL大小的函数的不同图形的图形，如图所示。请注意，这里的垂直轴代表一个恶意的挫败共识的可能性，因此较低的值表示一致成功的概率。从图中可以看出，即使PC高达10％，由于UNL增长超过100个节点，共识被挫败的可能性非常快地变得可以忽略不计。
由上可见保证pc低于0.1，UNL节点数大于100，即可有效防止共识被挫败。
瑞波共识算法通过以下措施降低pc:
1）提供默认UNL。
2）服务器会根据节点法律管辖权（例如美国，中国），政治制度（即民主，共产主义），政治派别（派对），商业类别（例如制造商，零售，金融，教会，政府）选择不同的节点形成UNL。
3）识别一些恶意行为，将有恶意行为的节点从UNL删除。
2
一致性
一致性是指在分布结算制度面前维持单一的全球事实的问题。为了满足一致性要求，系统必须做到，所有非故障节点都可以在同一套交易上达成共识，尽管他们的UNL不同。为保障一致性，瑞波共识协议保证每个节点的UNL之间的连通性，这样便可以保证避免出现分叉，因为列表之间会互相制约。
如下图中：假设左右两个集团a（左），b（右）分属不同服务器的UNL，且他们达成了相反的共识，如对同一笔交易a集团通过，b集团不通过。对于上面一组UNL，a集团的1个节点参与了b集团的共识过程，但1个节点不足b集团6个节点总数的20%，所以a，b集团的共识都会通过，从而产生分裂；而下面一组，a集团中有2个节点参与到b集团的共识过程中，2个节点占b集团7个节点的20%+，所以b的共识不会通过，同理a集团的共识也不会通过，因此不会产生分裂，保证了系统的一致性。
由此可见，保持各个UNL之间的连通性，即可保障系统一致性的达成。
3
高效性
效率是一个稍微更抽象的问题，一般将其定义为分布式支付系统的“有用性”，但实际上通常会简化为系统的延迟，但效率不仅指速度上的优势，还要保证正确性。
瑞波共识算法通过以下措施保证效率：
1)所有节点都有一个强制性的2秒窗口，在每一轮共识中提出其初始候选集。 虽然这确实为每个共识一轮引入了2秒的下限，但它也保证所有具有合理潜伏期的节点都有能力参与协商一致的过程
2）由于每一轮共识的票数记录在分类账中，一些常见的、易于识别的恶意行为（如：在每笔交易上投票为“否”；提出的的交易从未被共识过程通过）可被识别出来，做出这些恶意行为的节点可以被标记和从网络中删除。
3)为所有用户提供了策略化的默认UNL，它被选择以最小化如前面所述的pc。虽然用户可以并且应该选择自己的UNL，但是这个默认的节点列表保证即使是对共识过程一无所知的用户也可以参与到正确性和一致性概率极其高的共识过程中。
4)采用网络分割检测算法来避免网络中的分支。 虽然协商一致的算法证明最后一个关闭的分类帐上的交易是正确的，但它并不禁止在连接不良的网络的不同子部分上存在不止一个上限分类帐的可能性。为了尝试并确定是否发生了这样的分裂，每个节点监视其UNL的活动成员的大小。如果这个大小突然下降到预设的阈值以下，就有可能出现分裂。为了防止UNL中大部分节点因网络延迟使共识过程进入无限等待状态，允许节点发布“部分验证“，它们不对交易处理或投票，但声明仍在参与协商一致的过程，而不是参与断开的子网络上的不同交易。
5)虽然一次共识过程可以采用一轮共识通票的方式，但通过最低通过票数逐轮提高的多轮投票方式更可以提高投票的效率。在有节点成为交易率瓶颈的轮次允许检测潜在节点。这些节点将能够在较低要求轮次期间初始跟踪，但不投票，并在阈值增加时加入到投票过程。在一轮共识的情况下，有可能出现即使是慢节点可以跟上，但最后只有极少的交易通过了80％的门槛的情况，这样效率极低。
总结
毫无疑问瑞波网络共识算法突破了传统区块连共识算法PoW对算力消耗大，区块生成慢的缺点，但其高效性是建立在牺牲部分去中心化的基础上。相对来说，瑞波网络共识算法基本能实现分布式系统的要求。
注：本文由青岛智能产业技术研究院智慧社会研究所王康根据论文“The Ripple Protocol Consensus Algorithm”整理。
扫描上方二维码，关注公众号“平行区块链”，获取更多精彩内容！