改版中,提建议就可获得币视界股 
从零开始构建一个区块链(二): 工作量证明
作者:梁培利浏览数:17 

我们在上一篇中设计的区块链还很简单,并且很容易添加更长的区块链来覆盖最初合法的交易。要想维持整个系统的健康运转,需要在系统中设计一定的激励机制。在比特币体系中,我们知道有一个“挖矿”的概念的存在。就是平均每10分钟,比特币系统会奖励一定量的比特币(最初是50个,现在已经是12.5个了)。但是网络中有那么多比特币节点,这笔奖励该奖励给谁呢?这就是工作量证明(Proof-of-Work)算法要解决的问题。

本篇我们会阐述工作量证明算法的原理及其实现。

一、 Proof-of-Work

一个健康运行的区块链系统随时会产生交易,我们需要有服务器进行以下工作:定时把一个时间段(比特币是10分钟,Asch是10秒)的交易打包到一个区块,并且添加到现有的区块链中。但是一个区块链系统中可能有很多台服务器,究竟是以哪台服务器打包的区块为准呢?为了解决这个问题,比特币中采用了一种叫做工作量证明的算法来决定采用哪一台服务器打包的区块并且给予相应的奖励。

工作量证明的算法可以大概描述为:在一个时间段同时有多台服务器对这一段时间的交易进行打包,打包完成后连带区块Header信息一起经过SHA256算法进行运算。在区块头以及奖励交易coinbase里各有一个变量nonce,如果运算的结果不符合难度(稍后解释这个概念)要求,那么就调整nonce的值继续运算。如果有某台服务器率先计算出了符合难度值的区块,那么它可以广播这个区块。其他服务器验证没问题后就可以添加到现有区块链上,然后大家再一起竞争下一个区块。这个过程也称为挖矿。

工作量证明算法采用了SHA256,特点是难以运算但是容易验证。找到一个符合难度要求的区块需要耗费10分钟,但是验证它是否有效却是瞬间的事。在下面的代码实现里我们会看到这一点。

举一个简单的例子: 假设有一群人玩一个扔硬币游戏,每个人有十枚硬币,依次扔完十枚硬币,最后看十枚中的正面和反面的排序结果。由于是有顺序的,这里的结果有2^10种可能。现在有个规定,在一轮游戏中,谁先扔出了前4枚硬币都是正面的结果,谁就可以得到奖励。于是大家都开始扔十枚硬币并统计结果。前五枚都是正面的可能性有2^6种,因此一个人能获取该结果的期望尝试次数为2^4。 如果规定正面的个数越多,那么每个人的尝试次数就会越多,而这里的个数就是难度。如果玩游戏的人逐渐增多,那我们就可以要求前6个、前8个是正面,这样每轮游戏的时间依然差不多。这也是为什么比特币的算力大增,而依然能保持平均每10分钟产生一个区块的原因。


二、 实现方式

第一部分讲了工作量证明的算法,那如何把它添加到我们的区块链应用中呢?

任何一个数据经过SHA256运算后都会得到长度为256bit的二进制数值,我们可以通过调整最开始的部分连续的0的个数作为难度。比如我们要求最后的区块经过SHA256运算后第一个bit为0,那么平均每两次运算就会得到一个这样的结果。但是如果我们要求连续10个bit都是0,那就需要平均计算2^10次才能得到一次这样的结果了(怎么求出这里的平均计算次数?看看高中数学的概率和统计部分吧……)。通过调整连续0的个数来达成调整难度的目标。

另外关于哈希函数的特性,可以参考专栏的第一篇文章加密哈希函数及其应用

我们在区块的头信息中添加一个变量nonce。通过不停的调节nonce的值来重新计算整个区块的Hash值,直到满足难度要求。


三、代码实现

基于以上的概念,我们开始改造现在的区块链应用。首先在Block类添加一个nonce变量:

class Block {  constructor(index, timestamp) {    this.index = index;    this.timestamp = timestamp;    this.transactions = [];    this.previousHash = '';    this.hash = this.calculateHash();    this.nonce = 0;  }

然后在Block类中添加一个mineBlock方法

  mineBlock(difficulty) {    console.log(`Mining block ${this.index}`);    while (this.hash.substring(0, difficulty) !== Array(difficulty + 1).join("0")) {        this.nonce++;        this.hash = this.calculateHash();    }    console.log("BLOCK MINED: " + this.hash);  }

这里的difficulty指的是结果里从一开始连续为0的个数。如果不符合难度要求,那么nonce加1,然后重新计算区块的Hash值。

然后我们在Blockchain类里定义一个难度:

  constructor() {    this.chain = [this.createGenesisBlock()];    this.difficulty = 2;  }

把挖矿的过程应用到添加区块到区块链的过程中。

  addBlock(newBlock) {    newBlock.previousHash = this.getLatestBlock().hash;    newBlock.mineBlock(this.difficulty);    this.chain.push(newBlock);  }

到此为止,我们对应用的改造就完成了。简单吧?


下面对代码进行测试。

我们只添加一个区块:

const testCoin = new Blockchain();block1 = new Block('1', '02/10/2017');block1.addNewTransaction('Alice', 'Bob', 500);testCoin.addBlock(block1);console.log(block1)

在我电脑上运算的结果是:

Mining block 1BLOCK MINED: 005fed00324fcbe1f0ab1703afe94e45a99e197a7df142e669444687f9513e57Block {  index: '1',  timestamp: '02/10/2017',  transactions: [ { sender: 'Alice', recipient: 'Bob', amount: 500 } ],  previousHash: '31b15cc32d6772f237dcf298d5b7a2417f298f40ce6d8d5fbe07958141df7a4c',  hash: '005fed00324fcbe1f0ab1703afe94e45a99e197a7df142e669444687f9513e57',  nonce: 419 }

注意那个nonce值以及hash值。nonce值表明了计算次数,hash是最后得到的结果。这次我们设置的难度为2,期望计算次数是2^8次(hash里一个字符代表4个bit)。如果把难度改成3呢?运算结果为:

Mining block 1BLOCK MINED: 000b7f17beaf58bc8fea996a9fed11103ed27ad6d63818b87d89a440cd9757b5Block {  index: '1',  timestamp: '02/10/2017',  transactions: [ { sender: 'Alice', recipient: 'Bob', amount: 500 } ],  previousHash: '31b15cc32d6772f237dcf298d5b7a2417f298f40ce6d8d5fbe07958141df7a4c',  hash: '000b7f17beaf58bc8fea996a9fed11103ed27ad6d63818b87d89a440cd9757b5',  nonce: 4848 }

可以看到计算的次数增加了。而随着难度增大,CPU计算的次数也会指数级增加,相应耗费的时间也就越长。

完整代码见:github.com/liangpeili/t, 你也可以试试。


预告:下一篇我们会使用 Express 改造现在的区块链应用,使之成为可对外提供服务的API,敬请期待!


参考:

Implementing proof-of-work (Javascript blockchain, part 2)

hackernoon.com/learn-bl

Building Blockchain in Go. Part 2: Proof-of-Work