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);