From eece63fa72566068cb2a1bf85c95a72a5ba59bc9 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 17 Nov 2015 17:35:44 +0100 Subject: Switch blocks to a constant-space Merkle root/branch algorithm. This switches the Merkle tree logic for blocks to one that runs in constant (small) space. The old code is moved to tests, and a new test is added that for various combinations of block sizes, transaction positions to compute a branch for, and mutations: * Verifies that the old code and new code agree for the Merkle root. * Verifies that the old code and new code agree for the Merkle branch. * Verifies that the computed Merkle branch is valid. * Verifies that mutations don't change the Merkle root. * Verifies that mutations are correctly detected. --- src/miner.cpp | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'src/miner.cpp') diff --git a/src/miner.cpp b/src/miner.cpp index bb6b51337..8187e5818 100644 --- a/src/miner.cpp +++ b/src/miner.cpp @@ -10,6 +10,7 @@ #include "chainparams.h" #include "coins.h" #include "consensus/consensus.h" +#include "consensus/merkle.h" #include "consensus/validation.h" #include "hash.h" #include "main.h" @@ -373,7 +374,7 @@ void IncrementExtraNonce(CBlock* pblock, const CBlockIndex* pindexPrev, unsigned assert(txCoinbase.vin[0].scriptSig.size() <= 100); pblock->vtx[0] = txCoinbase; - pblock->hashMerkleRoot = pblock->ComputeMerkleRoot(); + pblock->hashMerkleRoot = BlockMerkleRoot(*pblock); } ////////////////////////////////////////////////////////////////////////////// -- cgit v1.2.3 From b966aa836a3bc5bfa1314248258308f0026d41bb Mon Sep 17 00:00:00 2001 From: Luke Dashjr Date: Sat, 27 Jun 2015 19:21:41 +0000 Subject: Constrain constant values to a single location in code --- src/miner.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/miner.cpp') diff --git a/src/miner.cpp b/src/miner.cpp index bb6b51337..5b711210d 100644 --- a/src/miner.cpp +++ b/src/miner.cpp @@ -153,7 +153,7 @@ CBlockTemplate* CreateNewBlock(const CChainParams& chainparams, const CScript& s // Priority order to process transactions list vOrphan; // list memory doesn't move map > mapDependers; - bool fPrintPriority = GetBoolArg("-printpriority", false); + bool fPrintPriority = GetBoolArg("-printpriority", DEFAULT_PRINTPRIORITY); // This vector will be sorted into a priority queue: vector vecPriority; -- cgit v1.2.3 From 553cad94e29c33872b60d97b8574ed2773355f0b Mon Sep 17 00:00:00 2001 From: Alex Morcos Date: Tue, 3 Nov 2015 10:35:39 -0500 Subject: Rewrite CreateNewBlock Use the score index on the mempool to only add sorted txs in order. Remove much of the validation while building the block, relying on mempool to be consistent and only contain txs that can be mined. The mempool is assumed to be consistent as far as not containing txs which spend non-existent outputs or double spends, and scripts are valid. Finality of txs is still checked (except not coinbase maturity, assumed in mempool). Still TestBlockValidity in case mempool consistency breaks and return error state if an invalid block was created. Unit tests are modified to realize that invalid blocks can now be constructed if the mempool breaks its consistency assumptions and also updated to have the right fees, since the cached value is now used for block construction. Conflicts: src/miner.cpp --- src/miner.cpp | 301 +++++++++++++++++++++++----------------------------------- 1 file changed, 120 insertions(+), 181 deletions(-) (limited to 'src/miner.cpp') diff --git a/src/miner.cpp b/src/miner.cpp index 27a1fbcf8..c6db00d30 100644 --- a/src/miner.cpp +++ b/src/miner.cpp @@ -27,6 +27,7 @@ #include #include +#include using namespace std; @@ -40,48 +41,18 @@ using namespace std; // transactions in the memory pool. When we select transactions from the // pool, we select by highest priority or fee rate, so we might consider // transactions that depend on transactions that aren't yet in the block. -// The COrphan class keeps track of these 'temporary orphans' while -// CreateBlock is figuring out which transactions to include. -// -class COrphan -{ -public: - const CTransaction* ptx; - set setDependsOn; - CFeeRate feeRate; - double dPriority; - - COrphan(const CTransaction* ptxIn) : ptx(ptxIn), feeRate(0), dPriority(0) - { - } -}; uint64_t nLastBlockTx = 0; uint64_t nLastBlockSize = 0; -// We want to sort transactions by priority and fee rate, so: -typedef boost::tuple TxPriority; -class TxPriorityCompare +class ScoreCompare { - bool byFee; - public: - TxPriorityCompare(bool _byFee) : byFee(_byFee) { } + ScoreCompare() {} - bool operator()(const TxPriority& a, const TxPriority& b) + bool operator()(const CTxMemPool::txiter a, const CTxMemPool::txiter b) { - if (byFee) - { - if (a.get<1>() == b.get<1>()) - return a.get<0>() < b.get<0>(); - return a.get<1>() < b.get<1>(); - } - else - { - if (a.get<0>() == b.get<0>()) - return a.get<1>() < b.get<1>(); - return a.get<0>() < b.get<0>(); - } + return CompareTxMemPoolEntryByScore()(*b,*a); // Convert to less than } }; @@ -141,6 +112,22 @@ CBlockTemplate* CreateNewBlock(const CChainParams& chainparams, const CScript& s nBlockMinSize = std::min(nBlockMaxSize, nBlockMinSize); // Collect memory pool transactions into the block + CTxMemPool::setEntries inBlock; + CTxMemPool::setEntries waitSet; + + // This vector will be sorted into a priority queue: + vector vecPriority; + TxCoinAgePriorityCompare pricomparer; + std::map waitPriMap; + typedef std::map::iterator waitPriIter; + double actualPriority = -1; + + std::priority_queue, ScoreCompare> clearedTxs; + bool fPrintPriority = GetBoolArg("-printpriority", DEFAULT_PRINTPRIORITY); + uint64_t nBlockSize = 1000; + uint64_t nBlockTx = 0; + unsigned int nBlockSigOps = 100; + int lastFewTxs = 0; CAmount nFees = 0; { @@ -149,157 +136,102 @@ CBlockTemplate* CreateNewBlock(const CChainParams& chainparams, const CScript& s const int nHeight = pindexPrev->nHeight + 1; pblock->nTime = GetAdjustedTime(); const int64_t nMedianTimePast = pindexPrev->GetMedianTimePast(); - CCoinsViewCache view(pcoinsTip); - - // Priority order to process transactions - list vOrphan; // list memory doesn't move - map > mapDependers; - bool fPrintPriority = GetBoolArg("-printpriority", DEFAULT_PRINTPRIORITY); - - // This vector will be sorted into a priority queue: - vector vecPriority; - vecPriority.reserve(mempool.mapTx.size()); - for (CTxMemPool::indexed_transaction_set::iterator mi = mempool.mapTx.begin(); - mi != mempool.mapTx.end(); ++mi) - { - const CTransaction& tx = mi->GetTx(); - - int64_t nLockTimeCutoff = (STANDARD_LOCKTIME_VERIFY_FLAGS & LOCKTIME_MEDIAN_TIME_PAST) - ? nMedianTimePast - : pblock->GetBlockTime(); - - if (tx.IsCoinBase() || !IsFinalTx(tx, nHeight, nLockTimeCutoff)) - continue; - - COrphan* porphan = NULL; - double dPriority = 0; - CAmount nTotalIn = 0; - bool fMissingInputs = false; - BOOST_FOREACH(const CTxIn& txin, tx.vin) - { - // Read prev transaction - if (!view.HaveCoins(txin.prevout.hash)) - { - // This should never happen; all transactions in the memory - // pool should connect to either transactions in the chain - // or other transactions in the memory pool. - if (!mempool.mapTx.count(txin.prevout.hash)) - { - LogPrintf("ERROR: mempool transaction missing input\n"); - if (fDebug) assert("mempool transaction missing input" == 0); - fMissingInputs = true; - if (porphan) - vOrphan.pop_back(); - break; - } - - // Has to wait for dependencies - if (!porphan) - { - // Use list for automatic deletion - vOrphan.push_back(COrphan(&tx)); - porphan = &vOrphan.back(); - } - mapDependers[txin.prevout.hash].push_back(porphan); - porphan->setDependsOn.insert(txin.prevout.hash); - nTotalIn += mempool.mapTx.find(txin.prevout.hash)->GetTx().vout[txin.prevout.n].nValue; - continue; - } - const CCoins* coins = view.AccessCoins(txin.prevout.hash); - assert(coins); - - CAmount nValueIn = coins->vout[txin.prevout.n].nValue; - nTotalIn += nValueIn; - - int nConf = nHeight - coins->nHeight; - - dPriority += (double)nValueIn * nConf; - } - if (fMissingInputs) continue; - - // Priority is sum(valuein * age) / modified_txsize - unsigned int nTxSize = ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION); - dPriority = tx.ComputePriority(dPriority, nTxSize); - - uint256 hash = tx.GetHash(); - mempool.ApplyDeltas(hash, dPriority, nTotalIn); - CFeeRate feeRate(nTotalIn-tx.GetValueOut(), nTxSize); + int64_t nLockTimeCutoff = (STANDARD_LOCKTIME_VERIFY_FLAGS & LOCKTIME_MEDIAN_TIME_PAST) + ? nMedianTimePast + : pblock->GetBlockTime(); - if (porphan) + bool fPriorityBlock = nBlockPrioritySize > 0; + if (fPriorityBlock) { + vecPriority.reserve(mempool.mapTx.size()); + for (CTxMemPool::indexed_transaction_set::iterator mi = mempool.mapTx.begin(); + mi != mempool.mapTx.end(); ++mi) { - porphan->dPriority = dPriority; - porphan->feeRate = feeRate; + double dPriority = mi->GetPriority(nHeight); + CAmount dummy; + mempool.ApplyDeltas(mi->GetTx().GetHash(), dPriority, dummy); + vecPriority.push_back(TxCoinAgePriority(dPriority, mi)); } - else - vecPriority.push_back(TxPriority(dPriority, feeRate, &(mi->GetTx()))); + std::make_heap(vecPriority.begin(), vecPriority.end(), pricomparer); } - // Collect transactions into block - uint64_t nBlockSize = 1000; - uint64_t nBlockTx = 0; - int nBlockSigOps = 100; - bool fSortedByFee = (nBlockPrioritySize <= 0); + CTxMemPool::indexed_transaction_set::nth_index<3>::type::iterator mi = mempool.mapTx.get<3>().begin(); + CTxMemPool::txiter iter; - TxPriorityCompare comparer(fSortedByFee); - std::make_heap(vecPriority.begin(), vecPriority.end(), comparer); - - while (!vecPriority.empty()) + while (mi != mempool.mapTx.get<3>().end() || !clearedTxs.empty()) { - // Take highest priority transaction off the priority queue: - double dPriority = vecPriority.front().get<0>(); - CFeeRate feeRate = vecPriority.front().get<1>(); - const CTransaction& tx = *(vecPriority.front().get<2>()); - - std::pop_heap(vecPriority.begin(), vecPriority.end(), comparer); - vecPriority.pop_back(); - - // Size limits - unsigned int nTxSize = ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION); - if (nBlockSize + nTxSize >= nBlockMaxSize) - continue; + bool priorityTx = false; + if (fPriorityBlock && !vecPriority.empty()) { // add a tx from priority queue to fill the blockprioritysize + priorityTx = true; + iter = vecPriority.front().second; + actualPriority = vecPriority.front().first; + std::pop_heap(vecPriority.begin(), vecPriority.end(), pricomparer); + vecPriority.pop_back(); + } + else if (clearedTxs.empty()) { // add tx with next highest score + iter = mempool.mapTx.project<0>(mi); + mi++; + } + else { // try to add a previously postponed child tx + iter = clearedTxs.top(); + clearedTxs.pop(); + } - // Legacy limits on sigOps: - unsigned int nTxSigOps = GetLegacySigOpCount(tx); - if (nBlockSigOps + nTxSigOps >= MAX_BLOCK_SIGOPS) - continue; + if (inBlock.count(iter)) + continue; // could have been added to the priorityBlock - // Skip free transactions if we're past the minimum block size: - const uint256& hash = tx.GetHash(); - double dPriorityDelta = 0; - CAmount nFeeDelta = 0; - mempool.ApplyDeltas(hash, dPriorityDelta, nFeeDelta); - if (fSortedByFee && (dPriorityDelta <= 0) && (nFeeDelta <= 0) && (feeRate < ::minRelayTxFee) && (nBlockSize + nTxSize >= nBlockMinSize)) - continue; + const CTransaction& tx = iter->GetTx(); - // Prioritise by fee once past the priority size or we run out of high-priority - // transactions: - if (!fSortedByFee && - ((nBlockSize + nTxSize >= nBlockPrioritySize) || !AllowFree(dPriority))) + bool fOrphan = false; + BOOST_FOREACH(CTxMemPool::txiter parent, mempool.GetMemPoolParents(iter)) { - fSortedByFee = true; - comparer = TxPriorityCompare(fSortedByFee); - std::make_heap(vecPriority.begin(), vecPriority.end(), comparer); + if (!inBlock.count(parent)) { + fOrphan = true; + break; + } } - - if (!view.HaveInputs(tx)) + if (fOrphan) { + if (priorityTx) + waitPriMap.insert(std::make_pair(iter,actualPriority)); + else + waitSet.insert(iter); continue; + } - CAmount nTxFees = view.GetValueIn(tx)-tx.GetValueOut(); - - nTxSigOps += GetP2SHSigOpCount(tx, view); - if (nBlockSigOps + nTxSigOps >= MAX_BLOCK_SIGOPS) + unsigned int nTxSize = iter->GetTxSize(); + if (fPriorityBlock && + (nBlockSize + nTxSize >= nBlockPrioritySize || !AllowFree(actualPriority))) { + fPriorityBlock = false; + waitPriMap.clear(); + } + if (!priorityTx && + (iter->GetModifiedFee() < ::minRelayTxFee.GetFee(nTxSize) && nBlockSize >= nBlockMinSize)) { + break; + } + if (nBlockSize + nTxSize >= nBlockMaxSize) { + if (nBlockSize > nBlockMaxSize - 100 || lastFewTxs > 50) { + break; + } + // Once we're within 1000 bytes of a full block, only look at 50 more txs + // to try to fill the remaining space. + if (nBlockSize > nBlockMaxSize - 1000) { + lastFewTxs++; + } continue; + } - // Note that flags: we don't want to set mempool/IsStandard() - // policy here, but we still have to ensure that the block we - // create only contains transactions that are valid in new blocks. - CValidationState state; - if (!CheckInputs(tx, state, view, true, MANDATORY_SCRIPT_VERIFY_FLAGS, true)) + if (!IsFinalTx(tx, nHeight, nLockTimeCutoff)) continue; - UpdateCoins(tx, state, view, nHeight); + unsigned int nTxSigOps = iter->GetSigOpCount(); + if (nBlockSigOps + nTxSigOps >= MAX_BLOCK_SIGOPS) { + if (nBlockSigOps > MAX_BLOCK_SIGOPS - 2) { + break; + } + continue; + } + CAmount nTxFees = iter->GetFee(); // Added pblock->vtx.push_back(tx); pblocktemplate->vTxFees.push_back(nTxFees); @@ -311,31 +243,37 @@ CBlockTemplate* CreateNewBlock(const CChainParams& chainparams, const CScript& s if (fPrintPriority) { + double dPriority = iter->GetPriority(nHeight); + CAmount dummy; + mempool.ApplyDeltas(tx.GetHash(), dPriority, dummy); LogPrintf("priority %.1f fee %s txid %s\n", - dPriority, feeRate.ToString(), tx.GetHash().ToString()); + dPriority , CFeeRate(iter->GetModifiedFee(), nTxSize).ToString(), tx.GetHash().ToString()); } + inBlock.insert(iter); + // Add transactions that depend on this one to the priority queue - if (mapDependers.count(hash)) + BOOST_FOREACH(CTxMemPool::txiter child, mempool.GetMemPoolChildren(iter)) { - BOOST_FOREACH(COrphan* porphan, mapDependers[hash]) - { - if (!porphan->setDependsOn.empty()) - { - porphan->setDependsOn.erase(hash); - if (porphan->setDependsOn.empty()) - { - vecPriority.push_back(TxPriority(porphan->dPriority, porphan->feeRate, porphan->ptx)); - std::push_heap(vecPriority.begin(), vecPriority.end(), comparer); - } + if (fPriorityBlock) { + waitPriIter wpiter = waitPriMap.find(child); + if (wpiter != waitPriMap.end()) { + vecPriority.push_back(TxCoinAgePriority(wpiter->second,child)); + std::push_heap(vecPriority.begin(), vecPriority.end(), pricomparer); + waitPriMap.erase(wpiter); + } + } + else { + if (waitSet.count(child)) { + clearedTxs.push(child); + waitSet.erase(child); } } } } - nLastBlockTx = nBlockTx; nLastBlockSize = nBlockSize; - LogPrintf("CreateNewBlock(): total size %u\n", nBlockSize); + LogPrintf("CreateNewBlock(): total size %u txs: %u fees: %ld sigops %d\n", nBlockSize, nBlockTx, nFees, nBlockSigOps); // Compute final coinbase transaction. txNew.vout[0].nValue = nFees + GetBlockSubsidy(nHeight, chainparams.GetConsensus()); @@ -351,8 +289,9 @@ CBlockTemplate* CreateNewBlock(const CChainParams& chainparams, const CScript& s pblocktemplate->vTxSigOps[0] = GetLegacySigOpCount(pblock->vtx[0]); CValidationState state; - if (!TestBlockValidity(state, chainparams, *pblock, pindexPrev, false, false)) - throw std::runtime_error("CreateNewBlock(): TestBlockValidity failed"); + if (!TestBlockValidity(state, chainparams, *pblock, pindexPrev, false, false)) { + throw std::runtime_error(strprintf("%s: TestBlockValidity failed: %s", __func__, FormatStateMessage(state))); + } } return pblocktemplate.release(); -- cgit v1.2.3 From 74f7341fecd327587cba77db3fc1455efcaa20be Mon Sep 17 00:00:00 2001 From: antonio-fr Date: Mon, 10 Aug 2015 23:56:04 +0200 Subject: Update miner.cpp: Fix typo in comment --- src/miner.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/miner.cpp') diff --git a/src/miner.cpp b/src/miner.cpp index c6db00d30..2728c7e6a 100644 --- a/src/miner.cpp +++ b/src/miner.cpp @@ -98,7 +98,7 @@ CBlockTemplate* CreateNewBlock(const CChainParams& chainparams, const CScript& s // Largest block you're willing to create: unsigned int nBlockMaxSize = GetArg("-blockmaxsize", DEFAULT_BLOCK_MAX_SIZE); - // Limit to betweeen 1K and MAX_BLOCK_SIZE-1K for sanity: + // Limit to between 1K and MAX_BLOCK_SIZE-1K for sanity: nBlockMaxSize = std::max((unsigned int)1000, std::min((unsigned int)(MAX_BLOCK_SIZE-1000), nBlockMaxSize)); // How much of the block should be dedicated to high-priority transactions, -- cgit v1.2.3 From fa24439ff3d8ab5b9efaf66ef4dae6713b88cb35 Mon Sep 17 00:00:00 2001 From: MarcoFalke Date: Sun, 13 Dec 2015 17:58:29 +0100 Subject: Bump copyright headers to 2015 --- src/miner.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/miner.cpp') diff --git a/src/miner.cpp b/src/miner.cpp index 2728c7e6a..c454c0279 100644 --- a/src/miner.cpp +++ b/src/miner.cpp @@ -1,5 +1,5 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto -// Copyright (c) 2009-2014 The Bitcoin Core developers +// Copyright (c) 2009-2015 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. -- cgit v1.2.3