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.

1 files changed, 19 insertions, 1 deletions

diff --git a/src/crypto/crypto.h b/src/crypto/crypto.h
index 596090329..d8cd6c6a0 100644
--- a/src/crypto/crypto.h
+++ b/src/crypto/crypto.h
@@ -99,6 +99,10 @@ namespace crypto {
     ec_scalar c, r;
     friend class crypto_ops;
   };
+
+  POD_CLASS view_tag {
+    char data;
+  };
 #pragma pack(pop)
 
   void hash_to_scalar(const void *data, size_t length, ec_scalar &res);
@@ -107,7 +111,7 @@ namespace crypto {
   static_assert(sizeof(ec_point) == 32 && sizeof(ec_scalar) == 32 &&
     sizeof(public_key) == 32 && sizeof(public_key_memsafe) == 32 && sizeof(secret_key) == 32 &&
     sizeof(key_derivation) == 32 && sizeof(key_image) == 32 &&
-    sizeof(signature) == 64, "Invalid structure size");
+    sizeof(signature) == 64 && sizeof(view_tag) == 1, "Invalid structure size");
 
   class crypto_ops {
     crypto_ops();
@@ -151,6 +155,8 @@ namespace crypto {
       const public_key *const *, std::size_t, const signature *);
     friend bool check_ring_signature(const hash &, const key_image &,
       const public_key *const *, std::size_t, const signature *);
+    static void derive_view_tag(const key_derivation &, std::size_t, view_tag &);
+    friend void derive_view_tag(const key_derivation &, std::size_t, view_tag &);
   };
 
   void generate_random_bytes_thread_safe(size_t N, uint8_t *bytes);
@@ -297,6 +303,14 @@ namespace crypto {
     return check_ring_signature(prefix_hash, image, pubs.data(), pubs.size(), sig);
   }
 
+  /* Derive a 1-byte view tag from the sender-receiver shared secret to reduce scanning time.
+   * When scanning outputs that were not sent to the user, checking the view tag for a match removes the need to proceed with expensive EC operations
+   * for an expected 99.6% of outputs (expected false positive rate = 1/2^8 = 1/256 = 0.4% = 100% - 99.6%).
+   */
+  inline void derive_view_tag(const key_derivation &derivation, std::size_t output_index, view_tag &vt) {
+    crypto_ops::derive_view_tag(derivation, output_index, vt);
+  }
+
   inline std::ostream &operator <<(std::ostream &o, const crypto::public_key &v) {
     epee::to_hex::formatted(o, epee::as_byte_span(v)); return o;
   }
@@ -312,6 +326,9 @@ namespace crypto {
   inline std::ostream &operator <<(std::ostream &o, const crypto::signature &v) {
     epee::to_hex::formatted(o, epee::as_byte_span(v)); return o;
   }
+  inline std::ostream &operator <<(std::ostream &o, const crypto::view_tag &v) {
+    epee::to_hex::formatted(o, epee::as_byte_span(v)); return o;
+  }
 
   const extern crypto::public_key null_pkey;
   const extern crypto::secret_key null_skey;
@@ -325,3 +342,4 @@ CRYPTO_MAKE_HASHABLE_CONSTANT_TIME(secret_key)
 CRYPTO_MAKE_HASHABLE_CONSTANT_TIME(public_key_memsafe)
 CRYPTO_MAKE_HASHABLE(key_image)
 CRYPTO_MAKE_COMPARABLE(signature)
+CRYPTO_MAKE_COMPARABLE(view_tag)