BIP158: block filter encoding is inefficient in case of hash collisions #27003

issue Kixunil opened this issue on January 31, 2023
  1. Kixunil commented at 5:44 AM on January 31, 2023: none

    The elements in the block filter are de-duplicated on insertion into a set, however the hashes are not. This means a zero is encoded in the filter for each collision. The client never cares about these so they should not be needed.

    Is this actually a bug or am I missing something?

    For reference, the same issue is present in the Rust library.

  2. john-moffett commented at 5:41 PM on January 31, 2023: contributor

    It appears to be a bug (or at least an inefficiency), but I think the practical implications are pretty minimal, as collisions should only occur about 1/784931 of the time on average for the basic filter.

    It does appear that the BIP calls for a "set" of the hashes, which implies no duplicates, but it's not explicit.

  3. bitcoin deleted a comment on Apr 12, 2023
  4. pinheadmz commented at 1:50 PM on April 27, 2023: member

    This is not a Bitcoin Core problem and should be addressed on the mailing list to update the BIP.

  5. pinheadmz closed this on Apr 27, 2023

  6. bitcoin locked this on Apr 26, 2024

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-05-02 15:13 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me