Merge #9484: Introduce assumevalid setting to skip validation presumed valid scripts.

7b5e3fe Add assumevalid testcase (John Newbery)
e440ac7 Introduce assumevalid setting to skip presumed valid scripts. (Gregory Maxwell)

8 files changed, 266 insertions, 12 deletions

diff --git a/doc/release-notes.md b/doc/release-notes.md
index 96d1cb9ed5..bbda55854f 100644
--- a/doc/release-notes.md
+++ b/doc/release-notes.md
@@ -52,7 +52,7 @@ Fee Estimation Changes
   (previously 25) and for RPC calls (previously 2).
 
 Removal of Priority Estimation
-------------------------------
+-------------------------------
 
 - Estimation of "priority" needed for a transaction to be included within a target
   number of blocks has been removed.  The rpc calls are deprecated and will either
@@ -76,6 +76,27 @@ P2P connection management
 
 - New connections to manually added peers are much faster.
 
+Introduction of assumed-valid blocks
+-------------------------------------
+
+- A significant portion of the initial block download time is spent verifying
+  scripts/signatures.  Although the verification must pass to ensure the security
+  of the system, no other result from this verification is needed: If the node
+  knew the history of a given block were valid it could skip checking scripts
+  for its ancestors.
+
+- A new configuration option 'assumevalid' is provided to express this knowledge
+  to the software.  Unlike the 'checkpoints' in the past this setting does not
+  force the use of a particular chain: chains that are consistent with it are
+  processed quicker, but other chains are still accepted if they'd otherwise
+  be chosen as best. Also unlike 'checkpoints' the user can configure which
+  block history is assumed true, this means that even outdated software can
+  sync more quickly if the setting is updated by the user.
+
+- Because the validity of a chain history is a simple objective fact it is much
+  easier to review this setting.  As a result the software ships with a default
+  value adjusted to match the current chain shortly before release.  The use
+  of this default value can be disabled by setting -assumevalid=0
 
 0.14.0 Change log
 =================
diff --git a/doc/release-process.md b/doc/release-process.md
index 61f05b0771..399ed25c91 100644
--- a/doc/release-process.md
+++ b/doc/release-process.md
@@ -13,6 +13,11 @@ Before every minor and major release:
 * Update version in sources (see below)
 * Write release notes (see below)
 * Update `src/chainparams.cpp` nMinimumChainWork with information from the getblockchaininfo rpc.
+* Update `src/chainparams.cpp` defaultAssumeValid  with information from the getblockhash rpc.
+  - The selected value must not be orphaned so it may be useful to set the value two blocks back from the tip.
+  - Testnet should be set some tens of thousands back from the tip due to reorgs there.
+  - This update should be reviewed with a reindex-chainstate with assumevalid=0 to catch any defect
+     that causes rejection of blocks in the past history.
 
 Before every major release:
 
diff --git a/qa/rpc-tests/assumevalid.py b/qa/rpc-tests/assumevalid.py
new file mode 100755
index 0000000000..e4bc22951b
--- /dev/null
+++ b/qa/rpc-tests/assumevalid.py
@@ -0,0 +1,191 @@
+#!/usr/bin/env python3
+# Copyright (c) 2014-2016 The Bitcoin Core developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+'''
+assumevalid.py
+
+Test logic for skipping signature validation on blocks which we've assumed
+valid (https://github.com/bitcoin/bitcoin/pull/9484)
+
+We build a chain that includes and invalid signature for one of the
+transactions:
+
+    0:        genesis block
+    1:        block 1 with coinbase transaction output.
+    2-101:    bury that block with 100 blocks so the coinbase transaction
+              output can be spent
+    102:      a block containing a transaction spending the coinbase
+              transaction output. The transaction has an invalid signature. 
+    103-2202: bury the bad block with just over two weeks' worth of blocks
+              (2100 blocks)
+
+Start three nodes:
+
+    - node0 has no -assumevalid parameter. Try to sync to block 2202. It will
+      reject block 102 and only sync as far as block 101
+    - node1 has -assumevalid set to the hash of block 102. Try to sync to
+      block 2202. node1 will sync all the way to block 2202.
+    - node2 has -assumevalid set to the hash of block 102. Try to sync to
+      block 200. node2 will reject block 102 since it's assumed valid, but it
+      isn't buried by at least two weeks' work.
+'''
+
+from test_framework.mininode import *
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.util import *
+from test_framework.blocktools import create_block, create_coinbase
+from test_framework.key import CECKey
+from test_framework.script import *
+
+class BaseNode(SingleNodeConnCB):
+    def __init__(self):
+        SingleNodeConnCB.__init__(self)
+        self.last_inv = None
+        self.last_headers = None
+        self.last_block = None
+        self.last_getdata = None
+        self.block_announced = False
+        self.last_getheaders = None
+        self.disconnected = False
+        self.last_blockhash_announced = None
+
+    def on_close(self, conn):
+        self.disconnected = True
+
+    def wait_for_disconnect(self, timeout=60):
+        test_function = lambda: self.disconnected
+        assert(wait_until(test_function, timeout=timeout))
+        return
+
+    def send_header_for_blocks(self, new_blocks):
+        headers_message = msg_headers()
+        headers_message.headers = [ CBlockHeader(b) for b in new_blocks ]
+        self.send_message(headers_message)
+
+class SendHeadersTest(BitcoinTestFramework):
+    def __init__(self):
+        super().__init__()
+        self.setup_clean_chain = True
+        self.num_nodes = 3
+
+    def setup_network(self):
+        # Start node0. We don't start the other nodes yet since
+        # we need to pre-mine a block with an invalid transaction
+        # signature so we can pass in the block hash as assumevalid.
+        self.nodes = []
+        self.nodes.append(start_node(0, self.options.tmpdir, ["-debug"]))
+
+    def run_test(self):
+
+        # Connect to node0
+        node0 = BaseNode()
+        connections = []
+        connections.append(NodeConn('127.0.0.1', p2p_port(0), self.nodes[0], node0))
+        node0.add_connection(connections[0])
+
+        NetworkThread().start() # Start up network handling in another thread
+        node0.wait_for_verack()
+
+        # Build the blockchain
+        self.tip = int(self.nodes[0].getbestblockhash(), 16)
+        self.block_time = self.nodes[0].getblock(self.nodes[0].getbestblockhash())['time'] + 1
+
+        self.blocks = []
+
+        # Get a pubkey for the coinbase TXO
+        coinbase_key = CECKey()
+        coinbase_key.set_secretbytes(b"horsebattery")
+        coinbase_pubkey = coinbase_key.get_pubkey()
+
+        # Create the first block with a coinbase output to our key
+        height = 1
+        block = create_block(self.tip, create_coinbase(height, coinbase_pubkey), self.block_time)
+        self.blocks.append(block)
+        self.block_time += 1
+        block.solve()
+        # Save the coinbase for later
+        self.block1 = block
+        self.tip = block.sha256
+        height += 1
+
+        # Bury the block 100 deep so the coinbase output is spendable
+        for i in range(100):
+            block = create_block(self.tip, create_coinbase(height), self.block_time)
+            block.solve()
+            self.blocks.append(block)
+            self.tip = block.sha256
+            self.block_time += 1
+            height += 1
+
+        # Create a transaction spending the coinbase output with an invalid (null) signature
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(self.block1.vtx[0].sha256, 0), scriptSig=b""))
+        tx.vout.append(CTxOut(49*100000000, CScript([OP_TRUE])))
+        tx.calc_sha256()
+
+        block102 = create_block(self.tip, create_coinbase(height), self.block_time)
+        self.block_time += 1
+        block102.vtx.extend([tx])
+        block102.hashMerkleRoot = block102.calc_merkle_root()
+        block102.rehash()
+        block102.solve()
+        self.blocks.append(block102)
+        self.tip = block102.sha256
+        self.block_time += 1
+        height += 1
+
+        # Bury the assumed valid block 2100 deep
+        for i in range(2100):
+            block = create_block(self.tip, create_coinbase(height), self.block_time)
+            block.nVersion = 4
+            block.solve()
+            self.blocks.append(block)
+            self.tip = block.sha256
+            self.block_time += 1
+            height += 1
+
+        # Start node1 and node2 with assumevalid so they accept a block with a bad signature.
+        self.nodes.append(start_node(1, self.options.tmpdir,
+                                     ["-debug", "-assumevalid=" + hex(block102.sha256)]))
+        node1 = BaseNode()  # connects to node1
+        connections.append(NodeConn('127.0.0.1', p2p_port(1), self.nodes[1], node1))
+        node1.add_connection(connections[1])
+        node1.wait_for_verack()
+
+        self.nodes.append(start_node(2, self.options.tmpdir,
+                                     ["-debug", "-assumevalid=" + hex(block102.sha256)]))
+        node2 = BaseNode()  # connects to node2
+        connections.append(NodeConn('127.0.0.1', p2p_port(2), self.nodes[2], node2))
+        node2.add_connection(connections[2])
+        node2.wait_for_verack()
+
+        # send header lists to all three nodes
+        node0.send_header_for_blocks(self.blocks[0:2000])
+        node0.send_header_for_blocks(self.blocks[2000:])
+        node1.send_header_for_blocks(self.blocks[0:2000])
+        node1.send_header_for_blocks(self.blocks[2000:])
+        node2.send_header_for_blocks(self.blocks[0:200])
+
+        # Send 102 blocks to node0. Block 102 will be rejected.
+        for i in range(101):
+            node0.send_message(msg_block(self.blocks[i]))
+        node0.sync_with_ping() # make sure the most recent block is synced
+        node0.send_message(msg_block(self.blocks[101]))
+        assert_equal(self.nodes[0].getblock(self.nodes[0].getbestblockhash())['height'], 101)
+
+        # Send 3102 blocks to node1. All blocks will be accepted.
+        for i in range(2202):
+            node1.send_message(msg_block(self.blocks[i]))
+        node1.sync_with_ping() # make sure the most recent block is synced
+        assert_equal(self.nodes[1].getblock(self.nodes[1].getbestblockhash())['height'], 2202)
+
+        # Send 102 blocks to node2. Block 102 will be rejected.
+        for i in range(101):
+            node2.send_message(msg_block(self.blocks[i]))
+        node2.sync_with_ping() # make sure the most recent block is synced
+        node2.send_message(msg_block(self.blocks[101]))
+        assert_equal(self.nodes[2].getblock(self.nodes[2].getbestblockhash())['height'], 101)
+
+if __name__ == '__main__':
+    SendHeadersTest().main()
diff --git a/src/chainparams.cpp b/src/chainparams.cpp
index 66b5d48fd9..d99f800f0a 100644
--- a/src/chainparams.cpp
+++ b/src/chainparams.cpp
@@ -99,6 +99,9 @@ public:
         // The best chain should have at least this much work.
         consensus.nMinimumChainWork = uint256S("0x0000000000000000000000000000000000000000002cb971dd56d1c583c20f90");
 
+        // By default assume that the signatures in ancestors of this block are valid.
+        consensus.defaultAssumeValid = uint256S("0x0000000000000000030abc968e1bd635736e880b946085c93152969b9a81a6e2"); //447235
+
         /**
          * The message start string is designed to be unlikely to occur in normal data.
          * The characters are rarely used upper ASCII, not valid as UTF-8, and produce
@@ -201,6 +204,9 @@ public:
         // The best chain should have at least this much work.
         consensus.nMinimumChainWork = uint256S("0x0000000000000000000000000000000000000000000000198b4def2baa9338d6");
 
+        // By default assume that the signatures in ancestors of this block are valid.
+        consensus.defaultAssumeValid = uint256S("0x000000000871ee6842d3648317ccc8a435eb8cc3c2429aee94faff9ba26b05a0"); //1043841
+
         pchMessageStart[0] = 0x0b;
         pchMessageStart[1] = 0x11;
         pchMessageStart[2] = 0x09;
@@ -283,6 +289,9 @@ public:
         // The best chain should have at least this much work.
         consensus.nMinimumChainWork = uint256S("0x00");
 
+        // By default assume that the signatures in ancestors of this block are valid.
+        consensus.defaultAssumeValid = uint256S("0x00");
+
         pchMessageStart[0] = 0xfa;
         pchMessageStart[1] = 0xbf;
         pchMessageStart[2] = 0xb5;
diff --git a/src/consensus/params.h b/src/consensus/params.h
index edf445e1c7..3f98938f7e 100644
--- a/src/consensus/params.h
+++ b/src/consensus/params.h
@@ -62,6 +62,7 @@ struct Params {
     int64_t nPowTargetTimespan;
     int64_t DifficultyAdjustmentInterval() const { return nPowTargetTimespan / nPowTargetSpacing; }
     uint256 nMinimumChainWork;
+    uint256 defaultAssumeValid;
 };
 } // namespace Consensus
 
diff --git a/src/init.cpp b/src/init.cpp
index 07af9acc80..14c0a36f52 100644
--- a/src/init.cpp
+++ b/src/init.cpp
@@ -329,8 +329,7 @@ std::string HelpMessage(HelpMessageMode mode)
     strUsage += HelpMessageOpt("-blocknotify=<cmd>", _("Execute command when the best block changes (%s in cmd is replaced by block hash)"));
     if (showDebug)
         strUsage += HelpMessageOpt("-blocksonly", strprintf(_("Whether to operate in a blocks only mode (default: %u)"), DEFAULT_BLOCKSONLY));
-    strUsage += HelpMessageOpt("-checkblocks=<n>", strprintf(_("How many blocks to check at startup (default: %u, 0 = all)"), DEFAULT_CHECKBLOCKS));
-    strUsage += HelpMessageOpt("-checklevel=<n>", strprintf(_("How thorough the block verification of -checkblocks is (0-4, default: %u)"), DEFAULT_CHECKLEVEL));
+    strUsage +=HelpMessageOpt("-assumevalid=<hex>", strprintf(_("If this block is in the chain assume that it and its ancestors are valid and potentially skip their script verification (0 to verify all, default: %s, testnet: %s)"), Params(CBaseChainParams::MAIN).GetConsensus().defaultAssumeValid.GetHex(), Params(CBaseChainParams::TESTNET).GetConsensus().defaultAssumeValid.GetHex()));
     strUsage += HelpMessageOpt("-conf=<file>", strprintf(_("Specify configuration file (default: %s)"), BITCOIN_CONF_FILENAME));
     if (mode == HMM_BITCOIND)
     {
@@ -420,6 +419,8 @@ std::string HelpMessage(HelpMessageMode mode)
     strUsage += HelpMessageOpt("-uacomment=<cmt>", _("Append comment to the user agent string"));
     if (showDebug)
     {
+        strUsage += HelpMessageOpt("-checkblocks=<n>", strprintf(_("How many blocks to check at startup (default: %u, 0 = all)"), DEFAULT_CHECKBLOCKS));
+        strUsage += HelpMessageOpt("-checklevel=<n>", strprintf(_("How thorough the block verification of -checkblocks is (0-4, default: %u)"), DEFAULT_CHECKLEVEL));
         strUsage += HelpMessageOpt("-checkblockindex", strprintf("Do a full consistency check for mapBlockIndex, setBlockIndexCandidates, chainActive and mapBlocksUnlinked occasionally. Also sets -checkmempool (default: %u)", Params(CBaseChainParams::MAIN).DefaultConsistencyChecks()));
         strUsage += HelpMessageOpt("-checkmempool=<n>", strprintf("Run checks every <n> transactions (default: %u)", Params(CBaseChainParams::MAIN).DefaultConsistencyChecks()));
         strUsage += HelpMessageOpt("-checkpoints", strprintf("Disable expensive verification for known chain history (default: %u)", DEFAULT_CHECKPOINTS_ENABLED));
@@ -924,6 +925,12 @@ bool AppInitParameterInteraction()
     fCheckBlockIndex = GetBoolArg("-checkblockindex", chainparams.DefaultConsistencyChecks());
     fCheckpointsEnabled = GetBoolArg("-checkpoints", DEFAULT_CHECKPOINTS_ENABLED);
 
+    hashAssumeValid = uint256S(GetArg("-assumevalid", chainparams.GetConsensus().defaultAssumeValid.GetHex()));
+    if (!hashAssumeValid.IsNull())
+        LogPrintf("Assuming ancestors of block %s have valid signatures.\n", hashAssumeValid.GetHex());
+    else
+        LogPrintf("Validating signatures for all blocks.\n");
+
     // mempool limits
     int64_t nMempoolSizeMax = GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000;
     int64_t nMempoolSizeMin = GetArg("-limitdescendantsize", DEFAULT_DESCENDANT_SIZE_LIMIT) * 1000 * 40;
diff --git a/src/validation.cpp b/src/validation.cpp
index 9013e82ce9..2ad3dadeb6 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -78,6 +78,7 @@ uint64_t nPruneTarget = 0;
 int64_t nMaxTipAge = DEFAULT_MAX_TIP_AGE;
 bool fEnableReplacement = DEFAULT_ENABLE_REPLACEMENT;
 
+uint256 hashAssumeValid;
 
 CFeeRate minRelayTxFee = CFeeRate(DEFAULT_MIN_RELAY_TX_FEE);
 CAmount maxTxFee = DEFAULT_TRANSACTION_MAXFEE;
@@ -1389,11 +1390,10 @@ bool CheckInputs(const CTransaction& tx, CValidationState &state, const CCoinsVi
         // Only if ALL inputs pass do we perform expensive ECDSA signature checks.
         // Helps prevent CPU exhaustion attacks.
 
-        // Skip ECDSA signature verification when connecting blocks before the
-        // last block chain checkpoint. Assuming the checkpoints are valid this
+        // Skip script verification when connecting blocks under the
+        // assumedvalid block. Assuming the assumedvalid block is valid this
         // is safe because block merkle hashes are still computed and checked,
-        // and any change will be caught at the next checkpoint. Of course, if
-        // the checkpoint is for a chain that's invalid due to false scriptSigs
+        // Of course, if an assumed valid block is invalid due to false scriptSigs
         // this optimization would allow an invalid chain to be accepted.
         if (fScriptChecks) {
             for (unsigned int i = 0; i < tx.vin.size(); i++) {
@@ -1721,11 +1721,28 @@ bool ConnectBlock(const CBlock& block, CValidationState& state, CBlockIndex* pin
     }
 
     bool fScriptChecks = true;
-    if (fCheckpointsEnabled) {
-        CBlockIndex *pindexLastCheckpoint = Checkpoints::GetLastCheckpoint(chainparams.Checkpoints());
-        if (pindexLastCheckpoint && pindexLastCheckpoint->GetAncestor(pindex->nHeight) == pindex) {
-            // This block is an ancestor of a checkpoint: disable script checks
-            fScriptChecks = false;
+    if (!hashAssumeValid.IsNull()) {
+        // We've been configured with the hash of a block which has been externally verified to have a valid history.
+        // A suitable default value is included with the software and updated from time to time.  Because validity
+        //  relative to a piece of software is an objective fact these defaults can be easily reviewed.
+        // This setting doesn't force the selection of any particular chain but makes validating some faster by
+        //  effectively caching the result of part of the verification.
+        BlockMap::const_iterator  it = mapBlockIndex.find(hashAssumeValid);
+        if (it != mapBlockIndex.end()) {
+            if (it->second->GetAncestor(pindex->nHeight) == pindex &&
+                pindexBestHeader->GetAncestor(pindex->nHeight) == pindex &&
+                pindexBestHeader->nChainWork >= UintToArith256(chainparams.GetConsensus().nMinimumChainWork)) {
+                // This block is a member of the assumed verified chain and an ancestor of the best header.
+                // The equivalent time check discourages hashpower from extorting the network via DOS attack
+                //  into accepting an invalid block through telling users they must manually set assumevalid.
+                //  Requiring a software change or burying the invalid block, regardless of the setting, makes
+                //  it hard to hide the implication of the demand.  This also avoids having release candidates
+                //  that are hardly doing any signature verification at all in testing without having to
+                //  artificially set the default assumed verified block further back.
+                // The test against nMinimumChainWork prevents the skipping when denied access to any chain at
+                //  least as good as the expected chain.
+                fScriptChecks = (GetBlockProofEquivalentTime(*pindexBestHeader, *pindex, *pindexBestHeader, chainparams.GetConsensus()) <= 60 * 60 * 24 * 7 * 2);
+            }
         }
     }
 
diff --git a/src/validation.h b/src/validation.h
index 43a37e46e5..e57c636422 100644
--- a/src/validation.h
+++ b/src/validation.h
@@ -186,6 +186,9 @@ extern CAmount maxTxFee;
 extern int64_t nMaxTipAge;
 extern bool fEnableReplacement;
 
+/** Block hash whose ancestors we will assume to have valid scripts without checking them. */
+extern uint256 hashAssumeValid;
+
 /** Best header we've seen so far (used for getheaders queries' starting points). */
 extern CBlockIndex *pindexBestHeader;