本文共 14121 字，大约阅读时间需要 47 分钟。
PoW，全称Proof of Work，即工作量证明，又称挖矿。大部分公有链或虚拟货币，如比特币、以太坊，均基于PoW算法，来实现其共识机制。即根据挖矿贡献的有效工作，来决定货币的分配。
比特币区块由区块头和该区块所包含的交易列表组成。区块头大小为80字节，其构成包括： 4字节：版本号 32字节：上一个区块的哈希值 32字节：交易列表的Merkle根哈希值 4字节：当前时间戳 4字节：当前难度值 4字节：随机数Nonce值 此80字节长度的区块头，即为比特币Pow算法的输入字符串。 交易列表附加在区块头之后，其中第一笔交易为矿工获得奖励和手续费的特殊交易。 bitcoin-0.15.1源码中区块头和区块定义：
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 vtx; //其它代码略};//代码位置src/primitives/block.h
Pow的过程，即为不断调整Nonce值，对区块头做双重SHA256哈希运算，使得结果满足给定数量前导0的哈希值的过程。 其中前导0的个数，取决于挖矿难度，前导0的个数越多，挖矿难度越大。 具体如下： 1、生成铸币交易，并与其它所有准备打包进区块的交易组成交易列表，生成Merkle根哈希值。 2、将Merkle根哈希值，与区块头其它字段组成区块头，80字节长度的区块头作为Pow算法的输入。 3、不断变更区块头中的随机数Nonce，对变更后的区块头做双重SHA256哈希运算，与当前难度的目标值做比对，如果小于目标难度，即Pow完成。 Pow完成的区块向全网广播，其他节点将验证其是否符合规则，如果验证有效，其他节点将接收此区块，并附加在已有区块链之后。之后将进入下一轮挖矿。 bitcoin-0.15.1源码中Pow算法实现：
UniValue generateBlocks(std::shared_ptrcoinbaseScript, 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 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 shared_pblock = std::make_shared (*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源码中生成铸币交易和创建新块：
std::unique_ptrBlockAssembler::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个块的难度总和，即单个块的难度x总时间。 3、计算新的难度，即2016个块的难度总和/14天的秒数，得到每秒的难度值。 4、要求新的难度，难度不低于参数定义的最小难度。 bitcoin-0.15.1源码中计算挖矿难度代码如下：
//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源码中区块头和区块定义：
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算法可以表示为如下公式： 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算法实现：
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源码中计算挖矿难度代码如下：
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%算力，购买超过半数以上的货币难度更大，也使得恶意***更加困难。
转载于:https://blog.51cto.com/11821908/2059711