BIP 158 Flexibility and Filter Size

Summary:

Laolu has submitted a pull request (PR) to the BIP repository to modify BIP 158 based on recent feedback. The PR can be found at https://github.com/bitcoin/bips/pull/687. Laolu has also updated the test vectors and the code used to generate them based on the current parameters and filter format. The changes in parametrization have resulted in the test vectors targeting (P=19 M=784931), and there are no longer any cases related to extended filters.One notable thing that Laolu 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. To mitigate this, Laolu recommends that if nodes present conflicting information, then the light client should 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 makes it rather straightforward for light clients to bisect the state to find the conflicting advertisement.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, Laolu has implemented these changes across btcutil, btcd, btcwallet, and lnd. For lnd at least, the code impact was rather minimal, as they use the pkScript for matching a block, but then still scan the block manually to find the precise transaction (by txid) that they were interested in (if it's there).Olaoluwa Osuntokun disagrees with splitting up the filters because 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, he is convinced that the savings had by including the previous output script (address reuse 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 they do currently.Based on a recent thread, discussions on various IRC channels, and the proposed re-parametrization of the gcs parameters, Laolu plans to make the following modifications to the BIP:1. Use P=2^19 and M=784931 as gcs parameters and bind them 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 altogether, as their original use case has been nerfed as the filter size grew too large when doing recursive parsing. Instead, they'll 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 their target use case. More information about the proposed re-parametrization of the gcs parameters can be found at https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/016029.html.

Updated on: 2023-05-20T08:21:49.882922+00:00