diff --git a/src/test/test_bitcoin.cpp b/src/test/test_bitcoin.cpp
--- a/src/test/test_bitcoin.cpp
+++ b/src/test/test_bitcoin.cpp
@@ -164,6 +164,14 @@
     for (const CMutableTransaction &tx : txns) {
         block.vtx.push_back(MakeTransactionRef(tx));
     }
+
+    // Order transactions by canonical order
+    std::sort(std::begin(block.vtx) + 1, std::end(block.vtx),
+              [](const std::shared_ptr<const CTransaction> &txa,
+                 const std::shared_ptr<const CTransaction> &txb) -> bool {
+                  return txa->GetId() < txb->GetId();
+              });
+
     // IncrementExtraNonce creates a valid coinbase and merkleRoot
     unsigned int extraNonce = 0;
     IncrementExtraNonce(config, &block, chainActive.Tip(), extraNonce);
diff --git a/src/test/txvalidationcache_tests.cpp b/src/test/txvalidationcache_tests.cpp
--- a/src/test/txvalidationcache_tests.cpp
+++ b/src/test/txvalidationcache_tests.cpp
@@ -189,7 +189,7 @@
     mutableSpend_tx.vout[3].nValue = 11 * CENT;
     mutableSpend_tx.vout[3].scriptPubKey = p2sh_scriptPubKey;
 
-    // Sign, and push an extra element on the stack.
+    // Sign
     {
         std::vector<uint8_t> vchSig;
         uint256 hash = SignatureHash(
@@ -197,21 +197,32 @@
             SigHashType().withForkId(), coinbaseTxns[0].vout[0].nValue);
         BOOST_CHECK(coinbaseKey.Sign(hash, vchSig));
         vchSig.push_back(uint8_t(SIGHASH_ALL | SIGHASH_FORKID));
-        mutableSpend_tx.vin[0].scriptSig << OP_TRUE << vchSig;
+        mutableSpend_tx.vin[0].scriptSig << vchSig;
     }
 
     const CTransaction spend_tx(mutableSpend_tx);
 
+    // Create a copy transaction which will fail cleanstack
+    {
+        std::vector<uint8_t> vchSig;
+        uint256 hash = SignatureHash(
+            p2pk_scriptPubKey, CTransaction(mutableSpend_tx), 0,
+            SigHashType().withForkId(), coinbaseTxns[0].vout[0].nValue);
+        BOOST_CHECK(coinbaseKey.Sign(hash, vchSig));
+        vchSig.push_back(uint8_t(SIGHASH_ALL | SIGHASH_FORKID));
+        mutableSpend_tx.vin[0].scriptSig << OP_1 << vchSig;
+    }
+    const CTransaction dirtystack_tx(mutableSpend_tx);
+
     LOCK(cs_main);
 
-    // Test that invalidity under a set of flags doesn't preclude validity under
-    // other (eg consensus) flags.
-    // spend_tx is invalid according to DERSIG
+    // Test that cleanstack fails properly
     {
         CValidationState state;
         PrecomputedTransactionData ptd_spend_tx(spend_tx);
 
-        BOOST_CHECK(!CheckInputs(spend_tx, state, pcoinsTip.get(), true,
+        // Valid under cleanstack
+        BOOST_CHECK(!CheckInputs(dirtystack_tx, state, pcoinsTip.get(), true,
                                  MANDATORY_SCRIPT_VERIFY_FLAGS |
                                      SCRIPT_VERIFY_CLEANSTACK,
                                  true, true, ptd_spend_tx, nullptr));
@@ -220,18 +231,41 @@
         // ConnectBlock), we should add a script check object for this -- we're
         // not caching invalidity (if that changes, delete this test case).
         std::vector<CScriptCheck> scriptchecks;
-        BOOST_CHECK(CheckInputs(spend_tx, state, pcoinsTip.get(), true,
+        BOOST_CHECK(CheckInputs(dirtystack_tx, state, pcoinsTip.get(), true,
                                 MANDATORY_SCRIPT_VERIFY_FLAGS |
                                     SCRIPT_VERIFY_CLEANSTACK,
                                 true, true, ptd_spend_tx, &scriptchecks));
         BOOST_CHECK_EQUAL(scriptchecks.size(), 1);
 
-        // Test that CheckInputs returns true iff cleanstack-enforcing flags are
-        // not present. Don't add these checks to the cache, so that we can test
-        // later that block validation works fine in the absence of cached
-        // successes.
-        ValidateCheckInputsForAllFlags(spend_tx, SCRIPT_VERIFY_CLEANSTACK,
+        // Test that CheckInputs returns false if cleanstack is enforced
+        ValidateCheckInputsForAllFlags(dirtystack_tx, SCRIPT_VERIFY_CLEANSTACK,
                                        false, false);
+    }
+
+    // Spend a transaction we can use later
+    {
+        CValidationState state;
+        PrecomputedTransactionData ptd_spend_tx(spend_tx);
+
+        // Valid under cleanstack
+        BOOST_CHECK(CheckInputs(spend_tx, state, pcoinsTip.get(), true,
+                                MANDATORY_SCRIPT_VERIFY_FLAGS |
+                                    SCRIPT_VERIFY_CLEANSTACK,
+                                true, false, ptd_spend_tx, nullptr));
+
+        // If we call again asking for scriptchecks (as happens in
+        // ConnectBlock), we should add a script check object for this -- we're
+        // not caching invalidity (if that changes, delete this test case).
+        std::vector<CScriptCheck> scriptchecks;
+        BOOST_CHECK(CheckInputs(spend_tx, state, pcoinsTip.get(), true,
+                                MANDATORY_SCRIPT_VERIFY_FLAGS |
+                                    SCRIPT_VERIFY_CLEANSTACK,
+                                true, true, ptd_spend_tx, &scriptchecks));
+        BOOST_CHECK_EQUAL(scriptchecks.size(), 1);
+
+        // Test that CheckInputs returns true if cleanstack is enforced
+        // ValidateCheckInputsForAllFlags(spend_tx, SCRIPT_VERIFY_CLEANSTACK,
+        //                              true, true);
 
         // And if we produce a block with this tx, it should be valid (LOW_S not
         // enabled yet), even though there's no cache entry.