Why we must reference the entire txid for each output we want to spend?

Question

Suppose I want to spend from 3 unspent outputs. I must reference the txid of these unspent outputs. Suppose they are:

eb36eca9a06fbe68278ad3e7d16d10ed02e22ad891ed59ef2b84ed4a49e8a6d2

e912d1d29c2daa30cee47a89329426d254aa1ca59927b2d2ae0a2c561a30c4ad

aec43a6a925e55a4f5aa3fdfa2df308912ae06636a7c92b2e19ba55e7d7fc689

Instead of pointing to the entire txids, couldn't I point to just like the first 7 digits of each, so it'd be eb36eca, e912d1d, aec43a6?

Of course, it's easy to generate a txid that matches just the 7 first digits of each of the used txids. But what if we also included the information that, once you find these 3 txids in the database that start with eb36eca, e912d1d and aec43a6, the hash of these 3 entire txids must be equal hash(eb36eca9a06fbe68278ad3e7d16d10ed02e22ad891ed59ef2b84ed4a49e8a6d2 + e912d1d29c2daa30cee47a89329426d254aa1ca59927b2d2ae0a2c561a30c4ad + aec43a6a925e55a4f5aa3fdfa2df308912ae06636a7c92b2e19ba55e7d7fc689) (where + here is concatenation).

So instead of including all 3 txids, we just include the first n digits of each and the hash of these 3 txids concatenated.

Wouldn't it free a lot of space? It's just one hash + n*k, being n the number of first digits, and k the number of inputs.

Also, wouldn't Schnorr signatures make it possible to sign all these outputs with just 1 signature? Wouldn't it make all transactions have almost the same size? Today, each new output adds to the transaction size at least: it txid and signature, which are the biggest parts.

Answer 1

By compressing the txids to a shorter fingerprint, you're reducing the unique identifiability. For example, there are three transactions that match the prefix eb36eca: tx1, tx2, tx3.

So, essentially, this is creating a combinatorics puzzle, especially considering that the txid is only part of the outpoint, you also have to add the output, otherwise you could be referring e.g. to any of the 51 outputs of the above tx3.

It seems to me that this would make it more complicated to operate thin clients safely, which don't have the complete UTXO Set at their disposal. For relay, similar compressions are already used, but while a such a system might be possible to implement for blockchain data, I'm not sure if the overall effect would be desirable.

Answer 2

Murch's "combinatorics puzzle" is a good point. Indeed, it seems to me that it leads to a pretty disastrous denial-of-service attack.

I can certainly create a transaction whose 7-nibble prefix is whatever I desire, just by brute force: for instance, put some random data in an OP_RETURN output and tweak it until I get a prefix I like. It needs 2^28 tries on average, about 256 million. So let me make 200 transactions, all with prefix 1234567. That needs about 40 billion operations - the work of a couple hours for a decent GPU. If I put a nice little fee in each one, at current rates, it might cost about US$2000 to get them all confirmed.

Now I choose 100 of them at random and create a transaction spending all of them as inputs. In order to check if my transaction is valid, you are going to need to start trying every possible combination of 100 out of the 200 possibilities, until you find the right ones. C(200,100) is about 10^59. Good luck getting through that before the sun goes out.

So I can, relatively cheaply, bring the entire Bitcoin network to its knees, as every node works on the impossible problem of figuring out which 100 transactions I spent.

You're going to have to put in some safeguard to say that if a matching set of transactions can't be found relatively fast, the transaction is just rejected. But your rule has to be deterministic; if some nodes find a match and others don't, they'll disagree on the validity of the transaction -> hard fork. It's not so clear what that would look like. And it also raises the possibility that I could intentionally create collisions with an existing transaction belonging to my enemy, and render it unspendable.

In short, this would not be an easy thing to do safely, and risks disaster for the currency if you don't get it exactly right. Seems much safer to keep it simple, even at the cost of efficiency.