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,50 @@
     mutableSpend_tx.vout[3].nValue = 11 * CENT;
     mutableSpend_tx.vout[3].scriptPubKey = p2sh_scriptPubKey;
 
-    // Sign, and push an extra element on the stack.
+    LOCK(cs_main);
+
+    // Test that invalidity under a set of flags doesn't preclude validity under
+    // other (eg consensus) flags.
+    {
+        // Create a 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 = CScript() << OP_1 << vchSig;
+        }
+        const CTransaction dirtystack_tx(mutableSpend_tx);
+
+        CValidationState state;
+        PrecomputedTransactionData ptd_spend_tx(dirtystack_tx);
+
+        // Invalid under cleanstack
+        BOOST_CHECK(!CheckInputs(dirtystack_tx, state, pcoinsTip.get(), true,
+                                 MANDATORY_SCRIPT_VERIFY_FLAGS |
+                                     SCRIPT_VERIFY_CLEANSTACK,
+                                 true, true, 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(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 false if cleanstack is enforced for
+        // all combinations of flags
+        ValidateCheckInputsForAllFlags(dirtystack_tx, SCRIPT_VERIFY_CLEANSTACK,
+                                       false, false);
+    }
+
+    // Create a transaction we can spend
+    // 1. Sign
     {
         std::vector<uint8_t> vchSig;
         uint256 hash = SignatureHash(
@@ -197,28 +240,26 @@
             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 = CScript() << vchSig;
     }
 
     const CTransaction spend_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
+    // 2. Spend into UTXOs we can respend later
     {
+
         CValidationState state;
         PrecomputedTransactionData ptd_spend_tx(spend_tx);
 
-        BOOST_CHECK(!CheckInputs(spend_tx, state, pcoinsTip.get(), true,
-                                 MANDATORY_SCRIPT_VERIFY_FLAGS |
-                                     SCRIPT_VERIFY_CLEANSTACK,
-                                 true, true, ptd_spend_tx, nullptr));
+        // Valid under cleanstack, but don't cache or the next step
+        // check won't be able to be tested.
+        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).
+        // ConnectBlock), we should add a script check object for this.
         std::vector<CScriptCheck> scriptchecks;
         BOOST_CHECK(CheckInputs(spend_tx, state, pcoinsTip.get(), true,
                                 MANDATORY_SCRIPT_VERIFY_FLAGS |
@@ -226,15 +267,7 @@
                                 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,
-                                       false, false);
-
-        // 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.
+        // And if we produce a block with this tx, it should be valid.
         CBlock block;
 
         block = CreateAndProcessBlock({spend_tx}, p2pk_scriptPubKey);