Are public keys and their corresponding hash values both added to a BitcoinJ Bloom filter?

Question

The paper, On the Privacy Provisions of Bloom Filters in Lightweight Bitcoin Clients has this to say about Bloom filters in SPV:

...Indeed, in current implementations of SPV clients [BitcoinJ], both the addresses and their public keys are inserted in the outsourced Bloom filter. As such, if the adversary knows both the address and its public key, then she can trivially test whether an address is a true positive of the filter by checking whether both the address and its public key are inserted within the filter. If not, then it is highly likely that the address is a false positive of the filter. We believe that the inclusion of both the address and its public key in the Bloom filter is a severe flaw in the current SPV client implementations—and can be easily countered; we thus do not exploit this flaw in our analysis. In fact, more than 99% of all Bitcoin transactions consist of payments to Bitcoin addresses (or the public key hash); moreover, only 4587 out of 33 million total addresses in the system received transactions destined for both their public keys and their public key hashes. This means that for the vast majority of Bitcoin clients, there is no need to include both the public keys and their hashes (i.e., the Bitcoin addresses) in the Bloom filters; inserting one or the other would suffice (in more than 99% of the cases). [my emphasis]

The idea behind this attack was re-iterated in Privacy in BitcoinJ:

The vulnerability is that if a pubkey is truly in the filter then querying both pubkey and pubkeyhash must return true. Because the pubkeyhash is just another almost uniformly random string, the probability of a false positive for the attacker is fp' = fp^2 = 0.0000000021555. I obtained around 56 million pubkeys from the blockchain (mid-January), which theoretically results in 56 million * fp' = 1.29 expected false positives when scanning the blockchain.

In other words, a simple attack is enough to pick out all of the public keys from a BitcoinJ Bloom filter.

Does the current release of BitcoinJ add both a public key and its hash value to its Bloom filters? If not, which release stopped it from occuring?

Also, why were both public keys and hashes added in the first place?

Answer 1

Does the current release of BitcoinJ add both a public key and its hash value to its Bloom filters? If not, which release stopped it from occuring?

Yes. The following code implements it:

/** Inserts the given key and equivalent hashed form (for the address). */
public synchronized void insert(ECKey key) {
    insert(key.getPubKey());
    insert(key.getPubKeyHash());
}

(Source.)

Also, why were both public keys and hashes added in the first place?

I'm not the guy who wrote this (Mike Hearn). That said, I would guess that it's difficult to tell whether deposits to an address will be in P2PKH or P2PK form. Pay to Public Key is really uncommon, but it is legal. Given the choice between having some of his customer's money go missing for mysterious reasons, or reducing their privacy, he chose the latter.

Now, if you're asking why filterload doesn't just take the HASH160 of a key before comparing it to the bloom filter so that a thin client can look for both the hash and the key at the same time, I don't know. That seems like it would fix the problem mentioned in that paper for a pretty reasonable amount of CPU time. I would blame the author of BIP37, but that was written by the same guy.

Answer 2

If a SPV client wants to monitor its wallet balance, it has to track both incoming funds - transactions with outputs containing the wallet public key hash (the bitcoin address), as well as the outgoing funds - transactions with inputs having the wallet public key in their signature script. (Of course the SPV client has to monitor all the pub keys / addresses that the wallet has generated.)

One could say that tracking the outgoing funds duplicates the auto-updating functionality of the bloom filter, but I guess the use case here is a SPV sync from an arbitrary block height.