Protection against txid collisions

[akrmn2021]

In Bitcoin Core I see BIP30 active only in certain cases after BIP34 is activated. But if there is a (rare) txid (sha256) collision, then wouldn't that cause a consensus fork? Can't that be avoided by enforcing BIP30 for all blocks, even if BIP34 is active?

[hosemary]

I am not sure I am understanding you correctly, but I know BIP30 is already applied to all blocks except blocks number 91842 and 91880.
With having BIP30 implemented, now it's not possible to have a block including a transaction with the same ID as a not-fully-spent transaction


See this:
https://github.com/bitcoin/bitcoin/commit/ab91bf39b7c11e9c86bb2043c24f0f377f1cf514

[NotATether]

In the event of a txid collision, since BIP30 and BIP34 are now active, the collision would have to come from a non-coinbase transaction, which is almost impossible to pull off due to the limited size of the UTXO set, and if said transactions have any spendable outputs then that transaction is going to be rejected now, not cause a fork.

Whereas if two colliding transactions have no spendable outputs then they don't have to be kept in the UTXO set anyway so they can be ignored and pass through.

[Mia Chloe]

Op you are right it could cause a consensus fork.
However the chances of having a situation of two transactions being broadcasted with the same txid is very thin. In any case to avoid something like that , enforcing BIP30 for all blocks including those with BIP34 is a nice solution. That should ensure that the TXid is always reversed in the block header to prevent any collision or a situation of the same Txid .

The problem has already been solved since version 0.19.1 of bitcoin core. Even with this solution like I said earlier the chances of a Txid collision is very slim because of the hash function and randomness in addition to number of characters allowed. It's almost like trying to double spend the Same coins of which the network will need to confirm the POW and the POW for the forged Txid would be invalid

[ranochigo]

There might be a bit of a confusion over here. BIP30 is only active at a specific block (1983702) and beyond (and pre-BIP34 other than the two blocks) due to the possibility of reintroducing collisions in TXIDs with the pre-BIP34 coinbase.

BIP30 is expensive because it involves searching each of the transaction id and checking if they have a colliding TXID within the UTXO set.

Code:

    if (fEnforceBIP30) {
        BOOST_FOREACH(const CTransaction& tx, block.vtx) {
            const CCoins* coins = view.AccessCoins(tx.GetHash());
            if (coins && !coins->IsPruned())
                return state.DoS(100, error("ConnectBlock(): tried to overwrite transaction"),
                                 REJECT_INVALID, "bad-txns-BIP30");
        }
    }

BIP34 simplifies this by ensuring block height in the coinbase and thereby making the TXIDs of coinbase tx unique. However, certain blocks pre-BIP34 has numbers in the scriptsig that coincides with block heights in the future which results in a small number of post-BIP34 blocks being able include the same coinbase again. IIRC there's one at height 1983702, and more after so that's why we enforce BIP30 again after 1983702.

Anyways, TXID collision can cause a problem and a consensus fork in a very specific scenario. Anyhow, it is not a big issue because of how unlikely TXID collisions are.

tl;dr: You're right that BIP30 is not required after BIP34's activation and that BIP30 will only be active again far in the future. We deactivated BIP30 in favour of BIP34 because it is unnecessary. BIP30 gets reactivated because of the possibility of a TXID collision in the coinbase again in the far future. However, enforcing it again would necessitate the client to waste resources on the unlikely scenario of SHA256 collision.

[akrmn2021]

I saw a discussion of this in the mailing list archive (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-November/013315.html). I don't fully understand what Eric is saying, but were his concerns ever addressed? Did libbitcoin implement it differently than Bitcoin Core?

With block hash collisions there's a protection mechanism according to this answer: https://bitcoin.stackexchange.com/questions/38384/how-does-the-bitcoin-network-recover-in-case-of-a-hash-collision-in-the-block-ha

But for txid collisions I am not sure if there is such a protection mechanism in Bitcoin Core. I need to think about the exact attack, and I will get back here.

[akrmn2021]

I think the basic example is say you have a piece of the blockchain
block a -> block b -> block c -> block d -> block e

where block b has transaction t with txid t'

Then suddenly someone creates a transaction u with same txid t' and broadcasts it to everyone

With current rules I think people synced past block b will replace transaction t with transaction u and people who are still not synced past b will eventually see either t or u first, and then whichever they see next (if any) they will replace the old tx with the new one. So it is not clear what tx the new syncers will have in their UTXO database (assuming both t and u have some unspent outputs). Once t or u is spent, there will be a fork between the new syncers and old syncers.

If instead we disallow t to be replaced by u, then old syncers will still have t. If new syncers see t first, then they continue syncing up to the blocks of the old syncers. Again, it depends what tx the new syncers see first.

In both cases, there will be a fork. No? So I think the same applies with the block hashes collisions...

I there should be some deterministic way to choose which transaction to use (t or u). Be it the one with the most coin age or something else. Same with colliding blocks...Other solution is just to use checkpoints, but that's not a decentralized solution.

Let me know if there's some flaws in my logic.