A Bitcoin transaction that takes 5 hours to verify

In 2013 I found a Bitcoin transaction that takes 3 minutes to verify (CVE-2013-2292) related to O(N^2) hashing in signatures. Since then, the O(N^2) argument has popped up in many contexts, mainly in discussions about a block size increase. Now the problem is partially solved by Segwit. During January 2016 I tried to beat the record, for fun. To do it, I decided I needed to dive into the least explored parts of the source code to find a flaw going undetected for 7 years in archaic code. About 28% of the original Bitcoin v0.1 source code remains in Bitcoin Core v0.12 (although that 28% now represents less than 1.9% of  the total source lines), so the possibility existed.  But after 7 years of code review, I was looking for a pearl. I was looking for the last Satoshi bug.

It is known that deprecated and backwards-compatibility functions are vulnerability-prone parts of any source code. So I focused on FindAndDelete() function: the oldest, most broken and less used part of the Bitcoin consensus code. Peter Todd wrote an excellent review of the nasty consequences of FindAndDelete() here. Luckily, after not much time, I found my pearl: O(N^2) data movement. The next step was to find a way to build a Bitcoin transaction that would exploit it. If you let me give you an advise, this is it: never trust your own vulnerability discoveries and go reporting before you have really tested them.  That is a lesson I learned the hard way: it’s very easy to be blinded by excitement. So I started coding an exploit with my friend Oscar Guindzberg, and after several tries we managed to convert it into an attack. In the worst case (in my computer) the transaction took 5.5 hours to verify, but it required a lot of preparation.

Before going into the details, I want to point out that OP_CODESEPARATOR, FindAndDelete() and the O(N^2) hashing are extremely annoying bugs in the original design that should be fixed by either by Segwit plus a soft-fork, or via a hard-fork, someday. Removing archaic code not only prevents vulnerabilities but also allows much secure re-implementation of the consensus code (although re-implementing consensus code is still a subject of debate).

This vulnerability had an easy fix so I  reported it and it was quickly fixed in Bitcoin Core v0.12.1 (on 14 Apr). The fix didn’t require a fork of any kind, just rewriting the FindAndDelete()  function to be O(N) and not O(N^2).

The Exploit

The way to exploit O(N^2) memory movement in FindAndDelete() is by building a transaction having the following scriptPub:

OP_0 (201 times)
OP_CHECKSIG (200 times)
OP_1
push [ 0 ]
OP_IF
OP_0 (9601 times)
OP_ENDIF

The OP_IF / OP_ENDIF prevents stack overflows by skipping the execution of the OP_0 (which push an empty vector into the stack). The scriptSig must be just an empty script (or a NOP). Each of the initial 200 OP_0 pushes represents a signature consumed by for each CHECKSIG. Since the signature is zero, and CHECKSIG tries to remove the signature from the scriptPub with FindAndDelete(), all  zeros are removed. The tail of the script contains an additional 9601 zeros, so each OP_CHECKSIG performs 9801^2/2 byte moves. The total number of bytes moved is 200*9801^2/2 (=9.6 GB).
The validation of a transaction consuming this prevout takes 1 sec on my virtual machine.
Since an input that redeems a prevout containing only an empty script consumes not more than 50 bytes, the number of redeems that can be performed in a block is about 20K (in a single transaction), and therefore the time it would take to process such block would be 20K*1 sec = 5.5 hours. However, it still requires 200 blocks full of these garbage outputs as preparation stage. So the worst case attack is more theoretical than practical.

To test it in a practical attack (a standalone block attack) I built a block containing a first transaction having 95 of the kind of scriptSigs described, plus another transaction consuming those 95 prevouts and this is the resource usage pattern when accepted by bitcoind:

20:41:39   - Load block from disk: 0.01ms [0.00s]
20:43:11       - Connect 3 transactions: 92230.60ms (30743.532ms/tx, 960.735ms/txin) [92.24s]
20:43:11     - Verify 96 txins: 92231.85ms (960.748ms/txin) [92.28s]
20:43:11     - Index writing: 18.93ms [0.06s]
20:43:11     - Callbacks: 0.86ms [0.02s]
20:43:11   - Connect total: 92265.11ms [92.39s]
20:43:11   - Flush: 0.77ms [0.01s]
20:43:11   - Writing chainstate: 1.16ms [0.02s]

It takes 92 seconds to verify the 96 txins, so my guess that a transaction that takes 5.5 hours to verify can be built was correct.

It is possible to use a standard p2sh transaction as the attack vector, but it seems to be a transaction that takes no more than 500 msec to be verified.

The Simple Solution

In this commit Bitcoin developers re-implemented FindAndDelete() to build a new script by copying the parts that are not removed, instead of removing in-place. I don’t know if any other re-implementation of the consensus code is more vulnerable to this type of resource consumption (I checked BitcoinJ and python bitcoinlib and were not vulnerable).

Other cryptocurrencies based on old versions of Bitcoin may still be vulnerable, but I can’t check every Bitcoin clone to see which are. I’ve lost the count of how many alt-coins there are.

Conclusion

Functions implementing old broken features that nobody use anymore are good places where vulnerabilities can hide, so it’s better to remove code that implements unused functionality.

Bugs are everywhere, keep an eye open and distrust source code.

This report was made public since between 80% and 98% of the network currently has their nodes patched. Special thanks to Oscar Guindzberg who helped me by coding the exploit using bitcoinj. The source code is available if anyone wants to re-test.