PoW挖礦演算法原理及其在比特幣、以太坊中的實現
PoW，全稱Proof of Work，即工作量證明，又稱挖礦。大部分公有鏈或虛擬貨幣，如比特幣、以太坊，均基於PoW演算法，來實現其共識機制。即根據挖礦貢獻的有效工作，來決定貨幣的分配。
比特幣區塊
比特幣區塊由區塊頭和該區塊所包含的交易列表組成。
區塊頭大小為80位元組，其構成包括：
4位元組：版本號
32位元組：上一個區塊的哈希值
32位元組：交易列表的Merkle根哈希值
4位元組：當前時間戳
4位元組：當前難度值
4位元組：隨機數Nonce值
此80位元組長度的區塊頭，即為比特幣Pow演算法的輸入字元串。
交易列表附加在區塊頭之後，其中第一筆交易為礦工獲得獎勵和手續費的特殊交易。
bitcoin-0.15.1源碼中區塊頭和區塊定義：
比特幣Pow演算法原理
Pow的過程，即為不斷調整Nonce值，對區塊頭做雙重SHA256哈希運算，使得結果滿足給定數量前導0的哈希值的過程。
其中前導0的個數，取決於挖礦難度，前導0的個數越多，挖礦難度越大。
具體如下：
1、生成鑄幣交易，並與其它所有準備打包進區塊的交易組成交易列表，生成Merkle根哈希值。
2、將Merkle根哈希值，與區塊頭其它欄位組成區塊頭，80位元組長度的區塊頭作為Pow演算法的輸入。
3、不斷變更區塊頭中的隨機數Nonce，對變更後的區塊頭做雙重SHA256哈希運算，與當前難度的目標值做比對，如果小於目標難度，即Pow完成。
Pow完成的區塊向全網廣播，其他節點將驗證其是否符合規則，如果驗證有效，其他節點將接收此區塊，並附加在已有區塊鏈之後。
之後將進入下一輪挖礦。
bitcoin-0.15.1源碼中Pow演算法實現：
另附bitcoin-0.15.1源碼中生成鑄幣交易和創建新塊：
比特幣挖礦難度計算
每創建2016個塊後將計算新的難度，此後的2016個塊使用新的難度。計算步驟如下：
1、找到前2016個塊的第一個塊，計算生成這2016個塊花費的時間。即最後一個塊的時間與第一個塊的時間差。時間差不小於3.5天，不大於56天。
2、計算前2016個塊的難度總和，即單個塊的難度*總時間。
3、計算新的難度，即2016個塊的難度總和/14天的秒數，得到每秒的難度值。
4、要求新的難度，難度不低於參數定義的最小難度。
bitcoin-0.15.1源碼中計算挖礦難度代碼如下：
以太坊區塊
以太坊區塊由Header和Body兩部分組成。
其中Header部分成員如下：
ParentHash，父區塊哈希
UncleHash，叔區塊哈希，具體為Body中Uncles數組的RLP哈希值。RLP哈希，即某類型對象RLP編碼後做SHA3哈希運算。
Coinbase，礦工地址。
Root，StateDB中state Trie根節點RLP哈希值。
TxHash，Block中tx Trie根節點RLP哈希值。
ReceiptHash，Block中Receipt Trie根節點的RLP哈希值。
Difficulty，區塊難度，即當前挖礦難度。
Number，區塊序號，即父區塊Number+1。
GasLimit，區塊內所有Gas消耗的理論上限，創建時指定，由父區塊GasUsed和GasLimit計算得出。
GasUsed，區塊內所有Transaction執行時消耗的Gas總和。
Time，當前時間戳。
Nonce，隨機數Nonce值。
有關叔區塊：
叔區塊，即孤立的塊。以太坊成塊速度較快，導致產生孤塊。
以太坊會給發現孤塊的礦工以回報，激勵礦工在新塊中引用孤塊，引用孤塊使主鏈更重。在以太坊中，主鏈是指最重的鏈。
有關state Trie、tx Trie和Receipt Trie：
state Trie，所有賬戶對象可以逐個插入一個Merkle-PatricaTrie(MPT)結構中，形成state Trie。
tx Trie：Block中Transactions中所有tx對象，逐個插入MPT結構中，形成tx Trie。
Receipt Trie：Block中所有Transaction執行後生成Receipt數組，所有Receipt逐個插入MPT結構中，形成Receipt Trie。
Body成員如下：
Transactions，交易列表。
Uncles，引用的叔區塊列表。
go-ethereum-1.7.3源碼中區塊頭和區塊定義：
以太坊Pow演算法原理
以太坊Pow演算法可以表示為如下公式：
RAND(h, n)
其中RAND()表示一個概念函數，代表一系列的複雜運算。
其中h和n為輸入，即區塊Header的哈希、以及Header中的Nonce。
M表示一個極大的數，此處使用2^256-1。
d，為區塊難度，即Header中的Difficulty。
因此在h和n確定的情況下，d越大，挖礦難度越大，即為Difficulty本義。
即不斷變更Nonce，使RAND(h, n)滿足RAND(h, n)
go-ethereum-1.7.3源碼中Pow演算法實現：
以太坊挖礦難度計算
以太坊每次挖礦均需計算當前區塊難度。
按版本不同有三種計算難度的規則，分別為：calcDifficultyByzantium（Byzantium版）、calcDifficultyHomestead（Homestead版）、calcDifficultyFrontier（Frontier版）。此處以calcDifficultyHomestead為例。
計算難度時輸入有：
parent_timestamp：父區塊時間戳
parent_diff：父區塊難度
block_timestamp：當前區塊時間戳
block_number：當前區塊的序號
當前區塊難度計算公式，即：
block_diff = parent_diff
+ (parent_diff / 2048 * max(1 - (block_timestamp - parent_timestamp) // 10, -99)
+ 2^((block_number // 100000) - 2)
其中//為整數除法運算符，a//b，即先計算a/b，然後取不大於a/b的最大整數。
調整難度的目的，即為使挖礦時間保持在10-19s期間內，如果低於10s增大挖礦難度，如果大於19s將減小難度。另外，計算出的當前區塊難度不應低於以太坊創世區塊難度，即131072。
go-ethereum-1.7.3源碼中計算挖礦難度代碼如下：
後記
Pow演算法概念簡單，即工作端提交難以計算但易於驗證的計算結果，其他節點通過驗證這個結果來確信工作端完成了相當的工作量。
但其缺陷也很明顯：1、隨著節點將CPU挖礦升級為GPU、甚至礦機挖礦，節點數和算力已漸漸失衡；2、比特幣等網路每秒需完成數百萬億次哈希計算，資源大量浪費。
為此，業內提出了Pow的替代者如PoS權益證明演算法，即要求用戶擁有一定數量的貨幣，才有權參與確定下一個合法區塊。另外，相對擁有51%算力，購買超過半數以上的貨幣難度更大，也使得惡意攻擊更加困難。
TAG:全球大搜羅 |