diff options
| -rw-r--r-- | src/random.h | 23 | ||||
| -rw-r--r-- | src/test/random_tests.cpp | 34 | ||||
| -rw-r--r-- | src/wallet/coinselection.cpp | 2 | ||||
| -rw-r--r-- | src/wallet/wallet.cpp | 4 |
4 files changed, 60 insertions, 3 deletions
diff --git a/src/random.h b/src/random.h index 3d5421eb3e..e7e5eb496a 100644 --- a/src/random.h +++ b/src/random.h @@ -130,6 +130,29 @@ public: inline uint64_t operator()() { return rand64(); } }; +/** More efficient than using std::shuffle on a FastRandomContext. + * + * This is more efficient as std::shuffle will consume entropy in groups of + * 64 bits at the time and throw away most. + * + * This also works around a bug in libstdc++ std::shuffle that may cause + * type::operator=(type&&) to be invoked on itself, which the library's + * debug mode detects and panics on. This is a known issue, see + * https://stackoverflow.com/questions/22915325/avoiding-self-assignment-in-stdshuffle + */ +template<typename I, typename R> +void Shuffle(I first, I last, R&& rng) +{ + while (first != last) { + size_t j = rng.randrange(last - first); + if (j) { + using std::swap; + swap(*first, *(first + j)); + } + ++first; + } +} + /* Number of random bytes returned by GetOSRand. * When changing this constant make sure to change all call sites, and make * sure that the underlying OS APIs for all platforms support the number. diff --git a/src/test/random_tests.cpp b/src/test/random_tests.cpp index 679e857ce6..9d69d1247d 100644 --- a/src/test/random_tests.cpp +++ b/src/test/random_tests.cpp @@ -75,8 +75,42 @@ BOOST_AUTO_TEST_CASE(stdrandom_test) for (int j = 1; j <= 10; ++j) { BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end()); } + Shuffle(test.begin(), test.end(), ctx); + for (int j = 1; j <= 10; ++j) { + BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end()); + } } } +/** Test that Shuffle reaches every permutation with equal probability. */ +BOOST_AUTO_TEST_CASE(shuffle_stat_test) +{ + FastRandomContext ctx(true); + uint32_t counts[5 * 5 * 5 * 5 * 5] = {0}; + for (int i = 0; i < 12000; ++i) { + int data[5] = {0, 1, 2, 3, 4}; + Shuffle(std::begin(data), std::end(data), ctx); + int pos = data[0] + data[1] * 5 + data[2] * 25 + data[3] * 125 + data[4] * 625; + ++counts[pos]; + } + unsigned int sum = 0; + double chi_score = 0.0; + for (int i = 0; i < 5 * 5 * 5 * 5 * 5; ++i) { + int i1 = i % 5, i2 = (i / 5) % 5, i3 = (i / 25) % 5, i4 = (i / 125) % 5, i5 = i / 625; + uint32_t count = counts[i]; + if (i1 == i2 || i1 == i3 || i1 == i4 || i1 == i5 || i2 == i3 || i2 == i4 || i2 == i5 || i3 == i4 || i3 == i5 || i4 == i5) { + BOOST_CHECK(count == 0); + } else { + chi_score += ((count - 100.0) * (count - 100.0)) / 100.0; + BOOST_CHECK(count > 50); + BOOST_CHECK(count < 150); + sum += count; + } + } + BOOST_CHECK(chi_score > 58.1411); // 99.9999% confidence interval + BOOST_CHECK(chi_score < 210.275); + BOOST_CHECK_EQUAL(sum, 12000); +} + BOOST_AUTO_TEST_SUITE_END() diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 5e955b8495..8a37f374a1 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -223,7 +223,7 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group std::vector<OutputGroup> applicable_groups; CAmount nTotalLower = 0; - random_shuffle(groups.begin(), groups.end(), GetRandInt); + Shuffle(groups.begin(), groups.end(), FastRandomContext()); for (const OutputGroup& group : groups) { if (group.m_value == nTargetValue) { diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index 829a1a2478..cea6564b4e 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -2462,7 +2462,7 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm // Cases where we have 11+ outputs all pointing to the same destination may result in // privacy leaks as they will potentially be deterministically sorted. We solve that by // explicitly shuffling the outputs before processing - std::shuffle(vCoins.begin(), vCoins.end(), FastRandomContext()); + Shuffle(vCoins.begin(), vCoins.end(), FastRandomContext()); } std::vector<OutputGroup> groups = GroupOutputs(vCoins, !coin_control.m_avoid_partial_spends); @@ -2922,7 +2922,7 @@ bool CWallet::CreateTransaction(interfaces::Chain::Lock& locked_chain, const std // Shuffle selected coins and fill in final vin txNew.vin.clear(); std::vector<CInputCoin> selected_coins(setCoins.begin(), setCoins.end()); - std::shuffle(selected_coins.begin(), selected_coins.end(), FastRandomContext()); + Shuffle(selected_coins.begin(), selected_coins.end(), FastRandomContext()); // Note how the sequence number is set to non-maxint so that // the nLockTime set above actually works. |