BIP37 privacy problems
BIP__0037 is a protocol for bitcoin lightweight wallets. It was designed with privacy in mind, but the protocol has serious design flaws leading to essentially no privacy for anyone who uses it. It is equivalent to sending all the wallets addresses to a random server which can easily spy on the wallet.
BIP37 uses bloom filters to aim to improve privacy with a false positive rate but the standard has a design error where the stated false positive rate (fp) is reduced to fp^2. The same wallet may produce different bloom filters from which the intersection can be computed which also removes the false positives.
The most comprehensive privacy break is when bloom filter leaks are combined with blockchain transaction privacy leaks. The false positive addresses found by the adversary can be eliminated by seeing that they dont make any transactions to any other addresses from the filter.
Mike Hearn describes this in more eloquence:
The reason bitcoinj doesn't use the obfuscation capabilities of the Bloom filtering protocol is that lying consistently is hard. Let's elaborate on what this means. The Bloom filtering protocol lie about what it's interested in from a remote node. But anyone who ever watched a cop show knows that lying is one thing, but lying without getting caught is something else entirely. Usually in these shows, the detective cleverly puzzles out whodunnit from inconsistencies and mistakes in the suspect's story. Common problems that let the detective catch the bad guy include: constantly changing their story, telling different lies to different observers, telling lies that contain elements of the truth and so on.
As we all know, Bloom filters allow us to match more transactions and script elements than we actually need, and in a way that the server doesn't know which we genuinely care about and which we don't. The problem starts when we realise that what we actually care about is not transactions but rather transaction chains. If we observe a payment to our address A whilst scanning the chain, we must also observe any transaction that spends that payment. Otherwise if someone cloned their wallet to another machine and we were in a watching wallet configuration, we would have no idea the money was actually spent. And it's recursive - having observed the transaction that spends the payment, if it had a change address we must also observe any transaction that spends that transaction, and so on, following the "peel chain" of transactions all the way to the bottom.
Lessons from the failure of BIP37 can be useful when designing and understanding other privacy solutions, especially with the point about data fusion of combining BIP37 bloom filter leaks with blockchain transaction information leaks.