Electrs: Script hash collisions

[kyuupichan]

Just wanted to say that

SHA256(script)[:8]

is absolutely not secure or recommendable on BCH or BTC chains. 64 bits is already just slightly below the prefix length where there are collisions on BCH (currently 56). There may well be collisions already on BTC. ElectrumX uses 88 bit indexing and I'm already getting uncomfortable; I will be raising it to 96 or 104 bits soon. 104 bits should suffice GB blocks for quite a long time to come.

[romanz]

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.

[romanz]

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"

[kyuupichan]

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

[romanz]

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:

https://github.com/romanz/electrs/blob/166372dbc09a8112f5e51039829c3bf0e66b8035/src/query.rs#L252

https://github.com/romanz/electrs/blob/166372dbc09a8112f5e51039829c3bf0e66b8035/src/query.rs#L228-L229

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

[kyuupichan]

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