<p>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.)</p>

<p>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.</p>

CC BY-SA 3.0
2016-08-25T02:01:52.137Z
2016-08-25T02:23:34.010Z
2016-08-25T02:23:34.010Z
ypocat
<blockquote>
  <p>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?</p>
</blockquote>

<p>Yes. The following code implements it:</p>

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

<p><a href="https://github.com/bitcoinj/bitcoinj/blob/e0870efd61e19b971664aaaea384e9e1cebcc7ae/core/src/main/java/org/bitcoinj/core/BloomFilter.java#L239" rel="nofollow">(Source.)</a></p>

<blockquote>
  <p>Also, why were both public keys and hashes added in the first place?</p>
</blockquote>

<p>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.</p>

<p>Now, if you're asking why <code>filterload</code> 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 <a href="https://github.com/bitcoin/bips/blob/master/bip-0037.mediawiki" rel="nofollow">BIP37</a>, but that was written by the same guy.</p>

CC BY-SA 3.0
2015-06-03T04:29:50.723Z
2016-08-25T13:02:58.857Z
2016-08-25T13:02:58.857Z
Nick ODell
<p>The paper, <a href="http://eprint.iacr.org/2014/763.pdf" rel="nofollow">On the Privacy Provisions of Bloom Filters in Lightweight
Bitcoin Clients</a> has this to say about Bloom filters in SPV:</p>

<blockquote>
  <p>...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. <em>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</em>; 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]</p>
</blockquote>

<p>The idea behind this attack was re-iterated in <a href="https://jonasnick.github.io/blog/2015/02/12/privacy-in-bitcoinj/" rel="nofollow">Privacy in BitcoinJ</a>:</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

<p>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?</p>

<p>Also, why were both public keys and hashes added in the first place?</p>

<bitcoinj><privacy><spv><bip37-bloom-filter>
Are public keys and their corresponding hash values both added to a BitcoinJ Bloom filter?
Rich Apodaca
# Are public keys and their corresponding hash values both added to a BitcoinJ Bloom filter?

(Asked by: username_0 on 2015-06-02)

The paper, [On the Privacy Provisions of Bloom Filters in Lightweight
Bitcoin Clients](http://eprint.iacr.org/2014/763.pdf) 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](https://jonasnick.github.io/blog/2015/02/12/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?

**Tags:** bitcoinj, privacy, spv, bip37-bloom-filter


---

## 2 answers

### Answer by username_2 on 2015-06-03. Score: 4 | Accepted answer

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 by username_1 on 2016-08-25. Score: 1

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.


---

