Optimize creation and verification of transactions with lots of inputs #6482

Instead of signing all of a transaction's inputs with SIGHASH_ALL, sign just the first input with SIGHASH_ALL (to eliminate one form of malleability) and sign all the rest with SIGHASH_ANYONECANPAY. That dramatically reduces the amount of data that has to be hashed to compute signature hashes.

Benchmark results from my machine:

500-input, 1-output, ~100,000-byte transaction:

Time to validate 500 SIGHASH_ALL inputs: 0.342 seconds Time to validate 500 SIGHASH_ANYONE inputs: 0.277 seconds

5,000-input, 1-output, ~1-megabyte transaction:

Time to validate 5,000 SIGHASH_ALL inputs: 8.753 seconds Time to validate 5,000 SIGHASH_ANYONE inputs: 2.783 seconds

Self-reviewing after having a chance to sleep on this:

This change would mean an unconfirmed transaction gives potential attackers some inputs that belong to me, but are signed so that they are committed to sending the coins to a particular set of outputs but NOT to-a-particular-set-of-outputs-but-only-when-bundled-with-a-particular-set-of-inputs.

So an attacker could:

1. Replace the SIGHASH_ALL first input with one of their inputs. Costs the attacker however many coins are in the first input, not a very interesting attack (unless part of a larger attack that requires transaction malleability to pull off).

2. If the first SIGHASH_ALL input's amount is less than the transaction fee, attacker could relay/broadcast without that first input. Not very interesting, worst case the alternate lower-fee transaction gets mined, user saves some coin.

3. If the wallet has TWO or more unconfirmed, multi-input transactions with exactly the same outputs (paying exactly same amount to same address-- if change is generated, then change address/amount exactly the same for both), then there is a worrisome attack: attacker can combine all of the SIGHASH_ANYONECANPAY inputs from the transactions into one big transaction that has an oversize fee, and mine that instead of the two transactions.

We can say "don't re-use addresses" ... but (3) is a good reason not to merge this as-is

I'm going to do a brain-dump on what it would take to make this change safe... but close this pull request. The performance improvement for transactions with lots of inputs is significant, but those transactions are pretty rare.

So, to do this safely, the wallet should only sign with SIGHASH_ANYONECANPAY if it knows it has never signed any other transactions with an identical set of outputs.

The naive way of doing that would be to iterate over all previous wallet 'send' transactions and check.

Or the code could keep track of whether or not a brand-new change address was being used, and only use ANYONECANPAY if it was.

Or the wallet could keep a bloom filter-- for each 'send' transaction in the wallet, add a hash of just the transaction's outputs to the filter. When sending a new transaction, if it's outputs don't match the bloom filter, it is safe to use ANYONECANPAY. If it does match the bloom filter, then assume it is not safe (it might be a false-positive, and that's OK).

It is not clear to me whether actually implementing that code is worth it; most wallets probably don't create transactions with lots of inputs, and maintaining the bloom filter is extra work that isn't needed in most cases.

This would also make transactions highly identifiable as coming from bitcoin-qt, as this is a publicly visible (e.g on the blockchain) implementation detail?

They're already identifiable to a significant extent (fee sniping, earlier due to randomization of outouts/change and non-reuse of change addresses). I din't think that's a worry. We should encourage best practices. @gavinandresen Considered adding an OP_RETURN with a bit of random data to make the outputs unique, for very large transactions?

They're already identifiable to a significant extent (fee sniping, earlier due to randomization of outouts/change and non-reuse of change addresses).

Fee sniping is on its last legs though right?

We should encourage best practices.

Of course, but would encouraging this for the sake of performance in this client, be considered best practice for other implementations?

Not only performance of the client. Performance of validation by others, which for very large transactions may be in thw best interest of the one creating it.

@sipa : ooh, I like the add-an-extra-OP_RETURN idea....