False positive rate in transaction index

[prusnak]

Hi all!

I'd like to know whether we know what is the false positive rate we are hitting in:

• Transaction outputs' index funding
• Transaction inputs' index spending
• Transaction ID index txid

I have some ideas how to make that value lower, but I am not sure if this is worth extra cycles for optimizing.

[Kixunil]

I see two ways of figuring it out:

• For each returned item log to prometheus whether it was TP or FP. Perform some queries and look at the results.
• Write something that checks each record in the database and count collisions. This is harder to implement and would take a while to run but would return accurate average result.

Not sure if the latter is worth it.

[romanz]

Great question!
IIRC (tested a few months back), there were no collisions in txid.
I didn't test funding / spending indices but they shouldn't have too much collisions:

• let's assume 64 bits' prefix
• for 50% collision probability we would need 2**32 rows (birthday paradox)
• currently, there are ~700M txid rows - so the collision probability should be ~1.4% = 700e6**2 / (2 * 2**64)
• there are ~1.9B funding outputs - so the collision probability should be ~9.8% = 1.9e9**2 / (2 * 2**64)
• there are ~1.8B spending rows - so the collision probability should be ~8.8% = 1.8e9**2 / (2 * 2**64)

[prusnak]

I have some ideas how to make that value lower

I was thinking about utilizing BIP158 filters while querying the funding index (if the node has blockfilterindex enabled). We can retrieve the blockfilter first and check whether it is worth downloading the whole block before we do so.

[romanz]

Great idea - this can help a lot when "syncing" a new block when there are a lot of subscriptions!

electrs/src/status.rs

Line 321 in 6f301a0

fn sync_confirmed(

[prusnak]

Should I create an issue for the BIP158 idea or having it here in Discussions is fine?

[romanz]

-> #655 :)

[romanz]

Unfortunately, BIP158 filter requires having the original script (to be hashed using SipHash24) but the Electrum protocol provides us with a scripthash i.e. SHA256(script).