org.bitcoinj.core

Class BloomFilter

java.lang.Object

org.bitcoinj.core.Message

org.bitcoinj.core.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.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	BloomFilter.BloomUpdate The BLOOM_UPDATE_* constants control when the bloom filter is auto-updated by the peer using it as a filter, either never, for all outputs or only for P2PK outputs (default)

Field Summary

Fields inherited from class org.bitcoinj.core.Message

cursor, length, MAX_SIZE, offset, params, payload, recached, serializer, UNKNOWN_LENGTH

Constructor Summary

Constructors

Constructor and Description
BloomFilter(int elements, double falsePositiveRate, long randomNonce) Constructs a filter with the given parameters which is updated on P2PK outputs only.
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.
BloomFilter(NetworkParameters params, byte[] payloadBytes) Construct a BloomFilter by deserializing payloadBytes

Method Summary

Modifier and Type	Method and Description
FilteredBlock	applyAndUpdate(Block block) Creates a new FilteredBlock from the given Block, using this filter to select transactions.
boolean	applyAndUpdate(Transaction tx)
protected void	bitcoinSerializeToStream(java.io.OutputStream stream) Serializes this message to the provided stream.
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.
boolean	equals(java.lang.Object o)
double	getFalsePositiveRate(int elements) Returns the theoretical false positive rate of this filter if were to contain the given number of elements.
BloomFilter.BloomUpdate	getUpdateFlag() The update flag controls how application of the filter to a block modifies the filter.
int	hashCode()
void	insert(byte[] object) Insert the given arbitrary data into the filter
void	insert(ECKey key) Inserts the given key and equivalent hashed form (for the address).
void	insert(TransactionOutPoint outpoint) Inserts the given transaction outpoint.
boolean	matchesAll() Returns true if this filter will match anything.
void	merge(BloomFilter filter) Copies filter into this.
static int	murmurHash3(byte[] data, long nTweak, int hashNum, byte[] object) Applies the MurmurHash3 (x86_32) algorithm to the given data.
protected void	parse()
void	setMatchAll() Sets this filter to match all objects.
java.lang.String	toString()

Methods inherited from class org.bitcoinj.core.Message

adjustLength, bitcoinSerialize, bitcoinSerialize, getHash, getMessageSize, getParams, hasMoreBytes, isCached, isRecached, readByte, readByteArray, readBytes, readHash, readInt64, readStr, readUint32, readUint64, readVarInt, readVarInt, setSerializer, unCache, unsafeBitcoinSerialize

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

BloomFilter

public BloomFilter(NetworkParameters params,
                   byte[] payloadBytes)
            throws ProtocolException

Construct a BloomFilter by deserializing payloadBytes

Throws:

ProtocolException

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

parse

protected void parse()
              throws ProtocolException

Specified by:

parse in class Message

Throws:

ProtocolException

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