Merge #7184: Implement SequenceLocks functions for BIP 68

b043c4b fix sdaftuar's nits again (Alex Morcos)
a51c79b Bug fix to RPC test (Alex Morcos)
da6ad5f Add RPC test exercising BIP68 (mempool only) (Suhas Daftuar)
c6c2f0f Implement SequenceLocks functions (Alex Morcos)

12 files changed, 696 insertions, 50 deletions

diff --git a/qa/rpc-tests/bip68-sequence.py b/qa/rpc-tests/bip68-sequence.py
new file mode 100755
index 0000000000..bd61282fa1
--- /dev/null
+++ b/qa/rpc-tests/bip68-sequence.py
@@ -0,0 +1,387 @@
+#!/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.
+
+#
+# Test BIP68 implementation (mempool only)
+#
+
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.util import *
+from test_framework.script import *
+from test_framework.mininode import *
+from test_framework.blocktools import *
+
+COIN = 100000000
+SEQUENCE_LOCKTIME_DISABLE_FLAG = (1<<31)
+SEQUENCE_LOCKTIME_TYPE_FLAG = (1<<22) # this means use time (0 means height)
+SEQUENCE_LOCKTIME_GRANULARITY = 9 # this is a bit-shift
+SEQUENCE_LOCKTIME_MASK = 0x0000ffff
+
+# RPC error for non-BIP68 final transactions
+NOT_FINAL_ERROR = "64: non-BIP68-final"
+
+class BIP68Test(BitcoinTestFramework):
+
+    def setup_network(self):
+        self.nodes = []
+        self.nodes.append(start_node(0, self.options.tmpdir, ["-debug", "-blockprioritysize=0"]))
+        self.is_network_split = False
+        self.relayfee = self.nodes[0].getnetworkinfo()["relayfee"]
+
+    def run_test(self):
+        # Generate some coins
+        self.nodes[0].generate(110)
+
+        print "Running test disable flag"
+        self.test_disable_flag()
+
+        print "Running test sequence-lock-confirmed-inputs"
+        self.test_sequence_lock_confirmed_inputs()
+
+        print "Running test sequence-lock-unconfirmed-inputs"
+        self.test_sequence_lock_unconfirmed_inputs()
+
+        # This test needs to change when BIP68 becomes consensus
+        print "Running test BIP68 not consensus"
+        self.test_bip68_not_consensus()
+
+        print "Passed\n"
+
+    # Test that BIP68 is not in effect if tx version is 1, or if
+    # the first sequence bit is set.
+    def test_disable_flag(self):
+        # Create some unconfirmed inputs
+        new_addr = self.nodes[0].getnewaddress()
+        self.nodes[0].sendtoaddress(new_addr, 2) # send 2 BTC
+
+        utxos = self.nodes[0].listunspent(0, 0)
+        assert(len(utxos) > 0)
+
+        utxo = utxos[0]
+
+        tx1 = CTransaction()
+        value = satoshi_round(utxo["amount"] - self.relayfee)*COIN
+
+        # Check that the disable flag disables relative locktime.
+        # If sequence locks were used, this would require 1 block for the
+        # input to mature.
+        sequence_value = SEQUENCE_LOCKTIME_DISABLE_FLAG | 1
+        tx1.vin = [CTxIn(COutPoint(int(utxo["txid"], 16), utxo["vout"]), nSequence=sequence_value)] 
+        tx1.vout = [CTxOut(value, CScript([b'a']))]
+
+        tx1_signed = self.nodes[0].signrawtransaction(ToHex(tx1))["hex"]
+        tx1_id = self.nodes[0].sendrawtransaction(tx1_signed)
+        tx1_id = int(tx1_id, 16)
+
+        # This transaction will enable sequence-locks, so this transaction should
+        # fail
+        tx2 = CTransaction()
+        tx2.nVersion = 2
+        sequence_value = sequence_value & 0x7fffffff
+        tx2.vin = [CTxIn(COutPoint(tx1_id, 0), nSequence=sequence_value)]
+        tx2.vout = [CTxOut(int(value-self.relayfee*COIN), CScript([b'a']))]
+        tx2.rehash()
+
+        try:
+            self.nodes[0].sendrawtransaction(ToHex(tx2))
+        except JSONRPCException as exp:
+            assert_equal(exp.error["message"], NOT_FINAL_ERROR)
+        else:
+            assert(False)
+
+        # Setting the version back down to 1 should disable the sequence lock,
+        # so this should be accepted.
+        tx2.nVersion = 1
+
+        self.nodes[0].sendrawtransaction(ToHex(tx2))
+
+    # Calculate the median time past of a prior block ("confirmations" before
+    # the current tip).
+    def get_median_time_past(self, confirmations):
+        block_hash = self.nodes[0].getblockhash(self.nodes[0].getblockcount()-confirmations)
+        return self.nodes[0].getblockheader(block_hash)["mediantime"]
+
+    # Test that sequence locks are respected for transactions spending confirmed inputs.
+    def test_sequence_lock_confirmed_inputs(self):
+        # Create lots of confirmed utxos, and use them to generate lots of random
+        # transactions.
+        max_outputs = 50
+        addresses = []
+        while len(addresses) < max_outputs:
+            addresses.append(self.nodes[0].getnewaddress())
+        while len(self.nodes[0].listunspent()) < 200:
+            import random
+            random.shuffle(addresses)
+            num_outputs = random.randint(1, max_outputs)
+            outputs = {}
+            for i in xrange(num_outputs):
+                outputs[addresses[i]] = random.randint(1, 20)*0.01
+            self.nodes[0].sendmany("", outputs)
+            self.nodes[0].generate(1)
+
+        utxos = self.nodes[0].listunspent()
+
+        # Try creating a lot of random transactions.
+        # Each time, choose a random number of inputs, and randomly set
+        # some of those inputs to be sequence locked (and randomly choose
+        # between height/time locking). Small random chance of making the locks
+        # all pass.
+        for i in xrange(400):
+            # Randomly choose up to 10 inputs
+            num_inputs = random.randint(1, 10)
+            random.shuffle(utxos)
+
+            # Track whether any sequence locks used should fail
+            should_pass = True
+            
+            # Track whether this transaction was built with sequence locks
+            using_sequence_locks = False
+
+            tx = CTransaction()
+            tx.nVersion = 2
+            value = 0
+            for j in xrange(num_inputs):
+                sequence_value = 0xfffffffe # this disables sequence locks
+
+                # 50% chance we enable sequence locks
+                if random.randint(0,1):
+                    using_sequence_locks = True
+
+                    # 10% of the time, make the input sequence value pass
+                    input_will_pass = (random.randint(1,10) == 1)
+                    sequence_value = utxos[j]["confirmations"]
+                    if not input_will_pass:
+                        sequence_value += 1
+                        should_pass = False
+
+                    # Figure out what the median-time-past was for the confirmed input
+                    # Note that if an input has N confirmations, we're going back N blocks
+                    # from the tip so that we're looking up MTP of the block
+                    # PRIOR to the one the input appears in, as per the BIP68 spec.
+                    orig_time = self.get_median_time_past(utxos[j]["confirmations"])
+                    cur_time = self.get_median_time_past(0) # MTP of the tip
+
+                    # can only timelock this input if it's not too old -- otherwise use height
+                    can_time_lock = True
+                    if ((cur_time - orig_time) >> SEQUENCE_LOCKTIME_GRANULARITY) >= SEQUENCE_LOCKTIME_MASK:
+                        can_time_lock = False
+
+                    # if time-lockable, then 50% chance we make this a time lock
+                    if random.randint(0,1) and can_time_lock:
+                        # Find first time-lock value that fails, or latest one that succeeds
+                        time_delta = sequence_value << SEQUENCE_LOCKTIME_GRANULARITY
+                        if input_will_pass and time_delta > cur_time - orig_time:
+                            sequence_value = ((cur_time - orig_time) >> SEQUENCE_LOCKTIME_GRANULARITY)
+                        elif (not input_will_pass and time_delta <= cur_time - orig_time):
+                            sequence_value = ((cur_time - orig_time) >> SEQUENCE_LOCKTIME_GRANULARITY)+1
+                        sequence_value |= SEQUENCE_LOCKTIME_TYPE_FLAG
+                tx.vin.append(CTxIn(COutPoint(int(utxos[j]["txid"], 16), utxos[j]["vout"]), nSequence=sequence_value))
+                value += utxos[j]["amount"]*COIN
+            # Overestimate the size of the tx - signatures should be less than 120 bytes, and leave 50 for the output
+            tx_size = len(ToHex(tx))/2 + 120*num_inputs + 50
+            tx.vout.append(CTxOut(value-self.relayfee*tx_size*COIN/1000, CScript([b'a'])))
+            rawtx = self.nodes[0].signrawtransaction(ToHex(tx))["hex"]
+
+            try:
+                self.nodes[0].sendrawtransaction(rawtx)
+            except JSONRPCException as exp:
+                assert(not should_pass and using_sequence_locks)
+                assert_equal(exp.error["message"], NOT_FINAL_ERROR)
+            else:
+                assert(should_pass or not using_sequence_locks)
+                # Recalculate utxos if we successfully sent the transaction
+                utxos = self.nodes[0].listunspent()
+
+    # Test that sequence locks on unconfirmed inputs must have nSequence
+    # height or time of 0 to be accepted.
+    # Then test that BIP68-invalid transactions are removed from the mempool
+    # after a reorg.
+    def test_sequence_lock_unconfirmed_inputs(self):
+        # Store height so we can easily reset the chain at the end of the test
+        cur_height = self.nodes[0].getblockcount()
+
+        # Create a mempool tx.
+        txid = self.nodes[0].sendtoaddress(self.nodes[0].getnewaddress(), 2)
+        tx1 = FromHex(CTransaction(), self.nodes[0].getrawtransaction(txid))
+        tx1.rehash()
+
+        # Anyone-can-spend mempool tx.
+        # Sequence lock of 0 should pass.
+        tx2 = CTransaction()
+        tx2.nVersion = 2
+        tx2.vin = [CTxIn(COutPoint(tx1.sha256, 0), nSequence=0)]
+        tx2.vout = [CTxOut(int(tx1.vout[0].nValue - self.relayfee*COIN), CScript([b'a']))]
+        tx2_raw = self.nodes[0].signrawtransaction(ToHex(tx2))["hex"]
+        tx2 = FromHex(tx2, tx2_raw)
+        tx2.rehash()
+
+        self.nodes[0].sendrawtransaction(tx2_raw)
+
+        # Create a spend of the 0th output of orig_tx with a sequence lock
+        # of 1, and test what happens when submitting.
+        # orig_tx.vout[0] must be an anyone-can-spend output
+        def test_nonzero_locks(orig_tx, node, relayfee, use_height_lock):
+            sequence_value = 1
+            if not use_height_lock:
+                sequence_value |= SEQUENCE_LOCKTIME_TYPE_FLAG
+
+            tx = CTransaction()
+            tx.nVersion = 2
+            tx.vin = [CTxIn(COutPoint(orig_tx.sha256, 0), nSequence=sequence_value)]
+            tx.vout = [CTxOut(int(orig_tx.vout[0].nValue - relayfee*COIN), CScript([b'a']))]
+            tx.rehash()
+
+            try:
+                node.sendrawtransaction(ToHex(tx))
+            except JSONRPCException as exp:
+                assert_equal(exp.error["message"], NOT_FINAL_ERROR)
+                assert(orig_tx.hash in node.getrawmempool())
+            else:
+                # orig_tx must not be in mempool
+                assert(orig_tx.hash not in node.getrawmempool())
+            return tx
+
+        test_nonzero_locks(tx2, self.nodes[0], self.relayfee, use_height_lock=True)
+        test_nonzero_locks(tx2, self.nodes[0], self.relayfee, use_height_lock=False)
+
+        # Now mine some blocks, but make sure tx2 doesn't get mined.
+        # Use prioritisetransaction to lower the effective feerate to 0
+        self.nodes[0].prioritisetransaction(tx2.hash, -1e15, int(-self.relayfee*COIN))
+        cur_time = int(time.time())
+        for i in xrange(10):
+            self.nodes[0].setmocktime(cur_time + 600)
+            self.nodes[0].generate(1)
+            cur_time += 600
+
+        assert(tx2.hash in self.nodes[0].getrawmempool())
+
+        test_nonzero_locks(tx2, self.nodes[0], self.relayfee, use_height_lock=True)
+        test_nonzero_locks(tx2, self.nodes[0], self.relayfee, use_height_lock=False)
+
+        # Mine tx2, and then try again
+        self.nodes[0].prioritisetransaction(tx2.hash, 1e15, int(self.relayfee*COIN))
+
+        # Advance the time on the node so that we can test timelocks
+        self.nodes[0].setmocktime(cur_time+600)
+        self.nodes[0].generate(1)
+        assert(tx2.hash not in self.nodes[0].getrawmempool())
+
+        # Now that tx2 is not in the mempool, a sequence locked spend should
+        # succeed
+        tx3 = test_nonzero_locks(tx2, self.nodes[0], self.relayfee, use_height_lock=False)
+        assert(tx3.hash in self.nodes[0].getrawmempool())
+
+        self.nodes[0].generate(1)
+        assert(tx3.hash not in self.nodes[0].getrawmempool())
+
+        # One more test, this time using height locks
+        tx4 = test_nonzero_locks(tx3, self.nodes[0], self.relayfee, use_height_lock=True)
+        assert(tx4.hash in self.nodes[0].getrawmempool())
+
+        # Now try combining confirmed and unconfirmed inputs
+        tx5 = test_nonzero_locks(tx4, self.nodes[0], self.relayfee, use_height_lock=True)
+        assert(tx5.hash not in self.nodes[0].getrawmempool())
+
+        utxos = self.nodes[0].listunspent()
+        tx5.vin.append(CTxIn(COutPoint(int(utxos[0]["txid"], 16), utxos[0]["vout"]), nSequence=1))
+        tx5.vout[0].nValue += int(utxos[0]["amount"]*COIN)
+        raw_tx5 = self.nodes[0].signrawtransaction(ToHex(tx5))["hex"]
+
+        try:
+            self.nodes[0].sendrawtransaction(raw_tx5)
+        except JSONRPCException as exp:
+            assert_equal(exp.error["message"], NOT_FINAL_ERROR)
+        else:
+            assert(False)
+
+        # Test mempool-BIP68 consistency after reorg
+        #
+        # State of the transactions in the last blocks:
+        # ... -> [ tx2 ] ->  [ tx3 ]
+        #         tip-1        tip
+        # And currently tx4 is in the mempool.
+        #
+        # If we invalidate the tip, tx3 should get added to the mempool, causing
+        # tx4 to be removed (fails sequence-lock).
+        self.nodes[0].invalidateblock(self.nodes[0].getbestblockhash())
+        assert(tx4.hash not in self.nodes[0].getrawmempool())
+        assert(tx3.hash in self.nodes[0].getrawmempool())
+
+        # Now mine 2 empty blocks to reorg out the current tip (labeled tip-1 in
+        # diagram above).
+        # This would cause tx2 to be added back to the mempool, which in turn causes
+        # tx3 to be removed.
+        tip = int(self.nodes[0].getblockhash(self.nodes[0].getblockcount()-1), 16)
+        height = self.nodes[0].getblockcount()
+        for i in xrange(2):
+            block = create_block(tip, create_coinbase(height), cur_time)
+            block.nVersion = 3
+            block.rehash()
+            block.solve()
+            tip = block.sha256
+            height += 1
+            self.nodes[0].submitblock(ToHex(block))
+            cur_time += 1
+
+        mempool = self.nodes[0].getrawmempool()
+        assert(tx3.hash not in mempool)
+        assert(tx2.hash in mempool)
+
+        # Reset the chain and get rid of the mocktimed-blocks
+        self.nodes[0].setmocktime(0)
+        self.nodes[0].invalidateblock(self.nodes[0].getblockhash(cur_height+1))
+        self.nodes[0].generate(10)
+
+    # Make sure that BIP68 isn't being used to validate blocks.
+    def test_bip68_not_consensus(self):
+        txid = self.nodes[0].sendtoaddress(self.nodes[0].getnewaddress(), 2)
+
+        tx1 = FromHex(CTransaction(), self.nodes[0].getrawtransaction(txid))
+        tx1.rehash()
+
+        # Make an anyone-can-spend transaction
+        tx2 = CTransaction()
+        tx2.nVersion = 1
+        tx2.vin = [CTxIn(COutPoint(tx1.sha256, 0), nSequence=0)]
+        tx2.vout = [CTxOut(int(tx1.vout[0].nValue - self.relayfee*COIN), CScript([b'a']))]
+
+        # sign tx2
+        tx2_raw = self.nodes[0].signrawtransaction(ToHex(tx2))["hex"]
+        tx2 = FromHex(tx2, tx2_raw)
+        tx2.rehash()
+
+        self.nodes[0].sendrawtransaction(ToHex(tx2))
+        
+        # Now make an invalid spend of tx2 according to BIP68
+        sequence_value = 100 # 100 block relative locktime
+
+        tx3 = CTransaction()
+        tx3.nVersion = 2
+        tx3.vin = [CTxIn(COutPoint(tx2.sha256, 0), nSequence=sequence_value)]
+        tx3.vout = [CTxOut(int(tx2.vout[0].nValue - self.relayfee*COIN), CScript([b'a']))]
+        tx3.rehash()
+
+        try:
+            self.nodes[0].sendrawtransaction(ToHex(tx3))
+        except JSONRPCException as exp:
+            assert_equal(exp.error["message"], NOT_FINAL_ERROR)
+        else:
+            assert(False)
+
+        # make a block that violates bip68; ensure that the tip updates
+        tip = int(self.nodes[0].getbestblockhash(), 16)
+        block = create_block(tip, create_coinbase(self.nodes[0].getblockcount()+1))
+        block.nVersion = 3
+        block.vtx.extend([tx1, tx2, tx3])
+        block.hashMerkleRoot = block.calc_merkle_root()
+        block.rehash()
+        block.solve()
+
+        self.nodes[0].submitblock(ToHex(block))
+        assert_equal(self.nodes[0].getbestblockhash(), block.hash)
+
+
+if __name__ == '__main__':
+    BIP68Test().main()
diff --git a/qa/rpc-tests/test_framework/mininode.py b/qa/rpc-tests/test_framework/mininode.py
index 2135570b8c..81bb439cea 100755
--- a/qa/rpc-tests/test_framework/mininode.py
+++ b/qa/rpc-tests/test_framework/mininode.py
@@ -231,6 +231,14 @@ def ser_int_vector(l):
         r += struct.pack("<i", i)
     return r
 
+# Deserialize from a hex string representation (eg from RPC)
+def FromHex(obj, hex_string):
+    obj.deserialize(cStringIO.StringIO(binascii.unhexlify(hex_string)))
+    return obj
+
+# Convert a binary-serializable object to hex (eg for submission via RPC)
+def ToHex(obj):
+    return binascii.hexlify(obj.serialize()).decode('utf-8')
 
 # Objects that map to bitcoind objects, which can be serialized/deserialized
 
diff --git a/src/consensus/consensus.h b/src/consensus/consensus.h
index 5a099cf53c..ad9cc26175 100644
--- a/src/consensus/consensus.h
+++ b/src/consensus/consensus.h
@@ -13,8 +13,11 @@ static const unsigned int MAX_BLOCK_SIGOPS = MAX_BLOCK_SIZE/50;
 /** Coinbase transaction outputs can only be spent after this number of new blocks (network rule) */
 static const int COINBASE_MATURITY = 100;
 
-/** Flags for LockTime() */
+/** Flags for nSequence and nLockTime locks */
 enum {
+    /* Interpret sequence numbers as relative lock-time constraints. */
+    LOCKTIME_VERIFY_SEQUENCE = (1 << 0),
+
     /* Use GetMedianTimePast() instead of nTime for end point timestamp. */
     LOCKTIME_MEDIAN_TIME_PAST = (1 << 1),
 };
diff --git a/src/main.cpp b/src/main.cpp
index 3ad2979b6b..6398fdad9a 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -672,9 +672,10 @@ bool IsFinalTx(const CTransaction &tx, int nBlockHeight, int64_t nBlockTime)
         return true;
     if ((int64_t)tx.nLockTime < ((int64_t)tx.nLockTime < LOCKTIME_THRESHOLD ? (int64_t)nBlockHeight : nBlockTime))
         return true;
-    BOOST_FOREACH(const CTxIn& txin, tx.vin)
-        if (!txin.IsFinal())
+    BOOST_FOREACH(const CTxIn& txin, tx.vin) {
+        if (!(txin.nSequence == CTxIn::SEQUENCE_FINAL))
             return false;
+    }
     return true;
 }
 
@@ -710,6 +711,128 @@ bool CheckFinalTx(const CTransaction &tx, int flags)
     return IsFinalTx(tx, nBlockHeight, nBlockTime);
 }
 
+/**
+ * Calculates the block height and previous block's median time past at
+ * which the transaction will be considered final in the context of BIP 68.
+ * Also removes from the vector of input heights any entries which did not
+ * correspond to sequence locked inputs as they do not affect the calculation.
+ */
+static std::pair<int, int64_t> CalculateSequenceLocks(const CTransaction &tx, int flags, std::vector<int>* prevHeights, const CBlockIndex& block)
+{
+    assert(prevHeights->size() == tx.vin.size());
+
+    // Will be set to the equivalent height- and time-based nLockTime
+    // values that would be necessary to satisfy all relative lock-
+    // time constraints given our view of block chain history.
+    // The semantics of nLockTime are the last invalid height/time, so
+    // use -1 to have the effect of any height or time being valid.
+    int nMinHeight = -1;
+    int64_t nMinTime = -1;
+
+    // tx.nVersion is signed integer so requires cast to unsigned otherwise
+    // we would be doing a signed comparison and half the range of nVersion
+    // wouldn't support BIP 68.
+    bool fEnforceBIP68 = static_cast<uint32_t>(tx.nVersion) >= 2
+                      && flags & LOCKTIME_VERIFY_SEQUENCE;
+
+    // Do not enforce sequence numbers as a relative lock time
+    // unless we have been instructed to
+    if (!fEnforceBIP68) {
+        return std::make_pair(nMinHeight, nMinTime);
+    }
+
+    for (size_t txinIndex = 0; txinIndex < tx.vin.size(); txinIndex++) {
+        const CTxIn& txin = tx.vin[txinIndex];
+
+        // Sequence numbers with the most significant bit set are not
+        // treated as relative lock-times, nor are they given any
+        // consensus-enforced meaning at this point.
+        if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_DISABLE_FLAG) {
+            // The height of this input is not relevant for sequence locks
+            (*prevHeights)[txinIndex] = 0;
+            continue;
+        }
+
+        int nCoinHeight = (*prevHeights)[txinIndex];
+
+        if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) {
+            int64_t nCoinTime = block.GetAncestor(std::max(nCoinHeight-1, 0))->GetMedianTimePast();
+            // NOTE: Subtract 1 to maintain nLockTime semantics
+            // BIP 68 relative lock times have the semantics of calculating
+            // the first block or time at which the transaction would be
+            // valid. When calculating the effective block time or height
+            // for the entire transaction, we switch to using the
+            // semantics of nLockTime which is the last invalid block
+            // time or height.  Thus we subtract 1 from the calculated
+            // time or height.
+
+            // Time-based relative lock-times are measured from the
+            // smallest allowed timestamp of the block containing the
+            // txout being spent, which is the median time past of the
+            // block prior.
+            nMinTime = std::max(nMinTime, nCoinTime + (int64_t)((txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) << CTxIn::SEQUENCE_LOCKTIME_GRANULARITY) - 1);
+        } else {
+            nMinHeight = std::max(nMinHeight, nCoinHeight + (int)(txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) - 1);
+        }
+    }
+
+    return std::make_pair(nMinHeight, nMinTime);
+}
+
+static bool EvaluateSequenceLocks(const CBlockIndex& block, std::pair<int, int64_t> lockPair)
+{
+    assert(block.pprev);
+    int64_t nBlockTime = block.pprev->GetMedianTimePast();
+    if (lockPair.first >= block.nHeight || lockPair.second >= nBlockTime)
+        return false;
+
+    return true;
+}
+
+bool SequenceLocks(const CTransaction &tx, int flags, std::vector<int>* prevHeights, const CBlockIndex& block)
+{
+    return EvaluateSequenceLocks(block, CalculateSequenceLocks(tx, flags, prevHeights, block));
+}
+
+bool CheckSequenceLocks(const CTransaction &tx, int flags)
+{
+    AssertLockHeld(cs_main);
+    AssertLockHeld(mempool.cs);
+
+    CBlockIndex* tip = chainActive.Tip();
+    CBlockIndex index;
+    index.pprev = tip;
+    // CheckSequenceLocks() uses chainActive.Height()+1 to evaluate
+    // height based locks because when SequenceLocks() is called within
+    // ConnectBlock(), the height of the block *being*
+    // evaluated is what is used.
+    // Thus if we want to know if a transaction can be part of the
+    // *next* block, we need to use one more than chainActive.Height()
+    index.nHeight = tip->nHeight + 1;
+
+    // pcoinsTip contains the UTXO set for chainActive.Tip()
+    CCoinsViewMemPool viewMemPool(pcoinsTip, mempool);
+    std::vector<int> prevheights;
+    prevheights.resize(tx.vin.size());
+    for (size_t txinIndex = 0; txinIndex < tx.vin.size(); txinIndex++) {
+        const CTxIn& txin = tx.vin[txinIndex];
+        CCoins coins;
+        if (!viewMemPool.GetCoins(txin.prevout.hash, coins)) {
+            return error("%s: Missing input", __func__);
+        }
+        if (coins.nHeight == MEMPOOL_HEIGHT) {
+            // Assume all mempool transaction confirm in the next block
+            prevheights[txinIndex] = tip->nHeight + 1;
+        } else {
+            prevheights[txinIndex] = coins.nHeight;
+        }
+    }
+
+    std::pair<int, int64_t> lockPair = CalculateSequenceLocks(tx, flags, &prevheights, index);
+    return EvaluateSequenceLocks(index, lockPair);
+}
+
+
 unsigned int GetLegacySigOpCount(const CTransaction& tx)
 {
     unsigned int nSigOps = 0;
@@ -931,6 +1054,14 @@ bool AcceptToMemoryPoolWorker(CTxMemPool& pool, CValidationState& state, const C
 
         // we have all inputs cached now, so switch back to dummy, so we don't need to keep lock on mempool
         view.SetBackend(dummy);
+
+        // Only accept BIP68 sequence locked transactions that can be mined in the next
+        // block; we don't want our mempool filled up with transactions that can't
+        // be mined yet.
+        // Must keep pool.cs for this unless we change CheckSequenceLocks to take a
+        // CoinsViewCache instead of create its own
+        if (!CheckSequenceLocks(tx, STANDARD_LOCKTIME_VERIFY_FLAGS))
+            return state.DoS(0, false, REJECT_NONSTANDARD, "non-BIP68-final");
         }
 
         // Check for non-standard pay-to-script-hash in inputs
@@ -2052,6 +2183,8 @@ bool ConnectBlock(const CBlock& block, CValidationState& state, CBlockIndex* pin
 
     CCheckQueueControl<CScriptCheck> control(fScriptChecks && nScriptCheckThreads ? &scriptcheckqueue : NULL);
 
+    std::vector<int> prevheights;
+    int nLockTimeFlags = 0;
     CAmount nFees = 0;
     int nInputs = 0;
     unsigned int nSigOps = 0;
@@ -2075,6 +2208,19 @@ bool ConnectBlock(const CBlock& block, CValidationState& state, CBlockIndex* pin
                 return state.DoS(100, error("ConnectBlock(): inputs missing/spent"),
                                  REJECT_INVALID, "bad-txns-inputs-missingorspent");
 
+            // Check that transaction is BIP68 final
+            // BIP68 lock checks (as opposed to nLockTime checks) must
+            // be in ConnectBlock because they require the UTXO set
+            prevheights.resize(tx.vin.size());
+            for (size_t j = 0; j < tx.vin.size(); j++) {
+                prevheights[j] = view.AccessCoins(tx.vin[j].prevout.hash)->nHeight;
+            }
+
+            if (!SequenceLocks(tx, nLockTimeFlags, &prevheights, *pindex)) {
+                return state.DoS(100, error("%s: contains a non-BIP68-final transaction", __func__),
+                                 REJECT_INVALID, "bad-txns-nonfinal");
+            }
+
             if (fStrictPayToScriptHash)
             {
                 // Add in sigops done by pay-to-script-hash inputs;
diff --git a/src/main.h b/src/main.h
index 4061daba3b..b6f61ca991 100644
--- a/src/main.h
+++ b/src/main.h
@@ -365,7 +365,22 @@ bool IsFinalTx(const CTransaction &tx, int nBlockHeight, int64_t nBlockTime);
  */
 bool CheckFinalTx(const CTransaction &tx, int flags = -1);
 
-/** 
+/**
+ * Check if transaction is final per BIP 68 sequence numbers and can be included in a block.
+ * Consensus critical. Takes as input a list of heights at which tx's inputs (in order) confirmed.
+ */
+bool SequenceLocks(const CTransaction &tx, int flags, std::vector<int>* prevHeights, const CBlockIndex& block);
+
+/**
+ * Check if transaction will be BIP 68 final in the next block to be created.
+ *
+ * Simulates calling SequenceLocks() with data from the tip of the current active chain.
+ *
+ * See consensus/consensus.h for flag definitions.
+ */
+bool CheckSequenceLocks(const CTransaction &tx, int flags);
+
+/**
  * Closure representing one script verification
  * Note that this stores references to the spending transaction 
  */
diff --git a/src/policy/policy.h b/src/policy/policy.h
index 726864f190..aabeebb25d 100644
--- a/src/policy/policy.h
+++ b/src/policy/policy.h
@@ -45,8 +45,9 @@ static const unsigned int STANDARD_SCRIPT_VERIFY_FLAGS = MANDATORY_SCRIPT_VERIFY
 /** For convenience, standard but not mandatory verify flags. */
 static const unsigned int STANDARD_NOT_MANDATORY_VERIFY_FLAGS = STANDARD_SCRIPT_VERIFY_FLAGS & ~MANDATORY_SCRIPT_VERIFY_FLAGS;
 
-/** Used as the flags parameter to CheckFinalTx() in non-consensus code */
-static const unsigned int STANDARD_LOCKTIME_VERIFY_FLAGS = LOCKTIME_MEDIAN_TIME_PAST;
+/** Used as the flags parameter to sequence and nLocktime checks in non-consensus code. */
+static const unsigned int STANDARD_LOCKTIME_VERIFY_FLAGS = LOCKTIME_VERIFY_SEQUENCE |
+                                                           LOCKTIME_MEDIAN_TIME_PAST;
 
 bool IsStandard(const CScript& scriptPubKey, txnouttype& whichType);
     /**
diff --git a/src/primitives/transaction.cpp b/src/primitives/transaction.cpp
index aea96d8a12..947f2e6a73 100644
--- a/src/primitives/transaction.cpp
+++ b/src/primitives/transaction.cpp
@@ -37,7 +37,7 @@ std::string CTxIn::ToString() const
         str += strprintf(", coinbase %s", HexStr(scriptSig));
     else
         str += strprintf(", scriptSig=%s", HexStr(scriptSig).substr(0, 24));
-    if (nSequence != std::numeric_limits<unsigned int>::max())
+    if (nSequence != SEQUENCE_FINAL)
         str += strprintf(", nSequence=%u", nSequence);
     str += ")";
     return str;
diff --git a/src/primitives/transaction.h b/src/primitives/transaction.h
index 8bd6d00e2e..07ae39e0b4 100644
--- a/src/primitives/transaction.h
+++ b/src/primitives/transaction.h
@@ -61,13 +61,40 @@ public:
     CScript scriptSig;
     uint32_t nSequence;
 
+    /* Setting nSequence to this value for every input in a transaction
+     * disables nLockTime. */
+    static const uint32_t SEQUENCE_FINAL = 0xffffffff;
+
+    /* Below flags apply in the context of BIP 68*/
+    /* If this flag set, CTxIn::nSequence is NOT interpreted as a
+     * relative lock-time. */
+    static const uint32_t SEQUENCE_LOCKTIME_DISABLE_FLAG = (1 << 31);
+
+    /* If CTxIn::nSequence encodes a relative lock-time and this flag
+     * is set, the relative lock-time has units of 512 seconds,
+     * otherwise it specifies blocks with a granularity of 1. */
+    static const uint32_t SEQUENCE_LOCKTIME_TYPE_FLAG = (1 << 22);
+
+    /* If CTxIn::nSequence encodes a relative lock-time, this mask is
+     * applied to extract that lock-time from the sequence field. */
+    static const uint32_t SEQUENCE_LOCKTIME_MASK = 0x0000ffff;
+
+    /* In order to use the same number of bits to encode roughly the
+     * same wall-clock duration, and because blocks are naturally
+     * limited to occur every 600s on average, the minimum granularity
+     * for time-based relative lock-time is fixed at 512 seconds.
+     * Converting from CTxIn::nSequence to seconds is performed by
+     * multiplying by 512 = 2^9, or equivalently shifting up by
+     * 9 bits. */
+    static const int SEQUENCE_LOCKTIME_GRANULARITY = 9;
+
     CTxIn()
     {
-        nSequence = std::numeric_limits<unsigned int>::max();
+        nSequence = SEQUENCE_FINAL;
     }
 
-    explicit CTxIn(COutPoint prevoutIn, CScript scriptSigIn=CScript(), uint32_t nSequenceIn=std::numeric_limits<unsigned int>::max());
-    CTxIn(uint256 hashPrevTx, uint32_t nOut, CScript scriptSigIn=CScript(), uint32_t nSequenceIn=std::numeric_limits<uint32_t>::max());
+    explicit CTxIn(COutPoint prevoutIn, CScript scriptSigIn=CScript(), uint32_t nSequenceIn=SEQUENCE_FINAL);
+    CTxIn(uint256 hashPrevTx, uint32_t nOut, CScript scriptSigIn=CScript(), uint32_t nSequenceIn=SEQUENCE_FINAL);
 
     ADD_SERIALIZE_METHODS;
 
@@ -78,11 +105,6 @@ public:
         READWRITE(nSequence);
     }
 
-    bool IsFinal() const
-    {
-        return (nSequence == std::numeric_limits<uint32_t>::max());
-    }
-
     friend bool operator==(const CTxIn& a, const CTxIn& b)
     {
         return (a.prevout   == b.prevout &&
diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
index 265131ae0d..901f901f01 100644
--- a/src/script/interpreter.cpp
+++ b/src/script/interpreter.cpp
@@ -1150,7 +1150,7 @@ bool TransactionSignatureChecker::CheckLockTime(const CScriptNum& nLockTime) con
     // prevent this condition. Alternatively we could test all
     // inputs, but testing just this input minimizes the data
     // required to prove correct CHECKLOCKTIMEVERIFY execution.
-    if (txTo->vin[nIn].IsFinal())
+    if (CTxIn::SEQUENCE_FINAL == txTo->vin[nIn].nSequence)
         return false;
 
     return true;
diff --git a/src/test/miner_tests.cpp b/src/test/miner_tests.cpp
index 71b52409b3..f3297e074d 100644
--- a/src/test/miner_tests.cpp
+++ b/src/test/miner_tests.cpp
@@ -57,6 +57,20 @@ struct {
     {2, 0xbbbeb305}, {2, 0xfe1c810a},
 };
 
+CBlockIndex CreateBlockIndex(int nHeight)
+{
+    CBlockIndex index;
+    index.nHeight = nHeight;
+    index.pprev = chainActive.Tip();
+    return index;
+}
+
+bool TestSequenceLocks(const CTransaction &tx, int flags)
+{
+    LOCK(mempool.cs);
+    return CheckSequenceLocks(tx, flags);
+}
+
 // NOTE: These tests rely on CreateNewBlock doing its own self-validation!
 BOOST_AUTO_TEST_CASE(CreateNewBlock_validity)
 {
@@ -79,6 +93,7 @@ BOOST_AUTO_TEST_CASE(CreateNewBlock_validity)
 
     // We can't make transactions until we have inputs
     // Therefore, load 100 blocks :)
+    int baseheight = 0;
     std::vector<CTransaction*>txFirst;
     for (unsigned int i = 0; i < sizeof(blockinfo)/sizeof(*blockinfo); ++i)
     {
@@ -92,7 +107,9 @@ BOOST_AUTO_TEST_CASE(CreateNewBlock_validity)
         txCoinbase.vin[0].scriptSig.push_back(chainActive.Height());
         txCoinbase.vout[0].scriptPubKey = CScript();
         pblock->vtx[0] = CTransaction(txCoinbase);
-        if (txFirst.size() < 2)
+        if (txFirst.size() == 0)
+            baseheight = chainActive.Height();
+        if (txFirst.size() < 4)
             txFirst.push_back(new CTransaction(pblock->vtx[0]));
         pblock->hashMerkleRoot = BlockMerkleRoot(*pblock);
         pblock->nNonce = blockinfo[i].nonce;
@@ -240,49 +257,96 @@ BOOST_AUTO_TEST_CASE(CreateNewBlock_validity)
 
     // non-final txs in mempool
     SetMockTime(chainActive.Tip()->GetMedianTimePast()+1);
+    int flags = LOCKTIME_VERIFY_SEQUENCE|LOCKTIME_MEDIAN_TIME_PAST;
+    // height map
+    std::vector<int> prevheights;
 
-    // height locked
-    tx.vin[0].prevout.hash = txFirst[0]->GetHash();
+    // relative height locked
+    tx.nVersion = 2;
+    tx.vin.resize(1);
+    prevheights.resize(1);
+    tx.vin[0].prevout.hash = txFirst[0]->GetHash(); // only 1 transaction
+    tx.vin[0].prevout.n = 0;
     tx.vin[0].scriptSig = CScript() << OP_1;
-    tx.vin[0].nSequence = 0;
+    tx.vin[0].nSequence = chainActive.Tip()->nHeight + 1; // txFirst[0] is the 2nd block
+    prevheights[0] = baseheight + 1;
+    tx.vout.resize(1);
     tx.vout[0].nValue = 4900000000LL;
     tx.vout[0].scriptPubKey = CScript() << OP_1;
-    tx.nLockTime = chainActive.Tip()->nHeight+1;
+    tx.nLockTime = 0;
     hash = tx.GetHash();
     mempool.addUnchecked(hash, entry.Fee(100000000L).Time(GetTime()).SpendsCoinbase(true).FromTx(tx));
-    BOOST_CHECK(!CheckFinalTx(tx, LOCKTIME_MEDIAN_TIME_PAST));
-
-    // time locked
-    tx2.vin.resize(1);
-    tx2.vin[0].prevout.hash = txFirst[1]->GetHash();
-    tx2.vin[0].prevout.n = 0;
-    tx2.vin[0].scriptSig = CScript() << OP_1;
-    tx2.vin[0].nSequence = 0;
-    tx2.vout.resize(1);
-    tx2.vout[0].nValue = 4900000000LL;
-    tx2.vout[0].scriptPubKey = CScript() << OP_1;
-    tx2.nLockTime = chainActive.Tip()->GetMedianTimePast()+1;
-    hash = tx2.GetHash();
-    mempool.addUnchecked(hash, entry.Fee(100000000L).Time(GetTime()).SpendsCoinbase(true).FromTx(tx2));
-    BOOST_CHECK(!CheckFinalTx(tx2, LOCKTIME_MEDIAN_TIME_PAST));
+    BOOST_CHECK(CheckFinalTx(tx, flags)); // Locktime passes
+    BOOST_CHECK(!TestSequenceLocks(tx, flags)); // Sequence locks fail
+    BOOST_CHECK(SequenceLocks(tx, flags, &prevheights, CreateBlockIndex(chainActive.Tip()->nHeight + 2))); // Sequence locks pass on 2nd block
+
+    // relative time locked
+    tx.vin[0].prevout.hash = txFirst[1]->GetHash();
+    tx.vin[0].nSequence = CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG | (((chainActive.Tip()->GetMedianTimePast()+1-chainActive[1]->GetMedianTimePast()) >> CTxIn::SEQUENCE_LOCKTIME_GRANULARITY) + 1); // txFirst[1] is the 3rd block
+    prevheights[0] = baseheight + 2;
+    hash = tx.GetHash();
+    mempool.addUnchecked(hash, entry.Time(GetTime()).FromTx(tx));
+    BOOST_CHECK(CheckFinalTx(tx, flags)); // Locktime passes
+    BOOST_CHECK(!TestSequenceLocks(tx, flags)); // Sequence locks fail
+
+    for (int i = 0; i < CBlockIndex::nMedianTimeSpan; i++)
+        chainActive.Tip()->GetAncestor(chainActive.Tip()->nHeight - i)->nTime += 512; //Trick the MedianTimePast
+    BOOST_CHECK(SequenceLocks(tx, flags, &prevheights, CreateBlockIndex(chainActive.Tip()->nHeight + 1))); // Sequence locks pass 512 seconds later
+    for (int i = 0; i < CBlockIndex::nMedianTimeSpan; i++)
+        chainActive.Tip()->GetAncestor(chainActive.Tip()->nHeight - i)->nTime -= 512; //undo tricked MTP
+
+    // absolute height locked
+    tx.vin[0].prevout.hash = txFirst[2]->GetHash();
+    tx.vin[0].nSequence = CTxIn::SEQUENCE_FINAL - 1;
+    prevheights[0] = baseheight + 3;
+    tx.nLockTime = chainActive.Tip()->nHeight + 1;
+    hash = tx.GetHash();
+    mempool.addUnchecked(hash, entry.Time(GetTime()).FromTx(tx));
+    BOOST_CHECK(!CheckFinalTx(tx, flags)); // Locktime fails
+    BOOST_CHECK(TestSequenceLocks(tx, flags)); // Sequence locks pass
+    BOOST_CHECK(IsFinalTx(tx, chainActive.Tip()->nHeight + 2, chainActive.Tip()->GetMedianTimePast())); // Locktime passes on 2nd block
+
+    // absolute time locked
+    tx.vin[0].prevout.hash = txFirst[3]->GetHash();
+    tx.nLockTime = chainActive.Tip()->GetMedianTimePast();
+    prevheights.resize(1);
+    prevheights[0] = baseheight + 4;
+    hash = tx.GetHash();
+    mempool.addUnchecked(hash, entry.Time(GetTime()).FromTx(tx));
+    BOOST_CHECK(!CheckFinalTx(tx, flags)); // Locktime fails
+    BOOST_CHECK(TestSequenceLocks(tx, flags)); // Sequence locks pass
+    BOOST_CHECK(IsFinalTx(tx, chainActive.Tip()->nHeight + 2, chainActive.Tip()->GetMedianTimePast() + 1)); // Locktime passes 1 second later
+
+    // mempool-dependent transactions (not added)
+    tx.vin[0].prevout.hash = hash;
+    prevheights[0] = chainActive.Tip()->nHeight + 1;
+    tx.nLockTime = 0;
+    tx.vin[0].nSequence = 0;
+    BOOST_CHECK(CheckFinalTx(tx, flags)); // Locktime passes
+    BOOST_CHECK(TestSequenceLocks(tx, flags)); // Sequence locks pass
+    tx.vin[0].nSequence = 1;
+    BOOST_CHECK(!TestSequenceLocks(tx, flags)); // Sequence locks fail
+    tx.vin[0].nSequence = CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG;
+    BOOST_CHECK(TestSequenceLocks(tx, flags)); // Sequence locks pass
+    tx.vin[0].nSequence = CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG | 1;
+    BOOST_CHECK(!TestSequenceLocks(tx, flags)); // Sequence locks fail
 
     BOOST_CHECK(pblocktemplate = CreateNewBlock(chainparams, scriptPubKey));
 
-    // Neither tx should have make it into the template.
-    BOOST_CHECK_EQUAL(pblocktemplate->block.vtx.size(), 1);
+    // None of the of the absolute height/time locked tx should have made
+    // it into the template because we still check IsFinalTx in CreateNewBlock,
+    // but relative locked txs will if inconsistently added to mempool.
+    // For now these will still generate a valid template until BIP68 soft fork
+    BOOST_CHECK_EQUAL(pblocktemplate->block.vtx.size(), 3);
     delete pblocktemplate;
-
-    // However if we advance height and time by one, both will.
+    // However if we advance height by 1 and time by 512, all of them should be mined
+    for (int i = 0; i < CBlockIndex::nMedianTimeSpan; i++)
+        chainActive.Tip()->GetAncestor(chainActive.Tip()->nHeight - i)->nTime += 512; //Trick the MedianTimePast
     chainActive.Tip()->nHeight++;
-    SetMockTime(chainActive.Tip()->GetMedianTimePast()+2);
-
-    // FIXME: we should *actually* create a new block so the following test
-    //        works; CheckFinalTx() isn't fooled by monkey-patching nHeight.
-    //BOOST_CHECK(CheckFinalTx(tx));
-    //BOOST_CHECK(CheckFinalTx(tx2));
+    SetMockTime(chainActive.Tip()->GetMedianTimePast() + 1);
 
     BOOST_CHECK(pblocktemplate = CreateNewBlock(chainparams, scriptPubKey));
-    BOOST_CHECK_EQUAL(pblocktemplate->block.vtx.size(), 2);
+    BOOST_CHECK_EQUAL(pblocktemplate->block.vtx.size(), 5);
     delete pblocktemplate;
 
     chainActive.Tip()->nHeight--;
diff --git a/src/test/script_tests.cpp b/src/test/script_tests.cpp
index 10175ebe8e..f370a4aa2a 100644
--- a/src/test/script_tests.cpp
+++ b/src/test/script_tests.cpp
@@ -63,7 +63,7 @@ CMutableTransaction BuildCreditingTransaction(const CScript& scriptPubKey)
     txCredit.vout.resize(1);
     txCredit.vin[0].prevout.SetNull();
     txCredit.vin[0].scriptSig = CScript() << CScriptNum(0) << CScriptNum(0);
-    txCredit.vin[0].nSequence = std::numeric_limits<unsigned int>::max();
+    txCredit.vin[0].nSequence = CTxIn::SEQUENCE_FINAL;
     txCredit.vout[0].scriptPubKey = scriptPubKey;
     txCredit.vout[0].nValue = 0;
 
@@ -80,7 +80,7 @@ CMutableTransaction BuildSpendingTransaction(const CScript& scriptSig, const CMu
     txSpend.vin[0].prevout.hash = txCredit.GetHash();
     txSpend.vin[0].prevout.n = 0;
     txSpend.vin[0].scriptSig = scriptSig;
-    txSpend.vin[0].nSequence = std::numeric_limits<unsigned int>::max();
+    txSpend.vin[0].nSequence = CTxIn::SEQUENCE_FINAL;
     txSpend.vout[0].scriptPubKey = CScript();
     txSpend.vout[0].nValue = 0;
 
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index f8e03c2533..0b0f32e406 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -506,7 +506,7 @@ void CTxMemPool::removeForReorg(const CCoinsViewCache *pcoins, unsigned int nMem
     list<CTransaction> transactionsToRemove;
     for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
         const CTransaction& tx = it->GetTx();
-        if (!CheckFinalTx(tx, flags)) {
+        if (!CheckFinalTx(tx, flags) || !CheckSequenceLocks(tx, flags)) {
             transactionsToRemove.push_back(tx);
         } else if (it->GetSpendsCoinbase()) {
             BOOST_FOREACH(const CTxIn& txin, tx.vin) {