wallet2: do not keep block hashes below last checkpoint

This saves a lot of space and load/save time for wallet caches

4 files changed, 230 insertions, 20 deletions

diff --git a/src/wallet/wallet2.cpp b/src/wallet/wallet2.cpp
index a8572902c..8daf26292 100644
--- a/src/wallet/wallet2.cpp
+++ b/src/wallet/wallet2.cpp
@@ -513,6 +513,7 @@ std::unique_ptr<wallet2> wallet2::make_dummy(const boost::program_options::varia
 //----------------------------------------------------------------------------------------------------
 bool wallet2::init(std::string daemon_address, boost::optional<epee::net_utils::http::login> daemon_login, uint64_t upper_transaction_size_limit)
 {
+  m_checkpoints.init_default_checkpoints(m_testnet);
   if(m_http_client.is_connected())
     m_http_client.disconnect();
   m_is_initialized = true;
@@ -1097,16 +1098,16 @@ void wallet2::get_short_chain_history(std::list<crypto::hash>& ids) const
 {
   size_t i = 0;
   size_t current_multiplier = 1;
-  size_t sz = m_blockchain.size();
+  size_t sz = m_blockchain.size() - m_blockchain.offset();
   if(!sz)
     return;
   size_t current_back_offset = 1;
-  bool genesis_included = false;
+  bool base_included = false;
   while(current_back_offset < sz)
   {
-    ids.push_back(m_blockchain[sz-current_back_offset]);
+    ids.push_back(m_blockchain[m_blockchain.offset() + sz-current_back_offset]);
     if(sz-current_back_offset == 0)
-      genesis_included = true;
+      base_included = true;
     if(i < 10)
     {
       ++current_back_offset;
@@ -1116,8 +1117,10 @@ void wallet2::get_short_chain_history(std::list<crypto::hash>& ids) const
     }
     ++i;
   }
-  if(!genesis_included)
-    ids.push_back(m_blockchain[0]);
+  if(!base_included)
+    ids.push_back(m_blockchain[m_blockchain.offset()]);
+  if(m_blockchain.offset())
+    ids.push_back(m_blockchain.genesis());
 }
 //----------------------------------------------------------------------------------------------------
 void wallet2::parse_block_round(const cryptonote::blobdata &blob, cryptonote::block &bl, crypto::hash &bl_id, bool &error) const
@@ -1754,6 +1757,13 @@ bool wallet2::refresh(uint64_t & blocks_fetched, bool& received_money, bool& ok)
 void wallet2::detach_blockchain(uint64_t height)
 {
   LOG_PRINT_L0("Detaching blockchain on height " << height);
+
+  // size  1 2 3 4 5 6 7 8 9
+  // block 0 1 2 3 4 5 6 7 8
+  //               C
+  THROW_WALLET_EXCEPTION_IF(height <= m_checkpoints.get_max_height() && m_blockchain.size() > m_checkpoints.get_max_height(),
+      error::wallet_internal_error, "Daemon claims reorg below last checkpoint");
+
   size_t transfers_detached = 0;
 
   for (size_t i = 0; i < m_transfers.size(); ++i)
@@ -1784,8 +1794,8 @@ void wallet2::detach_blockchain(uint64_t height)
   }
   m_transfers.erase(it, m_transfers.end());
 
-  size_t blocks_detached = m_blockchain.end() - (m_blockchain.begin()+height);
-  m_blockchain.erase(m_blockchain.begin()+height, m_blockchain.end());
+  size_t blocks_detached = m_blockchain.size() - height;
+  m_blockchain.crop(height);
   m_local_bc_height -= blocks_detached;
 
   for (auto it = m_payments.begin(); it != m_payments.end(); )
@@ -2529,13 +2539,26 @@ void wallet2::load(const std::string& wallet_, const std::string& password)
     check_genesis(genesis_hash);
   }
 
+  trim_hashchain();
+
   m_local_bc_height = m_blockchain.size();
 }
 //----------------------------------------------------------------------------------------------------
+void wallet2::trim_hashchain()
+{
+  uint64_t height = m_checkpoints.get_max_height();
+  if (height > 0)
+  {
+    --height;
+    MDEBUG("trimming to " << height << ", offset " << m_blockchain.offset());
+    m_blockchain.trim(height);
+  }
+}
+//----------------------------------------------------------------------------------------------------
 void wallet2::check_genesis(const crypto::hash& genesis_hash) const {
   std::string what("Genesis block mismatch. You probably use wallet without testnet flag with blockchain from test network or vice versa");
 
-  THROW_WALLET_EXCEPTION_IF(genesis_hash != m_blockchain[0], error::wallet_internal_error, what);
+  THROW_WALLET_EXCEPTION_IF(genesis_hash != m_blockchain.genesis(), error::wallet_internal_error, what);
 }
 //----------------------------------------------------------------------------------------------------
 std::string wallet2::path() const
@@ -2550,6 +2573,8 @@ void wallet2::store()
 //----------------------------------------------------------------------------------------------------
 void wallet2::store_to(const std::string &path, const std::string &password)
 {
+  trim_hashchain();
+
   // if file is the same, we do:
   // 1. save wallet to the *.new file
   // 2. remove old wallet file
@@ -5528,20 +5553,28 @@ void wallet2::import_payments_out(const std::list<std::pair<crypto::hash,wallet2
   }
 }
 
-std::vector<crypto::hash> wallet2::export_blockchain() const
+std::tuple<size_t,crypto::hash,std::vector<crypto::hash>> wallet2::export_blockchain() const
 {
-  std::vector<crypto::hash> bc;
-  for (auto const &b : m_blockchain)
+  std::tuple<size_t, crypto::hash, std::vector<crypto::hash>> bc;
+  std::get<0>(bc) = m_blockchain.offset();
+  std::get<1>(bc) = m_blockchain.empty() ? crypto::null_hash: m_blockchain.genesis();
+  for (size_t n = m_blockchain.offset(); n < m_blockchain.size(); ++n)
   {
-    bc.push_back(b);
+    std::get<2>(bc).push_back(m_blockchain[n]);
   }
   return bc;
 }
 
-void wallet2::import_blockchain(const std::vector<crypto::hash> &bc)
+void wallet2::import_blockchain(const std::tuple<size_t, crypto::hash, std::vector<crypto::hash>> &bc)
 {
   m_blockchain.clear();
-  for (auto const &b : bc)
+  if (std::get<0>(bc))
+  {
+    for (size_t n = std::get<0>(bc); n > 0; ++n)
+      m_blockchain.push_back(std::get<1>(bc));
+    m_blockchain.trim(std::get<0>(bc));
+  }
+  for (auto const &b : std::get<2>(bc))
   {
     m_blockchain.push_back(b);
   }
diff --git a/src/wallet/wallet2.h b/src/wallet/wallet2.h
index cf8dd171c..83863ca54 100644
--- a/src/wallet/wallet2.h
+++ b/src/wallet/wallet2.h
@@ -36,6 +36,7 @@
 #include <boost/program_options/variables_map.hpp>
 #include <boost/serialization/list.hpp>
 #include <boost/serialization/vector.hpp>
+#include <boost/serialization/deque.hpp>
 #include <atomic>
 
 #include "include_base_utils.h"
@@ -52,6 +53,7 @@
 #include "crypto/hash.h"
 #include "ringct/rctTypes.h"
 #include "ringct/rctOps.h"
+#include "checkpoints/checkpoints.h"
 
 #include "wallet_errors.h"
 #include "common/password.h"
@@ -91,6 +93,37 @@ namespace tools
     }
   };
 
+  class hashchain
+  {
+  public:
+    hashchain(): m_genesis(crypto::null_hash), m_offset(0) {}
+
+    size_t size() const { return m_blockchain.size() + m_offset; }
+    size_t offset() const { return m_offset; }
+    const crypto::hash &genesis() const { return m_genesis; }
+    void push_back(const crypto::hash &hash) { if (m_offset == 0 && m_blockchain.empty()) m_genesis = hash; m_blockchain.push_back(hash); }
+    bool is_in_bounds(size_t idx) const { return idx >= m_offset && idx < size(); }
+    const crypto::hash &operator[](size_t idx) const { return m_blockchain[idx - m_offset]; }
+    crypto::hash &operator[](size_t idx) { return m_blockchain[idx - m_offset]; }
+    void crop(size_t height) { m_blockchain.resize(height - m_offset); }
+    void clear() { m_offset = 0; m_blockchain.clear(); }
+    bool empty() const { return m_blockchain.empty() && m_offset == 0; }
+    void trim(size_t height) { while (height > m_offset && !m_blockchain.empty()) { m_blockchain.pop_front(); ++m_offset; } m_blockchain.shrink_to_fit(); }
+
+    template <class t_archive>
+    inline void serialize(t_archive &a, const unsigned int ver)
+    {
+      a & m_offset;
+      a & m_genesis;
+      a & m_blockchain;
+    }
+
+  private:
+    size_t m_offset;
+    crypto::hash m_genesis;
+    std::deque<crypto::hash> m_blockchain;
+  };
+
   class wallet2
   {
     friend class ::Serialization_portability_wallet_Test;
@@ -452,7 +485,19 @@ namespace tools
       uint64_t dummy_refresh_height = 0; // moved to keys file
       if(ver < 5)
         return;
-      a & m_blockchain;
+      if (ver < 19)
+      {
+        std::vector<crypto::hash> blockchain;
+        a & blockchain;
+        for (const auto &b: blockchain)
+        {
+          m_blockchain.push_back(b);
+        }
+      }
+      else
+      {
+        a & m_blockchain;
+      }
       a & m_transfers;
       a & m_account_public_address;
       a & m_key_images;
@@ -601,8 +646,8 @@ namespace tools
     payment_container export_payments() const;
     void import_payments(const payment_container &payments);
     void import_payments_out(const std::list<std::pair<crypto::hash,wallet2::confirmed_transfer_details>> &confirmed_payments);
-    std::vector<crypto::hash> export_blockchain() const;
-    void import_blockchain(const std::vector<crypto::hash> &bc);
+    std::tuple<size_t, crypto::hash, std::vector<crypto::hash>> export_blockchain() const;
+    void import_blockchain(const std::tuple<size_t, crypto::hash, std::vector<crypto::hash>> &bc);
     bool export_key_images(const std::string filename);
     std::vector<std::pair<crypto::key_image, crypto::signature>> export_key_images() const;
     uint64_t import_key_images(const std::vector<std::pair<crypto::key_image, crypto::signature>> &signed_key_images, uint64_t &spent, uint64_t &unspent, bool check_spent = true);
@@ -678,6 +723,7 @@ namespace tools
     bool should_pick_a_second_output(bool use_rct, size_t n_transfers, const std::vector<size_t> &unused_transfers_indices, const std::vector<size_t> &unused_dust_indices) const;
     std::vector<size_t> get_only_rct(const std::vector<size_t> &unused_dust_indices, const std::vector<size_t> &unused_transfers_indices) const;
     void scan_output(const cryptonote::account_keys &keys, const cryptonote::transaction &tx, const crypto::public_key &tx_pub_key, size_t i, tx_scan_info_t &tx_scan_info, int &num_vouts_received, uint64_t &tx_money_got_in_outs, std::vector<size_t> &outs);
+    void trim_hashchain();
 
     cryptonote::account_base m_account;
     boost::optional<epee::net_utils::http::login> m_daemon_login;
@@ -685,12 +731,13 @@ namespace tools
     std::string m_wallet_file;
     std::string m_keys_file;
     epee::net_utils::http::http_simple_client m_http_client;
-    std::vector<crypto::hash> m_blockchain;
+    hashchain m_blockchain;
     std::atomic<uint64_t> m_local_bc_height; //temporary workaround
     std::unordered_map<crypto::hash, unconfirmed_transfer_details> m_unconfirmed_txs;
     std::unordered_map<crypto::hash, confirmed_transfer_details> m_confirmed_txs;
     std::unordered_multimap<crypto::hash, payment_details> m_unconfirmed_payments;
     std::unordered_map<crypto::hash, crypto::secret_key> m_tx_keys;
+    cryptonote::checkpoints m_checkpoints;
 
     transfer_container m_transfers;
     payment_container m_payments;
@@ -730,7 +777,7 @@ namespace tools
     std::unordered_set<crypto::hash> m_scanned_pool_txs[2];
   };
 }
-BOOST_CLASS_VERSION(tools::wallet2, 18)
+BOOST_CLASS_VERSION(tools::wallet2, 19)
 BOOST_CLASS_VERSION(tools::wallet2::transfer_details, 7)
 BOOST_CLASS_VERSION(tools::wallet2::payment_details, 1)
 BOOST_CLASS_VERSION(tools::wallet2::unconfirmed_transfer_details, 6)
diff --git a/tests/unit_tests/CMakeLists.txt b/tests/unit_tests/CMakeLists.txt
index 63abe928d..53d93fcce 100644
--- a/tests/unit_tests/CMakeLists.txt
+++ b/tests/unit_tests/CMakeLists.txt
@@ -46,6 +46,7 @@ set(unit_tests_sources
   epee_utils.cpp
   fee.cpp
   get_xtype_from_string.cpp
+  hashchain.cpp
   http.cpp
   main.cpp
   mnemonics.cpp
diff --git a/tests/unit_tests/hashchain.cpp b/tests/unit_tests/hashchain.cpp
new file mode 100644
index 000000000..0fa0f784a
--- /dev/null
+++ b/tests/unit_tests/hashchain.cpp
@@ -0,0 +1,129 @@
+// Copyright (c) 2014-2017, The Monero Project
+// 
+// All rights reserved.
+// 
+// Redistribution and use in source and binary forms, with or without modification, are
+// permitted provided that the following conditions are met:
+// 
+// 1. Redistributions of source code must retain the above copyright notice, this list of
+//    conditions and the following disclaimer.
+// 
+// 2. Redistributions in binary form must reproduce the above copyright notice, this list
+//    of conditions and the following disclaimer in the documentation and/or other
+//    materials provided with the distribution.
+// 
+// 3. Neither the name of the copyright holder nor the names of its contributors may be
+//    used to endorse or promote products derived from this software without specific
+//    prior written permission.
+// 
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
+// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// FIXME: move this into a full wallet2 unit test suite, if possible
+
+#include "gtest/gtest.h"
+
+#include "wallet/wallet2.h"
+
+static crypto::hash make_hash(uint64_t n)
+{
+  union
+  {
+    crypto::hash hash;
+    uint64_t n;
+  } hash;
+  hash.hash = crypto::null_hash;
+  hash.n = n;
+  return hash.hash;
+}
+
+TEST(hashchain, empty)
+{
+  tools::hashchain hashchain;
+  ASSERT_EQ(hashchain.size(), 0);
+  ASSERT_EQ(hashchain.offset(), 0);
+}
+
+TEST(hashchain, genesis)
+{
+  tools::hashchain hashchain;
+  hashchain.push_back(make_hash(1));
+  ASSERT_EQ(hashchain.size(), 1);
+  ASSERT_EQ(hashchain.genesis(), make_hash(1));
+  hashchain.push_back(make_hash(2));
+  ASSERT_EQ(hashchain.size(), 2);
+  ASSERT_EQ(hashchain.genesis(), make_hash(1));
+}
+
+TEST(hashchain, push_back)
+{
+  tools::hashchain hashchain;
+  hashchain.push_back(make_hash(1));
+  hashchain.push_back(make_hash(2));
+  hashchain.push_back(make_hash(3));
+  ASSERT_EQ(hashchain[0], make_hash(1));
+  ASSERT_EQ(hashchain[1], make_hash(2));
+  ASSERT_EQ(hashchain[2], make_hash(3));
+}
+
+TEST(hashchain, clear_empty)
+{
+  tools::hashchain hashchain;
+  ASSERT_TRUE(hashchain.empty());
+  hashchain.push_back(make_hash(1));
+  ASSERT_FALSE(hashchain.empty());
+  hashchain.push_back(make_hash(2));
+  ASSERT_FALSE(hashchain.empty());
+  hashchain.clear();
+  ASSERT_TRUE(hashchain.empty());
+}
+
+TEST(hashchain, crop)
+{
+  tools::hashchain hashchain;
+  hashchain.push_back(make_hash(1));
+  hashchain.push_back(make_hash(2));
+  hashchain.push_back(make_hash(3));
+  ASSERT_EQ(hashchain.size(), 3);
+  ASSERT_EQ(hashchain[0], make_hash(1));
+  ASSERT_EQ(hashchain[1], make_hash(2));
+  ASSERT_EQ(hashchain[2], make_hash(3));
+  hashchain.crop(3);
+  ASSERT_EQ(hashchain.size(), 3);
+  hashchain.crop(2);
+  ASSERT_EQ(hashchain.size(), 2);
+  ASSERT_EQ(hashchain[0], make_hash(1));
+  ASSERT_EQ(hashchain[1], make_hash(2));
+  ASSERT_EQ(hashchain.genesis(), make_hash(1));
+  hashchain.crop(0);
+  ASSERT_TRUE(hashchain.empty());
+  ASSERT_EQ(hashchain.size(), 0);
+  hashchain.push_back(make_hash(5));
+  ASSERT_EQ(hashchain.genesis(), make_hash(5));
+  ASSERT_EQ(hashchain.size(), 1);
+}
+
+TEST(hashchain, trim)
+{
+  tools::hashchain hashchain;
+  hashchain.push_back(make_hash(1));
+  hashchain.push_back(make_hash(2));
+  hashchain.push_back(make_hash(3));
+  ASSERT_EQ(hashchain.offset(), 0);
+  hashchain.trim(2);
+  ASSERT_EQ(hashchain.offset(), 2);
+  ASSERT_EQ(hashchain.size(), 3);
+  ASSERT_EQ(hashchain[2], make_hash(3));
+  hashchain.trim(3);
+  ASSERT_EQ(hashchain.offset(), 3);
+  ASSERT_EQ(hashchain.size(), 3);
+  ASSERT_FALSE(hashchain.empty());
+  ASSERT_EQ(hashchain.genesis(), make_hash(1));
+}