diff options
Diffstat (limited to 'src/main.cpp')
-rw-r--r-- | src/main.cpp | 260 |
1 files changed, 220 insertions, 40 deletions
diff --git a/src/main.cpp b/src/main.cpp index e06c519ee2..04d9523e26 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -7,6 +7,7 @@ #include "addrman.h" #include "alert.h" +#include "bloom.h" #include "chainparams.h" #include "checkpoints.h" #include "checkqueue.h" @@ -72,6 +73,7 @@ const string strMessageMagic = "Bitcoin Signed Message:\n"; // Internal stuff namespace { + struct CBlockIndexWorkComparator { bool operator()(CBlockIndex *pa, CBlockIndex *pb) { @@ -120,7 +122,12 @@ namespace { }; map<uint256, pair<NodeId, list<QueuedBlock>::iterator> > mapBlocksInFlight; map<uint256, pair<NodeId, list<uint256>::iterator> > mapBlocksToDownload; -} + +} // anon namespace + +// Forward reference functions defined here: +static const unsigned int MAX_DOUBLESPEND_BLOOM = 1000; +static void RelayDoubleSpend(const COutPoint& outPoint, const CTransaction& doubleSpend, bool fInBlock, CBloomFilter& filter); ////////////////////////////////////////////////////////////////////////////// // @@ -130,6 +137,7 @@ namespace { // These functions dispatch to one or all registered wallets namespace { + struct CMainSignals { // Notifies listeners of updated transaction data (transaction, and optionally the block it is found in. boost::signals2::signal<void (const CTransaction &, const CBlock *)> SyncTransaction; @@ -143,9 +151,25 @@ struct CMainSignals { boost::signals2::signal<void (const uint256 &)> Inventory; // Tells listeners to broadcast their data. boost::signals2::signal<void ()> Broadcast; + // Notifies listeners of detection of a double-spent transaction. Arguments are outpoint that is + // double-spent, first transaction seen, double-spend transaction, and whether the second double-spend + // transaction was first seen in a block. + // Note: only notifies if the previous transaction is in the memory pool; if previous transction was in a block, + // then the double-spend simply fails when we try to lookup the inputs in the current UTXO set. + boost::signals2::signal<void (const COutPoint&, const CTransaction&, bool)> DetectedDoubleSpend; } g_signals; + +} // anon namespace + +void RegisterInternalSignals() { + static CBloomFilter doubleSpendFilter; + seed_insecure_rand(); + doubleSpendFilter = CBloomFilter(MAX_DOUBLESPEND_BLOOM, 0.01, insecure_rand(), BLOOM_UPDATE_NONE); + + g_signals.DetectedDoubleSpend.connect(boost::bind(RelayDoubleSpend, _1, _2, _3, doubleSpendFilter)); } + void RegisterWallet(CWalletInterface* pwalletIn) { g_signals.SyncTransaction.connect(boost::bind(&CWalletInterface::SyncTransaction, pwalletIn, _1, _2)); g_signals.EraseTransaction.connect(boost::bind(&CWalletInterface::EraseFromWallet, pwalletIn, _1)); @@ -203,6 +227,10 @@ struct CNodeState { std::string name; // List of asynchronously-determined block rejections to notify this peer about. std::vector<CBlockReject> rejects; + // The best known block we know this peer has announced. + CBlockIndex *pindexBestKnownBlock; + // The hash of the last unknown block this peer has announced. + uint256 hashLastUnknownBlock; list<QueuedBlock> vBlocksInFlight; int nBlocksInFlight; list<uint256> vBlocksToDownload; @@ -213,6 +241,8 @@ struct CNodeState { CNodeState() { nMisbehavior = 0; fShouldBan = false; + pindexBestKnownBlock = NULL; + hashLastUnknownBlock = uint256(0); nBlocksToDownload = 0; nBlocksInFlight = 0; nLastBlockReceive = 0; @@ -274,7 +304,6 @@ void MarkBlockAsReceived(const uint256 &hash, NodeId nodeFrom = -1) { state->nLastBlockReceive = GetTimeMicros(); mapBlocksInFlight.erase(itInFlight); } - } // Requires cs_main. @@ -310,14 +339,48 @@ void MarkBlockAsInFlight(NodeId nodeid, const uint256 &hash) { mapBlocksInFlight[hash] = std::make_pair(nodeid, it); } +/** Check whether the last unknown block a peer advertized is not yet known. */ +void ProcessBlockAvailability(NodeId nodeid) { + CNodeState *state = State(nodeid); + assert(state != NULL); + + if (state->hashLastUnknownBlock != 0) { + map<uint256, CBlockIndex*>::iterator itOld = mapBlockIndex.find(state->hashLastUnknownBlock); + if (itOld != mapBlockIndex.end() && itOld->second->nChainWork > 0) { + if (state->pindexBestKnownBlock == NULL || itOld->second->nChainWork >= state->pindexBestKnownBlock->nChainWork) + state->pindexBestKnownBlock = itOld->second; + state->hashLastUnknownBlock = uint256(0); + } + } } +/** Update tracking information about which blocks a peer is assumed to have. */ +void UpdateBlockAvailability(NodeId nodeid, const uint256 &hash) { + CNodeState *state = State(nodeid); + assert(state != NULL); + + ProcessBlockAvailability(nodeid); + + map<uint256, CBlockIndex*>::iterator it = mapBlockIndex.find(hash); + if (it != mapBlockIndex.end() && it->second->nChainWork > 0) { + // An actually better block was announced. + if (state->pindexBestKnownBlock == NULL || it->second->nChainWork >= state->pindexBestKnownBlock->nChainWork) + state->pindexBestKnownBlock = it->second; + } else { + // An unknown block was announced; just assume that the latest one is the best one. + state->hashLastUnknownBlock = hash; + } +} + +} // anon namespace + bool GetNodeStateStats(NodeId nodeid, CNodeStateStats &stats) { LOCK(cs_main); CNodeState *state = State(nodeid); if (state == NULL) return false; stats.nMisbehavior = state->nMisbehavior; + stats.nSyncHeight = state->pindexBestKnownBlock ? state->pindexBestKnownBlock->nHeight : -1; return true; } @@ -371,8 +434,11 @@ CBlockLocator CChain::GetLocator(const CBlockIndex *pindex) const { break; // Exponentially larger steps back, plus the genesis block. int nHeight = std::max(pindex->nHeight - nStep, 0); + // Jump back quickly to the same height as the chain. + if (pindex->nHeight > nHeight) + pindex = pindex->GetAncestor(nHeight); // In case pindex is not in this chain, iterate pindex->pprev to find blocks. - while (pindex->nHeight > nHeight && !Contains(pindex)) + while (!Contains(pindex)) pindex = pindex->pprev; // If pindex is in this chain, use direct height-based access. if (pindex->nHeight > nHeight) @@ -399,6 +465,8 @@ CBlockIndex *CChain::FindFork(const CBlockLocator &locator) const { } CBlockIndex *CChain::FindFork(CBlockIndex *pindex) const { + if (pindex->nHeight > Height()) + pindex = pindex->GetAncestor(Height()); while (pindex && !Contains(pindex)) pindex = pindex->pprev; return pindex; @@ -488,7 +556,7 @@ bool IsStandardTx(const CTransaction& tx, string& reason) // Treat non-final transactions as non-standard to prevent a specific type // of double-spend attack, as well as DoS attacks. (if the transaction // can't be mined, the attacker isn't expending resources broadcasting it) - // Basically we don't want to propagate transactions that can't included in + // Basically we don't want to propagate transactions that can't be included in // the next block. // // However, IsFinalTx() is confusing... Without arguments, it uses @@ -521,7 +589,7 @@ bool IsStandardTx(const CTransaction& tx, string& reason) { // Biggest 'standard' txin is a 15-of-15 P2SH multisig with compressed // keys. (remember the 520 byte limit on redeemScript size) That works - // out to a (15*(33+1))+3=513 byte redeemScript, 513+1+15*(73+1)=1624 + // out to a (15*(33+1))+3=513 byte redeemScript, 513+1+15*(73+1)+3=1627 // bytes of scriptSig, which we round off to 1650 bytes for some minor // future-proofing. That's also enough to spend a 20-of-20 // CHECKMULTISIG scriptPubKey, though such a scriptPubKey is not @@ -583,15 +651,13 @@ bool IsFinalTx(const CTransaction &tx, int nBlockHeight, int64_t nBlockTime) } // -// Check transaction inputs, and make sure any -// pay-to-script-hash transactions are evaluating IsStandard scripts +// Check transaction inputs to mitigate two +// potential denial-of-service attacks: // -// Why bother? To avoid denial-of-service attacks; an attacker -// can submit a standard HASH... OP_EQUAL transaction, -// which will get accepted into blocks. The redemption -// script can be anything; an attacker could use a very -// expensive-to-check-upon-redemption script like: -// DUP CHECKSIG DROP ... repeated 100 times... OP_1 +// 1. scriptSigs with extra data stuffed into them, +// not consumed by scriptPubKey (or P2SH script) +// 2. P2SH scripts with a crazy number of expensive +// CHECKSIG/CHECKMULTISIG operations // bool AreInputsStandard(const CTransaction& tx, CCoinsViewCache& mapInputs) { @@ -615,8 +681,9 @@ bool AreInputsStandard(const CTransaction& tx, CCoinsViewCache& mapInputs) // Transactions with extra stuff in their scriptSigs are // non-standard. Note that this EvalScript() call will // be quick, because if there are any operations - // beside "push data" in the scriptSig the - // IsStandard() call returns false + // beside "push data" in the scriptSig + // IsStandard() will have already returned false + // and this method isn't called. vector<vector<unsigned char> > stack; if (!EvalScript(stack, tx.vin[i].scriptSig, tx, i, false, 0)) return false; @@ -628,16 +695,20 @@ bool AreInputsStandard(const CTransaction& tx, CCoinsViewCache& mapInputs) CScript subscript(stack.back().begin(), stack.back().end()); vector<vector<unsigned char> > vSolutions2; txnouttype whichType2; - if (!Solver(subscript, whichType2, vSolutions2)) - return false; - if (whichType2 == TX_SCRIPTHASH) - return false; - - int tmpExpected; - tmpExpected = ScriptSigArgsExpected(whichType2, vSolutions2); - if (tmpExpected < 0) - return false; - nArgsExpected += tmpExpected; + if (Solver(subscript, whichType2, vSolutions2)) + { + int tmpExpected = ScriptSigArgsExpected(whichType2, vSolutions2); + if (tmpExpected < 0) + return false; + nArgsExpected += tmpExpected; + } + else + { + // Any other Script with less than 15 sigops OK: + unsigned int sigops = subscript.GetSigOpCount(true); + // ... extra data left on the stack after execution is OK, too: + return (sigops <= MAX_P2SH_SIGOPS); + } } if (stack.size() != (unsigned int)nArgsExpected) @@ -821,6 +892,21 @@ int64_t GetMinFee(const CTransaction& tx, unsigned int nBytes, bool fAllowFree, return nMinFee; } +// Exponentially limit the rate of nSize flow to nLimit. nLimit unit is thousands-per-minute. +bool RateLimitExceeded(double& dCount, int64_t& nLastTime, int64_t nLimit, unsigned int nSize) +{ + static CCriticalSection csLimiter; + int64_t nNow = GetTime(); + + LOCK(csLimiter); + + dCount *= pow(1.0 - 1.0/600.0, (double)(nNow - nLastTime)); + nLastTime = nNow; + if (dCount >= nLimit*10*1000) + return true; + dCount += nSize; + return false; +} bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransaction &tx, bool fLimitFree, bool* pfMissingInputs, bool fRejectInsaneFee) @@ -855,9 +941,10 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa for (unsigned int i = 0; i < tx.vin.size(); i++) { COutPoint outpoint = tx.vin[i].prevout; - if (pool.mapNextTx.count(outpoint)) + // Does tx conflict with a member of the pool, and is it not equivalent to that member? + if (pool.mapNextTx.count(outpoint) && !tx.IsEquivalentTo(*pool.mapNextTx[outpoint].ptx)) { - // Disable replacement feature for now + g_signals.DetectedDoubleSpend(outpoint, tx, false); return false; } } @@ -929,23 +1016,15 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa // be annoying or make others' transactions take longer to confirm. if (fLimitFree && nFees < CTransaction::minRelayTxFee.GetFee(nSize)) { - static CCriticalSection csFreeLimiter; static double dFreeCount; - static int64_t nLastTime; - int64_t nNow = GetTime(); + static int64_t nLastFreeTime; + static int64_t nFreeLimit = GetArg("-limitfreerelay", 15); - LOCK(csFreeLimiter); - - // 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) + if (RateLimitExceeded(dFreeCount, nLastFreeTime, nFreeLimit, nSize)) return state.DoS(0, error("AcceptToMemoryPool : free transaction rejected by rate limiter"), REJECT_INSUFFICIENTFEE, "insufficient priority"); + LogPrint("mempool", "Rate limit dFreeCount: %g => %g\n", dFreeCount, dFreeCount+nSize); - dFreeCount += nSize; } if (fRejectInsaneFee && nFees > CTransaction::minRelayTxFee.GetFee(nSize) * 10000) @@ -968,6 +1047,48 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa return true; } +static void RelayDoubleSpend(const COutPoint& outPoint, const CTransaction& doubleSpend, bool fInBlock, CBloomFilter& filter) +{ + // Relaying double-spend attempts to our peers lets them detect when + // somebody might be trying to cheat them. However, blindly relaying + // every double-spend across the entire network gives attackers + // a denial-of-service attack: just generate a stream of double-spends + // re-spending the same (limited) set of outpoints owned by the attacker. + // So, we use a bloom filter and only relay (at most) the first double + // spend for each outpoint. False-positives ("we have already relayed") + // are OK, because if the peer doesn't hear about the double-spend + // from us they are very likely to hear about it from another peer, since + // each peer uses a different, randomized bloom filter. + + if (fInBlock || filter.contains(outPoint)) return; + + // Apply an independent rate limit to double-spend relays + static double dRespendCount; + static int64_t nLastRespendTime; + static int64_t nRespendLimit = GetArg("-limitrespendrelay", 100); + unsigned int nSize = ::GetSerializeSize(doubleSpend, SER_NETWORK, PROTOCOL_VERSION); + + if (RateLimitExceeded(dRespendCount, nLastRespendTime, nRespendLimit, nSize)) + { + LogPrint("mempool", "Double-spend relay rejected by rate limiter\n"); + return; + } + + LogPrint("mempool", "Rate limit dRespendCount: %g => %g\n", dRespendCount, dRespendCount+nSize); + + // Clear the filter on average every MAX_DOUBLE_SPEND_BLOOM + // insertions + if (insecure_rand()%MAX_DOUBLESPEND_BLOOM == 0) + filter.clear(); + + filter.insert(outPoint); + + RelayTransaction(doubleSpend); + + // Share conflict with wallet + g_signals.SyncTransaction(doubleSpend, NULL); +} + int CMerkleTx::GetDepthInMainChainINTERNAL(CBlockIndex* &pindexRet) const { @@ -2105,6 +2226,7 @@ CBlockIndex* AddToBlockIndex(CBlockHeader& block) { pindexNew->pprev = (*miPrev).second; pindexNew->nHeight = pindexNew->pprev->nHeight + 1; + pindexNew->BuildSkip(); } pindexNew->nChainWork = (pindexNew->pprev ? pindexNew->pprev->nChainWork : 0) + pindexNew->GetBlockWork(); pindexNew->RaiseValidity(BLOCK_VALID_TREE); @@ -2462,6 +2584,55 @@ bool CBlockIndex::IsSuperMajority(int minVersion, const CBlockIndex* pstart, uns return (nFound >= nRequired); } +/** Turn the lowest '1' bit in the binary representation of a number into a '0'. */ +int static inline InvertLowestOne(int n) { return n & (n - 1); } + +/** Compute what height to jump back to with the CBlockIndex::pskip pointer. */ +int static inline GetSkipHeight(int height) { + if (height < 2) + return 0; + + // Determine which height to jump back to. Any number strictly lower than height is acceptable, + // but the following expression seems to perform well in simulations (max 110 steps to go back + // up to 2**18 blocks). + return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height); +} + +CBlockIndex* CBlockIndex::GetAncestor(int height) +{ + if (height > nHeight || height < 0) + return NULL; + + CBlockIndex* pindexWalk = this; + int heightWalk = nHeight; + while (heightWalk > height) { + int heightSkip = GetSkipHeight(heightWalk); + int heightSkipPrev = GetSkipHeight(heightWalk - 1); + if (heightSkip == height || + (heightSkip > height && !(heightSkipPrev < heightSkip - 2 && + heightSkipPrev >= height))) { + // Only follow pskip if pprev->pskip isn't better than pskip->pprev. + pindexWalk = pindexWalk->pskip; + heightWalk = heightSkip; + } else { + pindexWalk = pindexWalk->pprev; + heightWalk--; + } + } + return pindexWalk; +} + +const CBlockIndex* CBlockIndex::GetAncestor(int height) const +{ + return const_cast<CBlockIndex*>(this)->GetAncestor(height); +} + +void CBlockIndex::BuildSkip() +{ + if (pprev) + pskip = pprev->GetAncestor(GetSkipHeight(nHeight)); +} + void PushGetBlocks(CNode* pnode, CBlockIndex* pindexBegin, uint256 hashEnd) { AssertLockHeld(cs_main); @@ -2812,6 +2983,8 @@ bool static LoadBlockIndexDB() setBlockIndexValid.insert(pindex); if (pindex->nStatus & BLOCK_FAILED_MASK && (!pindexBestInvalid || pindex->nChainWork > pindexBestInvalid->nChainWork)) pindexBestInvalid = pindex; + if (pindex->pprev) + pindex->BuildSkip(); } // Load block file info @@ -3607,6 +3780,9 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) PushGetBlocks(pfrom, chainActive.Tip(), GetOrphanRoot(inv.hash)); } + if (inv.type == MSG_BLOCK) + UpdateBlockAvailability(pfrom->GetId(), inv.hash); + // Track requests for our stuff g_signals.Inventory(inv.hash); } @@ -3649,7 +3825,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) if (pindex) pindex = chainActive.Next(pindex); int nLimit = 500; - LogPrint("net", "getblocks %d to %s limit %d\n", (pindex ? pindex->nHeight : -1), hashStop.ToString(), nLimit); + LogPrint("net", "getblocks %d to %s limit %d\n", (pindex ? pindex->nHeight : -1), hashStop==uint256(0) ? "end" : hashStop.ToString(), nLimit); for (; pindex; pindex = chainActive.Next(pindex)) { if (pindex->GetBlockHash() == hashStop) @@ -4038,6 +4214,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) else { // Ignore unknown commands for extensibility + LogPrint("net", "Unknown command \"%s\" from peer=%d\n", SanitizeString(strCommand), pfrom->id); } @@ -4352,6 +4529,9 @@ bool SendMessages(CNode* pto, bool fSendTrickle) pto->fDisconnect = true; } + // Update knowledge of peer's block availability. + ProcessBlockAvailability(pto->GetId()); + // // Message: getdata (blocks) // |