changeset 23713:2afbae511976

modified excessive block chain semantics -- once a chain that has an excessive block has been accepted, stay on its tip even if other excessive blocks are mined on that same chain. If no excessive blocks produced for 24 hours (approx) then reset and resist a new excessive block on that chain. This means clients and miners won't continually lag behind the tip if a chain is produced with lots of excessive blocks.
author Andrew Stone <g.andrew.stone@gmail.com>
date Tue, 08 Mar 2016 15:34:34 -0500
parents 347f871de0ac
children 995396e80224
files qa/rpc-tests/excessive.py src/Makefile.test.include src/main.cpp src/test/excessiveblock_test.cpp src/unlimited.cpp src/unlimited.h
diffstat 6 files changed, 244 insertions(+), 19 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/qa/rpc-tests/excessive.py	Tue Mar 08 15:34:34 2016 -0500
@@ -0,0 +1,154 @@
+#!/usr/bin/env python2
+# Copyright (c) 2014-2015 The Bitcoin Core developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+# Exercise the getchaintips API.  We introduce a network split, work
+# on chains of different lengths, and join the network together again.
+# This gives us two tips, verify that it works.
+import time
+import random
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.util import assert_equal
+from test_framework.util import *
+import pdb
+
+class ExcessiveBlockTest (BitcoinTestFramework):
+
+    def run_test (self):
+        BitcoinTestFramework.run_test (self)
+        tips = self.nodes[0].getchaintips ()
+        assert_equal (len (tips), 1)
+        assert_equal (tips[0]['branchlen'], 0)
+        assert_equal (tips[0]['height'], 200)
+        assert_equal (tips[0]['status'], 'active')
+        # get spendable coins
+        if 0:
+          for n in self.nodes:
+            n.generate(1)
+            self.sync_all()
+          self.nodes[0].generate(100)
+	  self.sync_all()
+        
+        t = self.nodes[1].getexcessiveblock()
+        # print t
+	# Set the accept depth at 1, 2, and 3 and watch each nodes resist the chain for that long
+        self.nodes[1].setexcessiveblock(1000, 1)
+        self.nodes[2].setexcessiveblock(1000, 2)
+        self.nodes[3].setexcessiveblock(1000, 3)
+        t = self.nodes[1].getexcessiveblock()
+        # print t
+        addr = self.nodes[3].getnewaddress()
+        for i in range(0,20):
+          self.nodes[0].sendtoaddress(addr, 1.0)
+        self.nodes[0].generate(1)
+        time.sleep(.5) # sleep gives the block time to propagate
+        counts = [ x.getblockcount() for x in self.nodes ]
+        assert_equal(counts, [201,200,200,200])  
+
+        self.nodes[0].generate(1)
+        time.sleep(.5)
+        counts = [ x.getblockcount() for x in self.nodes ]
+        assert_equal(counts, [202,202,200,200])  
+
+	self.nodes[0].generate(1)
+        time.sleep(.5)
+        counts = [ x.getblockcount() for x in self.nodes ]
+        assert_equal(counts, [203,203,203,200])  
+
+	self.nodes[0].generate(1)
+        time.sleep(.5)
+        counts = [ x.getblockcount() for x in self.nodes ]
+        assert_equal(counts, [204,204,204,204])  
+
+        # Now generate another excessive block, but all nodes should snap right to it because they have an older excessive block
+	for i in range(0,20):
+          self.nodes[0].sendtoaddress(addr, 1.0)
+        self.nodes[0].generate(1)
+        time.sleep(1)
+        counts = [ x.getblockcount() for x in self.nodes ]
+        # print counts
+        assert_equal(counts, [205,205,205,205])  
+      
+        self.nodes[0].generate(6*24)  # Now generate a day's worth of small blocks which should re-enable the node's reluctance to accept a large block
+	time.sleep(5)
+	for i in range(0,20):
+          self.nodes[0].sendtoaddress(addr, 1.0)
+        self.nodes[0].generate(1)
+	time.sleep(.5)
+        counts = [ x.getblockcount() for x in self.nodes ]
+	# print counts
+        assert_equal(counts, [350,349,349,349])  
+
+	for i in range(0,20):
+          self.nodes[0].sendtoaddress(addr, 1.0)
+        self.nodes[0].generate(1)
+	time.sleep(.5)
+        counts = [ x.getblockcount() for x in self.nodes ]
+	# print counts
+        assert_equal(counts, [351,351,350,350])  
+
+	for i in range(0,20):
+          self.nodes[0].sendtoaddress(addr, 1.0)
+        self.nodes[0].generate(1)
+	time.sleep(.5)
+        counts = [ x.getblockcount() for x in self.nodes ]
+	# print counts
+        assert_equal(counts, [352,352,352,351])  
+
+	for i in range(0,20):
+          self.nodes[0].sendtoaddress(addr, 1.0)
+        self.nodes[0].generate(1)
+	time.sleep(.5)
+        counts = [ x.getblockcount() for x in self.nodes ]
+	# print counts
+        assert_equal(counts, [353,353,353,353])  
+
+	for i in range(0,20):
+          self.nodes[0].sendtoaddress(addr, 1.0)
+        self.nodes[0].generate(1)
+	time.sleep(.5)
+        counts = [ x.getblockcount() for x in self.nodes ]
+	# print counts
+        assert_equal(counts, [354,354,354,354])  
+
+        self.nodes[0].generate(6*24 + 10)  # Now generate a day's worth of small blocks which should re-enable the node's reluctance to accept a large block + 10 because we have to get beyond all the node's accept depths
+	time.sleep(5)
+
+        counts = [ x.getblockcount() for x in self.nodes ]
+	# print counts
+        self.nodes[1].setexcessiveblock(100000, 1)  # not sure how big the txns will be but smaller than this 
+ 	for i in range(0,40):
+          self.nodes[0].sendtoaddress(addr, 1.0)
+	time.sleep(.5)
+        self.nodes[0].generate(1)
+	time.sleep(.5)
+        counts = [ x.getblockcount() for x in self.nodes ]
+	# print counts
+        assert_equal(counts[0], counts[1])  
+        assert_equal(counts[2], counts[3])  
+      
+
+        print "Random test"
+        random.seed(1)
+        for i in range(0,2):
+          print "round ", i,
+          for n in self.nodes:
+            n.setexcessiveblock(random.randint(1,1000)*1000, random.randint(0,10))
+          addrs = [x.getnewaddress() for x in self.nodes]
+          ntxs=0
+          for i in range(0,random.randint(1,1000)):
+            try:
+              self.nodes[random.randint(0,3)].sendtoaddress(addrs[random.randint(0,3)], .1)
+              ntxs += 1
+            except JSONRPCException: # could be spent all the txouts
+              pass
+          print ntxs, " transactions"
+          time.sleep(1)
+          self.nodes[random.randint(0,3)].generate(1)
+          time.sleep(1)
+
+
+
+if __name__ == '__main__':
+    ExcessiveBlockTest ().main ()
--- a/src/Makefile.test.include	Fri Mar 04 20:53:23 2016 -0500
+++ b/src/Makefile.test.include	Tue Mar 08 15:34:34 2016 -0500
@@ -34,6 +34,7 @@
 GENERATED_TEST_FILES = $(JSON_TEST_FILES:.json=.json.h) $(RAW_TEST_FILES:.raw=.raw.h)
 
 BITCOIN_TESTS =\
+  test/excessiveblock_test.cpp \
   test/arith_uint256_tests.cpp \
   test/scriptnum10.h \
   test/addrman_tests.cpp \
--- a/src/main.cpp	Fri Mar 04 20:53:23 2016 -0500
+++ b/src/main.cpp	Tue Mar 08 15:34:34 2016 -0500
@@ -2487,6 +2487,10 @@
         CBlockIndex *pindexTest = pindexNew;
         bool fInvalidAncestor = false;
         uint64_t depth=0;
+        bool fFailedChain = false;
+        bool fMissingData = false;
+        bool fRecentExcessive = false;  // Has there been a excessive block within our accept depth?
+        bool fOldExcessive = false;     // Was there an excessive block prior to our accept depth (if so we ignore the accept depth -- this chain has already been accepted as valid)
         while (pindexTest && !chainActive.Contains(pindexTest)) {  // follow the chain all the way back to where it joins the current active chain.
             assert(pindexTest->nChainTx || pindexTest->nHeight == 0);
 
@@ -2494,10 +2498,47 @@
             // which block files have been deleted.  Remove those as candidates
             // for the most work chain if we come across them; we can't switch
             // to a chain unless we have all the non-active-chain parent blocks.
-            bool fFailedChain = pindexTest->nStatus & BLOCK_FAILED_MASK;
-            bool fMissingData = !(pindexTest->nStatus & BLOCK_HAVE_DATA);
-            bool fExcessive = (depth < excessiveAcceptDepth) && (pindexTest->nStatus & BLOCK_EXCESSIVE);  // Unlimited: deny this candidate chain if there's a recent excessive block
-            if (fFailedChain || fMissingData || fExcessive) {
+            fFailedChain = pindexTest->nStatus & BLOCK_FAILED_MASK;
+            fMissingData = !(pindexTest->nStatus & BLOCK_HAVE_DATA);
+            if (depth < excessiveAcceptDepth)
+	      {
+		fRecentExcessive |= ((pindexTest->nStatus & BLOCK_EXCESSIVE) != 0);  // Unlimited: deny this candidate chain if there's a recent excessive block
+	      }
+            else
+	      {
+		fOldExcessive |= ((pindexTest->nStatus & BLOCK_EXCESSIVE) != 0);  // Unlimited: unless there is an even older excessive block
+	      }
+
+            if (fFailedChain | fMissingData | fRecentExcessive) break;
+            pindexTest = pindexTest->pprev;
+            depth++;
+        }
+
+        // If there was a recent excessive block, check a certain distance beyond the acceptdepth to see if this chain has already seen an excessive block... if it has then allow the chain.
+        // This stops the client from always tracking excessiveDepth blocks behind the chain tip in a situation where lots of excessive blocks are being created.
+        // But after a while with no excessive blocks, we reset and our reluctance to accept an excessive block resumes on this chain.
+        // An alternate algorithm would be to move the excessive block size up to match the size of the accepted block, but this changes a user-defined field and is awkward to code because
+        // block sizes are not saved.
+        if ((fRecentExcessive && !fOldExcessive)&&(depth<excessiveAcceptDepth+EXCESSIVE_BLOCK_CHAIN_RESET))
+	  {
+            CBlockIndex *chain = pindexTest;  
+            while (chain && (depth<excessiveAcceptDepth)) // skip accept depth blocks, we are looking for an older excessive
+	      {
+              chain = chain->pprev;
+              depth++;
+	      }
+
+            while (chain && (depth<excessiveAcceptDepth+EXCESSIVE_BLOCK_CHAIN_RESET)) 
+              {
+              fOldExcessive |= ((chain->nStatus & BLOCK_EXCESSIVE) != 0);
+              chain = chain->pprev;
+              depth++;
+              }
+	  }
+
+        // Conditions where we want to reject the chain
+	if (fFailedChain || fMissingData || (fRecentExcessive && !fOldExcessive)) 
+          {
                 // Candidate chain is not usable (either invalid or missing data)
                 if (fFailedChain && (pindexBestInvalid == NULL || pindexNew->nChainWork > pindexBestInvalid->nChainWork))
                     pindexBestInvalid = pindexNew;
@@ -2506,7 +2547,7 @@
                 while (pindexTest != pindexFailed) {
                     if (fFailedChain) {
                         pindexFailed->nStatus |= BLOCK_FAILED_CHILD;
-                    } else if (fMissingData || fExcessive) {
+                    } else if (fMissingData || (fRecentExcessive && !fOldExcessive)) {
                         // If we're missing data, then add back to mapBlocksUnlinked,
                         // so that if the block arrives in the future we can try adding
                         // to setBlockIndexCandidates again.
@@ -2517,14 +2558,12 @@
                 }
                 setBlockIndexCandidates.erase(pindexTest);
                 fInvalidAncestor = true;
-                break;
             }
-            pindexTest = pindexTest->pprev;
-            depth++;
-        }
+
         if (!fInvalidAncestor)
             return pindexNew;
     } while(true);
+    assert(0); // should never get here
 }
 
 /** Delete all entries in setBlockIndexCandidates that are worse than the current tip. */
@@ -3935,7 +3974,7 @@
                 // is valid and we have all data for its parents, it must be in
                 // setBlockIndexCandidates.  chainActive.Tip() must also be there
                 // even if some data has been pruned.
-              if ((!isChainExcessive(pindex)) && (pindexFirstMissing == NULL || pindex == chainActive.Tip()) )  // BU: if the chain is excessive it won't be on the list of active chain candidates
+              if ((!chainContainsExcessive(pindex)) && (pindexFirstMissing == NULL || pindex == chainActive.Tip()) )  // BU: if the chain is excessive it won't be on the list of active chain candidates
                 assert(setBlockIndexCandidates.count(pindex));
                 // If some parent is missing, then it could be that this block was in
                 // setBlockIndexCandidates but had to be removed because of the missing data.
@@ -3960,7 +3999,7 @@
             assert(foundInUnlinked);
         }
         if (!(pindex->nStatus & BLOCK_HAVE_DATA)) assert(!foundInUnlinked); // Can't be in mapBlocksUnlinked if we don't HAVE_DATA
-        if ((pindexFirstMissing == NULL)&&(!isChainExcessive(pindex))) // BU: why is this needed here?
+        if ((pindexFirstMissing == NULL)&&(!chainContainsExcessive(pindex))) // BU: blocks that are excessive are placed in the unlinked map
           {
           assert(!foundInUnlinked); // We aren't missing data for any parent -- cannot be in mapBlocksUnlinked.
           }
--- a/src/test/excessiveblock_test.cpp	Fri Mar 04 20:53:23 2016 -0500
+++ b/src/test/excessiveblock_test.cpp	Tue Mar 08 15:34:34 2016 -0500
@@ -7,9 +7,9 @@
 #include <boost/lexical_cast.hpp>
 
 using namespace std;
-using namespace json_spirit;
 
-extern Value CallRPC(string args);
+// Defined in rpc_tests.cpp not bitcoin-cli.cpp
+extern UniValue CallRPC(string strMethod);
 
 BOOST_FIXTURE_TEST_SUITE(excessiveblock_test, TestingSetup)
 
--- a/src/unlimited.cpp	Fri Mar 04 20:53:23 2016 -0500
+++ b/src/unlimited.cpp	Tue Mar 08 15:34:34 2016 -0500
@@ -208,17 +208,44 @@
            "\n";
 }
 
+
+int chainContainsExcessive(const CBlockIndex* blk, unsigned int goBack)
+{
+    if (goBack == 0)
+        goBack = excessiveAcceptDepth+EXCESSIVE_BLOCK_CHAIN_RESET;
+    for (unsigned int i = 0; i < goBack; i++, blk = blk->pprev) 
+    {
+        if (!blk)
+	  break; // we hit the beginning
+        if (blk->nStatus & BLOCK_EXCESSIVE)
+	  return true;
+    }
+    return false;
+}
+
 int isChainExcessive(const CBlockIndex* blk, unsigned int goBack)
 {
     if (goBack == 0)
         goBack = excessiveAcceptDepth;
-    for (unsigned int i = 1; i <= goBack; i++, blk = blk->pprev) {
+    bool recentExcessive = false;
+    bool oldExcessive = false;
+    for (unsigned int i = 0; i < goBack; i++, blk = blk->pprev) {
         if (!blk)
-            return 0; // Not excessive if we hit the beginning
+	  break; // we hit the beginning
         if (blk->nStatus & BLOCK_EXCESSIVE)
-            return i;
+	  recentExcessive = true;
     }
-    return 0;
+ 
+    // Once an excessive block is built upon the chain is not excessive even if more large blocks appear.
+    // So look back to make sure that this is the "first" excessive block for a while
+    for (unsigned int i = 0; i < EXCESSIVE_BLOCK_CHAIN_RESET; i++, blk = blk->pprev) {
+        if (!blk)
+	  break; // we hit the beginning
+        if (blk->nStatus & BLOCK_EXCESSIVE)
+	  oldExcessive = true;
+    }
+
+    return (recentExcessive && !oldExcessive);
 }
 
 bool CheckExcessive(const CBlock& block, uint64_t blockSize, uint64_t nSigOps, uint64_t nTx)
--- a/src/unlimited.h	Fri Mar 04 20:53:23 2016 -0500
+++ b/src/unlimited.h	Tue Mar 08 15:34:34 2016 -0500
@@ -15,7 +15,8 @@
     DEFAULT_EXCESSIVE_ACCEPT_DEPTH = 4,
     DEFAULT_EXCESSIVE_BLOCK_SIZE = 16000000,
     DEFAULT_MAX_MESSAGE_SIZE_MULTIPLIER = 10,
-    MAX_COINBASE_SCRIPTSIG_SIZE = 100
+    MAX_COINBASE_SCRIPTSIG_SIZE = 100,
+    EXCESSIVE_BLOCK_CHAIN_RESET = 6*24,  // After 1 day of non-excessive blocks, reset the checker
 };
 
 class CBlock;
@@ -52,8 +53,11 @@
 // Check whether this block is bigger in some metric than we really want to accept
 extern bool CheckExcessive(const CBlock& block, uint64_t blockSize, uint64_t nSigOps, uint64_t nTx);
 
+// Check whether this chain qualifies as excessive.
+extern int isChainExcessive(const CBlockIndex* blk, unsigned int checkDepth = excessiveAcceptDepth);
+
 // Check whether any block N back in this chain is an excessive block
-extern int isChainExcessive(const CBlockIndex* blk, unsigned int checkDepth = excessiveAcceptDepth);
+extern int chainContainsExcessive(const CBlockIndex* blk, unsigned int goBack=0);
 
 // RPC calls
 extern UniValue settrafficshaping(const UniValue& params, bool fHelp);