Script hash collisions about electrs HOT 5 CLOSED

You're right, and thanks for opening this issue!
I need to explain it better at doc/schema.md, but even if collisions happen - the current code should still do the correct thing:

• in case of a hash prefix collision, a query will return a few unrelated transaction IDs (in addition to the correct one).
• the server verifies that each transaction actually has a relevant output/input (to the specified script_hash).

Therefore, a collision should only make the server do more TX lookups, but shouldn't hurt the correctness of the result.

from electrs.

FTR, by running the following tool, it seems that the Bitcoin transaction IDs have at most 6 bytes collisions (as of today):

$ cargo run --release --example txid_collisions -- -vvvv --timestamp --network=mainnet --db-dir=./db
2018-08-01T12:39:50.749+03:00 - DEBUG - opening DB at "./db/mainnet"
3 bytes collision found:
"acfb8519dd11de9e7c697b2ebc80f9e86cb5f860a0cf7a73666b062f01000000"
"3525c2e14ec21e6a6f5304deb5a1a7a553806b4ecad7d5c7d596055f1b000000"

4 bytes collision found:
"185b74db16c2771a319fca80d7029e76d6ad1fd102523f768a845d9096000000"
"76a4cd4f848d8fd8b173fe6291d77ac35666611d976ea8306150dac696000000"

5 bytes collision found:
"b83ae2c5b8d95374d9fb346d1f893c507c3506e8f1fb0c4a493a45bfa8e20000"
"b9a7eb7066740d7c4ab09115b5d77a28df77554041b4b02877b6a7bfa8e20000"

6 bytes collision found:
"18378dddaf6b3a296c8408dbd362dae0e0223f54b96d163cc73a41f468bef000"
"2bb37d516bc27dad079ca715d2c29d01b7f121cf1d9c21db2bb941f468bef000"

2018-08-01T12:41:53.934+03:00 - TRACE - closing DB at "/opt/tmp/mainnet"

from electrs.

You're right - I compare only "full bytes" when looking for collisions, so it's very likely that we're very close to a full 7 bytes transaction ID collision.

However, even if there are a few collisions, the query handling code should handle them correctly (AFAIU), since it verifies that the actual script has the same hash, and that each spending transaction actually spends a valid output:

So, the impact should be a slowdown for querying addresses with a script hash collision.

from electrs.

Yes the scheme is good if the client assumes it'll get a superset of transactions. I suspect Electrum / Electron Cash does that, but they are generally not very fault tolerant; it's easy for a malicious server to bring them all down

from electrs.

I don't think that's right, someone posted on Twitter 1 year ago it was about 56 bits for tx hashes, perhaps Stick, which is what you'd expect from the birthday problem and number of txs. I actually ran the calculation, and a bunch of other stats on BCH, and it's 56 bits for a hashX there. Of course a hashX I use in ElectrumX is a script hash, but still

from electrs.