零点课堂 | 区块链主流共识算法分析(1)

据库,密码学相关理论,共识机制P2P网络。本文将详细探讨目前主流的区块链共识算法。

共识算法与CAP理论

要探讨共识算法,首先就需要了解计算机中的CAP理论。CAP是由Eric Brewer在2000年PODC会议上,提出分布式系统不能同时完全满足三个要求的假设,其中包括以下三个方面:

· Consistency:一致性,是指在分布式系统中的所有数据备份,在同一时刻是否具有同样的值。
· Avaliability:可用性,是指在集群中一部分节点故障后,集群群体是否还能响应客户端的读写请求。
· Partition tolerance:分区容错性,以实际效果而言,分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性,就意味着发生了分区的情况,必须就当前操作在C和A之间做出选择。

和所有的分布式系统一样,区块链共识算法设计也是在权衡上面的三个因素。假设区块链中的节点能够立即确认交易数据,这就满足了CAP理论中的AP,可⻛险是失去了数据的强一致性,因为其他节点可能丢弃这个区块,因为区块所在的区块链分叉在竞争性的选举中失败了;如果是为了获得强一致性,即满足CP的话,那么客户端应该等待区块链中的大多数节点都接受了这笔交易后才能真正的接收它,这说明了这笔交易所在的分叉已经选举胜利,获得了大部分的共识,获得了强一致性。但是代价却是失去了可用性。

那么为什么没有CA这种情况呢?首先在分布式环境下,网络分区是一个自然的事实。因为分区是必然的,所以如果舍弃P,意味着要舍弃分布式系统,那这也就没有必要再讨论CAP理论了。所以在上述中,我们以系统在满足P的前提下,探讨了CP和AP两种情况下的得与失。

主流的共识算法概述

目前业界主流的区块链共识算法有工作量证明POW,权益证明POS,授权股权证明DPOS,用于Hyperledger的拜占庭算法PBFT等。下面将对这几种共识的典型代表进行讲解。

工作量证明POW

工作量证明POW(Proof-of-work)在区块链中最早被提及的是,2008年中本聪的比特币白皮书论文《A peer to peer electronic cash system》,并随后在2009年应用到比特币(BiTCOin)中。该共识算法的设 计理念是整个分布式系统的节点中,每个节点为整个系统提供计算能力(简称算力),通过一个竞争机制, 让计算工作完成最出色的节点获得系统的奖励,从而完成新生成货币的分配。

POW工作量证明需要满足三个要素,分别是:

· 工作量证明函数
在比特币中使用的是SHA256函数,是密码哈希函数家族中输出值为256位的哈希算法。

· 区块
在区块中会利用到merkle算法,将交易以树的形式进行组合,然后两两进行哈希运算,当为奇数的时候则多算上最后一个交易进行补充。依次进行以叶子节点向根节点的运算,并最终得到根节点的hash值。包含在区块头中。

· 难度值

难度值默认是每2016个区块调节一次(大概2周)。
难度系数 = 期望2016个区块生成所有的时间 / 实际所用的分钟数 = 20160 / 实际所用的分钟数
如果矿工可以比预期更快的构建区块,比如9分钟出一个块,套用公式:
难度系数 = (2016 * 10) / (2016 * 9) = 1.11
每个节点使用这个数值来计算下一个阶段2016区块的难度值:
Difficulty * 1.11 = new Difficulty
如果系数大于1(即区块出块速度大于预期),难度值将提高;
如果系数小于1(即区块出块速度小于预期),难度值降低。

POW工作量证明的流程如下:

区块链主流共识算法分析

从流程图中可以看出,POW工作量证明的流程主要经历三步:

· 生成Merkle根哈希
· 组装区块头
· 计算出工作量证明的输出

在这里,我们以伪代码的形式去理解工作量证明的输出:

i. 工作量证明的输出 = SHA256(SHA256(区块头 + 变更的随机数))
ii. if (工作量证明的输出 >= 目标值),变更随机数,递归i的逻辑,继续与目标值比对。
iii. if (工作量证明的输出 >= 目标值),变更随机数,递归i的逻辑,继续与目标值比对。

最后,生成的符合难度的区块,将通过P2P传递到比特币的全网络节点并接收,添加到原有区块链的尾部。

由此,我们可以看到POW主要是通过CPU的算力来保证全网的共识安全。

本文由 零点财经 作者:tao 发表,其版权均为 零点财经 所有,文章内容系作者个人观点,不代表 零点财经 对观点赞同或支持。如需转载,请注明文章来源。
分享生成图片
50

发表回复

零点课堂 | 区块链主流共识算法分析(1)

2021-06-22 10:44:45

据库,密码学相关理论,共识机制P2P网络。本文将详细探讨目前主流的区块链共识算法。

共识算法与CAP理论

要探讨共识算法,首先就需要了解计算机中的CAP理论。CAP是由Eric Brewer在2000年PODC会议上,提出分布式系统不能同时完全满足三个要求的假设,其中包括以下三个方面:

· Consistency:一致性,是指在分布式系统中的所有数据备份,在同一时刻是否具有同样的值。
· Avaliability:可用性,是指在集群中一部分节点故障后,集群群体是否还能响应客户端的读写请求。
· Partition tolerance:分区容错性,以实际效果而言,分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性,就意味着发生了分区的情况,必须就当前操作在C和A之间做出选择。

和所有的分布式系统一样,区块链共识算法设计也是在权衡上面的三个因素。假设区块链中的节点能够立即确认交易数据,这就满足了CAP理论中的AP,可⻛险是失去了数据的强一致性,因为其他节点可能丢弃这个区块,因为区块所在的区块链分叉在竞争性的选举中失败了;如果是为了获得强一致性,即满足CP的话,那么客户端应该等待区块链中的大多数节点都接受了这笔交易后才能真正的接收它,这说明了这笔交易所在的分叉已经选举胜利,获得了大部分的共识,获得了强一致性。但是代价却是失去了可用性。

那么为什么没有CA这种情况呢?首先在分布式环境下,网络分区是一个自然的事实。因为分区是必然的,所以如果舍弃P,意味着要舍弃分布式系统,那这也就没有必要再讨论CAP理论了。所以在上述中,我们以系统在满足P的前提下,探讨了CP和AP两种情况下的得与失。

主流的共识算法概述

目前业界主流的区块链共识算法有工作量证明POW,权益证明POS,授权股权证明DPOS,用于Hyperledger的拜占庭算法PBFT等。下面将对这几种共识的典型代表进行讲解。

工作量证明POW

工作量证明POW(Proof-of-work)在区块链中最早被提及的是,2008年中本聪的比特币白皮书论文《A peer to peer electronic cash system》,并随后在2009年应用到比特币(BiTCOin)中。该共识算法的设 计理念是整个分布式系统的节点中,每个节点为整个系统提供计算能力(简称算力),通过一个竞争机制, 让计算工作完成最出色的节点获得系统的奖励,从而完成新生成货币的分配。

POW工作量证明需要满足三个要素,分别是:

· 工作量证明函数
在比特币中使用的是SHA256函数,是密码哈希函数家族中输出值为256位的哈希算法。

· 区块
在区块中会利用到merkle算法,将交易以树的形式进行组合,然后两两进行哈希运算,当为奇数的时候则多算上最后一个交易进行补充。依次进行以叶子节点向根节点的运算,并最终得到根节点的hash值。包含在区块头中。

· 难度值

难度值默认是每2016个区块调节一次(大概2周)。
难度系数 = 期望2016个区块生成所有的时间 / 实际所用的分钟数 = 20160 / 实际所用的分钟数
如果矿工可以比预期更快的构建区块,比如9分钟出一个块,套用公式:
难度系数 = (2016 * 10) / (2016 * 9) = 1.11
每个节点使用这个数值来计算下一个阶段2016区块的难度值:
Difficulty * 1.11 = new Difficulty
如果系数大于1(即区块出块速度大于预期),难度值将提高;
如果系数小于1(即区块出块速度小于预期),难度值降低。

POW工作量证明的流程如下:

区块链主流共识算法分析

从流程图中可以看出,POW工作量证明的流程主要经历三步:

· 生成Merkle根哈希
· 组装区块头
· 计算出工作量证明的输出

在这里,我们以伪代码的形式去理解工作量证明的输出:

i. 工作量证明的输出 = SHA256(SHA256(区块头 + 变更的随机数))
ii. if (工作量证明的输出 >= 目标值),变更随机数,递归i的逻辑,继续与目标值比对。
iii. if (工作量证明的输出 >= 目标值),变更随机数,递归i的逻辑,继续与目标值比对。

最后,生成的符合难度的区块,将通过P2P传递到比特币的全网络节点并接收,添加到原有区块链的尾部。

由此,我们可以看到POW主要是通过CPU的算力来保证全网的共识安全。