常见的分布式协议与算法【转】 (5)

image-20200705194418116

最后,当某个将军收到 2f + 1 个验证通过的提交消息后,大部分的将军们已经达成共识,这时可以执行作战指 令了,那么该将军将执行苏秦的作战指令,执行完毕后发送执行成功的消息给苏秦。

image-20200705194505846

最后,当苏秦收到 f+1 个相同的响应(Reply)消息时,说明各位将军们已经就作战指令达 成了共识,并执行了作战指令。

在上面的这个例子中:

可以将赵、魏、韩、楚理解为分布式系统的四个节点,其中赵是主节点(Primary node),魏、韩、楚是从节点(Secondary node);

将苏秦理解为业务,也就是客户端;

将消息理解为网络消息;

将作战指令“进攻”,理解成客户端提议的值,也就是希望被各节点达成共识,并提交 给状态机的值。

最终的共识是否达成,客户端是会做判断的,如果客户端在指定时间内未 收到请求对应的 f + 1 相同响应,就认为集群出故障了,共识未达成,客户端会重新发送请 求。

PBFT 算法通过视图变更(View Change)的方式,来处理主节点作 恶,当发现主节点在作恶时,会以“轮流上岗”方式,推举新的主节点。感兴趣的可以自己去查阅。

相比 Raft 算法完全不适应有人作恶的场景,PBFT 算法能容忍 (n 1)/3 个恶意节点 (也可以是故障节点)。另外,相比 PoW 算法,PBFT 的优点是不消耗算 力。PBFT 算法是O(n ^ 2) 的消息复杂度的算法,所以以及随着消息数 的增加,网络时延对系统运行的影响也会越大,这些都限制了运行 PBFT 算法的分布式系统 的规模,也决定了 PBFT 算法适用于中小型分布式系统。

PoW算法

工作量证明 (Proof Of Work,简称 PoW),就是一份证明,用 来确认你做过一定量的工作。具体来说就是,客户端需要做一定难度的工作才能得出一个结果,验 证方却很容易通过结果来检查出客户端是不是做了相应的工作。

具体的工作量证明过程,就像下图中的样子:

image-20200705195044872

所以工作量证明通常用于区块链中,区块链通过工作量证明(Proof of Work)增加了坏人作恶的成本,以此防止坏 人作恶。

工作量证明

哈希函数(Hash Function),也叫散列函数。就是说,你输入一个任意长度的字符串,哈 希函数会计算出一个长度相同的哈希值。

在了解了什么是哈希函数之后,那么如何通过哈希函数进行哈希运算,从而证明工作量呢?

例如,我们可以给出一个工作量的要求:基于一个基本的字符串,你可以在这个字 符串后面添加一个整数值,然后对变更后(添加整数值) 的字符串进行 SHA256 哈希运 算,如果运算后得到的哈希值(16 进制形式)是以"0000"开头的,就验证通过。

为了达到 这个工作量证明的目标,我们需要不停地递增整数值,一个一个试,对得到的新字符串进行 SHA256 哈希运算。

通过这个示例你可以看到,工作量证明是通过执行哈希运算,经过一段时间的计算后,得到 符合条件的哈希值。也就是说,可以通过这个哈希值,来证明我们的工作量。

区块链如何实现 PoW 算法的?

首先看看什么是区块链:

区块链的区块,是由区块头、区块体 2 部分组成的:

区块头(Block Head):区块头主要由上一个区块的哈希值、区块体的哈希值、4 字节 的随机数(nonce)等组成的。

区块体(Block Body):区块包含的交易数据,其中的第一笔交易是 Coinbase 交易, 这是一笔激励矿工的特殊交易。

在区块链中,拥有 80 字节固定长度的区块头,就是用于区块链工作量证明的哈希运算中输 入字符串,而且通过双重 SHA256 哈希运算(也就是对 SHA256 哈希运算的结果,再执行 一次哈希运算),计算出的哈希值,只有小于目标值(target),才是有效的,否则哈希值 是无效的,必须重算。

所以,在区块链中是通过对区块头执行 SHA256 哈希运算,得到小于目标 值的哈希值,来证明自己的工作量的。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzdyzz.html