aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/Makefile.test.include2
-rw-r--r--src/addrman.cpp8
-rw-r--r--src/addrman.h11
-rw-r--r--src/random.cpp33
-rw-r--r--src/random.h66
-rw-r--r--src/test/addrman_tests.cpp9
-rw-r--r--src/test/prevector_tests.cpp8
-rw-r--r--src/test/random_tests.cpp21
-rw-r--r--src/test/test_bitcoin.cpp3
-rw-r--r--src/test/test_random.h8
10 files changed, 126 insertions, 43 deletions
diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index fe0ed59fe2..194fc0c249 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -57,8 +57,8 @@ BITCOIN_TESTS =\
test/policyestimator_tests.cpp \
test/pow_tests.cpp \
test/prevector_tests.cpp \
- test/random_tests.cpp \
test/raii_event_tests.cpp \
+ test/random_tests.cpp \
test/reverselock_tests.cpp \
test/rpc_tests.cpp \
test/sanity_tests.cpp \
diff --git a/src/addrman.cpp b/src/addrman.cpp
index b6ab4c6305..33a623c1f2 100644
--- a/src/addrman.cpp
+++ b/src/addrman.cpp
@@ -351,8 +351,8 @@ CAddrInfo CAddrMan::Select_(bool newOnly)
int nKBucket = RandomInt(ADDRMAN_TRIED_BUCKET_COUNT);
int nKBucketPos = RandomInt(ADDRMAN_BUCKET_SIZE);
while (vvTried[nKBucket][nKBucketPos] == -1) {
- nKBucket = (nKBucket + insecure_rand.rand32()) % ADDRMAN_TRIED_BUCKET_COUNT;
- nKBucketPos = (nKBucketPos + insecure_rand.rand32()) % ADDRMAN_BUCKET_SIZE;
+ nKBucket = (nKBucket + insecure_rand.randbits(ADDRMAN_TRIED_BUCKET_COUNT_LOG2)) % ADDRMAN_TRIED_BUCKET_COUNT;
+ nKBucketPos = (nKBucketPos + insecure_rand.randbits(ADDRMAN_BUCKET_SIZE_LOG2)) % ADDRMAN_BUCKET_SIZE;
}
int nId = vvTried[nKBucket][nKBucketPos];
assert(mapInfo.count(nId) == 1);
@@ -368,8 +368,8 @@ CAddrInfo CAddrMan::Select_(bool newOnly)
int nUBucket = RandomInt(ADDRMAN_NEW_BUCKET_COUNT);
int nUBucketPos = RandomInt(ADDRMAN_BUCKET_SIZE);
while (vvNew[nUBucket][nUBucketPos] == -1) {
- nUBucket = (nUBucket + insecure_rand.rand32()) % ADDRMAN_NEW_BUCKET_COUNT;
- nUBucketPos = (nUBucketPos + insecure_rand.rand32()) % ADDRMAN_BUCKET_SIZE;
+ nUBucket = (nUBucket + insecure_rand.randbits(ADDRMAN_NEW_BUCKET_COUNT_LOG2)) % ADDRMAN_NEW_BUCKET_COUNT;
+ nUBucketPos = (nUBucketPos + insecure_rand.randbits(ADDRMAN_BUCKET_SIZE_LOG2)) % ADDRMAN_BUCKET_SIZE;
}
int nId = vvNew[nUBucket][nUBucketPos];
assert(mapInfo.count(nId) == 1);
diff --git a/src/addrman.h b/src/addrman.h
index 6e5f946bf2..bb45ac91ea 100644
--- a/src/addrman.h
+++ b/src/addrman.h
@@ -136,13 +136,13 @@ public:
*/
//! total number of buckets for tried addresses
-#define ADDRMAN_TRIED_BUCKET_COUNT 256
+#define ADDRMAN_TRIED_BUCKET_COUNT_LOG2 8
//! total number of buckets for new addresses
-#define ADDRMAN_NEW_BUCKET_COUNT 1024
+#define ADDRMAN_NEW_BUCKET_COUNT_LOG2 10
//! maximum allowed number of entries in buckets for new and tried addresses
-#define ADDRMAN_BUCKET_SIZE 64
+#define ADDRMAN_BUCKET_SIZE_LOG2 6
//! over how many buckets entries with tried addresses from a single group (/16 for IPv4) are spread
#define ADDRMAN_TRIED_BUCKETS_PER_GROUP 8
@@ -171,6 +171,11 @@ public:
//! the maximum number of nodes to return in a getaddr call
#define ADDRMAN_GETADDR_MAX 2500
+//! Convenience
+#define ADDRMAN_TRIED_BUCKET_COUNT (1 << ADDRMAN_TRIED_BUCKET_COUNT_LOG2)
+#define ADDRMAN_NEW_BUCKET_COUNT (1 << ADDRMAN_NEW_BUCKET_COUNT_LOG2)
+#define ADDRMAN_BUCKET_SIZE (1 << ADDRMAN_BUCKET_SIZE_LOG2)
+
/**
* Stochastical (IP) address manager
*/
diff --git a/src/random.cpp b/src/random.cpp
index 8284f457c9..c1e313cbde 100644
--- a/src/random.cpp
+++ b/src/random.cpp
@@ -240,22 +240,16 @@ uint256 GetRandHash()
return hash;
}
-FastRandomContext::FastRandomContext(bool fDeterministic)
+void FastRandomContext::RandomSeed()
{
- // The seed values have some unlikely fixed points which we avoid.
- if (fDeterministic) {
- Rz = Rw = 11;
- } else {
- uint32_t tmp;
- do {
- GetRandBytes((unsigned char*)&tmp, 4);
- } while (tmp == 0 || tmp == 0x9068ffffU);
- Rz = tmp;
- do {
- GetRandBytes((unsigned char*)&tmp, 4);
- } while (tmp == 0 || tmp == 0x464fffffU);
- Rw = tmp;
- }
+ uint256 seed = GetRandHash();
+ rng.SetKey(seed.begin(), 32);
+ requires_seed = false;
+}
+
+FastRandomContext::FastRandomContext(const uint256& seed) : requires_seed(false), bytebuf_size(0), bitbuf_size(0)
+{
+ rng.SetKey(seed.begin(), 32);
}
bool Random_SanityCheck()
@@ -288,3 +282,12 @@ bool Random_SanityCheck()
} while (num_overwritten < NUM_OS_RANDOM_BYTES && tries < MAX_TRIES);
return (num_overwritten == NUM_OS_RANDOM_BYTES); /* If this failed, bailed out after too many tries */
}
+
+FastRandomContext::FastRandomContext(bool fDeterministic) : requires_seed(!fDeterministic), bytebuf_size(0), bitbuf_size(0)
+{
+ if (!fDeterministic) {
+ return;
+ }
+ uint256 seed;
+ rng.SetKey(seed.begin(), 32);
+}
diff --git a/src/random.h b/src/random.h
index 82886bec59..077f58c4d9 100644
--- a/src/random.h
+++ b/src/random.h
@@ -6,6 +6,7 @@
#ifndef BITCOIN_RANDOM_H
#define BITCOIN_RANDOM_H
+#include "crypto/chacha20.h"
#include "uint256.h"
#include <stdint.h>
@@ -33,21 +34,68 @@ void GetStrongRandBytes(unsigned char* buf, int num);
* This class is not thread-safe.
*/
class FastRandomContext {
+private:
+ bool requires_seed;
+ ChaCha20 rng;
+
+ unsigned char bytebuf[64];
+ int bytebuf_size;
+
+ uint64_t bitbuf;
+ int bitbuf_size;
+
+ void RandomSeed();
+
+ void FillByteBuffer()
+ {
+ if (requires_seed) {
+ RandomSeed();
+ }
+ rng.Output(bytebuf, sizeof(bytebuf));
+ bytebuf_size = sizeof(bytebuf);
+ }
+
+ void FillBitBuffer()
+ {
+ bitbuf = rand64();
+ bitbuf_size = 64;
+ }
+
public:
- explicit FastRandomContext(bool fDeterministic=false);
+ explicit FastRandomContext(bool fDeterministic = false);
- uint32_t rand32() {
- Rz = 36969 * (Rz & 65535) + (Rz >> 16);
- Rw = 18000 * (Rw & 65535) + (Rw >> 16);
- return (Rw << 16) + Rz;
+ /** Initialize with explicit seed (only for testing) */
+ explicit FastRandomContext(const uint256& seed);
+
+ /** Generate a random 64-bit integer. */
+ uint64_t rand64()
+ {
+ if (bytebuf_size < 8) FillByteBuffer();
+ uint64_t ret = ReadLE64(bytebuf + 64 - bytebuf_size);
+ bytebuf_size -= 8;
+ return ret;
}
- bool randbool() {
- return rand32() & 1;
+ /** Generate a random (bits)-bit integer. */
+ uint64_t randbits(int bits) {
+ if (bits == 0) {
+ return 0;
+ } else if (bits > 32) {
+ return rand64() >> (64 - bits);
+ } else {
+ if (bitbuf_size < bits) FillBitBuffer();
+ uint64_t ret = bitbuf & (~(uint64_t)0 >> (64 - bits));
+ bitbuf >>= bits;
+ bitbuf_size -= bits;
+ return ret;
+ }
}
- uint32_t Rz;
- uint32_t Rw;
+ /** Generate a random 32-bit integer. */
+ uint32_t rand32() { return randbits(32); }
+
+ /** Generate a random boolean. */
+ bool randbool() { return randbits(1); }
};
/* Number of random bytes returned by GetOSRand.
diff --git a/src/test/addrman_tests.cpp b/src/test/addrman_tests.cpp
index 5d1c5b78d1..39fa381dd0 100644
--- a/src/test/addrman_tests.cpp
+++ b/src/test/addrman_tests.cpp
@@ -203,10 +203,11 @@ BOOST_AUTO_TEST_CASE(addrman_select)
BOOST_CHECK(addrman.size() == 7);
// Test 12: Select pulls from new and tried regardless of port number.
- BOOST_CHECK(addrman.Select().ToString() == "250.4.6.6:8333");
- BOOST_CHECK(addrman.Select().ToString() == "250.3.2.2:9999");
- BOOST_CHECK(addrman.Select().ToString() == "250.3.3.3:9999");
- BOOST_CHECK(addrman.Select().ToString() == "250.4.4.4:8333");
+ std::set<uint16_t> ports;
+ for (int i = 0; i < 20; ++i) {
+ ports.insert(addrman.Select().GetPort());
+ }
+ BOOST_CHECK_EQUAL(ports.size(), 3);
}
BOOST_AUTO_TEST_CASE(addrman_new_collisions)
diff --git a/src/test/prevector_tests.cpp b/src/test/prevector_tests.cpp
index bd8a7819a4..cfed5e347e 100644
--- a/src/test/prevector_tests.cpp
+++ b/src/test/prevector_tests.cpp
@@ -28,6 +28,7 @@ class prevector_tester {
typedef typename pretype::size_type Size;
bool passed = true;
FastRandomContext rand_cache;
+ uint256 rand_seed;
template <typename A, typename B>
@@ -183,13 +184,12 @@ public:
}
~prevector_tester() {
- BOOST_CHECK_MESSAGE(passed, "insecure_rand_Rz: "
- << rand_cache.Rz
- << ", insecure_rand_Rw: "
- << rand_cache.Rw);
+ BOOST_CHECK_MESSAGE(passed, "insecure_rand: " + rand_seed.ToString());
}
+
prevector_tester() {
seed_insecure_rand();
+ rand_seed = insecure_rand_seed;
rand_cache = insecure_rand_ctx;
}
};
diff --git a/src/test/random_tests.cpp b/src/test/random_tests.cpp
index d2c46c0daa..31b993cd38 100644
--- a/src/test/random_tests.cpp
+++ b/src/test/random_tests.cpp
@@ -15,5 +15,24 @@ BOOST_AUTO_TEST_CASE(osrandom_tests)
BOOST_CHECK(Random_SanityCheck());
}
-BOOST_AUTO_TEST_SUITE_END()
+BOOST_AUTO_TEST_CASE(fastrandom_tests)
+{
+ // Check that deterministic FastRandomContexts are deterministic
+ FastRandomContext ctx1(true);
+ FastRandomContext ctx2(true);
+
+ BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
+ BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
+ BOOST_CHECK_EQUAL(ctx1.rand64(), ctx2.rand64());
+ BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
+ BOOST_CHECK_EQUAL(ctx1.randbits(7), ctx2.randbits(7));
+ BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
+ BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
+ // Check that a nondeterministic ones are not
+ FastRandomContext ctx3;
+ FastRandomContext ctx4;
+ BOOST_CHECK(ctx3.rand64() != ctx4.rand64()); // extremely unlikely to be equal
+}
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/test_bitcoin.cpp b/src/test/test_bitcoin.cpp
index abaec45cd7..48593f62d5 100644
--- a/src/test/test_bitcoin.cpp
+++ b/src/test/test_bitcoin.cpp
@@ -27,7 +27,8 @@
#include <boost/filesystem.hpp>
#include <boost/thread.hpp>
-FastRandomContext insecure_rand_ctx(true);
+uint256 insecure_rand_seed = GetRandHash();
+FastRandomContext insecure_rand_ctx(insecure_rand_seed);
extern bool fPrintToConsole;
extern void noui_connect();
diff --git a/src/test/test_random.h b/src/test/test_random.h
index 4a1637ac72..318c44df4d 100644
--- a/src/test/test_random.h
+++ b/src/test/test_random.h
@@ -8,11 +8,17 @@
#include "random.h"
+extern uint256 insecure_rand_seed;
extern FastRandomContext insecure_rand_ctx;
static inline void seed_insecure_rand(bool fDeterministic = false)
{
- insecure_rand_ctx = FastRandomContext(fDeterministic);
+ if (fDeterministic) {
+ insecure_rand_seed = uint256();
+ } else {
+ insecure_rand_seed = GetRandHash();
+ }
+ insecure_rand_ctx = FastRandomContext(insecure_rand_seed);
}
static inline uint32_t insecure_rand(void)