From c3def40293a89307d296ff66653b5927165c3c18 Mon Sep 17 00:00:00 2001 From: Gavin Andresen Date: Tue, 15 May 2012 15:53:30 -0400 Subject: Optimize orphan transaction handling Changes suggested by Sergio Demian Lerner to help prevent potential DoS attacks. --- src/main.cpp | 46 ++++++++++++++++++++++++++++++---------------- 1 file changed, 30 insertions(+), 16 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 0f45b2e16b..b7067b2092 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -45,7 +45,7 @@ map mapOrphanBlocks; multimap mapOrphanBlocksByPrev; map mapOrphanTransactions; -multimap mapOrphanTransactionsByPrev; +map > mapOrphanTransactionsByPrev; double dHashesPerSec; @@ -160,17 +160,37 @@ void static ResendWalletTransactions() // mapOrphanTransactions // -void AddOrphanTx(const CDataStream& vMsg) +bool AddOrphanTx(const CDataStream& vMsg) { CTransaction tx; CDataStream(vMsg) >> tx; uint256 hash = tx.GetHash(); if (mapOrphanTransactions.count(hash)) - return; + return false; + + CDataStream* pvMsg = new CDataStream(vMsg); + + // Ignore big transactions, to avoid a + // send-big-orphans memory exhaustion attack. If a peer has a legitimate + // large transaction with a missing parent then we assume + // it will rebroadcast it later, after the parent transaction(s) + // have been mined or received. + // 10,000 orphans, each of which is at most 5,000 bytes big is + // at most 500 megabytes of orphans: + if (pvMsg->size() > 5000) + { + delete pvMsg; + printf("ignoring large orphan tx (size: %u, hash: %s)\n", pvMsg->size(), hash.ToString().substr(0,10).c_str()); + return false; + } - CDataStream* pvMsg = mapOrphanTransactions[hash] = new CDataStream(vMsg); + mapOrphanTransactions[hash] = pvMsg; BOOST_FOREACH(const CTxIn& txin, tx.vin) - mapOrphanTransactionsByPrev.insert(make_pair(txin.prevout.hash, pvMsg)); + mapOrphanTransactionsByPrev[txin.prevout.hash].insert(make_pair(hash, pvMsg)); + + printf("stored orphan tx %s (mapsz %u)\n", hash.ToString().substr(0,10).c_str(), + mapOrphanTransactions.size()); + return true; } void static EraseOrphanTx(uint256 hash) @@ -182,14 +202,9 @@ void static EraseOrphanTx(uint256 hash) CDataStream(*pvMsg) >> tx; BOOST_FOREACH(const CTxIn& txin, tx.vin) { - for (multimap::iterator mi = mapOrphanTransactionsByPrev.lower_bound(txin.prevout.hash); - mi != mapOrphanTransactionsByPrev.upper_bound(txin.prevout.hash);) - { - if ((*mi).second == pvMsg) - mapOrphanTransactionsByPrev.erase(mi++); - else - mi++; - } + mapOrphanTransactionsByPrev[txin.prevout.hash].erase(hash); + if (mapOrphanTransactionsByPrev[txin.prevout.hash].empty()) + mapOrphanTransactionsByPrev.erase(txin.prevout.hash); } delete pvMsg; mapOrphanTransactions.erase(hash); @@ -2371,8 +2386,8 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) for (unsigned int i = 0; i < vWorkQueue.size(); i++) { uint256 hashPrev = vWorkQueue[i]; - for (multimap::iterator mi = mapOrphanTransactionsByPrev.lower_bound(hashPrev); - mi != mapOrphanTransactionsByPrev.upper_bound(hashPrev); + for (map::iterator mi = mapOrphanTransactionsByPrev[hashPrev].begin(); + mi != mapOrphanTransactionsByPrev[hashPrev].end(); ++mi) { const CDataStream& vMsg = *((*mi).second); @@ -2396,7 +2411,6 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) } else if (fMissingInputs) { - printf("storing orphan tx %s\n", inv.hash.ToString().substr(0,10).c_str()); AddOrphanTx(vMsg); // DoS prevention: do not allow mapOrphanTransactions to grow unbounded -- cgit v1.2.3 From ce1a071f6d6d1548974796c4327399659415b489 Mon Sep 17 00:00:00 2001 From: Gavin Andresen Date: Wed, 16 May 2012 11:26:56 -0400 Subject: Further DoS prevention: Verify signatures last Loop over all inputs doing inexpensive validity checks first, and then loop over them a second time doing expensive signature checks. This helps prevent possible CPU exhaustion attacks where an attacker tries to make a victim waste time checking signatures for invalid transactions. --- src/main.cpp | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index b7067b2092..00f0633431 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -1033,15 +1033,26 @@ bool CTransaction::ConnectInputs(MapPrevTx inputs, if (pindex->nBlockPos == txindex.pos.nBlockPos && pindex->nFile == txindex.pos.nFile) return error("ConnectInputs() : tried to spend coinbase at depth %d", pindexBlock->nHeight - pindex->nHeight); - // Check for conflicts (double-spend) - if (!txindex.vSpent[prevout.n].IsNull()) - return fMiner ? false : error("ConnectInputs() : %s prev tx already used at %s", GetHash().ToString().substr(0,10).c_str(), txindex.vSpent[prevout.n].ToString().c_str()); - // Check for negative or overflow input values nValueIn += txPrev.vout[prevout.n].nValue; if (!MoneyRange(txPrev.vout[prevout.n].nValue) || !MoneyRange(nValueIn)) return error("ConnectInputs() : txin values out of range"); + } + // The first loop above does all the inexpensive checks. + // Only if ALL inputs pass do we perform expensive ECDSA signature checks. + // Helps prevent CPU exhaustion attacks. + for (unsigned int i = 0; i < vin.size(); i++) + { + COutPoint prevout = vin[i].prevout; + assert(inputs.count(prevout.hash) > 0); + CTxIndex& txindex = inputs[prevout.hash].first; + CTransaction& txPrev = inputs[prevout.hash].second; + + // Check for conflicts (double-spend) + if (!txindex.vSpent[prevout.n].IsNull()) + return fMiner ? false : error("ConnectInputs() : %s prev tx already used at %s", GetHash().ToString().substr(0,10).c_str(), txindex.vSpent[prevout.n].ToString().c_str()); + // Verify signature if (!VerifySignature(txPrev, *this, i, fStrictPayToScriptHash, 0)) { -- cgit v1.2.3 From 01473c3f40cea8209186e737ae20289eebcb8898 Mon Sep 17 00:00:00 2001 From: Gavin Andresen Date: Thu, 17 May 2012 10:12:04 -0400 Subject: Remove invalid dependent orphans from memory Remove orphan transactions from memory once all of their parent transactions are received and they're still not valid. Thanks to Sergio Demian Lerner for suggesting this fix. --- src/main.cpp | 14 ++++++++++++-- 1 file changed, 12 insertions(+), 2 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 00f0633431..432ec871f5 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -2378,6 +2378,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) else if (strCommand == "tx") { vector vWorkQueue; + vector vEraseQueue; CDataStream vMsg(vRecv); CTransaction tx; vRecv >> tx; @@ -2392,6 +2393,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) RelayMessage(inv, vMsg); mapAlreadyAskedFor.erase(inv); vWorkQueue.push_back(inv.hash); + vEraseQueue.push_back(inv.hash); // Recursively process any orphan transactions that depended on this one for (unsigned int i = 0; i < vWorkQueue.size(); i++) @@ -2405,19 +2407,27 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) CTransaction tx; CDataStream(vMsg) >> tx; CInv inv(MSG_TX, tx.GetHash()); + bool fMissingInputs2 = false; - if (tx.AcceptToMemoryPool(true)) + if (tx.AcceptToMemoryPool(true, &fMissingInputs2)) { printf(" accepted orphan tx %s\n", inv.hash.ToString().substr(0,10).c_str()); SyncWithWallets(tx, NULL, true); RelayMessage(inv, vMsg); mapAlreadyAskedFor.erase(inv); vWorkQueue.push_back(inv.hash); + vEraseQueue.push_back(inv.hash); + } + else if (!fMissingInputs2) + { + // invalid orphan + vEraseQueue.push_back(inv.hash); + printf(" removed invalid orphan tx %s\n", inv.hash.ToString().substr(0,10).c_str()); } } } - BOOST_FOREACH(uint256 hash, vWorkQueue) + BOOST_FOREACH(uint256 hash, vEraseQueue) EraseOrphanTx(hash); } else if (fMissingInputs) -- cgit v1.2.3 From 3023e782bdaee3448e1543b482cf5cd022c9699f Mon Sep 17 00:00:00 2001 From: Gavin Andresen Date: Tue, 19 Jun 2012 15:50:12 -0400 Subject: print large orphan warning BEFORE deleting pvMsg --- src/main.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 432ec871f5..7ce7c92e5d 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -179,8 +179,8 @@ bool AddOrphanTx(const CDataStream& vMsg) // at most 500 megabytes of orphans: if (pvMsg->size() > 5000) { - delete pvMsg; printf("ignoring large orphan tx (size: %u, hash: %s)\n", pvMsg->size(), hash.ToString().substr(0,10).c_str()); + delete pvMsg; return false; } -- cgit v1.2.3