New Bitcoin vulnerability: A transaction that takes at least 3 minutes to be verified by a peerWhat is the most CPU consuming transaction an attacker can create? (*)
Don't keep reading. Take a minute to think about it...
.
.
.
.
.
.
Most people will immediately look for a transaction that verifies as many signatures as possible.
One can achieve this by trying to spend many previous outputs that you own, with a single signature verification for each.
But it turns out that that attack is quite expensive: given that each TxIn requires at least 100 bytes to hold a signature,
a 1Mb transaction would only hold 10K signatures. Assuming each signature verification takes 2 msec, processing the transaction
would take 20 seconds. But even then we would need 10K previns ready to be spent, which would be quite hard to achieve.
If the attacker is a miner, he can create a transaction that exposes 10K outputs (TxPrep), and follow it by the transaction that consumes them (TxAttack). But TxPrep would require an additional 340 Kbytes, so TxAttack would be shorter than expected.
Repeated SHA-256 hashingThere is a another way of forcing clients to do expensive computations with less resources, and that is by forcing clients to hash
the transaction many times: by design each time a signature is verified, the whole transaction is hashed, with some minor modifications.
(check
https://en.bitcoin.it/wiki/OP_CHECKSIG and the beautiful accompanying graph made by Etotheipi)
Using this fact, a miner can construct a transaction take takes more than 3 minutes to be verified (assuming 100 MiB/sec of SHA-256 hashing speed).
First the attacker creates a a transaction that sends 1 satoshi to 100 outputs. Each output is not a standard scriptPub, but special scriptPub that consist of the opcodes: OP_CHECKSIG (200 times) OP_TRUE
This script constains no more than 200 sigops, so is a valid script (200 is the limit).
TxPrep takes aproximately 21 Kbytes from the 1M block.
Then the attacker builds the transaction TxAttack which uses all these TxPrep outputs.
To make the transaction valid, each scriptSig is: OP_0 (201 times)
The previn part of the Txattack transaction takes aproximately 24 Kbytes.
The rest of the TxAttack transaction (upto 1Mb is filled) is made of a few outputs with long scripts (or a lot of outputs with short scripts).
This part of the transaction is almost 955 Kbytes long. (**)
Now, to verify a single script (scriptSig+ScriptPub) the client tries to verify 200 signatures.
Obviously each of those verification return false, since 0x00 is neither a valid ECDSA public key nor a valid ECDSA signature.
But the client has to rehash the 955 Kbytes of data 200 times.
The total size hashed is 100*200*955000=19 100 000 000 bytes
Assuming that OpenSSL code performance of SHA-256 hashing is 100 MiB/sec, then the hashing takes 191 seconds.
The proposed attack requires that miners includes both TxPrep and TxAttack in blocks (but I may be different blocks).
This could be achieved by any user by adding some BTC as fees (I think 1 BTC will do).
Nevertheless, another attack can be constructed by using a standard transaction, that is relied normally from peer to peer.
The attacker can use a standard multisignature transaction to try to pack more verifications in less space ( 1-in-3 OP_CHECKMULTISIG ).
This attack is much more difficult, since it requires the attacker to prepare more than 6000 outputs to be used.
How this vulnerability could be used to perform an attack?1. A miner that can mine one of these block every 10 blocks (having 10% of the network hashing power) can force the blockchain verification process to be a lot slower. Verifying a year of the blockchain would take more than 10 days of CPU time.
2. A miner could use this attack combined by other idea gets a greater probability of finding a block the next block.
3. A peer wants to DoS attack another peer. (but the penny-flooding protection must be bypassed somehow)
4. If miners do not prevent these transactions from being included in their blocks, an attacker can create a TxPrep/TxAttack pair transaction for every block mined, and send the pair every 10 minutes, with a 1 BTC fee, to be included in the next block. Validating the blockchain would take almost half the time it takes to generate it, then the coin price would collapse, the attack becomes cheaper, ... dooms day. Obviously miners will stop including such transactions and nothing horrible really happens. But miners should have to reject tasty fees, and I don't know how the incentives will play for them.
Not a Solution (without hard-forking)Create a Transaction hash cache to temporarily store the last used hash during the evaluation of a script.
Note that the attack can still be executed by using independent outputs.
(TxPrep creates 20K outputs, using 200 Kbytes, then TxAttack consumes these 20K outputs, and requires 152 seconds to be verified)
Quite good Solution (without hard-forking)Verify that the ECDSA signature and the ECDSA public key are well-formed before hashing the transaction.
(this reduces the maximum CPU time to about 30 seconds, since now TxAttack wastes more bytes in signatures)
My Solution proposals1. Soft-forking: Reduce the maximum transaction size to 100 Kbytes. (AGAIN Sergio !?!)
2. Hard-forking: For script evaluation purposes Define
Hash(Tx,previn-index) = Hash ( Hash(outputs) || Hash (Inputs-with-script-cleared) || <previn-index> )
(for SIGHASH_ALL)
This way the values "Hash(outputs)" and "Hash(Inputs-with-script-cleared)" can be cached and reused.
Best regards,
Sergio.
(*) Note that I have excluded the hard-disk resource on purpose, since that's another story I'll be telling you in some time(**) I've not created and tested the transaction, but it seems to me that there is nothing in the protocol that stops it.
