设为首页收藏本站
查看: 129|回复: 0

SERO Se—Random共识算法探索

[复制链接]
发表于 2019-6-5 12:03:03 | 显示全部楼层 |阅读模式

      PBFT是一种经典的联盟链共识算法,在节点情况较少的情况下,性能比较高,安全性也比较好,因此EOS、COSMOS、NEO基本上都是用的PBFT—DPOS,极大的提高了公链的性能与安全性。但是在主网节点众多的情况下,性能会直线下降,极大的限制了主网的速度,但是VRF(可验证随机函数) 随机函数的出现改变了这一现状,VRF可以在保证安全、去中心化的情况下随机选取主网的节点进行验证、广播、出块,解决了DPOS的去中心化问题。今天的主角就是SERO的SE-Random(PBFT+VRF)共识算法
共识算法层面在去中心化基础上解决区块链性能的最优算法,SERO超零协议的SE-Random共识(PBFT+VRF)
QQ截图20190605115035.png
本篇文章会从PBFT、VRF(简介、工作原理)—SE-Random(PBFT+VRF)—多共识算法对比来简单的讲解SE-Random共识算法。

PBFT简介:
       PBFT是Practical Byzantine Fault Tolerance的缩写,意为实用拜占庭容错算法。该算法是Miguel Castro (卡斯特罗)和Barbara Liskov(利斯科夫)在1999年提出来的,解决了原始拜占庭容错算法效率不高的问题,将算法复杂度由指数级降低到多项式级,使得拜占庭容错算法在实际系统应用中变得可行。该论文发表在1999年的操作系统设计与实现国际会议上(OSDI99)。没错,这个Loskov就是提出著名的里氏替换原则(LSP)的人,2008年图灵奖得主。
QQ截图20190605115120.png


工作原理:
PBFT算法流程:
       PBFT算法前提,采用密码学算法保证节点之间的消息传送是不可篡改的。
PBFT容忍无效或者恶意节点数:f,为了保障整个系统可以正常运转,需要有2f+1个正常节点,系统的总节点数为:|R| = 3f + 1。也就是说,PBFT算法可以容忍小于1/3个无效或者恶意节点,该部分的原理证明请参考PBFT论文,下文有链接地址。
PBFT是一种状态机副本复制算法,所有的副本在一个视图(view)轮换的过程中操作,主节点通过视图编号以及节点数集合来确定,即:主节点 p = v mod |R|。v:视图编号,|R|节点个数,p:主节点编号。
QQ截图20190605115131.png


PBFT算法主体实现流程图如下:
1. REQUEST:
客户端c向主节点p发送<REQUEST, o, t, c>请求。o: 请求的具体操作,t: 请求时客户端追加的时间戳,c:客户端标识。REQUEST: 包含消息内容m,以及消息摘要d(m)。客户端对请求进行签名。
2. PRE-PREPARE:
主节点收到客户端的请求,需要进行以下交验:
a. 客户端请求消息签名是否正确。
非法请求丢弃。正确请求,分配一个编号n,编号n主要用于对客户端的请求进行排序。然后广播一条<<;PRE-PREPARE, v, n, d>,  m>消息给其他副本节点。v:视图编号,d客户端消息摘要,m消息内容。<;PRE-PREPARE, v, n, d>进行主节点签名。n是要在某一个范围区间内的[h, H],具体原因参见垃圾回收章节。
3. PREPARE:
副本节点i收到主节点的PRE-PREPARE消息,需要进行以下交验:
a. 主节点PRE-PREPARE消息签名是否正确。
b. 当前副本节点是否已经收到了一条在同一v下并且编号也是n,但是签名不同的PRE-PREPARE信息。
c. d与m的摘要是否一致。
d. n是否在区间[h, H]内。
非法请求丢弃。正确请求,副本节点i向其他节点包括主节点发送一条<;PREPARE, v, n, d, i>消息, v, n, d, m与上述PRE-PREPARE消息内容相同,i是当前副本节点编号。<;PREPARE, v, n, d, i>进行副本节点i的签名。记录PRE-PREPARE和PREPARE消息到log中,用于View Change过程中恢复未完成的请求操作。
4. COMMIT:
主节点和副本节点收到PREPARE消息,需要进行以下交验:
a. 副本节点PREPARE消息签名是否正确。
b. 当前副本节点是否已经收到了同一视图v下的n。
c. n是否在区间[h, H]内。
d. d是否和当前已收到PRE-PPREPARE中的d相同
非法请求丢弃。如果副本节点i收到了2f+1个验证通过的PREPARE消息,则向其他节点包括主节点发送一条<COMMIT, v, n, d, i>消息,v, n, d,  i与上述PREPARE消息内容相同。<COMMIT, v, n, d, i>进行副本节点i的签名。记录COMMIT消息到日志中,用于View Change过程中恢复未完成的请求操作。记录其他副本节点发送的PREPARE消息到log中。
5. REPLY:
主节点和副本节点收到COMMIT消息,需要进行以下交验:
a. 副本节点COMMIT消息签名是否正确。
b. 当前副本节点是否已经收到了同一视图v下的n。
c. d与m的摘要是否一致。
d. n是否在区间[h, H]内。
QQ截图20190605115144.png


        非法请求丢弃。如果副本节点i收到了2f+1个验证通过的COMMIT消息,说明当前网络中的大部分节点已经达成共识,运行客户端的请求操作o,并返回<REPLY, v, t, c, i, r>给客户端,r:是请求操作结果,客户端如果收到f+1个相同的REPLY消息,说明客户端发起的请求已经达成全网共识,否则客户端需要判断是否重新发送请求给主节点。记录其他副本节点发送的COMMIT消息到log中。

VRF简介:
       可验证随机函数(Verifiable Random Function),简称为VRF,是一种加密原语,可将输入映射到可验证的伪随机输出。 在1999年,Micali(Algorand的创始人),Rabin和Vadhan推出了VRF。 如今,VRF算法被用在各种加密方案,协议和系统中。
Algorand率先使用VRF进行秘密地加密抽签,以选举委员会来运行共识协议。 这使得Algorand区块链能够实现支持数百万用户所需的规模和性能。 到目前为止,其他区块链项目也在共识协议中使用同样的想法来执行领导者或委员会选举。
在本文中,我们将介绍VRF的基础知识; 并讨论其关键属性如何在Algorand区块链中进行独特和安全的委员会选举,并扩展我们选择在Algorand实施的特定VRF。
QQ截图20190605115153.png
VRF工作原理
       要理解VRF的工作原理,先理解一下这里说的“随机”是什么意思:一个理想的哈希函数,其值域应该是离散的、均匀分布的,给定不同的输入值,其输出值应该没有规律,随机的分布在值域区间内。
       再看一个简单的哈希函数变种,即结合了密钥secret的哈希函数,比如result = SHA256(secret,info),那么要得到结果result,仅仅拥有info是不够的,必须要知道secret才能计算出来,或者说我们已经拥有了结果result和info,但是必须知道secret才能验证info和result是否是匹配,这就是带密钥的哈希函数。此时引出另一个问题,有没有可能不通过密匙secret,也能验证info和result是匹配的?于是就有了可验证的随机函数即:VRF。实现原理:结合了非对称加密技术的哈希函数,例如:result = VRF_Hash(SK, info), SK是私钥,不公开,和SK对应的公钥PK,需要发送给验证者。

QQ截图20190605115204.png
具体操作流程如下:
1. 证明者生成一对密钥,SK、PK;
2、证明者计算result = VRF_Hash(SK,info);
3、证明者计算proof = VRF_Proof(SK,info);
4、证明者把result和proof递交给验证者;
5、 验证者计算result = VRF_P2H(proof)是否成立,若成立,继续下面的步骤,否则中止;
6、 证明者把PK,info递交给验证者;
7、 验证者计算True/False = VRF_Verify(PK, info, proof) ,True表示验证通过,False表示验证未通过。
所谓的验证通过,就是指proof是否是通过info生成的,通过proof是否可以计算出result,从而推导出info和result是否对应匹配、证明者给出的材料是否有问题。在整个操作流程中,证明者始终没有出示自己的私钥SK,验证者却可以推导出info和result是否对应匹配,这就是VRF的妙用。

SE-Random:PBFT+VRF



SE-Random简介:
       SE-Random是一个结合VRF(Verifiable Random Function)和PBFT的全新共识算法,是SERO的SE-Random的核心共识算法。SE-Random可以支持共识群体的规模性扩展,通过VRF保障了共识群体生成的随机性和公平性,同时保证快速地达到状态终局性。
SERO在研究各类共识的基础上,提出了⾃⼰的主链共识引擎SE-Random。SE-Random共识引擎的设计思路受到最新⼀代共识研究Algorand和Ourboros的启发,只需要验证节点很少的计算开销,整个区块链⽹络产⽣分叉概率极⼩,并能实现近乎⽆限的扩展性。

QQ截图20190605115216.png
下⾯描述⼀下SE-Random共识的细节。
SE-Random使⽤拜占庭协议SE-RANDOM(Byzantine Agreement)在⼀组交易中达成共识。为了扩展性,SE-Random使⽤⼀种随机算法筛选出⼀批⽤户,允许⽤户⾃⼰私下检查是否被选中,并参与SE-RANDOM协议中共识的达成。在此算法下,随着⽤户量的增多,整个SE-RANDOM共识系统不会变慢。

SE-Random共识的工作原理
       在随机选出的验证者节点中进⾏SE-Random共识计算
验证节点(包括⼦验证节点)在秘密的情况下获知⾃⼰被选中,但他们只有公布凭证才能证明⾃⼰的验证者资格。对于每⼀个选中的节点,使⽤⾃⼰的私钥对seed进⾏签名,并输⼊哈函数后得到⾃⼰的凭证。哈希函数的性质表明凭证是⼀个随机的⻓度为256的字符串,不同节点的凭证不会相同,并且凭证字符串的分布是均匀的。⽤同样的⽅式选出⼀批候选领导节点,把候选领导节点的凭证按照字典顺序进⾏排列,排序中最⼩的候选领导节点被选为领导节点,即领导节点是通过候选领导节点集合随机的公共选举产⽣。
验证节点和领导节点⼀起参与拜占庭协议SE-RANDOM的运算,在SE-RANDOM的每⼀个阶段和步骤⾥,节点都通过私⼈和⾮互动的⽅式来独⽴确定⾃⼰是否被选择在当前步骤的委员会中。SE-RANDOM是⼀个两个阶段的投票机制。第⼀阶段,验证节点对收到的候选区块进⾏分级共识,选取验证共识最多的候选区块。第⼆阶段,对第⼀阶段筛选出的候选区块进⾏⼆元拜占庭判断。SE-RANDOM共识要保证参与共识的诚实节点⼤于2/3,如果随机选出的集合不能满⾜该条件,那么需要进⾏多次随机选举,只要有⼀次参与共识的诚实节点⼤于2/3,就能达成共识。SE-RANDOM共识的每个步骤的验证节点并⾏指定或抽签筛选出来⽤来加快共识确认速度。

SE-Random共识算法的计算流程:
QQ截图20190605115239.png


分级共识协议
       这个协议将在任意⼀个块上达成⼀致的问题转化为在的两个值上达成⼀致,这两个值是最后确定特定块的散列或者空块的散列的依据,总共分为3个步骤,我们会在后⾯的技术⻩⽪书中详细说明。⼤体来说判断消息中是否有超过2/3的 并且相同,如果有,则⼴播此特定区块,如果没有,则⼴播空块,此消息⽤于后继⼆元拜占庭判断。

元拜占庭判断
在这⾥验证节点统计判断分级共识协议发出的值。⼆元拜占庭判断是⼀个三步的循环,验证节点会不断的对收到的历史进⾏检查,看是否达到了有两种结束条件,即区块合法或者区块不合法是否达到2/3的投票总数;如果区块不合法,共识系统会判断并⽣成⼀个空区块。为了预防⽆限循环的情况发⽣,我们会设定⼀个最⼤总循环数m,如达到m后还没判定出是否符合⼀个结束条件,共识系统会临时⽣成暂定的共识,并在后续过程中(后⾯⼏轮)形成最终共识,并确认这些较早的交易。
SE-Random共识会适应⽹络弱同步情况下的共识判定。在⽹络强情况下不会造成区块分叉,在⽹络弱同步情况下,会临时做出暂定共识并在⽹络强同步恢复后达到最终共识。SE[1]random可以防范⼥巫攻击、⾃私挖矿攻击、Nothing-at-Stake攻击、远程攻击等各类攻击⽅式。即使SERO链的⽤户扩散到亿级以上的节点,SE-Random共识也可借助VRF机制快速达成全⽹⼀致的拜占庭共识。


共识对比

QQ截图20190605115304.png




上一篇:2019年区块链技术发展趋势
下一篇:TRBBEX全球火爆的数字资产交易中心
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

 
在线客服
点击这里给我发消息
Loading...
快速回复 返回顶部 返回列表