Are there valid transactions which are impossible to mine?

Question

Is it possible to have a bitcoin transaction T that is valid with a very generous transaction fee for which it is impossible for T to be included in the next block, or even in all subsequent blocks?

The block header contains a hash of the previous block header as well the hash of the merkle root of all transactions in the block. Can T exist such that including T in the block renders all possible nonce values for that block futile in solving the mining puzzle?

I'm guessing that the existence of such a transaction for any particular network configuration occurs with very low probability. Is there a proof which shows that such an event is unlikely or even impossible due to the cryptographic properties of the SHA256 hash function?

Answer 1

I think that the answer to your question is no, a transaction which makes every block it is included in invalid does not exist.

An important core property of a cryptographic hash function is that there is no discernable relationship between the input data, and output data. If such a relationship existed, then miners could 'cheat' by only creating blocks (input data) that would lead to a valid hash (output data) in the preferred range (lower than the difficulty target). In reality, we see that changing the input data slightly will drastically alter the output data, in a deterministic but unpredictable way.

And so I don't believe a transaction could exist, which would invalidate every block which it was attempted to be included in. Even if you create a block with just a coinbase transaction, and exhaust the nonce and extranonce space without finding a valid solution, the timestamp will still slowly increment, and each time it does you can search the entire nonce/extranonce space again. Probabilistically, since we expect an even, and random output value distribution from the hash function, after enough time, some combination of your transaction / the timestamp / the nonce and extranonce should lead to a valid block.

There is also lots of other data that can be included in a block, and altering any piece of it will affect the block hash as well. Murch's answer here tells us that lately there are ~2000 transactions in a block on average. For simplicity, lets assume that all transactions in the block are independent, so they could be included in any order. The number of permutations for the transaction ordering is thus 2000!, which is a huge number (~3.316 E +5735). For each of these combinations, the miner could exhaust the nonce space, the extranonce space, and then increment the timestamp and do it all again. This makes our number of possible arrangements even more enormous! Given enough time, and computational power, it becomes likely that a valid block hash will be found.

So, just from a probabilistic argument, I don't believe it is possible for the inclusion of some transaction to magically only create invalid blocks. Perhaps someone more well versed in the nitty-gritty details can offer a more thorough proof of this, but I think just the numbers alone, combined with the security properties of a cryptographic hash function, are reasonable enough proof.

Answer 2

Adding onto @chytrik answer, the "proof" that it's impossible to find such a hash is purely probabilistic; perhaps there is some transaction hash which by sheer mind-boggling coincidence would not be hashable with all the others or any nonce to find a block with the necessary difficulty.

If we supposed that this were the case, the next question would be how to find it. I think trying to actually find such a hash would have the difficulty of finding an arbitrary hash collision or harder, where finding a collision is already so difficult that for practical purposes it's considered impossible.

So if you had enough hash power to find the TX that would break the blockchain, you could already break the blockchain in numerous other ways.