Merge #7575: Minimal BIP9 implementation

8c74ced RPC test for BIP9 warning logic (Suhas Daftuar)
7870deb Test versionbits deployments (Suhas Daftuar)
532cbb2 Add testing of ComputeBlockVersion (Suhas Daftuar)
d23f6c6 Softfork status report in RPC (Pieter Wuille)
732e774 Versionbits tests (Pieter Wuille)
6851107 BIP9 Implementation (Pieter Wuille)

15 files changed, 703 insertions, 20 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index fa7a78f330..7765ea43ed 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -152,6 +152,7 @@ BITCOIN_CORE_H = \
   utilmoneystr.h \
   utiltime.h \
   validationinterface.h \
+  versionbits.h \
   wallet/crypter.h \
   wallet/db.h \
   wallet/rpcwallet.h \
@@ -204,6 +205,7 @@ libbitcoin_server_a_SOURCES = \
   txdb.cpp \
   txmempool.cpp \
   validationinterface.cpp \
+  versionbits.cpp \
   $(BITCOIN_CORE_H)
 
 if ENABLE_ZMQ
diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index 0c4e47a147..57f9ac50e0 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -83,6 +83,7 @@ BITCOIN_TESTS =\
   test/timedata_tests.cpp \
   test/transaction_tests.cpp \
   test/txvalidationcache_tests.cpp \
+  test/versionbits_tests.cpp \
   test/uint256_tests.cpp \
   test/univalue_tests.cpp \
   test/util_tests.cpp
diff --git a/src/chain.h b/src/chain.h
index 9199983565..5b9605a80b 100644
--- a/src/chain.h
+++ b/src/chain.h
@@ -14,8 +14,6 @@
 
 #include <vector>
 
-#include <boost/foreach.hpp>
-
 struct CDiskBlockPos
 {
     int nFile;
diff --git a/src/chainparams.cpp b/src/chainparams.cpp
index b962f6ac0a..35e090a0b3 100644
--- a/src/chainparams.cpp
+++ b/src/chainparams.cpp
@@ -81,6 +81,11 @@ public:
         consensus.nPowTargetSpacing = 10 * 60;
         consensus.fPowAllowMinDifficultyBlocks = false;
         consensus.fPowNoRetargeting = false;
+        consensus.nRuleChangeActivationThreshold = 1916; // 95% of 2016
+        consensus.nMinerConfirmationWindow = 2016; // nPowTargetTimespan / nPowTargetSpacing
+        consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].bit = 28;
+        consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nStartTime = 1199145601; // January 1, 2008
+        consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nTimeout = 1230767999; // December 31, 2008
         /** 
          * 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
@@ -162,6 +167,11 @@ public:
         consensus.nPowTargetSpacing = 10 * 60;
         consensus.fPowAllowMinDifficultyBlocks = true;
         consensus.fPowNoRetargeting = false;
+        consensus.nRuleChangeActivationThreshold = 1512; // 75% for testchains
+        consensus.nMinerConfirmationWindow = 2016; // nPowTargetTimespan / nPowTargetSpacing
+        consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].bit = 28;
+        consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nStartTime = 1199145601; // January 1, 2008
+        consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nTimeout = 1230767999; // December 31, 2008
         pchMessageStart[0] = 0x0b;
         pchMessageStart[1] = 0x11;
         pchMessageStart[2] = 0x09;
@@ -225,6 +235,11 @@ public:
         consensus.nPowTargetSpacing = 10 * 60;
         consensus.fPowAllowMinDifficultyBlocks = true;
         consensus.fPowNoRetargeting = true;
+        consensus.nRuleChangeActivationThreshold = 108; // 75% for testchains
+        consensus.nMinerConfirmationWindow = 144; // Faster than normal for regtest (144 instead of 2016)
+        consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].bit = 28;
+        consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nStartTime = 0;
+        consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nTimeout = 999999999999ULL;
 
         pchMessageStart[0] = 0xfa;
         pchMessageStart[1] = 0xbf;
diff --git a/src/consensus/params.h b/src/consensus/params.h
index 335750fe80..7c3a8e84c3 100644
--- a/src/consensus/params.h
+++ b/src/consensus/params.h
@@ -7,8 +7,29 @@
 #define BITCOIN_CONSENSUS_PARAMS_H
 
 #include "uint256.h"
+#include <map>
+#include <string>
 
 namespace Consensus {
+
+enum DeploymentPos
+{
+    DEPLOYMENT_TESTDUMMY,
+    MAX_VERSION_BITS_DEPLOYMENTS
+};
+
+/**
+ * Struct for each individual consensus rule change using BIP9.
+ */
+struct BIP9Deployment {
+    /** Bit position to select the particular bit in nVersion. */
+    int bit;
+    /** Start MedianTime for version bits miner confirmation. Can be a date in the past */
+    int64_t nStartTime;
+    /** Timeout/expiry MedianTime for the deployment attempt. */
+    int64_t nTimeout;
+};
+
 /**
  * Parameters that influence chain consensus.
  */
@@ -22,6 +43,14 @@ struct Params {
     /** Block height and hash at which BIP34 becomes active */
     int BIP34Height;
     uint256 BIP34Hash;
+    /**
+     * Minimum blocks including miner confirmation of the total of 2016 blocks in a retargetting period,
+     * (nPowTargetTimespan / nPowTargetSpacing) which is also used for BIP9 deployments.
+     * Examples: 1916 for 95%, 1512 for testchains.
+     */
+    uint32_t nRuleChangeActivationThreshold;
+    uint32_t nMinerConfirmationWindow;
+    BIP9Deployment vDeployments[MAX_VERSION_BITS_DEPLOYMENTS];
     /** Proof of work parameters */
     uint256 powLimit;
     bool fPowAllowMinDifficultyBlocks;
diff --git a/src/init.cpp b/src/init.cpp
index 637b69ab05..a39256c6e3 100644
--- a/src/init.cpp
+++ b/src/init.cpp
@@ -466,7 +466,7 @@ std::string HelpMessage(HelpMessageMode mode)
     strUsage += HelpMessageOpt("-blockmaxsize=<n>", strprintf(_("Set maximum block size in bytes (default: %d)"), DEFAULT_BLOCK_MAX_SIZE));
     strUsage += HelpMessageOpt("-blockprioritysize=<n>", strprintf(_("Set maximum size of high-priority/low-fee transactions in bytes (default: %d)"), DEFAULT_BLOCK_PRIORITY_SIZE));
     if (showDebug)
-        strUsage += HelpMessageOpt("-blockversion=<n>", strprintf("Override block version to test forking scenarios (default: %d)", (int)CBlock::CURRENT_VERSION));
+        strUsage += HelpMessageOpt("-blockversion=<n>", "Override block version to test forking scenarios");
 
     strUsage += HelpMessageGroup(_("RPC server options:"));
     strUsage += HelpMessageOpt("-server", _("Accept command line and JSON-RPC commands"));
diff --git a/src/main.cpp b/src/main.cpp
index 924c2f9e0c..1bc88326b6 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -34,6 +34,7 @@
 #include "utilmoneystr.h"
 #include "utilstrencodings.h"
 #include "validationinterface.h"
+#include "versionbits.h"
 
 #include <sstream>
 
@@ -2120,6 +2121,51 @@ void PartitionCheck(bool (*initialDownloadCheck)(), CCriticalSection& cs, const
     }
 }
 
+// Protected by cs_main
+static VersionBitsCache versionbitscache;
+
+int32_t ComputeBlockVersion(const CBlockIndex* pindexPrev, const Consensus::Params& params)
+{
+    LOCK(cs_main);
+    int32_t nVersion = VERSIONBITS_TOP_BITS;
+
+    for (int i = 0; i < (int)Consensus::MAX_VERSION_BITS_DEPLOYMENTS; i++) {
+        ThresholdState state = VersionBitsState(pindexPrev, params, (Consensus::DeploymentPos)i, versionbitscache);
+        if (state == THRESHOLD_LOCKED_IN || state == THRESHOLD_STARTED) {
+            nVersion |= VersionBitsMask(params, (Consensus::DeploymentPos)i);
+        }
+    }
+
+    return nVersion;
+}
+
+/**
+ * Threshold condition checker that triggers when unknown versionbits are seen on the network.
+ */
+class WarningBitsConditionChecker : public AbstractThresholdConditionChecker
+{
+private:
+    int bit;
+
+public:
+    WarningBitsConditionChecker(int bitIn) : bit(bitIn) {}
+
+    int64_t BeginTime(const Consensus::Params& params) const { return 0; }
+    int64_t EndTime(const Consensus::Params& params) const { return std::numeric_limits<int64_t>::max(); }
+    int Period(const Consensus::Params& params) const { return params.nMinerConfirmationWindow; }
+    int Threshold(const Consensus::Params& params) const { return params.nRuleChangeActivationThreshold; }
+
+    bool Condition(const CBlockIndex* pindex, const Consensus::Params& params) const
+    {
+        return ((pindex->nVersion & VERSIONBITS_TOP_MASK) == VERSIONBITS_TOP_BITS) &&
+               ((pindex->nVersion >> bit) & 1) != 0 &&
+               ((ComputeBlockVersion(pindex->pprev, params) >> bit) & 1) == 0;
+    }
+};
+
+// Protected by cs_main
+static ThresholdConditionCache warningcache[VERSIONBITS_NUM_BITS];
+
 static int64_t nTimeCheck = 0;
 static int64_t nTimeForks = 0;
 static int64_t nTimeVerify = 0;
@@ -2489,24 +2535,42 @@ void static UpdateTip(CBlockIndex *pindexNew) {
 
     // Check the version of the last 100 blocks to see if we need to upgrade:
     static bool fWarned = false;
-    if (!IsInitialBlockDownload() && !fWarned)
+    if (!IsInitialBlockDownload())
     {
         int nUpgraded = 0;
         const CBlockIndex* pindex = chainActive.Tip();
+        for (int bit = 0; bit < VERSIONBITS_NUM_BITS; bit++) {
+            WarningBitsConditionChecker checker(bit);
+            ThresholdState state = checker.GetStateFor(pindex, chainParams.GetConsensus(), warningcache[bit]);
+            if (state == THRESHOLD_ACTIVE || state == THRESHOLD_LOCKED_IN) {
+                if (state == THRESHOLD_ACTIVE) {
+                    strMiscWarning = strprintf(_("Warning: unknown new rules activated (versionbit %i)"), bit);
+                    if (!fWarned) {
+                        CAlert::Notify(strMiscWarning, true);
+                        fWarned = true;
+                    }
+                } else {
+                    LogPrintf("%s: unknown new rules are about to activate (versionbit %i)\n", __func__, bit);
+                }
+            }
+        }
         for (int i = 0; i < 100 && pindex != NULL; i++)
         {
-            if (pindex->nVersion > CBlock::CURRENT_VERSION)
+            int32_t nExpectedVersion = ComputeBlockVersion(pindex->pprev, chainParams.GetConsensus());
+            if (pindex->nVersion > VERSIONBITS_LAST_OLD_BLOCK_VERSION && (pindex->nVersion & ~nExpectedVersion) != 0)
                 ++nUpgraded;
             pindex = pindex->pprev;
         }
         if (nUpgraded > 0)
-            LogPrintf("%s: %d of last 100 blocks above version %d\n", __func__, nUpgraded, (int)CBlock::CURRENT_VERSION);
+            LogPrintf("%s: %d of last 100 blocks have unexpected version\n", __func__, nUpgraded);
         if (nUpgraded > 100/2)
         {
             // strMiscWarning is read by GetWarnings(), called by Qt and the JSON-RPC code to warn the user:
-            strMiscWarning = _("Warning: This version is obsolete; upgrade required!");
-            CAlert::Notify(strMiscWarning, true);
-            fWarned = true;
+            strMiscWarning = _("Warning: Unknown block versions being mined! It's possible unknown rules are in effect");
+            if (!fWarned) {
+                CAlert::Notify(strMiscWarning, true);
+                fWarned = true;
+            }
         }
     }
 }
@@ -3800,6 +3864,10 @@ void UnloadBlockIndex()
     setDirtyFileInfo.clear();
     mapNodeState.clear();
     recentRejects.reset(NULL);
+    versionbitscache.Clear();
+    for (int b = 0; b < VERSIONBITS_NUM_BITS; b++) {
+        warningcache[b].clear();
+    }
 
     BOOST_FOREACH(BlockMap::value_type& entry, mapBlockIndex) {
         delete entry.second;
@@ -5828,7 +5896,11 @@ bool SendMessages(CNode* pto)
      return strprintf("CBlockFileInfo(blocks=%u, size=%u, heights=%u...%u, time=%s...%s)", nBlocks, nSize, nHeightFirst, nHeightLast, DateTimeStrFormat("%Y-%m-%d", nTimeFirst), DateTimeStrFormat("%Y-%m-%d", nTimeLast));
  }
 
-
+ThresholdState VersionBitsTipState(const Consensus::Params& params, Consensus::DeploymentPos pos)
+{
+    LOCK(cs_main);
+    return VersionBitsState(chainActive.Tip(), params, pos, versionbitscache);
+}
 
 class CMainCleanup
 {
diff --git a/src/main.h b/src/main.h
index 85ec60ac61..6936b5379a 100644
--- a/src/main.h
+++ b/src/main.h
@@ -16,6 +16,7 @@
 #include "net.h"
 #include "script/script_error.h"
 #include "sync.h"
+#include "versionbits.h"
 
 #include <algorithm>
 #include <exception>
@@ -290,6 +291,9 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
 /** Convert CValidationState to a human-readable message for logging */
 std::string FormatStateMessage(const CValidationState &state);
 
+/** Get the BIP9 state for a given deployment at the current tip. */
+ThresholdState VersionBitsTipState(const Consensus::Params& params, Consensus::DeploymentPos pos);
+
 struct CNodeStateStats {
     int nMisbehavior;
     int nSyncHeight;
@@ -547,6 +551,11 @@ extern CBlockTreeDB *pblocktree;
  */
 int GetSpendHeight(const CCoinsViewCache& inputs);
 
+/**
+ * Determine what nVersion a new block should use.
+ */
+int32_t ComputeBlockVersion(const CBlockIndex* pindexPrev, const Consensus::Params& params);
+
 /** Reject codes greater or equal to this can be returned by AcceptToMemPool
  * for transactions, to signal internal conditions. They cannot and should not
  * be sent over the P2P network.
diff --git a/src/miner.cpp b/src/miner.cpp
index ec87e84ca7..ef8fd4db43 100644
--- a/src/miner.cpp
+++ b/src/miner.cpp
@@ -79,11 +79,6 @@ CBlockTemplate* CreateNewBlock(const CChainParams& chainparams, const CScript& s
         return NULL;
     CBlock *pblock = &pblocktemplate->block; // pointer for convenience
 
-    // -regtest only: allow overriding block.nVersion with
-    // -blockversion=N to test forking scenarios
-    if (chainparams.MineBlocksOnDemand())
-        pblock->nVersion = GetArg("-blockversion", pblock->nVersion);
-
     // Create coinbase tx
     CMutableTransaction txNew;
     txNew.vin.resize(1);
@@ -137,6 +132,12 @@ CBlockTemplate* CreateNewBlock(const CChainParams& chainparams, const CScript& s
         pblock->nTime = GetAdjustedTime();
         const int64_t nMedianTimePast = pindexPrev->GetMedianTimePast();
 
+        pblock->nVersion = ComputeBlockVersion(pindexPrev, chainparams.GetConsensus());
+        // -regtest only: allow overriding block.nVersion with
+        // -blockversion=N to test forking scenarios
+        if (chainparams.MineBlocksOnDemand())
+            pblock->nVersion = GetArg("-blockversion", pblock->nVersion);
+
         int64_t nLockTimeCutoff = (STANDARD_LOCKTIME_VERIFY_FLAGS & LOCKTIME_MEDIAN_TIME_PAST)
                                 ? nMedianTimePast
                                 : pblock->GetBlockTime();
diff --git a/src/primitives/block.h b/src/primitives/block.h
index 0e93399c08..42276b2bc2 100644
--- a/src/primitives/block.h
+++ b/src/primitives/block.h
@@ -21,7 +21,6 @@ class CBlockHeader
 {
 public:
     // header
-    static const int32_t CURRENT_VERSION=4;
     int32_t nVersion;
     uint256 hashPrevBlock;
     uint256 hashMerkleRoot;
@@ -49,7 +48,7 @@ public:
 
     void SetNull()
     {
-        nVersion = CBlockHeader::CURRENT_VERSION;
+        nVersion = 0;
         hashPrevBlock.SetNull();
         hashMerkleRoot.SetNull();
         nTime = 0;
diff --git a/src/rpc/blockchain.cpp b/src/rpc/blockchain.cpp
index da57973dae..a110dff0d1 100644
--- a/src/rpc/blockchain.cpp
+++ b/src/rpc/blockchain.cpp
@@ -604,6 +604,20 @@ static UniValue SoftForkDesc(const std::string &name, int version, CBlockIndex*
     return rv;
 }
 
+static UniValue BIP9SoftForkDesc(const std::string& name, const Consensus::Params& consensusParams, Consensus::DeploymentPos id)
+{
+    UniValue rv(UniValue::VOBJ);
+    rv.push_back(Pair("id", name));
+    switch (VersionBitsTipState(consensusParams, id)) {
+    case THRESHOLD_DEFINED: rv.push_back(Pair("status", "defined")); break;
+    case THRESHOLD_STARTED: rv.push_back(Pair("status", "started")); break;
+    case THRESHOLD_LOCKED_IN: rv.push_back(Pair("status", "locked_in")); break;
+    case THRESHOLD_ACTIVE: rv.push_back(Pair("status", "active")); break;
+    case THRESHOLD_FAILED: rv.push_back(Pair("status", "failed")); break;
+    }
+    return rv;
+}
+
 UniValue getblockchaininfo(const UniValue& params, bool fHelp)
 {
     if (fHelp || params.size() != 0)
@@ -634,6 +648,12 @@ UniValue getblockchaininfo(const UniValue& params, bool fHelp)
             "        },\n"
             "        \"reject\": { ... }      (object) progress toward rejecting pre-softfork blocks (same fields as \"enforce\")\n"
             "     }, ...\n"
+            "  ],\n"
+            "  \"bip9_softforks\": [       (array) status of BIP9 softforks in progress\n"
+            "     {\n"
+            "        \"id\": \"xxxx\",        (string) name of the softfork\n"
+            "        \"status\": \"xxxx\",    (string) one of \"defined\", \"started\", \"lockedin\", \"active\", \"failed\"\n"
+            "     }\n"
             "  ]\n"
             "}\n"
             "\nExamples:\n"
@@ -657,10 +677,12 @@ UniValue getblockchaininfo(const UniValue& params, bool fHelp)
     const Consensus::Params& consensusParams = Params().GetConsensus();
     CBlockIndex* tip = chainActive.Tip();
     UniValue softforks(UniValue::VARR);
+    UniValue bip9_softforks(UniValue::VARR);
     softforks.push_back(SoftForkDesc("bip34", 2, tip, consensusParams));
     softforks.push_back(SoftForkDesc("bip66", 3, tip, consensusParams));
     softforks.push_back(SoftForkDesc("bip65", 4, tip, consensusParams));
     obj.push_back(Pair("softforks",             softforks));
+    obj.push_back(Pair("bip9_softforks", bip9_softforks));
 
     if (fPruneMode)
     {
diff --git a/src/test/miner_tests.cpp b/src/test/miner_tests.cpp
index f3297e074d..ab6485081c 100644
--- a/src/test/miner_tests.cpp
+++ b/src/test/miner_tests.cpp
@@ -247,13 +247,40 @@ BOOST_AUTO_TEST_CASE(CreateNewBlock_validity)
 
     // subsidy changing
     int nHeight = chainActive.Height();
-    chainActive.Tip()->nHeight = 209999;
+    // Create an actual 209999-long block chain (without valid blocks).
+    while (chainActive.Tip()->nHeight < 209999) {
+        CBlockIndex* prev = chainActive.Tip();
+        CBlockIndex* next = new CBlockIndex();
+        next->phashBlock = new uint256(GetRandHash());
+        pcoinsTip->SetBestBlock(next->GetBlockHash());
+        next->pprev = prev;
+        next->nHeight = prev->nHeight + 1;
+        next->BuildSkip();
+        chainActive.SetTip(next);
+    }
     BOOST_CHECK(pblocktemplate = CreateNewBlock(chainparams, scriptPubKey));
     delete pblocktemplate;
-    chainActive.Tip()->nHeight = 210000;
+    // Extend to a 210000-long block chain.
+    while (chainActive.Tip()->nHeight < 210000) {
+        CBlockIndex* prev = chainActive.Tip();
+        CBlockIndex* next = new CBlockIndex();
+        next->phashBlock = new uint256(GetRandHash());
+        pcoinsTip->SetBestBlock(next->GetBlockHash());
+        next->pprev = prev;
+        next->nHeight = prev->nHeight + 1;
+        next->BuildSkip();
+        chainActive.SetTip(next);
+    }
     BOOST_CHECK(pblocktemplate = CreateNewBlock(chainparams, scriptPubKey));
     delete pblocktemplate;
-    chainActive.Tip()->nHeight = nHeight;
+    // Delete the dummy blocks again.
+    while (chainActive.Tip()->nHeight > nHeight) {
+        CBlockIndex* del = chainActive.Tip();
+        chainActive.SetTip(del->pprev);
+        pcoinsTip->SetBestBlock(del->pprev->GetBlockHash());
+        delete del->phashBlock;
+        delete del;
+    }
 
     // non-final txs in mempool
     SetMockTime(chainActive.Tip()->GetMedianTimePast()+1);
diff --git a/src/test/versionbits_tests.cpp b/src/test/versionbits_tests.cpp
new file mode 100644
index 0000000000..1f86a06a3f
--- /dev/null
+++ b/src/test/versionbits_tests.cpp
@@ -0,0 +1,316 @@
+// 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.
+
+#include "chain.h"
+#include "random.h"
+#include "versionbits.h"
+#include "test/test_bitcoin.h"
+#include "chainparams.h"
+#include "main.h"
+#include "consensus/params.h"
+
+#include <boost/test/unit_test.hpp>
+
+/* Define a virtual block time, one block per 10 minutes after Nov 14 2014, 0:55:36am */
+int32_t TestTime(int nHeight) { return 1415926536 + 600 * nHeight; }
+
+static const Consensus::Params paramsDummy = Consensus::Params();
+
+class TestConditionChecker : public AbstractThresholdConditionChecker
+{
+private:
+    mutable ThresholdConditionCache cache;
+
+public:
+    int64_t BeginTime(const Consensus::Params& params) const { return TestTime(10000); }
+    int64_t EndTime(const Consensus::Params& params) const { return TestTime(20000); }
+    int Period(const Consensus::Params& params) const { return 1000; }
+    int Threshold(const Consensus::Params& params) const { return 900; }
+    bool Condition(const CBlockIndex* pindex, const Consensus::Params& params) const { return (pindex->nVersion & 0x100); }
+
+    ThresholdState GetStateFor(const CBlockIndex* pindexPrev) const { return AbstractThresholdConditionChecker::GetStateFor(pindexPrev, paramsDummy, cache); }
+};
+
+#define CHECKERS 6
+
+class VersionBitsTester
+{
+    // A fake blockchain
+    std::vector<CBlockIndex*> vpblock;
+
+    // 6 independent checkers for the same bit.
+    // The first one performs all checks, the second only 50%, the third only 25%, etc...
+    // This is to test whether lack of cached information leads to the same results.
+    TestConditionChecker checker[CHECKERS];
+
+    // Test counter (to identify failures)
+    int num;
+
+public:
+    VersionBitsTester() : num(0) {}
+
+    VersionBitsTester& Reset() {
+        for (unsigned int i = 0; i < vpblock.size(); i++) {
+            delete vpblock[i];
+        }
+        for (unsigned int  i = 0; i < CHECKERS; i++) {
+            checker[i] = TestConditionChecker();
+        }
+        vpblock.clear();
+        return *this;
+    }
+
+    ~VersionBitsTester() {
+         Reset();
+    }
+
+    VersionBitsTester& Mine(unsigned int height, int32_t nTime, int32_t nVersion) {
+        while (vpblock.size() < height) {
+            CBlockIndex* pindex = new CBlockIndex();
+            pindex->nHeight = vpblock.size();
+            pindex->pprev = vpblock.size() > 0 ? vpblock.back() : NULL;
+            pindex->nTime = nTime;
+            pindex->nVersion = nVersion;
+            pindex->BuildSkip();
+            vpblock.push_back(pindex);
+        }
+        return *this;
+    }
+
+    VersionBitsTester& TestDefined() {
+        for (int i = 0; i < CHECKERS; i++) {
+            if ((insecure_rand() & ((1 << i) - 1)) == 0) {
+                BOOST_CHECK_MESSAGE(checker[i].GetStateFor(vpblock.empty() ? NULL : vpblock.back()) == THRESHOLD_DEFINED, strprintf("Test %i for DEFINED", num));
+            }
+        }
+        num++;
+        return *this;
+    }
+
+    VersionBitsTester& TestStarted() {
+        for (int i = 0; i < CHECKERS; i++) {
+            if ((insecure_rand() & ((1 << i) - 1)) == 0) {
+                BOOST_CHECK_MESSAGE(checker[i].GetStateFor(vpblock.empty() ? NULL : vpblock.back()) == THRESHOLD_STARTED, strprintf("Test %i for STARTED", num));
+            }
+        }
+        num++;
+        return *this;
+    }
+
+    VersionBitsTester& TestLockedIn() {
+        for (int i = 0; i < CHECKERS; i++) {
+            if ((insecure_rand() & ((1 << i) - 1)) == 0) {
+                BOOST_CHECK_MESSAGE(checker[i].GetStateFor(vpblock.empty() ? NULL : vpblock.back()) == THRESHOLD_LOCKED_IN, strprintf("Test %i for LOCKED_IN", num));
+            }
+        }
+        num++;
+        return *this;
+    }
+
+    VersionBitsTester& TestActive() {
+        for (int i = 0; i < CHECKERS; i++) {
+            if ((insecure_rand() & ((1 << i) - 1)) == 0) {
+                BOOST_CHECK_MESSAGE(checker[i].GetStateFor(vpblock.empty() ? NULL : vpblock.back()) == THRESHOLD_ACTIVE, strprintf("Test %i for ACTIVE", num));
+            }
+        }
+        num++;
+        return *this;
+    }
+
+    VersionBitsTester& TestFailed() {
+        for (int i = 0; i < CHECKERS; i++) {
+            if ((insecure_rand() & ((1 << i) - 1)) == 0) {
+                BOOST_CHECK_MESSAGE(checker[i].GetStateFor(vpblock.empty() ? NULL : vpblock.back()) == THRESHOLD_FAILED, strprintf("Test %i for FAILED", num));
+            }
+        }
+        num++;
+        return *this;
+    }
+
+    CBlockIndex * Tip() { return vpblock.size() ? vpblock.back() : NULL; }
+};
+
+BOOST_FIXTURE_TEST_SUITE(versionbits_tests, TestingSetup)
+
+BOOST_AUTO_TEST_CASE(versionbits_test)
+{
+    for (int i = 0; i < 64; i++) {
+        // DEFINED -> FAILED
+        VersionBitsTester().TestDefined()
+                           .Mine(1, TestTime(1), 0x100).TestDefined()
+                           .Mine(11, TestTime(11), 0x100).TestDefined()
+                           .Mine(989, TestTime(989), 0x100).TestDefined()
+                           .Mine(999, TestTime(20000), 0x100).TestDefined()
+                           .Mine(1000, TestTime(20000), 0x100).TestFailed()
+                           .Mine(1999, TestTime(30001), 0x100).TestFailed()
+                           .Mine(2000, TestTime(30002), 0x100).TestFailed()
+                           .Mine(2001, TestTime(30003), 0x100).TestFailed()
+                           .Mine(2999, TestTime(30004), 0x100).TestFailed()
+                           .Mine(3000, TestTime(30005), 0x100).TestFailed()
+
+        // DEFINED -> STARTED -> FAILED
+                           .Reset().TestDefined()
+                           .Mine(1, TestTime(1), 0).TestDefined()
+                           .Mine(1000, TestTime(10000) - 1, 0x100).TestDefined() // One second more and it would be defined
+                           .Mine(2000, TestTime(10000), 0x100).TestStarted() // So that's what happens the next period
+                           .Mine(2051, TestTime(10010), 0).TestStarted() // 51 old blocks
+                           .Mine(2950, TestTime(10020), 0x100).TestStarted() // 899 new blocks
+                           .Mine(3000, TestTime(20000), 0).TestFailed() // 50 old blocks (so 899 out of the past 1000)
+                           .Mine(4000, TestTime(20010), 0x100).TestFailed()
+
+        // DEFINED -> STARTED -> FAILED while threshold reached
+                           .Reset().TestDefined()
+                           .Mine(1, TestTime(1), 0).TestDefined()
+                           .Mine(1000, TestTime(10000) - 1, 0x101).TestDefined() // One second more and it would be defined
+                           .Mine(2000, TestTime(10000), 0x101).TestStarted() // So that's what happens the next period
+                           .Mine(2999, TestTime(30000), 0x100).TestStarted() // 999 new blocks
+                           .Mine(3000, TestTime(30000), 0x100).TestFailed() // 1 new block (so 1000 out of the past 1000 are new)
+                           .Mine(3999, TestTime(30001), 0).TestFailed()
+                           .Mine(4000, TestTime(30002), 0).TestFailed()
+                           .Mine(14333, TestTime(30003), 0).TestFailed()
+                           .Mine(24000, TestTime(40000), 0).TestFailed()
+
+        // DEFINED -> STARTED -> LOCKEDIN at the last minute -> ACTIVE
+                           .Reset().TestDefined()
+                           .Mine(1, TestTime(1), 0).TestDefined()
+                           .Mine(1000, TestTime(10000) - 1, 0x101).TestDefined() // One second more and it would be defined
+                           .Mine(2000, TestTime(10000), 0x101).TestStarted() // So that's what happens the next period
+                           .Mine(2050, TestTime(10010), 0x200).TestStarted() // 50 old blocks
+                           .Mine(2950, TestTime(10020), 0x100).TestStarted() // 900 new blocks
+                           .Mine(2999, TestTime(19999), 0x200).TestStarted() // 49 old blocks
+                           .Mine(3000, TestTime(29999), 0x200).TestLockedIn() // 1 old block (so 900 out of the past 1000)
+                           .Mine(3999, TestTime(30001), 0).TestLockedIn()
+                           .Mine(4000, TestTime(30002), 0).TestActive()
+                           .Mine(14333, TestTime(30003), 0).TestActive()
+                           .Mine(24000, TestTime(40000), 0).TestActive();
+    }
+
+    // Sanity checks of version bit deployments
+    const Consensus::Params &mainnetParams = Params(CBaseChainParams::MAIN).GetConsensus();
+    for (int i=0; i<(int) Consensus::MAX_VERSION_BITS_DEPLOYMENTS; i++) {
+        uint32_t bitmask = VersionBitsMask(mainnetParams, (Consensus::DeploymentPos)i);
+        // Make sure that no deployment tries to set an invalid bit.
+        BOOST_CHECK_EQUAL(bitmask & ~(uint32_t)VERSIONBITS_TOP_MASK, bitmask);
+
+        // Verify that the deployment windows of different deployment using the
+        // same bit are disjoint.
+        // This test may need modification at such time as a new deployment
+        // is proposed that reuses the bit of an activated soft fork, before the
+        // end time of that soft fork.  (Alternatively, the end time of that
+        // activated soft fork could be later changed to be earlier to avoid
+        // overlap.)
+        for (int j=i+1; j<(int) Consensus::MAX_VERSION_BITS_DEPLOYMENTS; j++) {
+            if (VersionBitsMask(mainnetParams, (Consensus::DeploymentPos)j) == bitmask) {
+                BOOST_CHECK(mainnetParams.vDeployments[j].nStartTime > mainnetParams.vDeployments[i].nTimeout ||
+                        mainnetParams.vDeployments[i].nStartTime > mainnetParams.vDeployments[j].nTimeout);
+            }
+        }
+    }
+}
+
+BOOST_AUTO_TEST_CASE(versionbits_computeblockversion)
+{
+    // Check that ComputeBlockVersion will set the appropriate bit correctly
+    // on mainnet.
+    const Consensus::Params &mainnetParams = Params(CBaseChainParams::MAIN).GetConsensus();
+
+    // Use the TESTDUMMY deployment for testing purposes.
+    int64_t bit = mainnetParams.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].bit;
+    int64_t nStartTime = mainnetParams.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nStartTime;
+    int64_t nTimeout = mainnetParams.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nTimeout;
+
+    assert(nStartTime < nTimeout);
+
+    // In the first chain, test that the bit is set by CBV until it has failed.
+    // In the second chain, test the bit is set by CBV while STARTED and
+    // LOCKED-IN, and then no longer set while ACTIVE.
+    VersionBitsTester firstChain, secondChain;
+
+    // Start generating blocks before nStartTime
+    int64_t nTime = nStartTime - 1;
+
+    // Before MedianTimePast of the chain has crossed nStartTime, the bit
+    // should not be set.
+    CBlockIndex *lastBlock = NULL;
+    lastBlock = firstChain.Mine(2016, nTime, VERSIONBITS_LAST_OLD_BLOCK_VERSION).Tip();
+    BOOST_CHECK_EQUAL(ComputeBlockVersion(lastBlock, mainnetParams) & (1<<bit), 0);
+
+    // Mine 2011 more blocks at the old time, and check that CBV isn't setting the bit yet.
+    for (int i=1; i<2012; i++) {
+        lastBlock = firstChain.Mine(2016+i, nTime, VERSIONBITS_LAST_OLD_BLOCK_VERSION).Tip();
+        // This works because VERSIONBITS_LAST_OLD_BLOCK_VERSION happens
+        // to be 4, and the bit we're testing happens to be bit 28.
+        BOOST_CHECK_EQUAL(ComputeBlockVersion(lastBlock, mainnetParams) & (1<<bit), 0);
+    }
+    // Now mine 5 more blocks at the start time -- MTP should not have passed yet, so
+    // CBV should still not yet set the bit.
+    nTime = nStartTime;
+    for (int i=2012; i<=2016; i++) {
+        lastBlock = firstChain.Mine(2016+i, nTime, VERSIONBITS_LAST_OLD_BLOCK_VERSION).Tip();
+        BOOST_CHECK_EQUAL(ComputeBlockVersion(lastBlock, mainnetParams) & (1<<bit), 0);
+    }
+
+    // Advance to the next period and transition to STARTED,
+    lastBlock = firstChain.Mine(6048, nTime, VERSIONBITS_LAST_OLD_BLOCK_VERSION).Tip();
+    // so ComputeBlockVersion should now set the bit,
+    BOOST_CHECK((ComputeBlockVersion(lastBlock, mainnetParams) & (1<<bit)) != 0);
+    // and should also be using the VERSIONBITS_TOP_BITS.
+    BOOST_CHECK_EQUAL(ComputeBlockVersion(lastBlock, mainnetParams) & VERSIONBITS_TOP_MASK, VERSIONBITS_TOP_BITS);
+
+    // Check that ComputeBlockVersion will set the bit until nTimeout
+    nTime += 600;
+    int blocksToMine = 4032; // test blocks for up to 2 time periods
+    int nHeight = 6048;
+    // These blocks are all before nTimeout is reached.
+    while (nTime < nTimeout && blocksToMine > 0) {
+        lastBlock = firstChain.Mine(nHeight+1, nTime, VERSIONBITS_LAST_OLD_BLOCK_VERSION).Tip();
+        BOOST_CHECK((ComputeBlockVersion(lastBlock, mainnetParams) & (1<<bit)) != 0);
+        BOOST_CHECK_EQUAL(ComputeBlockVersion(lastBlock, mainnetParams) & VERSIONBITS_TOP_MASK, VERSIONBITS_TOP_BITS);
+        blocksToMine--;
+        nTime += 600;
+        nHeight += 1;
+    };
+
+    nTime = nTimeout;
+    // FAILED is only triggered at the end of a period, so CBV should be setting
+    // the bit until the period transition.
+    for (int i=0; i<2015; i++) {
+        lastBlock = firstChain.Mine(nHeight+1, nTime, VERSIONBITS_LAST_OLD_BLOCK_VERSION).Tip();
+        BOOST_CHECK((ComputeBlockVersion(lastBlock, mainnetParams) & (1<<bit)) != 0);
+        nHeight += 1;
+    }
+    // The next block should trigger no longer setting the bit.
+    lastBlock = firstChain.Mine(nHeight+1, nTime, VERSIONBITS_LAST_OLD_BLOCK_VERSION).Tip();
+    BOOST_CHECK_EQUAL(ComputeBlockVersion(lastBlock, mainnetParams) & (1<<bit), 0);
+
+    // On a new chain:
+    // verify that the bit will be set after lock-in, and then stop being set
+    // after activation.
+    nTime = nStartTime;
+
+    // Mine one period worth of blocks, and check that the bit will be on for the
+    // next period.
+    lastBlock = secondChain.Mine(2016, nStartTime, VERSIONBITS_LAST_OLD_BLOCK_VERSION).Tip();
+    BOOST_CHECK((ComputeBlockVersion(lastBlock, mainnetParams) & (1<<bit)) != 0);
+
+    // Mine another period worth of blocks, signaling the new bit.
+    lastBlock = secondChain.Mine(4032, nStartTime, VERSIONBITS_TOP_BITS | (1<<bit)).Tip();
+    // After one period of setting the bit on each block, it should have locked in.
+    // We keep setting the bit for one more period though, until activation.
+    BOOST_CHECK((ComputeBlockVersion(lastBlock, mainnetParams) & (1<<bit)) != 0);
+
+    // Now check that we keep mining the block until the end of this period, and
+    // then stop at the beginning of the next period.
+    lastBlock = secondChain.Mine(6047, nStartTime, VERSIONBITS_LAST_OLD_BLOCK_VERSION).Tip();
+    BOOST_CHECK((ComputeBlockVersion(lastBlock, mainnetParams) & (1<<bit)) != 0);
+    lastBlock = secondChain.Mine(6048, nStartTime, VERSIONBITS_LAST_OLD_BLOCK_VERSION).Tip();
+    BOOST_CHECK_EQUAL(ComputeBlockVersion(lastBlock, mainnetParams) & (1<<bit), 0);
+
+    // Finally, verify that after a soft fork has activated, CBV no longer uses
+    // VERSIONBITS_LAST_OLD_BLOCK_VERSION.
+    //BOOST_CHECK_EQUAL(ComputeBlockVersion(lastBlock, mainnetParams) & VERSIONBITS_TOP_MASK, VERSIONBITS_TOP_BITS);
+}
+
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/versionbits.cpp b/src/versionbits.cpp
new file mode 100644
index 0000000000..fbb60c0fc5
--- /dev/null
+++ b/src/versionbits.cpp
@@ -0,0 +1,133 @@
+// Copyright (c) 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.
+
+#include "versionbits.h"
+
+ThresholdState AbstractThresholdConditionChecker::GetStateFor(const CBlockIndex* pindexPrev, const Consensus::Params& params, ThresholdConditionCache& cache) const
+{
+    int nPeriod = Period(params);
+    int nThreshold = Threshold(params);
+    int64_t nTimeStart = BeginTime(params);
+    int64_t nTimeTimeout = EndTime(params);
+
+    // A block's state is always the same as that of the first of its period, so it is computed based on a pindexPrev whose height equals a multiple of nPeriod - 1.
+    if (pindexPrev != NULL) {
+        pindexPrev = pindexPrev->GetAncestor(pindexPrev->nHeight - ((pindexPrev->nHeight + 1) % nPeriod));
+    }
+
+    // Walk backwards in steps of nPeriod to find a pindexPrev whose information is known
+    std::vector<const CBlockIndex*> vToCompute;
+    while (cache.count(pindexPrev) == 0) {
+        if (pindexPrev == NULL) {
+            // The genesis block is by definition defined.
+            cache[pindexPrev] = THRESHOLD_DEFINED;
+            break;
+        }
+        if (pindexPrev->GetMedianTimePast() < nTimeStart) {
+            // Optimizaton: don't recompute down further, as we know every earlier block will be before the start time
+            cache[pindexPrev] = THRESHOLD_DEFINED;
+            break;
+        }
+        vToCompute.push_back(pindexPrev);
+        pindexPrev = pindexPrev->GetAncestor(pindexPrev->nHeight - nPeriod);
+    }
+
+    // At this point, cache[pindexPrev] is known
+    assert(cache.count(pindexPrev));
+    ThresholdState state = cache[pindexPrev];
+
+    // Now walk forward and compute the state of descendants of pindexPrev
+    while (!vToCompute.empty()) {
+        ThresholdState stateNext = state;
+        pindexPrev = vToCompute.back();
+        vToCompute.pop_back();
+
+        switch (state) {
+            case THRESHOLD_DEFINED: {
+                if (pindexPrev->GetMedianTimePast() >= nTimeTimeout) {
+                    stateNext = THRESHOLD_FAILED;
+                } else if (pindexPrev->GetMedianTimePast() >= nTimeStart) {
+                    stateNext = THRESHOLD_STARTED;
+                }
+                break;
+            }
+            case THRESHOLD_STARTED: {
+                if (pindexPrev->GetMedianTimePast() >= nTimeTimeout) {
+                    stateNext = THRESHOLD_FAILED;
+                    break;
+                }
+                // We need to count
+                const CBlockIndex* pindexCount = pindexPrev;
+                int count = 0;
+                for (int i = 0; i < nPeriod; i++) {
+                    if (Condition(pindexCount, params)) {
+                        count++;
+                    }
+                    pindexCount = pindexCount->pprev;
+                }
+                if (count >= nThreshold) {
+                    stateNext = THRESHOLD_LOCKED_IN;
+                }
+                break;
+            }
+            case THRESHOLD_LOCKED_IN: {
+                // Always progresses into ACTIVE.
+                stateNext = THRESHOLD_ACTIVE;
+                break;
+            }
+            case THRESHOLD_FAILED:
+            case THRESHOLD_ACTIVE: {
+                // Nothing happens, these are terminal states.
+                break;
+            }
+        }
+        cache[pindexPrev] = state = stateNext;
+    }
+
+    return state;
+}
+
+namespace
+{
+/**
+ * Class to implement versionbits logic.
+ */
+class VersionBitsConditionChecker : public AbstractThresholdConditionChecker {
+private:
+    const Consensus::DeploymentPos id;
+
+protected:
+    int64_t BeginTime(const Consensus::Params& params) const { return params.vDeployments[id].nStartTime; }
+    int64_t EndTime(const Consensus::Params& params) const { return params.vDeployments[id].nTimeout; }
+    int Period(const Consensus::Params& params) const { return params.nMinerConfirmationWindow; }
+    int Threshold(const Consensus::Params& params) const { return params.nRuleChangeActivationThreshold; }
+
+    bool Condition(const CBlockIndex* pindex, const Consensus::Params& params) const
+    {
+        return (((pindex->nVersion & VERSIONBITS_TOP_MASK) == VERSIONBITS_TOP_BITS) && (pindex->nVersion & Mask(params)) != 0);
+    }
+
+public:
+    VersionBitsConditionChecker(Consensus::DeploymentPos id_) : id(id_) {}
+    uint32_t Mask(const Consensus::Params& params) const { return ((uint32_t)1) << params.vDeployments[id].bit; }
+};
+
+}
+
+ThresholdState VersionBitsState(const CBlockIndex* pindexPrev, const Consensus::Params& params, Consensus::DeploymentPos pos, VersionBitsCache& cache)
+{
+    return VersionBitsConditionChecker(pos).GetStateFor(pindexPrev, params, cache.caches[pos]);
+}
+
+uint32_t VersionBitsMask(const Consensus::Params& params, Consensus::DeploymentPos pos)
+{
+    return VersionBitsConditionChecker(pos).Mask(params);
+}
+
+void VersionBitsCache::Clear()
+{
+    for (unsigned int d = 0; d < Consensus::MAX_VERSION_BITS_DEPLOYMENTS; d++) {
+        caches[d].clear();
+    }
+}
diff --git a/src/versionbits.h b/src/versionbits.h
new file mode 100644
index 0000000000..04f4738272
--- /dev/null
+++ b/src/versionbits.h
@@ -0,0 +1,59 @@
+// Copyright (c) 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.
+
+#ifndef BITCOIN_CONSENSUS_VERSIONBITS
+#define BITCOIN_CONSENSUS_VERSIONBITS
+
+#include "chain.h"
+#include <map>
+
+/** What block version to use for new blocks (pre versionbits) */
+static const int32_t VERSIONBITS_LAST_OLD_BLOCK_VERSION = 4;
+/** What bits to set in version for versionbits blocks */
+static const int32_t VERSIONBITS_TOP_BITS = 0x20000000UL;
+/** What bitmask determines whether versionbits is in use */
+static const int32_t VERSIONBITS_TOP_MASK = 0xE0000000UL;
+/** Total bits available for versionbits */
+static const int32_t VERSIONBITS_NUM_BITS = 29;
+
+enum ThresholdState {
+    THRESHOLD_DEFINED,
+    THRESHOLD_STARTED,
+    THRESHOLD_LOCKED_IN,
+    THRESHOLD_ACTIVE,
+    THRESHOLD_FAILED,
+};
+
+// A map that gives the state for blocks whose height is a multiple of Period().
+// The map is indexed by the block's parent, however, so all keys in the map
+// will either be NULL or a block with (height + 1) % Period() == 0.
+typedef std::map<const CBlockIndex*, ThresholdState> ThresholdConditionCache;
+
+/**
+ * Abstract class that implements BIP9-style threshold logic, and caches results.
+ */
+class AbstractThresholdConditionChecker {
+protected:
+    virtual bool Condition(const CBlockIndex* pindex, const Consensus::Params& params) const =0;
+    virtual int64_t BeginTime(const Consensus::Params& params) const =0;
+    virtual int64_t EndTime(const Consensus::Params& params) const =0;
+    virtual int Period(const Consensus::Params& params) const =0;
+    virtual int Threshold(const Consensus::Params& params) const =0;
+
+public:
+    // Note that the function below takes a pindexPrev as input: they compute information for block B based on its parent.
+    ThresholdState GetStateFor(const CBlockIndex* pindexPrev, const Consensus::Params& params, ThresholdConditionCache& cache) const;
+};
+
+struct VersionBitsCache
+{
+    ThresholdConditionCache caches[Consensus::MAX_VERSION_BITS_DEPLOYMENTS];
+
+    void Clear();
+};
+
+ThresholdState VersionBitsState(const CBlockIndex* pindexPrev, const Consensus::Params& params, Consensus::DeploymentPos pos, VersionBitsCache& cache);
+uint32_t VersionBitsMask(const Consensus::Params& params, Consensus::DeploymentPos pos);
+
+#endif