diff --git a/src/bloom.h b/src/bloom.h index 3e1141f761..99f147fdb8 100644 --- a/src/bloom.h +++ b/src/bloom.h @@ -1,149 +1,149 @@ // Copyright (c) 2012-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_BLOOM_H #define BITCOIN_BLOOM_H -#include "serialize.h" +#include #include #include class COutPoint; class CTransaction; class uint256; //! 20,000 items with fp rate < 0.1% or 10,000 items and <0.0001% static const uint32_t MAX_BLOOM_FILTER_SIZE = 36000; // bytes static const uint32_t MAX_HASH_FUNCS = 50; /** * First two bits of nFlags control how much IsRelevantAndUpdate actually * updates. The remaining bits are reserved. */ enum bloomflags { BLOOM_UPDATE_NONE = 0, BLOOM_UPDATE_ALL = 1, // Only adds outpoints to the filter if the output is a // pay-to-pubkey/pay-to-multisig script BLOOM_UPDATE_P2PUBKEY_ONLY = 2, BLOOM_UPDATE_MASK = 3, }; /** * BloomFilter is a probabilistic filter which SPV clients provide so that we * can filter the transactions we send them. * * This allows for significantly more efficient transaction and block downloads. * * Because bloom filters are probabilistic, a SPV node can increase the * false-positive rate, making us send it transactions which aren't actually * its, allowing clients to trade more bandwidth for more privacy by obfuscating * which keys are controlled by them. */ class CBloomFilter { private: std::vector vData; bool isFull; bool isEmpty; uint32_t nHashFuncs; uint32_t nTweak; uint8_t nFlags; uint32_t Hash(uint32_t nHashNum, const std::vector &vDataToHash) const; // Private constructor for CRollingBloomFilter, no restrictions on size CBloomFilter(uint32_t nElements, double nFPRate, uint32_t nTweak); friend class CRollingBloomFilter; public: /** * Creates a new bloom filter which will provide the given fp rate when * filled with the given number of elements. Note that if the given * parameters will result in a filter outside the bounds of the protocol * limits, the filter created will be as close to the given parameters as * possible within the protocol limits. This will apply if nFPRate is very * low or nElements is unreasonably high. nTweak is a constant which is * added to the seed value passed to the hash function. It should generally * always be a random value (and is largely only exposed for unit testing) * nFlags should be one of the BLOOM_UPDATE_* enums (not _MASK) */ CBloomFilter(uint32_t nElements, double nFPRate, uint32_t nTweak, uint8_t nFlagsIn); CBloomFilter() : isFull(true), isEmpty(false), nHashFuncs(0), nTweak(0), nFlags(0) {} ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(vData); READWRITE(nHashFuncs); READWRITE(nTweak); READWRITE(nFlags); } void insert(const std::vector &vKey); void insert(const COutPoint &outpoint); void insert(const uint256 &hash); bool contains(const std::vector &vKey) const; bool contains(const COutPoint &outpoint) const; bool contains(const uint256 &hash) const; void clear(); void reset(uint32_t nNewTweak); //! True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash //! functions is <= MAX_HASH_FUNCS (catch a filter which was just //! deserialized which was too big) bool IsWithinSizeConstraints() const; //! Also adds any outputs which match the filter to the filter (to match //! their spending txes) bool IsRelevantAndUpdate(const CTransaction &tx); //! Checks for empty and full filters to avoid wasting cpu void UpdateEmptyFull(); }; /** * RollingBloomFilter is a probabilistic "keep track of most recently inserted" * set. Construct it with the number of items to keep track of, and a * false-positive rate. Unlike CBloomFilter, by default nTweak is set to a * cryptographically secure random value for you. Similarly rather than clear() * the method reset() is provided, which also changes nTweak to decrease the * impact of false-positives. * * contains(item) will always return true if item was one of the last N to 1.5*N * insert()'ed ... but may also return true for items that were not inserted. * * It needs around 1.8 bytes per element per factor 0.1 of false positive rate. * (More accurately: 3/(log(256)*log(2)) * log(1/fpRate) * nElements bytes) */ class CRollingBloomFilter { public: // A random bloom filter calls GetRand() at creation time. Don't create // global CRollingBloomFilter objects, as they may be constructed before the // randomizer is properly initialized. CRollingBloomFilter(uint32_t nElements, double nFPRate); void insert(const std::vector &vKey); void insert(const uint256 &hash); bool contains(const std::vector &vKey) const; bool contains(const uint256 &hash) const; void reset(); private: int nEntriesPerGeneration; int nEntriesThisGeneration; int nGeneration; std::vector data; uint32_t nTweak; int nHashFuncs; }; #endif // BITCOIN_BLOOM_H diff --git a/src/cashaddr.cpp b/src/cashaddr.cpp index 6e09693e27..3dcb71f891 100644 --- a/src/cashaddr.cpp +++ b/src/cashaddr.cpp @@ -1,299 +1,299 @@ // Copyright (c) 2017 Pieter Wuille // Copyright (c) 2017 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. -#include "cashaddr.h" +#include namespace { typedef std::vector data; /** * The cashaddr character set for encoding. */ const char *CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"; /** * The cashaddr character set for decoding. */ const int8_t CHARSET_REV[128] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 15, -1, 10, 17, 21, 20, 26, 30, 7, 5, -1, -1, -1, -1, -1, -1, -1, 29, -1, 24, 13, 25, 9, 8, 23, -1, 18, 22, 31, 27, 19, -1, 1, 0, 3, 16, 11, 28, 12, 14, 6, 4, 2, -1, -1, -1, -1, -1, -1, 29, -1, 24, 13, 25, 9, 8, 23, -1, 18, 22, 31, 27, 19, -1, 1, 0, 3, 16, 11, 28, 12, 14, 6, 4, 2, -1, -1, -1, -1, -1}; /** * Concatenate two byte arrays. */ data Cat(data x, const data &y) { x.insert(x.end(), y.begin(), y.end()); return x; } /** * This function will compute what 8 5-bit values to XOR into the last 8 input * values, in order to make the checksum 0. These 8 values are packed together * in a single 40-bit integer. The higher bits correspond to earlier values. */ uint64_t PolyMod(const data &v) { /** * The input is interpreted as a list of coefficients of a polynomial over F * = GF(32), with an implicit 1 in front. If the input is [v0,v1,v2,v3,v4], * that polynomial is v(x) = 1*x^5 + v0*x^4 + v1*x^3 + v2*x^2 + v3*x + v4. * The implicit 1 guarantees that [v0,v1,v2,...] has a distinct checksum * from [0,v0,v1,v2,...]. * * The output is a 40-bit integer whose 5-bit groups are the coefficients of * the remainder of v(x) mod g(x), where g(x) is the cashaddr generator, x^8 * + {19}*x^7 + {3}*x^6 + {25}*x^5 + {11}*x^4 + {25}*x^3 + {3}*x^2 + {19}*x * + {1}. g(x) is chosen in such a way that the resulting code is a BCH * code, guaranteeing detection of up to 4 errors within a window of 1025 * characters. Among the various possible BCH codes, one was selected to in * fact guarantee detection of up to 5 errors within a window of 160 * characters and 6 erros within a window of 126 characters. In addition, * the code guarantee the detection of a burst of up to 8 errors. * * Note that the coefficients are elements of GF(32), here represented as * decimal numbers between {}. In this finite field, addition is just XOR of * the corresponding numbers. For example, {27} + {13} = {27 ^ 13} = {22}. * Multiplication is more complicated, and requires treating the bits of * values themselves as coefficients of a polynomial over a smaller field, * GF(2), and multiplying those polynomials mod a^5 + a^3 + 1. For example, * {5} * {26} = (a^2 + 1) * (a^4 + a^3 + a) = (a^4 + a^3 + a) * a^2 + (a^4 + * a^3 + a) = a^6 + a^5 + a^4 + a = a^3 + 1 (mod a^5 + a^3 + 1) = {9}. * * During the course of the loop below, `c` contains the bitpacked * coefficients of the polynomial constructed from just the values of v that * were processed so far, mod g(x). In the above example, `c` initially * corresponds to 1 mod (x), and after processing 2 inputs of v, it * corresponds to x^2 + v0*x + v1 mod g(x). As 1 mod g(x) = 1, that is the * starting value for `c`. */ uint64_t c = 1; for (uint8_t d : v) { /** * We want to update `c` to correspond to a polynomial with one extra * term. If the initial value of `c` consists of the coefficients of * c(x) = f(x) mod g(x), we modify it to correspond to * c'(x) = (f(x) * x + d) mod g(x), where d is the next input to * process. * * Simplifying: * c'(x) = (f(x) * x + d) mod g(x) * ((f(x) mod g(x)) * x + d) mod g(x) * (c(x) * x + d) mod g(x) * If c(x) = c0*x^5 + c1*x^4 + c2*x^3 + c3*x^2 + c4*x + c5, we want to * compute * c'(x) = (c0*x^5 + c1*x^4 + c2*x^3 + c3*x^2 + c4*x + c5) * x + d * mod g(x) * = c0*x^6 + c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + d * mod g(x) * = c0*(x^6 mod g(x)) + c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + * c5*x + d * If we call (x^6 mod g(x)) = k(x), this can be written as * c'(x) = (c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + d) + c0*k(x) */ // First, determine the value of c0: uint8_t c0 = c >> 35; // Then compute c1*x^5 + c2*x^4 + c3*x^3 + c4*x^2 + c5*x + d: c = ((c & 0x07ffffffff) << 5) ^ d; // Finally, for each set bit n in c0, conditionally add {2^n}k(x): if (c0 & 0x01) { // k(x) = {19}*x^7 + {3}*x^6 + {25}*x^5 + {11}*x^4 + {25}*x^3 + // {3}*x^2 + {19}*x + {1} c ^= 0x98f2bc8e61; } if (c0 & 0x02) { // {2}k(x) = {15}*x^7 + {6}*x^6 + {27}*x^5 + {22}*x^4 + {27}*x^3 + // {6}*x^2 + {15}*x + {2} c ^= 0x79b76d99e2; } if (c0 & 0x04) { // {4}k(x) = {30}*x^7 + {12}*x^6 + {31}*x^5 + {5}*x^4 + {31}*x^3 + // {12}*x^2 + {30}*x + {4} c ^= 0xf33e5fb3c4; } if (c0 & 0x08) { // {8}k(x) = {21}*x^7 + {24}*x^6 + {23}*x^5 + {10}*x^4 + {23}*x^3 + // {24}*x^2 + {21}*x + {8} c ^= 0xae2eabe2a8; } if (c0 & 0x10) { // {16}k(x) = {3}*x^7 + {25}*x^6 + {7}*x^5 + {20}*x^4 + {7}*x^3 + // {25}*x^2 + {3}*x + {16} c ^= 0x1e4f43e470; } } /** * PolyMod computes what value to xor into the final values to make the * checksum 0. However, if we required that the checksum was 0, it would be * the case that appending a 0 to a valid list of values would result in a * new valid list. For that reason, cashaddr requires the resulting checksum * to be 1 instead. */ return c ^ 1; } /** * Convert to lower case. * * Assume the input is a character. */ inline uint8_t LowerCase(uint8_t c) { // ASCII black magic. return c | 0x20; } /** * Expand the address prefix for the checksum computation. */ data ExpandPrefix(const std::string &prefix) { data ret; ret.resize(prefix.size() + 1); for (size_t i = 0; i < prefix.size(); ++i) { ret[i] = prefix[i] & 0x1f; } ret[prefix.size()] = 0; return ret; } /** * Verify a checksum. */ bool VerifyChecksum(const std::string &prefix, const data &payload) { return PolyMod(Cat(ExpandPrefix(prefix), payload)) == 0; } /** * Create a checksum. */ data CreateChecksum(const std::string &prefix, const data &payload) { data enc = Cat(ExpandPrefix(prefix), payload); // Append 8 zeroes. enc.resize(enc.size() + 8); // Determine what to XOR into those 8 zeroes. uint64_t mod = PolyMod(enc); data ret(8); for (size_t i = 0; i < 8; ++i) { // Convert the 5-bit groups in mod to checksum values. ret[i] = (mod >> (5 * (7 - i))) & 0x1f; } return ret; } } // namespace namespace cashaddr { /** * Encode a cashaddr string. */ std::string Encode(const std::string &prefix, const data &payload) { data checksum = CreateChecksum(prefix, payload); data combined = Cat(payload, checksum); std::string ret = prefix + ':'; ret.reserve(ret.size() + combined.size()); for (uint8_t c : combined) { ret += CHARSET[c]; } return ret; } /** * Decode a cashaddr string. */ std::pair Decode(const std::string &str, const std::string &default_prefix) { // Go over the string and do some sanity checks. bool lower = false, upper = false, hasNumber = false; size_t prefixSize = 0; for (size_t i = 0; i < str.size(); ++i) { uint8_t c = str[i]; if (c >= 'a' && c <= 'z') { lower = true; continue; } if (c >= 'A' && c <= 'Z') { upper = true; continue; } if (c >= '0' && c <= '9') { // We cannot have numbers in the prefix. hasNumber = true; continue; } if (c == ':') { // The separator cannot be the first character, cannot have number // and there must not be 2 separators. if (hasNumber || i == 0 || prefixSize != 0) { return {}; } prefixSize = i; continue; } // We have an unexpected character. return {}; } // We can't have both upper case and lowercase. if (upper && lower) { return {}; } // Get the prefix. std::string prefix; if (prefixSize == 0) { prefix = default_prefix; } else { prefix.reserve(prefixSize); for (size_t i = 0; i < prefixSize; ++i) { prefix += LowerCase(str[i]); } // Now add the ':' in the size. prefixSize++; } // Decode values. const size_t valuesSize = str.size() - prefixSize; data values(valuesSize); for (size_t i = 0; i < valuesSize; ++i) { uint8_t c = str[i + prefixSize]; // We have an invalid char in there. if (c > 127 || CHARSET_REV[c] == -1) { return {}; } values[i] = CHARSET_REV[c]; } // Verify the checksum. if (!VerifyChecksum(prefix, values)) { return {}; } return {std::move(prefix), data(values.begin(), values.end() - 8)}; } } // namespace cashaddr diff --git a/src/cashaddrenc.cpp b/src/cashaddrenc.cpp index 081a264842..ce1d9a4d64 100644 --- a/src/cashaddrenc.cpp +++ b/src/cashaddrenc.cpp @@ -1,189 +1,190 @@ // Copyright (c) 2017 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. -#include "cashaddrenc.h" -#include "cashaddr.h" -#include "chainparams.h" -#include "pubkey.h" -#include "script/script.h" -#include "utilstrencodings.h" +#include + +#include +#include +#include +#include