大数跨境

【区块链技术】常见的共识算法资料调研

【区块链技术】常见的共识算法资料调研 数组智控产业发展科技院
2022-03-17
3
导读:本人很忌讳去研究虚拟B,但是研究到共识的时候又不得不去调研这方面的资料,以便更好的理解,大家全当是研究研究技


本人很忌讳去研究虚拟B,但是研究到共识的时候又不得不去调研这方面的资料,以便更好的理解,大家全当是研究研究技术而已。


1.工作量证明


工作量证明(Proof of Work, PoW)是一种应对拒绝服务攻击和其他服务滥用的经济对策。


它要求发起者进行一定量的运算,也就意味着需要消耗计算机一定的时间


这个概念由Cynthia Dwork和Moni Naor 1993年在学术论文中首次提出。而工作量证明(PoW)这个名词,则是在1999年Markus Jakobsson和Ari Juels的文章中才被真正提出。


在比特币之前,哈希现金被用于垃圾邮件的过滤,也被微软用于Hotmail/Exchange/Outlook等产品中。


工作量证明系统的主要特征是客户端需要做一定难度的工作得出一个结果,验证方却很容易通过结果来检查出客户端是不是做了相应的工作。


这种方案的一个核心特征是不对称性:工作对于请求方是困难的,对于验证方则是简单的。


具体来讲,每个可出块节点通过不断猜测一个数值(nonce),使得该数值拼凑上所出块中包含的交易内容的哈希值满足一定条件。


由于哈希问题在目前的计算模型下是一个不可逆的问题,除了反复猜测数值,进行计算验证外,还没有有效的方法能够逆推计算出符合条件的nonce值。


且比特币系统可以通过调整计算出的哈希值所需要满足的条件来控制计算出新区块的难度,从而调整生成一个新区块所需的时间的期望值。


Nonce值计算的难度保证了在一定的时间内,整个比特币系统中只能出现少数合法提案。


另外,在节点生成一个合法提案后,会将提案在网络中进行广播,收到的用户在对该提案进行验证后,会基于它所认为的最长链的基础上继续生成下一个分叉。


这种机制保证了系统中虽然可能会出现分叉,但最终会有一条链成为最长的链,被绝大多数节点所共识。


然而,由于比特币采用SHA-256算法,挖矿速度与机器算力成正比,这就催生了专门的“挖矿专用集成电路”,即矿机。


矿机的挖矿效率相比普通的GPU高数个数量级,带来的影响即是算力越发集中于专用矿场,使得普通用户难以入场,降低了区块链的“去中心化”程度。


针对这个问题,莱特币采用了一种“内存难题算法”——Scrypt作为其挖矿算法,其求解速度主要取决于计算机内存大小,这大大降低了大规模矿场在莱特币中的优势,使得去中心化这一特性得以保证。


当前,以太坊所采用的PoW算法——Ethash也与Scrypt类似,是一种“内存难题算法”,其所要解决的主要问题也是专用矿机相比普通PC在挖矿上展现出来的巨大优势。


2.权益证明


PoW虽然是目前区块链平台采用最多的共识算法,且其可靠性已经得到了大量验证,然而PoW并不是没有缺陷,相反,其对能源的大量消耗一直饱受诟病,同时矿池引起的中心化问题也一直争议不断。


在这样的背景下,权益证明(Proof ofStake, PoS)共识算法应运而生。


最早出现的权益证明共识算法的应用是在点点币(PeerCoin, PPC)平台,这里PoS是一个根据你持有货币的量和时间,给你发利息的一种制度。


具体地,平台里有一个名词叫币龄,每个币每天产生1币龄,比如你持有100个币,总共持有了30天,那么,此时你的币龄就为3000,这个时候,如果你发现了一个区块,你的币龄就会被清空为0。


假如你每被清空365币龄,将会从区块中获得0.05个币的利息,那么在这个案例中,利息为:3000×5%/365=0.41个币。


在该PoS体系中,仍然需要挖矿,该机制只是根据币龄降低挖矿难度,加快寻找随机数的时间,这一定程度上减少了计算哈希的资源消耗。


另外一种PoS的实现,则是像以太坊未来会采用的共识算法一样,每个节点通过缴纳一定数量的以太币作为保证金来参与验证工作,如果权益人做出不诚实的行为,其保证金则会被罚掉。


此外,Algorand、Quroboros等都是目前很热门的PoS类共识算法。


3.委托股权证明


PoS共识算法确实可以解决很多PoW共识算法的问题,但是对于没币的人而言,他们并无代价可付,使得一些恶意行为对于他们是有益的,这就会导致著名的公地悲剧。


在PoS作为共识算法的区块链系统里,上述问题叫做无利益攻击,所以必须有对付这种攻击的有效办法,否则就不能直接使用。


PoS的一个变种算法DPoS,就是解决无利益攻击的一种有效方式,即只有公认具有较大权益的节点才能参加共识。


因此,DPoS的本质实际上是一个中心化的共识机制。


其中,EOS网络即对DPoS共识算法进行了可靠尝试。


EOS网络在刚发布的时候采用了DPoS的共识机制——委托股权证明(DelegatedProof of Stake, DPoS),这种共识机制的基本原理是,网络中的所有节点依据他们所拥有的代币的量,分配对应的投票权重;


网络中的所有节点进行投票,选出一定数量的(EOS使用的是21个)区块生产者进行新区块的生产与协商。


区块生产者通过某种方式(随机或顺序)进行出块,且每个区块生产者通过出块来对之前的块进行确认。


一个交易在2/3以上(14个)的见证人确认后,达到不可逆状态。


这样,EOS每个超级节点在6秒钟之内出12个块,平均每半秒出一个块的速度下,一个交易需要达到不可逆状态所需的确认时间为90秒(需要等待14个其他见证人出块以确认自己)。


总的来说,每期选举出固定数目的区块生产者后,区块生产者之间可建立直接连接从而保证通信的可靠及快速,DPoS就能在较快的时间里达成共识。


4.瑞波共识


严格来说,瑞波网络并不能算是去中心化的数字货币。


在瑞波网络中,用户发起的交易经过追踪节点(tracking node)或验证节点(validating node)的广播而传递到整个网络中。


其中,追踪节点主要负责与客户端的交易请求交互及分发交易信息,验证节点则除了具有追踪节点的功能外,还负责在节点间达成并维系共识,并向账本中添加新的交易信息。


瑞波网络中的每个验证节点都预先配置了一份可信任节点名单(Unique NodeList, UNL),并与名单中的每个节点维护着点对点的网络连接,因此可以实现较快的通信。


每间隔一段时间,瑞波网络将进行如下的共识过程。


1)每个验证节点会不断收到从网络发送过来的交易,通过与本地账本数据验证后,不合法的交易直接丢弃,合法的交易将汇总成交易候选集(candidateset)。


交易候选集里面还包括之前共识过程无法确认而遗留下来的交易。


2)每个验证节点把自己的交易候选集作为提案发送给其他验证节点。


3)验证节点在收到其他节点发来的提案后,如果不是来自UNL上的节点,则忽略该提案;


如果是来自UNL上的节点,就会对比提案中的交易和本地的交易候选集,如果有相同的交易,该交易就获得一票。


在一定时间内,当交易获得超过50%的票数时,则该交易进入下一轮。


没有超过50%的交易,将留待下一次共识过程去确认。


4)验证节点把超过50%票数的交易作为提案发给其他节点,同时提高所需票数的阈值到60%,重复步骤3)、步骤4),直到阈值达到80%。


5)验证节点把经过80%UNL节点确认的交易正式写入本地的账本数据中,称为最后关闭账本(Last Closed Ledger),即账本最后(最新)的状态。


可以看到,在瑞波网络的共识算法中,参与共识的验证节点是事先知道的,且验证节点间的通信是很快的,因此其达成共识的效率很高,且没有PoW类共识算法的额外计算开销。


当然,这也使得瑞波网络只适用于联盟链的场景。


瑞波网络的共识拜占庭容错能力为(n-1)/5,即可以容忍验证节点的20%出现拜占庭错误。


5.拜占庭将军共识


拜占庭将军问题是用来解释异步系统中存在恶意节点情况下的共识问题的一个虚构模型。


拜占庭地域宽广,守卫边境的多个将军需要通过信使来传递消息,进而达成一致决定——是否攻击某一支敌军。


问题是这些将军在地理上是分隔开来的,并且将军中存在叛徒。


叛徒可以任意行动以达到以下目标:


欺骗某些将军采取进攻;


促成一个不是所有将军都同意的决定,例如,当将军们不希望进攻时促成进攻行动;


或者迷惑某些将军,使他们无法做出决定。


如果叛徒达到了这些目的的任意一个,则任何攻击行动都是注定要失败的,只有完全达成一致的努力才能获得胜利。


拜占庭假设是对现实世界的模型化,由于硬件错误、网络拥塞或断开以及遭到恶意攻击,计算机和网络可能出现不可预料的行为。


拜占庭容错协议必须处理这些失效,并且这些协议还要满足所要解决的问题要求的规范。


这些算法通常以其弹性t作为特征,t表示算法可以应付的错误节点数。


很多经典算法问题只有在t小于n/3时才有解,如实用拜占庭容错算法(PBFT),其中n是系统中的节点总数。


算法核心的关键在于少数人服从多数人这个策略。


以4个将军为例,当叛变者小于或等于1时,系统总能达成共识。


具体说明如下:


将军A将信息传递给将军B、C、D,且传递一定有结果,消息简单分为进攻、撤退(分别用0,1表示)两种,假定大家各自的决定是进攻(0)。


第一种情况,当发令者将军A不是叛徒,而传递后的将军中有一个叛徒(例如B),则会有以下情况:


A的信息正确传递到BCD,

B将错误的信息发送给CD,

但是由于CD发送的结果是正确的,

所以最终每个节点都以多数0胜过了少数1,

达成一致的进攻决议。



当发令者将军A是叛徒时,A向B发送消息0,向CD发送1。


但由于B接收到CD的消息为1,且相互传递后有四条正确信息。


因此,最终结果还是以多数正确(4个1)赢过少数错误(2个0)而最终实现一致。



由此可见,无论哪种情形,系统均可达成一致共识。


当然上述描述只是一个简单示意,具体一个完全可用的拜占庭容错共识算法可以参见PBFT及其变种算法,而近期大红大紫的Algorand,其本质上也是一种拜占庭容错算法。


广义来讲,区块链系统中的共识算法均为拜占庭容错共识算法,因为区块链主要应对的就是各类外在欺骗、攻击行为,只不过前面所述的共识算法并不是强一致的共识算法,而是一种最终一致的共识算法,需要依赖链式结构或者DAG结构来完成算法的一致性;


而如PBFT这样的共识算法则是强一致的共识算法,一旦经过共识便是一致确定的结果,不会出现反复的情况,这也是前述共识算法与其他类区块链共识算法的核心区别。


暂时还没发现哪个共识会成为Web3.0的标准潜力,所以在第三代互联网概念上,我们目前依然尚在路上。


【声明】内容源于网络
0
0
数组智控产业发展科技院
以AI技术为底层能力,聚焦智慧园区、城市公共安全、数智警务、健康医疗、能源电力、科研实验及平安校园等领域,提供从感知到决策的全流程软硬件一体化的国产装备智能体产品解决方案。
内容 986
粉丝 0
数组智控产业发展科技院 以AI技术为底层能力,聚焦智慧园区、城市公共安全、数智警务、健康医疗、能源电力、科研实验及平安校园等领域,提供从感知到决策的全流程软硬件一体化的国产装备智能体产品解决方案。
总阅读1.6k
粉丝0
内容986