PoW挖礦算法原理及其在比特幣、以太坊中的實(shí)現(xiàn)

　　PoW，全稱Proof of Work，即工作量證明，又稱挖礦。大部分公有鏈或虛擬貨幣，如比特幣、以太坊，均基于PoW算法，來(lái)實(shí)現(xiàn)其共識(shí)機(jī)制。即根據(jù)挖礦貢獻(xiàn)的有效工作，來(lái)決定貨幣的分配。
?

比特幣區(qū)塊

?
　　比特幣區(qū)塊由區(qū)塊頭和該區(qū)塊所包含的交易列表組成。區(qū)塊頭大小為80字節(jié)，其構(gòu)成包括：
?
　　 4字節(jié)：版本號(hào)
　　32字節(jié)：上一個(gè)區(qū)塊的哈希值
　　32字節(jié)：交易列表的Merkle根哈希值
　　 4字節(jié)：當(dāng)前時(shí)間戳
　　 4字節(jié)：當(dāng)前難度值
　　 4字節(jié)：隨機(jī)數(shù)Nonce值
?
　　此80字節(jié)長(zhǎng)度的區(qū)塊頭，即為比特幣Pow算法的輸入字符串。
　　交易列表附加在區(qū)塊頭之后，其中第一筆交易為礦工獲得獎(jiǎng)勵(lì)和手續(xù)費(fèi)的特殊交易。
?
　　bitcoin-0.15.1源碼中區(qū)塊頭和區(qū)塊定義：
?

class CBlockHeader
{
public:
    //版本號(hào)
    int32_t nVersion;
    //上一個(gè)區(qū)塊的哈希值
    uint256 hashPrevBlock;
    //交易列表的Merkle根哈希值
    uint256 hashMerkleRoot;
    //當(dāng)前時(shí)間戳
    uint32_t nTime;
    //當(dāng)前挖礦難度，nBits越小難度越大
    uint32_t nBits;
    //隨機(jī)數(shù)Nonce值
    uint32_t nNonce;
    //其它代碼略
};

class CBlock : public CBlockHeader
{
public:
    //交易列表
    std::vector<CTransactionRef> vtx;
    //其它代碼略
};
//代碼位置src/primitives/block.h

?

比特幣Pow算法原理

?
　　Pow的過(guò)程，即為不斷調(diào)整Nonce值，對(duì)區(qū)塊頭做雙重SHA256哈希運(yùn)算，使得結(jié)果滿足給定數(shù)量前導(dǎo)0的哈希值的過(guò)程。
　　其中前導(dǎo)0的個(gè)數(shù)，取決于挖礦難度，前導(dǎo)0的個(gè)數(shù)越多，挖礦難度越大。
?
　　具體如下：
?
　　1、生成鑄幣交易，并與其它所有準(zhǔn)備打包進(jìn)區(qū)塊的交易組成交易列表，生成Merkle根哈希值。
　　2、將Merkle根哈希值，與區(qū)塊頭其它字段組成區(qū)塊頭，80字節(jié)長(zhǎng)度的區(qū)塊頭作為Pow算法的輸入。
　　3、不斷變更區(qū)塊頭中的隨機(jī)數(shù)Nonce，對(duì)變更后的區(qū)塊頭做雙重SHA256哈希運(yùn)算，與當(dāng)前難度的目標(biāo)值做比對(duì)，如果小于目標(biāo)難度，即Pow完成。
?
　　Pow完成的區(qū)塊向全網(wǎng)廣播，其他節(jié)點(diǎn)將驗(yàn)證其是否符合規(guī)則，如果驗(yàn)證有效，其他節(jié)點(diǎn)將接收此區(qū)塊，并附加在已有區(qū)塊鏈之后。之后將進(jìn)入下一輪挖礦。
?
　　bitcoin-0.15.1源碼中Pow算法實(shí)現(xiàn)：

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);
        }
        //不斷變更區(qū)塊頭中的隨機(jī)數(shù)Nonce
        //對(duì)變更后的區(qū)塊頭做雙重SHA256哈希運(yùn)算
        //與當(dāng)前難度的目標(biāo)值做比對(duì)，如果小于目標(biāo)難度，即Pow完成
        //uint64_t nMaxTries = 1000000;即重試100萬(wàn)次
        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源碼中生成鑄幣交易和創(chuàng)建新塊：
?

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;

    //版本號(hào)
    pblock->nVersion = ComputeBlockVersion(pindexPrev, chainparams.GetConsensus());
    if (chainparams.MineBlocksOnDemand())
        pblock->nVersion = gArgs.GetArg("-blockversion", pblock->nVersion);

    //當(dāng)前時(shí)間戳
    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;

    //創(chuàng)建鑄幣交易
    CMutableTransaction coinbaseTx;
    coinbaseTx.vin.resize(1);
    coinbaseTx.vin[0].prevout.SetNull();
    coinbaseTx.vout.resize(1);
    //挖礦獎(jiǎng)勵(lì)和手續(xù)費(fèi)
    coinbaseTx.vout[0].scriptPubKey = scriptPubKeyIn;
    coinbaseTx.vout[0].nValue = nFees + GetBlockSubsidy(nHeight, chainparams.GetConsensus());
    coinbaseTx.vin[0].scriptSig = CScript() << nHeight << OP_0;
    //第一筆交易即為礦工獲得獎(jiǎng)勵(lì)和手續(xù)費(fèi)的特殊交易
    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);

    //上一個(gè)區(qū)塊的哈希值
    pblock->hashPrevBlock  = pindexPrev->GetBlockHash();
    UpdateTime(pblock, chainparams.GetConsensus(), pindexPrev);
    //當(dāng)前挖礦難度
    pblock->nBits          = GetNextWorkRequired(pindexPrev, pblock, chainparams.GetConsensus());
    //隨機(jī)數(shù)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

?

比特幣挖礦難度計(jì)算

?
　　每創(chuàng)建2016個(gè)塊后將計(jì)算新的難度，此后的2016個(gè)塊使用新的難度。計(jì)算步驟如下：
?
　　1、找到前2016個(gè)塊的第一個(gè)塊，計(jì)算生成這2016個(gè)塊花費(fèi)的時(shí)間。
即最后一個(gè)塊的時(shí)間與第一個(gè)塊的時(shí)間差。時(shí)間差不小于3.5天，不大于56天。
　　2、計(jì)算前2016個(gè)塊的難度總和，即單個(gè)塊的難度x總時(shí)間。
　　3、計(jì)算新的難度，即2016個(gè)塊的難度總和/14天的秒數(shù)，得到每秒的難度值。
　　4、要求新的難度，難度不低于參數(shù)定義的最小難度。
?
　　bitcoin-0.15.1源碼中計(jì)算挖礦難度代碼如下：
?

//nFirstBlockTime即前2016個(gè)塊的第一個(gè)塊的時(shí)間戳
unsigned int CalculateNextWorkRequired(const CBlockIndex* pindexLast, int64_t nFirstBlockTime, const Consensus::Params& params)
{
    if (params.fPowNoRetargeting)
        return pindexLast->nBits;

    //計(jì)算生成這2016個(gè)塊花費(fèi)的時(shí)間
    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 = UintToArith356(params.powLimit);
    arith_uint256 bnNew;
    bnNew.SetCompact(pindexLast->nBits);
    //計(jì)算前2016個(gè)塊的難度總和
    //即單個(gè)塊的難度*總時(shí)間
    bnNew *= nActualTimespan;
    //計(jì)算新的難度
    //即2016個(gè)塊的難度總和/14天的秒數(shù)
    bnNew /= params.nPowTargetTimespan;

    //bnNew越小，難度越大
    //bnNew越大，難度越小
    //要求新的難度，難度不低于參數(shù)定義的最小難度
    if (bnNew > bnPowLimit)
        bnNew = bnPowLimit;

    return bnNew.GetCompact();
}
//代碼位置src/pow.cpp

?

以太坊區(qū)塊

?
　　以太坊區(qū)塊由Header和Body兩部分組成。
?
　　其中Header部分成員如下：
　　ParentHash，父區(qū)塊哈希
　　UncleHash，叔區(qū)塊哈希，具體為Body中Uncles數(shù)組的RLP哈希值。RLP哈希，即某類型對(duì)象RLP編碼后做SHA3哈希運(yùn)算。
　　Coinbase，礦工地址。
　　Root，StateDB中state Trie根節(jié)點(diǎn)RLP哈希值。
　　TxHash，Block中tx Trie根節(jié)點(diǎn)RLP哈希值。
　　ReceiptHash，Block中Receipt Trie根節(jié)點(diǎn)的RLP哈希值。
　　Difficulty，區(qū)塊難度，即當(dāng)前挖礦難度。
　　Number，區(qū)塊序號(hào)，即父區(qū)塊Number+1。
　　GasLimit，區(qū)塊內(nèi)所有Gas消耗的理論上限，創(chuàng)建時(shí)指定，由父區(qū)塊GasUsed和GasLimit計(jì)算得出。
　　GasUsed，區(qū)塊內(nèi)所有Transaction執(zhí)行時(shí)消耗的Gas總和。
　　Time，當(dāng)前時(shí)間戳。
　　Nonce，隨機(jī)數(shù)Nonce值。
?
　　有關(guān)叔區(qū)塊：
　　叔區(qū)塊，即孤立的塊。以太坊成塊速度較快，導(dǎo)致產(chǎn)生孤塊。
　　以太坊會(huì)給發(fā)現(xiàn)孤塊的礦工以回報(bào)，激勵(lì)礦工在新塊中引用孤塊，引用孤塊使主鏈更重。在以太坊中，主鏈?zhǔn)侵缸钪氐逆湣?br/>?
　　有關(guān)state Trie、tx Trie和Receipt Trie：
　　state Trie，所有賬戶對(duì)象可以逐個(gè)插入一個(gè)Merkle-PatricaTrie(MPT)結(jié)構(gòu)中，形成state Trie。
　　tx Trie：Block中Transactions中所有tx對(duì)象，逐個(gè)插入MPT結(jié)構(gòu)中，形成tx Trie。
　　Receipt Trie：Block中所有Transaction執(zhí)行后生成Receipt數(shù)組，所有Receipt逐個(gè)插入MPT結(jié)構(gòu)中，形成Receipt Trie。
?
　　Body成員如下：
　　Transactions，交易列表。
　　Uncles，引用的叔區(qū)塊列表。
?
　　go-ethereum-1.7.3源碼中區(qū)塊頭和區(qū)塊定義：
?

type Header struct {
    //父區(qū)塊哈希
    ParentHash  common.Hash
    //叔區(qū)塊哈希
    UncleHash   common.Hash
    //礦工地址
    Coinbase    common.Address
    //StateDB中state Trie根節(jié)點(diǎn)RLP哈希值
    Root        common.Hash
    //Block中tx Trie根節(jié)點(diǎn)RLP哈希值
    TxHash      common.Hash
    //Block中Receipt Trie根節(jié)點(diǎn)的RLP哈希值
    ReceiptHash common.Hash
    Bloom       Bloom
    //區(qū)塊難度
    Difficulty  *big.Int
    //區(qū)塊序號(hào)
    Number      *big.Int
    //區(qū)塊內(nèi)所有Gas消耗的理論上限
    GasLimit    *big.Int
    //區(qū)塊內(nèi)所有Transaction執(zhí)行時(shí)消耗的Gas總和
    GasUsed     *big.Int
    //當(dāng)前時(shí)間戳
    Time        *big.Int
    Extra       []byte
    MixDigest   common.Hash
    //隨機(jī)數(shù)Nonce值
    Nonce       BlockNonce
}

type Body struct {
    //交易列表
    Transactions []*Transaction
    //引用的叔區(qū)塊列表
    Uncles       []*Header
}
//代碼位置core/types/block.go

?

以太坊Pow算法原理

?
　　以太坊Pow算法可以表示為如下公式：
　　RAND(h, n) <= M / d
?
　　其中RAND()表示一個(gè)概念函數(shù)，代表一系列的復(fù)雜運(yùn)算。
　　其中h和n為輸入，即區(qū)塊Header的哈希、以及Header中的Nonce。
　　M表示一個(gè)極大的數(shù)，此處使用2^256-1。
　　d，為區(qū)塊難度，即Header中的Difficulty。
?
　　因此在h和n確定的情況下，d越大，挖礦難度越大，即為Difficulty本義。
　　即不斷變更Nonce，使RAND(h, n)滿足RAND(h, n) <= M / d，即完成Pow。
?
　　go-ethereum-1.7.3源碼中Pow算法實(shí)現(xiàn)：
?

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)所代表的一系列的復(fù)雜運(yù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

?

以太坊挖礦難度計(jì)算

?
　　以太坊每次挖礦均需計(jì)算當(dāng)前區(qū)塊難度。
　　按版本不同有三種計(jì)算難度的規(guī)則，分別為：calcDifficultyByzantium（Byzantium版）、calcDifficultyHomestead（Homestead版）、calcDifficultyFrontier（Frontier版）。此處以calcDifficultyHomestead為例。
?
　　計(jì)算難度時(shí)輸入有：
　　parent_timestamp：父區(qū)塊時(shí)間戳
　　parent_diff：父區(qū)塊難度
　　block_timestamp：當(dāng)前區(qū)塊時(shí)間戳
　　block_number：當(dāng)前區(qū)塊的序號(hào)
?
　　當(dāng)前區(qū)塊難度計(jì)算公式，即：
?

block_diff = parent_diff
+ (parent_diff / 2048 * max(1 - (block_timestamp - parent_timestamp) // 10, -99)
+ 2^((block_number // 100000) - 2)

?
　　其中//為整數(shù)除法運(yùn)算符，a//b，即先計(jì)算a/b，然后取不大于a/b的最大整數(shù)。
?
　　調(diào)整難度的目的，即為使挖礦時(shí)間保持在10-19s期間內(nèi)，如果低于10s增大挖礦難度，如果大于19s將減小難度。另外，計(jì)算出的當(dāng)前區(qū)塊難度不應(yīng)低于以太坊創(chuàng)世區(qū)塊難度，即131072。
?
　　go-ethereum-1.7.3源碼中計(jì)算挖礦難度代碼如下：
?

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算法概念簡(jiǎn)單，即工作端提交難以計(jì)算但易于驗(yàn)證的計(jì)算結(jié)果，其他節(jié)點(diǎn)通過(guò)驗(yàn)證這個(gè)結(jié)果來(lái)確信工作端完成了相當(dāng)?shù)墓ぷ髁俊?br/>　　但其缺陷也很明顯：1、隨著節(jié)點(diǎn)將CPU挖礦升級(jí)為GPU、甚至礦機(jī)挖礦，節(jié)點(diǎn)數(shù)和算力已漸漸失衡；2、比特幣等網(wǎng)絡(luò)每秒需完成數(shù)百萬(wàn)億次哈希計(jì)算，資源大量浪費(fèi)。
　　為此，業(yè)內(nèi)提出了Pow的替代者如PoS權(quán)益證明算法，即要求用戶擁有一定數(shù)量的貨幣，才有權(quán)參與確定下一個(gè)合法區(qū)塊。另外，相對(duì)擁有51%算力，購(gòu)買超過(guò)半數(shù)以上的貨幣難度更大，也使得惡意***更加困難。