diff options
| -rw-r--r-- | src/blockchain_db/blockchain_db.h | 15 | ||||
| -rw-r--r-- | src/blockchain_db/lmdb/db_lmdb.cpp | 52 | ||||
| -rw-r--r-- | src/blockchain_db/lmdb/db_lmdb.h | 2 | ||||
| -rw-r--r-- | src/blockchain_db/testdb.h | 1 | ||||
| -rw-r--r-- | src/cryptonote_basic/cryptonote_basic_impl.cpp | 47 | ||||
| -rw-r--r-- | src/cryptonote_basic/cryptonote_basic_impl.h | 35 | ||||
| -rw-r--r-- | src/rpc/core_rpc_server.cpp | 76 | ||||
| -rw-r--r-- | src/rpc/core_rpc_server.h | 2 | ||||
| -rw-r--r-- | src/rpc/core_rpc_server_commands_defs.h | 27 | ||||
| -rwxr-xr-x | tests/functional_tests/functional_tests_rpc.py | 6 | ||||
| -rwxr-xr-x | tests/functional_tests/k_anonymity.py | 314 | ||||
| -rw-r--r-- | tests/unit_tests/lmdb.cpp | 182 | ||||
| -rw-r--r-- | utils/python-rpc/framework/daemon.py | 12 |
13 files changed, 770 insertions, 1 deletions
diff --git a/src/blockchain_db/blockchain_db.h b/src/blockchain_db/blockchain_db.h index b38ec9e05..9628a5c4d 100644 --- a/src/blockchain_db/blockchain_db.h +++ b/src/blockchain_db/blockchain_db.h @@ -1306,6 +1306,21 @@ public: virtual bool get_pruned_tx_blobs_from(const crypto::hash& h, size_t count, std::vector<cryptonote::blobdata> &bd) const = 0; /** + * @brief Get all txids in the database (chain and pool) that match a certain nbits txid template + * + * To be more specific, for all `dbtxid` txids in the database, return `dbtxid` if + * `0 == cryptonote::compare_hash32_reversed_nbits(txid_template, dbtxid, nbits)`. + * + * @param txid_template the transaction id template + * @param nbits number of bits to compare against in the template + * @param max_num_txs The maximum number of txids to match, if we hit this limit, throw early + * @return std::vector<crypto::hash> the list of all matching txids + * + * @throw TX_EXISTS if the number of txids that match exceed `max_num_txs` + */ + virtual std::vector<crypto::hash> get_txids_loose(const crypto::hash& txid_template, std::uint32_t nbits, uint64_t max_num_txs = 0) = 0; + + /** * @brief fetches a variable number of blocks and transactions from the given height, in canonical blockchain order * * The subclass should return the blocks and transactions stored from the one with the given diff --git a/src/blockchain_db/lmdb/db_lmdb.cpp b/src/blockchain_db/lmdb/db_lmdb.cpp index 4178c862b..2c015faee 100644 --- a/src/blockchain_db/lmdb/db_lmdb.cpp +++ b/src/blockchain_db/lmdb/db_lmdb.cpp @@ -3144,6 +3144,58 @@ bool BlockchainLMDB::get_pruned_tx_blobs_from(const crypto::hash& h, size_t coun return true; } +std::vector<crypto::hash> BlockchainLMDB::get_txids_loose(const crypto::hash& txid_template, std::uint32_t bits, uint64_t max_num_txs) +{ + LOG_PRINT_L3("BlockchainLMDB::" << __func__); + check_open(); + + std::vector<crypto::hash> matching_hashes; + + TXN_PREFIX_RDONLY(); // Start a read-only transaction + RCURSOR(tx_indices); // Open cursors to the tx_indices and txpool_meta databases + RCURSOR(txpool_meta); + + // Search on-chain and pool transactions together, starting with on-chain txs + MDB_cursor* cursor = m_cur_tx_indices; + MDB_val k = zerokval; // tx_indicies DB uses a dummy key + MDB_val_set(v, txid_template); // tx_indicies DB indexes data values by crypto::hash value on front + MDB_cursor_op op = MDB_GET_BOTH_RANGE; // Set the cursor to the first key/value pair >= the given key + bool doing_chain = true; // this variable tells us whether we are processing chain or pool txs + while (1) + { + const int get_result = mdb_cursor_get(cursor, &k, &v, op); + op = doing_chain ? MDB_NEXT_DUP : MDB_NEXT; // Set the cursor to the next key/value pair + if (get_result && get_result != MDB_NOTFOUND) + throw0(DB_ERROR(lmdb_error("DB error attempting to fetch txid range", get_result).c_str())); + + // In tx_indicies, the hash is stored at the data, in txpool_meta at the key + const crypto::hash* const p_dbtxid = (const crypto::hash*)(doing_chain ? v.mv_data : k.mv_data); + + // Check if we reached the end of a DB or the hashes no longer match the template + if (get_result == MDB_NOTFOUND || compare_hash32_reversed_nbits(txid_template, *p_dbtxid, bits)) + { + if (doing_chain) // done with chain processing, switch to pool processing + { + k.mv_size = sizeof(crypto::hash); // txpool_meta DB is indexed using crypto::hash as keys + k.mv_data = (void*) txid_template.data; + cursor = m_cur_txpool_meta; // switch databases + op = MDB_SET_RANGE; // Set the cursor to the first key >= the given key + doing_chain = false; + continue; + } + break; // if we get to this point, then we finished pool processing and we are done + } + else if (matching_hashes.size() >= max_num_txs && max_num_txs != 0) + throw0(TX_EXISTS("number of tx hashes in template range exceeds maximum")); + + matching_hashes.push_back(*p_dbtxid); + } + + TXN_POSTFIX_RDONLY(); // End the read-only transaction + + return matching_hashes; +} + bool BlockchainLMDB::get_blocks_from(uint64_t start_height, size_t min_block_count, size_t max_block_count, size_t max_tx_count, size_t max_size, std::vector<std::pair<std::pair<cryptonote::blobdata, crypto::hash>, std::vector<std::pair<crypto::hash, cryptonote::blobdata>>>>& blocks, bool pruned, bool skip_coinbase, bool get_miner_tx_hash) const { LOG_PRINT_L3("BlockchainLMDB::" << __func__); diff --git a/src/blockchain_db/lmdb/db_lmdb.h b/src/blockchain_db/lmdb/db_lmdb.h index c352458b4..95e7b2aa4 100644 --- a/src/blockchain_db/lmdb/db_lmdb.h +++ b/src/blockchain_db/lmdb/db_lmdb.h @@ -262,6 +262,8 @@ public: virtual bool get_prunable_tx_blob(const crypto::hash& h, cryptonote::blobdata &tx) const; virtual bool get_prunable_tx_hash(const crypto::hash& tx_hash, crypto::hash &prunable_hash) const; + virtual std::vector<crypto::hash> get_txids_loose(const crypto::hash& h, std::uint32_t bits, uint64_t max_num_txs = 0); + virtual uint64_t get_tx_count() const; virtual std::vector<transaction> get_tx_list(const std::vector<crypto::hash>& hlist) const; diff --git a/src/blockchain_db/testdb.h b/src/blockchain_db/testdb.h index 946f26270..a27183b2c 100644 --- a/src/blockchain_db/testdb.h +++ b/src/blockchain_db/testdb.h @@ -71,6 +71,7 @@ public: virtual bool get_pruned_tx_blob(const crypto::hash& h, cryptonote::blobdata &tx) const override { return false; } virtual bool get_pruned_tx_blobs_from(const crypto::hash& h, size_t count, std::vector<cryptonote::blobdata> &bd) const override { return false; } virtual bool get_blocks_from(uint64_t start_height, size_t min_block_count, size_t max_block_count, size_t max_tx_count, size_t max_size, std::vector<std::pair<std::pair<cryptonote::blobdata, crypto::hash>, std::vector<std::pair<crypto::hash, cryptonote::blobdata>>>>& blocks, bool pruned, bool skip_coinbase, bool get_miner_tx_hash) const override { return false; } + virtual std::vector<crypto::hash> get_txids_loose(const crypto::hash& h, std::uint32_t bits, uint64_t max_num_txs = 0) override { return {}; } virtual bool get_prunable_tx_blob(const crypto::hash& h, cryptonote::blobdata &tx) const override { return false; } virtual bool get_prunable_tx_hash(const crypto::hash& tx_hash, crypto::hash &prunable_hash) const override { return false; } virtual uint64_t get_block_height(const crypto::hash& h) const override { return 0; } 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); diff --git a/src/rpc/core_rpc_server.cpp b/src/rpc/core_rpc_server.cpp index 03e9ec494..a6162c3f9 100644 --- a/src/rpc/core_rpc_server.cpp +++ b/src/rpc/core_rpc_server.cpp @@ -3535,6 +3535,82 @@ namespace cryptonote return true; } //------------------------------------------------------------------------------------------------------------------------------ + bool core_rpc_server::on_get_txids_loose(const COMMAND_RPC_GET_TXIDS_LOOSE::request& req, COMMAND_RPC_GET_TXIDS_LOOSE::response& res, epee::json_rpc::error& error_resp, const connection_context *ctx) + { + RPC_TRACKER(get_txids_loose); + + // Maybe don't use bootstrap since this endpoint is meant to retreive TXIDs w/ k-anonymity, + // so shunting this request to a random node seems counterproductive. + +#if BYTE_ORDER == LITTLE_ENDIAN + const uint64_t max_num_txids = RESTRICTED_SPENT_KEY_IMAGES_COUNT * (m_restricted ? 1 : 10); + + // Sanity check parameters + if (req.num_matching_bits > 256) + { + error_resp.code = CORE_RPC_ERROR_CODE_WRONG_PARAM; + error_resp.message = "There are only 256 bits in a hash, you gave too many"; + return false; + } + + // Attempt to guess when bit count is too low before fetching, within a certain margin of error + const uint64_t num_txs_ever = m_core.get_blockchain_storage().get_db().get_tx_count(); + const uint64_t num_expected_fetch = (num_txs_ever >> std::min((int) req.num_matching_bits, 63)); + const uint64_t max_num_txids_with_margin = 2 * max_num_txids; + if (num_expected_fetch > max_num_txids_with_margin) + { + error_resp.code = CORE_RPC_ERROR_CODE_WRONG_PARAM; + error_resp.message = "Trying to search with too few matching bits, detected before fetching"; + return false; + } + + // Convert txid template to a crypto::hash + crypto::hash search_hash; + if (!epee::string_tools::hex_to_pod(req.txid_template, search_hash)) + { + error_resp.code = CORE_RPC_ERROR_CODE_WRONG_PARAM; + error_resp.message = "Could not decode hex txid"; + return false; + } + // Check that txid template is zeroed correctly for number of given matchign bits + else if (search_hash != make_hash32_loose_template(req.num_matching_bits, search_hash)) + { + error_resp.code = CORE_RPC_ERROR_CODE_WRONG_PARAM; + error_resp.message = "Txid template is not zeroed correctly for number of bits. You could be leaking true txid!"; + return false; + } + + try + { + // Do the DB fetch + const auto txids = m_core.get_blockchain_storage().get_db().get_txids_loose(search_hash, req.num_matching_bits, max_num_txids); + // Fill out response form + for (const auto& txid : txids) + res.txids.emplace_back(epee::string_tools::pod_to_hex(txid)); + } + catch (const TX_EXISTS&) + { + error_resp.code = CORE_RPC_ERROR_CODE_WRONG_PARAM; + error_resp.message = "Trying to search with too few matching bits"; + return false; + } + catch (const std::exception& e) + { + error_resp.code = CORE_RPC_ERROR_CODE_INTERNAL_ERROR; + error_resp.message = std::string("Error during get_txids_loose: ") + e.what(); + return false; + } + + res.status = CORE_RPC_STATUS_OK; + return true; +#else // BYTE_ORDER == BIG_ENDIAN + // BlockchainLMDB::compare_hash32 has different key ordering (thus different txid templates) on BE systems + error_resp.code = CORE_RPC_ERROR_CODE_INTERNAL_ERROR; + error_resp.message = "Due to implementation details, this feature is not available on big-endian daemons"; + return false; +#endif + } + //------------------------------------------------------------------------------------------------------------------------------ bool core_rpc_server::on_rpc_access_submit_nonce(const COMMAND_RPC_ACCESS_SUBMIT_NONCE::request& req, COMMAND_RPC_ACCESS_SUBMIT_NONCE::response& res, epee::json_rpc::error& error_resp, const connection_context *ctx) { RPC_TRACKER(rpc_access_submit_nonce); diff --git a/src/rpc/core_rpc_server.h b/src/rpc/core_rpc_server.h index 790d5eb23..7c31d2539 100644 --- a/src/rpc/core_rpc_server.h +++ b/src/rpc/core_rpc_server.h @@ -178,6 +178,7 @@ namespace cryptonote MAP_JON_RPC_WE("get_output_distribution", on_get_output_distribution, COMMAND_RPC_GET_OUTPUT_DISTRIBUTION) MAP_JON_RPC_WE_IF("prune_blockchain", on_prune_blockchain, COMMAND_RPC_PRUNE_BLOCKCHAIN, !m_restricted) MAP_JON_RPC_WE_IF("flush_cache", on_flush_cache, COMMAND_RPC_FLUSH_CACHE, !m_restricted) + MAP_JON_RPC_WE("get_txids_loose", on_get_txids_loose, COMMAND_RPC_GET_TXIDS_LOOSE) MAP_JON_RPC_WE("rpc_access_info", on_rpc_access_info, COMMAND_RPC_ACCESS_INFO) MAP_JON_RPC_WE("rpc_access_submit_nonce",on_rpc_access_submit_nonce, COMMAND_RPC_ACCESS_SUBMIT_NONCE) MAP_JON_RPC_WE("rpc_access_pay", on_rpc_access_pay, COMMAND_RPC_ACCESS_PAY) @@ -255,6 +256,7 @@ namespace cryptonote bool on_get_output_distribution(const COMMAND_RPC_GET_OUTPUT_DISTRIBUTION::request& req, COMMAND_RPC_GET_OUTPUT_DISTRIBUTION::response& res, epee::json_rpc::error& error_resp, const connection_context *ctx = NULL); bool on_prune_blockchain(const COMMAND_RPC_PRUNE_BLOCKCHAIN::request& req, COMMAND_RPC_PRUNE_BLOCKCHAIN::response& res, epee::json_rpc::error& error_resp, const connection_context *ctx = NULL); bool on_flush_cache(const COMMAND_RPC_FLUSH_CACHE::request& req, COMMAND_RPC_FLUSH_CACHE::response& res, epee::json_rpc::error& error_resp, const connection_context *ctx = NULL); + bool on_get_txids_loose(const COMMAND_RPC_GET_TXIDS_LOOSE::request& req, COMMAND_RPC_GET_TXIDS_LOOSE::response& res, epee::json_rpc::error& error_resp, const connection_context *ctx = NULL); bool on_rpc_access_info(const COMMAND_RPC_ACCESS_INFO::request& req, COMMAND_RPC_ACCESS_INFO::response& res, epee::json_rpc::error& error_resp, const connection_context *ctx = NULL); bool on_rpc_access_submit_nonce(const COMMAND_RPC_ACCESS_SUBMIT_NONCE::request& req, COMMAND_RPC_ACCESS_SUBMIT_NONCE::response& res, epee::json_rpc::error& error_resp, const connection_context *ctx = NULL); bool on_rpc_access_pay(const COMMAND_RPC_ACCESS_PAY::request& req, COMMAND_RPC_ACCESS_PAY::response& res, epee::json_rpc::error& error_resp, const connection_context *ctx = NULL); diff --git a/src/rpc/core_rpc_server_commands_defs.h b/src/rpc/core_rpc_server_commands_defs.h index 819d77c1f..37f9b8f2f 100644 --- a/src/rpc/core_rpc_server_commands_defs.h +++ b/src/rpc/core_rpc_server_commands_defs.h @@ -2793,4 +2793,31 @@ namespace cryptonote typedef epee::misc_utils::struct_init<response_t> response; }; + struct COMMAND_RPC_GET_TXIDS_LOOSE + { + struct request_t: public rpc_request_base + { + std::string txid_template; + std::uint32_t num_matching_bits; + + BEGIN_KV_SERIALIZE_MAP() + KV_SERIALIZE_PARENT(rpc_request_base) + KV_SERIALIZE(txid_template) + KV_SERIALIZE(num_matching_bits) + END_KV_SERIALIZE_MAP() + }; + typedef epee::misc_utils::struct_init<request_t> request; + + struct response_t: public rpc_response_base + { + std::vector<std::string> txids; + + BEGIN_KV_SERIALIZE_MAP() + KV_SERIALIZE_PARENT(rpc_response_base) + KV_SERIALIZE(txids) + END_KV_SERIALIZE_MAP() + }; + typedef epee::misc_utils::struct_init<response_t> response; + }; + } diff --git a/tests/functional_tests/functional_tests_rpc.py b/tests/functional_tests/functional_tests_rpc.py index 9975cdfa2..7e4d49ffa 100755 --- a/tests/functional_tests/functional_tests_rpc.py +++ b/tests/functional_tests/functional_tests_rpc.py @@ -10,7 +10,11 @@ import string import os USAGE = 'usage: functional_tests_rpc.py <python> <srcdir> <builddir> [<tests-to-run> | all]' -DEFAULT_TESTS = ['address_book', 'bans', 'blockchain', 'cold_signing', 'daemon_info', 'get_output_distribution', 'integrated_address', 'mining', 'multisig', 'p2p', 'proofs', 'rpc_payment', 'sign_message', 'transfer', 'txpool', 'uri', 'validate_address', 'wallet'] +DEFAULT_TESTS = [ + 'address_book', 'bans', 'blockchain', 'cold_signing', 'daemon_info', 'get_output_distribution', + 'integrated_address', 'k_anonymity', 'mining', 'multisig', 'p2p', 'proofs', 'rpc_payment', + 'sign_message', 'transfer', 'txpool', 'uri', 'validate_address', 'wallet' +] try: python = sys.argv[1] srcdir = sys.argv[2] diff --git a/tests/functional_tests/k_anonymity.py b/tests/functional_tests/k_anonymity.py new file mode 100755 index 000000000..ffa670b4c --- /dev/null +++ b/tests/functional_tests/k_anonymity.py @@ -0,0 +1,314 @@ +#!/usr/bin/env python3 + +# Copyright (c) 2023, 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. + +from __future__ import print_function +import math +import random + +""" +Test the k-anonymity daemon RPC features: +* txid fetching by prefix +""" + +from framework.daemon import Daemon +from framework.wallet import Wallet + +seeds = [ + 'velvet lymph giddy number token physics poetry unquoted nibs useful sabotage limits benches lifestyle eden nitrogen anvil fewest avoid batch vials washing fences goat unquoted', + 'peeled mixture ionic radar utopia puddle buying illness nuns gadget river spout cavernous bounced paradise drunk looking cottage jump tequila melting went winter adjust spout', + 'tadpoles shrugged ritual exquisite deepest rest people musical farming otherwise shelter fabrics altitude seventh request tidy ivory diet vapidly syllabus logic espionage oozed opened people', + 'ocio charla pomelo humilde maduro geranio bruto moño admitir mil difícil diva lucir cuatro odisea riego bebida mueble cáncer puchero carbón poeta flor fruta fruta' +] + +pub_addrs = [ + '42ey1afDFnn4886T7196doS9GPMzexD9gXpsZJDwVjeRVdFCSoHnv7KPbBeGpzJBzHRCAs9UxqeoyFQMYbqSWYTfJJQAWDm', + '44Kbx4sJ7JDRDV5aAhLJzQCjDz2ViLRduE3ijDZu3osWKBjMGkV1XPk4pfDUMqt1Aiezvephdqm6YD19GKFD9ZcXVUTp6BW', + '45uQD4jzWwPazqr9QJx8CmFPN7a9RaEE8T4kULg6r8GzfcrcgKXshfYf8cezLWwmENHC9pDN2fGAUFmmdFxjeZSs3n671rz', + '48hKTTTMfuiW2gDkmsibERHCjTCpqyCCh57WcU4KBeqDSAw7dG7Ad1h7v8iJF4q59aDqBATg315MuZqVmkF89E3cLPrBWsi' +] + +CRYPTONOTE_MINED_MONEY_UNLOCK_WINDOW = 60 +CRYPTONOTE_DEFAULT_TX_SPENDABLE_AGE = 10 +RESTRICTED_SPENT_KEY_IMAGES_COUNT = 5000 + +def make_hash32_loose_template(txid, nbits): + txid_bytes = list(bytes.fromhex(txid)) + for i in reversed(range(32)): + mask_nbits = min(8, nbits) + mask = 256 - (1 << (8 - mask_nbits)) + nbits -= mask_nbits + txid_bytes[i] &= mask + return bytes(txid_bytes).hex() + +def txid_list_is_sorted_in_template_order(txids): + reversed_txid_bytes = [bytes(reversed(bytes.fromhex(txid))) for txid in txids] + return sorted(reversed_txid_bytes) == reversed_txid_bytes + +def txid_matches_template(txid, template, nbits): + txid_bytes = bytes.fromhex(txid) + template_bytes = bytes.fromhex(template) + for i in reversed(range(32)): + mask_nbits = min(8, nbits) + mask = 256 - (1 << (8 - mask_nbits)) + nbits -= mask_nbits + if 0 != ((txid_bytes[i] ^ template_bytes[i]) & mask): + return False + return True + +class KAnonymityTest: + def run_test(self): + self.reset() + self.create_wallets() + + # If each of the N wallets is making N-1 transfers the first round, each N wallets needs + # N-1 unlocked coinbase outputs + N = len(seeds) + self.mine_and_refresh(2 * N * (N - 1)) + self.mine_and_refresh(CRYPTONOTE_MINED_MONEY_UNLOCK_WINDOW) + + # Generate a bunch of transactions + NUM_ROUNDS = 10 + intermediate_mining_period = int(math.ceil(CRYPTONOTE_DEFAULT_TX_SPENDABLE_AGE / N)) * N + for i in range(NUM_ROUNDS): + self.transfer_around() + self.mine_and_refresh(intermediate_mining_period) + print("Wallets created {} transactions in {} rounds".format(len(self.wallet_txids), NUM_ROUNDS)) + + self.test_all_chain_txids() # Also gathers miner_txids + + self.test_get_txids_loose_chain_suite() + + self.test_get_txids_loose_pool_suite() + + self.test_bad_txid_templates() + + def reset(self): + print('Resetting blockchain') + daemon = Daemon() + res = daemon.get_height() + daemon.pop_blocks(res.height - 1) + daemon.flush_txpool() + self.wallet_txids = set() + self.total_blocks_mined = 0 + self.miner_txids = set() + self.pool_txids = set() + + def create_wallets(self): + print('Creating wallets') + assert len(seeds) == len(pub_addrs) + self.wallet = [None] * len(seeds) + for i in range(len(seeds)): + self.wallet[i] = Wallet(idx = i) + # close the wallet if any, will throw if none is loaded + try: self.wallet[i].close_wallet() + except: pass + res = self.wallet[i].restore_deterministic_wallet(seed = seeds[i]) + + def mine_and_refresh(self, num_blocks): + print("Mining {} blocks".format(num_blocks)) + daemon = Daemon() + + res = daemon.get_info() + old_height = res.height + + assert num_blocks % len(self.wallet) == 0 + assert len(self.wallet) == len(pub_addrs) + + for i in range(len(self.wallet)): + daemon.generateblocks(pub_addrs[i], num_blocks // len(self.wallet)) + + res = daemon.get_info() + new_height = res.height + assert new_height == old_height + num_blocks, "height {} -> {}".format(old_height, new_height) + + for i in range(len(self.wallet)): + self.wallet[i].refresh() + res = self.wallet[i].get_height() + assert res.height == new_height, "{} vs {}".format(res.height, new_height) + + self.wallet_txids.update(self.pool_txids) + self.pool_txids.clear() + self.total_blocks_mined += num_blocks + + def transfer_around(self): + N = len(self.wallet) + assert N == len(pub_addrs) + + print("Creating transfers b/t wallets") + + num_successful_transfers = 0 + fee_margin = 0.05 # 5% + for sender in range(N): + receivers = list((r for r in range(N) if r != sender)) + random.shuffle(receivers) + assert len(receivers) == N - 1 + for j, receiver in enumerate(receivers): + unlocked_balance = self.wallet[sender].get_balance().unlocked_balance + if 0 == unlocked_balance: + assert j != 0 # we want all wallets to start out with at least some funds + break + imperfect_starting_balance = unlocked_balance * (N - 1) / (N - 1 - j) * (1 - fee_margin) + transfer_amount = int(imperfect_starting_balance / (N - 1)) + assert transfer_amount < unlocked_balance + dst = {'address': pub_addrs[receiver], 'amount': transfer_amount} + res = self.wallet[sender].transfer([dst], get_tx_metadata = True) + tx_hex = res.tx_metadata + self.pool_txids.add(res.tx_hash) + res = self.wallet[sender].relay_tx(tx_hex) + self.wallet[sender].refresh() + num_successful_transfers += 1 + + print("Transferred {} times".format(num_successful_transfers)) + + def test_all_chain_txids(self): + daemon = Daemon() + + print("Grabbing all txids from the daemon and testing against known txids") + + # If assert stmt below fails, this test case needs to be rewritten to chunk the requests; + # there are simply too many txids on-chain to gather at once + expected_total_num_txids = len(self.wallet_txids) + self.total_blocks_mined + 1 # +1 for genesis coinbase tx + assert expected_total_num_txids <= RESTRICTED_SPENT_KEY_IMAGES_COUNT + + res = daemon.get_txids_loose('0' * 64, 0) + all_txids = res.txids + assert 'c88ce9783b4f11190d7b9c17a69c1c52200f9faaee8e98dd07e6811175177139' in all_txids # genesis coinbase tx + assert len(all_txids) == expected_total_num_txids, "{} {}".format(len(all_txids), expected_total_num_txids) + + assert txid_list_is_sorted_in_template_order(all_txids) + + for txid in self.wallet_txids: + assert txid in all_txids + + self.miner_txids = set(all_txids) - self.wallet_txids + + def test_get_txids_loose_success(self, txid, num_matching_bits): + daemon = Daemon() + + txid_template = make_hash32_loose_template(txid, num_matching_bits) + + res = daemon.get_txids_loose(txid_template, num_matching_bits) + assert 'txids' in res + txids = res.txids + + first_pool_index = 0 + while first_pool_index < len(txids): + if txids[first_pool_index] in self.pool_txids: + break + else: + first_pool_index += 1 + + chain_txids = txids[:first_pool_index] + pool_txids = txids[first_pool_index:] + + assert txid_list_is_sorted_in_template_order(chain_txids) + assert txid_list_is_sorted_in_template_order(pool_txids) + + # Assert we know where txids came from + for txid in chain_txids: + assert (txid in self.wallet_txids) or (txid in self.miner_txids) + for txid in pool_txids: + assert txid in self.pool_txids + + # Assert that all known txids were matched as they should've been + for txid in self.wallet_txids: + assert txid_matches_template(txid, txid_template, num_matching_bits) == (txid in chain_txids) + for txid in self.miner_txids: + assert txid_matches_template(txid, txid_template, num_matching_bits) == (txid in chain_txids) + for txid in self.pool_txids: + assert txid_matches_template(txid, txid_template, num_matching_bits) == (txid in pool_txids) + + def test_get_txids_loose_chain_suite(self): + daemon = Daemon() + + print("Testing grabbing on-chain txids loosely with all different bit sizes") + + # Assert pool empty + assert len(self.pool_txids) == 0 + res = daemon.get_transaction_pool_hashes() + assert not 'tx_hashes' in res or len(res.tx_hashes) == 0 + + assert len(self.wallet_txids) + + current_chain_txids = list(self.wallet_txids.union(self.miner_txids)) + for nbits in range(0, 256): + random_txid = random.choice(current_chain_txids) + self.test_get_txids_loose_success(random_txid, nbits) + + def test_get_txids_loose_pool_suite(self): + daemon = Daemon() + + print("Testing grabbing pool txids loosely with all different bit sizes") + + # Create transactions to pool + self.transfer_around() + + # Assert pool not empty + assert len(self.pool_txids) != 0 + res = daemon.get_transaction_pool_hashes() + assert 'tx_hashes' in res and set(res.tx_hashes) == self.pool_txids + + current_pool_txids = list(self.pool_txids) + for nbits in range(0, 256): + random_txid = random.choice(current_pool_txids) + self.test_get_txids_loose_success(random_txid, nbits) + + def test_bad_txid_templates(self): + daemon = Daemon() + + print("Making sure the daemon catches bad txid templates") + + test_cases = [ + ['q', 256], + ['a', 128], + ['69' * 32, 257], + ['0abcdef1234567890abcdef1234567890abcdef1234567890abcdef123456789', 0], + ['0abcdef1234567890abcdef1234567890abcdef1234567890abcdef123456789', 1], + ['0abcdef1234567890abcdef1234567890abcdef1234567890abcdef123456789', 2], + ['0abcdef1234567890abcdef1234567890abcdef1234567890abcdef123456789', 4], + ['0abcdef1234567890abcdef1234567890abcdef1234567890abcdef123456789', 8], + ['0abcdef1234567890abcdef1234567890abcdef1234567890abcdef123456789', 16], + ['0abcdef1234567890abcdef1234567890abcdef1234567890abcdef123456789', 32], + ['0abcdef1234567890abcdef1234567890abcdef1234567890abcdef123456789', 64], + ['0abcdef1234567890abcdef1234567890abcdef1234567890abcdef123456789', 128], + ['0abcdef1234567890abcdef1234567890abcdef1234567890abcdef123456789', 193], + ['0000000000000000000000000000000000000000000000000000000000000080', 0], + ['0000000000000000000000000000000000000000000000000000000000000007', 5], + ['00000000000000000000000000000000000000000000000000000000000000f7', 5], + ] + + for txid_template, num_matching_bits in test_cases: + ok = False + try: res = daemon.get_txids_loose(txid_template, num_matching_bits) + except: ok = True + assert ok, 'bad template didnt error: {} {}'.format(txid_template, num_matching_bits) + +if __name__ == '__main__': + KAnonymityTest().run_test() diff --git a/tests/unit_tests/lmdb.cpp b/tests/unit_tests/lmdb.cpp index c859439eb..c213577fb 100644 --- a/tests/unit_tests/lmdb.cpp +++ b/tests/unit_tests/lmdb.cpp @@ -30,10 +30,14 @@ #include <boost/range/algorithm/equal.hpp> #include <gtest/gtest.h> +#include "blockchain_db/lmdb/db_lmdb.h" +#include "cryptonote_basic/cryptonote_basic_impl.h" +#include "hex.h" #include "lmdb/database.h" #include "lmdb/table.h" #include "lmdb/transaction.h" #include "lmdb/util.h" +#include "string_tools.h" namespace { @@ -53,6 +57,24 @@ namespace MDB_val right_val = lmdb::to_val(right); return (*cmp)(&left_val, &right_val); } + + crypto::hash postfix_hex_to_hash(const std::string& hex) + { + if (hex.size() > 64) throw std::logic_error("postfix_hex_to_hash"); + std::string decoded_bytes; + if (!epee::from_hex::to_string(decoded_bytes, hex)) throw std::logic_error("postfix_hex_to_hash"); + crypto::hash res = crypto::null_hash; + memcpy(res.data + 32 - decoded_bytes.size(), decoded_bytes.data(), decoded_bytes.size()); + return res; + } + + void test_make_template(const std::string& input_hex, unsigned int nbits, const std::string& expected_hex) + { + const crypto::hash input = postfix_hex_to_hash(input_hex); + const crypto::hash expected = postfix_hex_to_hash(expected_hex); + const crypto::hash actual = cryptonote::make_hash32_loose_template(nbits, input); + ASSERT_EQ(expected, actual); + } } TEST(LMDB, Traits) @@ -401,4 +423,164 @@ TEST(LMDB, InvalidKeyIterator) EXPECT_FALSE(test2 != test1); } +TEST(LMDB_kanonymity, compare_hash32_reversed_nbits) +{ + static constexpr size_t NUM_RANDOM_HASHES = 128; + std::vector<crypto::hash> random_hashes; + random_hashes.reserve(500); + for (size_t i = 0; i < NUM_RANDOM_HASHES; ++i) + random_hashes.push_back(crypto::rand<crypto::hash>()); + + bool r = true; + + // Compare behavior of compare_hash32_reversed_nbits(nbits=256) to BlockchainLMDB::compare_hash32 + for (size_t i = 0; i < NUM_RANDOM_HASHES; ++i) + { + for (size_t j = 0; j < NUM_RANDOM_HASHES; ++j) + { + const crypto::hash& ha = random_hashes[i]; + const crypto::hash& hb = random_hashes[j]; + const MDB_val mva = {sizeof(crypto::hash), (void*)(&ha)}; + const MDB_val mvb = {sizeof(crypto::hash), (void*)(&hb)}; + const int expected = cryptonote::BlockchainLMDB::compare_hash32(&mva, &mvb); + const int actual = cryptonote::compare_hash32_reversed_nbits(ha, hb, 256); + if (actual != expected) + { + std::cerr << "Failed compare_hash32_reversed_nbits test case with hashes:" << std::endl; + std::cerr << " " << epee::string_tools::pod_to_hex(ha) << std::endl; + std::cerr << " " << epee::string_tools::pod_to_hex(hb) << std::endl; + r = false; + } + EXPECT_EQ(expected, actual); + } + } + + ASSERT_TRUE(r); + + const auto cmp_byte_rev = [](const crypto::hash& ha, const crypto::hash& hb, unsigned int nbytes) -> int + { + if (nbytes > sizeof(crypto::hash)) throw std::logic_error("can't compare with nbytes too big"); + const uint8_t* va = (const uint8_t*)ha.data; + const uint8_t* vb = (const uint8_t*)hb.data; + for (size_t i = 31; nbytes; --i, --nbytes) + { + if (va[i] < vb[i]) return -1; + else if (va[i] > vb[i]) return 1; + } + return 0; + }; + + // Test partial hash compares w/o partial bytes + for (size_t i = 0; i < NUM_RANDOM_HASHES; ++i) + { + for (size_t j = 0; j < NUM_RANDOM_HASHES; ++j) + { + for (unsigned int nbytes = 0; nbytes <= 32; ++nbytes) + { + const crypto::hash& ha = random_hashes[i]; + const crypto::hash& hb = random_hashes[j]; + const int expected = cmp_byte_rev(ha, hb, nbytes); + const int actual = cryptonote::compare_hash32_reversed_nbits(ha, hb, nbytes * 8); + if (actual != expected) + { + std::cerr << "Failed compare_hash32_reversed_nbits test case with hashes and args:" << std::endl; + std::cerr << " " << epee::string_tools::pod_to_hex(ha) << std::endl; + std::cerr << " " << epee::string_tools::pod_to_hex(hb) << std::endl; + std::cerr << " nbytes=" << nbytes << std::endl; + r = false; + } + EXPECT_EQ(expected, actual); + } + } + } + + ASSERT_TRUE(r); + + // Test partial hash compares w/ partial bytes + for (size_t i = 0; i < NUM_RANDOM_HASHES; ++i) + { + const crypto::hash& ha = random_hashes[i]; + for (size_t modnbytes = 0; modnbytes < 32; ++modnbytes) + { + for (size_t modbitpos = 0; modbitpos < 8; ++modbitpos) + { + const size_t modbytepos = 31 - modnbytes; + const uint8_t mask = 1 << modbitpos; + const bool bit_was_zero = 0 == (static_cast<uint8_t>(ha.data[modbytepos]) & mask); + const unsigned int modnbits = modnbytes * 8 + (7 - modbitpos); + + // Create modified random hash by flipping one bit + crypto::hash hb = ha; + hb.data[modbytepos] = static_cast<uint8_t>(hb.data[modbytepos]) ^ mask; + + for (unsigned int cmpnbits = 0; cmpnbits <= 256; ++cmpnbits) + { + const int expected = cmpnbits <= modnbits ? 0 : bit_was_zero ? -1 : 1; + const int actual = cryptonote::compare_hash32_reversed_nbits(ha, hb, cmpnbits); + if (actual != expected) + { + std::cerr << "Failed compare_hash32_reversed_nbits test case with hashes and args:" << std::endl; + std::cerr << " " << epee::string_tools::pod_to_hex(ha) << std::endl; + std::cerr << " " << epee::string_tools::pod_to_hex(hb) << std::endl; + std::cerr << " modnbytes=" << modnbytes << std::endl; + std::cerr << " modbitpos=" << modbitpos << std::endl; + std::cerr << " cmpnbits=" << cmpnbits << std::endl; + r = false; + } + EXPECT_EQ(expected, actual); + } + } + } + } + + ASSERT_TRUE(r); + // Test equality + for (size_t i = 0; i < NUM_RANDOM_HASHES; ++i) + { + const crypto::hash& ha = random_hashes[i]; + for (unsigned int nbits = 0; nbits <= 256; ++nbits) + { + const int actual = cryptonote::compare_hash32_reversed_nbits(ha, ha, nbits); + if (actual) + { + std::cerr << "Failed compare_hash32_reversed_nbits test case with hash and args:" << std::endl; + std::cerr << " " << epee::string_tools::pod_to_hex(ha) << std::endl; + std::cerr << " nbits=" << nbits << std::endl; + r = false; + } + EXPECT_EQ(0, actual); + } + } + +} + +TEST(LMDB_kanonymity, make_hash32_loose_template) +{ + const std::string example_1 = "0abcdef1234567890abcdef1234567890abcdef1234567890abcdef123456789"; + + test_make_template(example_1, 0, ""); + + test_make_template(example_1, 1, "80"); + test_make_template(example_1, 2, "80"); + test_make_template(example_1, 3, "80"); + test_make_template(example_1, 4, "80"); + test_make_template(example_1, 5, "88"); + test_make_template(example_1, 6, "88"); + test_make_template(example_1, 7, "88"); + test_make_template(example_1, 8, "89"); + + test_make_template(example_1, 9, "0089"); + test_make_template(example_1, 10, "4089"); + test_make_template(example_1, 11, "6089"); + test_make_template(example_1, 12, "6089"); + test_make_template(example_1, 13, "6089"); + test_make_template(example_1, 14, "6489"); + test_make_template(example_1, 15, "6689"); + test_make_template(example_1, 16, "6789"); + + test_make_template(example_1, 32, "23456789"); + test_make_template(example_1, 64, "0abcdef123456789"); + test_make_template(example_1, 128, "0abcdef1234567890abcdef123456789"); + test_make_template(example_1, 256, example_1); +} diff --git a/utils/python-rpc/framework/daemon.py b/utils/python-rpc/framework/daemon.py index 43a1aa469..c7831d1ee 100644 --- a/utils/python-rpc/framework/daemon.py +++ b/utils/python-rpc/framework/daemon.py @@ -590,6 +590,18 @@ class Daemon(object): } return self.rpc.send_json_rpc_request(flush_cache) + def get_txids_loose(self, txid_template, num_matching_bits): + get_txids_loose = { + 'method': 'get_txids_loose', + 'params': { + 'txid_template': txid_template, + 'num_matching_bits': num_matching_bits + }, + 'jsonrpc': '2.0', + 'id': '0' + } + return self.rpc.send_json_rpc_request(get_txids_loose) + def sync_txpool(self): sync_txpool = { 'method': 'sync_txpool', |