原创

分布式基础(九)——分布式理论之分布式一致性:PoW算法

谈起比特币,大家至少都应该有所耳闻吧?比特币是基于区块链实现的,而区块链运行在Internet上,这就存在有人试图作恶的情况。

前面几章,我提到的口信消息解决方案和PBFT算法,虽然能防止坏人作恶,但只能防止少数,也就是 (n-1)/3 个坏人 (其中 n 为节点数)。可由于很多区块链是在公网环境,可能有坏人不断增加节点数,轻松突破 (n - 1) / 3 的限制。

解决上述问题的方法就是PoW算法。PoW算法通过工作量证明(Proof of Work)增加了坏人作恶的成本,以此防止坏人作恶。本章,我就来讲讲PoW算法的原理。

一、工作量证明

什么是工作量证明 (Proof Of Work,简称PoW) ?你可以这么理解:就是一份证明,用来确认你做过一定量的工作。比如,你的大学毕业证书就是一份工作量证明,证明你通过 4 年的努力完成了相关课程的学习。

那么,回到计算机世界,具体来说就是,客户端需要做一定难度的工作才能得出一个结果,验证方却很容易通过结果来检查出客户端是不是做了相应的工作。

比如小肖去Google面试,说自己的编程能力很强,那么她需要做一定难度的工作(比如做个算法题)。根据做题结果,面试官可以判断她是否适合这个岗位。这就是一个现实版的工作量证明。具体的工作量证明过程,就像下图中的样子:



1.1 哈希运算

既然工作量证明是通过指定的结果,来证明自己做过了一定量的工作。那么在区块链的 PoW 算法中需要做哪些工作呢?答案是哈希运算

哈希运算的核心是哈希函数(Hash Function),也叫散列函数。就是说,你输入一个任意长度的字符串,哈希函数会计算出一个哈希值。比如,我们对任意长度字符串(比如"tutuxiao")执行 SHA256 哈希运算,就会得到一个 32 字节的哈希值,就像下面的样子:

$ echo -n "tutuxiao" | sha256sum
bb2f0f297fe9d3b8669b6b4cec3bff99b9de596c46af2e4c4a504cfe1372dc52

那么我们如何通过哈希运算来证明工作量呢?

举个例子,我们给出的工作量要求是:基于一个基本的字符串(比如"tutuxiao"),在这个字符串后面添加一个整数值,然后对变更后的字符串进行 SHA256 哈希运算,如果运算后得到的哈希值(16 进制形式)是以"0000"开头的,就验证通过;为了达到这个工作量证明的目标,我们需要不停地递增整数值,对得到的新字符串进行 SHA256 哈希运算。

按照这个规则,我们需要经过 35024 次计算,才能找到恰好前 4 位为 0 的哈希值:

"tutuxiao0" => 01f28c5df06ef0a575fd0e529be9a6f73b1290794762de014ec84182081e118e
"tutuxiao1" => a2567c06fdb5775cb1e3ce17b72754cf146fcc6da75c8f1d87d7ab6a1b8c4523
...
"tutuxiao35022" =>
8afc85049a9e92fe0b6c98b02b27c09fb869fbfe273d0ab84ad8c5ac17b8627e
"tutuxiao35023" =>
0000ec5927ba10ea45a6822dcc205050ae74ae1ad2d9d41e978e1ec9762dc404

通过上面这个示例可以看到,工作量证明就是通过执行哈希运算,经过一段时间的计算后,得到符合条件的哈希值。在实际场景中,我们可以根据场景特点,制定不同的规则,比如,你可以试试分别运行多少次,才能找到恰好前 3 位和前 5 位为 0 的哈希值。

二、区块链

区块链也是通过 SHA256 执行哈希运算,通过计算出符合指定条件的哈希值,来证明工作量的。因为在区块链中,PoW 算法是基于区块链中的区块信息来进行哈希运算的。

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



  • 区块头(Block Head):区块头主要由上一个区块的哈希值、区块体的哈希值、4 字节的随机数(nonce)等组成的,共80 字节固定长度;
  • 区块体(Block Body):区块包含的交易数据,其中的第一笔交易是 Coinbase 交易,这是一笔激励矿工的特殊交易。

在区块链中,给出的工作量要求是:对区块头执行 SHA256 哈希运算,得到的结果再执行一个哈希运算,计算出的哈希值,只有小于目标值(target),才是有效的

计算出符合条件的哈希值后,矿工就会把这个信息广播给集群中所有其他节点,其他节点验证通过后,会将这个区块加入到自己的区块链中,最终形成一串区块链,就像下图的样子:



从上面这种工作量证明要求可以看出,算力越强,系统大概率会越先计算出这个哈希值。这也就意味着, 攻击者能挖掘一条比原链更长的攻击链,并将攻击链向全网广播。而按照约定,节点将接受更长的链,也就是攻击链,丢弃原链。就像下图的样子:



这样的话,按照比特币的区块链约定——“最长链胜出,其它节点在这条链基础上扩展”,那么如果坏人们掌握了 51% 的算力,就通过优势算力实现对最长链的争夺,也就是发起 51% 攻击,实现双花(Double Spending)。

即使攻击者只有 30% 的算力,他也有可能连续计算出多个区块的哈希值,挖掘出更长的攻击链,发动攻击; 另外,即使攻击者拥有 51% 的算力,他也有可能半天无法计算出一个区块的哈希值,也就是攻击失败。也就是说,能否计算出符合条件的哈希值,有一定的概率性,但长久来看,攻击者攻击成功的概率等同于攻击者算力的权重。

三、总结

PoW算法,属于拜占庭容错算法中的一种,能容忍一定比例的作恶行为,所以它在相对开放的场景中应用广泛,比如公链、联盟链。而非拜占庭容错算法(比如 Raft)无法对作恶行为进行容错,主要用于封闭、绝对可信的场景中,比如私链、公司内网的 DevOps 环境。

正文到此结束
本文目录