Class BloomFilter


  • public class BloomFilter
    extends Message

    A Bloom filter is a probabilistic data structure which can be sent to another client so that it can avoid sending us transactions that aren't relevant to our set of keys. This allows for significantly more efficient use of available network bandwidth and CPU time.

    Because a Bloom filter is probabilistic, it has a configurable false positive rate. So the filter will sometimes match transactions that weren't inserted into it, but it will never fail to match transactions that were. This is a useful privacy feature - if you have spare bandwidth the false positive rate can be increased so the remote peer gets a noisy picture of what transactions are relevant to your wallet.

    Instances of this class are not safe for use by multiple threads.

    • Constructor Detail

      • BloomFilter

        public BloomFilter​(int elements,
                           double falsePositiveRate,
                           long randomNonce)
        Constructs a filter with the given parameters which is updated on P2PK outputs only.
      • BloomFilter

        public BloomFilter​(int elements,
                           double falsePositiveRate,
                           long randomNonce,
                           BloomFilter.BloomUpdate updateFlag)

        Constructs a new Bloom Filter which will provide approximately the given false positive rate when the given number of elements have been inserted. If the filter would otherwise be larger than the maximum allowed size, it will be automatically downsized to the maximum size.

        To check the theoretical false positive rate of a given filter, use getFalsePositiveRate(int).

        The anonymity of which coins are yours to any peer which you send a BloomFilter to is controlled by the false positive rate. For reference, as of block 187,000, the total number of addresses used in the chain was roughly 4.5 million. Thus, if you use a false positive rate of 0.001 (0.1%), there will be, on average, 4,500 distinct public keys/addresses which will be thought to be yours by nodes which have your bloom filter, but which are not actually yours. Keep in mind that a remote node can do a pretty good job estimating the order of magnitude of the false positive rate of a given filter you provide it when considering the anonymity of a given filter.

        In order for filtered block download to function efficiently, the number of matched transactions in any given block should be less than (with some headroom) the maximum size of the MemoryPool used by the Peer doing the downloading (default is TxConfidenceTable.MAX_SIZE). See the comment in processBlock(FilteredBlock) for more information on this restriction.

        randomNonce is a tweak for the hash function used to prevent some theoretical DoS attacks. It should be a random value, however secureness of the random value is of no great consequence.

        updateFlag is used to control filter behaviour on the server (remote node) side when it encounters a hit. See BloomFilter.BloomUpdate for a brief description of each mode. The purpose of this flag is to reduce network round-tripping and avoid over-dirtying the filter for the most common wallet configurations.

    • Method Detail

      • getFalsePositiveRate

        public double getFalsePositiveRate​(int elements)
        Returns the theoretical false positive rate of this filter if were to contain the given number of elements.
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • bitcoinSerializeToStream

        protected void bitcoinSerializeToStream​(java.io.OutputStream stream)
                                         throws java.io.IOException
        Serializes this message to the provided stream. If you just want the raw bytes use bitcoinSerialize().
        Overrides:
        bitcoinSerializeToStream in class Message
        Throws:
        java.io.IOException
      • murmurHash3

        public static int murmurHash3​(byte[] data,
                                      long nTweak,
                                      int hashNum,
                                      byte[] object)
        Applies the MurmurHash3 (x86_32) algorithm to the given data. See this C++ code for the original.
      • contains

        public boolean contains​(byte[] object)
        Returns true if the given object matches the filter either because it was inserted, or because we have a false-positive.
      • insert

        public void insert​(byte[] object)
        Insert the given arbitrary data into the filter
      • insert

        public void insert​(ECKey key)
        Inserts the given key and equivalent hashed form (for the address).
      • insert

        public void insert​(TransactionOutPoint outpoint)
        Inserts the given transaction outpoint.
      • setMatchAll

        public void setMatchAll()
        Sets this filter to match all objects. A Bloom filter which matches everything may seem pointless, however, it is useful in order to reduce steady state bandwidth usage when you want full blocks. Instead of receiving all transaction data twice, you will receive the vast majority of all transactions just once, at broadcast time. Solved blocks will then be send just as Merkle trees of tx hashes, meaning a constant 32 bytes of data for each transaction instead of 100-300 bytes as per usual.
      • merge

        public void merge​(BloomFilter filter)
        Copies filter into this. Filter must have the same size, hash function count and nTweak or an IllegalArgumentException will be thrown.
      • matchesAll

        public boolean matchesAll()
        Returns true if this filter will match anything. See setMatchAll() for when this can be a useful thing to do.
      • getUpdateFlag

        public BloomFilter.BloomUpdate getUpdateFlag()
        The update flag controls how application of the filter to a block modifies the filter. See the enum javadocs for information on what occurs and when.
      • applyAndUpdate

        public FilteredBlock applyAndUpdate​(Block block)
        Creates a new FilteredBlock from the given Block, using this filter to select transactions. Matches can cause the filter to be updated with the matched element, this ensures that when a filter is applied to a block, spends of matched transactions are also matched. However it means this filter can be mutated by the operation. The returned filtered block already has the matched transactions associated with it.
      • applyAndUpdate

        public boolean applyAndUpdate​(Transaction tx)
      • equals

        public boolean equals​(java.lang.Object o)
        Overrides:
        equals in class java.lang.Object
      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object