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。这样的性能基本能满足一般的生产需求。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏申龙斌的程序人生

如何开发一款支持多币种的钱包?

除了炒币之外,比较有深度的介入区块链行业的一种办法是开发Dapp,即去中心化的应用。钱包就是一种非常重要的Dapp,可以说是币圈用户的刚需,如果说微信是移动互联...

1354
来自专栏小文博客

PayPal美元提现手续费低至1.2%——连连支付

2763
来自专栏带你撸出一手好代码

浅谈比特币

最近比特币以及各种数字货币火的不行,区块链这个概念也三天两头霸占各种科技头条。以前虽然经常能听到「比特币」这个字眼,可完全没有足够的诱惑力吸引到我, 直到最近,...

3405
来自专栏飞总聊IT

比特币和区块链(3):比特币的共识机制

0 上一篇我们详细介绍了不可篡改的账本区块链的数据结构的实现。其核心技术第一是数字签名,比特币采用的是椭圆曲线数字签名算法。第二是加密级别的哈希,比特币采用的是...

3549
来自专栏服务端技术杂谈

区块链智能合约以太坊

以以太坊为代表的智能合约,被认为是区块链2.0的产物。 区块链可以看作是一个操作系统,而比特币则可以看作其上面生长的明珠。 区块链开发可以看作是自己开发一套系统...

3606

分片:以太坊可扩展性问题的解决方案?

以太坊区块链的创新本质毋庸置疑,其智能合约功能促进了去中心化应用程序(DApps)和初首次币发行(ICOs)的发展。然而,尽管迄今为止以太坊取得了立竿见影的成功...

3884
来自专栏Java架构师进阶

一个程序员眼中的区块链技术

我为什么要写这篇文章?在了解区块链相关信息时(例如维基百科上的内容),我发现这些内容非常零碎和不连贯。要把这些零碎的信息整合在一起,形成一个完整的视图需要花费大...

984
来自专栏陈树义

极简入门:什么是智能合约?

「智能合约」一词是由Nick Szabo在1997年首次提出的,比比特币的出现要早很多。他是位计算机科学家、法学学者,还是个密码译解专家,所以我还是替他跟你「讲...

681
来自专栏区块链大本营

比特币、以太坊、Fabric…你知道它们的优缺点吗?不懂的进

4456
来自专栏区块链大本营

我们是如何用分片技术把7笔/秒的区块链交易提升到2488笔/秒的?

3307

扫码关注云+社区

领取腾讯云代金券