Do not store Merkle branches in the wallet.

Assume that when a wallet transaction has a valid block hash and transaction position
in it, the transaction is actually there. We're already trusting wallet data in a
much more fundamental way anyway.

To prevent backward compatibility issues, a new record is used for storing the
block locator in the wallet. Old wallets will see a wallet file synchronized up
to the genesis block, and rescan automatically.

12 files changed, 25 insertions, 73 deletions

diff --git a/doc/release-notes.md b/doc/release-notes.md
index a06075334a..bef9af60ef 100644
--- a/doc/release-notes.md
+++ b/doc/release-notes.md
@@ -105,6 +105,15 @@ In this version, it is only enforced for peers that send protocol versions
 removed. It is recommended to update SPV clients to check for the `NODE_BLOOM`
 service bit for nodes that report versions newer than 70011.
 
+Merkle branches removed from wallet
+-----------------------------------
+
+Previously, every wallet transaction stored a Merkle branch to prove its
+presence in blocks. This wasn't being used for more than an expensive
+sanity check. Since 0.12, these are no longer stored. When loading a
+0.12 wallet into an older version, it will automatically rescan to avoid
+failed checks.
+
 0.12.0 Change log
 =================
 
diff --git a/src/chainparams.cpp b/src/chainparams.cpp
index 9c843f6e7e..15b86cdda6 100644
--- a/src/chainparams.cpp
+++ b/src/chainparams.cpp
@@ -31,7 +31,7 @@ static CBlock CreateGenesisBlock(const char* pszTimestamp, const CScript& genesi
     genesis.nVersion = nVersion;
     genesis.vtx.push_back(txNew);
     genesis.hashPrevBlock.SetNull();
-    genesis.hashMerkleRoot = genesis.BuildMerkleTree();
+    genesis.hashMerkleRoot = genesis.ComputeMerkleRoot();
     return genesis;
 }
 
diff --git a/src/core_memusage.h b/src/core_memusage.h
index 711135bb44..a05f59ee0c 100644
--- a/src/core_memusage.h
+++ b/src/core_memusage.h
@@ -48,7 +48,7 @@ static inline size_t RecursiveDynamicUsage(const CMutableTransaction& tx) {
 }
 
 static inline size_t RecursiveDynamicUsage(const CBlock& block) {
-    size_t mem = memusage::DynamicUsage(block.vtx) + memusage::DynamicUsage(block.vMerkleTree);
+    size_t mem = memusage::DynamicUsage(block.vtx);
     for (std::vector<CTransaction>::const_iterator it = block.vtx.begin(); it != block.vtx.end(); it++) {
         mem += RecursiveDynamicUsage(*it);
     }
diff --git a/src/main.cpp b/src/main.cpp
index 2a24d38e52..1e0194e2cd 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -2595,7 +2595,7 @@ bool CheckBlock(const CBlock& block, CValidationState& state, bool fCheckPOW, bo
     // Check the merkle root.
     if (fCheckMerkleRoot) {
         bool mutated;
-        uint256 hashMerkleRoot2 = block.BuildMerkleTree(&mutated);
+        uint256 hashMerkleRoot2 = block.ComputeMerkleRoot(&mutated);
         if (block.hashMerkleRoot != hashMerkleRoot2)
             return state.DoS(100, error("CheckBlock(): hashMerkleRoot mismatch"),
                              REJECT_INVALID, "bad-txnmrklroot", true);
diff --git a/src/miner.cpp b/src/miner.cpp
index b2a356e52d..42c8bb970b 100644
--- a/src/miner.cpp
+++ b/src/miner.cpp
@@ -368,7 +368,7 @@ void IncrementExtraNonce(CBlock* pblock, const CBlockIndex* pindexPrev, unsigned
     assert(txCoinbase.vin[0].scriptSig.size() <= 100);
 
     pblock->vtx[0] = txCoinbase;
-    pblock->hashMerkleRoot = pblock->BuildMerkleTree();
+    pblock->hashMerkleRoot = pblock->ComputeMerkleRoot();
 }
 
 //////////////////////////////////////////////////////////////////////////////
diff --git a/src/primitives/block.cpp b/src/primitives/block.cpp
index 5b9c13d870..7a58074d24 100644
--- a/src/primitives/block.cpp
+++ b/src/primitives/block.cpp
@@ -15,7 +15,7 @@ uint256 CBlockHeader::GetHash() const
     return SerializeHash(*this);
 }
 
-uint256 CBlock::BuildMerkleTree(bool* fMutated) const
+uint256 CBlock::ComputeMerkleRoot(bool* fMutated) const
 {
     /* WARNING! If you're reading this because you're learning about crypto
        and/or designing a new system that will use merkle trees, keep in mind
@@ -52,7 +52,7 @@ uint256 CBlock::BuildMerkleTree(bool* fMutated) const
        known ways of changing the transactions without affecting the merkle
        root.
     */
-    vMerkleTree.clear();
+    std::vector<uint256> vMerkleTree;
     vMerkleTree.reserve(vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
     for (std::vector<CTransaction>::const_iterator it(vtx.begin()); it != vtx.end(); ++it)
         vMerkleTree.push_back(it->GetHash());
@@ -78,37 +78,6 @@ uint256 CBlock::BuildMerkleTree(bool* fMutated) const
     return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
 }
 
-std::vector<uint256> CBlock::GetMerkleBranch(int nIndex) const
-{
-    if (vMerkleTree.empty())
-        BuildMerkleTree();
-    std::vector<uint256> vMerkleBranch;
-    int j = 0;
-    for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
-    {
-        int i = std::min(nIndex^1, nSize-1);
-        vMerkleBranch.push_back(vMerkleTree[j+i]);
-        nIndex >>= 1;
-        j += nSize;
-    }
-    return vMerkleBranch;
-}
-
-uint256 CBlock::CheckMerkleBranch(uint256 hash, const std::vector<uint256>& vMerkleBranch, int nIndex)
-{
-    if (nIndex == -1)
-        return uint256();
-    for (std::vector<uint256>::const_iterator it(vMerkleBranch.begin()); it != vMerkleBranch.end(); ++it)
-    {
-        if (nIndex & 1)
-            hash = Hash(BEGIN(*it), END(*it), BEGIN(hash), END(hash));
-        else
-            hash = Hash(BEGIN(hash), END(hash), BEGIN(*it), END(*it));
-        nIndex >>= 1;
-    }
-    return hash;
-}
-
 std::string CBlock::ToString() const
 {
     std::stringstream s;
@@ -123,9 +92,5 @@ std::string CBlock::ToString() const
     {
         s << "  " << vtx[i].ToString() << "\n";
     }
-    s << "  vMerkleTree: ";
-    for (unsigned int i = 0; i < vMerkleTree.size(); i++)
-        s << " " << vMerkleTree[i].ToString();
-    s << "\n";
     return s.str();
 }
diff --git a/src/primitives/block.h b/src/primitives/block.h
index 59f46deb1c..7fe8c84cb7 100644
--- a/src/primitives/block.h
+++ b/src/primitives/block.h
@@ -77,9 +77,6 @@ public:
     // network and disk
     std::vector<CTransaction> vtx;
 
-    // memory only
-    mutable std::vector<uint256> vMerkleTree;
-
     CBlock()
     {
         SetNull();
@@ -103,7 +100,6 @@ public:
     {
         CBlockHeader::SetNull();
         vtx.clear();
-        vMerkleTree.clear();
     }
 
     CBlockHeader GetBlockHeader() const
@@ -118,14 +114,12 @@ public:
         return block;
     }
 
-    // Build the in-memory merkle tree for this block and return the merkle root.
+    // Build the merkle tree for this block and return the merkle root.
     // If non-NULL, *mutated is set to whether mutation was detected in the merkle
     // tree (a duplication of transactions in the block leading to an identical
     // merkle root).
-    uint256 BuildMerkleTree(bool* mutated = NULL) const;
+    uint256 ComputeMerkleRoot(bool* mutated = NULL) const;
 
-    std::vector<uint256> GetMerkleBranch(int nIndex) const;
-    static uint256 CheckMerkleBranch(uint256 hash, const std::vector<uint256>& vMerkleBranch, int nIndex);
     std::string ToString() const;
 };
 
diff --git a/src/test/miner_tests.cpp b/src/test/miner_tests.cpp
index ad79a558c2..91a3a5738e 100644
--- a/src/test/miner_tests.cpp
+++ b/src/test/miner_tests.cpp
@@ -87,7 +87,7 @@ BOOST_AUTO_TEST_CASE(CreateNewBlock_validity)
         pblock->vtx[0] = CTransaction(txCoinbase);
         if (txFirst.size() < 2)
             txFirst.push_back(new CTransaction(pblock->vtx[0]));
-        pblock->hashMerkleRoot = pblock->BuildMerkleTree();
+        pblock->hashMerkleRoot = pblock->ComputeMerkleRoot();
         pblock->nNonce = blockinfo[i].nonce;
         CValidationState state;
         BOOST_CHECK(ProcessNewBlock(state, NULL, pblock, true, NULL));
diff --git a/src/test/pmt_tests.cpp b/src/test/pmt_tests.cpp
index f6d06d6805..d9f3c3e467 100644
--- a/src/test/pmt_tests.cpp
+++ b/src/test/pmt_tests.cpp
@@ -48,7 +48,7 @@ BOOST_AUTO_TEST_CASE(pmt_test1)
         }
 
         // calculate actual merkle root and height
-        uint256 merkleRoot1 = block.BuildMerkleTree();
+        uint256 merkleRoot1 = block.ComputeMerkleRoot();
         std::vector<uint256> vTxid(nTx, uint256());
         for (unsigned int j=0; j<nTx; j++)
             vTxid[j] = block.vtx[j].GetHash();
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index c3b1172201..39eff3af30 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -702,9 +702,8 @@ bool CWallet::AddToWallet(const CWalletTx& wtxIn, bool fFromLoadWallet, CWalletD
                 wtx.hashBlock = wtxIn.hashBlock;
                 fUpdated = true;
             }
-            if (wtxIn.nIndex != -1 && (wtxIn.vMerkleBranch != wtx.vMerkleBranch || wtxIn.nIndex != wtx.nIndex))
+            if (wtxIn.nIndex != -1 && (wtxIn.nIndex != wtx.nIndex))
             {
-                wtx.vMerkleBranch = wtxIn.vMerkleBranch;
                 wtx.nIndex = wtxIn.nIndex;
                 fUpdated = true;
             }
@@ -2812,15 +2811,11 @@ int CMerkleTx::SetMerkleBranch(const CBlock& block)
             break;
     if (nIndex == (int)block.vtx.size())
     {
-        vMerkleBranch.clear();
         nIndex = -1;
         LogPrintf("ERROR: SetMerkleBranch(): couldn't find tx in block\n");
         return 0;
     }
 
-    // Fill in merkle branch
-    vMerkleBranch = block.GetMerkleBranch(nIndex);
-
     // Is the tx in a block that's in the main chain
     BlockMap::iterator mi = mapBlockIndex.find(hashBlock);
     if (mi == mapBlockIndex.end())
@@ -2846,14 +2841,6 @@ int CMerkleTx::GetDepthInMainChainINTERNAL(const CBlockIndex* &pindexRet) const
     if (!pindex || !chainActive.Contains(pindex))
         return 0;
 
-    // Make sure the merkle branch connects to this block
-    if (!fMerkleVerified)
-    {
-        if (CBlock::CheckMerkleBranch(GetHash(), vMerkleBranch, nIndex) != pindex->hashMerkleRoot)
-            return 0;
-        fMerkleVerified = true;
-    }
-
     pindexRet = pindex;
     return chainActive.Height() - pindex->nHeight + 1;
 }
diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h
index bd30b67b09..34e98cfb81 100644
--- a/src/wallet/wallet.h
+++ b/src/wallet/wallet.h
@@ -151,13 +151,8 @@ private:
 
 public:
     uint256 hashBlock;
-    std::vector<uint256> vMerkleBranch;
     int nIndex;
 
-    // memory only
-    mutable bool fMerkleVerified;
-
-
     CMerkleTx()
     {
         Init();
@@ -172,13 +167,13 @@ public:
     {
         hashBlock = uint256();
         nIndex = -1;
-        fMerkleVerified = false;
     }
 
     ADD_SERIALIZE_METHODS;
 
     template <typename Stream, typename Operation>
     inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
+        std::vector<uint256> vMerkleBranch; // For compatibility with older versions.
         READWRITE(*(CTransaction*)this);
         nVersion = this->nVersion;
         READWRITE(hashBlock);
diff --git a/src/wallet/walletdb.cpp b/src/wallet/walletdb.cpp
index c1eb184581..0624e442d1 100644
--- a/src/wallet/walletdb.cpp
+++ b/src/wallet/walletdb.cpp
@@ -131,12 +131,14 @@ bool CWalletDB::EraseWatchOnly(const CScript &dest)
 bool CWalletDB::WriteBestBlock(const CBlockLocator& locator)
 {
     nWalletDBUpdated++;
-    return Write(std::string("bestblock"), locator);
+    Write(std::string("bestblock"), CBlockLocator()); // Write empty block locator so versions that require a merkle branch automatically rescan
+    return Write(std::string("bestblock_nomerkle"), locator);
 }
 
 bool CWalletDB::ReadBestBlock(CBlockLocator& locator)
 {
-    return Read(std::string("bestblock"), locator);
+    if (Read(std::string("bestblock"), locator) && !locator.vHave.empty()) return true;
+    return Read(std::string("bestblock_nomerkle"), locator);
 }
 
 bool CWalletDB::WriteOrderPosNext(int64_t nOrderPosNext)