第二章 PoW 工作量證明算法 · 區塊鏈共識算法

PoW，全稱Proof of Work，即工作量證明，又稱挖礦。大部分公有鏈或虛擬貨幣，如比特幣、以太坊，均基于PoW算法，來實現其共識機制。即根據挖礦貢獻的有效工作，來決定貨幣的分配。 ### **比特幣區塊** 比特幣區塊由區塊頭和該區塊所包含的交易列表組成。區塊頭大小為80字節，其構成包括： * 4字節：版本號 * 32字節：上一個區塊的哈希值 * 32字節：交易列表的Merkle根哈希值 * 4字節：當前時間戳 * 4字節：當前難度值 * 4字節：隨機數Nonce值此80字節長度的區塊頭，即為比特幣Pow算法的輸入字符串。交易列表附加在區塊頭之后，其中第一筆交易為礦工獲得獎勵和手續費的特殊交易。 bitcoin-0.15.1源碼中區塊頭和區塊定義： ```c++ class CBlockHeader { public: //版本號 int32_t nVersion; //上一個區塊的哈希值 uint256 hashPrevBlock; //交易列表的Merkle根哈希值 uint256 hashMerkleRoot; //當前時間戳 uint32_t nTime; //當前挖礦難度，nBits越小難度越大 uint32_t nBits; //隨機數Nonce值 uint32_t nNonce; //其它代碼略 }; class CBlock : public CBlockHeader { public: //交易列表 std::vector<CTransactionRef> vtx; //其它代碼略 }; //代碼位置src/primitives/block.h ``` ### **比特幣Pow算法原理** Pow的過程，即為不斷調整Nonce值，對區塊頭做雙重SHA256哈希運算，使得結果滿足給定數量前導0的哈希值的過程。其中前導0的個數，取決于挖礦難度，前導0的個數越多，挖礦難度越大。具體如下： * 1、生成鑄幣交易，并與其它所有準備打包進區塊的交易組成交易列表，生成Merkle根哈希值。 * 2、將Merkle根哈希值，與區塊頭其它字段組成區塊頭，80字節長度的區塊頭作為Pow算法的輸入。 * 3、不斷變更區塊頭中的隨機數Nonce，對變更后的區塊頭做雙重SHA256哈希運算，與當前難度的目標值做比對，如果小于目標難度，即Pow完成。 Pow完成的區塊向全網廣播，其他節點將驗證其是否符合規則，如果驗證有效，其他節點將接收此區塊，并附加在已有區塊鏈之后。之后將進入下一輪挖礦。 bitcoin-0.15.1源碼中Pow算法實現： ```c++ UniValue generateBlocks(std::shared_ptr<CReserveScript> coinbaseScript, int nGenerate, uint64_t nMaxTries, bool keepScript) { static const int nInnerLoopCount = 0x10000; int nHeightEnd = 0; int nHeight = 0; { // Don't keep cs_main locked LOCK(cs_main); nHeight = chainActive.Height(); nHeightEnd = nHeight+nGenerate; } unsigned int nExtraNonce = 0; UniValue blockHashes(UniValue::VARR); while (nHeight < nHeightEnd) { std::unique_ptr<CBlockTemplate> pblocktemplate(BlockAssembler(Params()).CreateNewBlock(coinbaseScript->reserveScript)); if (!pblocktemplate.get()) throw JSONRPCError(RPC_INTERNAL_ERROR, "Couldn't create new block"); CBlock *pblock = &pblocktemplate->block; { LOCK(cs_main); IncrementExtraNonce(pblock, chainActive.Tip(), nExtraNonce); } //不斷變更區塊頭中的隨機數Nonce //對變更后的區塊頭做雙重SHA256哈希運算 //與當前難度的目標值做比對，如果小于目標難度，即Pow完成 //uint64_t nMaxTries = 1000000;即重試100萬次 while (nMaxTries > 0 && pblock->nNonce < nInnerLoopCount && !CheckProofOfWork(pblock->GetHash(), pblock->nBits, Params().GetConsensus())) { ++pblock->nNonce; --nMaxTries; } if (nMaxTries == 0) { break; } if (pblock->nNonce == nInnerLoopCount) { continue; } std::shared_ptr<const CBlock> shared_pblock = std::make_shared<const CBlock>(*pblock); if (!ProcessNewBlock(Params(), shared_pblock, true, nullptr)) throw JSONRPCError(RPC_INTERNAL_ERROR, "ProcessNewBlock, block not accepted"); ++nHeight; blockHashes.push_back(pblock->GetHash().GetHex()); //mark script as important because it was used at least for one coinbase output if the script came from the wallet if (keepScript) { coinbaseScript->KeepScript(); } } return blockHashes; } //代碼位置src/rpc/mining.cpp ``` 另附bitcoin-0.15.1源碼中生成鑄幣交易和創建新塊： ```c++ std::unique_ptr<CBlockTemplate> BlockAssembler::CreateNewBlock(const CScript& scriptPubKeyIn, bool fMineWitnessTx) { int64_t nTimeStart = GetTimeMicros(); resetBlock(); pblocktemplate.reset(new CBlockTemplate()); if(!pblocktemplate.get()) return nullptr; pblock = &pblocktemplate->block; // pointer for convenience pblock->vtx.emplace_back(); pblocktemplate->vTxFees.push_back(-1); // updated at end pblocktemplate->vTxSigOpsCost.push_back(-1); // updated at end LOCK2(cs_main, mempool.cs); CBlockIndex* pindexPrev = chainActive.Tip(); nHeight = pindexPrev->nHeight + 1; //版本號 pblock->nVersion = ComputeBlockVersion(pindexPrev, chainparams.GetConsensus()); if (chainparams.MineBlocksOnDemand()) pblock->nVersion = gArgs.GetArg("-blockversion", pblock->nVersion); //當前時間戳 pblock->nTime = GetAdjustedTime(); const int64_t nMedianTimePast = pindexPrev->GetMedianTimePast(); nLockTimeCutoff = (STANDARD_LOCKTIME_VERIFY_FLAGS & LOCKTIME_MEDIAN_TIME_PAST) ? nMedianTimePast : pblock->GetBlockTime(); fIncludeWitness = IsWitnessEnabled(pindexPrev, chainparams.GetConsensus()) && fMineWitnessTx; int nPackagesSelected = 0; int nDescendantsUpdated = 0; addPackageTxs(nPackagesSelected, nDescendantsUpdated); int64_t nTime1 = GetTimeMicros(); nLastBlockTx = nBlockTx; nLastBlockWeight = nBlockWeight; //創建鑄幣交易 CMutableTransaction coinbaseTx; coinbaseTx.vin.resize(1); coinbaseTx.vin[0].prevout.SetNull(); coinbaseTx.vout.resize(1); //挖礦獎勵和手續費 coinbaseTx.vout[0].scriptPubKey = scriptPubKeyIn; coinbaseTx.vout[0].nValue = nFees + GetBlockSubsidy(nHeight, chainparams.GetConsensus()); coinbaseTx.vin[0].scriptSig = CScript() << nHeight << OP_0; //第一筆交易即為礦工獲得獎勵和手續費的特殊交易 pblock->vtx[0] = MakeTransactionRef(std::move(coinbaseTx)); pblocktemplate->vchCoinbaseCommitment = GenerateCoinbaseCommitment(*pblock, pindexPrev, chainparams.GetConsensus()); pblocktemplate->vTxFees[0] = -nFees; LogPrintf("CreateNewBlock(): block weight: %u txs: %u fees: %ld sigops %d\n", GetBlockWeight(*pblock), nBlockTx, nFees, nBlockSigOpsCost); //上一個區塊的哈希值 pblock->hashPrevBlock = pindexPrev->GetBlockHash(); UpdateTime(pblock, chainparams.GetConsensus(), pindexPrev); //當前挖礦難度 pblock->nBits = GetNextWorkRequired(pindexPrev, pblock, chainparams.GetConsensus()); //隨機數Nonce值 pblock->nNonce = 0; pblocktemplate->vTxSigOpsCost[0] = WITNESS_SCALE_FACTOR * GetLegacySigOpCount(*pblock->vtx[0]); CValidationState state; if (!TestBlockValidity(state, chainparams, *pblock, pindexPrev, false, false)) { throw std::runtime_error(strprintf("%s: TestBlockValidity failed: %s", __func__, FormatStateMessage(state))); } int64_t nTime2 = GetTimeMicros(); LogPrint(BCLog::BENCH, "CreateNewBlock() packages: %.2fms (%d packages, %d updated descendants), validity: %.2fms (total %.2fms)\n", 0.001 * (nTime1 - nTimeStart), nPackagesSelected, nDescendantsUpdated, 0.001 * (nTime2 - nTime1), 0.001 * (nTime2 - nTimeStart)); return std::move(pblocktemplate); } //代碼位置src/miner.cpp ``` ###** 比特幣挖礦難度計算** 每創建2016個塊后將計算新的難度，此后的2016個塊使用新的難度。計算步驟如下： * 1、找到前2016個塊的第一個塊，計算生成這2016個塊花費的時間。即最后一個塊的時間與第一個塊的時間差。時間差不小于3.5天，不大于56天。 * 2、計算前2016個塊的難度總和，即單個塊的難度*總時間。 * 3、計算新的難度，即2016個塊的難度總和/14天的秒數，得到每秒的難度值。 * 4、要求新的難度，難度不低于參數定義的最小難度。 bitcoin-0.15.1源碼中計算挖礦難度代碼如下： ```c++ //nFirstBlockTime即前2016個塊的第一個塊的時間戳 unsigned int CalculateNextWorkRequired(const CBlockIndex* pindexLast, int64_t nFirstBlockTime, const Consensus::Params& params) { if (params.fPowNoRetargeting) return pindexLast->nBits; //計算生成這2016個塊花費的時間 int64_t nActualTimespan = pindexLast->GetBlockTime() - nFirstBlockTime; //不小于3.5天 if (nActualTimespan < params.nPowTargetTimespan/4) nActualTimespan = params.nPowTargetTimespan/4; //不大于56天 if (nActualTimespan > params.nPowTargetTimespan*4) nActualTimespan = params.nPowTargetTimespan*4; // Retarget const arith_uint256 bnPowLimit = UintToArith256(params.powLimit); arith_uint256 bnNew; bnNew.SetCompact(pindexLast->nBits); //計算前2016個塊的難度總和 //即單個塊的難度*總時間 bnNew *= nActualTimespan; //計算新的難度 //即2016個塊的難度總和/14天的秒數 bnNew /= params.nPowTargetTimespan; //bnNew越小，難度越大 //bnNew越大，難度越小 //要求新的難度，難度不低于參數定義的最小難度 if (bnNew > bnPowLimit) bnNew = bnPowLimit; return bnNew.GetCompact(); } //代碼位置src/pow.cpp ``` ### **以太坊區塊** 以太坊區塊由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源碼中區塊頭和區塊定義： ```go type Header struct { //父區塊哈希 ParentHash common.Hash //叔區塊哈希 UncleHash common.Hash //礦工地址 Coinbase common.Address //StateDB中state Trie根節點RLP哈希值 Root common.Hash //Block中tx Trie根節點RLP哈希值 TxHash common.Hash //Block中Receipt Trie根節點的RLP哈希值 ReceiptHash common.Hash Bloom Bloom //區塊難度 Difficulty *big.Int //區塊序號 Number *big.Int //區塊內所有Gas消耗的理論上限 GasLimit *big.Int //區塊內所有Transaction執行時消耗的Gas總和 GasUsed *big.Int //當前時間戳 Time *big.Int Extra []byte MixDigest common.Hash //隨機數Nonce值 Nonce BlockNonce } type Body struct { //交易列表 Transactions []*Transaction //引用的叔區塊列表 Uncles []*Header } //代碼位置core/types/block.go ``` ###** 以太坊Pow算法原理** 以太坊Pow算法可以表示為如下公式： RAND(h, n) <= M / d 其中RAND()表示一個概念函數，代表一系列的復雜運算。其中h和n為輸入，即區塊Header的哈希、以及Header中的Nonce。 M表示一個極大的數，此處使用2^256-1。 d，為區塊難度，即Header中的Difficulty。因此在h和n確定的情況下，d越大，挖礦難度越大，即為Difficulty本義。即不斷變更Nonce，使RAND(h, n)滿足RAND(h, n) <= M / d，即完成Pow。 go-ethereum-1.7.3源碼中Pow算法實現： ```go func (ethash *Ethash) mine(block *types.Block, id int, seed uint64, abort chan struct{}, found chan *types.Block) { // Extract some data from the header var ( header = block.Header() hash = header.HashNoNonce().Bytes() //target，即M / d，即(2^256-1)/Difficulty target = new(big.Int).Div(maxUint256, header.Difficulty) number = header.Number.Uint64() dataset = ethash.dataset(number) ) // Start generating random nonces until we abort or find a good one var ( attempts = int64(0) nonce = seed ) logger := log.New("miner", id) logger.Trace("Started ethash search for new nonces", "seed", seed) for { select { case <-abort: // Mining terminated, update stats and abort logger.Trace("Ethash nonce search aborted", "attempts", nonce-seed) ethash.hashrate.Mark(attempts) return default: // We don't have to update hash rate on every nonce, so update after after 2^X nonces attempts++ if (attempts % (1 << 15)) == 0 { ethash.hashrate.Mark(attempts) attempts = 0 } //hashimotoFull即RAND(h, n)所代表的一系列的復雜運算 digest, result := hashimotoFull(dataset, hash, nonce) //result滿足RAND(h, n) <= M / d if new(big.Int).SetBytes(result).Cmp(target) <= 0 { // Correct nonce found, create a new header with it header = types.CopyHeader(header) header.Nonce = types.EncodeNonce(nonce) header.MixDigest = common.BytesToHash(digest) // Seal and return a block (if still needed) select { case found <- block.WithSeal(header): logger.Trace("Ethash nonce found and reported", "attempts", nonce-seed, "nonce", nonce) case <-abort: logger.Trace("Ethash nonce found but discarded", "attempts", nonce-seed, "nonce", nonce) } return } //不斷變更Nonce nonce++ } } } //代碼位置consensus/ethash/sealer.go ``` ### ** 以太坊挖礦難度計算** 以太坊每次挖礦均需計算當前區塊難度。按版本不同有三種計算難度的規則，分別為：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源碼中計算挖礦難度代碼如下： ```go func calcDifficultyHomestead(time uint64, parent *types.Header) *big.Int { // https://github.com/ethereum/EIPs/blob/master/EIPS/eip-2.mediawiki // algorithm: // diff = (parent_diff + // (parent_diff / 2048 * max(1 - (block_timestamp - parent_timestamp) // 10, -99)) // ) + 2^(periodCount - 2) bigTime := new(big.Int).SetUint64(time) bigParentTime := new(big.Int).Set(parent.Time) // holds intermediate values to make the algo easier to read & audit x := new(big.Int) y := new(big.Int) // 1 - (block_timestamp - parent_timestamp) // 10 x.Sub(bigTime, bigParentTime) x.Div(x, big10) x.Sub(big1, x) // max(1 - (block_timestamp - parent_timestamp) // 10, -99) if x.Cmp(bigMinus99) < 0 { x.Set(bigMinus99) } // (parent_diff + parent_diff // 2048 * max(1 - (block_timestamp - parent_timestamp) // 10, -99)) y.Div(parent.Difficulty, params.DifficultyBoundDivisor) x.Mul(y, x) x.Add(parent.Difficulty, x) // minimum difficulty can ever be (before exponential factor) if x.Cmp(params.MinimumDifficulty) < 0 { x.Set(params.MinimumDifficulty) } // for the exponential factor periodCount := new(big.Int).Add(parent.Number, big1) periodCount.Div(periodCount, expDiffPeriod) // the exponential factor, commonly referred to as "the bomb" // diff = diff + 2^(periodCount - 2) if periodCount.Cmp(big1) > 0 { y.Sub(periodCount, big2) y.Exp(big2, y, nil) x.Add(x, y) } return x } //代碼位置consensus/ethash/consensus.go ``` ### **后記** Pow算法概念簡單，即工作端提交難以計算但易于驗證的計算結果，其他節點通過驗證這個結果來確信工作端完成了相當的工作量。但其缺陷也很明顯：1、隨著節點將CPU挖礦升級為GPU、甚至礦機挖礦，節點數和算力已漸漸失衡； 2、比特幣等網絡每秒需完成數百萬億次哈希計算，資源大量浪費。為此，業內提出了Pow的替代者如PoS權益證明算法，即要求用戶擁有一定數量的貨幣，才有權參與確定下一個合法區塊。另外，相對擁有51%算力，購買超過半數以上的貨幣難度更大，也使得惡意攻擊更加困難