Bloom filter FP reset kills anonymity for most wallets

[GoogleCodeExporter]

If you have no transactions in a set of blocks (most users will fall into this 
category), the Bloom FP rate calculation is wrong and triggers constant filter 
resets (making the filter provide non anonymity).
The current code calculates Bloom FP rate as % of transactions received that 
were relevant, the actual FP rate is % of transactions which are in blocks 
which are considered relevant but aren't.

Original issue reported on code.google.com by BlueMatt...@gmail.com on 21 Dec 2013 at 7:49

[GoogleCodeExporter]

Or maybe thats not the wrong calculation, I didnt read the code, but its 
definitely constantly updating the filter if you dont have any transactions.

Original comment by BlueMatt...@gmail.com on 21 Dec 2013 at 7:51

[GoogleCodeExporter]

Oh, I think the issue is probably that the FP rate is multiplied by the number 
of inputs/outputs.
When downloading on a reasonable wallet with lots of keys on blocks with no 
transactions and a fp rate set to 0.01, I see the measured FP rate stay pretty 
consistently in the range of 0.04-0.06, sometimes going up to 0.11. So the 
MAX_FP_RATE_INCREASE should probably be at least 10.

Original comment by BlueMatt...@gmail.com on 21 Dec 2013 at 7:57

[GoogleCodeExporter]

Yep, so my original docs didn't take into account the multiple chances for 
matching on any given transaction. In any case, we need to be way more careful 
doing the filter auto-update (it gives up all anonymity the way its implemented 
now).

Original comment by BlueMatt...@gmail.com on 21 Dec 2013 at 8:03

[GoogleCodeExporter]

Is it a matter of turning the alpha/beta/max-increase FP params, or is there a 
more complicated issue here?

Original comment by c1.devra...@niftybox.net on 21 Dec 2013 at 9:38

[GoogleCodeExporter]

I think alpha/beta tuning could help quite a bit, but ultimately 
MAX_FP_RATE_INCREASE is going to need to be much larger than 2.
In any case, there is also a few much more serious bugs at play here:
1. The anonymity set is FP_rate^2 over the set of pubkeys in the chain, not the 
FP_rate claimed by the docs. This should be taken advantage of and false 
positive pubkeys that are in the filter (ie contains(pubkey) && 
contains(pubkeyhash)) should be kept in it as the filter as it is updated. This 
really only barely fixes the issue as you then need a very large FP rate before 
the filter provides any real privacy. Additionally, we should try to guess 
which p2address transactions which come in as false positive might not be spent 
yet and add those to our filter. Alternatively, we could consider changing our 
spend scripts to include the address on the scriptSig so that we don't need to 
push the pubkey into the filter. Sadly, we'd have to ensure our keys are always 
used in this way, which is difficult, and tags all bitcoinj transactions :(. 
Realistically, we should at least floor the FP rate so that people can't create 
a filter that is lower than, eg, 0.01 (which is pretty terrible for 
performance, and also pretty bad for privacy :(
2. Issue #502 (which I just posted a comment on to clarify how it should be 
fixed)

Original comment by BlueMatt...@gmail.com on 22 Dec 2013 at 12:01

[GoogleCodeExporter]

Hm, critical defect and no comment on it since 10 months.

Original comment by 1...@alpenjodel.de on 28 Oct 2014 at 12:28