diff options
Diffstat (limited to 'src/main.cpp')
| -rw-r--r-- | src/main.cpp | 652 |
1 files changed, 508 insertions, 144 deletions
diff --git a/src/main.cpp b/src/main.cpp index b59e8a5ac..0c9e43a9b 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -10,6 +10,7 @@ #include "net.h" #include "init.h" #include "ui_interface.h" +#include "checkqueue.h" #include <boost/algorithm/string/replace.hpp> #include <boost/filesystem.hpp> #include <boost/filesystem/fstream.hpp> @@ -40,12 +41,14 @@ uint256 hashBestChain = 0; CBlockIndex* pindexBest = NULL; set<CBlockIndex*, CBlockIndexWorkComparator> setBlockIndexValid; // may contain all CBlockIndex*'s that have validness >=BLOCK_VALID_TRANSACTIONS, and must contain those who aren't failed int64 nTimeBestReceived = 0; +int nScriptCheckThreads = 0; bool fImporting = false; bool fReindex = false; bool fBenchmark = false; +bool fTxIndex = false; unsigned int nCoinCacheSize = 5000; -CMedianFilter<int> cPeerBlockCounts(5, 0); // Amount of blocks that other nodes claim to have +CMedianFilter<int> cPeerBlockCounts(8, 0); // Amount of blocks that other nodes claim to have map<uint256, CBlock*> mapOrphanBlocks; multimap<uint256, CBlock*> mapOrphanBlocksByPrev; @@ -467,28 +470,21 @@ CTransaction::GetLegacySigOpCount() const int CMerkleTx::SetMerkleBranch(const CBlock* pblock) { - if (fClient) - { - if (hashBlock == 0) - return 0; - } - else - { - CBlock blockTmp; - - if (pblock == NULL) { - CCoins coins; - if (pcoinsTip->GetCoins(GetHash(), coins)) { - CBlockIndex *pindex = FindBlockByHeight(coins.nHeight); - if (pindex) { - if (!blockTmp.ReadFromDisk(pindex)) - return 0; - pblock = &blockTmp; - } + CBlock blockTmp; + + if (pblock == NULL) { + CCoins coins; + if (pcoinsTip->GetCoins(GetHash(), coins)) { + CBlockIndex *pindex = FindBlockByHeight(coins.nHeight); + if (pindex) { + if (!blockTmp.ReadFromDisk(pindex)) + return 0; + pblock = &blockTmp; } } + } - if (pblock) { + if (pblock) { // Update the tx's hashBlock hashBlock = pblock->GetHash(); @@ -506,7 +502,6 @@ int CMerkleTx::SetMerkleBranch(const CBlock* pblock) // Fill in merkle branch vMerkleBranch = pblock->GetMerkleBranch(nIndex); - } } // Is the tx in a block that's in the main chain @@ -635,7 +630,7 @@ void CTxMemPool::pruneSpent(const uint256 &hashTx, CCoins &coins) } } -bool CTxMemPool::accept(CTransaction &tx, bool fCheckInputs, +bool CTxMemPool::accept(CTransaction &tx, bool fCheckInputs, bool fLimitFree, bool* pfMissingInputs) { if (pfMissingInputs) @@ -741,7 +736,7 @@ bool CTxMemPool::accept(CTransaction &tx, bool fCheckInputs, // Don't accept it if it can't get into a block int64 txMinFee = tx.GetMinFee(1000, true, GMF_RELAY); - if (nFees < txMinFee) + if (fLimitFree && nFees < txMinFee) return error("CTxMemPool::accept() : not enough fees %s, %"PRI64d" < %"PRI64d, hash.ToString().c_str(), nFees, txMinFee); @@ -749,30 +744,29 @@ bool CTxMemPool::accept(CTransaction &tx, bool fCheckInputs, // Continuously rate-limit free transactions // This mitigates 'penny-flooding' -- sending thousands of free transactions just to // be annoying or make others' transactions take longer to confirm. - if (nFees < MIN_RELAY_TX_FEE) + if (fLimitFree && nFees < MIN_RELAY_TX_FEE) { - static CCriticalSection cs; static double dFreeCount; static int64 nLastTime; int64 nNow = GetTime(); - { - // Use an exponentially decaying ~10-minute window: - dFreeCount *= pow(1.0 - 1.0/600.0, (double)(nNow - nLastTime)); - nLastTime = nNow; - // -limitfreerelay unit is thousand-bytes-per-minute - // At default rate it would take over a month to fill 1GB - if (dFreeCount > GetArg("-limitfreerelay", 15)*10*1000 && !IsFromMe(tx)) - return error("CTxMemPool::accept() : free transaction rejected by rate limiter"); - if (fDebug) - printf("Rate limit dFreeCount: %g => %g\n", dFreeCount, dFreeCount+nSize); - dFreeCount += nSize; - } + LOCK(cs); + + // Use an exponentially decaying ~10-minute window: + dFreeCount *= pow(1.0 - 1.0/600.0, (double)(nNow - nLastTime)); + nLastTime = nNow; + // -limitfreerelay unit is thousand-bytes-per-minute + // At default rate it would take over a month to fill 1GB + if (dFreeCount >= GetArg("-limitfreerelay", 15)*10*1000) + return error("CTxMemPool::accept() : free transaction rejected by rate limiter"); + if (fDebug) + printf("Rate limit dFreeCount: %g => %g\n", dFreeCount, dFreeCount+nSize); + dFreeCount += nSize; } // Check against previous transactions // This is done last to help prevent CPU exhaustion denial-of-service attacks. - if (!tx.CheckInputs(view, CS_ALWAYS, SCRIPT_VERIFY_P2SH)) + if (!tx.CheckInputs(view, true, SCRIPT_VERIFY_P2SH)) { return error("CTxMemPool::accept() : ConnectInputs failed %s", hash.ToString().substr(0,10).c_str()); } @@ -793,6 +787,7 @@ bool CTxMemPool::accept(CTransaction &tx, bool fCheckInputs, // If updated, erase old tx from wallet if (ptxOld) EraseFromWallets(ptxOld->GetHash()); + SyncWithWallets(hash, tx, NULL, true); printf("CTxMemPool::accept() : accepted %s (poolsz %"PRIszu")\n", hash.ToString().substr(0,10).c_str(), @@ -800,9 +795,9 @@ bool CTxMemPool::accept(CTransaction &tx, bool fCheckInputs, return true; } -bool CTransaction::AcceptToMemoryPool(bool fCheckInputs, bool* pfMissingInputs) +bool CTransaction::AcceptToMemoryPool(bool fCheckInputs, bool fLimitFree, bool* pfMissingInputs) { - return mempool.accept(*this, fCheckInputs, pfMissingInputs); + return mempool.accept(*this, fCheckInputs, fLimitFree, pfMissingInputs); } bool CTxMemPool::addUnchecked(const uint256& hash, CTransaction &tx) @@ -913,18 +908,9 @@ int CMerkleTx::GetBlocksToMaturity() const } -bool CMerkleTx::AcceptToMemoryPool(bool fCheckInputs) +bool CMerkleTx::AcceptToMemoryPool(bool fCheckInputs, bool fLimitFree) { - if (fClient) - { - if (!IsInMainChain() && !ClientCheckInputs()) - return false; - return CTransaction::AcceptToMemoryPool(false); - } - else - { - return CTransaction::AcceptToMemoryPool(fCheckInputs); - } + return CTransaction::AcceptToMemoryPool(fCheckInputs, fLimitFree); } @@ -940,10 +926,10 @@ bool CWalletTx::AcceptWalletTransaction(bool fCheckInputs) { uint256 hash = tx.GetHash(); if (!mempool.exists(hash) && pcoinsTip->HaveCoins(hash)) - tx.AcceptToMemoryPool(fCheckInputs); + tx.AcceptToMemoryPool(fCheckInputs, false); } } - return AcceptToMemoryPool(fCheckInputs); + return AcceptToMemoryPool(fCheckInputs, false); } return false; } @@ -964,6 +950,25 @@ bool GetTransaction(const uint256 &hash, CTransaction &txOut, uint256 &hashBlock } } + if (fTxIndex) { + CDiskTxPos postx; + if (pblocktree->ReadTxIndex(hash, postx)) { + CAutoFile file(OpenBlockFile(postx, true), SER_DISK, CLIENT_VERSION); + CBlockHeader header; + try { + file >> header; + fseek(file, postx.nTxOffset, SEEK_CUR); + file >> txOut; + } catch (std::exception &e) { + return error("%s() : deserialize or I/O error", __PRETTY_FUNCTION__); + } + hashBlock = header.GetHash(); + if (txOut.GetHash() != hash) + return error("%s() : txid mismatch", __PRETTY_FUNCTION__); + return true; + } + } + if (fAllowSlow) { // use coin database to locate block that contains transaction, and scan it int nHeight = -1; { @@ -1348,10 +1353,25 @@ bool CTransaction::HaveInputs(CCoinsViewCache &inputs) const return true; } -bool CTransaction::CheckInputs(CCoinsViewCache &inputs, enum CheckSig_mode csmode, unsigned int flags) const +bool CScriptCheck::operator()() const { + const CScript &scriptSig = ptxTo->vin[nIn].scriptSig; + if (!VerifyScript(scriptSig, scriptPubKey, *ptxTo, nIn, nFlags, nHashType)) + return error("CScriptCheck() : %s VerifySignature failed", ptxTo->GetHash().ToString().substr(0,10).c_str()); + return true; +} + +bool VerifySignature(const CCoins& txFrom, const CTransaction& txTo, unsigned int nIn, unsigned int flags, int nHashType) +{ + return CScriptCheck(txFrom, txTo, nIn, flags, nHashType)(); +} + +bool CTransaction::CheckInputs(CCoinsViewCache &inputs, bool fScriptChecks, unsigned int flags, std::vector<CScriptCheck> *pvChecks) const { if (!IsCoinBase()) { + if (pvChecks) + pvChecks->reserve(vin.size()); + // This doesn't trigger the DoS code on purpose; if it did, it would make it easier // for an attacker to attempt to split the network. if (!HaveInputs(inputs)) @@ -1398,15 +1418,18 @@ bool CTransaction::CheckInputs(CCoinsViewCache &inputs, enum CheckSig_mode csmod // Skip ECDSA signature verification when connecting blocks // before the last block chain checkpoint. This is safe because block merkle hashes are // still computed and checked, and any change will be caught at the next checkpoint. - if (csmode == CS_ALWAYS || - (csmode == CS_AFTER_CHECKPOINT && inputs.GetBestBlock()->nHeight >= Checkpoints::GetTotalBlocksEstimate())) { + if (fScriptChecks) { for (unsigned int i = 0; i < vin.size(); i++) { const COutPoint &prevout = vin[i].prevout; const CCoins &coins = inputs.GetCoins(prevout.hash); // Verify signature - if (!VerifySignature(coins, *this, i, flags, 0)) - return DoS(100,error("CheckInputs() : %s VerifySignature failed", GetHash().ToString().substr(0,10).c_str())); + CScriptCheck check(coins, *this, i, flags, 0); + if (pvChecks) { + pvChecks->push_back(CScriptCheck()); + check.swap(pvChecks->back()); + } else if (!check()) + return DoS(100,false); } } } @@ -1464,23 +1487,24 @@ bool CTransaction::ClientCheckInputs() const -bool CBlock::DisconnectBlock(CBlockIndex *pindex, CCoinsViewCache &view) +bool CBlock::DisconnectBlock(CBlockIndex *pindex, CCoinsViewCache &view, bool *pfClean) { assert(pindex == view.GetBestBlock()); + if (pfClean) + *pfClean = false; + + bool fClean = true; + CBlockUndo blockUndo; - { - CDiskBlockPos pos = pindex->GetUndoPos(); - if (pos.IsNull()) - return error("DisconnectBlock() : no undo data available"); - FILE *file = OpenUndoFile(pos, true); - if (file == NULL) - return error("DisconnectBlock() : undo file not available"); - CAutoFile fileUndo(file, SER_DISK, CLIENT_VERSION); - fileUndo >> blockUndo; - } + CDiskBlockPos pos = pindex->GetUndoPos(); + if (pos.IsNull()) + return error("DisconnectBlock() : no undo data available"); + if (!blockUndo.ReadFromDisk(pos, pindex->pprev->GetBlockHash())) + return error("DisconnectBlock() : failure reading undo data"); - assert(blockUndo.vtxundo.size() + 1 == vtx.size()); + if (blockUndo.vtxundo.size() + 1 != vtx.size()) + return error("DisconnectBlock() : block and undo data inconsistent"); // undo transactions in reverse order for (int i = vtx.size() - 1; i >= 0; i--) { @@ -1488,13 +1512,15 @@ bool CBlock::DisconnectBlock(CBlockIndex *pindex, CCoinsViewCache &view) uint256 hash = tx.GetHash(); // check that all outputs are available - if (!view.HaveCoins(hash)) - return error("DisconnectBlock() : outputs still spent? database corrupted"); + if (!view.HaveCoins(hash)) { + fClean = fClean && error("DisconnectBlock() : outputs still spent? database corrupted"); + view.SetCoins(hash, CCoins()); + } CCoins &outs = view.GetCoins(hash); CCoins outsBlock = CCoins(tx, pindex->nHeight); if (outs != outsBlock) - return error("DisconnectBlock() : added transaction mismatch? database corrupted"); + fClean = fClean && error("DisconnectBlock() : added transaction mismatch? database corrupted"); // remove outputs outs = CCoins(); @@ -1502,24 +1528,27 @@ bool CBlock::DisconnectBlock(CBlockIndex *pindex, CCoinsViewCache &view) // restore inputs if (i > 0) { // not coinbases const CTxUndo &txundo = blockUndo.vtxundo[i-1]; - assert(txundo.vprevout.size() == tx.vin.size()); + if (txundo.vprevout.size() != tx.vin.size()) + return error("DisconnectBlock() : transaction and undo data inconsistent"); for (unsigned int j = tx.vin.size(); j-- > 0;) { const COutPoint &out = tx.vin[j].prevout; const CTxInUndo &undo = txundo.vprevout[j]; CCoins coins; view.GetCoins(out.hash, coins); // this can fail if the prevout was already entirely spent - if (coins.IsPruned()) { - if (undo.nHeight == 0) - return error("DisconnectBlock() : undo data doesn't contain tx metadata? database corrupted"); + if (undo.nHeight != 0) { + // undo data contains height: this is the last output of the prevout tx being spent + if (!coins.IsPruned()) + fClean = fClean && error("DisconnectBlock() : undo data overwriting existing transaction"); + coins = CCoins(); coins.fCoinBase = undo.fCoinBase; coins.nHeight = undo.nHeight; coins.nVersion = undo.nVersion; } else { - if (undo.nHeight != 0) - return error("DisconnectBlock() : undo data contains unneeded tx metadata? database corrupted"); + if (coins.IsPruned()) + fClean = fClean && error("DisconnectBlock() : undo data adding output to missing transaction"); } if (coins.IsAvailable(out.n)) - return error("DisconnectBlock() : prevout output not spent? database corrupted"); + fClean = fClean && error("DisconnectBlock() : undo data overwriting existing output"); if (coins.vout.size() < out.n+1) coins.vout.resize(out.n+1); coins.vout[out.n] = undo.txout; @@ -1532,7 +1561,12 @@ bool CBlock::DisconnectBlock(CBlockIndex *pindex, CCoinsViewCache &view) // move best block pointer to prevout block view.SetBestBlock(pindex->pprev); - return true; + if (pfClean) { + *pfClean = fClean; + return true; + } else { + return fClean; + } } void static FlushBlockFile() @@ -1556,6 +1590,19 @@ void static FlushBlockFile() bool FindUndoPos(int nFile, CDiskBlockPos &pos, unsigned int nAddSize); +static CCheckQueue<CScriptCheck> scriptcheckqueue(128); + +void ThreadScriptCheck(void*) { + vnThreadsRunning[THREAD_SCRIPTCHECK]++; + RenameThread("bitcoin-scriptch"); + scriptcheckqueue.Thread(); + vnThreadsRunning[THREAD_SCRIPTCHECK]--; +} + +void ThreadScriptCheckQuit() { + scriptcheckqueue.Quit(); +} + bool CBlock::ConnectBlock(CBlockIndex* pindex, CCoinsViewCache &view, bool fJustCheck) { // Check it again in case a previous version let a bad block in @@ -1565,6 +1612,16 @@ bool CBlock::ConnectBlock(CBlockIndex* pindex, CCoinsViewCache &view, bool fJust // verify that the view's current state corresponds to the previous block assert(pindex->pprev == view.GetBestBlock()); + // Special case for the genesis block, skipping connection of its transactions + // (its coinbase is unspendable) + if (GetHash() == hashGenesisBlock) { + view.SetBestBlock(pindex); + pindexGenesisBlock = pindex; + return true; + } + + bool fScriptChecks = pindex->nHeight >= Checkpoints::GetTotalBlocksEstimate(); + // Do not allow blocks that contain transactions which 'overwrite' older transactions, // unless those are already completely spent. // If such overwrites are allowed, coinbases and transactions depending upon those @@ -1592,12 +1649,20 @@ bool CBlock::ConnectBlock(CBlockIndex* pindex, CCoinsViewCache &view, bool fJust int64 nBIP16SwitchTime = 1333238400; bool fStrictPayToScriptHash = (pindex->nTime >= nBIP16SwitchTime); + unsigned int flags = SCRIPT_VERIFY_NOCACHE | + (fStrictPayToScriptHash ? SCRIPT_VERIFY_P2SH : SCRIPT_VERIFY_NONE); + CBlockUndo blockundo; + CCheckQueueControl<CScriptCheck> control(fScriptChecks && nScriptCheckThreads ? &scriptcheckqueue : NULL); + int64 nStart = GetTimeMicros(); int64 nFees = 0; int nInputs = 0; unsigned int nSigOps = 0; + CDiskTxPos pos(pindex->GetBlockPos(), GetSizeOfCompactSize(vtx.size())); + std::vector<std::pair<uint256, CDiskTxPos> > vPos; + vPos.reserve(vtx.size()); for (unsigned int i=0; i<vtx.size(); i++) { @@ -1625,8 +1690,10 @@ bool CBlock::ConnectBlock(CBlockIndex* pindex, CCoinsViewCache &view, bool fJust nFees += tx.GetValueIn(view)-tx.GetValueOut(); - if (!tx.CheckInputs(view, CS_AFTER_CHECKPOINT, fStrictPayToScriptHash ? SCRIPT_VERIFY_P2SH : SCRIPT_VERIFY_NONE)) + std::vector<CScriptCheck> vChecks; + if (!tx.CheckInputs(view, fScriptChecks, flags, nScriptCheckThreads ? &vChecks : NULL)) return false; + control.Add(vChecks); } CTxUndo txundo; @@ -1635,6 +1702,8 @@ bool CBlock::ConnectBlock(CBlockIndex* pindex, CCoinsViewCache &view, bool fJust if (!tx.IsCoinBase()) blockundo.vtxundo.push_back(txundo); + vPos.push_back(std::make_pair(GetTxHash(i), pos)); + pos.nTxOffset += ::GetSerializeSize(tx, SER_DISK, CLIENT_VERSION); } int64 nTime = GetTimeMicros() - nStart; if (fBenchmark) @@ -1643,6 +1712,12 @@ bool CBlock::ConnectBlock(CBlockIndex* pindex, CCoinsViewCache &view, bool fJust if (vtx[0].GetValueOut() > GetBlockValue(pindex->nHeight, nFees)) return error("ConnectBlock() : coinbase pays too much (actual=%"PRI64d" vs limit=%"PRI64d")", vtx[0].GetValueOut(), GetBlockValue(pindex->nHeight, nFees)); + if (!control.Wait()) + return DoS(100, false); + int64 nTime2 = GetTimeMicros() - nStart; + if (fBenchmark) + printf("- Verify %u txins: %.2fms (%.3fms/txin)\n", nInputs - 1, 0.001 * nTime2, nInputs <= 1 ? 0 : 0.001 * nTime2 / (nInputs-1)); + if (fJustCheck) return true; @@ -1651,9 +1726,9 @@ bool CBlock::ConnectBlock(CBlockIndex* pindex, CCoinsViewCache &view, bool fJust { if (pindex->GetUndoPos().IsNull()) { CDiskBlockPos pos; - if (!FindUndoPos(pindex->nFile, pos, ::GetSerializeSize(blockundo, SER_DISK, CLIENT_VERSION) + 8)) + if (!FindUndoPos(pindex->nFile, pos, ::GetSerializeSize(blockundo, SER_DISK, CLIENT_VERSION) + 40)) return error("ConnectBlock() : FindUndoPos failed"); - if (!blockundo.WriteToDisk(pos)) + if (!blockundo.WriteToDisk(pos, pindex->pprev->GetBlockHash())) return error("ConnectBlock() : CBlockUndo::WriteToDisk failed"); // update nUndoPos in block index @@ -1668,6 +1743,9 @@ bool CBlock::ConnectBlock(CBlockIndex* pindex, CCoinsViewCache &view, bool fJust return error("ConnectBlock() : WriteBlockIndex failed"); } + if (fTxIndex) + pblocktree->WriteTxIndex(vPos); + // add this block to the view's block chain if (!view.SetBestBlock(pindex)) return false; @@ -1685,21 +1763,6 @@ bool SetBestChain(CBlockIndex* pindexNew) // Only when all have succeeded, we push it to pcoinsTip. CCoinsViewCache view(*pcoinsTip, true); - // special case for attaching the genesis block - // note that no ConnectBlock is called, so its coinbase output is non-spendable - if (pindexGenesisBlock == NULL && pindexNew->GetBlockHash() == hashGenesisBlock) - { - view.SetBestBlock(pindexNew); - if (!view.Flush()) - return false; - pindexGenesisBlock = pindexNew; - pindexBest = pindexNew; - hashBestChain = pindexNew->GetBlockHash(); - nBestHeight = pindexBest->nHeight; - bnBestChainWork = pindexNew->bnChainWork; - return true; - } - // Find the fork (typically, there is none) CBlockIndex* pfork = view.GetBestBlock(); CBlockIndex* plonger = pindexNew; @@ -1803,7 +1866,7 @@ bool SetBestChain(CBlockIndex* pindexNew) // Resurrect memory transactions that were in the disconnected branch BOOST_FOREACH(CTransaction& tx, vResurrect) - tx.AcceptToMemoryPool(); + tx.AcceptToMemoryPool(true, false); // Delete redundant memory transactions that are in the connected branch BOOST_FOREACH(CTransaction& tx, vDelete) { @@ -2245,6 +2308,160 @@ bool ProcessBlock(CNode* pfrom, CBlock* pblock, CDiskBlockPos *dbp) +CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter& filter) +{ + header = block.GetBlockHeader(); + + vector<bool> vMatch; + vector<uint256> vHashes; + + vMatch.reserve(block.vtx.size()); + vHashes.reserve(block.vtx.size()); + + for (unsigned int i = 0; i < block.vtx.size(); i++) + { + uint256 hash = block.vtx[i].GetHash(); + if (filter.IsRelevantAndUpdate(block.vtx[i], hash)) + { + vMatch.push_back(true); + vMatchedTxn.push_back(make_pair(i, hash)); + } + else + vMatch.push_back(false); + vHashes.push_back(hash); + } + + txn = CPartialMerkleTree(vHashes, vMatch); +} + + + + + + + + +uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid) { + if (height == 0) { + // hash at height 0 is the txids themself + return vTxid[pos]; + } else { + // calculate left hash + uint256 left = CalcHash(height-1, pos*2, vTxid), right; + // calculate right hash if not beyong the end of the array - copy left hash otherwise1 + if (pos*2+1 < CalcTreeWidth(height-1)) + right = CalcHash(height-1, pos*2+1, vTxid); + else + right = left; + // combine subhashes + return Hash(BEGIN(left), END(left), BEGIN(right), END(right)); + } +} + +void CPartialMerkleTree::TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) { + // determine whether this node is the parent of at least one matched txid + bool fParentOfMatch = false; + for (unsigned int p = pos << height; p < (pos+1) << height && p < nTransactions; p++) + fParentOfMatch |= vMatch[p]; + // store as flag bit + vBits.push_back(fParentOfMatch); + if (height==0 || !fParentOfMatch) { + // if at height 0, or nothing interesting below, store hash and stop + vHash.push_back(CalcHash(height, pos, vTxid)); + } else { + // otherwise, don't store any hash, but descend into the subtrees + TraverseAndBuild(height-1, pos*2, vTxid, vMatch); + if (pos*2+1 < CalcTreeWidth(height-1)) + TraverseAndBuild(height-1, pos*2+1, vTxid, vMatch); + } +} + +uint256 CPartialMerkleTree::TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch) { + if (nBitsUsed >= vBits.size()) { + // overflowed the bits array - failure + fBad = true; + return 0; + } + bool fParentOfMatch = vBits[nBitsUsed++]; + if (height==0 || !fParentOfMatch) { + // if at height 0, or nothing interesting below, use stored hash and do not descend + if (nHashUsed >= vHash.size()) { + // overflowed the hash array - failure + fBad = true; + return 0; + } + const uint256 &hash = vHash[nHashUsed++]; + if (height==0 && fParentOfMatch) // in case of height 0, we have a matched txid + vMatch.push_back(hash); + return hash; + } else { + // otherwise, descend into the subtrees to extract matched txids and hashes + uint256 left = TraverseAndExtract(height-1, pos*2, nBitsUsed, nHashUsed, vMatch), right; + if (pos*2+1 < CalcTreeWidth(height-1)) + right = TraverseAndExtract(height-1, pos*2+1, nBitsUsed, nHashUsed, vMatch); + else + right = left; + // and combine them before returning + return Hash(BEGIN(left), END(left), BEGIN(right), END(right)); + } +} + +CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) : nTransactions(vTxid.size()), fBad(false) { + // reset state + vBits.clear(); + vHash.clear(); + + // calculate height of tree + int nHeight = 0; + while (CalcTreeWidth(nHeight) > 1) + nHeight++; + + // traverse the partial tree + TraverseAndBuild(nHeight, 0, vTxid, vMatch); +} + +CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {} + +uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatch) { + vMatch.clear(); + // An empty set will not work + if (nTransactions == 0) + return 0; + // check for excessively high numbers of transactions + if (nTransactions > MAX_BLOCK_SIZE / 60) // 60 is the lower bound for the size of a serialized CTransaction + return 0; + // there can never be more hashes provided than one for every txid + if (vHash.size() > nTransactions) + return 0; + // there must be at least one bit per node in the partial tree, and at least one node per hash + if (vBits.size() < vHash.size()) + return 0; + // calculate height of tree + int nHeight = 0; + while (CalcTreeWidth(nHeight) > 1) + nHeight++; + // traverse the partial tree + unsigned int nBitsUsed = 0, nHashUsed = 0; + uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch); + // verify that no problems occured during the tree traversal + if (fBad) + return 0; + // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence) + if ((nBitsUsed+7)/8 != (vBits.size()+7)/8) + return 0; + // verify that all hashes were consumed + if (nHashUsed != vHash.size()) + return 0; + return hashMerkleRoot; +} + + + + + + + + bool CheckDiskSpace(uint64 nAdditionalBytes) { uint64 nFreeBytesAvailable = filesystem::space(GetDataDir()).available; @@ -2358,6 +2575,10 @@ bool static LoadBlockIndexDB() pblocktree->ReadReindexing(fReindexing); fReindex |= fReindexing; + // Check whether we have a transaction index + pblocktree->ReadFlag("txindex", fTxIndex); + printf("LoadBlockIndex(): transaction index %s\n", fTxIndex ? "enabled" : "disabled"); + // Load hashBestChain pointer to end of best chain pindexBest = pcoinsTip->GetBestBlock(); if (pindexBest == NULL) @@ -2377,36 +2598,77 @@ bool static LoadBlockIndexDB() BlockHashStr(hashBestChain).c_str(), nBestHeight, DateTimeStrFormat("%Y-%m-%d %H:%M:%S", pindexBest->GetBlockTime()).c_str()); + return true; +} + +bool VerifyDB() { + if (pindexBest == NULL || pindexBest->pprev == NULL) + return true; + // Verify blocks in the best chain - int nCheckLevel = GetArg("-checklevel", 1); - int nCheckDepth = GetArg( "-checkblocks", 2500); + int nCheckLevel = GetArg("-checklevel", 3); + int nCheckDepth = GetArg( "-checkblocks", 288); if (nCheckDepth == 0) nCheckDepth = 1000000000; // suffices until the year 19000 if (nCheckDepth > nBestHeight) nCheckDepth = nBestHeight; + nCheckLevel = std::max(0, std::min(4, nCheckLevel)); printf("Verifying last %i blocks at level %i\n", nCheckDepth, nCheckLevel); - CBlockIndex* pindexFork = NULL; + CCoinsViewCache coins(*pcoinsTip, true); + CBlockIndex* pindexState = pindexBest; + CBlockIndex* pindexFailure = NULL; + int nGoodTransactions = 0; for (CBlockIndex* pindex = pindexBest; pindex && pindex->pprev; pindex = pindex->pprev) { if (fRequestShutdown || pindex->nHeight < nBestHeight-nCheckDepth) break; CBlock block; + // check level 0: read from disk if (!block.ReadFromDisk(pindex)) - return error("LoadBlockIndex() : block.ReadFromDisk failed"); + return error("VerifyDB() : *** block.ReadFromDisk failed at %d, hash=%s", pindex->nHeight, pindex->GetBlockHash().ToString().c_str()); // check level 1: verify block validity - if (nCheckLevel>0 && !block.CheckBlock()) - { - printf("LoadBlockIndex() : *** found bad block at %d, hash=%s\n", pindex->nHeight, pindex->GetBlockHash().ToString().c_str()); - pindexFork = pindex->pprev; + if (nCheckLevel >= 1 && !block.CheckBlock()) + return error("VerifyDB() : *** found bad block at %d, hash=%s\n", pindex->nHeight, pindex->GetBlockHash().ToString().c_str()); + // check level 2: verify undo validity + if (nCheckLevel >= 2 && pindex) { + CBlockUndo undo; + CDiskBlockPos pos = pindex->GetUndoPos(); + if (!pos.IsNull()) { + if (!undo.ReadFromDisk(pos, pindex->pprev->GetBlockHash())) + return error("VerifyDB() : *** found bad undo data at %d, hash=%s\n", pindex->nHeight, pindex->GetBlockHash().ToString().c_str()); + } + } + // check level 3: check for inconsistencies during memory-only disconnect of tip blocks + if (nCheckLevel >= 3 && pindex == pindexState && (coins.GetCacheSize() + pcoinsTip->GetCacheSize()) <= 2*nCoinCacheSize + 32000) { + bool fClean = true; + if (!block.DisconnectBlock(pindex, coins, &fClean)) + return error("VerifyDB() : *** irrecoverable inconsistency in block data at %d, hash=%s", pindex->nHeight, pindex->GetBlockHash().ToString().c_str()); + pindexState = pindex->pprev; + if (!fClean) { + nGoodTransactions = 0; + pindexFailure = pindex; + } else + nGoodTransactions += block.vtx.size(); } - // TODO: stronger verifications } - if (pindexFork && !fRequestShutdown) - { - // TODO: reorg back - return error("LoadBlockIndex(): chain database corrupted"); + if (pindexFailure) + return error("VerifyDB() : *** coin database inconsistencies found (last %i blocks, %i good transactions before that)\n", pindexBest->nHeight - pindexFailure->nHeight + 1, nGoodTransactions); + + // check level 4: try reconnecting blocks + if (nCheckLevel >= 4) { + CBlockIndex *pindex = pindexState; + while (pindex != pindexBest && !fRequestShutdown) { + pindex = pindex->pnext; + CBlock block; + if (!block.ReadFromDisk(pindex)) + return error("VerifyDB() : *** block.ReadFromDisk failed at %d, hash=%s", pindex->nHeight, pindex->GetBlockHash().ToString().c_str()); + if (!block.ConnectBlock(pindex, coins)) + return error("VerifyDB() : *** found unconnectable block at %d, hash=%s", pindex->nHeight, pindex->GetBlockHash().ToString().c_str()); + } } + printf("No coin database inconsistencies in last %i blocks (%i transactions)\n", pindexBest->nHeight - pindexState->nHeight, nGoodTransactions); + return true; } @@ -2421,13 +2683,10 @@ bool LoadBlockIndex() hashGenesisBlock = uint256("000000000933ea01ad0ee984209779baaec3ced90fa3f408719526f8d77f4943"); } - if (fReindex) - return true; - // // Load block index from databases // - if (!LoadBlockIndexDB()) + if (!fReindex && !LoadBlockIndexDB()) return false; // @@ -2435,6 +2694,13 @@ bool LoadBlockIndex() // if (mapBlockIndex.empty()) { + fTxIndex = GetBoolArg("-txindex", false); + pblocktree->WriteFlag("txindex", fTxIndex); + printf("Initializing databases...\n"); + + if (fReindex) + return true; + // Genesis Block: // CBlock(hash=000000000019d6, ver=1, hashPrevBlock=00000000000000, hashMerkleRoot=4a5e1e, nTime=1231006505, nBits=1d00ffff, nNonce=2083236893, vtx=1) // CTransaction(hash=4a5e1e, ver=1, vin.size=1, vout.size=1, nLockTime=0) @@ -2780,6 +3046,10 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) vRecv >> pfrom->strSubVer; if (!vRecv.empty()) vRecv >> pfrom->nStartingHeight; + if (!vRecv.empty()) + vRecv >> pfrom->fRelayTxes; // set to true after we get the first filter* message + else + pfrom->fRelayTxes = true; if (pfrom->fInbound && addrMe.IsRoutable()) { @@ -3003,6 +3273,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) if (fDebugNet || (vInv.size() != 1)) printf("received getdata (%"PRIszu" invsz)\n", vInv.size()); + vector<CInv> vNotFound; BOOST_FOREACH(const CInv& inv, vInv) { if (fShutdown) @@ -3010,7 +3281,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) if (fDebugNet || (vInv.size() == 1)) printf("received getdata for: %s\n", inv.ToString().c_str()); - if (inv.type == MSG_BLOCK) + if (inv.type == MSG_BLOCK || inv.type == MSG_FILTERED_BLOCK) { // Send block from disk map<uint256, CBlockIndex*>::iterator mi = mapBlockIndex.find(inv.hash); @@ -3018,7 +3289,29 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) { CBlock block; block.ReadFromDisk((*mi).second); - pfrom->PushMessage("block", block); + if (inv.type == MSG_BLOCK) + pfrom->PushMessage("block", block); + else // MSG_FILTERED_BLOCK) + { + LOCK(pfrom->cs_filter); + if (pfrom->pfilter) + { + CMerkleBlock merkleBlock(block, *pfrom->pfilter); + pfrom->PushMessage("merkleblock", merkleBlock); + // CMerkleBlock just contains hashes, so also push any transactions in the block the client did not see + // This avoids hurting performance by pointlessly requiring a round-trip + // Note that there is currently no way for a node to request any single transactions we didnt send here - + // they must either disconnect and retry or request the full block. + // Thus, the protocol spec specified allows for us to provide duplicate txn here, + // however we MUST always provide at least what the remote peer needs + typedef std::pair<unsigned int, uint256> PairType; + BOOST_FOREACH(PairType& pair, merkleBlock.vMatchedTxn) + if (!pfrom->setInventoryKnown.count(CInv(MSG_TX, pair.second))) + pfrom->PushMessage("tx", block.vtx[pair.first]); + } + // else + // no response + } // Trigger them to send a getblocks request for the next batch of inventory if (inv.hash == pfrom->hashContinue) @@ -3053,12 +3346,27 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) ss.reserve(1000); ss << tx; pfrom->PushMessage("tx", ss); + pushed = true; } } + if (!pushed) { + vNotFound.push_back(inv); + } } - // Track requests for our stuff + // Track requests for our stuff. Inventory(inv.hash); + + if (!vNotFound.empty()) { + // Let the peer know that we didn't find what it asked for, so it doesn't + // have to wait around forever. Currently only SPV clients actually care + // about this message: it's needed when they are recursively walking the + // dependencies of relevant unconfirmed transactions. SPV clients want to + // do that because they want to know about (and store and rebroadcast and + // risk analyze) the dependencies of transactions relevant to them, without + // having to download the entire memory pool. + pfrom->PushMessage("notfound", vNotFound); + } } } @@ -3146,10 +3454,9 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) pfrom->AddInventoryKnown(inv); bool fMissingInputs = false; - if (tx.AcceptToMemoryPool(true, &fMissingInputs)) + if (tx.AcceptToMemoryPool(true, true, &fMissingInputs)) { - SyncWithWallets(inv.hash, tx, NULL, true); - RelayMessage(inv, vMsg); + RelayTransaction(tx, inv.hash, vMsg); mapAlreadyAskedFor.erase(inv); vWorkQueue.push_back(inv.hash); vEraseQueue.push_back(inv.hash); @@ -3168,20 +3475,19 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) CInv inv(MSG_TX, tx.GetHash()); bool fMissingInputs2 = false; - if (tx.AcceptToMemoryPool(true, &fMissingInputs2)) + if (tx.AcceptToMemoryPool(true, true, &fMissingInputs2)) { printf(" accepted orphan tx %s\n", inv.hash.ToString().substr(0,10).c_str()); - SyncWithWallets(inv.hash, tx, NULL, true); - RelayMessage(inv, vMsg); + RelayTransaction(tx, inv.hash, vMsg); mapAlreadyAskedFor.erase(inv); vWorkQueue.push_back(inv.hash); vEraseQueue.push_back(inv.hash); } else if (!fMissingInputs2) { - // invalid orphan + // invalid or too-little-fee orphan vEraseQueue.push_back(inv.hash); - printf(" removed invalid orphan tx %s\n", inv.hash.ToString().substr(0,10).c_str()); + printf(" removed orphan tx %s\n", inv.hash.ToString().substr(0,10).c_str()); } } } @@ -3231,13 +3537,16 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) else if (strCommand == "mempool") { std::vector<uint256> vtxid; + LOCK2(mempool.cs, pfrom->cs_filter); mempool.queryHashes(vtxid); vector<CInv> vInv; - for (unsigned int i = 0; i < vtxid.size(); i++) { - CInv inv(MSG_TX, vtxid[i]); - vInv.push_back(inv); - if (i == (MAX_INV_SZ - 1)) - break; + BOOST_FOREACH(uint256& hash, vtxid) { + CInv inv(MSG_TX, hash); + if ((pfrom->pfilter && pfrom->pfilter->IsRelevantAndUpdate(mempool.lookup(hash), hash)) || + (!pfrom->pfilter)) + vInv.push_back(inv); + if (vInv.size() == MAX_INV_SZ) + break; } if (vInv.size() > 0) pfrom->PushMessage("inv", vInv); @@ -3297,6 +3606,53 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) } + else if (strCommand == "filterload") + { + CBloomFilter filter; + vRecv >> filter; + + if (!filter.IsWithinSizeConstraints()) + // There is no excuse for sending a too-large filter + pfrom->Misbehaving(100); + else + { + LOCK(pfrom->cs_filter); + delete pfrom->pfilter; + pfrom->pfilter = new CBloomFilter(filter); + } + pfrom->fRelayTxes = true; + } + + + else if (strCommand == "filteradd") + { + vector<unsigned char> vData; + vRecv >> vData; + + // Nodes must NEVER send a data item > 520 bytes (the max size for a script data object, + // and thus, the maximum size any matched object can have) in a filteradd message + if (vData.size() > MAX_SCRIPT_ELEMENT_SIZE) + { + pfrom->Misbehaving(100); + } else { + LOCK(pfrom->cs_filter); + if (pfrom->pfilter) + pfrom->pfilter->insert(vData); + else + pfrom->Misbehaving(100); + } + } + + + else if (strCommand == "filterclear") + { + LOCK(pfrom->cs_filter); + delete pfrom->pfilter; + pfrom->pfilter = NULL; + pfrom->fRelayTxes = true; + } + + else { // Ignore unknown commands for extensibility @@ -3732,12 +4088,13 @@ public: } }; -CBlock* CreateNewBlock(CReserveKey& reservekey) +CBlockTemplate* CreateNewBlock(CReserveKey& reservekey) { // Create new block - auto_ptr<CBlock> pblock(new CBlock()); - if (!pblock.get()) + auto_ptr<CBlockTemplate> pblocktemplate(new CBlockTemplate()); + if(!pblocktemplate.get()) return NULL; + CBlock *pblock = &pblocktemplate->block; // pointer for convenience // Create coinbase tx CTransaction txNew; @@ -3748,6 +4105,8 @@ CBlock* CreateNewBlock(CReserveKey& reservekey) // Add our coinbase tx as first transaction pblock->vtx.push_back(txNew); + pblocktemplate->vTxFees.push_back(-1); // updated at end + pblocktemplate->vTxSigOps.push_back(-1); // updated at end // Largest block you're willing to create: unsigned int nBlockMaxSize = GetArg("-blockmaxsize", MAX_BLOCK_SIZE_GEN/2); @@ -3912,7 +4271,7 @@ CBlock* CreateNewBlock(CReserveKey& reservekey) if (nBlockSigOps + nTxSigOps >= MAX_BLOCK_SIGOPS) continue; - if (!tx.CheckInputs(viewTemp, CS_ALWAYS, SCRIPT_VERIFY_P2SH)) + if (!tx.CheckInputs(viewTemp, true, SCRIPT_VERIFY_P2SH)) continue; CTxUndo txundo; @@ -3925,6 +4284,8 @@ CBlock* CreateNewBlock(CReserveKey& reservekey) // Added pblock->vtx.push_back(tx); + pblocktemplate->vTxFees.push_back(nTxFees); + pblocktemplate->vTxSigOps.push_back(nTxSigOps); nBlockSize += nTxSize; ++nBlockTx; nBlockSigOps += nTxSigOps; @@ -3959,13 +4320,15 @@ CBlock* CreateNewBlock(CReserveKey& reservekey) printf("CreateNewBlock(): total size %"PRI64u"\n", nBlockSize); pblock->vtx[0].vout[0].nValue = GetBlockValue(pindexPrev->nHeight+1, nFees); + pblocktemplate->vTxFees[0] = -nFees; // Fill in header pblock->hashPrevBlock = pindexPrev->GetBlockHash(); pblock->UpdateTime(pindexPrev); - pblock->nBits = GetNextWorkRequired(pindexPrev, pblock.get()); + pblock->nBits = GetNextWorkRequired(pindexPrev, pblock); pblock->nNonce = 0; pblock->vtx[0].vin[0].scriptSig = CScript() << OP_0 << OP_0; + pblocktemplate->vTxSigOps[0] = pblock->vtx[0].GetLegacySigOpCount(); CBlockIndex indexDummy(*pblock); indexDummy.pprev = pindexPrev; @@ -3975,7 +4338,7 @@ CBlock* CreateNewBlock(CReserveKey& reservekey) throw std::runtime_error("CreateNewBlock() : ConnectBlock failed"); } - return pblock.release(); + return pblocktemplate.release(); } @@ -4118,10 +4481,11 @@ void static BitcoinMiner(CWallet *pwallet) unsigned int nTransactionsUpdatedLast = nTransactionsUpdated; CBlockIndex* pindexPrev = pindexBest; - auto_ptr<CBlock> pblock(CreateNewBlock(reservekey)); - if (!pblock.get()) + auto_ptr<CBlockTemplate> pblocktemplate(CreateNewBlock(reservekey)); + if (!pblocktemplate.get()) return; - IncrementExtraNonce(pblock.get(), pindexPrev, nExtraNonce); + CBlock *pblock = &pblocktemplate->block; + IncrementExtraNonce(pblock, pindexPrev, nExtraNonce); printf("Running BitcoinMiner with %"PRIszu" transactions in block (%u bytes)\n", pblock->vtx.size(), ::GetSerializeSize(*pblock, SER_NETWORK, PROTOCOL_VERSION)); @@ -4134,7 +4498,7 @@ void static BitcoinMiner(CWallet *pwallet) char pdatabuf[128+16]; char* pdata = alignup<16>(pdatabuf); char phash1buf[64+16]; char* phash1 = alignup<16>(phash1buf); - FormatHashBuffers(pblock.get(), pmidstate, pdata, phash1); + FormatHashBuffers(pblock, pmidstate, pdata, phash1); unsigned int& nBlockTime = *(unsigned int*)(pdata + 64 + 4); unsigned int& nBlockBits = *(unsigned int*)(pdata + 64 + 8); @@ -4170,7 +4534,7 @@ void static BitcoinMiner(CWallet *pwallet) assert(hash == pblock->GetHash()); SetThreadPriority(THREAD_PRIORITY_NORMAL); - CheckWork(pblock.get(), *pwalletMain, reservekey); + CheckWork(pblock, *pwalletMain, reservekey); SetThreadPriority(THREAD_PRIORITY_LOWEST); break; } |