Add view tags to outputs to reduce wallet scanning time

Implements view tags as proposed by @UkoeHB in MRL issue
https://github.com/monero-project/research-lab/issues/73

At tx construction, the sender adds a 1-byte view tag to each
output. The view tag is derived from the sender-receiver
shared secret. When scanning for outputs, the receiver can
check the view tag for a match, in order to reduce scanning
time. When the view tag does not match, the wallet avoids the
more expensive EC operations when deriving the output public
key using the shared secret.

5 files changed, 175 insertions, 2 deletions

diff --git a/tests/performance_tests/CMakeLists.txt b/tests/performance_tests/CMakeLists.txt
index 03b124981..c079afe3a 100644
--- a/tests/performance_tests/CMakeLists.txt
+++ b/tests/performance_tests/CMakeLists.txt
@@ -43,6 +43,7 @@ set(performance_tests_headers
   generate_keypair.h
   signature.h
   is_out_to_acc.h
+  out_can_be_to_acc.h
   subaddress_expand.h
   range_proof.h
   bulletproof.h
diff --git a/tests/performance_tests/derive_view_tag.h b/tests/performance_tests/derive_view_tag.h
new file mode 100644
index 000000000..ee4efb16d
--- /dev/null
+++ b/tests/performance_tests/derive_view_tag.h
@@ -0,0 +1,62 @@
+// Copyright (c) 2014-2021, 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.
+//
+// Parts of this file are originally copyright (c) 2012-2013 The Cryptonote developers
+
+#pragma once
+
+#include "crypto/crypto.h"
+#include "cryptonote_basic/cryptonote_basic.h"
+
+#include "single_tx_test_base.h"
+
+class test_derive_view_tag : public single_tx_test_base
+{
+public:
+  static const size_t loop_count = 10000;
+
+  bool init()
+  {
+    if (!single_tx_test_base::init())
+      return false;
+
+    crypto::generate_key_derivation(m_tx_pub_key, m_bob.get_keys().m_view_secret_key, m_key_derivation);
+
+    return true;
+  }
+
+  bool test()
+  {
+    crypto::view_tag view_tag;
+    crypto::derive_view_tag(m_key_derivation, 0, view_tag);
+    return true;
+  }
+
+private:
+  crypto::key_derivation m_key_derivation;
+};
diff --git a/tests/performance_tests/is_out_to_acc.h b/tests/performance_tests/is_out_to_acc.h
index d1204ee68..75d4a5c46 100644
--- a/tests/performance_tests/is_out_to_acc.h
+++ b/tests/performance_tests/is_out_to_acc.h
@@ -43,8 +43,9 @@ public:
 
   bool test()
   {
-    const cryptonote::txout_to_key& tx_out = boost::get<cryptonote::txout_to_key>(m_tx.vout[0].target);
-    return cryptonote::is_out_to_acc(m_bob.get_keys(), tx_out, m_tx_pub_key, m_additional_tx_pub_keys, 0);
+    crypto::public_key output_public_key;
+    cryptonote::get_output_public_key(m_tx.vout[0], output_public_key);
+    return cryptonote::is_out_to_acc(m_bob.get_keys(), output_public_key, m_tx_pub_key, m_additional_tx_pub_keys, 0);
   }
 };
 
diff --git a/tests/performance_tests/main.cpp b/tests/performance_tests/main.cpp
index 8bd1008cb..71c736977 100644
--- a/tests/performance_tests/main.cpp
+++ b/tests/performance_tests/main.cpp
@@ -42,6 +42,7 @@
 #include "cn_slow_hash.h"
 #include "derive_public_key.h"
 #include "derive_secret_key.h"
+#include "derive_view_tag.h"
 #include "ge_frombytes_vartime.h"
 #include "ge_tobytes.h"
 #include "generate_key_derivation.h"
@@ -50,6 +51,7 @@
 #include "generate_keypair.h"
 #include "signature.h"
 #include "is_out_to_acc.h"
+#include "out_can_be_to_acc.h"
 #include "subaddress_expand.h"
 #include "sc_reduce32.h"
 #include "sc_check.h"
@@ -194,6 +196,9 @@ int main(int argc, char** argv)
 
   TEST_PERFORMANCE0(filter, p, test_is_out_to_acc);
   TEST_PERFORMANCE0(filter, p, test_is_out_to_acc_precomp);
+  TEST_PERFORMANCE2(filter, p, test_out_can_be_to_acc, false, true); // no view tag, owned
+  TEST_PERFORMANCE2(filter, p, test_out_can_be_to_acc, true, false); // use view tag, not owned
+  TEST_PERFORMANCE2(filter, p, test_out_can_be_to_acc, true, true); // use view tag, owned
   TEST_PERFORMANCE0(filter, p, test_generate_key_image_helper);
   TEST_PERFORMANCE0(filter, p, test_generate_key_derivation);
   TEST_PERFORMANCE0(filter, p, test_generate_key_image);
@@ -206,6 +211,7 @@ int main(int argc, char** argv)
   TEST_PERFORMANCE0(filter, p, test_sc_check);
   TEST_PERFORMANCE1(filter, p, test_signature, false);
   TEST_PERFORMANCE1(filter, p, test_signature, true);
+  TEST_PERFORMANCE0(filter, p, test_derive_view_tag);
 
   TEST_PERFORMANCE2(filter, p, test_wallet2_expand_subaddresses, 50, 200);
 
diff --git a/tests/performance_tests/out_can_be_to_acc.h b/tests/performance_tests/out_can_be_to_acc.h
new file mode 100644
index 000000000..86e236b7b
--- /dev/null
+++ b/tests/performance_tests/out_can_be_to_acc.h
@@ -0,0 +1,103 @@
+// Copyright (c) 2014-2021, 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.
+//
+// Parts of this file are originally copyright (c) 2012-2013 The Cryptonote developers
+
+#pragma once
+
+#include "crypto/crypto.h"
+#include "cryptonote_basic/cryptonote_basic.h"
+
+#include "single_tx_test_base.h"
+
+using namespace crypto;
+
+// use_view_tags: whether to enable view tag checking
+// is_owned: whether the output is owned by us
+template<bool use_view_tags, bool is_owned>
+class test_out_can_be_to_acc : public single_tx_test_base
+{
+  public:
+    static const size_t loop_count = 1000;
+
+    bool init()
+    {
+      if (!single_tx_test_base::init())
+        return false;
+
+      crypto::key_derivation key_derivation;
+      crypto::view_tag vt;
+
+      m_output_index = 0;
+      m_view_secret_key = m_bob.get_keys().m_view_secret_key;
+      m_spend_public_key = m_bob.get_keys().m_account_address.m_spend_public_key;
+
+      cryptonote::get_output_public_key(m_tx.vout[m_output_index], m_output_public_key);
+
+      if (use_view_tags)
+      {
+        crypto::generate_key_derivation(m_tx_pub_key, m_view_secret_key, key_derivation);
+        crypto::derive_view_tag(key_derivation, m_output_index, vt);
+        m_view_tag_opt = vt;
+      }
+      else
+        m_view_tag_opt = boost::optional<crypto::view_tag>();
+
+      return true;
+    }
+
+    bool test()
+    {
+      // include key derivation to demonstrate performance improvement when using view tags
+      crypto::key_derivation key_derivation;
+      crypto::generate_key_derivation(m_tx_pub_key, m_view_secret_key, key_derivation);
+
+      // if using view tags, this ensures we computed the view tag properly
+      if (!cryptonote::out_can_be_to_acc(m_view_tag_opt, key_derivation, m_output_index))
+        return false;
+
+      // if user owns output, this tests the output public key matches the derived
+      if (is_owned)
+      {
+        crypto::public_key output_public_key;
+        crypto::derive_public_key(key_derivation, m_output_index, m_spend_public_key, output_public_key);
+
+        if (m_output_public_key != output_public_key)
+          return false;
+      }
+
+      return true;
+    }
+
+    private:
+      size_t m_output_index;
+      crypto::secret_key m_view_secret_key;
+      crypto::public_key m_spend_public_key;
+      crypto::public_key m_output_public_key;
+      boost::optional<crypto::view_tag> m_view_tag_opt;
+};