FastRandomContext improvements and switch to ChaCha20 #9792

sipa · 2017-02-18T03:08:51Z

This switches FastRandomContext to use a ChaCha20-based random number generator. It also makes the class richer by adding support for getting single bits of entropy.

Benchmarks (also added) show that rand32 became around 5.25x slower on my machine (from 1.5ns to 8ns), but the new randbool is 15% faster than the old one (1.3ns).

gmaxwell · 2017-02-18T03:14:57Z

src/addrman.cpp: nKBucket = (nKBucket + insecure_rand.rand32()) % ADDRMAN_TRIED_BUCKET_COUNT;
src/addrman.cpp: nKBucketPos = (nKBucketPos + insecure_rand.rand32()) % ADDRMAN_BUCKET_SIZE;
src/addrman.cpp: nUBucket = (nUBucket + insecure_rand.rand32()) % ADDRMAN_NEW_BUCKET_COUNT;
src/addrman.cpp: nUBucketPos = (nUBucketPos + insecure_rand.rand32()) % ADDRMAN_BUCKET_SIZE;
src/bench/checkqueue.cpp: p.resize(insecure_rand.rand32() % (PREVECTOR_SIZE*2));
src/net.h: vAddrToSend[insecure_rand.rand32() % vAddrToSend.size()] = _addr;

Usage wants a randrange a lot more than a rand32

jonasschnelli · 2017-02-19T19:31:27Z

src/test/crypto_tests.cpp

@@ -439,4 +440,29 @@ BOOST_AUTO_TEST_CASE(aes_cbc_testvectors) {
                  "b2eb05e2c39be9fcda6c19078c6a9d1b3f461796d6b0d6b2e0c2a72b4d80e644");
 }

+BOOST_AUTO_TEST_CASE(chacha20_testvector)


Maybe add all test vectors (only 5) from the IEFT draft specs: https://github.com/jonasschnelli/chacha20poly1305/blob/master/tests.c#L35

jonasschnelli · 2017-02-19T19:32:00Z

Concept ACK

sipa · 2017-02-20T06:48:51Z

Added randrange and the test vectors @jonasschnelli suggested.

TheBlueMatt · 2017-02-22T18:22:10Z

src/test/prevector_tests.cpp

@@ -183,11 +183,8 @@ class prevector_tester {
    }

    ~prevector_tester() {
-        BOOST_CHECK_MESSAGE(passed, "insecure_rand_Rz: "


Looks like this disabled a bunch of tests?

Oops, nice catch. Fixed.

TheBlueMatt · 2017-02-22T18:35:34Z

configure.ac

@@ -533,6 +533,9 @@ AC_CHECK_DECLS([bswap_16, bswap_32, bswap_64],,,
                 #include <byteswap.h>
                 #endif])

+AC_MSG_CHECKING(for __builtin_clzl)


Hmm...is it definitely the case that all the compilers we support have this? Can we not have some fallback for those that do not?

I don't know of any compilers that don't. I'd be happy to write a fallback if there is one that isn't.

I think MSVC doesn't.

TheBlueMatt · 2017-02-22T18:37:56Z

src/random.h

@@ -35,6 +35,7 @@ void GetStrongRandBytes(unsigned char* buf, int num);
 */
 class FastRandomContext {
 private:
+    bool requires_seed;


...except you never check requires_seed to do the actual seeding?

Fixed, and added a test to catch that.

gmaxwell · 2017-02-23T18:12:43Z

src/random.h

+    unsigned long randrange(unsigned long range)
+    {
+        --range;
+        int bits = 8 * sizeof(long) - __builtin_clzl(range);


CLZ is undefined for 0, a range of 1 is dumb but might be mechanically generated in some case. At a minimum there should be a comment that range must be greater than 1.

sipa · 2017-02-25T20:41:42Z

Added a wrapper for __builtin_clzl, added unit tests, and fixed a few edge cases.

gmaxwell · 2017-02-28T21:44:41Z

src/random.h

@@ -89,6 +90,16 @@ class FastRandomContext {
        }
    }

+    uint64_t randrange(uint64_t range)


This needs a comment that points out that range returned will be [0..range) and that range must not be zero.

sipa · 2017-03-29T18:31:23Z

Rebased.

TheBlueMatt · 2017-04-14T22:22:54Z

Looks good to me. I didnt re-verify the chacha code is correct, and dont know that the makefile changes are sane.

gmaxwell

utACK

laanwj · 2017-04-24T12:28:42Z

utACK 4fd2d2f

4fd2d2f Add a FastRandomContext::randrange and use it (Pieter Wuille) 1632922 Switch FastRandomContext to ChaCha20 (Pieter Wuille) e04326f Add ChaCha20 (Pieter Wuille) 663fbae FastRandom benchmark (Pieter Wuille) c21cbe6 Introduce FastRandomContext::randbool() (Pieter Wuille) Tree-SHA512: 7fff61e3f6d6dc6ac846ca643d877b377db609646dd401a0e8f50b052c6b9bcd2f5fc34de6bbf28f04afd1724f6279ee163ead5f37d724fb782a00239f35db1d

…ha20 4fd2d2f Add a FastRandomContext::randrange and use it (Pieter Wuille) 1632922 Switch FastRandomContext to ChaCha20 (Pieter Wuille) e04326f Add ChaCha20 (Pieter Wuille) 663fbae FastRandom benchmark (Pieter Wuille) c21cbe6 Introduce FastRandomContext::randbool() (Pieter Wuille) Tree-SHA512: 7fff61e3f6d6dc6ac846ca643d877b377db609646dd401a0e8f50b052c6b9bcd2f5fc34de6bbf28f04afd1724f6279ee163ead5f37d724fb782a00239f35db1d

Micro-benchmarking framework part 1 Cherry-picked from the following upstream PRs: - bitcoin/bitcoin#6733 - bitcoin/bitcoin#6770 - bitcoin/bitcoin#6892 - Excluding changes to `src/policy/policy.h` which we don't have yet. - bitcoin/bitcoin#7934 - Just the benchmark, not the performance improvements. - bitcoin/bitcoin#8039 - bitcoin/bitcoin#8107 - bitcoin/bitcoin#8115 - bitcoin/bitcoin#8914 - Required resolving several merge conflicts in code that had been refactored upstream. The changes were simple enough that I decided it was okay to impose merge conflicts on pulling in those refactors later. - bitcoin/bitcoin#9200 - bitcoin/bitcoin#9202 - Adds support for measuring CPU cycles, which is later removed in an upstream PR after the refactor. I am including it to reduce future merge conflicts. - bitcoin/bitcoin#9281 - Only changes to `src/bench/bench.cpp` - bitcoin/bitcoin#9498 - bitcoin/bitcoin#9712 - bitcoin/bitcoin#9547 - bitcoin/bitcoin#9505 - Just the benchmark, not the performance improvements. - bitcoin/bitcoin#9792 - Just the benchmark, not the performance improvements. - bitcoin/bitcoin#10272 - bitcoin/bitcoin#10395 - Only changes to `src/bench/` - bitcoin/bitcoin#10735 - Only changes to `src/bench/base58.cpp` - bitcoin/bitcoin#10963 - bitcoin/bitcoin#11303 - Only the benchmark backend change. - bitcoin/bitcoin#11562 - bitcoin/bitcoin#11646 - bitcoin/bitcoin#11654 This pulls in all changes to the micro-benchmark framework prior to December 2017, when it was rewritten. The rewrite depends on other upstream PRs we have not pulled in yet. This does not pull in all benchmarks prior to December 2017. It leaves out benchmarks that either test code we do not have yet (except for the `FastRandomContext` refactor, which I decided to pull in), or would require rewrites to work with our changes to the codebase.

3f3edde [Bench] Use PIVX address in Base58Decode test (random-zebra) 5a1be90 [Travis] Disable benchmark framework for trusty test (random-zebra) 1bd89ac Initialize recently introduced non-static class member lastCycles to zero in constructor (random-zebra) ec60671 Require a steady clock for bench with at least micro precision (random-zebra) 84069ce bench: prefer a steady clock if the resolution is no worse (random-zebra) 38367b1 bench: switch to std::chrono for time measurements (random-zebra) a24633a Remove countMaskInv caching in bench framework (random-zebra) 9e9bc22 Restore default format state of cout after printing with std::fixed/setprecision (random-zebra) 3dd559d Avoid static analyzer warnings regarding uninitialized arguments (random-zebra) e85f224 Replace boost::function with std::function (C++11) (random-zebra) 98c0857 Prevent warning: variable 'x' is uninitialized (random-zebra) 7f0d4b3 FastRandom benchmark (random-zebra) d9fa0c6 Add prevector destructor benchmark (random-zebra) e1527ba Assert that what might look like a possible division by zero is actually unreachable (random-zebra) e94cf15 bench: Fix initialization order in registration (random-zebra) 151c25f Basic CCheckQueue Benchmarks (random-zebra) 51aedbc Use std:thread:hardware_concurrency, instead of Boost, to determine available cores (random-zebra) d447613 Use real number of cores for default -par, ignore virtual cores (random-zebra) 9162a56 [Refactoring] Removed using namespace <xxx> from bench/ sources (random-zebra) 5c07f67 bench: Add support for measuring CPU cycles (random-zebra) 41ce1ed bench: Fix subtle counting issue when rescaling iteration count (random-zebra) 68ea794 Avoid integer division in the benchmark inner-most loop. (random-zebra) 3fa4f27 bench: Added base58 encoding/decoding benchmarks (random-zebra) 4442118 bench: Add crypto hash benchmarks (random-zebra) a5179b6 [Trivial] ensure minimal header conventions (random-zebra) 8607d6b Support very-fast-running benchmarks (random-zebra) 4aebb60 Simple benchmarking framework (random-zebra) Pull request description: Introduces the benchmarking framework, loosely based on google's micro-benchmarking library (https://github.com/google/benchmark), ported from Bitcoin, up to 0.16. The benchmark framework is hard-coded to run each benchmark for one wall-clock second, and then spits out .csv-format timing information to stdout. Backported PR: - bitcoin#6733 - bitcoin#6770 - bitcoin#6892 - bitcoin#8039 - bitcoin#8107 - bitcoin#8115 - bitcoin#9200 - bitcoin#9202 - bitcoin#9281 - bitcoin#6361 - bitcoin#10271 - bitcoin#9498 - bitcoin#9712 - bitcoin#9547 - bitcoin#9505 (benchmark only. Rest was in #1557) - bitcoin#9792 (benchmark only. Rest was in #643) - bitcoin#10272 - bitcoin#10395 (base58 only) - bitcoin#10963 - bitcoin#11303 (first commit) - bitcoin#11562 - bitcoin#11646 - bitcoin#11654 Current output of `src/bench/bench_pivx`: ``` #Benchmark,count,min(ns),max(ns),average(ns),min_cycles,max_cycles,average_cycles Base58CheckEncode,131072,7697,8065,7785,20015,20971,20242 Base58Decode,294912,3305,3537,3454,8595,9198,8981 Base58Encode,180224,5498,6020,5767,14297,15652,14994 CCheckQueueSpeed,320,3159960,3535173,3352787,8216030,9191602,8717388 CCheckQueueSpeedPrevectorJob,96,9184484,11410840,10823070,23880046,29668680,28140445 FastRandom_1bit,320,3143690,4838162,3199156,8173726,12579373,8317941 FastRandom_32bit,60,17097612,17923669,17367440,44454504,46602306,45156079 PrevectorClear,3072,334741,366618,346731,870340,953224,901516 PrevectorDestructor,2816,344233,368912,357281,895022,959187,928948 RIPEMD160,288,3404503,3693917,3577774,8851850,9604334,9302363 SHA1,384,2718128,2891558,2802513,7067238,7518184,7286652 SHA256,176,6133760,6580005,6239866,15948035,17108376,16223916 SHA512,240,4251468,4358706,4313463,11054006,11332826,11215186 Sleep100ms,10,100221470,100302411,100239073,260580075,260790726,260625870 ``` NOTE: Not all the tests have been pulled yet (as we might not have the code being tested, or it would require rewrites to work with our different code base), but the framework is updated to December 2017. ACKs for top commit: Fuzzbawls: ACK 3f3edde Tree-SHA512: c283311a9accf6d2feeb93b185afa08589ebef3f18b6e86980dbc3647b9845f75ac9ecce2f1b08738d25ceac36596a2c89d41e4dbf3b463502aa695611aa1f8e

b886a4c Fix header guards using reserved identifiers (Dan Raviv) b389b3f speed up Unserialize_impl for prevector (Akio Nakamura) 13d2102 Minimal fix to slow prevector tests as stopgap measure (Jeremy Rubin) Pull request description: Backports bitcoin#12324. The `DeserializeAndCheckBlock` benchmark (introduced in #2146) shows a speedup of about 4% (not as much as the upstream PR, due to the optimizations already included in #2083). Cherry-picks also - bitcoin#8671 (with minimal changes to the random context, due to bitcoin#8914 and bitcoin#9792 being already ported out of order). - bitcoin#11151 ACKs for top commit: Fuzzbawls: utACK b886a4c furszy: utACK b886a4c and merging.. Tree-SHA512: f5de40e5acfb0b875d413d8995d71dd90489730fe4853f0be03d76a1c44ec95eaeb28c0c40d8e91906f23529ad26501bda4f9779ce466cd8603ed97f1662ca98

…tr4d FastRandomContext improvements and switch to ChaCha20 Backport of bitcoin/bitcoin#9792 Commits are recorded here in stack order - pick bitcoin/bitcoin@4fd2d2fc97 - pick bitcoin/bitcoin@16329224e7 - pick bitcoin/bitcoin@e04326fe66 - pick bitcoin/bitcoin@663fbae777 -- already applied in #3858, skip - pick bitcoin/bitcoin@c21cbe61c6 -- already applied in #3858, skip

fanquake added the Refactoring label Feb 18, 2017

jonasschnelli reviewed Feb 19, 2017

View reviewed changes

sipa force-pushed the chacha branch 2 times, most recently from 5b99a79 to b50ff22 Compare February 20, 2017 00:14

TheBlueMatt reviewed Feb 22, 2017

View reviewed changes

gmaxwell reviewed Feb 23, 2017

View reviewed changes

sipa force-pushed the chacha branch 2 times, most recently from 46f830b to 35c9510 Compare February 25, 2017 20:41

sipa force-pushed the chacha branch 3 times, most recently from 6591f94 to 3ea7f9e Compare February 27, 2017 22:21

gmaxwell reviewed Feb 28, 2017

View reviewed changes

sipa added 5 commits March 29, 2017 00:40

Introduce FastRandomContext::randbool()

c21cbe6

FastRandom benchmark

663fbae

Add ChaCha20

e04326f

Switch FastRandomContext to ChaCha20

1632922

Add a FastRandomContext::randrange and use it

4fd2d2f

sipa force-pushed the chacha branch from 3ea7f9e to 4fd2d2f Compare March 29, 2017 18:31

gmaxwell approved these changes Apr 15, 2017

View reviewed changes

laanwj merged commit 4fd2d2f into bitcoin:master Apr 24, 2017

paveljanik mentioned this pull request Apr 25, 2017

[Tests] Prevent warning: variable 'x' is uninitialized #10272

Merged

sipa mentioned this pull request Apr 29, 2017

Remove OpenSSL #10299

Closed

sickpig mentioned this pull request Oct 1, 2017

dbcache phase 3 enhancements BitcoinUnlimited/BitcoinUnlimited#785

Merged

str4d mentioned this pull request Feb 22, 2019

Micro-benchmarking framework part 1 zcash/zcash#3858

Merged

Warrows mentioned this pull request Jun 30, 2019

Bring PIVX random on par with bitcoin PIVX-Project/PIVX#799

Closed

42 tasks

sickpig mentioned this pull request Oct 24, 2019

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

Merged

random-zebra mentioned this pull request May 27, 2020

[Tests] Benchmarking Framework PIVX-Project/PIVX#1650

Merged

random-zebra mentioned this pull request Jan 19, 2021

[Core] Prevector Optimizations 2 PIVX-Project/PIVX#2148

Merged

This was referenced Feb 16, 2021

FastRandomContext improvements and switch to ChaCha20 zcash/zcash#4987

Closed

FastRandomContext improvements and switch to ChaCha20 zcash/zcash#4991

Merged

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

FastRandomContext improvements and switch to ChaCha20 #9792

FastRandomContext improvements and switch to ChaCha20 #9792

Uh oh!

Conversation

sipa commented Feb 18, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

gmaxwell commented Feb 18, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jonasschnelli commented Feb 19, 2017

Uh oh!

sipa commented Feb 20, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sipa commented Feb 25, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sipa commented Mar 29, 2017

Uh oh!

TheBlueMatt commented Apr 14, 2017

Uh oh!

gmaxwell left a comment

Choose a reason for hiding this comment

Uh oh!

laanwj commented Apr 24, 2017

Uh oh!

Uh oh!

sipa commented Feb 18, 2017 •

edited

Loading