Merge #8068: Compact Blocks

48efec8 Fix some minor compact block issues that came up in review (Matt Corallo)
ccd06b9 Elaborate bucket size math (Pieter Wuille)
0d4cb48 Use vTxHashes to optimize InitData significantly (Matt Corallo)
8119026 Provide a flat list of txid/terators to txn in CTxMemPool (Matt Corallo)
678ee97 Add BIP 152 to implemented BIPs list (Matt Corallo)
56ba516 Add reconstruction debug logging (Matt Corallo)
2f34a2e Get our "best three" peers to announce blocks using cmpctblocks (Matt Corallo)
927f8ee Add ability to fetch CNode by NodeId (Matt Corallo)
d25cd3e Add receiver-side protocol implementation for CMPCTBLOCK stuff (Matt Corallo)
9c837d5 Add sender-side protocol implementation for CMPCTBLOCK stuff (Matt Corallo)
00c4078 Add protocol messages for short-ids blocks (Matt Corallo)
e3b2222 Add some blockencodings tests (Matt Corallo)
f4f8f14 Add TestMemPoolEntryHelper::FromTx version for CTransaction (Matt Corallo)
85ad31e Add partial-block block encodings API (Matt Corallo)
5249dac Add COMPACTSIZE wrapper similar to VARINT for serialization (Matt Corallo)
cbda71c Move context-required checks from CheckBlockHeader to Contextual... (Matt Corallo)
7c29ec9 If AcceptBlockHeader returns true, pindex will be set. (Matt Corallo)
96806c3 Stop trimming when mapTx is empty (Pieter Wuille)

17 files changed, 1160 insertions, 53 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 3df8e267bb..e3eaacdb4c 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -74,6 +74,7 @@ BITCOIN_CORE_H = \
   addrman.h \
   base58.h \
   bloom.h \
+  blockencodings.h \
   chain.h \
   chainparams.h \
   chainparamsbase.h \
@@ -163,6 +164,7 @@ libbitcoin_server_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
 libbitcoin_server_a_SOURCES = \
   addrman.cpp \
   bloom.cpp \
+  blockencodings.cpp \
   chain.cpp \
   checkpoints.cpp \
   httprpc.cpp \
diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index 41d811fb54..c8918eb53f 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -45,6 +45,7 @@ BITCOIN_TESTS =\
   test/base58_tests.cpp \
   test/base64_tests.cpp \
   test/bip32_tests.cpp \
+  test/blockencodings_tests.cpp \
   test/bloom_tests.cpp \
   test/Checkpoints_tests.cpp \
   test/coins_tests.cpp \
diff --git a/src/blockencodings.cpp b/src/blockencodings.cpp
new file mode 100644
index 0000000000..7fd6a9cf52
--- /dev/null
+++ b/src/blockencodings.cpp
@@ -0,0 +1,180 @@
+// Copyright (c) 2016 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include "blockencodings.h"
+#include "consensus/consensus.h"
+#include "consensus/validation.h"
+#include "chainparams.h"
+#include "hash.h"
+#include "random.h"
+#include "streams.h"
+#include "txmempool.h"
+#include "main.h"
+#include "util.h"
+
+#include <unordered_map>
+
+#define MIN_TRANSACTION_SIZE (::GetSerializeSize(CTransaction(), SER_NETWORK, PROTOCOL_VERSION))
+
+CBlockHeaderAndShortTxIDs::CBlockHeaderAndShortTxIDs(const CBlock& block) :
+        nonce(GetRand(std::numeric_limits<uint64_t>::max())),
+        shorttxids(block.vtx.size() - 1), prefilledtxn(1), header(block) {
+    FillShortTxIDSelector();
+    //TODO: Use our mempool prior to block acceptance to predictively fill more than just the coinbase
+    prefilledtxn[0] = {0, block.vtx[0]};
+    for (size_t i = 1; i < block.vtx.size(); i++) {
+        const CTransaction& tx = block.vtx[i];
+        shorttxids[i - 1] = GetShortID(tx.GetHash());
+    }
+}
+
+void CBlockHeaderAndShortTxIDs::FillShortTxIDSelector() const {
+    CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
+    stream << header << nonce;
+    CSHA256 hasher;
+    hasher.Write((unsigned char*)&(*stream.begin()), stream.end() - stream.begin());
+    uint256 shorttxidhash;
+    hasher.Finalize(shorttxidhash.begin());
+    shorttxidk0 = shorttxidhash.GetUint64(0);
+    shorttxidk1 = shorttxidhash.GetUint64(1);
+}
+
+uint64_t CBlockHeaderAndShortTxIDs::GetShortID(const uint256& txhash) const {
+    static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids calculation assumes 6-byte shorttxids");
+    return SipHashUint256(shorttxidk0, shorttxidk1, txhash) & 0xffffffffffffL;
+}
+
+
+
+ReadStatus PartiallyDownloadedBlock::InitData(const CBlockHeaderAndShortTxIDs& cmpctblock) {
+    if (cmpctblock.header.IsNull() || (cmpctblock.shorttxids.empty() && cmpctblock.prefilledtxn.empty()))
+        return READ_STATUS_INVALID;
+    if (cmpctblock.shorttxids.size() + cmpctblock.prefilledtxn.size() > MAX_BLOCK_SIZE / MIN_TRANSACTION_SIZE)
+        return READ_STATUS_INVALID;
+
+    assert(header.IsNull() && txn_available.empty());
+    header = cmpctblock.header;
+    txn_available.resize(cmpctblock.BlockTxCount());
+
+    int32_t lastprefilledindex = -1;
+    for (size_t i = 0; i < cmpctblock.prefilledtxn.size(); i++) {
+        if (cmpctblock.prefilledtxn[i].tx.IsNull())
+            return READ_STATUS_INVALID;
+
+        lastprefilledindex += cmpctblock.prefilledtxn[i].index + 1; //index is a uint16_t, so cant overflow here
+        if (lastprefilledindex > std::numeric_limits<uint16_t>::max())
+            return READ_STATUS_INVALID;
+        if ((uint32_t)lastprefilledindex > cmpctblock.shorttxids.size() + i) {
+            // If we are inserting a tx at an index greater than our full list of shorttxids
+            // plus the number of prefilled txn we've inserted, then we have txn for which we
+            // have neither a prefilled txn or a shorttxid!
+            return READ_STATUS_INVALID;
+        }
+        txn_available[lastprefilledindex] = std::make_shared<CTransaction>(cmpctblock.prefilledtxn[i].tx);
+    }
+    prefilled_count = cmpctblock.prefilledtxn.size();
+
+    // Calculate map of txids -> positions and check mempool to see what we have (or dont)
+    // Because well-formed cmpctblock messages will have a (relatively) uniform distribution
+    // of short IDs, any highly-uneven distribution of elements can be safely treated as a
+    // READ_STATUS_FAILED.
+    std::unordered_map<uint64_t, uint16_t> shorttxids(cmpctblock.shorttxids.size());
+    uint16_t index_offset = 0;
+    for (size_t i = 0; i < cmpctblock.shorttxids.size(); i++) {
+        while (txn_available[i + index_offset])
+            index_offset++;
+        shorttxids[cmpctblock.shorttxids[i]] = i + index_offset;
+        // To determine the chance that the number of entries in a bucket exceeds N,
+        // we use the fact that the number of elements in a single bucket is
+        // binomially distributed (with n = the number of shorttxids S, and p =
+        // 1 / the number of buckets), that in the worst case the number of buckets is
+        // equal to S (due to std::unordered_map having a default load factor of 1.0),
+        // and that the chance for any bucket to exceed N elements is at most
+        // buckets * (the chance that any given bucket is above N elements).
+        // Thus: P(max_elements_per_bucket > N) <= S * (1 - cdf(binomial(n=S,p=1/S), N)).
+        // If we assume blocks of up to 16000, allowing 12 elements per bucket should
+        // only fail once per ~1 million block transfers (per peer and connection).
+        if (shorttxids.bucket_size(shorttxids.bucket(cmpctblock.shorttxids[i])) > 12)
+            return READ_STATUS_FAILED;
+    }
+    // TODO: in the shortid-collision case, we should instead request both transactions
+    // which collided. Falling back to full-block-request here is overkill.
+    if (shorttxids.size() != cmpctblock.shorttxids.size())
+        return READ_STATUS_FAILED; // Short ID collision
+
+    std::vector<bool> have_txn(txn_available.size());
+    LOCK(pool->cs);
+    const std::vector<std::pair<uint256, CTxMemPool::txiter> >& vTxHashes = pool->vTxHashes;
+    for (size_t i = 0; i < vTxHashes.size(); i++) {
+        uint64_t shortid = cmpctblock.GetShortID(vTxHashes[i].first);
+        std::unordered_map<uint64_t, uint16_t>::iterator idit = shorttxids.find(shortid);
+        if (idit != shorttxids.end()) {
+            if (!have_txn[idit->second]) {
+                txn_available[idit->second] = vTxHashes[i].second->GetSharedTx();
+                have_txn[idit->second]  = true;
+                mempool_count++;
+            } else {
+                // If we find two mempool txn that match the short id, just request it.
+                // This should be rare enough that the extra bandwidth doesn't matter,
+                // but eating a round-trip due to FillBlock failure would be annoying
+                if (txn_available[idit->second]) {
+                    txn_available[idit->second].reset();
+                    mempool_count--;
+                }
+            }
+        }
+        // Though ideally we'd continue scanning for the two-txn-match-shortid case,
+        // the performance win of an early exit here is too good to pass up and worth
+        // the extra risk.
+        if (mempool_count == shorttxids.size())
+            break;
+    }
+
+    LogPrint("cmpctblock", "Initialized PartiallyDownloadedBlock for block %s using a cmpctblock of size %lu\n", cmpctblock.header.GetHash().ToString(), cmpctblock.GetSerializeSize(SER_NETWORK, PROTOCOL_VERSION));
+
+    return READ_STATUS_OK;
+}
+
+bool PartiallyDownloadedBlock::IsTxAvailable(size_t index) const {
+    assert(!header.IsNull());
+    assert(index < txn_available.size());
+    return txn_available[index] ? true : false;
+}
+
+ReadStatus PartiallyDownloadedBlock::FillBlock(CBlock& block, const std::vector<CTransaction>& vtx_missing) const {
+    assert(!header.IsNull());
+    block = header;
+    block.vtx.resize(txn_available.size());
+
+    size_t tx_missing_offset = 0;
+    for (size_t i = 0; i < txn_available.size(); i++) {
+        if (!txn_available[i]) {
+            if (vtx_missing.size() <= tx_missing_offset)
+                return READ_STATUS_INVALID;
+            block.vtx[i] = vtx_missing[tx_missing_offset++];
+        } else
+            block.vtx[i] = *txn_available[i];
+    }
+    if (vtx_missing.size() != tx_missing_offset)
+        return READ_STATUS_INVALID;
+
+    CValidationState state;
+    if (!CheckBlock(block, state, Params().GetConsensus())) {
+        // TODO: We really want to just check merkle tree manually here,
+        // but that is expensive, and CheckBlock caches a block's
+        // "checked-status" (in the CBlock?). CBlock should be able to
+        // check its own merkle root and cache that check.
+        if (state.CorruptionPossible())
+            return READ_STATUS_FAILED; // Possible Short ID collision
+        return READ_STATUS_INVALID;
+    }
+
+    LogPrint("cmpctblock", "Successfully reconstructed block %s with %lu txn prefilled, %lu txn from mempool and %lu txn requested\n", header.GetHash().ToString(), prefilled_count, mempool_count, vtx_missing.size());
+    if (vtx_missing.size() < 5) {
+        for(const CTransaction& tx : vtx_missing)
+            LogPrint("cmpctblock", "Reconstructed block %s required tx %s\n", header.GetHash().ToString(), tx.GetHash().ToString());
+    }
+
+    return READ_STATUS_OK;
+}
diff --git a/src/blockencodings.h b/src/blockencodings.h
new file mode 100644
index 0000000000..b980e9e286
--- /dev/null
+++ b/src/blockencodings.h
@@ -0,0 +1,206 @@
+// Copyright (c) 2016 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_BLOCK_ENCODINGS_H
+#define BITCOIN_BLOCK_ENCODINGS_H
+
+#include "primitives/block.h"
+
+#include <memory>
+
+class CTxMemPool;
+
+// Dumb helper to handle CTransaction compression at serialize-time
+struct TransactionCompressor {
+private:
+    CTransaction& tx;
+public:
+    TransactionCompressor(CTransaction& txIn) : tx(txIn) {}
+
+    ADD_SERIALIZE_METHODS;
+
+    template <typename Stream, typename Operation>
+    inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
+        READWRITE(tx); //TODO: Compress tx encoding
+    }
+};
+
+class BlockTransactionsRequest {
+public:
+    // A BlockTransactionsRequest message
+    uint256 blockhash;
+    std::vector<uint16_t> indexes;
+
+    ADD_SERIALIZE_METHODS;
+
+    template <typename Stream, typename Operation>
+    inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
+        READWRITE(blockhash);
+        uint64_t indexes_size = (uint64_t)indexes.size();
+        READWRITE(COMPACTSIZE(indexes_size));
+        if (ser_action.ForRead()) {
+            size_t i = 0;
+            while (indexes.size() < indexes_size) {
+                indexes.resize(std::min((uint64_t)(1000 + indexes.size()), indexes_size));
+                for (; i < indexes.size(); i++) {
+                    uint64_t index = 0;
+                    READWRITE(COMPACTSIZE(index));
+                    if (index > std::numeric_limits<uint16_t>::max())
+                        throw std::ios_base::failure("index overflowed 16 bits");
+                    indexes[i] = index;
+                }
+            }
+
+            uint16_t offset = 0;
+            for (size_t i = 0; i < indexes.size(); i++) {
+                if (uint64_t(indexes[i]) + uint64_t(offset) > std::numeric_limits<uint16_t>::max())
+                    throw std::ios_base::failure("indexes overflowed 16 bits");
+                indexes[i] = indexes[i] + offset;
+                offset = indexes[i] + 1;
+            }
+        } else {
+            for (size_t i = 0; i < indexes.size(); i++) {
+                uint64_t index = indexes[i] - (i == 0 ? 0 : (indexes[i - 1] + 1));
+                READWRITE(COMPACTSIZE(index));
+            }
+        }
+    }
+};
+
+class BlockTransactions {
+public:
+    // A BlockTransactions message
+    uint256 blockhash;
+    std::vector<CTransaction> txn;
+
+    BlockTransactions() {}
+    BlockTransactions(const BlockTransactionsRequest& req) :
+        blockhash(req.blockhash), txn(req.indexes.size()) {}
+
+    ADD_SERIALIZE_METHODS;
+
+    template <typename Stream, typename Operation>
+    inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
+        READWRITE(blockhash);
+        uint64_t txn_size = (uint64_t)txn.size();
+        READWRITE(COMPACTSIZE(txn_size));
+        if (ser_action.ForRead()) {
+            size_t i = 0;
+            while (txn.size() < txn_size) {
+                txn.resize(std::min((uint64_t)(1000 + txn.size()), txn_size));
+                for (; i < txn.size(); i++)
+                    READWRITE(REF(TransactionCompressor(txn[i])));
+            }
+        } else {
+            for (size_t i = 0; i < txn.size(); i++)
+                READWRITE(REF(TransactionCompressor(txn[i])));
+        }
+    }
+};
+
+// Dumb serialization/storage-helper for CBlockHeaderAndShortTxIDs and PartiallyDownlaodedBlock
+struct PrefilledTransaction {
+    // Used as an offset since last prefilled tx in CBlockHeaderAndShortTxIDs,
+    // as a proper transaction-in-block-index in PartiallyDownloadedBlock
+    uint16_t index;
+    CTransaction tx;
+
+    ADD_SERIALIZE_METHODS;
+
+    template <typename Stream, typename Operation>
+    inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
+        uint64_t idx = index;
+        READWRITE(COMPACTSIZE(idx));
+        if (idx > std::numeric_limits<uint16_t>::max())
+            throw std::ios_base::failure("index overflowed 16-bits");
+        index = idx;
+        READWRITE(REF(TransactionCompressor(tx)));
+    }
+};
+
+typedef enum ReadStatus_t
+{
+    READ_STATUS_OK,
+    READ_STATUS_INVALID, // Invalid object, peer is sending bogus crap
+    READ_STATUS_FAILED, // Failed to process object
+} ReadStatus;
+
+class CBlockHeaderAndShortTxIDs {
+private:
+    mutable uint64_t shorttxidk0, shorttxidk1;
+    uint64_t nonce;
+
+    void FillShortTxIDSelector() const;
+
+    friend class PartiallyDownloadedBlock;
+
+    static const int SHORTTXIDS_LENGTH = 6;
+protected:
+    std::vector<uint64_t> shorttxids;
+    std::vector<PrefilledTransaction> prefilledtxn;
+
+public:
+    CBlockHeader header;
+
+    // Dummy for deserialization
+    CBlockHeaderAndShortTxIDs() {}
+
+    CBlockHeaderAndShortTxIDs(const CBlock& block);
+
+    uint64_t GetShortID(const uint256& txhash) const;
+
+    size_t BlockTxCount() const { return shorttxids.size() + prefilledtxn.size(); }
+
+    ADD_SERIALIZE_METHODS;
+
+    template <typename Stream, typename Operation>
+    inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
+        READWRITE(header);
+        READWRITE(nonce);
+
+        uint64_t shorttxids_size = (uint64_t)shorttxids.size();
+        READWRITE(COMPACTSIZE(shorttxids_size));
+        if (ser_action.ForRead()) {
+            size_t i = 0;
+            while (shorttxids.size() < shorttxids_size) {
+                shorttxids.resize(std::min((uint64_t)(1000 + shorttxids.size()), shorttxids_size));
+                for (; i < shorttxids.size(); i++) {
+                    uint32_t lsb = 0; uint16_t msb = 0;
+                    READWRITE(lsb);
+                    READWRITE(msb);
+                    shorttxids[i] = (uint64_t(msb) << 32) | uint64_t(lsb);
+                    static_assert(SHORTTXIDS_LENGTH == 6, "shorttxids serialization assumes 6-byte shorttxids");
+                }
+            }
+        } else {
+            for (size_t i = 0; i < shorttxids.size(); i++) {
+                uint32_t lsb = shorttxids[i] & 0xffffffff;
+                uint16_t msb = (shorttxids[i] >> 32) & 0xffff;
+                READWRITE(lsb);
+                READWRITE(msb);
+            }
+        }
+
+        READWRITE(prefilledtxn);
+
+        if (ser_action.ForRead())
+            FillShortTxIDSelector();
+    }
+};
+
+class PartiallyDownloadedBlock {
+protected:
+    std::vector<std::shared_ptr<const CTransaction> > txn_available;
+    size_t prefilled_count = 0, mempool_count = 0;
+    CTxMemPool* pool;
+public:
+    CBlockHeader header;
+    PartiallyDownloadedBlock(CTxMemPool* poolIn) : pool(poolIn) {}
+
+    ReadStatus InitData(const CBlockHeaderAndShortTxIDs& cmpctblock);
+    bool IsTxAvailable(size_t index) const;
+    ReadStatus FillBlock(CBlock& block, const std::vector<CTransaction>& vtx_missing) const;
+};
+
+#endif
diff --git a/src/main.cpp b/src/main.cpp
index 361526f337..ae195ecc40 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -7,6 +7,7 @@
 
 #include "addrman.h"
 #include "arith_uint256.h"
+#include "blockencodings.h"
 #include "chainparams.h"
 #include "checkpoints.h"
 #include "checkqueue.h"
@@ -207,11 +208,15 @@ namespace {
     /** Blocks that are in flight, and that are in the queue to be downloaded. Protected by cs_main. */
     struct QueuedBlock {
         uint256 hash;
-        CBlockIndex* pindex;     //!< Optional.
-        bool fValidatedHeaders;  //!< Whether this block has validated headers at the time of request.
+        CBlockIndex* pindex;                                     //!< Optional.
+        bool fValidatedHeaders;                                  //!< Whether this block has validated headers at the time of request.
+        std::unique_ptr<PartiallyDownloadedBlock> partialBlock;  //!< Optional, used for CMPCTBLOCK downloads
     };
     map<uint256, pair<NodeId, list<QueuedBlock>::iterator> > mapBlocksInFlight;
 
+    /** Stack of nodes which we have set to announce using compact blocks */
+    list<NodeId> lNodesAnnouncingHeaderAndIDs;
+
     /** Number of preferable block download peers. */
     int nPreferredDownload = 0;
 
@@ -284,6 +289,10 @@ struct CNodeState {
     bool fPreferredDownload;
     //! Whether this peer wants invs or headers (when possible) for block announcements.
     bool fPreferHeaders;
+    //! Whether this peer wants invs or cmpctblocks (when possible) for block announcements.
+    bool fPreferHeaderAndIDs;
+    //! Whether this peer will send us cmpctblocks if we request them
+    bool fProvidesHeaderAndIDs;
 
     CNodeState() {
         fCurrentlyConnected = false;
@@ -300,6 +309,8 @@ struct CNodeState {
         nBlocksInFlightValidHeaders = 0;
         fPreferredDownload = false;
         fPreferHeaders = false;
+        fPreferHeaderAndIDs = false;
+        fProvidesHeaderAndIDs = false;
     }
 };
 
@@ -368,6 +379,7 @@ void FinalizeNode(NodeId nodeid) {
 
 // Requires cs_main.
 // Returns a bool indicating whether we requested this block.
+// Also used if a block was /not/ received and timed out or started with another peer
 bool MarkBlockAsReceived(const uint256& hash) {
     map<uint256, pair<NodeId, list<QueuedBlock>::iterator> >::iterator itInFlight = mapBlocksInFlight.find(hash);
     if (itInFlight != mapBlocksInFlight.end()) {
@@ -391,17 +403,26 @@ bool MarkBlockAsReceived(const uint256& hash) {
 }
 
 // Requires cs_main.
-void MarkBlockAsInFlight(NodeId nodeid, const uint256& hash, const Consensus::Params& consensusParams, CBlockIndex *pindex = NULL) {
+// returns false, still setting pit, if the block was already in flight from the same peer
+// pit will only be valid as long as the same cs_main lock is being held
+bool MarkBlockAsInFlight(NodeId nodeid, const uint256& hash, const Consensus::Params& consensusParams, CBlockIndex *pindex = NULL, list<QueuedBlock>::iterator **pit = NULL) {
     CNodeState *state = State(nodeid);
     assert(state != NULL);
 
+    // Short-circuit most stuff in case its from the same node
+    map<uint256, pair<NodeId, list<QueuedBlock>::iterator> >::iterator itInFlight = mapBlocksInFlight.find(hash);
+    if (itInFlight != mapBlocksInFlight.end() && itInFlight->second.first == nodeid) {
+        *pit = &itInFlight->second.second;
+        return false;
+    }
+
     // Make sure it's not listed somewhere already.
     MarkBlockAsReceived(hash);
 
-    QueuedBlock newentry = {hash, pindex, pindex != NULL};
-    list<QueuedBlock>::iterator it = state->vBlocksInFlight.insert(state->vBlocksInFlight.end(), newentry);
+    list<QueuedBlock>::iterator it = state->vBlocksInFlight.insert(state->vBlocksInFlight.end(),
+            {hash, pindex, pindex != NULL, std::unique_ptr<PartiallyDownloadedBlock>(pit ? new PartiallyDownloadedBlock(&mempool) : NULL)});
     state->nBlocksInFlight++;
-    state->nBlocksInFlightValidHeaders += newentry.fValidatedHeaders;
+    state->nBlocksInFlightValidHeaders += it->fValidatedHeaders;
     if (state->nBlocksInFlight == 1) {
         // We're starting a block download (batch) from this peer.
         state->nDownloadingSince = GetTimeMicros();
@@ -409,7 +430,10 @@ void MarkBlockAsInFlight(NodeId nodeid, const uint256& hash, const Consensus::Pa
     if (state->nBlocksInFlightValidHeaders == 1 && pindex != NULL) {
         nPeersWithValidatedDownloads++;
     }
-    mapBlocksInFlight[hash] = std::make_pair(nodeid, it);
+    itInFlight = mapBlocksInFlight.insert(std::make_pair(hash, std::make_pair(nodeid, it))).first;
+    if (pit)
+        *pit = &itInFlight->second.second;
+    return true;
 }
 
 /** Check whether the last unknown block a peer advertised is not yet known. */
@@ -445,6 +469,28 @@ void UpdateBlockAvailability(NodeId nodeid, const uint256 &hash) {
     }
 }
 
+void MaybeSetPeerAsAnnouncingHeaderAndIDs(const CNodeState* nodestate, CNode* pfrom) {
+    if (nodestate->fProvidesHeaderAndIDs) {
+        BOOST_FOREACH(const NodeId nodeid, lNodesAnnouncingHeaderAndIDs)
+            if (nodeid == pfrom->GetId())
+                return;
+        bool fAnnounceUsingCMPCTBLOCK = false;
+        uint64_t nCMPCTBLOCKVersion = 1;
+        if (lNodesAnnouncingHeaderAndIDs.size() >= 3) {
+            // As per BIP152, we only get 3 of our peers to announce
+            // blocks using compact encodings.
+            CNode* pnodeStop = FindNode(lNodesAnnouncingHeaderAndIDs.front());
+            if (pnodeStop) {
+                pnodeStop->PushMessage(NetMsgType::SENDCMPCT, fAnnounceUsingCMPCTBLOCK, nCMPCTBLOCKVersion);
+                lNodesAnnouncingHeaderAndIDs.pop_front();
+            }
+        }
+        fAnnounceUsingCMPCTBLOCK = true;
+        pfrom->PushMessage(NetMsgType::SENDCMPCT, fAnnounceUsingCMPCTBLOCK, nCMPCTBLOCKVersion);
+        lNodesAnnouncingHeaderAndIDs.push_back(pfrom->GetId());
+    }
+}
+
 // Requires cs_main
 bool CanDirectFetch(const Consensus::Params &consensusParams)
 {
@@ -2272,7 +2318,7 @@ bool ConnectBlock(const CBlock& block, CValidationState& state, CBlockIndex* pin
     int64_t nTimeStart = GetTimeMicros();
 
     // Check it again in case a previous version let a bad block in
-    if (!CheckBlock(block, state, chainparams.GetConsensus(), GetAdjustedTime(), !fJustCheck, !fJustCheck))
+    if (!CheckBlock(block, state, chainparams.GetConsensus(), !fJustCheck, !fJustCheck))
         return error("%s: Consensus::CheckBlock: %s", __func__, FormatStateMessage(state));
 
     // verify that the view's current state corresponds to the previous block
@@ -3310,20 +3356,16 @@ bool FindUndoPos(CValidationState &state, int nFile, CDiskBlockPos &pos, unsigne
     return true;
 }
 
-bool CheckBlockHeader(const CBlockHeader& block, CValidationState& state, const Consensus::Params& consensusParams, int64_t nAdjustedTime, bool fCheckPOW)
+bool CheckBlockHeader(const CBlockHeader& block, CValidationState& state, const Consensus::Params& consensusParams, bool fCheckPOW)
 {
     // Check proof of work matches claimed amount
     if (fCheckPOW && !CheckProofOfWork(block.GetHash(), block.nBits, consensusParams))
         return state.DoS(50, false, REJECT_INVALID, "high-hash", false, "proof of work failed");
 
-    // Check timestamp
-    if (block.GetBlockTime() > nAdjustedTime + 2 * 60 * 60)
-        return state.Invalid(false, REJECT_INVALID, "time-too-new", "block timestamp too far in the future");
-
     return true;
 }
 
-bool CheckBlock(const CBlock& block, CValidationState& state, const Consensus::Params& consensusParams, int64_t nAdjustedTime, bool fCheckPOW, bool fCheckMerkleRoot)
+bool CheckBlock(const CBlock& block, CValidationState& state, const Consensus::Params& consensusParams, bool fCheckPOW, bool fCheckMerkleRoot)
 {
     // These are checks that are independent of context.
 
@@ -3332,7 +3374,7 @@ bool CheckBlock(const CBlock& block, CValidationState& state, const Consensus::P
 
     // Check that the header is valid (particularly PoW).  This is mostly
     // redundant with the call in AcceptBlockHeader.
-    if (!CheckBlockHeader(block, state, consensusParams, nAdjustedTime, fCheckPOW))
+    if (!CheckBlockHeader(block, state, consensusParams, fCheckPOW))
         return false;
 
     // Check the merkle root.
@@ -3398,7 +3440,7 @@ static bool CheckIndexAgainstCheckpoint(const CBlockIndex* pindexPrev, CValidati
     return true;
 }
 
-bool ContextualCheckBlockHeader(const CBlockHeader& block, CValidationState& state, const Consensus::Params& consensusParams, CBlockIndex * const pindexPrev)
+bool ContextualCheckBlockHeader(const CBlockHeader& block, CValidationState& state, const Consensus::Params& consensusParams, CBlockIndex * const pindexPrev, int64_t nAdjustedTime)
 {
     // Check proof of work
     if (block.nBits != GetNextWorkRequired(pindexPrev, &block, consensusParams))
@@ -3408,6 +3450,10 @@ bool ContextualCheckBlockHeader(const CBlockHeader& block, CValidationState& sta
     if (block.GetBlockTime() <= pindexPrev->GetMedianTimePast())
         return state.Invalid(false, REJECT_INVALID, "time-too-old", "block's timestamp is too early");
 
+    // Check timestamp
+    if (block.GetBlockTime() > nAdjustedTime + 2 * 60 * 60)
+        return state.Invalid(false, REJECT_INVALID, "time-too-new", "block timestamp too far in the future");
+
     // Reject outdated version blocks when 95% (75% on testnet) of the network has upgraded:
     for (int32_t version = 2; version < 5; ++version) // check for version 2, 3 and 4 upgrades
         if (block.nVersion < version && IsSuperMajority(version, pindexPrev, consensusParams.nMajorityRejectBlockOutdated, consensusParams))
@@ -3472,7 +3518,7 @@ static bool AcceptBlockHeader(const CBlockHeader& block, CValidationState& state
             return true;
         }
 
-        if (!CheckBlockHeader(block, state, chainparams.GetConsensus(), GetAdjustedTime()))
+        if (!CheckBlockHeader(block, state, chainparams.GetConsensus()))
             return error("%s: Consensus::CheckBlockHeader: %s, %s", __func__, hash.ToString(), FormatStateMessage(state));
 
         // Get prev block index
@@ -3488,7 +3534,7 @@ static bool AcceptBlockHeader(const CBlockHeader& block, CValidationState& state
         if (fCheckpointsEnabled && !CheckIndexAgainstCheckpoint(pindexPrev, state, chainparams, hash))
             return error("%s: CheckIndexAgainstCheckpoint(): %s", __func__, state.GetRejectReason().c_str());
 
-        if (!ContextualCheckBlockHeader(block, state, chainparams.GetConsensus(), pindexPrev))
+        if (!ContextualCheckBlockHeader(block, state, chainparams.GetConsensus(), pindexPrev, GetAdjustedTime()))
             return error("%s: Consensus::ContextualCheckBlockHeader: %s, %s", __func__, hash.ToString(), FormatStateMessage(state));
     }
     if (pindex == NULL)
@@ -3621,9 +3667,9 @@ bool TestBlockValidity(CValidationState& state, const CChainParams& chainparams,
     indexDummy.nHeight = pindexPrev->nHeight + 1;
 
     // NOTE: CheckBlockHeader is called by CheckBlock
-    if (!ContextualCheckBlockHeader(block, state, chainparams.GetConsensus(), pindexPrev))
+    if (!ContextualCheckBlockHeader(block, state, chainparams.GetConsensus(), pindexPrev, GetAdjustedTime()))
         return error("%s: Consensus::ContextualCheckBlockHeader: %s", __func__, FormatStateMessage(state));
-    if (!CheckBlock(block, state, chainparams.GetConsensus(), GetAdjustedTime(), fCheckPOW, fCheckMerkleRoot))
+    if (!CheckBlock(block, state, chainparams.GetConsensus(), fCheckPOW, fCheckMerkleRoot))
         return error("%s: Consensus::CheckBlock: %s", __func__, FormatStateMessage(state));
     if (!ContextualCheckBlock(block, state, pindexPrev))
         return error("%s: Consensus::ContextualCheckBlock: %s", __func__, FormatStateMessage(state));
@@ -3968,7 +4014,7 @@ bool CVerifyDB::VerifyDB(const CChainParams& chainparams, CCoinsView *coinsview,
         if (!ReadBlockFromDisk(block, pindex, chainparams.GetConsensus()))
             return error("VerifyDB(): *** ReadBlockFromDisk failed at %d, hash=%s", pindex->nHeight, pindex->GetBlockHash().ToString());
         // check level 1: verify block validity
-        if (nCheckLevel >= 1 && !CheckBlock(block, state, chainparams.GetConsensus(), GetAdjustedTime()))
+        if (nCheckLevel >= 1 && !CheckBlock(block, state, chainparams.GetConsensus()))
             return error("%s: *** found bad block at %d, hash=%s (%s)\n", __func__, 
                          pindex->nHeight, pindex->GetBlockHash().ToString(), FormatStateMessage(state));
         // check level 2: verify undo validity
@@ -4506,7 +4552,7 @@ void static ProcessGetData(CNode* pfrom, const Consensus::Params& consensusParam
             boost::this_thread::interruption_point();
             it++;
 
-            if (inv.type == MSG_BLOCK || inv.type == MSG_FILTERED_BLOCK)
+            if (inv.type == MSG_BLOCK || inv.type == MSG_FILTERED_BLOCK || inv.type == MSG_CMPCT_BLOCK)
             {
                 bool send = false;
                 BlockMap::iterator mi = mapBlockIndex.find(inv.hash);
@@ -4548,7 +4594,7 @@ void static ProcessGetData(CNode* pfrom, const Consensus::Params& consensusParam
                         assert(!"cannot load block from disk");
                     if (inv.type == MSG_BLOCK)
                         pfrom->PushMessage(NetMsgType::BLOCK, block);
-                    else // MSG_FILTERED_BLOCK)
+                    else if (inv.type == MSG_FILTERED_BLOCK)
                     {
                         LOCK(pfrom->cs_filter);
                         if (pfrom->pfilter)
@@ -4568,6 +4614,18 @@ void static ProcessGetData(CNode* pfrom, const Consensus::Params& consensusParam
                         // else
                             // no response
                     }
+                    else if (inv.type == MSG_CMPCT_BLOCK)
+                    {
+                        // If a peer is asking for old blocks, we're almost guaranteed
+                        // they wont have a useful mempool to match against a compact block,
+                        // and we dont feel like constructing the object for them, so
+                        // instead we respond with the full, non-compact block.
+                        if (mi->second->nHeight >= chainActive.Height() - 10) {
+                            CBlockHeaderAndShortTxIDs cmpctblock(block);
+                            pfrom->PushMessage(NetMsgType::CMPCTBLOCK, cmpctblock);
+                        } else
+                            pfrom->PushMessage(NetMsgType::BLOCK, block);
+                    }
 
                     // Trigger the peer node to send a getblocks request for the next batch of inventory
                     if (inv.hash == pfrom->hashContinue)
@@ -4607,7 +4665,7 @@ void static ProcessGetData(CNode* pfrom, const Consensus::Params& consensusParam
             // Track requests for our stuff.
             GetMainSignals().Inventory(inv.hash);
 
-            if (inv.type == MSG_BLOCK || inv.type == MSG_FILTERED_BLOCK)
+            if (inv.type == MSG_BLOCK || inv.type == MSG_FILTERED_BLOCK || inv.type == MSG_CMPCT_BLOCK)
                 break;
         }
     }
@@ -4817,6 +4875,16 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
             // nodes)
             pfrom->PushMessage(NetMsgType::SENDHEADERS);
         }
+        if (pfrom->nVersion >= SHORT_IDS_BLOCKS_VERSION) {
+            // Tell our peer we are willing to provide version-1 cmpctblocks
+            // However, we do not request new block announcements using
+            // cmpctblock messages.
+            // We send this to non-NODE NETWORK peers as well, because
+            // they may wish to request compact blocks from us
+            bool fAnnounceUsingCMPCTBLOCK = false;
+            uint64_t nCMPCTBLOCKVersion = 1;
+            pfrom->PushMessage(NetMsgType::SENDCMPCT, fAnnounceUsingCMPCTBLOCK, nCMPCTBLOCKVersion);
+        }
     }
 
 
@@ -4891,6 +4959,18 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
         State(pfrom->GetId())->fPreferHeaders = true;
     }
 
+    else if (strCommand == NetMsgType::SENDCMPCT)
+    {
+        bool fAnnounceUsingCMPCTBLOCK = false;
+        uint64_t nCMPCTBLOCKVersion = 1;
+        vRecv >> fAnnounceUsingCMPCTBLOCK >> nCMPCTBLOCKVersion;
+        if (nCMPCTBLOCKVersion == 1) {
+            LOCK(cs_main);
+            State(pfrom->GetId())->fProvidesHeaderAndIDs = true;
+            State(pfrom->GetId())->fPreferHeaderAndIDs = fAnnounceUsingCMPCTBLOCK;
+        }
+    }
+
 
     else if (strCommand == NetMsgType::INV)
     {
@@ -4937,7 +5017,10 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
                     CNodeState *nodestate = State(pfrom->GetId());
                     if (CanDirectFetch(chainparams.GetConsensus()) &&
                         nodestate->nBlocksInFlight < MAX_BLOCKS_IN_TRANSIT_PER_PEER) {
-                        vToFetch.push_back(inv);
+                        if (nodestate->fProvidesHeaderAndIDs)
+                            vToFetch.push_back(CInv(MSG_CMPCT_BLOCK, inv.hash));
+                        else
+                            vToFetch.push_back(inv);
                         // Mark block as in flight already, even though the actual "getdata" message only goes out
                         // later (within the same cs_main lock, though).
                         MarkBlockAsInFlight(pfrom->GetId(), inv.hash, chainparams.GetConsensus());
@@ -5034,6 +5117,39 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
     }
 
 
+    else if (strCommand == NetMsgType::GETBLOCKTXN)
+    {
+        BlockTransactionsRequest req;
+        vRecv >> req;
+
+        BlockMap::iterator it = mapBlockIndex.find(req.blockhash);
+        if (it == mapBlockIndex.end() || !(it->second->nStatus & BLOCK_HAVE_DATA)) {
+            Misbehaving(pfrom->GetId(), 100);
+            LogPrintf("Peer %d sent us a getblocktxn for a block we don't have", pfrom->id);
+            return true;
+        }
+
+        if (it->second->nHeight < chainActive.Height() - 15) {
+            LogPrint("net", "Peer %d sent us a getblocktxn for a block > 15 deep", pfrom->id);
+            return true;
+        }
+
+        CBlock block;
+        assert(ReadBlockFromDisk(block, it->second, chainparams.GetConsensus()));
+
+        BlockTransactions resp(req);
+        for (size_t i = 0; i < req.indexes.size(); i++) {
+            if (req.indexes[i] >= block.vtx.size()) {
+                Misbehaving(pfrom->GetId(), 100);
+                LogPrintf("Peer %d sent us a getblocktxn with out-of-bounds tx indices", pfrom->id);
+                return true;
+            }
+            resp.txn[i] = block.vtx[req.indexes[i]];
+        }
+        pfrom->PushMessage(NetMsgType::BLOCKTXN, resp);
+    }
+
+
     else if (strCommand == NetMsgType::GETHEADERS)
     {
         CBlockLocator locator;
@@ -5241,6 +5357,174 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
     }
 
 
+    else if (strCommand == NetMsgType::CMPCTBLOCK && !fImporting && !fReindex) // Ignore blocks received while importing
+    {
+        CBlockHeaderAndShortTxIDs cmpctblock;
+        vRecv >> cmpctblock;
+
+        LOCK(cs_main);
+
+        if (mapBlockIndex.find(cmpctblock.header.hashPrevBlock) == mapBlockIndex.end()) {
+            // Doesn't connect (or is genesis), instead of DoSing in AcceptBlockHeader, request deeper headers
+            if (!IsInitialBlockDownload())
+                pfrom->PushMessage(NetMsgType::GETHEADERS, chainActive.GetLocator(pindexBestHeader), uint256());
+            return true;
+        }
+
+        CBlockIndex *pindex = NULL;
+        CValidationState state;
+        if (!AcceptBlockHeader(cmpctblock.header, state, chainparams, &pindex)) {
+            int nDoS;
+            if (state.IsInvalid(nDoS)) {
+                if (nDoS > 0)
+                    Misbehaving(pfrom->GetId(), nDoS);
+                LogPrintf("Peer %d sent us invalid header via cmpctblock\n", pfrom->id);
+                return true;
+            }
+        }
+
+        // If AcceptBlockHeader returned true, it set pindex
+        assert(pindex);
+        UpdateBlockAvailability(pfrom->GetId(), pindex->GetBlockHash());
+
+        std::map<uint256, pair<NodeId, list<QueuedBlock>::iterator> >::iterator blockInFlightIt = mapBlocksInFlight.find(pindex->GetBlockHash());
+        bool fAlreadyInFlight = blockInFlightIt != mapBlocksInFlight.end();
+
+        if (pindex->nStatus & BLOCK_HAVE_DATA) // Nothing to do here
+            return true;
+
+        if (pindex->nChainWork <= chainActive.Tip()->nChainWork || // We know something better
+                pindex->nTx != 0) { // We had this block at some point, but pruned it
+            if (fAlreadyInFlight) {
+                // We requested this block for some reason, but our mempool will probably be useless
+                // so we just grab the block via normal getdata
+                std::vector<CInv> vInv(1);
+                vInv[0] = CInv(MSG_BLOCK, cmpctblock.header.GetHash());
+                pfrom->PushMessage(NetMsgType::GETDATA, vInv);
+                return true;
+            }
+        }
+
+        // If we're not close to tip yet, give up and let parallel block fetch work its magic
+        if (!fAlreadyInFlight && !CanDirectFetch(chainparams.GetConsensus()))
+            return true;
+
+        CNodeState *nodestate = State(pfrom->GetId());
+
+        // We want to be a bit conservative just to be extra careful about DoS
+        // possibilities in compact block processing...
+        if (pindex->nHeight <= chainActive.Height() + 2) {
+            if ((!fAlreadyInFlight && nodestate->nBlocksInFlight < MAX_BLOCKS_IN_TRANSIT_PER_PEER) ||
+                 (fAlreadyInFlight && blockInFlightIt->second.first == pfrom->GetId())) {
+                list<QueuedBlock>::iterator *queuedBlockIt = NULL;
+                if (!MarkBlockAsInFlight(pfrom->GetId(), pindex->GetBlockHash(), chainparams.GetConsensus(), pindex, &queuedBlockIt)) {
+                    if (!(*queuedBlockIt)->partialBlock)
+                        (*queuedBlockIt)->partialBlock.reset(new PartiallyDownloadedBlock(&mempool));
+                    else {
+                        // The block was already in flight using compact blocks from the same peer
+                        LogPrint("net", "Peer sent us compact block we were already syncing!\n");
+                        return true;
+                    }
+                }
+
+                PartiallyDownloadedBlock& partialBlock = *(*queuedBlockIt)->partialBlock;
+                ReadStatus status = partialBlock.InitData(cmpctblock);
+                if (status == READ_STATUS_INVALID) {
+                    MarkBlockAsReceived(pindex->GetBlockHash()); // Reset in-flight state in case of whitelist
+                    Misbehaving(pfrom->GetId(), 100);
+                    LogPrintf("Peer %d sent us invalid compact block\n", pfrom->id);
+                    return true;
+                } else if (status == READ_STATUS_FAILED) {
+                    // Duplicate txindexes, the block is now in-flight, so just request it
+                    std::vector<CInv> vInv(1);
+                    vInv[0] = CInv(MSG_BLOCK, cmpctblock.header.GetHash());
+                    pfrom->PushMessage(NetMsgType::GETDATA, vInv);
+                    return true;
+                }
+
+                BlockTransactionsRequest req;
+                for (size_t i = 0; i < cmpctblock.BlockTxCount(); i++) {
+                    if (!partialBlock.IsTxAvailable(i))
+                        req.indexes.push_back(i);
+                }
+                if (req.indexes.empty()) {
+                    // Dirty hack to jump to BLOCKTXN code (TODO: move message handling into their own functions)
+                    BlockTransactions txn;
+                    txn.blockhash = cmpctblock.header.GetHash();
+                    CDataStream blockTxnMsg(SER_NETWORK, PROTOCOL_VERSION);
+                    blockTxnMsg << txn;
+                    return ProcessMessage(pfrom, NetMsgType::BLOCKTXN, blockTxnMsg, nTimeReceived, chainparams);
+                } else {
+                    req.blockhash = pindex->GetBlockHash();
+                    pfrom->PushMessage(NetMsgType::GETBLOCKTXN, req);
+                }
+            }
+        } else {
+            if (fAlreadyInFlight) {
+                // We requested this block, but its far into the future, so our
+                // mempool will probably be useless - request the block normally
+                std::vector<CInv> vInv(1);
+                vInv[0] = CInv(MSG_BLOCK, cmpctblock.header.GetHash());
+                pfrom->PushMessage(NetMsgType::GETDATA, vInv);
+                return true;
+            } else {
+                // If this was an announce-cmpctblock, we want the same treatment as a header message
+                // Dirty hack to process as if it were just a headers message (TODO: move message handling into their own functions)
+                std::vector<CBlock> headers;
+                headers.push_back(cmpctblock.header);
+                CDataStream vHeadersMsg(SER_NETWORK, PROTOCOL_VERSION);
+                vHeadersMsg << headers;
+                return ProcessMessage(pfrom, NetMsgType::HEADERS, vHeadersMsg, nTimeReceived, chainparams);
+            }
+        }
+
+        CheckBlockIndex(chainparams.GetConsensus());
+    }
+
+    else if (strCommand == NetMsgType::BLOCKTXN && !fImporting && !fReindex) // Ignore blocks received while importing
+    {
+        BlockTransactions resp;
+        vRecv >> resp;
+
+        LOCK(cs_main);
+
+        map<uint256, pair<NodeId, list<QueuedBlock>::iterator> >::iterator it = mapBlocksInFlight.find(resp.blockhash);
+        if (it == mapBlocksInFlight.end() || !it->second.second->partialBlock ||
+                it->second.first != pfrom->GetId()) {
+            LogPrint("net", "Peer %d sent us block transactions for block we weren't expecting\n", pfrom->id);
+            return true;
+        }
+
+        PartiallyDownloadedBlock& partialBlock = *it->second.second->partialBlock;
+        CBlock block;
+        ReadStatus status = partialBlock.FillBlock(block, resp.txn);
+        if (status == READ_STATUS_INVALID) {
+            MarkBlockAsReceived(resp.blockhash); // Reset in-flight state in case of whitelist
+            Misbehaving(pfrom->GetId(), 100);
+            LogPrintf("Peer %d sent us invalid compact block/non-matching block transactions\n", pfrom->id);
+            return true;
+        } else if (status == READ_STATUS_FAILED) {
+            // Might have collided, fall back to getdata now :(
+            std::vector<CInv> invs;
+            invs.push_back(CInv(MSG_BLOCK, resp.blockhash));
+            pfrom->PushMessage(NetMsgType::GETDATA, invs);
+        } else {
+            CValidationState state;
+            ProcessNewBlock(state, chainparams, pfrom, &block, false, NULL);
+            int nDoS;
+            if (state.IsInvalid(nDoS)) {
+                assert (state.GetRejectCode() < REJECT_INTERNAL); // Blocks are never rejected with internal reject codes
+                pfrom->PushMessage(NetMsgType::REJECT, strCommand, (unsigned char)state.GetRejectCode(),
+                                   state.GetRejectReason().substr(0, MAX_REJECT_MESSAGE_LENGTH), block.GetHash());
+                if (nDoS > 0) {
+                    LOCK(cs_main);
+                    Misbehaving(pfrom->GetId(), nDoS);
+                }
+            }
+        }
+    }
+
+
     else if (strCommand == NetMsgType::HEADERS && !fImporting && !fReindex) // Ignore headers received while importing
     {
         std::vector<CBlockHeader> headers;
@@ -5290,10 +5574,10 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
             }
         }
 
-        if (pindexLast)
-            UpdateBlockAvailability(pfrom->GetId(), pindexLast->GetBlockHash());
+        assert(pindexLast);
+        UpdateBlockAvailability(pfrom->GetId(), pindexLast->GetBlockHash());
 
-        if (nCount == MAX_HEADERS_RESULTS && pindexLast && hasNewHeaders) {
+        if (nCount == MAX_HEADERS_RESULTS && hasNewHeaders) {
             // Headers message had its maximum size; the peer may have more headers.
             // TODO: optimize: if pindexLast is an ancestor of chainActive.Tip or pindexBestHeader, continue
             // from there instead.
@@ -5343,6 +5627,13 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv,
                             pindexLast->GetBlockHash().ToString(), pindexLast->nHeight);
                 }
                 if (vGetData.size() > 0) {
+                    if (nodestate->fProvidesHeaderAndIDs && vGetData.size() == 1 && mapBlocksInFlight.size() == 1 && pindexLast->pprev->IsValid(BLOCK_VALID_CHAIN)) {
+                        // We seem to be rather well-synced, so it appears pfrom was the first to provide us
+                        // with this block! Let's get them to announce using compact blocks in the future.
+                        MaybeSetPeerAsAnnouncingHeaderAndIDs(nodestate, pfrom);
+                        // In any case, we want to download using a compact block, not a regular one
+                        vGetData[0] = CInv(MSG_CMPCT_BLOCK, vGetData[0].hash);
+                    }
                     pfrom->PushMessage(NetMsgType::GETDATA, vGetData);
                 }
             }
@@ -5896,7 +6187,9 @@ bool SendMessages(CNode* pto)
             // add all to the inv queue.
             LOCK(pto->cs_inventory);
             vector<CBlock> vHeaders;
-            bool fRevertToInv = (!state.fPreferHeaders || pto->vBlockHashesToAnnounce.size() > MAX_BLOCKS_TO_ANNOUNCE);
+            bool fRevertToInv = ((!state.fPreferHeaders &&
+                                 (!state.fPreferHeaderAndIDs || pto->vBlockHashesToAnnounce.size() > 1)) ||
+                                pto->vBlockHashesToAnnounce.size() > MAX_BLOCKS_TO_ANNOUNCE);
             CBlockIndex *pBestIndex = NULL; // last header queued for delivery
             ProcessBlockAvailability(pto->id); // ensure pindexBestKnownBlock is up-to-date
 
@@ -5948,6 +6241,33 @@ bool SendMessages(CNode* pto)
                     }
                 }
             }
+            if (!fRevertToInv && !vHeaders.empty()) {
+                if (vHeaders.size() == 1 && state.fPreferHeaderAndIDs) {
+                    // We only send up to 1 block as header-and-ids, as otherwise
+                    // probably means we're doing an initial-ish-sync or they're slow
+                    LogPrint("net", "%s sending header-and-ids %s to peer %d\n", __func__,
+                            vHeaders.front().GetHash().ToString(), pto->id);
+                    //TODO: Shouldn't need to reload block from disk, but requires refactor
+                    CBlock block;
+                    assert(ReadBlockFromDisk(block, pBestIndex, consensusParams));
+                    CBlockHeaderAndShortTxIDs cmpctblock(block);
+                    pto->PushMessage(NetMsgType::CMPCTBLOCK, cmpctblock);
+                    state.pindexBestHeaderSent = pBestIndex;
+                } else if (state.fPreferHeaders) {
+                    if (vHeaders.size() > 1) {
+                        LogPrint("net", "%s: %u headers, range (%s, %s), to peer=%d\n", __func__,
+                                vHeaders.size(),
+                                vHeaders.front().GetHash().ToString(),
+                                vHeaders.back().GetHash().ToString(), pto->id);
+                    } else {
+                        LogPrint("net", "%s: sending header %s to peer=%d\n", __func__,
+                                vHeaders.front().GetHash().ToString(), pto->id);
+                    }
+                    pto->PushMessage(NetMsgType::HEADERS, vHeaders);
+                    state.pindexBestHeaderSent = pBestIndex;
+                } else
+                    fRevertToInv = true;
+            }
             if (fRevertToInv) {
                 // If falling back to using an inv, just try to inv the tip.
                 // The last entry in vBlockHashesToAnnounce was our tip at some point
@@ -5973,18 +6293,6 @@ bool SendMessages(CNode* pto)
                             pto->id, hashToAnnounce.ToString());
                     }
                 }
-            } else if (!vHeaders.empty()) {
-                if (vHeaders.size() > 1) {
-                    LogPrint("net", "%s: %u headers, range (%s, %s), to peer=%d\n", __func__,
-                            vHeaders.size(),
-                            vHeaders.front().GetHash().ToString(),
-                            vHeaders.back().GetHash().ToString(), pto->id);
-                } else {
-                    LogPrint("net", "%s: sending header %s to peer=%d\n", __func__,
-                            vHeaders.front().GetHash().ToString(), pto->id);
-                }
-                pto->PushMessage(NetMsgType::HEADERS, vHeaders);
-                state.pindexBestHeaderSent = pBestIndex;
             }
             pto->vBlockHashesToAnnounce.clear();
         }
diff --git a/src/main.h b/src/main.h
index a39ffbf56d..f004a29bb1 100644
--- a/src/main.h
+++ b/src/main.h
@@ -429,13 +429,13 @@ bool ReadBlockFromDisk(CBlock& block, const CBlockIndex* pindex, const Consensus
 /** Functions for validating blocks and updating the block tree */
 
 /** Context-independent validity checks */
-bool CheckBlockHeader(const CBlockHeader& block, CValidationState& state, const Consensus::Params& consensusParams, int64_t nAdjustedTime, bool fCheckPOW = true);
-bool CheckBlock(const CBlock& block, CValidationState& state, const Consensus::Params& consensusParams, int64_t nAdjustedTime, bool fCheckPOW = true, bool fCheckMerkleRoot = true);
+bool CheckBlockHeader(const CBlockHeader& block, CValidationState& state, const Consensus::Params& consensusParams, bool fCheckPOW = true);
+bool CheckBlock(const CBlock& block, CValidationState& state, const Consensus::Params& consensusParams, bool fCheckPOW = true, bool fCheckMerkleRoot = true);
 
 /** Context-dependent validity checks.
  *  By "context", we mean only the previous block headers, but not the UTXO
  *  set; UTXO-related validity checks are done in ConnectBlock(). */
-bool ContextualCheckBlockHeader(const CBlockHeader& block, CValidationState& state, const Consensus::Params& consensusParams, CBlockIndex* pindexPrev);
+bool ContextualCheckBlockHeader(const CBlockHeader& block, CValidationState& state, const Consensus::Params& consensusParams, CBlockIndex* pindexPrev, int64_t nAdjustedTime);
 bool ContextualCheckBlock(const CBlock& block, CValidationState& state, CBlockIndex *pindexPrev);
 
 /** Apply the effects of this block (with given index) on the UTXO set represented by coins.
diff --git a/src/net.cpp b/src/net.cpp
index 4eca3d75cc..336163a896 100644
--- a/src/net.cpp
+++ b/src/net.cpp
@@ -368,6 +368,16 @@ CNode* FindNode(const CService& addr)
     return NULL;
 }
 
+//TODO: This is used in only one place in main, and should be removed
+CNode* FindNode(const NodeId nodeid)
+{
+    LOCK(cs_vNodes);
+    BOOST_FOREACH(CNode* pnode, vNodes)
+        if (pnode->GetId() == nodeid)
+            return (pnode);
+    return NULL;
+}
+
 CNode* ConnectNode(CAddress addrConnect, const char *pszDest, bool fCountFailure)
 {
     if (pszDest == NULL) {
diff --git a/src/net.h b/src/net.h
index 67b95fe0e4..aa9b2c11a3 100644
--- a/src/net.h
+++ b/src/net.h
@@ -80,12 +80,15 @@ static const unsigned int DEFAULT_MISBEHAVING_BANTIME = 60 * 60 * 24;  // Defaul
 unsigned int ReceiveFloodSize();
 unsigned int SendBufferSize();
 
+typedef int NodeId;
+
 void AddOneShot(const std::string& strDest);
 void AddressCurrentlyConnected(const CService& addr);
 CNode* FindNode(const CNetAddr& ip);
 CNode* FindNode(const CSubNet& subNet);
 CNode* FindNode(const std::string& addrName);
 CNode* FindNode(const CService& ip);
+CNode* FindNode(const NodeId id); //TODO: Remove this
 bool OpenNetworkConnection(const CAddress& addrConnect, bool fCountFailure, CSemaphoreGrant *grantOutbound = NULL, const char *strDest = NULL, bool fOneShot = false);
 void MapPort(bool fUseUPnP);
 unsigned short GetListenPort();
@@ -94,8 +97,6 @@ void StartNode(boost::thread_group& threadGroup, CScheduler& scheduler);
 bool StopNode();
 void SocketSendData(CNode *pnode);
 
-typedef int NodeId;
-
 struct CombinerAll
 {
     typedef bool result_type;
diff --git a/src/protocol.cpp b/src/protocol.cpp
index 422ef6f636..2f90fb764c 100644
--- a/src/protocol.cpp
+++ b/src/protocol.cpp
@@ -35,6 +35,10 @@ const char *FILTERCLEAR="filterclear";
 const char *REJECT="reject";
 const char *SENDHEADERS="sendheaders";
 const char *FEEFILTER="feefilter";
+const char *SENDCMPCT="sendcmpct";
+const char *CMPCTBLOCK="cmpctblock";
+const char *GETBLOCKTXN="getblocktxn";
+const char *BLOCKTXN="blocktxn";
 };
 
 static const char* ppszTypeName[] =
@@ -42,7 +46,8 @@ static const char* ppszTypeName[] =
     "ERROR", // Should never occur
     NetMsgType::TX,
     NetMsgType::BLOCK,
-    "filtered block" // Should never occur
+    "filtered block", // Should never occur
+    "compact block" // Should never occur
 };
 
 /** All known message types. Keep this in the same order as the list of
@@ -70,7 +75,11 @@ const static std::string allNetMessageTypes[] = {
     NetMsgType::FILTERCLEAR,
     NetMsgType::REJECT,
     NetMsgType::SENDHEADERS,
-    NetMsgType::FEEFILTER
+    NetMsgType::FEEFILTER,
+    NetMsgType::SENDCMPCT,
+    NetMsgType::CMPCTBLOCK,
+    NetMsgType::GETBLOCKTXN,
+    NetMsgType::BLOCKTXN,
 };
 const static std::vector<std::string> allNetMessageTypesVec(allNetMessageTypes, allNetMessageTypes+ARRAYLEN(allNetMessageTypes));
 
diff --git a/src/protocol.h b/src/protocol.h
index ab0a581783..a72813e959 100644
--- a/src/protocol.h
+++ b/src/protocol.h
@@ -217,6 +217,32 @@ extern const char *SENDHEADERS;
  * @since protocol version 70013 as described by BIP133
  */
 extern const char *FEEFILTER;
+/**
+ * Contains a 1-byte bool and 8-byte LE version number.
+ * Indicates that a node is willing to provide blocks via "cmpctblock" messages.
+ * May indicate that a node prefers to receive new block announcements via a
+ * "cmpctblock" message rather than an "inv", depending on message contents.
+ * @since protocol version 70014 as described by BIP 152
+ */
+extern const char *SENDCMPCT;
+/**
+ * Contains a CBlockHeaderAndShortTxIDs object - providing a header and
+ * list of "short txids".
+ * @since protocol version 70014 as described by BIP 152
+ */
+extern const char *CMPCTBLOCK;
+/**
+ * Contains a BlockTransactionsRequest
+ * Peer should respond with "blocktxn" message.
+ * @since protocol version 70014 as described by BIP 152
+ */
+extern const char *GETBLOCKTXN;
+/**
+ * Contains a BlockTransactions.
+ * Sent in response to a "getblocktxn" message.
+ * @since protocol version 70014 as described by BIP 152
+ */
+extern const char *BLOCKTXN;
 };
 
 /* Get a vector of all valid message types (see above) */
@@ -315,9 +341,10 @@ public:
 enum {
     MSG_TX = 1,
     MSG_BLOCK,
-    // Nodes may always request a MSG_FILTERED_BLOCK in a getdata, however,
-    // MSG_FILTERED_BLOCK should not appear in any invs except as a part of getdata.
+    // Nodes may always request a MSG_FILTERED_BLOCK/MSG_CMPCT_BLOCK in a getdata, however,
+    // MSG_FILTERED_BLOCK/MSG_CMPCT_BLOCK should not appear in any invs except as a part of getdata.
     MSG_FILTERED_BLOCK,
+    MSG_CMPCT_BLOCK,
 };
 
 #endif // BITCOIN_PROTOCOL_H
diff --git a/src/serialize.h b/src/serialize.h
index 5c2db9d332..378ed39074 100644
--- a/src/serialize.h
+++ b/src/serialize.h
@@ -373,6 +373,7 @@ I ReadVarInt(Stream& is)
 
 #define FLATDATA(obj) REF(CFlatData((char*)&(obj), (char*)&(obj) + sizeof(obj)))
 #define VARINT(obj) REF(WrapVarInt(REF(obj)))
+#define COMPACTSIZE(obj) REF(CCompactSize(REF(obj)))
 #define LIMITED_STRING(obj,n) REF(LimitedString< n >(REF(obj)))
 
 /** 
@@ -443,6 +444,28 @@ public:
     }
 };
 
+class CCompactSize
+{
+protected:
+    uint64_t &n;
+public:
+    CCompactSize(uint64_t& nIn) : n(nIn) { }
+
+    unsigned int GetSerializeSize(int, int) const {
+        return GetSizeOfCompactSize(n);
+    }
+
+    template<typename Stream>
+    void Serialize(Stream &s, int, int) const {
+        WriteCompactSize<Stream>(s, n);
+    }
+
+    template<typename Stream>
+    void Unserialize(Stream& s, int, int) {
+        n = ReadCompactSize<Stream>(s);
+    }
+};
+
 template<size_t Limit>
 class LimitedString
 {
diff --git a/src/test/blockencodings_tests.cpp b/src/test/blockencodings_tests.cpp
new file mode 100644
index 0000000000..3884bf3fe3
--- /dev/null
+++ b/src/test/blockencodings_tests.cpp
@@ -0,0 +1,315 @@
+// Copyright (c) 2011-2015 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include "blockencodings.h"
+#include "consensus/merkle.h"
+#include "chainparams.h"
+#include "random.h"
+
+#include "test/test_bitcoin.h"
+
+#include <boost/test/unit_test.hpp>
+
+struct RegtestingSetup : public TestingSetup {
+    RegtestingSetup() : TestingSetup(CBaseChainParams::REGTEST) {}
+};
+
+BOOST_FIXTURE_TEST_SUITE(blockencodings_tests, RegtestingSetup)
+
+static CBlock BuildBlockTestCase() {
+    CBlock block;
+    CMutableTransaction tx;
+    tx.vin.resize(1);
+    tx.vin[0].scriptSig.resize(10);
+    tx.vout.resize(1);
+    tx.vout[0].nValue = 42;
+
+    block.vtx.resize(3);
+    block.vtx[0] = tx;
+    block.nVersion = 42;
+    block.hashPrevBlock = GetRandHash();
+    block.nBits = 0x207fffff;
+
+    tx.vin[0].prevout.hash = GetRandHash();
+    tx.vin[0].prevout.n = 0;
+    block.vtx[1] = tx;
+
+    tx.vin.resize(10);
+    for (size_t i = 0; i < tx.vin.size(); i++) {
+        tx.vin[i].prevout.hash = GetRandHash();
+        tx.vin[i].prevout.n = 0;
+    }
+    block.vtx[2] = tx;
+
+    bool mutated;
+    block.hashMerkleRoot = BlockMerkleRoot(block, &mutated);
+    assert(!mutated);
+    while (!CheckProofOfWork(block.GetHash(), block.nBits, Params().GetConsensus())) ++block.nNonce;
+    return block;
+}
+
+// Number of shared use_counts we expect for a tx we havent touched
+// == 2 (mempool + our copy from the GetSharedTx call)
+#define SHARED_TX_OFFSET 2
+
+BOOST_AUTO_TEST_CASE(SimpleRoundTripTest)
+{
+    CTxMemPool pool(CFeeRate(0));
+    TestMemPoolEntryHelper entry;
+    CBlock block(BuildBlockTestCase());
+
+    pool.addUnchecked(block.vtx[2].GetHash(), entry.FromTx(block.vtx[2]));
+    BOOST_CHECK_EQUAL(pool.mapTx.find(block.vtx[2].GetHash())->GetSharedTx().use_count(), SHARED_TX_OFFSET + 0);
+
+    // Do a simple ShortTxIDs RT
+    {
+        CBlockHeaderAndShortTxIDs shortIDs(block);
+
+        CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
+        stream << shortIDs;
+
+        CBlockHeaderAndShortTxIDs shortIDs2;
+        stream >> shortIDs2;
+
+        PartiallyDownloadedBlock partialBlock(&pool);
+        BOOST_CHECK(partialBlock.InitData(shortIDs2) == READ_STATUS_OK);
+        BOOST_CHECK( partialBlock.IsTxAvailable(0));
+        BOOST_CHECK(!partialBlock.IsTxAvailable(1));
+        BOOST_CHECK( partialBlock.IsTxAvailable(2));
+
+        BOOST_CHECK_EQUAL(pool.mapTx.find(block.vtx[2].GetHash())->GetSharedTx().use_count(), SHARED_TX_OFFSET + 1);
+
+        std::list<CTransaction> removed;
+        pool.removeRecursive(block.vtx[2], removed);
+        BOOST_CHECK_EQUAL(removed.size(), 1);
+
+        CBlock block2;
+        std::vector<CTransaction> vtx_missing;
+        BOOST_CHECK(partialBlock.FillBlock(block2, vtx_missing) == READ_STATUS_INVALID); // No transactions
+
+        vtx_missing.push_back(block.vtx[2]); // Wrong transaction
+        partialBlock.FillBlock(block2, vtx_missing); // Current implementation doesn't check txn here, but don't require that
+        bool mutated;
+        BOOST_CHECK(block.hashMerkleRoot != BlockMerkleRoot(block2, &mutated));
+
+        vtx_missing[0] = block.vtx[1];
+        CBlock block3;
+        BOOST_CHECK(partialBlock.FillBlock(block3, vtx_missing) == READ_STATUS_OK);
+        BOOST_CHECK_EQUAL(block.GetHash().ToString(), block3.GetHash().ToString());
+        BOOST_CHECK_EQUAL(block.hashMerkleRoot.ToString(), BlockMerkleRoot(block3, &mutated).ToString());
+        BOOST_CHECK(!mutated);
+    }
+}
+
+class TestHeaderAndShortIDs {
+    // Utility to encode custom CBlockHeaderAndShortTxIDs
+public:
+    CBlockHeader header;
+    uint64_t nonce;
+    std::vector<uint64_t> shorttxids;
+    std::vector<PrefilledTransaction> prefilledtxn;
+
+    TestHeaderAndShortIDs(const CBlockHeaderAndShortTxIDs& orig) {
+        CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
+        stream << orig;
+        stream >> *this;
+    }
+    TestHeaderAndShortIDs(const CBlock& block) :
+        TestHeaderAndShortIDs(CBlockHeaderAndShortTxIDs(block)) {}
+
+    uint64_t GetShortID(const uint256& txhash) const {
+        CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
+        stream << *this;
+        CBlockHeaderAndShortTxIDs base;
+        stream >> base;
+        return base.GetShortID(txhash);
+    }
+
+    ADD_SERIALIZE_METHODS;
+
+    template <typename Stream, typename Operation>
+    inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
+        READWRITE(header);
+        READWRITE(nonce);
+        size_t shorttxids_size = shorttxids.size();
+        READWRITE(VARINT(shorttxids_size));
+        shorttxids.resize(shorttxids_size);
+        for (size_t i = 0; i < shorttxids.size(); i++) {
+            uint32_t lsb = shorttxids[i] & 0xffffffff;
+            uint16_t msb = (shorttxids[i] >> 32) & 0xffff;
+            READWRITE(lsb);
+            READWRITE(msb);
+            shorttxids[i] = (uint64_t(msb) << 32) | uint64_t(lsb);
+        }
+        READWRITE(prefilledtxn);
+    }
+};
+
+BOOST_AUTO_TEST_CASE(NonCoinbasePreforwardRTTest)
+{
+    CTxMemPool pool(CFeeRate(0));
+    TestMemPoolEntryHelper entry;
+    CBlock block(BuildBlockTestCase());
+
+    pool.addUnchecked(block.vtx[2].GetHash(), entry.FromTx(block.vtx[2]));
+    BOOST_CHECK_EQUAL(pool.mapTx.find(block.vtx[2].GetHash())->GetSharedTx().use_count(), SHARED_TX_OFFSET + 0);
+
+    // Test with pre-forwarding tx 1, but not coinbase
+    {
+        TestHeaderAndShortIDs shortIDs(block);
+        shortIDs.prefilledtxn.resize(1);
+        shortIDs.prefilledtxn[0] = {1, block.vtx[1]};
+        shortIDs.shorttxids.resize(2);
+        shortIDs.shorttxids[0] = shortIDs.GetShortID(block.vtx[0].GetHash());
+        shortIDs.shorttxids[1] = shortIDs.GetShortID(block.vtx[2].GetHash());
+
+        CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
+        stream << shortIDs;
+
+        CBlockHeaderAndShortTxIDs shortIDs2;
+        stream >> shortIDs2;
+
+        PartiallyDownloadedBlock partialBlock(&pool);
+        BOOST_CHECK(partialBlock.InitData(shortIDs2) == READ_STATUS_OK);
+        BOOST_CHECK(!partialBlock.IsTxAvailable(0));
+        BOOST_CHECK( partialBlock.IsTxAvailable(1));
+        BOOST_CHECK( partialBlock.IsTxAvailable(2));
+
+        BOOST_CHECK_EQUAL(pool.mapTx.find(block.vtx[2].GetHash())->GetSharedTx().use_count(), SHARED_TX_OFFSET + 1);
+
+        CBlock block2;
+        std::vector<CTransaction> vtx_missing;
+        BOOST_CHECK(partialBlock.FillBlock(block2, vtx_missing) == READ_STATUS_INVALID); // No transactions
+
+        vtx_missing.push_back(block.vtx[1]); // Wrong transaction
+        partialBlock.FillBlock(block2, vtx_missing); // Current implementation doesn't check txn here, but don't require that
+        bool mutated;
+        BOOST_CHECK(block.hashMerkleRoot != BlockMerkleRoot(block2, &mutated));
+
+        vtx_missing[0] = block.vtx[0];
+        CBlock block3;
+        BOOST_CHECK(partialBlock.FillBlock(block3, vtx_missing) == READ_STATUS_OK);
+        BOOST_CHECK_EQUAL(block.GetHash().ToString(), block3.GetHash().ToString());
+        BOOST_CHECK_EQUAL(block.hashMerkleRoot.ToString(), BlockMerkleRoot(block3, &mutated).ToString());
+        BOOST_CHECK(!mutated);
+
+        BOOST_CHECK_EQUAL(pool.mapTx.find(block.vtx[2].GetHash())->GetSharedTx().use_count(), SHARED_TX_OFFSET + 1);
+    }
+    BOOST_CHECK_EQUAL(pool.mapTx.find(block.vtx[2].GetHash())->GetSharedTx().use_count(), SHARED_TX_OFFSET + 0);
+}
+
+BOOST_AUTO_TEST_CASE(SufficientPreforwardRTTest)
+{
+    CTxMemPool pool(CFeeRate(0));
+    TestMemPoolEntryHelper entry;
+    CBlock block(BuildBlockTestCase());
+
+    pool.addUnchecked(block.vtx[1].GetHash(), entry.FromTx(block.vtx[1]));
+    BOOST_CHECK_EQUAL(pool.mapTx.find(block.vtx[1].GetHash())->GetSharedTx().use_count(), SHARED_TX_OFFSET + 0);
+
+    // Test with pre-forwarding coinbase + tx 2 with tx 1 in mempool
+    {
+        TestHeaderAndShortIDs shortIDs(block);
+        shortIDs.prefilledtxn.resize(2);
+        shortIDs.prefilledtxn[0] = {0, block.vtx[0]};
+        shortIDs.prefilledtxn[1] = {1, block.vtx[2]}; // id == 1 as it is 1 after index 1
+        shortIDs.shorttxids.resize(1);
+        shortIDs.shorttxids[0] = shortIDs.GetShortID(block.vtx[1].GetHash());
+
+        CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
+        stream << shortIDs;
+
+        CBlockHeaderAndShortTxIDs shortIDs2;
+        stream >> shortIDs2;
+
+        PartiallyDownloadedBlock partialBlock(&pool);
+        BOOST_CHECK(partialBlock.InitData(shortIDs2) == READ_STATUS_OK);
+        BOOST_CHECK( partialBlock.IsTxAvailable(0));
+        BOOST_CHECK( partialBlock.IsTxAvailable(1));
+        BOOST_CHECK( partialBlock.IsTxAvailable(2));
+
+        BOOST_CHECK_EQUAL(pool.mapTx.find(block.vtx[1].GetHash())->GetSharedTx().use_count(), SHARED_TX_OFFSET + 1);
+
+        CBlock block2;
+        std::vector<CTransaction> vtx_missing;
+        BOOST_CHECK(partialBlock.FillBlock(block2, vtx_missing) == READ_STATUS_OK);
+        BOOST_CHECK_EQUAL(block.GetHash().ToString(), block2.GetHash().ToString());
+        bool mutated;
+        BOOST_CHECK_EQUAL(block.hashMerkleRoot.ToString(), BlockMerkleRoot(block2, &mutated).ToString());
+        BOOST_CHECK(!mutated);
+
+        BOOST_CHECK_EQUAL(pool.mapTx.find(block.vtx[1].GetHash())->GetSharedTx().use_count(), SHARED_TX_OFFSET + 1);
+    }
+    BOOST_CHECK_EQUAL(pool.mapTx.find(block.vtx[1].GetHash())->GetSharedTx().use_count(), SHARED_TX_OFFSET + 0);
+}
+
+BOOST_AUTO_TEST_CASE(EmptyBlockRoundTripTest)
+{
+    CTxMemPool pool(CFeeRate(0));
+    CMutableTransaction coinbase;
+    coinbase.vin.resize(1);
+    coinbase.vin[0].scriptSig.resize(10);
+    coinbase.vout.resize(1);
+    coinbase.vout[0].nValue = 42;
+
+    CBlock block;
+    block.vtx.resize(1);
+    block.vtx[0] = coinbase;
+    block.nVersion = 42;
+    block.hashPrevBlock = GetRandHash();
+    block.nBits = 0x207fffff;
+
+    bool mutated;
+    block.hashMerkleRoot = BlockMerkleRoot(block, &mutated);
+    assert(!mutated);
+    while (!CheckProofOfWork(block.GetHash(), block.nBits, Params().GetConsensus())) ++block.nNonce;
+
+    // Test simple header round-trip with only coinbase
+    {
+        CBlockHeaderAndShortTxIDs shortIDs(block);
+
+        CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
+        stream << shortIDs;
+
+        CBlockHeaderAndShortTxIDs shortIDs2;
+        stream >> shortIDs2;
+
+        PartiallyDownloadedBlock partialBlock(&pool);
+        BOOST_CHECK(partialBlock.InitData(shortIDs2) == READ_STATUS_OK);
+        BOOST_CHECK(partialBlock.IsTxAvailable(0));
+
+        CBlock block2;
+        std::vector<CTransaction> vtx_missing;
+        BOOST_CHECK(partialBlock.FillBlock(block2, vtx_missing) == READ_STATUS_OK);
+        BOOST_CHECK_EQUAL(block.GetHash().ToString(), block2.GetHash().ToString());
+        bool mutated;
+        BOOST_CHECK_EQUAL(block.hashMerkleRoot.ToString(), BlockMerkleRoot(block2, &mutated).ToString());
+        BOOST_CHECK(!mutated);
+    }
+}
+
+BOOST_AUTO_TEST_CASE(TransactionsRequestSerializationTest) {
+    BlockTransactionsRequest req1;
+    req1.blockhash = GetRandHash();
+    req1.indexes.resize(4);
+    req1.indexes[0] = 0;
+    req1.indexes[1] = 1;
+    req1.indexes[2] = 3;
+    req1.indexes[3] = 4;
+
+    CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
+    stream << req1;
+
+    BlockTransactionsRequest req2;
+    stream >> req2;
+
+    BOOST_CHECK_EQUAL(req1.blockhash.ToString(), req2.blockhash.ToString());
+    BOOST_CHECK_EQUAL(req1.indexes.size(), req2.indexes.size());
+    BOOST_CHECK_EQUAL(req1.indexes[0], req2.indexes[0]);
+    BOOST_CHECK_EQUAL(req1.indexes[1], req2.indexes[1]);
+    BOOST_CHECK_EQUAL(req1.indexes[2], req2.indexes[2]);
+    BOOST_CHECK_EQUAL(req1.indexes[3], req2.indexes[3]);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/test_bitcoin.cpp b/src/test/test_bitcoin.cpp
index 3dc59ddd08..1f3b198800 100644
--- a/src/test/test_bitcoin.cpp
+++ b/src/test/test_bitcoin.cpp
@@ -127,7 +127,11 @@ TestChain100Setup::~TestChain100Setup()
 
 CTxMemPoolEntry TestMemPoolEntryHelper::FromTx(CMutableTransaction &tx, CTxMemPool *pool) {
     CTransaction txn(tx);
-    bool hasNoDependencies = pool ? pool->HasNoInputsOf(tx) : hadNoDependencies;
+    return FromTx(txn, pool);
+}
+
+CTxMemPoolEntry TestMemPoolEntryHelper::FromTx(CTransaction &txn, CTxMemPool *pool) {
+    bool hasNoDependencies = pool ? pool->HasNoInputsOf(txn) : hadNoDependencies;
     // Hack to assume either its completely dependent on other mempool txs or not at all
     CAmount inChainValue = hasNoDependencies ? txn.GetValueOut() : 0;
 
diff --git a/src/test/test_bitcoin.h b/src/test/test_bitcoin.h
index 57f66f6c6d..78b87e7109 100644
--- a/src/test/test_bitcoin.h
+++ b/src/test/test_bitcoin.h
@@ -78,6 +78,7 @@ struct TestMemPoolEntryHelper
         hadNoDependencies(false), spendsCoinbase(false), sigOpCount(1) { }
     
     CTxMemPoolEntry FromTx(CMutableTransaction &tx, CTxMemPool *pool = NULL);
+    CTxMemPoolEntry FromTx(CTransaction &tx, CTxMemPool *pool = NULL);
 
     // Change the default value
     TestMemPoolEntryHelper &Fee(CAmount _fee) { nFee = _fee; return *this; }
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index 18c54b08bc..ead28546de 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -438,6 +438,9 @@ bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry,
     totalTxSize += entry.GetTxSize();
     minerPolicyEstimator->processTransaction(entry, fCurrentEstimate);
 
+    vTxHashes.emplace_back(hash, newit);
+    newit->vTxHashesIdx = vTxHashes.size() - 1;
+
     return true;
 }
 
@@ -447,6 +450,15 @@ void CTxMemPool::removeUnchecked(txiter it)
     BOOST_FOREACH(const CTxIn& txin, it->GetTx().vin)
         mapNextTx.erase(txin.prevout);
 
+    if (vTxHashes.size() > 1) {
+        vTxHashes[it->vTxHashesIdx] = std::move(vTxHashes.back());
+        vTxHashes[it->vTxHashesIdx].second->vTxHashesIdx = it->vTxHashesIdx;
+        vTxHashes.pop_back();
+        if (vTxHashes.size() * 2 < vTxHashes.capacity())
+            vTxHashes.shrink_to_fit();
+    } else
+        vTxHashes.clear();
+
     totalTxSize -= it->GetTxSize();
     cachedInnerUsage -= it->DynamicMemoryUsage();
     cachedInnerUsage -= memusage::DynamicUsage(mapLinks[it].parents) + memusage::DynamicUsage(mapLinks[it].children);
@@ -965,7 +977,7 @@ bool CCoinsViewMemPool::HaveCoins(const uint256 &txid) const {
 size_t CTxMemPool::DynamicMemoryUsage() const {
     LOCK(cs);
     // Estimate the overhead of mapTx to be 15 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
-    return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 15 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(mapLinks) + cachedInnerUsage;
+    return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 15 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(mapLinks) + memusage::DynamicUsage(vTxHashes) + cachedInnerUsage;
 }
 
 void CTxMemPool::RemoveStaged(setEntries &stage, bool updateDescendants) {
diff --git a/src/txmempool.h b/src/txmempool.h
index f0e9b2e2c6..d6d0d72ff5 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -150,6 +150,8 @@ public:
     uint64_t GetSizeWithAncestors() const { return nSizeWithAncestors; }
     CAmount GetModFeesWithAncestors() const { return nModFeesWithAncestors; }
     unsigned int GetSigOpCountWithAncestors() const { return nSigOpCountWithAncestors; }
+
+    mutable size_t vTxHashesIdx; //!< Index in mempool's vTxHashes
 };
 
 // Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index.
@@ -457,7 +459,10 @@ public:
 
     mutable CCriticalSection cs;
     indexed_transaction_set mapTx;
+
     typedef indexed_transaction_set::nth_index<0>::type::iterator txiter;
+    std::vector<std::pair<uint256, txiter> > vTxHashes; //!< All tx hashes/entries in mapTx, in random order
+
     struct CompareIteratorByHash {
         bool operator()(const txiter &a, const txiter &b) const {
             return a->GetTx().GetHash() < b->GetTx().GetHash();
diff --git a/src/version.h b/src/version.h
index 0e1d8a63ce..68ccd6d378 100644
--- a/src/version.h
+++ b/src/version.h
@@ -9,7 +9,7 @@
  * network protocol versioning
  */
 
-static const int PROTOCOL_VERSION = 70013;
+static const int PROTOCOL_VERSION = 70014;
 
 //! initial proto version, to be increased after version/verack negotiation
 static const int INIT_PROTO_VERSION = 209;
@@ -39,4 +39,7 @@ static const int SENDHEADERS_VERSION = 70012;
 //! "feefilter" tells peers to filter invs to you by fee starts with this version
 static const int FEEFILTER_VERSION = 70013;
 
+//! shord-id-based block download starts with this version
+static const int SHORT_IDS_BLOCKS_VERSION = 70014;
+
 #endif // BITCOIN_VERSION_H