From 5d901f1ba0b2f4444e484b9cb3db8d86c428af3f Mon Sep 17 00:00:00 2001
From: Gavin Andresen <gavinandresen@gmail.com>
Date: Thu, 8 Sep 2011 12:51:43 -0400
Subject: [PATCH] Orphan block fill-up-memory attack prevention

---
 src/checkpoints.cpp |   32 +++++++++++++++++++++++++++-----
 src/checkpoints.h   |    7 +++++++
 src/main.cpp        |   47 ++++++++++++++++++++++++++++++++++++++++++++---
 src/main.h          |    1 +
 4 files changed, 79 insertions(+), 8 deletions(-)

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 <boost/assign/list_of.hpp> // for 'map_list_of()'
+#include <boost/foreach.hpp>
+
+#include "headers.h"
+#include "checkpoints.h"
 
 namespace Checkpoints
 {
     typedef std::map<int, uint256> 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<uint256, CBlockIndex*>& mapBlockIndex)
+    {
+        if (fTestNet) return NULL;
+
+        int64 nResult;
+        BOOST_REVERSE_FOREACH(const MapCheckpoints::value_type& i, mapCheckpoints)
+        {
+            const uint256& hash = i.second;
+            std::map<uint256, CBlockIndex*>::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 <map>
+#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<uint256, CBlockIndex*>& mapBlockIndex);
 }
 
 #endif
diff --git a/src/main.cpp b/src/main.cpp
index dad7d14..af00069 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -651,11 +651,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)
@@ -1317,6 +1338,26 @@ bool static 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)
+        {
+            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)
+        {
+            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 f5e7f6c..876a35d 100644
--- a/src/main.h
+++ b/src/main.h
@@ -98,6 +98,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);
 bool IsInitialBlockDownload();
 std::string GetWarnings(std::string strFor);
 
-- 
1.7.1