Some simple improvements to the RNG code #14624

sipa · 2018-10-31T22:57:03Z

This improves a few minor issues with the RNG code:

Avoid calling GetRand*() functions (which currently invoke OpenSSL, later may switch to using our own RNG pool) inside loops in addrman, networking code, KnapsackSolver, and LimitOrphanSize
Fix a currently unreachable bug in FastRandomContext::randbytes.
Make a number of simplifications to the unit tests' randomness code (some tests unnecessarily used their own RNG or the OpenSSL one, instead of using the unit test specific insecure_rand_ctx).
As a precaution, make it illegal to copy a FastRandomContext.

DrahtBot · 2018-10-31T23:38:08Z

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#14626 (Select orphan transaction uniformly for eviction by sipa)
#14605 (Return of the Banman by dongcarl)
#13462 (Simplify common case of CHashWriter and drop SerializeHash by Empact)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

src/test/random_tests.cpp

practicalswift · 2018-11-01T10:00:18Z

Concept ACK

@sipa Regarding randbytes – very nice find! How was that issue found?

practicalswift · 2018-11-01T10:12:36Z

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.

How did you trigger this? I've built with -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC in the past and haven't encountered this. I also tried now and I was unable to reproduce.

Assuming a build with -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC – would the issue be triggered by make check or running the test suite?

I'm running:

$ g++ --version
g++ (Ubuntu 7.3.0-16ubuntu3) 7.3.0
$ dpkg -l | grep libstd
ii  libstdc++-7-dev:amd64                                       7.3.0-16ubuntu3                   amd64        GNU Standard C++ Library v3 (development files)
ii  libstdc++6:amd64                                            8-20180414-1ubuntu2               amd64        GNU Standard C++ Library v3

maflcko · 2018-11-01T14:00:15Z

Travis failure:

/bin/bash: line 1: 27706 Aborted                 (core dumped) test/test_bitcoin -l test_suite -t "`cat wallet/test/coinselector_tests.cpp | grep -E "(BOOST_FIXTURE_TEST_SUITE\\(|BOOST_AUTO_TEST_SUITE\\()" | cut -d '(' -f 2 | cut -d ',' -f 1 | cut -d ')' -f 1`" > wallet/test/coinselector_tests.cpp.log 2>&1
Running 4 test cases...
Test cases order is shuffled using seed: 1449235911
Entering test module "Bitcoin Test Suite"
wallet/test/coinselector_tests.cpp(17): Entering test suite "coinselector_tests"
wallet/test/coinselector_tests.cpp(569): Entering test case "SelectCoins_test"
wallet/test/coinselector_tests.cpp(569): Leaving test case "SelectCoins_test"; testing time: 3726243us
wallet/test/coinselector_tests.cpp(267): Entering test case "knapsack_solver_test"
/usr/include/c++/7/debug/safe_iterator.h:374:
Error: attempt to advance a past-the-end iterator 1 steps, which falls 
outside its valid range.
Objects involved in the operation:
    iterator @ 0x0x7fff06875e20 {
      type = __gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<OutputGroup*, std::__cxx1998::vector<OutputGroup, std::allocator<OutputGroup> > >, std::__debug::vector<OutputGroup, std::allocator<OutputGroup> > > (mutable iterator);
      state = past-the-end;
      references sequence with type 'std::__debug::vector<OutputGroup, std::allocator<OutputGroup> >' @ 0x0x7fff068766e0
    }
unknown location(0): fatal error: in "coinselector_tests/knapsack_solver_test": signal: SIGABRT (application abort requested)
wallet/test/coinselector_tests.cpp(281): last checkpoint
wallet/test/coinselector_tests.cpp(267): Leaving test case "knapsack_solver_test"; testing time: 78734us
wallet/test/coinselector_tests.cpp(122): Entering test case "bnb_search_test"
test_bitcoin: key.cpp:344: void ECC_Start(): Assertion `secp256k1_context_sign == nullptr' failed.
unknown location(0): fatal error: in "coinselector_tests/bnb_search_test": signal: SIGABRT (application abort requested)
wallet/test/coinselector_tests.cpp(122): last checkpoint: "bnb_search_test" fixture entry.
wallet/test/coinselector_tests.cpp(122): Leaving test case "bnb_search_test"; testing time: 271us
wallet/test/coinselector_tests.cpp(546): Entering test case "ApproximateBestSubset"
test_bitcoin: key.cpp:344: void ECC_Start(): Assertion `secp256k1_context_sign == nullptr' failed.
unknown location(0): fatal error: in "coinselector_tests/ApproximateBestSubset": signal: SIGABRT (application abort requested)
wallet/test/coinselector_tests.cpp(546): last checkpoint: "ApproximateBestSubset" fixture entry.
wallet/test/coinselector_tests.cpp(546): Leaving test case "ApproximateBestSubset"; testing time: 158us
wallet/test/coinselector_tests.cpp(17): Leaving test suite "coinselector_tests"; testing time: 3805580us
Leaving test module "Bitcoin Test Suite"; testing time: 3805777us
*** 3 failures are detected in the test module "Bitcoin Test Suite"

sipa · 2018-11-01T17:18:20Z

@practicalswift

@sipa Regarding randbytes – very nice find! How was that issue found?

In a follow-up change I was working on, which replaced more use sites of GetRand* functions with FastRandomContexts. One unit test failed which tested that the leveldb obfuscation key was not all zeroes...

How did you trigger this? I've built with -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC in the past and haven't encountered this. I also tried now and I was unable to reproduce.

Assuming a build with -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC – would the issue be triggered by make check or running the test suite?

Travis failed in an earlier version of this PR, in the Qt (!) unit tests.

@MarcoFalke

Travis failure:

Fixed now.

src/random.cpp

src/addrman.cpp

sipa · 2018-12-12T22:32:32Z

Rebased.

laanwj · 2018-12-13T12:58:16Z

all straightforward changes
utACK e414486

e414486 Do not permit copying FastRandomContexts (Pieter Wuille) 022cf47 Simplify testing RNG code (Pieter Wuille) fd3e797 Make unit tests use the insecure_rand_ctx exclusively (Pieter Wuille) 8d98d42 Bugfix: randbytes should seed when needed (non reachable issue) (Pieter Wuille) 273d025 Use a FastRandomContext in LimitOrphanTxSize (Pieter Wuille) 3db746b Introduce a Shuffle for FastRandomContext and use it in wallet and coinselection (Pieter Wuille) 8098379 Use a local FastRandomContext in a few more places in net (Pieter Wuille) 9695f31 Make addrman use its local RNG exclusively (Pieter Wuille) Pull request description: This improves a few minor issues with the RNG code: * Avoid calling `GetRand*()` functions (which currently invoke OpenSSL, later may switch to using our own RNG pool) inside loops in addrman, networking code, `KnapsackSolver`, and `LimitOrphanSize` * Fix a currently unreachable bug in `FastRandomContext::randbytes`. * Make a number of simplifications to the unit tests' randomness code (some tests unnecessarily used their own RNG or the OpenSSL one, instead of using the unit test specific `insecure_rand_ctx`). * As a precaution, make it illegal to copy a `FastRandomContext`. Tree-SHA512: 084c70b533ea68ca7adc0186c39f0b3e0a5c0ae43a12c37286e5d42086e056a8cd026dde61b12c0a296dc80f87fdc87fe303b9e8e6161b460ac2086cf7615f9d

…#3923) * random: Introduce std::shuffle alternative for FastRandomContext bitcoin@3db746b * random: change std::random_shuffle calls to std::shuffle https://en.cppreference.com/w/cpp/algorithm/random_shuffle (deprecated in c++14) * random: change FastRandomContext std::random_shuffle calls to shuffle * random: change last std::shuffle calls to Shuffle std::shuffle doesn't accept only two arguments so we use FastRandomContext() * llmq: use inherited FastRandomContext Co-authored-by: UdjinM6 <UdjinM6@users.noreply.github.com> * llmq: use inherited FastRandomContext Co-authored-by: UdjinM6 <UdjinM6@users.noreply.github.com> * Make the linter happy :) Co-authored-by: dustinface <35775977+xdustinface@users.noreply.github.com> Co-authored-by: UdjinM6 <UdjinM6@users.noreply.github.com> Co-authored-by: dustinface <35775977+xdustinface@users.noreply.github.com>

cecbf6c Use secure.h header for secure allocators (Fuzzbawls) d9f67da net: add ifaddrs.h include (fanquake) e906436 build: check if -lsocket is required with *ifaddrs (fanquake) 414f405 rand: only try and use freeifaddrs if available (fanquake) 3a039d6 build: avoid getifaddrs when unavailable (Cory Fields) 77bddd7 Use GetStrongRandBytes in gmp bignum initialization (Fuzzbawls) b70b26f Fix typo in comment in randomenv.cpp (Fuzzbawls) fec460c Put bounds on the number of CPUID leaves explored (Pieter Wuille) 41ab1ff Fix CPUID subleaf iteration (Pieter Wuille) 8a9bbb1 Move events_hasher into RNGState() (Pieter Wuille) 88c2ae5 random: mark RandAddPeriodic and SeedPeriodic as noexcept (fanquake) 81d382f doc: correct random.h docs after bitcoin#17270 (fanquake) f363ea9 Seed RNG with precision timestamps on receipt of net messages. (Matt Corallo) 7d6ddcb Run background seeding periodically instead of unpredictably (Pieter Wuille) 4679181 Add information gathered through getauxval() (Pieter Wuille) 88d97d0 Feed CPUID data into RNG (Pieter Wuille) 8f5b9c9 Use sysctl for seeding on MacOS/BSD (Pieter Wuille) 67de246 Gather additional entropy from the environment (Pieter Wuille) 6142e1f Seed randomness with process id / thread id / various clocks (Pieter Wuille) 7bde8b7 [MOVEONLY] Move cpuid code from random to compat/cpuid (Fuzzbawls) 52b5336 [MOVEONLY] Move perfmon data gathering to new randomenv module (Pieter Wuille) 27cf995 doc: minor corrections in random.cpp (fanquake) fccd2b8 doc: correct function name in ReportHardwareRand() (fanquake) 909473e Fix FreeBSD build by including utilstrencodings.h (Fuzzbawls) 630931f break circular dependency: random/sync -> util -> random/sync (Fuzzbawls) 5eed08c random: remove call to RAND_screen() (Windows only) (fanquake) ada9868 gui: remove OpenSSL PRNG seeding (Windows, Qt only) (fanquake) 22a7121 Fix non-deterministic coverage of test DoS_mapOrphans (Fuzzbawls) 79e7fd3 Add ChaCha20 bench (Jonas Schnelli) 6966aa9 Add ChaCha20 encryption option (XOR) (Jonas Schnelli) 28c9cdb tests: Add script checking for deterministic line coverage (practicalswift) c82e359 test: Make bloom tests deterministic (MarcoFalke) 7b33223 Document strenghtening (Pieter Wuille) 0190dec Add hash strengthening to the RNG (Pieter Wuille) 67e336d Use RdSeed when available, and reduce RdRand load (Pieter Wuille) 4ffda1f Document RNG design in random.h (Pieter Wuille) 2b6381e Use secure allocator for RNG state (Pieter Wuille) 080deb3 Encapsulate RNGState better (Pieter Wuille) 787d72f DRY: Implement GetRand using FastRandomContext::randrange (Pieter Wuille) 5bc2583 Sprinkle some sweet noexcepts over the RNG code (Pieter Wuille) 774899f Remove hwrand_initialized. (Pieter Wuille) 698d133 Switch all RNG code to the built-in PRNG. (Pieter Wuille) 038a45a Integrate util/system's CInit into RNGState (Fuzzbawls) 5f20e62 Abstract out seeding/extracting entropy into RNGState::MixExtract (Pieter Wuille) 298f97c Add thread safety annotations to RNG state (Pieter Wuille) 2326535 Rename some hardware RNG related functions (Pieter Wuille) d76ee83 Automatically initialize RNG on first use. (Pieter Wuille) 1a5dbc5 Don't log RandAddSeedPerfmon details (Pieter Wuille) 32e6c42 Simplify testing RNG code (Fuzzbawls) 972effa Make unit tests use the insecure_rand_ctx exclusively (Fuzzbawls) af52bf5 Use a FastRandomContext in LimitOrphanTxSize (Fuzzbawls) 746d466 Introduce a Shuffle for FastRandomContext and use it in wallet (Fuzzbawls) 1cdf124 Use a local FastRandomContext in a few more places in net (Fuzzbawls) e862564 Make addrman use its local RNG exclusively (Fuzzbawls) 94b2ead Make FastRandomContext support standard C++11 RNG interface (Pieter Wuille) Pull request description: This is a collection of upstream PRs that have been backported to bring our RNG (`src/random`) code more up-to-date. The following upstream PRs have been included here: - bitcoin#12742 - bitcoin#14624 - some of this had already been merged previously - bitcoin#14955 - bitcoin#15250 - bitcoin#15224 - bitcoin#15324 - bitcoin#15296 - bitcoin#15512 - bitcoin#16878 - bitcoin#17151 - bitcoin#17191 - bitcoin#13236 - bitcoin#13314 - bitcoin#17169 - bitcoin#17270 - omitted last commit as our testing framework doesn't support it currently - omitted bitcoin@64e1e02, to be pulled in after our time utility is updated in a separate PR - bitcoin#17573 - bitcoin#17507 - bitcoin#17670 - bitcoin#17527 - bitcoin#14127 - bitcoin#21486 ACKs for top commit: furszy: ACK cecbf6c with a minor nit that can be easily tackled later. random-zebra: rebase utACK cecbf6c and merging... Tree-SHA512: 3463b693cc9bddc1ec15228d264a794f5c2f159073fafa2ccf6e2563abfeb4369e49505f97ca84f2478ca792bd07b66d2cd83c58044d6a0cae6af42d22f5784b

e414486 Do not permit copying FastRandomContexts (Pieter Wuille) 022cf47 Simplify testing RNG code (Pieter Wuille) fd3e797 Make unit tests use the insecure_rand_ctx exclusively (Pieter Wuille) 8d98d42 Bugfix: randbytes should seed when needed (non reachable issue) (Pieter Wuille) 273d025 Use a FastRandomContext in LimitOrphanTxSize (Pieter Wuille) 3db746b Introduce a Shuffle for FastRandomContext and use it in wallet and coinselection (Pieter Wuille) 8098379 Use a local FastRandomContext in a few more places in net (Pieter Wuille) 9695f31 Make addrman use its local RNG exclusively (Pieter Wuille) Pull request description: This improves a few minor issues with the RNG code: * Avoid calling `GetRand*()` functions (which currently invoke OpenSSL, later may switch to using our own RNG pool) inside loops in addrman, networking code, `KnapsackSolver`, and `LimitOrphanSize` * Fix a currently unreachable bug in `FastRandomContext::randbytes`. * Make a number of simplifications to the unit tests' randomness code (some tests unnecessarily used their own RNG or the OpenSSL one, instead of using the unit test specific `insecure_rand_ctx`). * As a precaution, make it illegal to copy a `FastRandomContext`. Tree-SHA512: 084c70b533ea68ca7adc0186c39f0b3e0a5c0ae43a12c37286e5d42086e056a8cd026dde61b12c0a296dc80f87fdc87fe303b9e8e6161b460ac2086cf7615f9d

fanquake added the Refactoring label Oct 31, 2018

sipa force-pushed the 201810_randfast branch 4 times, most recently from c7105eb to 64e7360 Compare November 1, 2018 02:40

DrahtBot mentioned this pull request Nov 1, 2018

Select orphan transaction uniformly for eviction #14626

Merged

sipa force-pushed the 201810_randfast branch 2 times, most recently from 2deae8c to 5b7f385 Compare November 1, 2018 08:21

practicalswift reviewed Nov 1, 2018

View reviewed changes

src/test/random_tests.cpp Outdated Show resolved Hide resolved

sipa force-pushed the 201810_randfast branch 2 times, most recently from e53b92f to 66e69f2 Compare November 1, 2018 17:14

practicalswift reviewed Nov 2, 2018

View reviewed changes

src/random.cpp Outdated Show resolved Hide resolved

practicalswift reviewed Nov 2, 2018

View reviewed changes

src/addrman.cpp Outdated Show resolved Hide resolved

sipa force-pushed the 201810_randfast branch 6 times, most recently from ac9b9f9 to 8a652f5 Compare November 10, 2018 00:27

sipa added 4 commits December 12, 2018 14:22

Bugfix: randbytes should seed when needed (non reachable issue)

8d98d42

Make unit tests use the insecure_rand_ctx exclusively

fd3e797

Simplify testing RNG code

022cf47

Do not permit copying FastRandomContexts

e414486

sipa force-pushed the 201810_randfast branch from c53b821 to e414486 Compare December 12, 2018 22:32

DrahtBot removed the Needs rebase label Dec 12, 2018

laanwj added the Utils/log/libs label Dec 13, 2018

laanwj merged commit e414486 into bitcoin:master Dec 13, 2018

sipa mentioned this pull request Jan 17, 2019

Switch all RNG code to the built-in PRNG #14955

Merged

bitcoinhodler mentioned this pull request Apr 3, 2019

Improvement suggestions from Twitter GlacierProtocol/GlacierProtocol#64

Open

sickpig mentioned this pull request Oct 24, 2019

[port] Update BU random number generator BitcoinUnlimited/BitcoinUnlimited#1997

Merged

Fuzzbawls mentioned this pull request Mar 30, 2021

[Refactor] Update RNG code from upstream PIVX-Project/PIVX#2278

Merged

practicalswift mentioned this pull request Apr 29, 2021

refactor: Avoid UB in util/asmap (advance a dereferenceable iterator outside its valid range) #21802

Merged

kwvg pushed a commit to kwvg/dash that referenced this pull request Jul 2, 2021

merge bitcoin#14624: Some simple improvements to the RNG code

d21ef7c

kwvg pushed a commit to kwvg/dash that referenced this pull request Jul 2, 2021

merge bitcoin#14624: Some simple improvements to the RNG code

29a3d5b

kwvg added a commit to kwvg/dash that referenced this pull request Jul 2, 2021

merge bitcoin#14624: Some simple improvements to the RNG code

2b6e2d7

kwvg mentioned this pull request Jul 2, 2021

merge #16117, #18358, #17383, #21052, #14424, #15159, #14689, #14978, partial #16908, #14978, #13932: Auxillary Backports dashpay/dash#4229

Merged

kwvg added a commit to kwvg/dash that referenced this pull request Jul 4, 2021

merge bitcoin#14624: Some simple improvements to the RNG code

cce2966

kwvg added a commit to kwvg/dash that referenced this pull request Jul 9, 2021

merge bitcoin#14624: Some simple improvements to the RNG code

2614264

kwvg added a commit to kwvg/dash that referenced this pull request Jul 9, 2021

merge bitcoin#14624: Some simple improvements to the RNG code

b3dba89

kwvg added a commit to kwvg/dash that referenced this pull request Jul 15, 2021

merge bitcoin#14624: Some simple improvements to the RNG code

7dd3e9a

kwvg added a commit to kwvg/dash that referenced this pull request Jul 16, 2021

merge bitcoin#14624: Some simple improvements to the RNG code

0892afd

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Some simple improvements to the RNG code #14624

Some simple improvements to the RNG code #14624

Uh oh!

sipa commented Oct 31, 2018 •

edited

Loading

Uh oh!

DrahtBot commented Oct 31, 2018 •

edited

Loading

Uh oh!

Uh oh!

practicalswift commented Nov 1, 2018

Uh oh!

practicalswift commented Nov 1, 2018 •

edited

Loading

Uh oh!

maflcko commented Nov 1, 2018

Uh oh!

sipa commented Nov 1, 2018 •

edited

Loading

Uh oh!

Uh oh!

Uh oh!

sipa commented Dec 12, 2018

Uh oh!

laanwj commented Dec 13, 2018

Uh oh!

Uh oh!

Some simple improvements to the RNG code #14624

Some simple improvements to the RNG code #14624

Uh oh!

Conversation

sipa commented Oct 31, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Oct 31, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

Uh oh!

practicalswift commented Nov 1, 2018

Uh oh!

practicalswift commented Nov 1, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

maflcko commented Nov 1, 2018

Uh oh!

sipa commented Nov 1, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

sipa commented Dec 12, 2018

Uh oh!

laanwj commented Dec 13, 2018

Uh oh!

Uh oh!

sipa commented Oct 31, 2018 •

edited

Loading

DrahtBot commented Oct 31, 2018 •

edited

Loading

practicalswift commented Nov 1, 2018 •

edited

Loading

sipa commented Nov 1, 2018 •

edited

Loading