RPCA共识算法

1. RPCA概述

目前，针对决拜占庭将军问题，已经有几种可行的解决方案，比如比特币与以太坊采用的POW算法，HyperLedger采用的PBFT算法。然而，在这种分布式支付系统中，由于节点间需要同步沟通，导致共识效率比较低。

在RPCA算法中，为了降低这种同步沟通的成本，使用了一种子网络内部互相信任，由这些内部信任的子网络构成大的网络的方案。这里子网络的信任成本非常低，可以被进一步降低为网络节点对于子网络内部其它节点的原子性选择。另外，为了维护全网节点数据的一致性，子网络之间需要的连接度不能小于一个阈值。

通过以上解决方案，RPCA实现了一种高性能，同时拥有较高拜占庭容错的算法。RPCA算法已经应用在Ripple共识协议中。

2. 要解决的问题

近些年，针对分布式共识系统的研究越来越多，研究的目标是实现一种高性能，低花费，同时去中心化的交易系统。在这类系统的研究过程中主要问题可归为三类：正确性、一致性、可用性。

正确性指的是分布式系统要能识别正常交易与欺诈交易。在中心化系统中，这个问题是通过机构之间的信任以及数字签名来保证交易确实是由某个机构发出来解决的。而在去中心化系统中，大家甚至都不认识对方，自然无法建立类似的信任关系，因此，必须找到一种替代方案来保证交易的正确性。

一致性指的是要在去中心化系统中保证能达成全局唯一的共识。与正确性不同的是，一个恶意用户也许不会发起欺诈交易，但是他可以通过同时发起多笔正确的交易来谋利。在区块链中，典型的例子是“双花”问题。双花问题就是一笔钱花两次，比如你拿着比特币，在A商店买了瓶水，在B商店买了包瓜子。两个商店几乎同时花，假设商店都不等交易确认。那么可能A或B商店最后有一家没有能收到币。那么就实现一次双花。 因此一致性问题可被归结为如何保证系统中只能有一个全局唯一识别的交易集的问题。

可用性在去中心化支付系统中一般指的是性能问题。假设一个系统既能保证正确性又能保证一致性，但是需要一年时间才能确认一笔交易 ，那很显然这个系统的可用性很低。另外，可用性的其它方面包括达成正确性与一致性需要的算力水平、为避免一个用户被欺诈所应用的算法复杂度等。

RPCA算法就能很好的解决以上三个问题。

3. RPCA中的基本概念

在讲算法之前，有一些基本概念需要了解：

1. 服务节点，就是可以接收交易的区块链节点，包括验证节点与非验证节点两种，验证节点是指被其它节点加入到信任列表中的节点，可参与共识过程，非验证节点不参与共识过程。
2. 区块，区块记录交易，在RPCA中有两种区块比较关键，一个是最新关闭的区块，也就是最新被共识过的区块，另一个是开放区块，开放区块是指当前正被共识的区块，当开放区块被共识过，也就成了新的最新关闭的区块。
3. UNL（Unique Node List）信任节点列表，每个服务节点都会维护一个信任节点列表，这里的信任并不是我们通常理解的信任，而是指我信任这个列表中的节点不会联合起来作弊。在共识过程中，我们只接受来自信任节点列表中节点的投票。在Ripple中，我们用在配置文件中加入其它验证节点的公钥的方式来指定UNL。

4.共识过程

Ripple网络每隔几秒就会产生一个新的区块，这个区块的产生过程就是所有网络节点RPCA共识的过程。假设共识过程是成功的，并且网络中没有分叉产生，那么新生成的区块就是全网唯一的。

RPCA对交易分两个阶段完成，第一阶段是达成交易集的共识，第二阶段是对新生成的区块进行提议，最终形成被共识过的区块。

达成交易集的共识分轮进行，在每一轮中进行下面的操作：

交易共识，形成交易集

1 每个节点在共识开始时尽可能多的收集所能收集到的需要共识的交易，并放到“候选集”里面；

2 每个节点对它信任节点列表中的 “候选集”做一个并集，并对每一个交易进行投票；

3 UNL中的服务节点交流交易的投票结果，达到一定投票比例的交易会进入到下一轮，达不到比例的交易要么被丢弃，要么进入到下一次共识过程的候选集中；

1. 在最终轮中，所有投票超过80%的交易会被放到共识过的交易集中，这里的交易集与比特币类似，也是Merkle树的数据结构。

区块打包，再共识

形成交易集后，每个节点开始打包新的区块，打包区块的过程如下：

1. 把当前区块号、共识交易集的Merkle树根Hash、父区块Hash、当前时间戳等内容放到一起，计算一个区块哈希
2. 每个节点广播自己得出的区块哈希到它可见的节点，这里的可见节点不仅仅指可信列表中的节点，而是通过节点发现过程能发现的节点
3. 节点收集到它所有可信列表中节点广播过来的区块哈希后，结合自己生成的区块哈希，对每个区块哈希计算一个比例，如果某一哈希的比例超过一个阈值（一般是80%），则认识这个哈希是共识通过的区块哈希。如果自己的哈希与之相同，则说明自己打包的区块得到了确认，是新的被共识过的区块，直接存到本地，并且更新状态。如果自己的哈希与共识通过的哈希不同，那就需要去某个区块哈希正确的节点索要新的区块信息，要到之后存储到本地并且更新当前状态。
4. 如果上面没有对某一区块哈希超过设定的阈值，那么重新开始共识过程，直到满足条件。

至此，一个区块的共识过程结束，开启下一轮共识过程。

5.验证

前面第三节中我们提出了三个问题，正确性、一致性、可用性，下面我们挨个验证：

1. 正确性：

RPCA中正确性的验证方式很简单，因为共识需要80%的阈值，那么只要UNL中有80%的诚实节点，就能达成共识，另外即使有超过20%的欺诈节点，也不能破坏正确性，因为欺诈节点也必须达到80%以上才能达成共识。无论欺诈节点还是诚实节点，达不到80%，都无法通过共识。

1. 一致性：

RPCA中一致性是通过子网络与其它子网络的连通性来保证的，要保证区块链不分叉，必须确保每个子网络必须至少与整个网络节点中的20%保持连通性。达到20%连通性的前提下，如果一个子网络中得出的共识区块哈希与整个网络得出的不一致，也就无法达成80%的共识要求，也就无法产生分叉。

1. 可用性

在每一轮投票过程中，节点会搜集它UNL中每个节点的响应时间，一直响应时间慢的节点将会被剔除出去，这样UNL就能保持一个较高的沟通效率。在高效沟通的前提下，RPCA算法能保证每3秒左右就能产生一个区块，Ripple官方给出的tps数据是1500。这样的性能基本能满足一般的生产需求。