Merge #8149: Segregated witness rebased

f852813 BIP9 parameters for testnet (Johnson Lau)
070dbc4 --- [SEGWIT] begin: deployment --- (Pieter Wuille)
fdb43df [qa] Add GetTransactionSigOpCost unit tests (Jonas Nick)
d846e02 [qa] script_tests: witness tests can specify tx amount (Suhas Daftuar)
330b0f3 [qa] p2p segwit tests (Suhas Daftuar)
4f7ff00 [qa] Add rpc test for segwit (Alex Morcos)
66cca79 [qa] Autogeneration support for witness in script_tests (Pieter Wuille)
06d3805 [qa] Add segwit support to script_tests (Pieter Wuille)
00f46cb [qa] Add transaction tests for segwit (NicolasDorier)
0aa9207 [qa] Witness version 0 signing unit tests (Pieter Wuille)
978e200 --- [SEGWIT] begin: tests --- (Pieter Wuille)
745eb67 [RPC] signrawtransaction can sign P2WSH (NicolasDorier)
f4691ab [RPC] Add wallet support for witness transactions (using P2SH) (Pieter Wuille)
605e847 BIP143: Signing logic (Pieter Wuille)
9757b57 --- [SEGWIT] begin: wallet --- (Pieter Wuille)
af87a67 Do not use compact blocks when segwit is enabled (Pieter Wuille)
6032f69 Add rewind logic to deal with post-fork software updates (Pieter Wuille)
b7dbeb2 [libconsensus] Script verification API with amounts (Thomas Kerin)
2b1f6f9 BIP141: Other consensus critical limits, and BIP145 (Pieter Wuille)
7c4bf77 [RPC] Return witness data in blockchain RPCs (Johnson Lau)
3dd4102 BIP143: Verification logic (Pieter Wuille)
0ef1dd3 Refactor script validation to observe amounts (Pieter Wuille)
b8a9749 BIP144: Handshake and relay (receiver side) (Pieter Wuille)
8b49040 BIP141: Commitment structure and deployment (Pieter Wuille)
449f9b8 BIP141: Witness program (Pieter Wuille)
7030d9e BIP144: Serialization, hashes, relay (sender side) (Pieter Wuille)
ecacfd9 --- [SEGWIT] begin: P2P/node/consensus --- (Pieter Wuille)

7 files changed, 2126 insertions, 34 deletions

diff --git a/qa/pull-tester/rpc-tests.py b/qa/pull-tester/rpc-tests.py
index 6c0ed4510f..37979a933f 100755
--- a/qa/pull-tester/rpc-tests.py
+++ b/qa/pull-tester/rpc-tests.py
@@ -136,6 +136,8 @@ testScripts = [
     'invalidtxrequest.py',
     'abandonconflict.py',
     'p2p-versionbits-warning.py',
+    'p2p-segwit.py',
+    'segwit.py',
     'importprunedfunds.py',
     'signmessages.py',
 ]
diff --git a/qa/rpc-tests/maxuploadtarget.py b/qa/rpc-tests/maxuploadtarget.py
index 5087f07620..125d4eb275 100755
--- a/qa/rpc-tests/maxuploadtarget.py
+++ b/qa/rpc-tests/maxuploadtarget.py
@@ -97,7 +97,7 @@ class MaxUploadTest(BitcoinTestFramework):
     def setup_network(self):
         # Start a node with maxuploadtarget of 200 MB (/24h)
         self.nodes = []
-        self.nodes.append(start_node(0, self.options.tmpdir, ["-debug", "-maxuploadtarget=200", "-blockmaxsize=999000"]))
+        self.nodes.append(start_node(0, self.options.tmpdir, ["-debug", "-maxuploadtarget=800", "-blockmaxsize=999000"]))
 
     def mine_full_block(self, node, address):
         # Want to create a full block
@@ -175,13 +175,13 @@ class MaxUploadTest(BitcoinTestFramework):
         getdata_request = msg_getdata()
         getdata_request.inv.append(CInv(2, big_old_block))
 
-        max_bytes_per_day = 200*1024*1024
-        daily_buffer = 144 * MAX_BLOCK_SIZE
+        max_bytes_per_day = 800*1024*1024
+        daily_buffer = 144 * 4000000
         max_bytes_available = max_bytes_per_day - daily_buffer
         success_count = max_bytes_available // old_block_size
 
-        # 144MB will be reserved for relaying new blocks, so expect this to
-        # succeed for ~70 tries.
+        # 576MB will be reserved for relaying new blocks, so expect this to
+        # succeed for ~235 tries.
         for i in range(success_count):
             test_nodes[0].send_message(getdata_request)
             test_nodes[0].sync_with_ping()
@@ -198,9 +198,9 @@ class MaxUploadTest(BitcoinTestFramework):
 
         # Requesting the current block on test_nodes[1] should succeed indefinitely,
         # even when over the max upload target.
-        # We'll try 200 times
+        # We'll try 800 times
         getdata_request.inv = [CInv(2, big_new_block)]
-        for i in range(200):
+        for i in range(800):
             test_nodes[1].send_message(getdata_request)
             test_nodes[1].sync_with_ping()
             assert_equal(test_nodes[1].block_receive_map[big_new_block], i+1)
diff --git a/qa/rpc-tests/p2p-segwit.py b/qa/rpc-tests/p2p-segwit.py
new file mode 100755
index 0000000000..cf78954f28
--- /dev/null
+++ b/qa/rpc-tests/p2p-segwit.py
@@ -0,0 +1,1646 @@
+#!/usr/bin/env python3
+# 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.
+
+from test_framework.mininode import *
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.util import *
+from test_framework.script import *
+from test_framework.blocktools import create_block, create_coinbase, add_witness_commitment, WITNESS_COMMITMENT_HEADER
+from test_framework.key import CECKey, CPubKey
+import time
+import random
+from binascii import hexlify
+
+# The versionbit bit used to signal activation of SegWit
+VB_WITNESS_BIT = 1
+VB_PERIOD = 144
+VB_ACTIVATION_THRESHOLD = 108
+VB_TOP_BITS = 0x20000000
+
+MAX_SIGOP_COST = 80000
+
+'''
+SegWit p2p test.
+'''
+
+# Calculate the virtual size of a witness block:
+# (base + witness/4)
+def get_virtual_size(witness_block):
+    base_size = len(witness_block.serialize())
+    total_size = len(witness_block.serialize(with_witness=True))
+    # the "+3" is so we round up
+    vsize = int((3*base_size + total_size + 3)/4)
+    return vsize
+
+# Note: we can reduce code by using SingleNodeConnCB (in master, not 0.12)
+class TestNode(NodeConnCB):
+    def __init__(self):
+        NodeConnCB.__init__(self)
+        self.connection = None
+        self.ping_counter = 1
+        self.last_pong = msg_pong(0)
+        self.sleep_time = 0.05
+        self.getdataset = set()
+
+    def add_connection(self, conn):
+        self.connection = conn
+
+    # Wrapper for the NodeConn's send_message function
+    def send_message(self, message):
+        self.connection.send_message(message)
+
+    def on_inv(self, conn, message):
+        self.last_inv = message
+
+    def on_block(self, conn, message):
+        self.last_block = message.block
+        self.last_block.calc_sha256()
+
+    def on_getdata(self, conn, message):
+        for inv in message.inv:
+            self.getdataset.add(inv.hash)
+        self.last_getdata = message
+
+    def on_pong(self, conn, message):
+        self.last_pong = message
+
+    def on_reject(self, conn, message):
+        self.last_reject = message
+        #print message
+
+    # Syncing helpers
+    def sync(self, test_function, timeout=60):
+        while timeout > 0:
+            with mininode_lock:
+                if test_function():
+                    return
+            time.sleep(self.sleep_time)
+            timeout -= self.sleep_time
+        raise AssertionError("Sync failed to complete")
+        
+    def sync_with_ping(self, timeout=60):
+        self.send_message(msg_ping(nonce=self.ping_counter))
+        test_function = lambda: self.last_pong.nonce == self.ping_counter
+        self.sync(test_function, timeout)
+        self.ping_counter += 1
+        return
+
+    def wait_for_block(self, blockhash, timeout=60):
+        test_function = lambda: self.last_block != None and self.last_block.sha256 == blockhash
+        self.sync(test_function, timeout)
+        return
+
+    def wait_for_getdata(self, timeout=60):
+        test_function = lambda: self.last_getdata != None
+        self.sync(test_function, timeout)
+
+    def wait_for_inv(self, expected_inv, timeout=60):
+        test_function = lambda: self.last_inv != expected_inv
+        self.sync(test_function, timeout)
+
+    def announce_tx_and_wait_for_getdata(self, tx, timeout=60):
+        with mininode_lock:
+            self.last_getdata = None
+        self.send_message(msg_inv(inv=[CInv(1, tx.sha256)]))
+        self.wait_for_getdata(timeout)
+        return
+
+    def announce_block_and_wait_for_getdata(self, block, use_header, timeout=60):
+        with mininode_lock:
+            self.last_getdata = None
+        if use_header:
+            msg = msg_headers()
+            msg.headers = [ CBlockHeader(block) ]
+            self.send_message(msg)
+        else:
+            self.send_message(msg_inv(inv=[CInv(2, block.sha256)]))
+        self.wait_for_getdata()
+        return
+
+    def announce_block(self, block, use_header):
+        with mininode_lock:
+            self.last_getdata = None
+        if use_header:
+            msg = msg_headers()
+            msg.headers = [ CBlockHeader(block) ]
+            self.send_message(msg)
+        else:
+            self.send_message(msg_inv(inv=[CInv(2, block.sha256)]))
+
+    def request_block(self, blockhash, inv_type, timeout=60):
+        with mininode_lock:
+            self.last_block = None
+        self.send_message(msg_getdata(inv=[CInv(inv_type, blockhash)]))
+        self.wait_for_block(blockhash, timeout)
+        return self.last_block
+
+    def test_transaction_acceptance(self, tx, with_witness, accepted):
+        tx_message = msg_tx(tx)
+        if with_witness:
+            tx_message = msg_witness_tx(tx)
+        self.send_message(tx_message)
+        self.sync_with_ping()
+        assert_equal(tx.hash in self.connection.rpc.getrawmempool(), accepted)
+
+    # Test whether a witness block had the correct effect on the tip
+    def test_witness_block(self, block, accepted, with_witness=True):
+        if with_witness:
+            self.send_message(msg_witness_block(block))
+        else:
+            self.send_message(msg_block(block))
+        self.sync_with_ping()
+        assert_equal(self.connection.rpc.getbestblockhash() == block.hash, accepted)
+
+
+# Used to keep track of anyone-can-spend outputs that we can use in the tests
+class UTXO(object):
+    def __init__(self, sha256, n, nValue):
+        self.sha256 = sha256
+        self.n = n
+        self.nValue = nValue
+
+
+class SegWitTest(BitcoinTestFramework):
+    def setup_chain(self):
+        initialize_chain_clean(self.options.tmpdir, 3)
+
+    def add_options(self, parser):
+        parser.add_option("--oldbinary", dest="oldbinary",
+                          default=None,
+                          help="pre-segwit bitcoind binary for upgrade testing")
+
+    def setup_network(self):
+        self.nodes = []
+        self.nodes.append(start_node(0, self.options.tmpdir, ["-debug", "-logtimemicros=1", "-whitelist=127.0.0.1"]))
+        # Start a node for testing IsStandard rules.
+        self.nodes.append(start_node(1, self.options.tmpdir, ["-debug", "-logtimemicros=1", "-whitelist=127.0.0.1", "-acceptnonstdtxn=0"]))
+        connect_nodes(self.nodes[0], 1)
+
+        # If an old bitcoind is given, do the upgrade-after-activation test.
+        self.test_upgrade = False
+        if (self.options.oldbinary != None):
+            self.nodes.append(start_node(2, self.options.tmpdir, ["-debug", "-whitelist=127.0.0.1"], binary=self.options.oldbinary))
+            connect_nodes(self.nodes[0], 2)
+            self.test_upgrade = True
+
+    ''' Helpers '''
+    # Build a block on top of node0's tip.
+    def build_next_block(self, nVersion=4):
+        tip = self.nodes[0].getbestblockhash()
+        height = self.nodes[0].getblockcount() + 1
+        block_time = self.nodes[0].getblockheader(tip)["mediantime"] + 1
+        block = create_block(int(tip, 16), create_coinbase(height), block_time)
+        block.nVersion = nVersion
+        block.rehash()
+        return block
+
+    # Adds list of transactions to block, adds witness commitment, then solves.
+    def update_witness_block_with_transactions(self, block, tx_list, nonce=0):
+        block.vtx.extend(tx_list)
+        add_witness_commitment(block, nonce)
+        block.solve()
+        return
+
+    ''' Individual tests '''
+    def test_witness_services(self):
+        print("\tVerifying NODE_WITNESS service bit")
+        assert((self.test_node.connection.nServices & NODE_WITNESS) != 0)
+
+
+    # See if sending a regular transaction works, and create a utxo
+    # to use in later tests.
+    def test_non_witness_transaction(self):
+        # Mine a block with an anyone-can-spend coinbase,
+        # let it mature, then try to spend it.
+        print("\tTesting non-witness transaction")
+        block = self.build_next_block(nVersion=1)
+        block.solve()
+        self.test_node.send_message(msg_block(block))
+        self.test_node.sync_with_ping() # make sure the block was processed
+        txid = block.vtx[0].sha256
+
+        self.nodes[0].generate(99) # let the block mature
+
+        # Create a transaction that spends the coinbase
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(txid, 0), b""))
+        tx.vout.append(CTxOut(49*100000000, CScript([OP_TRUE])))
+        tx.calc_sha256()
+
+        # Check that serializing it with or without witness is the same
+        # This is a sanity check of our testing framework.
+        assert_equal(msg_tx(tx).serialize(), msg_witness_tx(tx).serialize())
+
+        self.test_node.send_message(msg_witness_tx(tx))
+        self.test_node.sync_with_ping() # make sure the tx was processed
+        assert(tx.hash in self.nodes[0].getrawmempool())
+        # Save this transaction for later
+        self.utxo.append(UTXO(tx.sha256, 0, 49*100000000))
+        self.nodes[0].generate(1)
+
+
+    # Verify that blocks with witnesses are rejected before activation.
+    def test_unnecessary_witness_before_segwit_activation(self):
+        print("\tTesting behavior of unnecessary witnesses")
+        # For now, rely on earlier tests to have created at least one utxo for
+        # us to use
+        assert(len(self.utxo) > 0)
+        assert(get_bip9_status(self.nodes[0], 'segwit')['status'] != 'active')
+
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b""))
+        tx.vout.append(CTxOut(self.utxo[0].nValue-1000, CScript([OP_TRUE])))
+        tx.wit.vtxinwit.append(CTxinWitness())
+        tx.wit.vtxinwit[0].scriptWitness.stack = [CScript([CScriptNum(1)])]
+
+        # Verify the hash with witness differs from the txid
+        # (otherwise our testing framework must be broken!)
+        tx.rehash()
+        assert(tx.sha256 != tx.calc_sha256(with_witness=True))
+
+        # Construct a segwit-signaling block that includes the transaction.
+        block = self.build_next_block(nVersion=(VB_TOP_BITS|(1 << VB_WITNESS_BIT)))
+        self.update_witness_block_with_transactions(block, [tx])
+        # Sending witness data before activation is not allowed (anti-spam
+        # rule).
+        self.test_node.test_witness_block(block, accepted=False)
+        # TODO: fix synchronization so we can test reject reason
+        # Right now, bitcoind delays sending reject messages for blocks
+        # until the future, making synchronization here difficult.
+        #assert_equal(self.test_node.last_reject.reason, "unexpected-witness")
+
+        # But it should not be permanently marked bad...
+        # Resend without witness information.
+        self.test_node.send_message(msg_block(block))
+        self.test_node.sync_with_ping()
+        assert_equal(self.nodes[0].getbestblockhash(), block.hash)
+
+        # Update our utxo list; we spent the first entry.
+        self.utxo.pop(0)
+        self.utxo.append(UTXO(tx.sha256, 0, tx.vout[0].nValue))
+
+
+    # Mine enough blocks for segwit's vb state to be 'started'.
+    def advance_to_segwit_started(self):
+        height = self.nodes[0].getblockcount()
+        # Will need to rewrite the tests here if we are past the first period
+        assert(height < VB_PERIOD - 1)
+        # Genesis block is 'defined'.
+        assert_equal(get_bip9_status(self.nodes[0], 'segwit')['status'], 'defined')
+        # Advance to end of period, status should now be 'started'
+        self.nodes[0].generate(VB_PERIOD-height-1)
+        assert_equal(get_bip9_status(self.nodes[0], 'segwit')['status'], 'started')
+
+    # Mine enough blocks to lock in segwit, but don't activate.
+    # TODO: we could verify that lockin only happens at the right threshold of
+    # signalling blocks, rather than just at the right period boundary.
+    def advance_to_segwit_lockin(self):
+        height = self.nodes[0].getblockcount()
+        assert_equal(get_bip9_status(self.nodes[0], 'segwit')['status'], 'started')
+        # Advance to end of period, and verify lock-in happens at the end
+        self.nodes[0].generate(VB_PERIOD-1)
+        height = self.nodes[0].getblockcount()
+        assert((height % VB_PERIOD) == VB_PERIOD - 2)
+        assert_equal(get_bip9_status(self.nodes[0], 'segwit')['status'], 'started')
+        self.nodes[0].generate(1)
+        assert_equal(get_bip9_status(self.nodes[0], 'segwit')['status'], 'locked_in')
+
+
+    # Mine enough blocks to activate segwit.
+    # TODO: we could verify that activation only happens at the right threshold
+    # of signalling blocks, rather than just at the right period boundary.
+    def advance_to_segwit_active(self):
+        assert_equal(get_bip9_status(self.nodes[0], 'segwit')['status'], 'locked_in')
+        height = self.nodes[0].getblockcount()
+        self.nodes[0].generate(VB_PERIOD - (height%VB_PERIOD) - 2)
+        assert_equal(get_bip9_status(self.nodes[0], 'segwit')['status'], 'locked_in')
+        self.nodes[0].generate(1)
+        assert_equal(get_bip9_status(self.nodes[0], 'segwit')['status'], 'active')
+
+
+    # This test can only be run after segwit has activated
+    def test_witness_commitments(self):
+        print("\tTesting witness commitments")
+
+        # First try a correct witness commitment.
+        block = self.build_next_block()
+        add_witness_commitment(block)
+        block.solve()
+
+        # Test the test -- witness serialization should be different
+        assert(msg_witness_block(block).serialize() != msg_block(block).serialize())
+
+        # This empty block should be valid.
+        self.test_node.test_witness_block(block, accepted=True)
+
+        # Try to tweak the nonce
+        block_2 = self.build_next_block()
+        add_witness_commitment(block_2, nonce=28)
+        block_2.solve()
+
+        # The commitment should have changed!
+        assert(block_2.vtx[0].vout[-1] != block.vtx[0].vout[-1])
+
+        # This should also be valid.
+        self.test_node.test_witness_block(block_2, accepted=True)
+
+        # Now test commitments with actual transactions
+        assert (len(self.utxo) > 0)
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b""))
+
+        # Let's construct a witness program
+        witness_program = CScript([OP_TRUE])
+        witness_hash = sha256(witness_program)
+        scriptPubKey = CScript([OP_0, witness_hash])
+        tx.vout.append(CTxOut(self.utxo[0].nValue-1000, scriptPubKey))
+        tx.rehash()
+
+        # tx2 will spend tx1, and send back to a regular anyone-can-spend address
+        tx2 = CTransaction()
+        tx2.vin.append(CTxIn(COutPoint(tx.sha256, 0), b""))
+        tx2.vout.append(CTxOut(tx.vout[0].nValue-1000, witness_program))
+        tx2.wit.vtxinwit.append(CTxinWitness())
+        tx2.wit.vtxinwit[0].scriptWitness.stack = [witness_program]
+        tx2.rehash()
+
+        block_3 = self.build_next_block()
+        self.update_witness_block_with_transactions(block_3, [tx, tx2], nonce=1)
+        # Add an extra OP_RETURN output that matches the witness commitment template,
+        # even though it has extra data after the incorrect commitment.
+        # This block should fail.
+        block_3.vtx[0].vout.append(CTxOut(0, CScript([OP_RETURN, WITNESS_COMMITMENT_HEADER + ser_uint256(2), 10])))
+        block_3.vtx[0].rehash()
+        block_3.hashMerkleRoot = block_3.calc_merkle_root()
+        block_3.rehash()
+        block_3.solve()
+
+        self.test_node.test_witness_block(block_3, accepted=False)
+
+        # Add a different commitment with different nonce, but in the
+        # right location, and with some funds burned(!).
+        # This should succeed (nValue shouldn't affect finding the
+        # witness commitment).
+        add_witness_commitment(block_3, nonce=0)
+        block_3.vtx[0].vout[0].nValue -= 1
+        block_3.vtx[0].vout[-1].nValue += 1
+        block_3.vtx[0].rehash()
+        block_3.hashMerkleRoot = block_3.calc_merkle_root()
+        block_3.rehash()
+        assert(len(block_3.vtx[0].vout) == 4) # 3 OP_returns
+        block_3.solve()
+        self.test_node.test_witness_block(block_3, accepted=True)
+
+        # Finally test that a block with no witness transactions can
+        # omit the commitment.
+        block_4 = self.build_next_block()
+        tx3 = CTransaction()
+        tx3.vin.append(CTxIn(COutPoint(tx2.sha256, 0), b""))
+        tx3.vout.append(CTxOut(tx.vout[0].nValue-1000, witness_program))
+        tx3.rehash()
+        block_4.vtx.append(tx3)
+        block_4.hashMerkleRoot = block_4.calc_merkle_root()
+        block_4.solve()
+        self.test_node.test_witness_block(block_4, with_witness=False, accepted=True)
+
+        # Update available utxo's for use in later test.
+        self.utxo.pop(0)
+        self.utxo.append(UTXO(tx3.sha256, 0, tx3.vout[0].nValue))
+
+
+    def test_block_malleability(self):
+        print("\tTesting witness block malleability")
+
+        # Make sure that a block that has too big a virtual size
+        # because of a too-large coinbase witness is not permanently
+        # marked bad.
+        block = self.build_next_block()
+        add_witness_commitment(block)
+        block.solve()
+
+        block.vtx[0].wit.vtxinwit[0].scriptWitness.stack.append(b'a'*5000000)
+        assert(get_virtual_size(block) > MAX_BLOCK_SIZE)
+
+        # We can't send over the p2p network, because this is too big to relay
+        # TODO: repeat this test with a block that can be relayed
+        self.nodes[0].submitblock(bytes_to_hex_str(block.serialize(True)))
+
+        assert(self.nodes[0].getbestblockhash() != block.hash)
+
+        block.vtx[0].wit.vtxinwit[0].scriptWitness.stack.pop()
+        assert(get_virtual_size(block) < MAX_BLOCK_SIZE)
+        self.nodes[0].submitblock(bytes_to_hex_str(block.serialize(True)))
+
+        assert(self.nodes[0].getbestblockhash() == block.hash)
+
+        # Now make sure that malleating the witness nonce doesn't
+        # result in a block permanently marked bad.
+        block = self.build_next_block()
+        add_witness_commitment(block)
+        block.solve()
+
+        # Change the nonce -- should not cause the block to be permanently
+        # failed
+        block.vtx[0].wit.vtxinwit[0].scriptWitness.stack = [ ser_uint256(1) ]
+        self.test_node.test_witness_block(block, accepted=False)
+
+        # Changing the witness nonce doesn't change the block hash
+        block.vtx[0].wit.vtxinwit[0].scriptWitness.stack = [ ser_uint256(0) ]
+        self.test_node.test_witness_block(block, accepted=True)
+
+
+    def test_witness_block_size(self):
+        print("\tTesting witness block size limit")
+        # TODO: Test that non-witness carrying blocks can't exceed 1MB
+        # Skipping this test for now; this is covered in p2p-fullblocktest.py
+
+        # Test that witness-bearing blocks are limited at ceil(base + wit/4) <= 1MB.
+        block = self.build_next_block()
+
+        assert(len(self.utxo) > 0)
+        
+        # Create a P2WSH transaction.
+        # The witness program will be a bunch of OP_2DROP's, followed by OP_TRUE.
+        # This should give us plenty of room to tweak the spending tx's
+        # virtual size.
+        NUM_DROPS = 200 # 201 max ops per script!
+        NUM_OUTPUTS = 50
+
+        witness_program = CScript([OP_2DROP]*NUM_DROPS + [OP_TRUE])
+        witness_hash = uint256_from_str(sha256(witness_program))
+        scriptPubKey = CScript([OP_0, ser_uint256(witness_hash)])
+
+        prevout = COutPoint(self.utxo[0].sha256, self.utxo[0].n)
+        value = self.utxo[0].nValue
+
+        parent_tx = CTransaction()
+        parent_tx.vin.append(CTxIn(prevout, b""))
+        child_value = int(value/NUM_OUTPUTS)
+        for i in range(NUM_OUTPUTS):
+            parent_tx.vout.append(CTxOut(child_value, scriptPubKey))
+        parent_tx.vout[0].nValue -= 50000
+        assert(parent_tx.vout[0].nValue > 0)
+        parent_tx.rehash()
+
+        child_tx = CTransaction()
+        for i in range(NUM_OUTPUTS):
+            child_tx.vin.append(CTxIn(COutPoint(parent_tx.sha256, i), b""))
+        child_tx.vout = [CTxOut(value - 100000, CScript([OP_TRUE]))]
+        for i in range(NUM_OUTPUTS):
+            child_tx.wit.vtxinwit.append(CTxinWitness())
+            child_tx.wit.vtxinwit[-1].scriptWitness.stack = [b'a'*195]*(2*NUM_DROPS) + [witness_program]
+        child_tx.rehash()
+        self.update_witness_block_with_transactions(block, [parent_tx, child_tx])
+
+        vsize = get_virtual_size(block)
+        additional_bytes = (MAX_BLOCK_SIZE - vsize)*4
+        i = 0
+        while additional_bytes > 0:
+            # Add some more bytes to each input until we hit MAX_BLOCK_SIZE+1
+            extra_bytes = min(additional_bytes+1, 55)
+            block.vtx[-1].wit.vtxinwit[int(i/(2*NUM_DROPS))].scriptWitness.stack[i%(2*NUM_DROPS)] = b'a'*(195+extra_bytes)
+            additional_bytes -= extra_bytes
+            i += 1
+
+        block.vtx[0].vout.pop()  # Remove old commitment
+        add_witness_commitment(block)
+        block.solve()
+        vsize = get_virtual_size(block)
+        assert_equal(vsize, MAX_BLOCK_SIZE + 1)
+        # Make sure that our test case would exceed the old max-network-message
+        # limit
+        assert(len(block.serialize(True)) > 2*1024*1024)
+
+        self.test_node.test_witness_block(block, accepted=False)
+
+        # Now resize the second transaction to make the block fit.
+        cur_length = len(block.vtx[-1].wit.vtxinwit[0].scriptWitness.stack[0])
+        block.vtx[-1].wit.vtxinwit[0].scriptWitness.stack[0] = b'a'*(cur_length-1)
+        block.vtx[0].vout.pop()
+        add_witness_commitment(block)
+        block.solve()
+        assert(get_virtual_size(block) == MAX_BLOCK_SIZE)
+
+        self.test_node.test_witness_block(block, accepted=True)
+
+        # Update available utxo's
+        self.utxo.pop(0)
+        self.utxo.append(UTXO(block.vtx[-1].sha256, 0, block.vtx[-1].vout[0].nValue))
+
+
+    # submitblock will try to add the nonce automatically, so that mining
+    # software doesn't need to worry about doing so itself.
+    def test_submit_block(self):
+        block = self.build_next_block()
+
+        # Try using a custom nonce and then don't supply it.
+        # This shouldn't possibly work.
+        add_witness_commitment(block, nonce=1)
+        block.vtx[0].wit = CTxWitness() # drop the nonce
+        block.solve()
+        self.nodes[0].submitblock(bytes_to_hex_str(block.serialize(True)))
+        assert(self.nodes[0].getbestblockhash() != block.hash)
+
+        # Now redo commitment with the standard nonce, but let bitcoind fill it in.
+        add_witness_commitment(block, nonce=0)
+        block.vtx[0].wit = CTxWitness()
+        block.solve()
+        self.nodes[0].submitblock(bytes_to_hex_str(block.serialize(True)))
+        assert_equal(self.nodes[0].getbestblockhash(), block.hash)
+
+        # This time, add a tx with non-empty witness, but don't supply
+        # the commitment.
+        block_2 = self.build_next_block()
+
+        add_witness_commitment(block_2)
+
+        block_2.solve()
+
+        # Drop commitment and nonce -- submitblock should not fill in.
+        block_2.vtx[0].vout.pop()
+        block_2.vtx[0].wit = CTxWitness()
+
+        self.nodes[0].submitblock(bytes_to_hex_str(block_2.serialize(True)))
+        # Tip should not advance!
+        assert(self.nodes[0].getbestblockhash() != block_2.hash)
+
+
+    # Consensus tests of extra witness data in a transaction.
+    def test_extra_witness_data(self):
+        print("\tTesting extra witness data in tx")
+
+        assert(len(self.utxo) > 0)
+        
+        block = self.build_next_block()
+
+        witness_program = CScript([OP_DROP, OP_TRUE])
+        witness_hash = sha256(witness_program)
+        scriptPubKey = CScript([OP_0, witness_hash])
+
+        # First try extra witness data on a tx that doesn't require a witness
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b""))
+        tx.vout.append(CTxOut(self.utxo[0].nValue-2000, scriptPubKey))
+        tx.vout.append(CTxOut(1000, CScript([OP_TRUE]))) # non-witness output
+        tx.wit.vtxinwit.append(CTxinWitness())
+        tx.wit.vtxinwit[0].scriptWitness.stack = [CScript([])]
+        tx.rehash()
+        self.update_witness_block_with_transactions(block, [tx])
+
+        # Extra witness data should not be allowed.
+        self.test_node.test_witness_block(block, accepted=False)
+
+        # Try extra signature data.  Ok if we're not spending a witness output.
+        block.vtx[1].wit.vtxinwit = []
+        block.vtx[1].vin[0].scriptSig = CScript([OP_0])
+        block.vtx[1].rehash()
+        add_witness_commitment(block)
+        block.solve()
+
+        self.test_node.test_witness_block(block, accepted=True)
+
+        # Now try extra witness/signature data on an input that DOES require a
+        # witness
+        tx2 = CTransaction()
+        tx2.vin.append(CTxIn(COutPoint(tx.sha256, 0), b"")) # witness output
+        tx2.vin.append(CTxIn(COutPoint(tx.sha256, 1), b"")) # non-witness
+        tx2.vout.append(CTxOut(tx.vout[0].nValue, CScript([OP_TRUE])))
+        tx2.wit.vtxinwit.extend([CTxinWitness(), CTxinWitness()])
+        tx2.wit.vtxinwit[0].scriptWitness.stack = [ CScript([CScriptNum(1)]), CScript([CScriptNum(1)]), witness_program ]
+        tx2.wit.vtxinwit[1].scriptWitness.stack = [ CScript([OP_TRUE]) ]
+
+        block = self.build_next_block()
+        self.update_witness_block_with_transactions(block, [tx2])
+
+        # This has extra witness data, so it should fail.
+        self.test_node.test_witness_block(block, accepted=False)
+
+        # Now get rid of the extra witness, but add extra scriptSig data
+        tx2.vin[0].scriptSig = CScript([OP_TRUE])
+        tx2.vin[1].scriptSig = CScript([OP_TRUE])
+        tx2.wit.vtxinwit[0].scriptWitness.stack.pop(0)
+        tx2.wit.vtxinwit[1].scriptWitness.stack = []
+        tx2.rehash()
+        add_witness_commitment(block)
+        block.solve()
+
+        # This has extra signature data for a witness input, so it should fail.
+        self.test_node.test_witness_block(block, accepted=False)
+
+        # Now get rid of the extra scriptsig on the witness input, and verify
+        # success (even with extra scriptsig data in the non-witness input)
+        tx2.vin[0].scriptSig = b""
+        tx2.rehash()
+        add_witness_commitment(block)
+        block.solve()
+
+        self.test_node.test_witness_block(block, accepted=True)
+
+        # Update utxo for later tests
+        self.utxo.pop(0)
+        self.utxo.append(UTXO(tx2.sha256, 0, tx2.vout[0].nValue))
+
+
+    def test_max_witness_push_length(self):
+        ''' Should only allow up to 520 byte pushes in witness stack '''
+        print("\tTesting maximum witness push size")
+        MAX_SCRIPT_ELEMENT_SIZE = 520
+        assert(len(self.utxo))
+
+        block = self.build_next_block()
+
+        witness_program = CScript([OP_DROP, OP_TRUE])
+        witness_hash = sha256(witness_program)
+        scriptPubKey = CScript([OP_0, witness_hash])
+
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b""))
+        tx.vout.append(CTxOut(self.utxo[0].nValue-1000, scriptPubKey))
+        tx.rehash()
+
+        tx2 = CTransaction()
+        tx2.vin.append(CTxIn(COutPoint(tx.sha256, 0), b""))
+        tx2.vout.append(CTxOut(tx.vout[0].nValue-1000, CScript([OP_TRUE])))
+        tx2.wit.vtxinwit.append(CTxinWitness())
+        # First try a 521-byte stack element
+        tx2.wit.vtxinwit[0].scriptWitness.stack = [ b'a'*(MAX_SCRIPT_ELEMENT_SIZE+1), witness_program ]
+        tx2.rehash()
+
+        self.update_witness_block_with_transactions(block, [tx, tx2])
+        self.test_node.test_witness_block(block, accepted=False)
+
+        # Now reduce the length of the stack element
+        tx2.wit.vtxinwit[0].scriptWitness.stack[0] = b'a'*(MAX_SCRIPT_ELEMENT_SIZE)
+
+        add_witness_commitment(block)
+        block.solve()
+        self.test_node.test_witness_block(block, accepted=True)
+
+        # Update the utxo for later tests
+        self.utxo.pop()
+        self.utxo.append(UTXO(tx2.sha256, 0, tx2.vout[0].nValue))
+
+    def test_max_witness_program_length(self):
+        # Can create witness outputs that are long, but can't be greater than
+        # 10k bytes to successfully spend
+        print("\tTesting maximum witness program length")
+        assert(len(self.utxo))
+        MAX_PROGRAM_LENGTH = 10000
+
+        # This program is 19 max pushes (9937 bytes), then 64 more opcode-bytes.
+        long_witness_program = CScript([b'a'*520]*19 + [OP_DROP]*63 + [OP_TRUE])
+        assert(len(long_witness_program) == MAX_PROGRAM_LENGTH+1)
+        long_witness_hash = sha256(long_witness_program)
+        long_scriptPubKey = CScript([OP_0, long_witness_hash])
+
+        block = self.build_next_block()
+
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b""))
+        tx.vout.append(CTxOut(self.utxo[0].nValue-1000, long_scriptPubKey))
+        tx.rehash()
+
+        tx2 = CTransaction()
+        tx2.vin.append(CTxIn(COutPoint(tx.sha256, 0), b""))
+        tx2.vout.append(CTxOut(tx.vout[0].nValue-1000, CScript([OP_TRUE])))
+        tx2.wit.vtxinwit.append(CTxinWitness())
+        tx2.wit.vtxinwit[0].scriptWitness.stack = [b'a']*44 + [long_witness_program]
+        tx2.rehash()
+
+        self.update_witness_block_with_transactions(block, [tx, tx2])
+
+        self.test_node.test_witness_block(block, accepted=False)
+
+        # Try again with one less byte in the witness program
+        witness_program = CScript([b'a'*520]*19 + [OP_DROP]*62 + [OP_TRUE])
+        assert(len(witness_program) == MAX_PROGRAM_LENGTH)
+        witness_hash = sha256(witness_program)
+        scriptPubKey = CScript([OP_0, witness_hash])
+
+        tx.vout[0] = CTxOut(tx.vout[0].nValue, scriptPubKey)
+        tx.rehash()
+        tx2.vin[0].prevout.hash = tx.sha256
+        tx2.wit.vtxinwit[0].scriptWitness.stack = [b'a']*43 + [witness_program]
+        tx2.rehash()
+        block.vtx = [block.vtx[0]]
+        self.update_witness_block_with_transactions(block, [tx, tx2])
+        self.test_node.test_witness_block(block, accepted=True)
+
+        self.utxo.pop()
+        self.utxo.append(UTXO(tx2.sha256, 0, tx2.vout[0].nValue))
+
+
+    def test_witness_input_length(self):
+        ''' Ensure that vin length must match vtxinwit length '''
+        print("\tTesting witness input length")
+        assert(len(self.utxo))
+
+        witness_program = CScript([OP_DROP, OP_TRUE])
+        witness_hash = sha256(witness_program)
+        scriptPubKey = CScript([OP_0, witness_hash])
+        
+        # Create a transaction that splits our utxo into many outputs
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b""))
+        nValue = self.utxo[0].nValue
+        for i in range(10):
+            tx.vout.append(CTxOut(int(nValue/10), scriptPubKey))
+        tx.vout[0].nValue -= 1000
+        assert(tx.vout[0].nValue >= 0)
+
+        block = self.build_next_block()
+        self.update_witness_block_with_transactions(block, [tx])
+        self.test_node.test_witness_block(block, accepted=True)
+
+        # Try various ways to spend tx that should all break.
+        # This "broken" transaction serializer will not normalize
+        # the length of vtxinwit.
+        class BrokenCTransaction(CTransaction):
+            def serialize_with_witness(self):
+                flags = 0
+                if not self.wit.is_null():
+                    flags |= 1
+                r = b""
+                r += struct.pack("<i", self.nVersion)
+                if flags:
+                    dummy = []
+                    r += ser_vector(dummy)
+                    r += struct.pack("<B", flags)
+                r += ser_vector(self.vin)
+                r += ser_vector(self.vout)
+                if flags & 1:
+                    r += self.wit.serialize()
+                r += struct.pack("<I", self.nLockTime)
+                return r
+
+        tx2 = BrokenCTransaction()
+        for i in range(10):
+            tx2.vin.append(CTxIn(COutPoint(tx.sha256, i), b""))
+        tx2.vout.append(CTxOut(nValue-3000, CScript([OP_TRUE])))
+
+        # First try using a too long vtxinwit
+        for i in range(11):
+            tx2.wit.vtxinwit.append(CTxinWitness())
+            tx2.wit.vtxinwit[i].scriptWitness.stack = [b'a', witness_program]
+
+        block = self.build_next_block()
+        self.update_witness_block_with_transactions(block, [tx2])
+        self.test_node.test_witness_block(block, accepted=False)
+
+        # Now try using a too short vtxinwit
+        tx2.wit.vtxinwit.pop()
+        tx2.wit.vtxinwit.pop()
+
+        block.vtx = [block.vtx[0]]
+        self.update_witness_block_with_transactions(block, [tx2])
+        self.test_node.test_witness_block(block, accepted=False)
+
+        # Now make one of the intermediate witnesses be incorrect
+        tx2.wit.vtxinwit.append(CTxinWitness())
+        tx2.wit.vtxinwit[-1].scriptWitness.stack = [b'a', witness_program]
+        tx2.wit.vtxinwit[5].scriptWitness.stack = [ witness_program ]
+
+        block.vtx = [block.vtx[0]]
+        self.update_witness_block_with_transactions(block, [tx2])
+        self.test_node.test_witness_block(block, accepted=False)
+
+        # Fix the broken witness and the block should be accepted.
+        tx2.wit.vtxinwit[5].scriptWitness.stack = [b'a', witness_program]
+        block.vtx = [block.vtx[0]]
+        self.update_witness_block_with_transactions(block, [tx2])
+        self.test_node.test_witness_block(block, accepted=True)
+
+        self.utxo.pop()
+        self.utxo.append(UTXO(tx2.sha256, 0, tx2.vout[0].nValue))
+
+
+    def test_witness_tx_relay_before_segwit_activation(self):
+        print("\tTesting relay of witness transactions")
+        # Generate a transaction that doesn't require a witness, but send it
+        # with a witness.  Should be rejected for premature-witness, but should
+        # not be added to recently rejected list.
+        assert(len(self.utxo))
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b""))
+        tx.vout.append(CTxOut(self.utxo[0].nValue-1000, CScript([OP_TRUE])))
+        tx.wit.vtxinwit.append(CTxinWitness())
+        tx.wit.vtxinwit[0].scriptWitness.stack = [ b'a' ]
+        tx.rehash()
+
+        tx_hash = tx.sha256
+        tx_value = tx.vout[0].nValue
+
+        # Verify that if a peer doesn't set nServices to include NODE_WITNESS,
+        # the getdata is just for the non-witness portion.
+        self.old_node.announce_tx_and_wait_for_getdata(tx)
+        assert(self.old_node.last_getdata.inv[0].type == 1)
+
+        # Since we haven't delivered the tx yet, inv'ing the same tx from
+        # a witness transaction ought not result in a getdata.
+        try:
+            self.test_node.announce_tx_and_wait_for_getdata(tx, timeout=2)
+            print("Error: duplicate tx getdata!")
+            assert(False)
+        except AssertionError as e:
+            pass
+
+        # Delivering this transaction with witness should fail (no matter who
+        # its from)
+        assert_equal(len(self.nodes[0].getrawmempool()), 0)
+        assert_equal(len(self.nodes[1].getrawmempool()), 0)
+        self.old_node.test_transaction_acceptance(tx, with_witness=True, accepted=False)
+        self.test_node.test_transaction_acceptance(tx, with_witness=True, accepted=False)
+
+        # But eliminating the witness should fix it
+        self.test_node.test_transaction_acceptance(tx, with_witness=False, accepted=True)
+
+        # Verify that inv's to test_node come with getdata's for non-witness tx's
+        # Just tweak the transaction, announce it, and verify we get a getdata
+        # for a normal tx
+        tx.vout[0].scriptPubKey = CScript([OP_TRUE, OP_TRUE])
+        tx.rehash()
+        self.test_node.announce_tx_and_wait_for_getdata(tx)
+        assert(self.test_node.last_getdata.inv[0].type == 1)
+
+        # Cleanup: mine the first transaction and update utxo
+        self.nodes[0].generate(1)
+        assert_equal(len(self.nodes[0].getrawmempool()),  0)
+
+        self.utxo.pop(0)
+        self.utxo.append(UTXO(tx_hash, 0, tx_value))
+
+
+    # After segwit activates, verify that mempool:
+    # - rejects transactions with unnecessary/extra witnesses
+    # - accepts transactions with valid witnesses
+    # and that witness transactions are relayed to non-upgraded peers.
+    def test_tx_relay_after_segwit_activation(self):
+        print("\tTesting relay of witness transactions")
+        # Generate a transaction that doesn't require a witness, but send it
+        # with a witness.  Should be rejected because we can't use a witness
+        # when spending a non-witness output.
+        assert(len(self.utxo))
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b""))
+        tx.vout.append(CTxOut(self.utxo[0].nValue-1000, CScript([OP_TRUE])))
+        tx.wit.vtxinwit.append(CTxinWitness())
+        tx.wit.vtxinwit[0].scriptWitness.stack = [ b'a' ]
+        tx.rehash()
+
+        tx_hash = tx.sha256
+        tx_value = tx.vout[0].nValue
+
+        # Verify that unnecessary witnesses are rejected.
+        self.test_node.announce_tx_and_wait_for_getdata(tx)
+        assert_equal(len(self.nodes[0].getrawmempool()), 0)
+        self.test_node.test_transaction_acceptance(tx, with_witness=True, accepted=False)
+
+        # Verify that removing the witness succeeds.
+        # Re-announcing won't result in a getdata for ~2.5 minutes, so just
+        # deliver the modified transaction.
+        self.test_node.test_transaction_acceptance(tx, with_witness=False, accepted=True)
+
+        # Now try to add extra witness data to a valid witness tx.
+        witness_program = CScript([OP_TRUE])
+        witness_hash = sha256(witness_program)
+        scriptPubKey = CScript([OP_0, witness_hash])
+        tx2 = CTransaction()
+        tx2.vin.append(CTxIn(COutPoint(tx_hash, 0), b""))
+        tx2.vout.append(CTxOut(tx.vout[0].nValue-1000, scriptPubKey))
+        tx2.rehash()
+
+        tx3 = CTransaction()
+        tx3.vin.append(CTxIn(COutPoint(tx2.sha256, 0), b""))
+        tx3.vout.append(CTxOut(tx2.vout[0].nValue-1000, CScript([OP_TRUE])))
+        tx3.wit.vtxinwit.append(CTxinWitness())
+        tx3.wit.vtxinwit[0].scriptWitness.stack = [CScript([CScriptNum(1)]), witness_program ]
+        tx3.rehash()
+
+        self.test_node.test_transaction_acceptance(tx2, with_witness=True, accepted=True)
+        self.test_node.test_transaction_acceptance(tx3, with_witness=True, accepted=False)
+
+        # Get rid of the extra witness, and verify acceptance.
+        tx3.wit.vtxinwit[0].scriptWitness.stack = [ witness_program ]
+        # Also check that old_node gets a tx announcement, even though this is
+        # a witness transaction.
+        self.old_node.wait_for_inv(CInv(1, tx2.sha256)) # wait until tx2 was inv'ed
+        self.test_node.test_transaction_acceptance(tx3, with_witness=True, accepted=True)
+        self.old_node.wait_for_inv(CInv(1, tx3.sha256))
+
+        # Test that getrawtransaction returns correct witness information
+        # hash, size, vsize
+        raw_tx = self.nodes[0].getrawtransaction(tx3.hash, 1)
+        assert_equal(int(raw_tx["hash"], 16), tx3.calc_sha256(True))
+        assert_equal(raw_tx["size"], len(tx3.serialize_with_witness()))
+        vsize = (len(tx3.serialize_with_witness()) + 3*len(tx3.serialize_without_witness()) + 3) / 4
+        assert_equal(raw_tx["vsize"], vsize)
+        assert_equal(len(raw_tx["vin"][0]["txinwitness"]), 1)
+        assert_equal(raw_tx["vin"][0]["txinwitness"][0], hexlify(witness_program).decode('ascii'))
+        assert(vsize != raw_tx["size"])
+
+        # Cleanup: mine the transactions and update utxo for next test
+        self.nodes[0].generate(1)
+        assert_equal(len(self.nodes[0].getrawmempool()),  0)
+
+        self.utxo.pop(0)
+        self.utxo.append(UTXO(tx3.sha256, 0, tx3.vout[0].nValue))
+
+
+    # Test that block requests to NODE_WITNESS peer are with MSG_WITNESS_FLAG
+    # This is true regardless of segwit activation.
+    # Also test that we don't ask for blocks from unupgraded peers
+    def test_block_relay(self, segwit_activated):
+        print("\tTesting block relay")
+
+        blocktype = 2|MSG_WITNESS_FLAG if segwit_activated else 2
+
+        # test_node has set NODE_WITNESS, so all getdata requests should be for
+        # witness blocks.
+        # Test announcing a block via inv results in a getdata, and that
+        # announcing a version 4 or random VB block with a header results in a getdata
+        block1 = self.build_next_block()
+        block1.solve()
+
+        self.test_node.announce_block_and_wait_for_getdata(block1, use_header=False)
+        assert(self.test_node.last_getdata.inv[0].type == blocktype)
+        self.test_node.test_witness_block(block1, True)
+
+        block2 = self.build_next_block(nVersion=4)
+        block2.solve()
+
+        self.test_node.announce_block_and_wait_for_getdata(block2, use_header=True)
+        assert(self.test_node.last_getdata.inv[0].type == blocktype)
+        self.test_node.test_witness_block(block2, True)
+
+        block3 = self.build_next_block(nVersion=(VB_TOP_BITS | (1<<15)))
+        block3.solve()
+        self.test_node.announce_block_and_wait_for_getdata(block3, use_header=True)
+        assert(self.test_node.last_getdata.inv[0].type == blocktype)
+        self.test_node.test_witness_block(block3, True)
+
+        # Check that we can getdata for witness blocks or regular blocks,
+        # and the right thing happens.
+        if segwit_activated == False:
+            # Before activation, we should be able to request old blocks with
+            # or without witness, and they should be the same.
+            chain_height = self.nodes[0].getblockcount()
+            # Pick 10 random blocks on main chain, and verify that getdata's
+            # for MSG_BLOCK, MSG_WITNESS_BLOCK, and rpc getblock() are equal.
+            all_heights = list(range(chain_height+1))
+            random.shuffle(all_heights)
+            all_heights = all_heights[0:10]
+            for height in all_heights:
+                block_hash = self.nodes[0].getblockhash(height)
+                rpc_block = self.nodes[0].getblock(block_hash, False)
+                block_hash = int(block_hash, 16)
+                block = self.test_node.request_block(block_hash, 2)
+                wit_block = self.test_node.request_block(block_hash, 2|MSG_WITNESS_FLAG)
+                assert_equal(block.serialize(True), wit_block.serialize(True))
+                assert_equal(block.serialize(), hex_str_to_bytes(rpc_block))
+        else:
+            # After activation, witness blocks and non-witness blocks should
+            # be different.  Verify rpc getblock() returns witness blocks, while
+            # getdata respects the requested type.
+            block = self.build_next_block()
+            self.update_witness_block_with_transactions(block, [])
+            # This gives us a witness commitment.
+            assert(len(block.vtx[0].wit.vtxinwit) == 1)
+            assert(len(block.vtx[0].wit.vtxinwit[0].scriptWitness.stack) == 1)
+            self.test_node.test_witness_block(block, accepted=True)
+            # Now try to retrieve it...
+            rpc_block = self.nodes[0].getblock(block.hash, False)
+            non_wit_block = self.test_node.request_block(block.sha256, 2)
+            wit_block = self.test_node.request_block(block.sha256, 2|MSG_WITNESS_FLAG)
+            assert_equal(wit_block.serialize(True), hex_str_to_bytes(rpc_block))
+            assert_equal(wit_block.serialize(False), non_wit_block.serialize())
+            assert_equal(wit_block.serialize(True), block.serialize(True))
+
+            # Test size, vsize, cost
+            rpc_details = self.nodes[0].getblock(block.hash, True)
+            assert_equal(rpc_details["size"], len(block.serialize(True)))
+            assert_equal(rpc_details["strippedsize"], len(block.serialize(False)))
+            cost = 3*len(block.serialize(False)) + len(block.serialize(True))
+            assert_equal(rpc_details["cost"], cost)
+
+            # Upgraded node should not ask for blocks from unupgraded
+            block4 = self.build_next_block(nVersion=4)
+            block4.solve()
+            self.old_node.getdataset = set()
+            # Blocks can be requested via direct-fetch (immediately upon processing the announcement)
+            # or via parallel download (with an indeterminate delay from processing the announcement)
+            # so to test that a block is NOT requested, we could guess a time period to sleep for,
+            # and then check. We can avoid the sleep() by taking advantage of transaction getdata's
+            # being processed after block getdata's, and announce a transaction as well,
+            # and then check to see if that particular getdata has been received.
+            self.old_node.announce_block(block4, use_header=False)
+            self.old_node.announce_tx_and_wait_for_getdata(block4.vtx[0])
+            assert(block4.sha256 not in self.old_node.getdataset)
+
+    # Verify that future segwit upgraded transactions are non-standard,
+    # but valid in blocks. Can run this before and after segwit activation.
+    def test_segwit_versions(self):
+        print("\tTesting standardness/consensus for segwit versions (0-16)")
+        assert(len(self.utxo))
+        NUM_TESTS = 17 # will test OP_0, OP1, ..., OP_16
+        if (len(self.utxo) < NUM_TESTS):
+            tx = CTransaction()
+            tx.vin.append(CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b""))
+            split_value = (self.utxo[0].nValue - 4000) // NUM_TESTS
+            for i in range(NUM_TESTS):
+                tx.vout.append(CTxOut(split_value, CScript([OP_TRUE])))
+            tx.rehash()
+            block = self.build_next_block()
+            self.update_witness_block_with_transactions(block, [tx])
+            self.test_node.test_witness_block(block, accepted=True)
+            self.utxo.pop(0)
+            for i in range(NUM_TESTS):
+                self.utxo.append(UTXO(tx.sha256, i, split_value))
+
+        sync_blocks(self.nodes)
+        temp_utxo = []
+        tx = CTransaction()
+        count = 0
+        witness_program = CScript([OP_TRUE])
+        witness_hash = sha256(witness_program)
+        assert_equal(len(self.nodes[1].getrawmempool()), 0)
+        for version in list(range(OP_1, OP_16+1)) + [OP_0]:
+            count += 1
+            # First try to spend to a future version segwit scriptPubKey.
+            scriptPubKey = CScript([CScriptOp(version), witness_hash])
+            tx.vin = [CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b"")]
+            tx.vout = [CTxOut(self.utxo[0].nValue-1000, scriptPubKey)]
+            tx.rehash()
+            self.std_node.test_transaction_acceptance(tx, with_witness=True, accepted=False)
+            self.test_node.test_transaction_acceptance(tx, with_witness=True, accepted=True)
+            self.utxo.pop(0)
+            temp_utxo.append(UTXO(tx.sha256, 0, tx.vout[0].nValue))
+
+        self.nodes[0].generate(1) # Mine all the transactions
+        sync_blocks(self.nodes)
+        assert(len(self.nodes[0].getrawmempool()) == 0)
+
+        # Finally, verify that version 0 -> version 1 transactions
+        # are non-standard
+        scriptPubKey = CScript([CScriptOp(OP_1), witness_hash])
+        tx2 = CTransaction()
+        tx2.vin = [CTxIn(COutPoint(tx.sha256, 0), b"")]
+        tx2.vout = [CTxOut(tx.vout[0].nValue-1000, scriptPubKey)]
+        tx2.wit.vtxinwit.append(CTxinWitness())
+        tx2.wit.vtxinwit[0].scriptWitness.stack = [ witness_program ]
+        tx2.rehash()
+        # Gets accepted to test_node, because standardness of outputs isn't
+        # checked with fRequireStandard
+        self.test_node.test_transaction_acceptance(tx2, with_witness=True, accepted=True)
+        self.std_node.test_transaction_acceptance(tx2, with_witness=True, accepted=False)
+        temp_utxo.pop() # last entry in temp_utxo was the output we just spent
+        temp_utxo.append(UTXO(tx2.sha256, 0, tx2.vout[0].nValue))
+
+        # Spend everything in temp_utxo back to an OP_TRUE output.
+        tx3 = CTransaction()
+        total_value = 0
+        for i in temp_utxo:
+            tx3.vin.append(CTxIn(COutPoint(i.sha256, i.n), b""))
+            tx3.wit.vtxinwit.append(CTxinWitness())
+            total_value += i.nValue
+        tx3.wit.vtxinwit[-1].scriptWitness.stack = [witness_program]
+        tx3.vout.append(CTxOut(total_value - 1000, CScript([OP_TRUE])))
+        tx3.rehash()
+        # Spending a higher version witness output is not allowed by policy,
+        # even with fRequireStandard=false.
+        self.test_node.test_transaction_acceptance(tx3, with_witness=True, accepted=False)
+        self.test_node.sync_with_ping()
+        with mininode_lock:
+            assert(b"reserved for soft-fork upgrades" in self.test_node.last_reject.reason)
+
+        # Building a block with the transaction must be valid, however.
+        block = self.build_next_block()
+        self.update_witness_block_with_transactions(block, [tx2, tx3])
+        self.test_node.test_witness_block(block, accepted=True)
+        sync_blocks(self.nodes)
+
+        # Add utxo to our list
+        self.utxo.append(UTXO(tx3.sha256, 0, tx3.vout[0].nValue))
+
+
+    def test_premature_coinbase_witness_spend(self):
+        print("\tTesting premature coinbase witness spend")
+        block = self.build_next_block()
+        # Change the output of the block to be a witness output.
+        witness_program = CScript([OP_TRUE])
+        witness_hash = sha256(witness_program)
+        scriptPubKey = CScript([OP_0, witness_hash])
+        block.vtx[0].vout[0].scriptPubKey = scriptPubKey
+        # This next line will rehash the coinbase and update the merkle
+        # root, and solve.
+        self.update_witness_block_with_transactions(block, [])
+        self.test_node.test_witness_block(block, accepted=True)
+
+        spend_tx = CTransaction()
+        spend_tx.vin = [CTxIn(COutPoint(block.vtx[0].sha256, 0), b"")]
+        spend_tx.vout = [CTxOut(block.vtx[0].vout[0].nValue, witness_program)]
+        spend_tx.wit.vtxinwit.append(CTxinWitness())
+        spend_tx.wit.vtxinwit[0].scriptWitness.stack = [ witness_program ]
+        spend_tx.rehash()
+
+        # Now test a premature spend.
+        self.nodes[0].generate(98)
+        sync_blocks(self.nodes)
+        block2 = self.build_next_block()
+        self.update_witness_block_with_transactions(block2, [spend_tx])
+        self.test_node.test_witness_block(block2, accepted=False)
+
+        # Advancing one more block should allow the spend.
+        self.nodes[0].generate(1)
+        block2 = self.build_next_block()
+        self.update_witness_block_with_transactions(block2, [spend_tx])
+        self.test_node.test_witness_block(block2, accepted=True)
+        sync_blocks(self.nodes)
+
+
+    def test_signature_version_1(self):
+        print("\tTesting segwit signature hash version 1")
+        key = CECKey()
+        key.set_secretbytes(b"9")
+        pubkey = CPubKey(key.get_pubkey())
+
+        witness_program = CScript([pubkey, CScriptOp(OP_CHECKSIG)])
+        witness_hash = sha256(witness_program)
+        scriptPubKey = CScript([OP_0, witness_hash])
+
+        # First create a witness output for use in the tests.
+        assert(len(self.utxo))
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b""))
+        tx.vout.append(CTxOut(self.utxo[0].nValue-1000, scriptPubKey))
+        tx.rehash()
+
+        self.test_node.test_transaction_acceptance(tx, with_witness=True, accepted=True)
+        # Mine this transaction in preparation for following tests.
+        block = self.build_next_block()
+        self.update_witness_block_with_transactions(block, [tx])
+        self.test_node.test_witness_block(block, accepted=True)
+        sync_blocks(self.nodes)
+        self.utxo.pop(0)
+
+        # Add signature for a P2PK witness program.
+        def sign_P2PK_witness_input(script, txTo, inIdx, hashtype, value, key):
+            tx_hash = SegwitVersion1SignatureHash(script, txTo, inIdx, hashtype, value)
+            signature = key.sign(tx_hash) + chr(hashtype).encode('latin-1')
+            txTo.wit.vtxinwit[inIdx].scriptWitness.stack = [signature, script]
+            txTo.rehash()
+
+        # Test each hashtype
+        prev_utxo = UTXO(tx.sha256, 0, tx.vout[0].nValue)
+        for sigflag in [ 0, SIGHASH_ANYONECANPAY ]:
+            for hashtype in [SIGHASH_ALL, SIGHASH_NONE, SIGHASH_SINGLE]:
+                hashtype |= sigflag
+                block = self.build_next_block()
+                tx = CTransaction()
+                tx.vin.append(CTxIn(COutPoint(prev_utxo.sha256, prev_utxo.n), b""))
+                tx.vout.append(CTxOut(prev_utxo.nValue - 1000, scriptPubKey))
+                tx.wit.vtxinwit.append(CTxinWitness())
+                # Too-large input value
+                sign_P2PK_witness_input(witness_program, tx, 0, hashtype, prev_utxo.nValue+1, key)
+                self.update_witness_block_with_transactions(block, [tx])
+                self.test_node.test_witness_block(block, accepted=False)
+
+                # Too-small input value
+                sign_P2PK_witness_input(witness_program, tx, 0, hashtype, prev_utxo.nValue-1, key)
+                block.vtx.pop() # remove last tx
+                self.update_witness_block_with_transactions(block, [tx])
+                self.test_node.test_witness_block(block, accepted=False)
+
+                # Now try correct value
+                sign_P2PK_witness_input(witness_program, tx, 0, hashtype, prev_utxo.nValue, key)
+                block.vtx.pop()
+                self.update_witness_block_with_transactions(block, [tx])
+                self.test_node.test_witness_block(block, accepted=True)
+
+                prev_utxo = UTXO(tx.sha256, 0, tx.vout[0].nValue)
+
+        # Test combinations of signature hashes.
+        # Split the utxo into a lot of outputs.
+        # Randomly choose up to 10 to spend, sign with different hashtypes, and
+        # output to a random number of outputs.  Repeat NUM_TESTS times.
+        # Ensure that we've tested a situation where we use SIGHASH_SINGLE with
+        # an input index > number of outputs.
+        NUM_TESTS = 500
+        temp_utxos = []
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(prev_utxo.sha256, prev_utxo.n), b""))
+        split_value = prev_utxo.nValue // NUM_TESTS
+        for i in range(NUM_TESTS):
+            tx.vout.append(CTxOut(split_value, scriptPubKey))
+        tx.wit.vtxinwit.append(CTxinWitness())
+        sign_P2PK_witness_input(witness_program, tx, 0, SIGHASH_ALL, prev_utxo.nValue, key)
+        for i in range(NUM_TESTS):
+            temp_utxos.append(UTXO(tx.sha256, i, split_value))
+
+        block = self.build_next_block()
+        self.update_witness_block_with_transactions(block, [tx])
+        self.test_node.test_witness_block(block, accepted=True)
+
+        block = self.build_next_block()
+        used_sighash_single_out_of_bounds = False
+        for i in range(NUM_TESTS):
+            # Choose random number of inputs to use.
+            num_inputs = random.randint(1, 10)
+            # Create a slight bias for producing more utxos
+            num_outputs = random.randint(1, 11)
+            random.shuffle(temp_utxos)
+            assert(len(temp_utxos) > num_inputs)
+            tx = CTransaction()
+            total_value = 0
+            for i in range(num_inputs):
+                tx.vin.append(CTxIn(COutPoint(temp_utxos[i].sha256, temp_utxos[i].n), b""))
+                tx.wit.vtxinwit.append(CTxinWitness())
+                total_value += temp_utxos[i].nValue
+            split_value = total_value // num_outputs
+            for i in range(num_outputs):
+                tx.vout.append(CTxOut(split_value, scriptPubKey))
+            for i in range(num_inputs):
+                # Now try to sign each input, using a random hashtype.
+                anyonecanpay = 0
+                if random.randint(0, 1):
+                    anyonecanpay = SIGHASH_ANYONECANPAY
+                hashtype = random.randint(1, 3) | anyonecanpay
+                sign_P2PK_witness_input(witness_program, tx, i, hashtype, temp_utxos[i].nValue, key)
+                if (hashtype == SIGHASH_SINGLE and i >= num_outputs):
+                    used_sighash_single_out_of_bounds = True
+            tx.rehash()
+            for i in range(num_outputs):
+                temp_utxos.append(UTXO(tx.sha256, i, split_value))
+            temp_utxos = temp_utxos[num_inputs:]
+
+            block.vtx.append(tx)
+
+            # Test the block periodically, if we're close to maxblocksize
+            if (get_virtual_size(block) > MAX_BLOCK_SIZE - 1000):
+                self.update_witness_block_with_transactions(block, [])
+                self.test_node.test_witness_block(block, accepted=True)
+                block = self.build_next_block()
+
+        if (not used_sighash_single_out_of_bounds):
+            print("WARNING: this test run didn't attempt SIGHASH_SINGLE with out-of-bounds index value")
+        # Test the transactions we've added to the block
+        if (len(block.vtx) > 1):
+            self.update_witness_block_with_transactions(block, [])
+            self.test_node.test_witness_block(block, accepted=True)
+
+        # Now test witness version 0 P2PKH transactions
+        pubkeyhash = hash160(pubkey)
+        scriptPKH = CScript([OP_0, pubkeyhash])
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(temp_utxos[0].sha256, temp_utxos[0].n), b""))
+        tx.vout.append(CTxOut(temp_utxos[0].nValue, scriptPKH))
+        tx.wit.vtxinwit.append(CTxinWitness())
+        sign_P2PK_witness_input(witness_program, tx, 0, SIGHASH_ALL, temp_utxos[0].nValue, key)
+        tx2 = CTransaction()
+        tx2.vin.append(CTxIn(COutPoint(tx.sha256, 0), b""))
+        tx2.vout.append(CTxOut(tx.vout[0].nValue, CScript([OP_TRUE])))
+
+        script = CScript([CScriptOp(OP_DUP), CScriptOp(OP_HASH160), pubkeyhash, CScriptOp(OP_EQUALVERIFY), CScriptOp(OP_CHECKSIG)])
+        sig_hash = SegwitVersion1SignatureHash(script, tx2, 0, SIGHASH_ALL, tx.vout[0].nValue)
+        signature = key.sign(sig_hash) + b'\x01' # 0x1 is SIGHASH_ALL
+
+        # Check that we can't have a scriptSig
+        tx2.vin[0].scriptSig = CScript([signature, pubkey])
+        block = self.build_next_block()
+        self.update_witness_block_with_transactions(block, [tx, tx2])
+        self.test_node.test_witness_block(block, accepted=False)
+
+        # Move the signature to the witness.
+        block.vtx.pop()
+        tx2.wit.vtxinwit.append(CTxinWitness())
+        tx2.wit.vtxinwit[0].scriptWitness.stack = [signature, pubkey]
+        tx2.vin[0].scriptSig = b""
+        tx2.rehash()
+
+        self.update_witness_block_with_transactions(block, [tx2])
+        self.test_node.test_witness_block(block, accepted=True)
+
+        temp_utxos.pop(0)
+
+        # Update self.utxos for later tests. Just spend everything in
+        # temp_utxos to a corresponding entry in self.utxos
+        tx = CTransaction()
+        index = 0
+        for i in temp_utxos:
+            # Just spend to our usual anyone-can-spend output
+            # Use SIGHASH_SINGLE|SIGHASH_ANYONECANPAY so we can build up
+            # the signatures as we go.
+            tx.vin.append(CTxIn(COutPoint(i.sha256, i.n), b""))
+            tx.vout.append(CTxOut(i.nValue, CScript([OP_TRUE])))
+            tx.wit.vtxinwit.append(CTxinWitness())
+            sign_P2PK_witness_input(witness_program, tx, index, SIGHASH_SINGLE|SIGHASH_ANYONECANPAY, i.nValue, key)
+            index += 1
+        block = self.build_next_block()
+        self.update_witness_block_with_transactions(block, [tx])
+        self.test_node.test_witness_block(block, accepted=True)
+
+        for i in range(len(tx.vout)):
+            self.utxo.append(UTXO(tx.sha256, i, tx.vout[i].nValue))
+
+
+    # Test P2SH wrapped witness programs.
+    def test_p2sh_witness(self, segwit_activated):
+        print("\tTesting P2SH witness transactions")
+
+        assert(len(self.utxo))
+
+        # Prepare the p2sh-wrapped witness output
+        witness_program = CScript([OP_DROP, OP_TRUE])
+        witness_hash = sha256(witness_program)
+        p2wsh_pubkey = CScript([OP_0, witness_hash])
+        p2sh_witness_hash = hash160(p2wsh_pubkey)
+        scriptPubKey = CScript([OP_HASH160, p2sh_witness_hash, OP_EQUAL])
+        scriptSig = CScript([p2wsh_pubkey]) # a push of the redeem script
+
+        # Fund the P2SH output
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b""))
+        tx.vout.append(CTxOut(self.utxo[0].nValue-1000, scriptPubKey))
+        tx.rehash()
+
+        # Verify mempool acceptance and block validity
+        self.test_node.test_transaction_acceptance(tx, with_witness=False, accepted=True)
+        block = self.build_next_block()
+        self.update_witness_block_with_transactions(block, [tx])
+        self.test_node.test_witness_block(block, accepted=True, with_witness=segwit_activated)
+        sync_blocks(self.nodes)
+
+        # Now test attempts to spend the output.
+        spend_tx = CTransaction()
+        spend_tx.vin.append(CTxIn(COutPoint(tx.sha256, 0), scriptSig))
+        spend_tx.vout.append(CTxOut(tx.vout[0].nValue-1000, CScript([OP_TRUE])))
+        spend_tx.rehash()
+
+        # This transaction should not be accepted into the mempool pre- or
+        # post-segwit.  Mempool acceptance will use SCRIPT_VERIFY_WITNESS which
+        # will require a witness to spend a witness program regardless of
+        # segwit activation.  Note that older bitcoind's that are not
+        # segwit-aware would also reject this for failing CLEANSTACK.
+        self.test_node.test_transaction_acceptance(spend_tx, with_witness=False, accepted=False)
+
+        # Try to put the witness script in the scriptSig, should also fail.
+        spend_tx.vin[0].scriptSig = CScript([p2wsh_pubkey, b'a'])
+        spend_tx.rehash()
+        self.test_node.test_transaction_acceptance(spend_tx, with_witness=False, accepted=False)
+
+        # Now put the witness script in the witness, should succeed after
+        # segwit activates.
+        spend_tx.vin[0].scriptSig = scriptSig
+        spend_tx.rehash()
+        spend_tx.wit.vtxinwit.append(CTxinWitness())
+        spend_tx.wit.vtxinwit[0].scriptWitness.stack = [ b'a', witness_program ]
+
+        # Verify mempool acceptance
+        self.test_node.test_transaction_acceptance(spend_tx, with_witness=True, accepted=segwit_activated)
+        block = self.build_next_block()
+        self.update_witness_block_with_transactions(block, [spend_tx])
+
+        # If we're before activation, then sending this without witnesses
+        # should be valid.  If we're after activation, then sending this with
+        # witnesses should be valid.
+        if segwit_activated:
+            self.test_node.test_witness_block(block, accepted=True)
+        else:
+            self.test_node.test_witness_block(block, accepted=True, with_witness=False)
+
+        # Update self.utxo
+        self.utxo.pop(0)
+        self.utxo.append(UTXO(spend_tx.sha256, 0, spend_tx.vout[0].nValue))
+
+    # Test the behavior of starting up a segwit-aware node after the softfork
+    # has activated.  As segwit requires different block data than pre-segwit
+    # nodes would have stored, this requires special handling.
+    # To enable this test, pass --oldbinary=<path-to-pre-segwit-bitcoind> to
+    # the test.
+    def test_upgrade_after_activation(self, node, node_id):
+        print("\tTesting software upgrade after softfork activation")
+
+        assert(node_id != 0) # node0 is assumed to be a segwit-active bitcoind
+
+        # Make sure the nodes are all up
+        sync_blocks(self.nodes)
+
+        # Restart with the new binary
+        stop_node(node, node_id)
+        self.nodes[node_id] = start_node(node_id, self.options.tmpdir, ["-debug"])
+        connect_nodes(self.nodes[0], node_id)
+
+        sync_blocks(self.nodes)
+
+        # Make sure that this peer thinks segwit has activated.
+        assert(get_bip9_status(node, 'segwit')['status'] == "active")
+
+        # Make sure this peers blocks match those of node0.
+        height = node.getblockcount()
+        while height >= 0:
+            block_hash = node.getblockhash(height)
+            assert_equal(block_hash, self.nodes[0].getblockhash(height))
+            assert_equal(self.nodes[0].getblock(block_hash), node.getblock(block_hash))
+            height -= 1
+
+
+    def test_witness_sigops(self):
+        '''Ensure sigop counting is correct inside witnesses.'''
+        print("\tTesting sigops limit")
+
+        assert(len(self.utxo))
+
+        # Keep this under MAX_OPS_PER_SCRIPT (201)
+        witness_program = CScript([OP_TRUE, OP_IF, OP_TRUE, OP_ELSE] + [OP_CHECKMULTISIG]*5 + [OP_CHECKSIG]*193 + [OP_ENDIF])
+        witness_hash = sha256(witness_program)
+        scriptPubKey = CScript([OP_0, witness_hash])
+
+        sigops_per_script = 20*5 + 193*1
+        # We'll produce 2 extra outputs, one with a program that would take us
+        # over max sig ops, and one with a program that would exactly reach max
+        # sig ops
+        outputs = (MAX_SIGOP_COST // sigops_per_script) + 2
+        extra_sigops_available = MAX_SIGOP_COST % sigops_per_script
+
+        # We chose the number of checkmultisigs/checksigs to make this work:
+        assert(extra_sigops_available < 100) # steer clear of MAX_OPS_PER_SCRIPT
+
+        # This script, when spent with the first
+        # N(=MAX_SIGOP_COST//sigops_per_script) outputs of our transaction,
+        # would push us just over the block sigop limit.
+        witness_program_toomany = CScript([OP_TRUE, OP_IF, OP_TRUE, OP_ELSE] + [OP_CHECKSIG]*(extra_sigops_available + 1) + [OP_ENDIF])
+        witness_hash_toomany = sha256(witness_program_toomany)
+        scriptPubKey_toomany = CScript([OP_0, witness_hash_toomany])
+
+        # If we spend this script instead, we would exactly reach our sigop
+        # limit (for witness sigops).
+        witness_program_justright = CScript([OP_TRUE, OP_IF, OP_TRUE, OP_ELSE] + [OP_CHECKSIG]*(extra_sigops_available) + [OP_ENDIF])
+        witness_hash_justright = sha256(witness_program_justright)
+        scriptPubKey_justright = CScript([OP_0, witness_hash_justright])
+
+        # First split our available utxo into a bunch of outputs
+        split_value = self.utxo[0].nValue // outputs
+        tx = CTransaction()
+        tx.vin.append(CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b""))
+        for i in range(outputs):
+            tx.vout.append(CTxOut(split_value, scriptPubKey))
+        tx.vout[-2].scriptPubKey = scriptPubKey_toomany
+        tx.vout[-1].scriptPubKey = scriptPubKey_justright
+        tx.rehash()
+
+        block_1 = self.build_next_block()
+        self.update_witness_block_with_transactions(block_1, [tx])
+        self.test_node.test_witness_block(block_1, accepted=True)
+
+        tx2 = CTransaction()
+        # If we try to spend the first n-1 outputs from tx, that should be
+        # too many sigops.
+        total_value = 0
+        for i in range(outputs-1):
+            tx2.vin.append(CTxIn(COutPoint(tx.sha256, i), b""))
+            tx2.wit.vtxinwit.append(CTxinWitness())
+            tx2.wit.vtxinwit[-1].scriptWitness.stack = [ witness_program ]
+            total_value += tx.vout[i].nValue
+        tx2.wit.vtxinwit[-1].scriptWitness.stack = [ witness_program_toomany ] 
+        tx2.vout.append(CTxOut(total_value, CScript([OP_TRUE])))
+        tx2.rehash()
+
+        block_2 = self.build_next_block()
+        self.update_witness_block_with_transactions(block_2, [tx2])
+        self.test_node.test_witness_block(block_2, accepted=False)
+
+        # Try dropping the last input in tx2, and add an output that has
+        # too many sigops (contributing to legacy sigop count).
+        checksig_count = (extra_sigops_available // 4) + 1
+        scriptPubKey_checksigs = CScript([OP_CHECKSIG]*checksig_count)
+        tx2.vout.append(CTxOut(0, scriptPubKey_checksigs));
+        tx2.vin.pop()
+        tx2.wit.vtxinwit.pop()
+        tx2.vout[0].nValue -= tx.vout[-2].nValue
+        tx2.rehash()
+        block_3 = self.build_next_block()
+        self.update_witness_block_with_transactions(block_3, [tx2])
+        self.test_node.test_witness_block(block_3, accepted=False)
+
+        # If we drop the last checksig in this output, the tx should succeed.
+        block_4 = self.build_next_block()
+        tx2.vout[-1].scriptPubKey = CScript([OP_CHECKSIG]*(checksig_count-1))
+        tx2.rehash()
+        self.update_witness_block_with_transactions(block_4, [tx2])
+        self.test_node.test_witness_block(block_4, accepted=True)
+
+        # Reset the tip back down for the next test
+        sync_blocks(self.nodes)
+        for x in self.nodes:
+            x.invalidateblock(block_4.hash)
+
+        # Try replacing the last input of tx2 to be spending the last
+        # output of tx
+        block_5 = self.build_next_block()
+        tx2.vout.pop()
+        tx2.vin.append(CTxIn(COutPoint(tx.sha256, outputs-1), b""))
+        tx2.wit.vtxinwit.append(CTxinWitness())
+        tx2.wit.vtxinwit[-1].scriptWitness.stack = [ witness_program_justright ]
+        tx2.rehash()
+        self.update_witness_block_with_transactions(block_5, [tx2])
+        self.test_node.test_witness_block(block_5, accepted=True)
+
+        # TODO: test p2sh sigop counting
+
+    def test_getblocktemplate_before_lockin(self):
+        print("\tTesting getblocktemplate setting of segwit versionbit (before lockin)")
+        block_version = (self.nodes[0].getblocktemplate())['version']
+        assert_equal(block_version & (1 << VB_WITNESS_BIT), 0)
+
+        # Workaround:
+        # Can either change the tip, or change the mempool and wait 5 seconds
+        # to trigger a recomputation of getblocktemplate.
+        self.nodes[0].sendtoaddress(self.nodes[0].getnewaddress(), 1)
+        # Using mocktime lets us avoid sleep()
+        self.nodes[0].setmocktime(int(time.time())+10)
+
+        block_version = self.nodes[0].getblocktemplate({"rules" : ["segwit"]})['version']
+        assert(block_version & (1 << VB_WITNESS_BIT) != 0)
+        self.nodes[0].setmocktime(0) # undo mocktime
+
+    def run_test(self):
+        # Setup the p2p connections and start up the network thread.
+        self.test_node = TestNode() # sets NODE_WITNESS|NODE_NETWORK
+        self.old_node = TestNode()  # only NODE_NETWORK
+        self.std_node = TestNode() # for testing node1 (fRequireStandard=true)
+
+        self.p2p_connections = [self.test_node, self.old_node]
+
+        self.connections = []
+        self.connections.append(NodeConn('127.0.0.1', p2p_port(0), self.nodes[0], self.test_node, services=NODE_NETWORK|NODE_WITNESS))
+        self.connections.append(NodeConn('127.0.0.1', p2p_port(0), self.nodes[0], self.old_node, services=NODE_NETWORK))
+        self.connections.append(NodeConn('127.0.0.1', p2p_port(1), self.nodes[1], self.std_node, services=NODE_NETWORK|NODE_WITNESS))
+        self.test_node.add_connection(self.connections[0])
+        self.old_node.add_connection(self.connections[1])
+        self.std_node.add_connection(self.connections[2])
+
+        NetworkThread().start() # Start up network handling in another thread
+
+        # Keep a place to store utxo's that can be used in later tests
+        self.utxo = []
+
+        # Test logic begins here
+        self.test_node.wait_for_verack()
+
+        print("\nStarting tests before segwit lock in:")
+
+        self.test_witness_services() # Verifies NODE_WITNESS
+        self.test_non_witness_transaction() # non-witness tx's are accepted
+        self.test_unnecessary_witness_before_segwit_activation()
+        self.test_block_relay(segwit_activated=False)
+
+        # Advance to segwit being 'started'
+        self.advance_to_segwit_started()
+        self.test_getblocktemplate_before_lockin()
+
+        sync_blocks(self.nodes)
+
+        # At lockin, nothing should change.
+        print("\nTesting behavior post lockin, pre-activation")
+        self.advance_to_segwit_lockin()
+
+        # Retest unnecessary witnesses
+        self.test_unnecessary_witness_before_segwit_activation()
+        self.test_witness_tx_relay_before_segwit_activation()
+        self.test_block_relay(segwit_activated=False)
+        self.test_p2sh_witness(segwit_activated=False)
+
+        sync_blocks(self.nodes)
+
+        # Now activate segwit
+        print("\nTesting behavior after segwit activation")
+        self.advance_to_segwit_active()
+
+        sync_blocks(self.nodes)
+
+        # Test P2SH witness handling again
+        self.test_p2sh_witness(segwit_activated=True)
+        self.test_witness_commitments()
+        self.test_block_malleability()
+        self.test_witness_block_size()
+        self.test_submit_block()
+        self.test_extra_witness_data()
+        self.test_max_witness_push_length()
+        self.test_max_witness_program_length()
+        self.test_witness_input_length()
+        self.test_block_relay(segwit_activated=True)
+        self.test_tx_relay_after_segwit_activation()
+        self.test_segwit_versions()
+        self.test_premature_coinbase_witness_spend()
+        self.test_signature_version_1()
+        sync_blocks(self.nodes)
+        if self.test_upgrade:
+            self.test_upgrade_after_activation(self.nodes[2], 2)
+        else:
+            print("\tSkipping upgrade-after-activation test (use --oldbinary to enable)")
+        self.test_witness_sigops()
+
+
+if __name__ == '__main__':
+    SegWitTest().main()
diff --git a/qa/rpc-tests/segwit.py b/qa/rpc-tests/segwit.py
new file mode 100755
index 0000000000..d4c9a8afed
--- /dev/null
+++ b/qa/rpc-tests/segwit.py
@@ -0,0 +1,209 @@
+#!/usr/bin/env python3
+# 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.
+
+#
+# Test the SegWit changeover logic
+#
+
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.util import *
+from test_framework.mininode import sha256, ripemd160
+import os
+import shutil
+
+NODE_0 = 0
+NODE_1 = 1
+NODE_2 = 2
+WIT_V0 = 0
+WIT_V1 = 1
+
+def witness_script(version, pubkey):
+    if (version == 0):
+        pubkeyhash = bytes_to_hex_str(ripemd160(sha256(hex_str_to_bytes(pubkey))))
+        pkscript = "0014" + pubkeyhash
+    elif (version == 1):
+        # 1-of-1 multisig
+        scripthash = bytes_to_hex_str(sha256(hex_str_to_bytes("5121" + pubkey + "51ae")))
+        pkscript = "0020" + scripthash
+    else:
+        assert("Wrong version" == "0 or 1")
+    return pkscript
+
+def addlength(script):
+    scriptlen = format(len(script)//2, 'x')
+    assert(len(scriptlen) == 2)
+    return scriptlen + script
+
+def create_witnessprogram(version, node, utxo, pubkey, encode_p2sh, amount):
+    pkscript = witness_script(version, pubkey);
+    if (encode_p2sh):
+        p2sh_hash = bytes_to_hex_str(ripemd160(sha256(hex_str_to_bytes(pkscript))))
+        pkscript = "a914"+p2sh_hash+"87"
+    inputs = []
+    outputs = {}
+    inputs.append({ "txid" : utxo["txid"], "vout" : utxo["vout"]} )
+    DUMMY_P2SH = "2MySexEGVzZpRgNQ1JdjdP5bRETznm3roQ2" # P2SH of "OP_1 OP_DROP"
+    outputs[DUMMY_P2SH] = amount
+    tx_to_witness = node.createrawtransaction(inputs,outputs)
+    #replace dummy output with our own
+    tx_to_witness = tx_to_witness[0:110] + addlength(pkscript) + tx_to_witness[-8:]
+    return tx_to_witness
+
+def send_to_witness(version, node, utxo, pubkey, encode_p2sh, amount, sign=True, insert_redeem_script=""):
+    tx_to_witness = create_witnessprogram(version, node, utxo, pubkey, encode_p2sh, amount)
+    if (sign):
+        signed = node.signrawtransaction(tx_to_witness)
+        assert("errors" not in signed or len(["errors"]) == 0)
+        return node.sendrawtransaction(signed["hex"])
+    else:
+        if (insert_redeem_script):
+            tx_to_witness = tx_to_witness[0:82] + addlength(insert_redeem_script) + tx_to_witness[84:]
+
+    return node.sendrawtransaction(tx_to_witness)
+
+def getutxo(txid):
+    utxo = {}
+    utxo["vout"] = 0
+    utxo["txid"] = txid
+    return utxo
+
+class SegWitTest(BitcoinTestFramework):
+
+    def setup_chain(self):
+        print("Initializing test directory "+self.options.tmpdir)
+        initialize_chain_clean(self.options.tmpdir, 3)
+
+    def setup_network(self):
+        self.nodes = []
+        self.nodes.append(start_node(0, self.options.tmpdir, ["-logtimemicros", "-debug", "-walletprematurewitness"]))
+        self.nodes.append(start_node(1, self.options.tmpdir, ["-logtimemicros", "-debug", "-blockversion=4", "-promiscuousmempoolflags=517", "-prematurewitness", "-walletprematurewitness"]))
+        self.nodes.append(start_node(2, self.options.tmpdir, ["-logtimemicros", "-debug", "-blockversion=536870915", "-promiscuousmempoolflags=517", "-prematurewitness", "-walletprematurewitness"]))
+        connect_nodes(self.nodes[1], 0)
+        connect_nodes(self.nodes[2], 1)
+        connect_nodes(self.nodes[0], 2)
+        self.is_network_split = False
+        self.sync_all()
+
+    def success_mine(self, node, txid, sign, redeem_script=""):
+        send_to_witness(1, node, getutxo(txid), self.pubkey[0], False, Decimal("49.998"), sign, redeem_script)
+        block = node.generate(1)
+        assert_equal(len(node.getblock(block[0])["tx"]), 2)
+        sync_blocks(self.nodes)
+
+    def skip_mine(self, node, txid, sign, redeem_script=""):
+        send_to_witness(1, node, getutxo(txid), self.pubkey[0], False, Decimal("49.998"), sign, redeem_script)
+        block = node.generate(1)
+        assert_equal(len(node.getblock(block[0])["tx"]), 1)
+        sync_blocks(self.nodes)
+
+    def fail_accept(self, node, txid, sign, redeem_script=""):
+        try:
+            send_to_witness(1, node, getutxo(txid), self.pubkey[0], False, Decimal("49.998"), sign, redeem_script)
+        except JSONRPCException as exp:
+            assert(exp.error["code"] == -26)
+        else:
+            raise AssertionError("Tx should not have been accepted")
+
+    def fail_mine(self, node, txid, sign, redeem_script=""):
+        send_to_witness(1, node, getutxo(txid), self.pubkey[0], False, Decimal("49.998"), sign, redeem_script)
+        try:
+            node.generate(1)
+        except JSONRPCException as exp:
+            assert(exp.error["code"] == -1)
+        else:
+            raise AssertionError("Created valid block when TestBlockValidity should have failed")
+        sync_blocks(self.nodes)
+
+    def run_test(self):
+        self.nodes[0].generate(160) #block 160
+
+        self.pubkey = []
+        p2sh_ids = [] # p2sh_ids[NODE][VER] is an array of txids that spend to a witness version VER pkscript to an address for NODE embedded in p2sh
+        wit_ids = [] # wit_ids[NODE][VER] is an array of txids that spend to a witness version VER pkscript to an address for NODE via bare witness
+        for i in range(3):
+            newaddress = self.nodes[i].getnewaddress()
+            self.pubkey.append(self.nodes[i].validateaddress(newaddress)["pubkey"])
+            multiaddress = self.nodes[i].addmultisigaddress(1, [self.pubkey[-1]])
+            self.nodes[i].addwitnessaddress(newaddress)
+            self.nodes[i].addwitnessaddress(multiaddress)
+            p2sh_ids.append([])
+            wit_ids.append([])
+            for v in range(2):
+                p2sh_ids[i].append([])
+                wit_ids[i].append([])
+
+        for i in range(5):
+            for n in range(3):
+                for v in range(2):
+                    wit_ids[n][v].append(send_to_witness(v, self.nodes[0], self.nodes[0].listunspent()[0], self.pubkey[n], False, Decimal("49.999")))
+                    p2sh_ids[n][v].append(send_to_witness(v, self.nodes[0], self.nodes[0].listunspent()[0], self.pubkey[n], True, Decimal("49.999")))
+
+        self.nodes[0].generate(1) #block 161
+        sync_blocks(self.nodes)
+
+        # Make sure all nodes recognize the transactions as theirs
+        assert_equal(self.nodes[0].getbalance(), 60*50 - 60*50 + 20*Decimal("49.999") + 50)
+        assert_equal(self.nodes[1].getbalance(), 20*Decimal("49.999"))
+        assert_equal(self.nodes[2].getbalance(), 20*Decimal("49.999"))
+
+        self.nodes[0].generate(262) #block 423
+        sync_blocks(self.nodes)
+
+        print("Verify default node can't accept any witness format txs before fork")
+        # unsigned, no scriptsig
+        self.fail_accept(self.nodes[0], wit_ids[NODE_0][WIT_V0][0], False)
+        self.fail_accept(self.nodes[0], wit_ids[NODE_0][WIT_V1][0], False)
+        self.fail_accept(self.nodes[0], p2sh_ids[NODE_0][WIT_V0][0], False)
+        self.fail_accept(self.nodes[0], p2sh_ids[NODE_0][WIT_V1][0], False)
+        # unsigned with redeem script
+        self.fail_accept(self.nodes[0], p2sh_ids[NODE_0][WIT_V0][0], False, addlength(witness_script(0, self.pubkey[0])))
+        self.fail_accept(self.nodes[0], p2sh_ids[NODE_0][WIT_V1][0], False, addlength(witness_script(1, self.pubkey[0])))
+        # signed
+        self.fail_accept(self.nodes[0], wit_ids[NODE_0][WIT_V0][0], True)
+        self.fail_accept(self.nodes[0], wit_ids[NODE_0][WIT_V1][0], True)
+        self.fail_accept(self.nodes[0], p2sh_ids[NODE_0][WIT_V0][0], True)
+        self.fail_accept(self.nodes[0], p2sh_ids[NODE_0][WIT_V1][0], True)
+
+        print("Verify witness txs are skipped for mining before the fork")
+        self.skip_mine(self.nodes[2], wit_ids[NODE_2][WIT_V0][0], True) #block 424
+        self.skip_mine(self.nodes[2], wit_ids[NODE_2][WIT_V1][0], True) #block 425
+        self.skip_mine(self.nodes[2], p2sh_ids[NODE_2][WIT_V0][0], True) #block 426
+        self.skip_mine(self.nodes[2], p2sh_ids[NODE_2][WIT_V1][0], True) #block 427
+
+        # TODO: An old node would see these txs without witnesses and be able to mine them
+
+        print("Verify unsigned bare witness txs in versionbits-setting blocks are valid before the fork")
+        self.success_mine(self.nodes[2], wit_ids[NODE_2][WIT_V0][1], False) #block 428
+        self.success_mine(self.nodes[2], wit_ids[NODE_2][WIT_V1][1], False) #block 429
+
+        print("Verify unsigned p2sh witness txs without a redeem script are invalid")
+        self.fail_accept(self.nodes[2], p2sh_ids[NODE_2][WIT_V0][1], False)
+        self.fail_accept(self.nodes[2], p2sh_ids[NODE_2][WIT_V1][1], False)
+
+        print("Verify unsigned p2sh witness txs with a redeem script in versionbits-settings blocks are valid before the fork")
+        self.success_mine(self.nodes[2], p2sh_ids[NODE_2][WIT_V0][1], False, addlength(witness_script(0, self.pubkey[2]))) #block 430
+        self.success_mine(self.nodes[2], p2sh_ids[NODE_2][WIT_V1][1], False, addlength(witness_script(1, self.pubkey[2]))) #block 431
+
+        print("Verify previous witness txs skipped for mining can now be mined")
+        assert_equal(len(self.nodes[2].getrawmempool()), 4)
+        block = self.nodes[2].generate(1) #block 432 (first block with new rules; 432 = 144 * 3)
+        sync_blocks(self.nodes)
+        assert_equal(len(self.nodes[2].getrawmempool()), 0)
+        assert_equal(len(self.nodes[2].getblock(block[0])["tx"]), 5)
+
+        print("Verify witness txs without witness data are invalid after the fork")
+        self.fail_mine(self.nodes[2], wit_ids[NODE_2][WIT_V0][2], False)
+        self.fail_mine(self.nodes[2], wit_ids[NODE_2][WIT_V1][2], False)
+        self.fail_mine(self.nodes[2], p2sh_ids[NODE_2][WIT_V0][2], False, addlength(witness_script(0, self.pubkey[2])))
+        self.fail_mine(self.nodes[2], p2sh_ids[NODE_2][WIT_V1][2], False, addlength(witness_script(1, self.pubkey[2])))
+
+        print("Verify default node can now use witness txs")
+        self.success_mine(self.nodes[0], wit_ids[NODE_0][WIT_V0][0], True) #block 432
+        self.success_mine(self.nodes[0], wit_ids[NODE_0][WIT_V1][0], True) #block 433
+        self.success_mine(self.nodes[0], p2sh_ids[NODE_0][WIT_V0][0], True) #block 434
+        self.success_mine(self.nodes[0], p2sh_ids[NODE_0][WIT_V1][0], True) #block 435
+
+if __name__ == '__main__':
+    SegWitTest().main()
diff --git a/qa/rpc-tests/test_framework/blocktools.py b/qa/rpc-tests/test_framework/blocktools.py
index 26cc396315..df4fe13e5c 100644
--- a/qa/rpc-tests/test_framework/blocktools.py
+++ b/qa/rpc-tests/test_framework/blocktools.py
@@ -5,7 +5,7 @@
 # file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 from .mininode import *
-from .script import CScript, OP_TRUE, OP_CHECKSIG
+from .script import CScript, OP_TRUE, OP_CHECKSIG, OP_RETURN
 
 # Create a block (with regtest difficulty)
 def create_block(hashprev, coinbase, nTime=None):
@@ -22,6 +22,29 @@ def create_block(hashprev, coinbase, nTime=None):
     block.calc_sha256()
     return block
 
+# From BIP141
+WITNESS_COMMITMENT_HEADER = b"\xaa\x21\xa9\xed"
+
+# According to BIP141, blocks with witness rules active must commit to the
+# hash of all in-block transactions including witness.
+def add_witness_commitment(block, nonce=0):
+    # First calculate the merkle root of the block's
+    # transactions, with witnesses.
+    witness_nonce = nonce
+    witness_root = block.calc_witness_merkle_root()
+    witness_commitment = uint256_from_str(hash256(ser_uint256(witness_root)+ser_uint256(witness_nonce)))
+    # witness_nonce should go to coinbase witness.
+    block.vtx[0].wit.vtxinwit = [CTxinWitness()]
+    block.vtx[0].wit.vtxinwit[0].scriptWitness.stack = [ser_uint256(witness_nonce)]
+
+    # witness commitment is the last OP_RETURN output in coinbase
+    output_data = WITNESS_COMMITMENT_HEADER + ser_uint256(witness_commitment)
+    block.vtx[0].vout.append(CTxOut(0, CScript([OP_RETURN, output_data])))
+    block.vtx[0].rehash()
+    block.hashMerkleRoot = block.calc_merkle_root()
+    block.rehash()
+
+
 def serialize_script_num(value):
     r = bytearray(0)
     if value == 0:
diff --git a/qa/rpc-tests/test_framework/mininode.py b/qa/rpc-tests/test_framework/mininode.py
index 6612b99b84..4548e2e7c0 100755
--- a/qa/rpc-tests/test_framework/mininode.py
+++ b/qa/rpc-tests/test_framework/mininode.py
@@ -28,7 +28,7 @@ import asyncore
 import time
 import sys
 import random
-from binascii import hexlify, unhexlify
+from .util import hex_str_to_bytes, bytes_to_hex_str
 from io import BytesIO
 from codecs import encode
 import hashlib
@@ -46,6 +46,11 @@ MAX_BLOCK_SIZE = 1000000
 
 COIN = 100000000 # 1 btc in satoshis
 
+NODE_NETWORK = (1 << 0)
+NODE_GETUTXO = (1 << 1)
+NODE_BLOOM = (1 << 2)
+NODE_WITNESS = (1 << 3)
+
 # Keep our own socket map for asyncore, so that we can track disconnects
 # ourselves (to workaround an issue with closing an asyncore socket when 
 # using select)
@@ -63,6 +68,8 @@ mininode_lock = RLock()
 def sha256(s):
     return hashlib.new('sha256', s).digest()
 
+def ripemd160(s):
+    return hashlib.new('ripemd160', s).digest()
 
 def hash256(s):
     return sha256(sha256(s))
@@ -133,7 +140,10 @@ def deser_vector(f, c):
     return r
 
 
-def ser_vector(l):
+# ser_function_name: Allow for an alternate serialization function on the
+# entries in the vector (we use this for serializing the vector of transactions
+# for a witness block).
+def ser_vector(l, ser_function_name=None):
     r = b""
     if len(l) < 253:
         r = struct.pack("B", len(l))
@@ -144,7 +154,10 @@ def ser_vector(l):
     else:
         r = struct.pack("<BQ", 255, len(l))
     for i in l:
-        r += i.serialize()
+        if ser_function_name:
+            r += getattr(i, ser_function_name)()
+        else:
+            r += i.serialize()
     return r
 
 
@@ -239,12 +252,12 @@ def ser_int_vector(l):
 
 # Deserialize from a hex string representation (eg from RPC)
 def FromHex(obj, hex_string):
-    obj.deserialize(BytesIO(unhexlify(hex_string.encode('ascii'))))
+    obj.deserialize(BytesIO(hex_str_to_bytes(hex_string)))
     return obj
 
 # Convert a binary-serializable object to hex (eg for submission via RPC)
 def ToHex(obj):
-    return hexlify(obj.serialize()).decode('ascii')
+    return bytes_to_hex_str(obj.serialize())
 
 # Objects that map to bitcoind objects, which can be serialized/deserialized
 
@@ -273,12 +286,16 @@ class CAddress(object):
         return "CAddress(nServices=%i ip=%s port=%i)" % (self.nServices,
                                                          self.ip, self.port)
 
+MSG_WITNESS_FLAG = 1<<30
 
 class CInv(object):
     typemap = {
         0: "Error",
         1: "TX",
-        2: "Block"}
+        2: "Block",
+        1|MSG_WITNESS_FLAG: "WitnessTx",
+        2|MSG_WITNESS_FLAG : "WitnessBlock"
+    }
 
     def __init__(self, t=0, h=0):
         self.type = t
@@ -362,7 +379,7 @@ class CTxIn(object):
 
     def __repr__(self):
         return "CTxIn(prevout=%s scriptSig=%s nSequence=%i)" \
-            % (repr(self.prevout), hexlify(self.scriptSig),
+            % (repr(self.prevout), bytes_to_hex_str(self.scriptSig),
                self.nSequence)
 
 
@@ -384,7 +401,67 @@ class CTxOut(object):
     def __repr__(self):
         return "CTxOut(nValue=%i.%08i scriptPubKey=%s)" \
             % (self.nValue // COIN, self.nValue % COIN,
-               hexlify(self.scriptPubKey))
+               bytes_to_hex_str(self.scriptPubKey))
+
+
+class CScriptWitness(object):
+    def __init__(self):
+        # stack is a vector of strings
+        self.stack = []
+
+    def __repr__(self):
+        return "CScriptWitness(%s)" % \
+               (",".join([bytes_to_hex_str(x) for x in self.stack]))
+
+    def is_null(self):
+        if self.stack:
+            return False
+        return True
+
+
+class CTxinWitness(object):
+    def __init__(self):
+        self.scriptWitness = CScriptWitness()
+
+    def deserialize(self, f):
+        self.scriptWitness.stack = deser_string_vector(f)
+
+    def serialize(self):
+        return ser_string_vector(self.scriptWitness.stack)
+
+    def __repr__(self):
+        return repr(self.scriptWitness)
+
+    def is_null(self):
+        return self.scriptWitness.is_null()
+
+
+class CTxWitness(object):
+    def __init__(self):
+        self.vtxinwit = []
+
+    def deserialize(self, f):
+        for i in range(len(self.vtxinwit)):
+            self.vtxinwit[i].deserialize(f)
+
+    def serialize(self):
+        r = b""
+        # This is different than the usual vector serialization --
+        # we omit the length of the vector, which is required to be
+        # the same length as the transaction's vin vector.
+        for x in self.vtxinwit:
+            r += x.serialize()
+        return r
+
+    def __repr__(self):
+        return "CTxWitness(%s)" % \
+               (';'.join([repr(x) for x in self.vtxinwit]))
+
+    def is_null(self):
+        for x in self.vtxinwit:
+            if not x.is_null():
+                return False
+        return True
 
 
 class CTransaction(object):
@@ -393,6 +470,7 @@ class CTransaction(object):
             self.nVersion = 1
             self.vin = []
             self.vout = []
+            self.wit = CTxWitness()
             self.nLockTime = 0
             self.sha256 = None
             self.hash = None
@@ -401,32 +479,80 @@ class CTransaction(object):
             self.vin = copy.deepcopy(tx.vin)
             self.vout = copy.deepcopy(tx.vout)
             self.nLockTime = tx.nLockTime
-            self.sha256 = None
-            self.hash = None
+            self.sha256 = tx.sha256
+            self.hash = tx.hash
+            self.wit = copy.deepcopy(tx.wit)
 
     def deserialize(self, f):
         self.nVersion = struct.unpack("<i", f.read(4))[0]
         self.vin = deser_vector(f, CTxIn)
-        self.vout = deser_vector(f, CTxOut)
+        flags = 0
+        if len(self.vin) == 0:
+            flags = struct.unpack("<B", f.read(1))[0]
+            # Not sure why flags can't be zero, but this
+            # matches the implementation in bitcoind
+            if (flags != 0):
+                self.vin = deser_vector(f, CTxIn)
+                self.vout = deser_vector(f, CTxOut)
+        else:
+            self.vout = deser_vector(f, CTxOut)
+        if flags != 0:
+            self.wit.vtxinwit = [CTxinWitness()]*len(self.vin)
+            self.wit.deserialize(f)
         self.nLockTime = struct.unpack("<I", f.read(4))[0]
         self.sha256 = None
         self.hash = None
 
-    def serialize(self):
+    def serialize_without_witness(self):
+        r = b""
+        r += struct.pack("<i", self.nVersion)
+        r += ser_vector(self.vin)
+        r += ser_vector(self.vout)
+        r += struct.pack("<I", self.nLockTime)
+        return r
+
+    # Only serialize with witness when explicitly called for
+    def serialize_with_witness(self):
+        flags = 0
+        if not self.wit.is_null():
+            flags |= 1
         r = b""
         r += struct.pack("<i", self.nVersion)
+        if flags:
+            dummy = []
+            r += ser_vector(dummy)
+            r += struct.pack("<B", flags)
         r += ser_vector(self.vin)
         r += ser_vector(self.vout)
+        if flags & 1:
+            if (len(self.wit.vtxinwit) != len(self.vin)):
+                # vtxinwit must have the same length as vin
+                self.wit.vtxinwit = self.wit.vtxinwit[:len(self.vin)]
+                for i in range(len(self.wit.vtxinwit), len(self.vin)):
+                    self.wit.vtxinwit.append(CTxinWitness())
+            r += self.wit.serialize()
         r += struct.pack("<I", self.nLockTime)
         return r
 
+    # Regular serialization is without witness -- must explicitly
+    # call serialize_with_witness to include witness data.
+    def serialize(self):
+        return self.serialize_without_witness()
+
+    # Recalculate the txid (transaction hash without witness)
     def rehash(self):
         self.sha256 = None
         self.calc_sha256()
 
-    def calc_sha256(self):
+    # We will only cache the serialization without witness in
+    # self.sha256 and self.hash -- those are expected to be the txid.
+    def calc_sha256(self, with_witness=False):
+        if with_witness:
+            # Don't cache the result, just return it
+            return uint256_from_str(hash256(self.serialize_with_witness()))
+
         if self.sha256 is None:
-            self.sha256 = uint256_from_str(hash256(self.serialize()))
+            self.sha256 = uint256_from_str(hash256(self.serialize_without_witness()))
         self.hash = encode(hash256(self.serialize())[::-1], 'hex_codec').decode('ascii')
 
     def is_valid(self):
@@ -518,17 +644,17 @@ class CBlock(CBlockHeader):
         super(CBlock, self).deserialize(f)
         self.vtx = deser_vector(f, CTransaction)
 
-    def serialize(self):
+    def serialize(self, with_witness=False):
         r = b""
         r += super(CBlock, self).serialize()
-        r += ser_vector(self.vtx)
+        if with_witness:
+            r += ser_vector(self.vtx, "serialize_with_witness")
+        else:
+            r += ser_vector(self.vtx)
         return r
 
-    def calc_merkle_root(self):
-        hashes = []
-        for tx in self.vtx:
-            tx.calc_sha256()
-            hashes.append(ser_uint256(tx.sha256))
+    # Calculate the merkle root given a vector of transaction hashes
+    def get_merkle_root(self, hashes):
         while len(hashes) > 1:
             newhashes = []
             for i in range(0, len(hashes), 2):
@@ -537,6 +663,24 @@ class CBlock(CBlockHeader):
             hashes = newhashes
         return uint256_from_str(hashes[0])
 
+    def calc_merkle_root(self):
+        hashes = []
+        for tx in self.vtx:
+            tx.calc_sha256()
+            hashes.append(ser_uint256(tx.sha256))
+        return self.get_merkle_root(hashes)
+
+    def calc_witness_merkle_root(self):
+        # For witness root purposes, the hash of the
+        # coinbase, with witness, is defined to be 0...0
+        hashes = [ser_uint256(0)]
+
+        for tx in self.vtx[1:]:
+            # Calculate the hashes with witness data
+            hashes.append(ser_uint256(tx.calc_sha256(True)))
+
+        return self.get_merkle_root(hashes)
+
     def is_valid(self):
         self.calc_sha256()
         target = uint256_from_compact(self.nBits)
@@ -812,11 +956,16 @@ class msg_tx(object):
         self.tx.deserialize(f)
 
     def serialize(self):
-        return self.tx.serialize()
+        return self.tx.serialize_without_witness()
 
     def __repr__(self):
         return "msg_tx(tx=%s)" % (repr(self.tx))
 
+class msg_witness_tx(msg_tx):
+
+    def serialize(self):
+        return self.tx.serialize_with_witness()
+
 
 class msg_block(object):
     command = b"block"
@@ -849,6 +998,12 @@ class msg_generic(object):
     def __repr__(self):
         return "msg_generic()"
 
+class msg_witness_block(msg_block):
+
+    def serialize(self):
+        r = self.block.serialize(with_witness=True)
+        return r
+
 class msg_getaddr(object):
     command = b"getaddr"
 
@@ -947,6 +1102,7 @@ class msg_sendheaders(object):
     def __repr__(self):
         return "msg_sendheaders()"
 
+
 # getheaders message has
 # number of entries
 # vector of hashes
@@ -1068,6 +1224,8 @@ class NodeConnCB(object):
         # tests; it causes message delivery to sleep for the specified time
         # before acquiring the global lock and delivering the next message.
         self.deliver_sleep_time = None
+        # Remember the services our peer has advertised
+        self.peer_services = None
 
     def set_deliver_sleep_time(self, value):
         with mininode_lock:
@@ -1105,6 +1263,7 @@ class NodeConnCB(object):
         conn.ver_send = min(MY_VERSION, message.nVersion)
         if message.nVersion < 209:
             conn.ver_recv = conn.ver_send
+        conn.nServices = message.nServices
 
     def on_verack(self, conn, message):
         conn.ver_recv = conn.ver_send
@@ -1135,6 +1294,7 @@ class NodeConnCB(object):
     def on_mempool(self, conn): pass
     def on_pong(self, conn, message): pass
     def on_feefilter(self, conn, message): pass
+    def on_sendheaders(self, conn, message): pass
 
 # More useful callbacks and functions for NodeConnCB's which have a single NodeConn
 class SingleNodeConnCB(NodeConnCB):
@@ -1183,15 +1343,16 @@ class NodeConn(asyncore.dispatcher):
         b"getheaders": msg_getheaders,
         b"reject": msg_reject,
         b"mempool": msg_mempool,
-        b"feefilter": msg_feefilter
+        b"feefilter": msg_feefilter,
+        b"sendheaders": msg_sendheaders
     }
     MAGIC_BYTES = {
         "mainnet": b"\xf9\xbe\xb4\xd9",   # mainnet
         "testnet3": b"\x0b\x11\x09\x07",  # testnet3
-        "regtest": b"\xfa\xbf\xb5\xda"    # regtest
+        "regtest": b"\xfa\xbf\xb5\xda",   # regtest
     }
 
-    def __init__(self, dstaddr, dstport, rpc, callback, net="regtest", services=1):
+    def __init__(self, dstaddr, dstport, rpc, callback, net="regtest", services=NODE_NETWORK):
         asyncore.dispatcher.__init__(self, map=mininode_socket_map)
         self.log = logging.getLogger("NodeConn(%s:%d)" % (dstaddr, dstport))
         self.dstaddr = dstaddr
@@ -1206,6 +1367,7 @@ class NodeConn(asyncore.dispatcher):
         self.network = net
         self.cb = callback
         self.disconnect = False
+        self.nServices = 0
 
         # stuff version msg into sendbuf
         vt = msg_version()
diff --git a/qa/rpc-tests/test_framework/script.py b/qa/rpc-tests/test_framework/script.py
index 44a894fc8f..7678228c42 100644
--- a/qa/rpc-tests/test_framework/script.py
+++ b/qa/rpc-tests/test_framework/script.py
@@ -15,8 +15,9 @@ Functionality to build scripts, as well as SignatureHash().
 """
 
 
-from .mininode import CTransaction, CTxOut, hash256
+from .mininode import CTransaction, CTxOut, sha256, hash256, uint256_from_str, ser_uint256, ser_string
 from binascii import hexlify
+import hashlib
 
 import sys
 bchr = chr
@@ -36,6 +37,10 @@ MAX_SCRIPT_OPCODES = 201
 
 OPCODE_NAMES = {}
 
+def hash160(s):
+    return hashlib.new('ripemd160', sha256(s)).digest()
+
+
 _opcode_instances = []
 class CScriptOp(int):
     """A single script opcode"""
@@ -895,3 +900,48 @@ def SignatureHash(script, txTo, inIdx, hashtype):
     hash = hash256(s)
 
     return (hash, None)
+
+# TODO: Allow cached hashPrevouts/hashSequence/hashOutputs to be provided.
+# Performance optimization probably not necessary for python tests, however.
+# Note that this corresponds to sigversion == 1 in EvalScript, which is used
+# for version 0 witnesses.
+def SegwitVersion1SignatureHash(script, txTo, inIdx, hashtype, amount):
+
+    hashPrevouts = 0
+    hashSequence = 0
+    hashOutputs = 0
+
+    if not (hashtype & SIGHASH_ANYONECANPAY):
+        serialize_prevouts = bytes()
+        for i in txTo.vin:
+            serialize_prevouts += i.prevout.serialize()
+        hashPrevouts = uint256_from_str(hash256(serialize_prevouts))
+
+    if (not (hashtype & SIGHASH_ANYONECANPAY) and (hashtype & 0x1f) != SIGHASH_SINGLE and (hashtype & 0x1f) != SIGHASH_NONE):
+        serialize_sequence = bytes()
+        for i in txTo.vin:
+            serialize_sequence += struct.pack("<I", i.nSequence)
+        hashSequence = uint256_from_str(hash256(serialize_sequence))
+
+    if ((hashtype & 0x1f) != SIGHASH_SINGLE and (hashtype & 0x1f) != SIGHASH_NONE):
+        serialize_outputs = bytes()
+        for o in txTo.vout:
+            serialize_outputs += o.serialize()
+        hashOutputs = uint256_from_str(hash256(serialize_outputs))
+    elif ((hashtype & 0x1f) == SIGHASH_SINGLE and inIdx < len(txTo.vout)):
+        serialize_outputs = txTo.vout[inIdx].serialize()
+        hashOutputs = uint256_from_str(hash256(serialize_outputs))
+
+    ss = bytes()
+    ss += struct.pack("<i", txTo.nVersion)
+    ss += ser_uint256(hashPrevouts)
+    ss += ser_uint256(hashSequence)
+    ss += txTo.vin[inIdx].prevout.serialize()
+    ss += ser_string(script)
+    ss += struct.pack("<q", amount)
+    ss += struct.pack("<I", txTo.vin[inIdx].nSequence)
+    ss += ser_uint256(hashOutputs)
+    ss += struct.pack("<i", txTo.nLockTime)
+    ss += struct.pack("<I", hashtype)
+
+    return hash256(ss)