HomePhabricator

fix BIP37 processing for non-topologically ordered blocks

Description

fix BIP37 processing for non-topologically ordered blocks

Summary:
CMerkleBlock::CMerkleBlock called IsRelevantAndUpdate() on each transaction
in order, which (due to the outpoint-adding feature) assumes a topological
order of transactions in order to work correctly. If an outpoint of interest were
created later in a block than when gets spent, then it would be added into
the bloom filter too late, and thus that spending transaction would get missed.

This changes CMerkleBlock::CMerkleBlock to scan all outputs first, then
make a second loop to scan all inputs. This requires breaking up the
IsRelevantAndUpdate() function into two parts. The original
IsRelevantAndUpdate() functionality remains fully intact however, as it
gets called from mempool-related code (mempool has topological order)
and tests.

Note that vMatchedTxn.push_back is moved into the second loop so that
index i keeps ascending order, in case that is somehow relevant. (the tests
at least do check this)

A two-loop construction like this will very slightly increase the false
positive rate.

Depends on D3399

Test Plan: make check

Reviewers: deadalnix, jasonbcox, Fabien, schancel, #bitcoin_abc, bvk

Reviewed By: deadalnix, #bitcoin_abc, bvk

Subscribers: bvk

Differential Revision: https://reviews.bitcoinabc.org/D3371

Details

Provenance
Mark Lundeberg <36528214+markblundeberg@users.noreply.github.com>Authored on Jun 19 2019, 23:12
markblundebergPushed on Jun 25 2019, 03:18
Reviewer
Restricted Project
Differential Revision
D3371: fix BIP37 processing for non-topologically ordered blocks
Parents
rABC37da7fbc098c: unsigned int -> size_t in merkleblock-related code
Branches
Unknown
Tags
Unknown

Event Timeline

Mark Lundeberg <36528214+markblundeberg@users.noreply.github.com> committed rABC2ff49c21be18: fix BIP37 processing for non-topologically ordered blocks (authored by Mark Lundeberg <36528214+markblundeberg@users.noreply.github.com>).Jun 25 2019, 03:18