Back to home page

Bitcoin sources

 
 

    


File indexing completed on 2020-06-26 04:55:41

0001 // Copyright (c) 2012-2014 The Bitcoin developers
0002 // Distributed under the MIT software license, see the accompanying
0003 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
0004 
0005 #ifndef BITCOIN_BLOOM_H
0006 #define BITCOIN_BLOOM_H
0007 
0008 #include "serialize.h"
0009 
0010 #include <vector>
0011 
0012 class COutPoint;
0013 class CTransaction;
0014 class uint256;
0015 
0016 //! 20,000 items with fp rate < 0.1% or 10,000 items and <0.0001%
0017 static const unsigned int MAX_BLOOM_FILTER_SIZE = 36000; // bytes
0018 static const unsigned int MAX_HASH_FUNCS = 50;
0019 
0020 /**
0021  * First two bits of nFlags control how much IsRelevantAndUpdate actually updates
0022  * The remaining bits are reserved
0023  */
0024 enum bloomflags
0025 {
0026     BLOOM_UPDATE_NONE = 0,
0027     BLOOM_UPDATE_ALL = 1,
0028     // Only adds outpoints to the filter if the output is a pay-to-pubkey/pay-to-multisig script
0029     BLOOM_UPDATE_P2PUBKEY_ONLY = 2,
0030     BLOOM_UPDATE_MASK = 3,
0031 };
0032 
0033 /**
0034  * BloomFilter is a probabilistic filter which SPV clients provide
0035  * so that we can filter the transactions we sends them.
0036  * 
0037  * This allows for significantly more efficient transaction and block downloads.
0038  * 
0039  * Because bloom filters are probabilistic, an SPV node can increase the false-
0040  * positive rate, making us send them transactions which aren't actually theirs, 
0041  * allowing clients to trade more bandwidth for more privacy by obfuscating which
0042  * keys are owned by them.
0043  */
0044 class CBloomFilter
0045 {
0046 private:
0047     std::vector<unsigned char> vData;
0048     bool isFull;
0049     bool isEmpty;
0050     unsigned int nHashFuncs;
0051     unsigned int nTweak;
0052     unsigned char nFlags;
0053 
0054     unsigned int Hash(unsigned int nHashNum, const std::vector<unsigned char>& vDataToHash) const;
0055 
0056 public:
0057     /**
0058      * Creates a new bloom filter which will provide the given fp rate when filled with the given number of elements
0059      * Note that if the given parameters will result in a filter outside the bounds of the protocol limits,
0060      * the filter created will be as close to the given parameters as possible within the protocol limits.
0061      * This will apply if nFPRate is very low or nElements is unreasonably high.
0062      * nTweak is a constant which is added to the seed value passed to the hash function
0063      * It should generally always be a random value (and is largely only exposed for unit testing)
0064      * nFlags should be one of the BLOOM_UPDATE_* enums (not _MASK)
0065      */
0066     CBloomFilter(unsigned int nElements, double nFPRate, unsigned int nTweak, unsigned char nFlagsIn);
0067     CBloomFilter() : isFull(true), isEmpty(false), nHashFuncs(0), nTweak(0), nFlags(0) {}
0068 
0069     ADD_SERIALIZE_METHODS;
0070 
0071     template <typename Stream, typename Operation>
0072     inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
0073         READWRITE(vData);
0074         READWRITE(nHashFuncs);
0075         READWRITE(nTweak);
0076         READWRITE(nFlags);
0077     }
0078 
0079     void insert(const std::vector<unsigned char>& vKey);
0080     void insert(const COutPoint& outpoint);
0081     void insert(const uint256& hash);
0082 
0083     bool contains(const std::vector<unsigned char>& vKey) const;
0084     bool contains(const COutPoint& outpoint) const;
0085     bool contains(const uint256& hash) const;
0086 
0087     void clear();
0088 
0089     //! True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash functions is <= MAX_HASH_FUNCS
0090     //! (catch a filter which was just deserialized which was too big)
0091     bool IsWithinSizeConstraints() const;
0092 
0093     //! Also adds any outputs which match the filter to the filter (to match their spending txes)
0094     bool IsRelevantAndUpdate(const CTransaction& tx);
0095 
0096     //! Checks for empty and full filters to avoid wasting cpu
0097     void UpdateEmptyFull();
0098 };
0099 
0100 #endif // BITCOIN_BLOOM_H