From: Gavin Andresen Date: Thu, 8 Sep 2011 16:51:43 +0000 (-0400) Subject: Orphan block fill-up-memory attack prevention X-Git-Tag: v0.4.0-unstable~226^2~12^2 X-Git-Url: https://git.novaco.in/?p=novacoin.git;a=commitdiff_plain;h=10fd7f66893fd62ab65f9302115834c441eb571b Orphan block fill-up-memory attack prevention --- diff --git a/src/checkpoints.cpp b/src/checkpoints.cpp index 4419a06..c7e054d 100644 --- a/src/checkpoints.cpp +++ b/src/checkpoints.cpp @@ -2,16 +2,23 @@ // Distributed under the MIT/X11 software license, see the accompanying // file license.txt or http://www.opensource.org/licenses/mit-license.php. -#include "checkpoints.h" -#include "uint256.h" -#include "util.h" - #include // for 'map_list_of()' +#include + +#include "headers.h" +#include "checkpoints.h" namespace Checkpoints { typedef std::map MapCheckpoints; + // + // What makes a good checkpoint block? + // + Is surrounded by blocks with reasonable timestamps + // (no blocks before with a timestamp after, none after with + // timestamp before) + // + Contains no strange transactions + // static MapCheckpoints mapCheckpoints = boost::assign::map_list_of ( 11111, uint256("0x0000000069e244f73d78e8fd29ba2fd2ed618bd6fa2ee92559f542fdb26e7c1d")) @@ -36,8 +43,23 @@ namespace Checkpoints int GetTotalBlocksEstimate() { - if (fTestNet) return 0; // Testnet has no checkpoints + if (fTestNet) return 0; return mapCheckpoints.rbegin()->first; } + + CBlockIndex* GetLastCheckpoint(const std::map& mapBlockIndex) + { + if (fTestNet) return NULL; + + int64 nResult; + BOOST_REVERSE_FOREACH(const MapCheckpoints::value_type& i, mapCheckpoints) + { + const uint256& hash = i.second; + std::map::const_iterator t = mapBlockIndex.find(hash); + if (t != mapBlockIndex.end()) + return t->second; + } + return NULL; + } } diff --git a/src/checkpoints.h b/src/checkpoints.h index 32094fd..9d52da4 100644 --- a/src/checkpoints.h +++ b/src/checkpoints.h @@ -4,7 +4,11 @@ #ifndef BITCOIN_CHECKPOINT_H #define BITCOIN_CHECKPOINT_H +#include +#include "util.h" + class uint256; +class CBlockIndex; // // Block-chain checkpoints are compiled-in sanity checks. @@ -17,6 +21,9 @@ namespace Checkpoints // Return conservative estimate of total number of blocks, 0 if unknown int GetTotalBlocksEstimate(); + + // Returns last CBlockIndex* in mapBlockIndex that is a checkpoint + CBlockIndex* GetLastCheckpoint(const std::map& mapBlockIndex); } #endif diff --git a/src/main.cpp b/src/main.cpp index 832a0f9..a7871fc 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -659,11 +659,32 @@ int64 static GetBlockValue(int nHeight, int64 nFees) return nSubsidy + nFees; } +static const int64 nTargetTimespan = 14 * 24 * 60 * 60; // two weeks +static const int64 nTargetSpacing = 10 * 60; +static const int64 nInterval = nTargetTimespan / nTargetSpacing; + +// +// minimum amount of work that could possibly be required nTime after +// minimum work required was nBase +// +unsigned int ComputeMinWork(unsigned int nBase, int64 nTime) +{ + CBigNum bnResult; + bnResult.SetCompact(nBase); + while (nTime > 0 && bnResult < bnProofOfWorkLimit) + { + // Maximum 400% adjustment... + bnResult *= 4; + // ... in best-case exactly 4-times-normal target time + nTime -= nTargetTimespan*4; + } + if (bnResult > bnProofOfWorkLimit) + bnResult = bnProofOfWorkLimit; + return bnResult.GetCompact(); +} + unsigned int static GetNextWorkRequired(const CBlockIndex* pindexLast) { - const int64 nTargetTimespan = 14 * 24 * 60 * 60; // two weeks - const int64 nTargetSpacing = 10 * 60; - const int64 nInterval = nTargetTimespan / nTargetSpacing; // Genesis block if (pindexLast == NULL) @@ -1340,6 +1361,28 @@ bool ProcessBlock(CNode* pfrom, CBlock* pblock) if (!pblock->CheckBlock()) return error("ProcessBlock() : CheckBlock FAILED"); + CBlockIndex* pcheckpoint = Checkpoints::GetLastCheckpoint(mapBlockIndex); + if (pcheckpoint && pblock->hashPrevBlock != hashBestChain) + { + // Extra checks to prevent "fill up memory by spamming with bogus blocks" + int64 deltaTime = pblock->GetBlockTime() - pcheckpoint->nTime; + if (deltaTime < 0) + { + pfrom->Misbehaving(100); + return error("ProcessBlock() : block with timestamp before last checkpoint"); + } + CBigNum bnNewBlock; + bnNewBlock.SetCompact(pblock->nBits); + CBigNum bnRequired; + bnRequired.SetCompact(ComputeMinWork(pcheckpoint->nBits, deltaTime)); + if (bnNewBlock > bnRequired) + { + pfrom->Misbehaving(100); + return error("ProcessBlock() : block with too little proof-of-work"); + } + } + + // If don't already have its previous block, shunt it off to holding area until we get it if (!mapBlockIndex.count(pblock->hashPrevBlock)) { diff --git a/src/main.h b/src/main.h index f459d05..3870cee 100644 --- a/src/main.h +++ b/src/main.h @@ -99,6 +99,7 @@ void IncrementExtraNonce(CBlock* pblock, CBlockIndex* pindexPrev, unsigned int& void FormatHashBuffers(CBlock* pblock, char* pmidstate, char* pdata, char* phash1); bool CheckWork(CBlock* pblock, CWallet& wallet, CReserveKey& reservekey); bool CheckProofOfWork(uint256 hash, unsigned int nBits); +unsigned int ComputeMinWork(unsigned int nBase, int64 nTime); int GetNumBlocksOfPeers(); bool IsInitialBlockDownload(); std::string GetWarnings(std::string strFor); diff --git a/src/test/DoS_tests.cpp b/src/test/DoS_tests.cpp index 1093b73..01e6691 100644 --- a/src/test/DoS_tests.cpp +++ b/src/test/DoS_tests.cpp @@ -1,6 +1,7 @@ // // Unit tests for denial-of-service detection/prevention code // +#include // for 'map_list_of()' #include #include @@ -64,4 +65,54 @@ BOOST_AUTO_TEST_CASE(DoS_bantime) BOOST_CHECK(!CNode::IsBanned(addr.ip)); } +static bool CheckNBits(unsigned int nbits1, int64 time1, unsigned int nbits2, int64 time2) +{ + if (time1 > time2) + return CheckNBits(nbits2, time2, nbits1, time1); + int64 deltaTime = time2-time1; + + CBigNum required; + required.SetCompact(ComputeMinWork(nbits1, deltaTime)); + CBigNum have; + have.SetCompact(nbits2); + return (have <= required); +} + +BOOST_AUTO_TEST_CASE(DoS_checknbits) +{ + using namespace boost::assign; // for 'map_list_of()' + + // Timestamps,nBits from the bitcoin blockchain. + // These are the block-chain checkpoint blocks + typedef std::map BlockData; + BlockData chainData = + map_list_of(1239852051,486604799)(1262749024,486594666) + (1279305360,469854461)(1280200847,469830746)(1281678674,469809688) + (1296207707,453179945)(1302624061,453036989)(1309640330,437004818) + (1313172719,436789733); + + // Make sure CheckNBits considers every combination of block-chain-lock-in-points + // "sane": + BOOST_FOREACH(const BlockData::value_type& i, chainData) + { + BOOST_FOREACH(const BlockData::value_type& j, chainData) + { + BOOST_CHECK(CheckNBits(i.second, i.first, j.second, j.first)); + } + } + + // Test a couple of insane combinations: + BlockData::value_type firstcheck = *(chainData.begin()); + BlockData::value_type lastcheck = *(chainData.rbegin()); + + // First checkpoint difficulty at or a while after the last checkpoint time should fail when + // compared to last checkpoint + BOOST_CHECK(!CheckNBits(firstcheck.second, lastcheck.first+60*10, lastcheck.second, lastcheck.first)); + BOOST_CHECK(!CheckNBits(firstcheck.second, lastcheck.first+60*60*24*14, lastcheck.second, lastcheck.first)); + + // ... but OK if enough time passed for difficulty to adjust downward: + BOOST_CHECK(CheckNBits(firstcheck.second, lastcheck.first+60*60*24*365*4, lastcheck.second, lastcheck.first)); + +} + BOOST_AUTO_TEST_SUITE_END()