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.

2 files changed, 43 insertions, 1 deletions

diff --git a/src/crypto/crypto.cpp b/src/crypto/crypto.cpp
index 1f46164d7..77a36069a 100644
--- a/src/crypto/crypto.cpp
+++ b/src/crypto/crypto.cpp
@@ -749,4 +749,28 @@ POP_WARNINGS
     sc_sub(&h, &h, &sum);
     return sc_isnonzero(&h) == 0;
   }
+
+  void crypto_ops::derive_view_tag(const key_derivation &derivation, size_t output_index, view_tag &view_tag) {
+    #pragma pack(push, 1)
+    struct {
+      char salt[8]; // view tag domain-separator
+      key_derivation derivation;
+      char output_index[(sizeof(size_t) * 8 + 6) / 7];
+    } buf;
+    #pragma pack(pop)
+
+    char *end = buf.output_index;
+    memcpy(buf.salt, "view_tag", 8); // leave off null terminator
+    buf.derivation = derivation;
+    tools::write_varint(end, output_index);
+    assert(end <= buf.output_index + sizeof buf.output_index);
+
+    // view_tag_full = H[salt|derivation|output_index]
+    hash view_tag_full;
+    cn_fast_hash(&buf, end - reinterpret_cast<char *>(&buf), view_tag_full);
+
+    // only need a slice of view_tag_full to realize optimal perf/space efficiency
+    static_assert(sizeof(crypto::view_tag) <= sizeof(view_tag_full), "view tag should not be larger than hash result");
+    memcpy(&view_tag, &view_tag_full, sizeof(crypto::view_tag));
+  }
 }
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)