blockchain_db: add k-anonymity to txid fetching

Read more about k-anonymity [here](https://en.wikipedia.org/wiki/K-anonymity). We implement this feature in the monero daemon for transactions
by providing a "Txid Template", which is simply a txid with all but `num_matching_bits` bits zeroed out, and the number `num_matching_bits`. We add an operation to `BlockchainLMDB` called
`get_txids_loose` which takes a txid template and returns all txids in the database (chain and mempool) that satisfy that template. Thus, a client can
ask about a specific transaction from a daemon without revealing the exact transaction they are inquiring about. The client can control the statistical
chance that other TXIDs (besides the one in question) match the txid template sent to the daemon up to a power of 2. For example, if a client sets their `num_matching_bits`
to 5, then statistically any txid has a 1/(2^5) chance to match. With `num_matching_bits`=10, there is a 1/(2^10) chance, so on and so forth.

Co-authored-by: ACK-J <60232273+ACK-J@users.noreply.github.com>

2 files changed, 82 insertions, 0 deletions

diff --git a/src/cryptonote_basic/cryptonote_basic_impl.cpp b/src/cryptonote_basic/cryptonote_basic_impl.cpp
index 9bde20609..7fe398283 100644
--- a/src/cryptonote_basic/cryptonote_basic_impl.cpp
+++ b/src/cryptonote_basic/cryptonote_basic_impl.cpp
@@ -310,6 +310,53 @@ namespace cryptonote {
   bool operator ==(const cryptonote::block& a, const cryptonote::block& b) {
     return cryptonote::get_block_hash(a) == cryptonote::get_block_hash(b);
   }
+  //--------------------------------------------------------------------------------
+  int compare_hash32_reversed_nbits(const crypto::hash& ha, const crypto::hash& hb, unsigned int nbits)
+  {
+    static_assert(sizeof(uint64_t) * 4 == sizeof(crypto::hash), "hash is wrong size");
+
+    // We have to copy these buffers b/c of the strict aliasing rule
+    uint64_t va[4];
+    memcpy(va, &ha, sizeof(crypto::hash));
+    uint64_t vb[4];
+    memcpy(vb, &hb, sizeof(crypto::hash));
+
+    for (int n = 3; n >= 0 && nbits; --n)
+    {
+      const unsigned int msb_nbits = std::min<unsigned int>(64, nbits);
+      const uint64_t lsb_nbits_dropped = static_cast<uint64_t>(64 - msb_nbits);
+      const uint64_t van = SWAP64LE(va[n]) >> lsb_nbits_dropped;
+      const uint64_t vbn = SWAP64LE(vb[n]) >> lsb_nbits_dropped;
+      nbits -= msb_nbits;
+
+      if (van < vbn) return -1; else if (van > vbn) return 1;
+    }
+
+    return 0;
+  }
+
+  crypto::hash make_hash32_loose_template(unsigned int nbits, const crypto::hash& h)
+  {
+    static_assert(sizeof(uint64_t) * 4 == sizeof(crypto::hash), "hash is wrong size");
+
+    // We have to copy this buffer b/c of the strict aliasing rule
+    uint64_t vh[4];
+    memcpy(vh, &h, sizeof(crypto::hash));
+
+    for (int n = 3; n >= 0; --n)
+    {
+      const unsigned int msb_nbits = std::min<unsigned int>(64, nbits);
+      const uint64_t mask = msb_nbits ? (~((std::uint64_t(1) << (64 - msb_nbits)) - 1)) : 0;
+      nbits -= msb_nbits;
+
+      vh[n] &= SWAP64LE(mask);
+    }
+
+    crypto::hash res;
+    memcpy(&res, vh, sizeof(crypto::hash));
+    return res;
+  }
+  //--------------------------------------------------------------------------------
 }
 
 //--------------------------------------------------------------------------------
diff --git a/src/cryptonote_basic/cryptonote_basic_impl.h b/src/cryptonote_basic/cryptonote_basic_impl.h
index 984bee19f..53dbc47d7 100644
--- a/src/cryptonote_basic/cryptonote_basic_impl.h
+++ b/src/cryptonote_basic/cryptonote_basic_impl.h
@@ -112,6 +112,41 @@ namespace cryptonote {
 
   bool operator ==(const cryptonote::transaction& a, const cryptonote::transaction& b);
   bool operator ==(const cryptonote::block& a, const cryptonote::block& b);
+
+  /************************************************************************/
+  /* K-anonymity helper functions                                         */
+  /************************************************************************/
+
+  /**
+   * @brief Compares two hashes up to `nbits` bits in reverse byte order ("LMDB key order")
+   *
+   * The comparison essentially goes from the 31th, 30th, 29th, ..., 0th byte and compares the MSBs
+   * to the LSBs in each byte, up to `nbits` bits. If we use up `nbits` bits before finding a
+   * difference in the bits between the two hashes, we return 0. If we encounter a zero bit in `ha`
+   * where `hb` has a one in that bit place, then we reutrn -1. If the converse scenario happens,
+   * we return a 1. When `nbits` == 256 (there are 256 bits in `crypto::hash`), calling this is
+   * functionally identical to `BlockchainLMDB::compare_hash32`.
+   *
+   * @param ha left hash
+   * @param hb right hash
+   * @param nbits the number of bits to consider, a higher value means a finer comparison
+   * @return int 0 if ha == hb, -1 if ha < hb, 1 if ha > hb
+   */
+  int compare_hash32_reversed_nbits(const crypto::hash& ha, const crypto::hash& hb, unsigned int nbits);
+
+  /**
+   * @brief Make a template which matches `h` in LMDB order up to `nbits` bits, safe for k-anonymous fetching
+   *
+   * To be more technical, this function creates a hash which satifies the following property:
+   *     For all `H_prime` s.t. `0 == compare_hash32_reversed_nbits(real_hash, H_prime, nbits)`,
+   *     `1 > compare_hash32_reversed_nbits(real_hash, H_prime, 256)`.
+   * In other words, we return the "least" hash nbit-equal to `real_hash`.
+   *
+   * @param nbits The number of "MSB" bits to include in the template
+   * @param real_hash The original hash which contains more information than we want to disclose
+   * @return crypto::hash hash template that contains `nbits` bits matching real_hash and no more
+   */
+  crypto::hash make_hash32_loose_template(unsigned int nbits, const crypto::hash& real_hash);
 }
 
 bool parse_hash256(const std::string &str_hash, crypto::hash& hash);