Hi y'all, 

I've made a PR to the BIP repo to modify BIP 158 based on this thread, and
other recent threads giving feedback on the current version of the BIP:

  * https://github.com/bitcoin/bips/pull/687

I've also updated the test vectors based on the current parameters (and
filter format), and also the code used to generate the test vectors. Due to
the change in parametrization, the test vectors now target (P=19 M=784931),
and there're no longer any cases related to extended filters.

One notable thing that I left off is the proposed change to use the previous
output script rather than the outpoint. Modifying the filters in this
fashion would be a downgrade in the security model for light clients, as it
would allow full nodes to lie by omission, just as they can with BIP 37. As
is now, if nodes present conflicting information, then the light client can
download the target block, fully reconstruct the filter itself, then ban any
nodes which advertised the incorrect filter. The inclusion of the filter
header checkpoints make it rather straight forward for light clients to
bisect the state to find the conflicting advertisement, and it's strongly
recommended that they do so.

To get a feel for the level of impact these changes would have on existing
applications that depend on the txid being included in the filter, I've
implemented these changes across btcutil, btcd, btcwallet, and lnd (which
previously relied on the txid for confirmation notifications). For lnd at
least, the code impact was rather minimal, as we use the pkScript for
matching a block, but then still scan the block manually to find the precise
transaction (by txid) that we were interested in (if it's there).

-- Laolu


On Mon, May 28, 2018 at 9:01 PM Olaoluwa Osuntokun <laolu32@gmail.com> wrote:
> The additional benefit of the input script/outpoint filter is to watch for
> unexpected spends (coins getting stolen or spent from another wallet) or
> transactions without a unique change or output address. I think this is a
> reasonable implementation, and it would be nice to be able to download that
> filter without any input elements. 

As someone who's implemented a complete integration of the filtering
technique into an existing wallet, and a higher application I disagree.
There's not much gain to be had in splitting up the filters: it'll result in
additional round trips (to fetch these distinct filter) during normal
operation, complicate routine seed rescanning logic, and also is detrimental
to privacy if one is fetching blocks from the same peer as they've
downloaded the filters from.

However, I'm now convinced that the savings had by including the prev output
script (addr re-use and outputs spent in the same block as they're created)
outweigh the additional booking keeping required in an implementation (when
extracting the precise tx that matched) compared to using regular outpoint
as we do currently. Combined with the recently proposed re-parametrization
of the gcs parameters[1], the filter size should shrink by quite a bit!

I'm very happy with the review the BIPs has been receiving as of late. It
would've been nice to have this 1+ year ago when the draft was initially
proposed, but better late that never!

Based on this thread, [1], and discussions on various IRC channels, I plan
to make the following modifications to the BIP:

  1. use P=2^19 and M=784931 as gcs parameters, and also bind these to the
     filter instance, so future filter types may use distinct parameters
  2. use the prev output script rather than the prev input script in the
     regular filter
  3. remove the txid from the regular filter(as with some extra book-keeping
     the output script is enough) 
  4. do away with the extended filter all together, as our original use case
     for it has been nerfed as the filter size grew too large when doing
     recursive parsing. instead we watch for the outpoint being spent and
     extract the pre-image from it if it matches now

The resulting changes should slash the size of the filters, yet still ensure
that they're useful enough for our target use case.


-- Laolu