diff options
| -rw-r--r-- | src/common/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/common/apply_permutation.h | 68 | ||||
| -rw-r--r-- | src/cryptonote_core/blockchain.cpp | 39 | ||||
| -rw-r--r-- | src/cryptonote_core/cryptonote_tx_utils.cpp | 36 | ||||
| -rw-r--r-- | src/cryptonote_core/cryptonote_tx_utils.h | 2 | ||||
| -rw-r--r-- | tests/unit_tests/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | tests/unit_tests/apply_permutation.cpp | 74 |
7 files changed, 215 insertions, 6 deletions
diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt index 19d90253b..50887e35c 100644 --- a/src/common/CMakeLists.txt +++ b/src/common/CMakeLists.txt @@ -47,6 +47,7 @@ endif() set(common_headers) set(common_private_headers + apply_permutation.h base58.h boost_serialization_helper.h command_line.h diff --git a/src/common/apply_permutation.h b/src/common/apply_permutation.h new file mode 100644 index 000000000..4fd952686 --- /dev/null +++ b/src/common/apply_permutation.h @@ -0,0 +1,68 @@ +// Copyright (c) 2017, 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. +// +// Most of this file is originally copyright (c) 2017 Raymond Chen, Microsoft +// This algorithm is adapted from Raymond Chen's code: +// https://blogs.msdn.microsoft.com/oldnewthing/20170109-00/?p=95145 + +#include <vector> +#include <functional> +#include "misc_log_ex.h" + +namespace tools +{ + +template<typename F> +void apply_permutation(std::vector<size_t> permutation, const F &swap) +{ + //sanity check + for (size_t n = 0; n < permutation.size(); ++n) + CHECK_AND_ASSERT_THROW_MES(std::find(permutation.begin(), permutation.end(), n) != permutation.end(), "Bad permutation"); + + for (size_t i = 0; i < permutation.size(); ++i) + { + size_t current = i; + while (i != permutation[current]) + { + size_t next = permutation[current]; + swap(current, next); + permutation[current] = current; + current = next; + } + permutation[current] = current; + } +} + +template<typename T> +void apply_permutation(const std::vector<size_t> &permutation, std::vector<T> &v) +{ + CHECK_AND_ASSERT_THROW_MES(permutation.size() == v.size(), "Mismatched vector sizes"); + apply_permutation(permutation, [&v](size_t i0, size_t i1){ std::swap(v[i0], v[i1]); }); +} + +} diff --git a/src/cryptonote_core/blockchain.cpp b/src/cryptonote_core/blockchain.cpp index 274c8cd07..7ee88e430 100644 --- a/src/cryptonote_core/blockchain.cpp +++ b/src/cryptonote_core/blockchain.cpp @@ -2384,6 +2384,26 @@ bool Blockchain::check_tx_outputs(const transaction& tx, tx_verification_context } } + // from v7, sorted outs + if (m_hardfork->get_current_version() >= 7) { + const crypto::public_key *last_key = NULL; + for (size_t n = 0; n < tx.vout.size(); ++n) + { + const tx_out &o = tx.vout[n]; + if (o.target.type() == typeid(txout_to_key)) + { + const txout_to_key& out_to_key = boost::get<txout_to_key>(o.target); + if (last_key && memcmp(&out_to_key.key, last_key, sizeof(*last_key)) >= 0) + { + MERROR_VER("transaction has unsorted outputs"); + tvc.m_invalid_output = true; + return false; + } + last_key = &out_to_key.key; + } + } + } + return true; } //------------------------------------------------------------------ @@ -2552,6 +2572,25 @@ bool Blockchain::check_tx_inputs(transaction& tx, tx_verification_context &tvc, } } + // from v7, sorted ins + if (hf_version >= 7) { + const crypto::key_image *last_key_image = NULL; + for (size_t n = 0; n < tx.vin.size(); ++n) + { + const txin_v &txin = tx.vin[n]; + if (txin.type() == typeid(txin_to_key)) + { + const txin_to_key& in_to_key = boost::get<txin_to_key>(txin); + if (last_key_image && memcmp(&in_to_key.k_image, last_key_image, sizeof(*last_key_image)) >= 0) + { + MERROR_VER("transaction has unsorted inputs"); + tvc.m_verifivation_failed = true; + return false; + } + last_key_image = &in_to_key.k_image; + } + } + } auto it = m_check_txin_table.find(tx_prefix_hash); if(it == m_check_txin_table.end()) { diff --git a/src/cryptonote_core/cryptonote_tx_utils.cpp b/src/cryptonote_core/cryptonote_tx_utils.cpp index 94f069827..9b442029a 100644 --- a/src/cryptonote_core/cryptonote_tx_utils.cpp +++ b/src/cryptonote_core/cryptonote_tx_utils.cpp @@ -31,6 +31,7 @@ #include "include_base_utils.h" using namespace epee; +#include "common/apply_permutation.h" #include "cryptonote_tx_utils.h" #include "cryptonote_config.h" #include "cryptonote_basic/miner.h" @@ -156,7 +157,7 @@ namespace cryptonote return destinations[0].addr.m_view_public_key; } //--------------------------------------------------------------- - bool construct_tx_and_get_tx_key(const account_keys& sender_account_keys, const std::vector<tx_source_entry>& sources, const std::vector<tx_destination_entry>& destinations, std::vector<uint8_t> extra, transaction& tx, uint64_t unlock_time, crypto::secret_key &tx_key, bool rct) + bool construct_tx_and_get_tx_key(const account_keys& sender_account_keys, std::vector<tx_source_entry> sources, const std::vector<tx_destination_entry>& destinations, std::vector<uint8_t> extra, transaction& tx, uint64_t unlock_time, crypto::secret_key &tx_key, bool rct) { std::vector<rct::key> amount_keys; tx.set_null(); @@ -263,14 +264,25 @@ namespace cryptonote tx.vin.push_back(input_to_key); } - // "Shuffle" outs - std::vector<tx_destination_entry> shuffled_dsts(destinations); - std::random_shuffle(shuffled_dsts.begin(), shuffled_dsts.end(), [](unsigned int i) { return crypto::rand<unsigned int>() % i; }); + // sort ins by their key image + std::vector<size_t> ins_order(sources.size()); + for (size_t n = 0; n < sources.size(); ++n) + ins_order[n] = n; + std::sort(ins_order.begin(), ins_order.end(), [&](const size_t i0, const size_t i1) { + const txin_to_key &tk0 = boost::get<txin_to_key>(tx.vin[i0]); + const txin_to_key &tk1 = boost::get<txin_to_key>(tx.vin[i1]); + return memcmp(&tk0.k_image, &tk1.k_image, sizeof(tk0.k_image)) < 0; + }); + tools::apply_permutation(ins_order, [&] (size_t i0, size_t i1) { + std::swap(tx.vin[i0], tx.vin[i1]); + std::swap(in_contexts[i0], in_contexts[i1]); + std::swap(sources[i0], sources[i1]); + }); uint64_t summary_outs_money = 0; //fill outputs size_t output_index = 0; - for(const tx_destination_entry& dst_entr: shuffled_dsts) + for(const tx_destination_entry& dst_entr: destinations) { CHECK_AND_ASSERT_MES(dst_entr.amount > 0 || tx.version > 1, false, "Destination with wrong amount: " << dst_entr.amount); crypto::key_derivation derivation; @@ -297,6 +309,20 @@ namespace cryptonote summary_outs_money += dst_entr.amount; } + // sort outs by their public key + std::vector<size_t> outs_order(tx.vout.size()); + for (size_t n = 0; n < tx.vout.size(); ++n) + outs_order[n] = n; + std::sort(outs_order.begin(), outs_order.end(), [&](size_t i0, size_t i1) { + const txout_to_key &tk0 = boost::get<txout_to_key>(tx.vout[i0].target); + const txout_to_key &tk1 = boost::get<txout_to_key>(tx.vout[i1].target); + return memcmp(&tk0.key, &tk1.key, sizeof(tk0.key)) < 0; + }); + tools::apply_permutation(outs_order, [&] (size_t i0, size_t i1) { + std::swap(tx.vout[i0], tx.vout[i1]); + std::swap(amount_keys[i0], amount_keys[i1]); + }); + //check money if(summary_outs_money > summary_inputs_money ) { diff --git a/src/cryptonote_core/cryptonote_tx_utils.h b/src/cryptonote_core/cryptonote_tx_utils.h index 7aa7c280d..69254fb5f 100644 --- a/src/cryptonote_core/cryptonote_tx_utils.h +++ b/src/cryptonote_core/cryptonote_tx_utils.h @@ -71,7 +71,7 @@ namespace cryptonote //--------------------------------------------------------------- crypto::public_key get_destination_view_key_pub(const std::vector<tx_destination_entry> &destinations, const account_keys &sender_keys); bool construct_tx(const account_keys& sender_account_keys, const std::vector<tx_source_entry>& sources, const std::vector<tx_destination_entry>& destinations, std::vector<uint8_t> extra, transaction& tx, uint64_t unlock_time); - bool construct_tx_and_get_tx_key(const account_keys& sender_account_keys, const std::vector<tx_source_entry>& sources, const std::vector<tx_destination_entry>& destinations, std::vector<uint8_t> extra, transaction& tx, uint64_t unlock_time, crypto::secret_key &tx_key, bool rct = false); + bool construct_tx_and_get_tx_key(const account_keys& sender_account_keys, std::vector<tx_source_entry> sources, const std::vector<tx_destination_entry>& destinations, std::vector<uint8_t> extra, transaction& tx, uint64_t unlock_time, crypto::secret_key &tx_key, bool rct = false); bool generate_genesis_block( block& bl diff --git a/tests/unit_tests/CMakeLists.txt b/tests/unit_tests/CMakeLists.txt index f5e08b102..a7f120443 100644 --- a/tests/unit_tests/CMakeLists.txt +++ b/tests/unit_tests/CMakeLists.txt @@ -27,6 +27,7 @@ # THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. set(unit_tests_sources + apply_permutation.cpp address_from_url.cpp ban.cpp base58.cpp diff --git a/tests/unit_tests/apply_permutation.cpp b/tests/unit_tests/apply_permutation.cpp new file mode 100644 index 000000000..a008b74ee --- /dev/null +++ b/tests/unit_tests/apply_permutation.cpp @@ -0,0 +1,74 @@ +// Copyright (c) 2017, 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. + +#include "gtest/gtest.h" +#include "common/apply_permutation.h" + +TEST(apply_permutation, empty) +{ + std::vector<int> v = {}; + tools::apply_permutation({}, v); + ASSERT_EQ(v, std::vector<int>({})); +} + +TEST(apply_permutation, reorder) +{ + // 0 1 2 3 4 5 6 + std::vector<int> v = {8, 4, 6, 1, 7, 2, 4}; + tools::apply_permutation({3, 5, 6, 1, 2, 4, 0}, v); + ASSERT_EQ(v, std::vector<int>({1, 2, 4, 4, 6, 7, 8})); +} + +TEST(apply_permutation, bad_size) +{ + std::vector<int> v_large = {8, 4, 6, 1, 7, 2, 4, 9}; + std::vector<int> v_small = {8, 4, 6, 1, 7, 2}; + try + { + tools::apply_permutation({3, 5, 6, 1, 2, 4, 0}, v_large); + ASSERT_FALSE(true); + } + catch (const std::exception &e) {} + try + { + tools::apply_permutation({3, 5, 6, 1, 2, 4, 0}, v_small); + ASSERT_FALSE(true); + } + catch (const std::exception &e) {} +} + +TEST(apply_permutation, bad_permutation) +{ + std::vector<int> v = {8, 4, 6, 1, 7, 2, 4}; + try + { + tools::apply_permutation({3, 5, 6, 1, 2, 4, 1}, v); + ASSERT_FALSE(true); + } + catch (const std::exception &e) {} +} |