bip158: include duplicate filter elements only once #2303

pull Bruce039 wants to merge 1 commits into bitcoin:master from Bruce039:bip158-dedup-elements changing 1 files +5 −0
  1. Bruce039 commented at 11:49 AM on September 25, 2026: contributor

    The Contents section says what goes into a basic filter, but nothing in the BIP says that an item appearing more than once is only included once. Set Construction describes L as "a vector of N raw items", so building the filter from the text alone keeps duplicates.

    That gives a different result from the test vectors. Block 926485 in bip-0158/testnet-19.json ("Duplicate pushdata 913bcc2b...") spends several outputs with the same script. Keeping every item gives N=17 and a filter and filter header that don't match. Removing duplicates gives N=9, which matches the vector. All other vectors come out the same either way.

    Bitcoin Core (GCSFilter::ElementSet is a std::unordered_set) and btcd (gcs/builder collects into a map) both dedupe, so this only writes down what implementations already do.

  2. bip158: include duplicate filter elements only once
    A script that shows up more than once in a block, for example as the
    previous output script of several inputs, is added to the basic filter a
    single time and N counts distinct items. Bitcoin Core and btcd both do
    this and the test vector for block 926485 depends on it, but the text
    only describes L as a vector of N raw items.
    2479691dc8
  3. in bip-0158.mediawiki:277 in 2479691dc8
     273 | @@ -274,6 +274,11 @@ following items for each transaction in a block:
     274 |  
     275 |  Any "nil" items MUST NOT be included into the final set of filter elements.
     276 |  
     277 | +Duplicate items MUST be included only once. If the same script appears more
    


    murchandamus commented at 6:52 PM on September 25, 2026:

    The document refers to the filter data as a “set”. In computer science, set refers to a data structure that stores unordered unique values. Sets cannot contain duplicates, trying to add a duplicate is either ignored or results in an error. I don’t think this clarification is necessary.


    jonatack commented at 7:11 PM on September 25, 2026:

    Agree. Suggest closing.

  4. murchandamus commented at 6:56 PM on September 25, 2026: member

    Thanks for the submission, I’m not sure this is a useful change.

  5. jonatack closed this on Sep 25, 2026


github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bips. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-09-30 17:10 UTC

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