©2016-2024 Matools All rights reserved,
粤ICP备17059708号
前面的两篇文章学习了非拜占庭模型的经典共识算法paxos和拜占庭模型的经典共识算法PBFT，本文学习另外两种基于概率的共识算法：工作量证明算法PoW和权益证明算法PoS。其中PoW也是比特币区块链所采用的共识算法。
1 PoW算法
1.1 PoW历史
工作量证明源于经济学，是一个经济学的概念，是指为了达成某种目标而设定一个度量的方法。可以和平时工作中的绩效考核做类比：为了考核达到5星，你必须要完成leader指派给你的KPI，这些KPI就是工作量证明，完成它可能需要加班加点干很久，但是考评的时候leader验证起来却很容易。
1993年，Cynthia Dwork和Moni Naor在学术论文中首次提出工作量证明的的概念。
1997年，Adam Back在学术论文Hashcash <http://www.hashcash.org/papers/hashcash.pdf>
中提出了Hahscash的概念，用于抵抗Dos攻击和垃圾邮件网关的滥用。Hahscash和比特币区块链的PoW如出一辙，在比特币之前，Hashcash的最常见应用场景就是反垃圾邮件。
1999年，Markus Jakobsson和Ari Juels发表的论文中首次提出了Proof of Work这个名词。
PoW需要两个角色：工作者和验证者，并且具备以下特点：
(1) 工作只能由验证者发布；
(2) 工作者必须要完成一定量的工作，具体的工作量有验证者给出；
(3) 工作者没有办法快速完成工作，要完成工作必须消耗一定代价，但是验证者验证起来很容易；
1.2 Hashcash
Hashcash是Adam Back与1997年发明的一种抵抗邮件服务DoS攻击的算法。理解了Hashcash，就能够轻而易举的理解比特币中的PoW。
Hashcash是基于SHA1散列算法，它抵抗垃圾邮件的原理如下：
假设S给R发送邮件，要想发送成功，则：
(1) S的邮件头中需要带一个称之为hashcash stamp的戳记；
(2) 对hashcash stamp进行SHA1后的值必须满足接收方R设定的条件：生成的hash值的前20位必须为0；
(3) hashcash stamp可能由多个域组成，比如生成邮件的时间，收件人地址等不变量，还包含可变量counter；
(4) 由于Hash的特点，导致发送方S没有办法快速找到满足条件的hashcash stamp，只能通过不断递增counter的值来穷举；
(5) 发送方S通过暴力破解的方式计算出满足接收方条件的值，这个过程发送方消耗了一定量的CPU。而验证方只需要对收到的hashcash
stamp进行SHA1，检查结果是否满足；
由于发送方计算满足邮件接收方条件的值需要消耗一定时间，对于垃圾邮件系统来说，这样的成本基本上是不可接受的，从而有效避免了垃圾邮件。
1.3 PoW如何解决分布式系统的共识问题
可以把比特币区块链看成一个分布式的账本，然后定义几个名词：
(1) 分布式账本：比特币区块链是一个分布式账本，这个账本人人可以随时查阅，但是由谁来记账需要通过共识算法来决定；
(2) 记账：将区块写入区块链；
(3) 记账者：就是平常所说的矿工，比特币系统中的每个矿工节点都是潜在的记账者；
(4) 选举：就是大家所熟知的挖矿，用某种算法从一批候选矿工（记账者）中选出一个来记账（写入账本）；
记账者中大部分都是正常的，但是也有少数不怀好意的记账者，因此系统需要通过共识算法选出一个正常的记账者来记账，这其实就是一个拜占庭将军问题：在可能存在恶意节点时，如何保证账本的正确性。
既然是拜占庭问题，那么像PBFT，PoW等算法都可以解决，比特币使用PoW，其达成共识的过程如下：
(1) 系统指定一个目标hash值，各个矿工节点竞争，构造出候选区块，并不断计算区块头hash，直到得到满足条件的hash为止；
(2) 与hashcash一样，矿工节点除了暴力破解，没有快速找到答案的办法；
(3) 率先计算出解的矿工节点将区块广播给全网，其他节点验证区块（工作量是否满足，交易是否合法），没有问题就将区块加入到区块链中；
(4) 计算出解的矿工得到一笔奖励费；
很明显，这是一个凭算力取胜的游戏，简单分析一下：
假设系统有4个矿工节点A，B，C，D，则：
(1) 如果4个矿工节点的算力都相同，其中存在一个恶意节点，那么最终能正确写入账本的概率是3/4，而被恶意矿工写入的概率是1/4；
(2) 假如B是恶意节点，他买了一台奇快的专用矿机，使得他的算力大增，达到了全部矿工节点算力的51%，那么系统基本上就被这个恶意矿工控制；
因此，系统最坏的情况下能容忍的问题节点的数量是：占据整个系统51%算力的问题节点的数量，当然要掌控这么高的算力还是很困难的。
关于具体的源码，后续会单独用一篇文章来分析比特币挖矿的过程，本文先理解PoW算法就好。
2 PoS算法
2.1 PoS的提出
PoW算法存在两个问题：
(1) 太浪费资源，因为需要巨量的计算，会浪费资源（电力）；
(2) 存在51%攻击问题：一旦能掌握系统51%的算力基本上就能控制整个系统。
(3) 系统的吞吐量降低，比如比特币，平均每10分钟才产生一个区块；
为了克服PoW算法的问题，2012年Sunny King提出了PoS权益证明算法，并发布了点点币（PPCoin），点点币中采用了PoS作为共识算法。
PoS与PoW原理上很相似，都是一种基于概率的解决共识问题的算法。只不过PoW是拼算力，算力越强的抢到记账权的概率越大，而PoS则是拼财力，谁的财力越高，抢到记账权的概率就越大。
2.2 PoS算法的原理
PoS一个重要的概念是币龄，币龄 = 持有的币数 * 持有币的天数，例如钱包里有90个点点币，都持有了10天，则币龄=900；
与PoW一样，为了抢到将区块写入区块链的权利，节点同样要进行hash计算，只不过最终的解和币龄有关，计算公式：
proofHash < coinAge * target；
coinAge是币龄，target是一个目标值，用于调整难度。coinAge * target的值越大，难度就越小，抢到区块的概率就越高。
假如你的钱包里是0个币，那么你的币龄就是0, 计算一个小于0的hash值的概率基本上也0，因此基本上抢不到区块；
PoS可以解决PoW的问题：
(1) 首先，不需要PoW那么大的算力，可以减少资源浪费；
(2) 不容易遭受51%攻击，相比起掌握系统一半以上的算力，拥有整个系统51%的财力会更加困难。
但是PoS也存在明显的缺陷：
(1)
容易被垄断：因为持币越多，持有的越久，币龄就越高，越容易挖到区块并得到激励，持币少的人基本上没有机会，这样整个系统的安全性实际上会被持币数量较大的一部分人（大股东们）掌握；而比特币则不存在这个问题，因为理论上任何人都可以购买矿机获得提高自己的算力（甚至可以联合起来），提升自己挖矿成功的概率；
(2)
很难应对分叉的情况：当出现分叉时，PoS可以在两条链上同时挖矿并获得收益。而PoW则不存在这个问题，因为当出现分叉以后，PoW总是选择工作量大的链做为主链。
2.3 DPoS算法
PoS算法中记账权很容易被持币较多的人垄断，从而容易趋于中心化（永远是持币多的那些人获得写入区块并获得奖励），于是又有了DPoS（委托权益证明）算法。与PoS算法相比，DPoS中多了受托人的概念。DPoS算法是在2014年由Bitshares的首席开发者Dan
Larimer提出，此人现为EOS的CTO。DPoS算法的原理如下：
(1) 区块由受托人产生并写入区块链；
(2) 受托人由持币人选举产生；
(3) 根据受托人所得的票数排名，选取排名最靠前的若干（一般为101位）作为记账节点，来生成区块并写入区块链；
(4) 被选中的受托人会隔一定的周期进行一次调整；
相比于PoS，DPoS机制更加安全和去中心化：
首先，为了利益最大化，股东会选择将票投给那些信誉好，可靠性高的节点；
其次，受托人每隔一定的周期就会重新投票进行调整，更加民主和公平。这就好比公司选举领导层干部，为了公司利益最大化，股东一般会选择能力强的人进入管理层。而一旦管理层出了问题领导，股东可以把他撸下去，重新投票选择更胜任的人。
3 总结
本文介绍了PoW、PoS两类基于概率的共识算法，任何一个区块链都必须要解决区块何时产生，由谁将区块写入区块链的问题，PoW和PoS解决的思路总结起来就是：
(1) PoW：比拼算力，算力越强越容易拿到写区块链的权利；
(2) PoS：比拼财力，占的股份越大（币龄越高），越容易拿到记账权；
(3) DPoS：引入了受托人，由投票选举出的若干信誉度更高的受托人记账，受托人每隔一定周期调整，更加安全和去中心化。
这些算法在许多的区块链中被广泛使用，这些算法是区块链安全的基石，学习中需要结合项目源码加以理解，弄清楚区块链到底在共识什么，为什么需要共识，共识算法是如何解决这些问题的。
热门工具 换一换