mvtxinhash.mediawiki

  BIP: ___
  Title: Minimum Viable TXin Hash
  Author: Jeremy Rubin <jr@mit.edu>
  Status: Draft
  Type: Standards Track
  Created: 2015-06-24

Table of Contents Abstract Motivation Specification Backward compatibility Discussion

Abstract

Increase the total number of transactions per block by reducing the size of txin hash required.

Motivation

1. Enable network growth.
2. Make transactions less expensive for users as a per-byte fee market develops.

Specification

1. Current standard transaction data includes a 32-byte hash of every parent transaction id
2. This is overkill for unique identification because the only tansactions that could be legitimately referenced are those that exist in the UTXO pool at the time of attempt to spend.
3. Therefore, this proposal suggests truncating the committed value to be a bitstring of length max(256, log2(utxo set size)*k + c) which is long enough to uniquely identify a transaction expected to be in the UTXO set
4. Collisions in this space are possible, however, they are highly unlikely to result in problems as it would require the signatures to be valid spends for the ambiguous transaction
5. On ambiguous lookup, both possible UTXOs could be tried
6. Well-behaved clients can purposefully avoid broadcasting transactions with an existing conflict in the UTXO pool by reselecting the signature nonce to increase chance of ambiguity.
7. For performance, the txid lookup would need to be re-engineered to be prefix based. Based on my limited knowledge of inner bloom filter workings, this seems possible.

Backward compatibility

This BIP can be rolled out via a soft fork.

Transactions would have to be signed with the full hash length, and broadcast with an implicitly truncated hash. The miner would then have to fill out the rest of the hash, mine it, and then re-cut it to be broadcast back out in abbreviated form. Earlier version miners could be sent the expanded form.

It could also more easily, ignoring the difficulties of a hard-fork period, be rolled out as a hard fork to avoid hokey-pokey. ^[1]

The same theory can also be used to compress the existing chain by computing the txid splice possible for unambiguous lookups. The hashes can then be re-expanded for reproducing the hashes (this idea could be written up as a separate BIP).

Discussion

This BIP would reduce the size of a standard transaction by approximately, assuming a 32 bit cut is not ambiguous, 224 bits would be saved for a standard single input transaction. This is a savings of 12.5% for a standard 225 byte txn.

However, the average transaction has more than one input (by the following logic, all (excluding coinbase for simplicity) transactions have at least one input, therefore the existence of a transaction with 2 inputs proves average is greater than 1), which shows that such a change would have larger space savings potential.

This would allow for more transactions to be processed or stored in a single block.

Security wise, because the signatures would still need to match, the possible negative impact is basically 0. In the event of a re-org, the "try all matches" pattern would prevent invalidation at the cost of performance. These events are rare in any case.

Performance wise, there could be a small hit from the 'try all matches' pattern, but it should be relatively hard to create conflicts.

A longer TXID could always be used, but would be more expensive to the user.

1. ^ Because someone asked... The Txid Hokey Pokey: you put the tail end in, you put the tail end out, you put the tail end in and you hash it all about you do the hokey pokey and you solve the block difficulty bound, that's what it's all about!