Possible to create a double spend attack by replacing a Tx in the merkle tree?

Question

This question on crypto.SE describes how preimage attacks are avoided in the Bitcoin network.

For a second preimage attack:

hash(x) = hash(y) implies hash(hash(x)) = hash(hash(y))

So it wouldn't protect against a direct preimage attack. Bitcoin builds a Merkle tree for a b c like this: hash(hash(hash(a)+hash(b))+hash(hash(c)+hash(c))).

You can see again that if someone found a c' that has the same SHA-256 hash as c, they could substitute it and the final result would still be the same.

While it's true that this might improve resistance to first preimage attacks, there aren't any obvious cases where those would matter -- an attacker typically would have the plaintext that generated the hash. (And preimage attacks on addresses seem far fetched, given that the ECDSA operation is in there.)

Suppose two offline transactions are generated with the same c' hash. Assume it takes several months/years to create each Tx. Then:

1. The attacker creates a Tx to a merchant
2. The attacker creates a second Tx with the same inputs as #1. Then a private key is regenerated until the Tx hash equals the hash of c'.

Question

1. How does the Bitcoin network respond to these competing transactions with the same hash?

2. How would the outcome be different if the transaction was non-standard, and therefore not replicated across miners?

Answer 1

You should also know that the task of finding an SHA256 collision (same hash for two different byte arrays) is a pretty complex one. Miners are spending terahashes per second to find a hash which is smaller than a target. An exact match would be very hard to find.

Also, the attacker in this task is required to be a miner with enough power to solve and broadcast a [special] block to be included in the main chain.

In short, I can say that this task requires so much hashing power - so if someone has enough power for that, he may perform a less complex 51% attack rather than this one.

Answer 2

Even without the whole discussion about merkle trees, having two transactions with the same hash could create a fork that would not be resolved without manual intervention.

As the transactions are also identified by their hash on the protocol the clients would get either t or t', where hash(t) = hash(t'), that means that while nodes believe they accepted the same transaction, they would in fact have agreed upon two different transactions that conflict with each other. This would cause havoc down the line when a transaction tries to claim the outputs created by t. As these outputs are created in t and not in t' depending on which of the two you accepted, the followup transaction would be either valid or invalid, and so the problem spreads from one transaction to many.

A transaction being valid in one part of the network and not in the other will cause a blockchain fork, that might persist possibly requiring manual intervention.

Going back to the scenario you stated: the merchant would be tricked out of his money. He would believe the funds to be spendable, but every transaction he attempts with those outputs would be flagged as invalid, as per your scenario he gets t whereas a majority of the mining power gets t' and therefore t' will make it into the chain.

That being said, SHA-256 is thought to be collision resistant and the chance of finding a collision to a specific hash requires incredible amounts of attempts. Even finding a collision between any two inputs is incredibly hard, and the subject of many research challenges. So, it's unlikely to happen anytime soon.