列旭松
來自：Linux內(nèi)核那些事（微信號：like_linux）
作者：列旭松，唯品會資深工程師，曾任職于YY語音，熟識PHP、C語言和Go語言。10年P(guān)HP開發(fā)經(jīng)驗，對PHP底層實現(xiàn)原理有較深理解。熱衷于開源事業(yè)，開源過多個PHP相關(guān)的擴展，流行的PHP源碼加密擴展（PHP-Beast）作者。另外，本人對分布式緩存系統(tǒng)（如Redis、Memcached）有較大的興趣，喜歡鉆研底層實現(xiàn)原理，《 PHP 核心技術(shù)與最佳實踐》一書的作者。
1、前言
上一篇文章我們介紹了區(qū)塊鏈的最基本數(shù)據(jù)結(jié)構(gòu)－區(qū)塊，而且還構(gòu)建了一個最原始的區(qū)塊鏈。但是現(xiàn)在我們很容易就可以向區(qū)塊鏈中添加區(qū)塊，這樣有可能導致大量的區(qū)塊在同時添加到區(qū)塊鏈中，從而導致廣播風暴。而且在分布式環(huán)境中，如果并發(fā)量太大會導致很多問題，例如拜占庭問題。
為了解決這個問題，比特幣使用了工作量證明機制。
2、工作量證明
由于現(xiàn)在添加一個區(qū)塊的成本很低，所以必須找到一個增加添加區(qū)塊成本的方法，而在比特幣中使用的是工作量證明，我們也效仿比特幣使用工作量證明。
工作量證明（POW，Proof-of-Work）是一個用于阻止拒絕服務攻擊和類似垃圾郵件等服務錯誤問題的協(xié)議，它在 1993 年被 Cynthia Dwork 和 Moni Naor 提出。
那么什么是工作量證明呢？其實很簡單，就是找到一個符合某一規(guī)定的Hash值。例如我們規(guī)定區(qū)塊的Hash值的前 20 個位必須為 0，要符合這樣的區(qū)塊才能添加到區(qū)塊鏈中，那么工作量證明就是要找到符合這樣規(guī)定的Hash值。
由于找到這樣的Hash值是非常困難的，所以會給予找到合適Hash值的人相應獎勵（比特幣），找到符合規(guī)定Hash值的過程被稱為“挖礦”，而挖礦的機器被稱為“礦工”。
3、Hash值計算
如前面所說，我們需要找到一個符合規(guī)定的Hash值才能將區(qū)塊添加到區(qū)塊鏈中，而在我們的前一篇文章中計算區(qū)塊Hash值的方法是直接序列化區(qū)塊，然后使用SHA-256來計算其Hash值。那么有個問題是，區(qū)塊的內(nèi)容是不變的，所以計算出來的Hash值也是固定的，那么有什么辦法來改變區(qū)塊的Hash值呢？這里我們使用Hashcash?算法，步驟如下：
1. 取一些公開的數(shù)據(jù)（比如區(qū)塊頭）。
2. 給這個公開數(shù)據(jù)添加一個計數(shù)器。計數(shù)器默認從 0 開始。
3. 將數(shù)據(jù)和計數(shù)器組合到一起，獲得一個Hash值。
4. 檢查Hash值是否符合規(guī)定的條件：
? ?1) 如果符合條件，結(jié)束
? ?2) 如果不符合，增加計數(shù)器，重復步驟 3-4
可以看出這個是一個暴力計算的過程：改變計數(shù)器，計算新的Hash值，檢查是否符合條件，直到找到符合條件的Hash值。
在 Hashcash 算法中，它的要求是“一個Hash值的前 20 位必須是 0”。條件越苛刻，找到符合條件的Hash值就越難。下圖詳細說明了這個過程：
在上圖中，129022是計數(shù)器的值，而符合條件的Hash值是前 16 個位為 0 （上圖中表現(xiàn)為Hash值的前4個字符為0）。
4、實現(xiàn)
在上一篇文章中的Block對象的實現(xiàn)中，添加一個findBlockHash()的方法用于找到符合條件的Hash值：
class?Block
{
????...
????public?$nonce;
????private?function?prepareData($nonce)
????{
????????return?json_encode([
????????????$this->prevHash,
????????????$this->timeStamp,
????????????$this->data,
????????????$nonce,
????????]);
????}
????public?function?findBlockHash()
????{
????????$found?=?false;
????????$condition?=?'0000';?//?Hash值前N個字符必須等于$condition
????????$condlength?=?strlen($condition);
????????printf("Mining?the?block?containing?"%s" ",?$this->data);
????????for?($nonce?=?0;?$nonce?<?PHP_INT_MAX;?$nonce++)?{
????????????$data?=?$this->prepareData($nonce);
????????????$hash?=?hash('sha256',?$data);
????????????printf(" %d:?%s",?$nonce,?$hash);
????????????if?(substr($hash,?0,?$condlength)?===?$condition)?{
????????????????$found?=?true;
????????????????break;
????????????}
????????}
????????print(" ");
????????if?($found)?{
????????????$this->nonce?=?$nonce;
????????????$this->hash?=?$hash;
????????}
????????return?$found;
????}
}
在上面的代碼中，我們?yōu)锽lock類添加了一個nonce的成員變量，用于記錄計數(shù)器。而在findBlockHash()函數(shù)中，我們不斷增加計數(shù)器的值，計算出Hash值，然后比較Hash值是否符合條件（前N個字符是否等于變量$condition）。如果找到合適的Hash值就退出循環(huán)，否則增加計數(shù)器的值計算下一個Hash值。而prepareData()方法用于序列化要計算Hash值的數(shù)據(jù)。
最后，我們在Block類的構(gòu)造函數(shù)中調(diào)用findBlockHash()方法：
class?Block
{
????...
????public?function?__construct($prevHash,?$data)
????{
????????$this->prevHash?=?$prevHash;
????????$this->timeStamp?=?time();
????????$this->data?=?$data;
????????$this->findBlockHash();
????}
????...
}
現(xiàn)在我們來運行一下代碼看看效果：
從運行結(jié)果可以看到，算出來的Hash值都符合我們規(guī)定的條件。當然，你可以修改更苛刻的條件來增加挖礦的難度。
最后還有一件事需要做，就是驗證區(qū)塊是否合法：
class?Block
{
????...
????public?function?validate()
????{
????????$condition?=?'0000';
????????$condlength?=?strlen($condition);
????????$data?=?$this->prepareData($this->nonce);
????????return?substr(hash('sha256',?$data),?0,?$condlength)?===?$condition;?
????}
}
驗證的方法很簡單，就是計算出區(qū)塊的Hash值，然后比較Hash值是否符合條件。然后我們在打印區(qū)塊鏈的時候驗證區(qū)塊是否合法：
include('blockchain.php');
$bc?=?new?Blockchain();
$bc->addBlock('This?is?block1');
$bc->addBlock('This?is?block2');
foreach?($bc->blocks?as?$block)?{
????...
????printf("PoW:?%s ",?$block->validate()???'true'?:?'false');
????...
}
運行代碼查看結(jié)果：
結(jié)果符合我們的預期，代碼在：https://github.com/liexusong/blockchain-php/tree/v2.0
