Merge pull request #5199

1ec900a Remove broken+useless lock/unlock log prints (Matt Corallo)
352ed22 Add merkle blocks test (Matt Corallo)
59ed61b Add RPC call to generate and verify merkle blocks (Matt Corallo)
30da90d Add CMerkleBlock constructor for tx set + block and an empty one (Matt Corallo)

9 files changed, 238 insertions, 5 deletions

diff --git a/qa/pull-tester/rpc-tests.sh b/qa/pull-tester/rpc-tests.sh
index 053e8b8a7f..dd2f8d4e5e 100755
--- a/qa/pull-tester/rpc-tests.sh
+++ b/qa/pull-tester/rpc-tests.sh
@@ -28,6 +28,7 @@ testScripts=(
     'httpbasics.py'
     'zapwallettxes.py'
     'proxy_test.py'
+    'merkle_blocks.py'
 #    'forknotify.py'
 );
 if [ "x${ENABLE_BITCOIND}${ENABLE_UTILS}${ENABLE_WALLET}" = "x111" ]; then
diff --git a/qa/rpc-tests/merkle_blocks.py b/qa/rpc-tests/merkle_blocks.py
new file mode 100755
index 0000000000..a143d21a21
--- /dev/null
+++ b/qa/rpc-tests/merkle_blocks.py
@@ -0,0 +1,90 @@
+#!/usr/bin/env python2
+# Copyright (c) 2014 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 merkleblock fetch/validation
+#
+
+from test_framework import BitcoinTestFramework
+from bitcoinrpc.authproxy import AuthServiceProxy, JSONRPCException
+from util import *
+import os
+import shutil
+
+class MerkleBlockTest(BitcoinTestFramework):
+
+    def setup_chain(self):
+        print("Initializing test directory "+self.options.tmpdir)
+        initialize_chain_clean(self.options.tmpdir, 4)
+
+    def setup_network(self):
+        self.nodes = []
+        # Nodes 0/1 are "wallet" nodes
+        self.nodes.append(start_node(0, self.options.tmpdir, ["-debug"]))
+        self.nodes.append(start_node(1, self.options.tmpdir, ["-debug"]))
+        # Nodes 2/3 are used for testing
+        self.nodes.append(start_node(2, self.options.tmpdir, ["-debug"]))
+        self.nodes.append(start_node(3, self.options.tmpdir, ["-debug", "-txindex"]))
+        connect_nodes(self.nodes[0], 1)
+        connect_nodes(self.nodes[0], 2)
+        connect_nodes(self.nodes[0], 3)
+
+        self.is_network_split = False
+        self.sync_all()
+
+    def run_test(self):
+        print "Mining blocks..."
+        self.nodes[0].generate(105)
+        self.sync_all()
+
+        chain_height = self.nodes[1].getblockcount()
+        assert_equal(chain_height, 105)
+        assert_equal(self.nodes[1].getbalance(), 0)
+        assert_equal(self.nodes[2].getbalance(), 0)
+
+        node0utxos = self.nodes[0].listunspent(1)
+        tx1 = self.nodes[0].createrawtransaction([node0utxos.pop()], {self.nodes[1].getnewaddress(): 50})
+        txid1 = self.nodes[0].sendrawtransaction(self.nodes[0].signrawtransaction(tx1)["hex"])
+        tx2 = self.nodes[0].createrawtransaction([node0utxos.pop()], {self.nodes[1].getnewaddress(): 50})
+        txid2 = self.nodes[0].sendrawtransaction(self.nodes[0].signrawtransaction(tx2)["hex"])
+        assert_raises(JSONRPCException, self.nodes[0].gettxoutproof, [txid1])
+
+        self.nodes[0].generate(1)
+        blockhash = self.nodes[0].getblockhash(chain_height + 1)
+        self.sync_all()
+
+        txlist = []
+        blocktxn = self.nodes[0].getblock(blockhash, True)["tx"]
+        txlist.append(blocktxn[1])
+        txlist.append(blocktxn[2])
+
+        assert_equal(self.nodes[2].verifytxoutproof(self.nodes[2].gettxoutproof([txid1])), [txid1])
+        assert_equal(self.nodes[2].verifytxoutproof(self.nodes[2].gettxoutproof([txid1, txid2])), txlist)
+        assert_equal(self.nodes[2].verifytxoutproof(self.nodes[2].gettxoutproof([txid1, txid2], blockhash)), txlist)
+
+        txin_spent = self.nodes[1].listunspent(1).pop()
+        tx3 = self.nodes[1].createrawtransaction([txin_spent], {self.nodes[0].getnewaddress(): 50})
+        self.nodes[0].sendrawtransaction(self.nodes[1].signrawtransaction(tx3)["hex"])
+        self.nodes[0].generate(1)
+        self.sync_all()
+
+        txid_spent = txin_spent["txid"]
+        txid_unspent = txid1 if txin_spent["txid"] != txid1 else txid2
+
+        # We cant find the block from a fully-spent tx
+        assert_raises(JSONRPCException, self.nodes[2].gettxoutproof, [txid_spent])
+        # ...but we can if we specify the block
+        assert_equal(self.nodes[2].verifytxoutproof(self.nodes[2].gettxoutproof([txid_spent], blockhash)), [txid_spent])
+        # ...or if the first tx is not fully-spent
+        assert_equal(self.nodes[2].verifytxoutproof(self.nodes[2].gettxoutproof([txid_unspent])), [txid_unspent])
+        try:
+            assert_equal(self.nodes[2].verifytxoutproof(self.nodes[2].gettxoutproof([txid1, txid2])), txlist)
+        except JSONRPCException:
+            assert_equal(self.nodes[2].verifytxoutproof(self.nodes[2].gettxoutproof([txid2, txid1])), txlist)
+        # ...or if we have a -txindex
+        assert_equal(self.nodes[2].verifytxoutproof(self.nodes[3].gettxoutproof([txid_spent])), [txid_spent])
+
+if __name__ == '__main__':
+    MerkleBlockTest().main()
diff --git a/src/merkleblock.cpp b/src/merkleblock.cpp
index c48d8cd508..dc87d0377a 100644
--- a/src/merkleblock.cpp
+++ b/src/merkleblock.cpp
@@ -37,6 +37,29 @@ CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter& filter)
     txn = CPartialMerkleTree(vHashes, vMatch);
 }
 
+CMerkleBlock::CMerkleBlock(const CBlock& block, const std::set<uint256>& txids)
+{
+    header = block.GetBlockHeader();
+
+    vector<bool> vMatch;
+    vector<uint256> vHashes;
+
+    vMatch.reserve(block.vtx.size());
+    vHashes.reserve(block.vtx.size());
+
+    for (unsigned int i = 0; i < block.vtx.size(); i++)
+    {
+        const uint256& hash = block.vtx[i].GetHash();
+        if (txids.count(hash))
+            vMatch.push_back(true);
+        else
+            vMatch.push_back(false);
+        vHashes.push_back(hash);
+    }
+
+    txn = CPartialMerkleTree(vHashes, vMatch);
+}
+
 uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid) {
     if (height == 0) {
         // hash at height 0 is the txids themself
diff --git a/src/merkleblock.h b/src/merkleblock.h
index 52c914967f..d90face17c 100644
--- a/src/merkleblock.h
+++ b/src/merkleblock.h
@@ -139,6 +139,11 @@ public:
      */
     CMerkleBlock(const CBlock& block, CBloomFilter& filter);
 
+    // Create from a CBlock, matching the txids in the set
+    CMerkleBlock(const CBlock& block, const std::set<uint256>& txids);
+
+    CMerkleBlock() {}
+
     ADD_SERIALIZE_METHODS;
 
     template <typename Stream, typename Operation>
diff --git a/src/rpcclient.cpp b/src/rpcclient.cpp
index 428e1049dc..ad676f9edc 100644
--- a/src/rpcclient.cpp
+++ b/src/rpcclient.cpp
@@ -79,6 +79,7 @@ static const CRPCConvertParam vRPCConvertParams[] =
     { "sendrawtransaction", 1 },
     { "gettxout", 1 },
     { "gettxout", 2 },
+    { "gettxoutproof", 0 },
     { "lockunspent", 0 },
     { "lockunspent", 1 },
     { "importprivkey", 2 },
diff --git a/src/rpcrawtransaction.cpp b/src/rpcrawtransaction.cpp
index 8393a8502e..1e13f5dbba 100644
--- a/src/rpcrawtransaction.cpp
+++ b/src/rpcrawtransaction.cpp
@@ -9,6 +9,7 @@
 #include "init.h"
 #include "keystore.h"
 #include "main.h"
+#include "merkleblock.h"
 #include "net.h"
 #include "rpcserver.h"
 #include "script/script.h"
@@ -193,6 +194,119 @@ Value getrawtransaction(const Array& params, bool fHelp)
     return result;
 }
 
+Value gettxoutproof(const Array& params, bool fHelp)
+{
+    if (fHelp || (params.size() != 1 && params.size() != 2))
+        throw runtime_error(
+            "gettxoutproof [\"txid\",...] ( blockhash )\n"
+            "\nReturns a hex-encoded proof that \"txid\" was included in a block.\n"
+            "\nNOTE: By default this function only works sometimes. This is when there is an\n"
+            "unspent output in the utxo for this transaction. To make it always work,\n"
+            "you need to maintain a transaction index, using the -txindex command line option or\n"
+            "specify the block in which the transaction is included in manually (by blockhash).\n"
+            "\nReturn the raw transaction data.\n"
+            "\nArguments:\n"
+            "1. \"txids\"       (string) A json array of txids to filter\n"
+            "    [\n"
+            "      \"txid\"     (string) A transaction hash\n"
+            "      ,...\n"
+            "    ]\n"
+            "2. \"block hash\"  (string, optional) If specified, looks for txid in the block with this hash\n"
+            "\nResult:\n"
+            "\"data\"           (string) A string that is a serialized, hex-encoded data for the proof.\n"
+        );
+
+    set<uint256> setTxids;
+    uint256 oneTxid;
+    Array txids = params[0].get_array();
+    BOOST_FOREACH(Value& txid, txids) {
+        if (txid.get_str().length() != 64 || !IsHex(txid.get_str()))
+            throw JSONRPCError(RPC_INVALID_PARAMETER, string("Invalid txid ")+txid.get_str());
+        uint256 hash(uint256S(txid.get_str()));
+        if (setTxids.count(hash))
+            throw JSONRPCError(RPC_INVALID_PARAMETER, string("Invalid parameter, duplicated txid: ")+txid.get_str());
+       setTxids.insert(hash);
+       oneTxid = hash;
+    }
+
+    LOCK(cs_main);
+
+    CBlockIndex* pblockindex = NULL;
+
+    uint256 hashBlock;
+    if (params.size() > 1)
+    {
+        hashBlock = uint256S(params[1].get_str());
+        if (!mapBlockIndex.count(hashBlock))
+            throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, "Block not found");
+        pblockindex = mapBlockIndex[hashBlock];
+    } else {
+        CCoins coins;
+        if (pcoinsTip->GetCoins(oneTxid, coins) && coins.nHeight > 0 && coins.nHeight <= chainActive.Height())
+            pblockindex = chainActive[coins.nHeight];
+    }
+
+    if (pblockindex == NULL)
+    {
+        CTransaction tx;
+        if (!GetTransaction(oneTxid, tx, hashBlock, false) || hashBlock.IsNull())
+            throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, "Transaction not yet in block");
+        if (!mapBlockIndex.count(hashBlock))
+            throw JSONRPCError(RPC_INTERNAL_ERROR, "Transaction index corrupt");
+        pblockindex = mapBlockIndex[hashBlock];
+    }
+
+    CBlock block;
+    if(!ReadBlockFromDisk(block, pblockindex))
+        throw JSONRPCError(RPC_INTERNAL_ERROR, "Can't read block from disk");
+
+    unsigned int ntxFound = 0;
+    BOOST_FOREACH(const CTransaction&tx, block.vtx)
+        if (setTxids.count(tx.GetHash()))
+            ntxFound++;
+    if (ntxFound != setTxids.size())
+        throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, "(Not all) transactions not found in specified block");
+
+    CDataStream ssMB(SER_NETWORK, PROTOCOL_VERSION);
+    CMerkleBlock mb(block, setTxids);
+    ssMB << mb;
+    std::string strHex = HexStr(ssMB.begin(), ssMB.end());
+    return strHex;
+}
+
+Value verifytxoutproof(const Array& params, bool fHelp)
+{
+    if (fHelp || params.size() != 1)
+        throw runtime_error(
+            "verifytxoutproof \"proof\"\n"
+            "\nVerifies that a proof points to a transaction in a block, returning the transaction it commits to\n"
+            "and throwing an RPC error if the block is not in our best chain\n"
+            "\nArguments:\n"
+            "1. \"proof\"    (string, required) The hex-encoded proof generated by gettxoutproof\n"
+            "\nResult:\n"
+            "[\"txid\"]      (array, strings) The txid(s) which the proof commits to, or empty array if the proof is invalid\n"
+        );
+
+    CDataStream ssMB(ParseHexV(params[0], "proof"), SER_NETWORK, PROTOCOL_VERSION);
+    CMerkleBlock merkleBlock;
+    ssMB >> merkleBlock;
+
+    Array res;
+
+    vector<uint256> vMatch;
+    if (merkleBlock.txn.ExtractMatches(vMatch) != merkleBlock.header.hashMerkleRoot)
+        return res;
+
+    LOCK(cs_main);
+
+    if (!mapBlockIndex.count(merkleBlock.header.GetHash()) || !chainActive.Contains(mapBlockIndex[merkleBlock.header.GetHash()]))
+        throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, "Block not found in chain");
+
+    BOOST_FOREACH(const uint256& hash, vMatch)
+        res.push_back(hash.GetHex());
+    return res;
+}
+
 Value createrawtransaction(const Array& params, bool fHelp)
 {
     if (fHelp || params.size() != 2)
diff --git a/src/rpcserver.cpp b/src/rpcserver.cpp
index e2df41fe21..61dda9125b 100644
--- a/src/rpcserver.cpp
+++ b/src/rpcserver.cpp
@@ -293,6 +293,8 @@ static const CRPCCommand vRPCCommands[] =
     { "blockchain",         "getmempoolinfo",         &getmempoolinfo,         true  },
     { "blockchain",         "getrawmempool",          &getrawmempool,          true  },
     { "blockchain",         "gettxout",               &gettxout,               true  },
+    { "blockchain",         "gettxoutproof",          &gettxoutproof,          true  },
+    { "blockchain",         "verifytxoutproof",       &verifytxoutproof,       true  },
     { "blockchain",         "gettxoutsetinfo",        &gettxoutsetinfo,        true  },
     { "blockchain",         "verifychain",            &verifychain,            true  },
 
diff --git a/src/rpcserver.h b/src/rpcserver.h
index c3200d8c35..790104f8c9 100644
--- a/src/rpcserver.h
+++ b/src/rpcserver.h
@@ -218,6 +218,8 @@ extern json_spirit::Value decoderawtransaction(const json_spirit::Array& params,
 extern json_spirit::Value decodescript(const json_spirit::Array& params, bool fHelp);
 extern json_spirit::Value signrawtransaction(const json_spirit::Array& params, bool fHelp);
 extern json_spirit::Value sendrawtransaction(const json_spirit::Array& params, bool fHelp);
+extern json_spirit::Value gettxoutproof(const json_spirit::Array& params, bool fHelp);
+extern json_spirit::Value verifytxoutproof(const json_spirit::Array& params, bool fHelp);
 
 extern json_spirit::Value getblockcount(const json_spirit::Array& params, bool fHelp); // in rpcblockchain.cpp
 extern json_spirit::Value getbestblockhash(const json_spirit::Array& params, bool fHelp);
diff --git a/src/sync.cpp b/src/sync.cpp
index e28caee8e7..a422939964 100644
--- a/src/sync.cpp
+++ b/src/sync.cpp
@@ -86,7 +86,6 @@ static void push_lock(void* c, const CLockLocation& locklocation, bool fTry)
     if (lockstack.get() == NULL)
         lockstack.reset(new LockStack);
 
-    LogPrint("lock", "Locking: %s\n", locklocation.ToString());
     dd_mutex.lock();
 
     (*lockstack).push_back(std::make_pair(c, locklocation));
@@ -113,10 +112,6 @@ static void push_lock(void* c, const CLockLocation& locklocation, bool fTry)
 
 static void pop_lock()
 {
-    if (fDebug) {
-        const CLockLocation& locklocation = (*lockstack).rbegin()->second;
-        LogPrint("lock", "Unlocked: %s\n", locklocation.ToString());
-    }
     dd_mutex.lock();
     (*lockstack).pop_back();
     dd_mutex.unlock();