Rusty Russell's Coding Blog | Stealing From Smart People

Jul/15

8

The Megatransaction: Why Does It Take 25 Seconds?

Last night f2pool mined a 1MB block containing a single 1MB transaction.  This scooped up some of the spam which has been going to various weakly-passworded “brainwallets”, gaining them 0.5569 bitcoins (on top of the normal 25 BTC subsidy).  You can see the megatransaction on blockchain.info.

It was widely reported to take about 25 seconds for bitcoin core to process this block: this is far worse than my “2 seconds per MB” result in my last post, which was considered a pretty bad case.  Let’s look at why.

How Signatures Are Verified

The algorithm to check a transaction input (of this form) looks like this:

  1. Strip the other inputs from the transaction.
  2. Replace the input script we’re checking with the script of the output it’s trying to spend.
  3. Hash the resulting transaction with SHA256, then hash the result with SHA256 again.
  4. Check the signature correctly signed that hash result.

Now, for a transaction with 5570 inputs, we have to do this 5570 times.  And the bitcoin core code does this by making a copy of the transaction each time, and using the marshalling code to hash that; it’s not a huge surprise that we end up spending 20 seconds on it.

How Fast Could Bitcoin Core Be If Optimized?

Once we strip the inputs, the result is only about 6k long; hashing 6k 5570 times takes about 265 milliseconds (on my modern i3 laptop).  We have to do some work to change the transaction each time, but we should end up under half a second without any major backflips.

Problem solved?  Not quite….

This Block Isn’t The Worst Case (For An Optimized Implementation)

As I said above, the amount we have to hash is about 6k; if a transaction has larger outputs, that number changes.  We can fit in fewer inputs though.  A simple simulation shows the worst case for 1MB transaction has 3300 inputs, and 406000 byte output(s): simply doing the hashing for input signatures takes about 10.9 seconds.  That’s only about two or three times faster than the bitcoind naive implementation.

This problem is far worse if blocks were 8MB: an 8MB transaction with 22,500 inputs and 3.95MB of outputs takes over 11 minutes to hash.  If you can mine one of those, you can keep competitors off your heels forever, and own the bitcoin network… Well, probably not.  But there’d be a lot of emergency patching, forking and screaming…

Short Term Steps

An optimized implementation in bitcoind is a good idea anyway, and there are three obvious paths:

  1. Optimize the signature hash path to avoid the copy, and hash in place as much as possible.
  2. Use the Intel and ARM optimized SHA256 routines, which increase SHA256 speed by about 80%.
  3. Parallelize the input checking for large numbers of inputs.

Longer Term Steps

A soft fork could introduce an OP_CHECKSIG2, which hashes the transaction in a different order.  In particular, it should hash the input script replacement at the end, so the “midstate” of the hash can be trivially reused.  This doesn’t entirely eliminate the problem, since the sighash flags can require other permutations of the transaction; these would have to be carefully explored (or only allowed with OP_CHECKSIG).

This soft fork could also place limits on how big an OP_CHECKSIG-using transaction could be.

Such a change will take a while: there are other things which would be nice to change for OP_CHECKSIG2, such as new sighash flags for the Lightning Network, and removing the silly DER encoding of signatures.

RSS Feed

10 Comments for The Megatransaction: Why Does It Take 25 Seconds?

Michael | July 8, 2015 at 5:22 pm

Great Post. Mike Hearn said that gavin wants to introduce a Hard 100 Kb limit per tx with the block size Fork. Is this number resonable? Want is the verfification time for a worst case 100 Kb tx?
Seems like a trade-off between verfification time and creating multiple tx (not sure why this is Bad).

Author comment by rusty | July 8, 2015 at 5:30 pm

That seems like a knee-jerk reaction; in particular, Lighthouse could benefit from much larger transaction sizes. It might become an issue for sidechains as well (though that’s not immediately clear).

Edmund Edgar | July 8, 2015 at 5:58 pm

> Seems like a trade-off between verfification time and creating multiple tx (not sure why this is Bad).

It’s useful to include more in a single TX when you want it to be handled atomically, so that everything in the transaction goes through together or none of it goes through.

The classic case here is Mike Hearn’s Lighthouse, where you want to make an assurance contract such that lots of people make a donation to a common goal, but if not enough people chip in then everybody gets their money back.

Ultimately the thought is apparently to do what Rusty suggests and make a better signature hashing function, but even if you do that you still need to support the old one, and you don’t want to make it too easy to DoS nodes in the meantime.
https://www.reddit.com/r/Bitcoin/comments/3cgft7/largest_transaction_ever_mined_999657_kb_consumes/csvbtp4

Mcgravier | July 8, 2015 at 6:17 pm

How about limit on a number of hashes per 1kb?

Author comment by rusty | July 8, 2015 at 9:14 pm

Well, the hashes are required for signing. And there is a limit on the number of CHECKSIG operations (50,000 per block if I recall correctly).

Michael | July 8, 2015 at 9:00 pm

Thanks for your replies.

> That seems like a knee-jerk reaction
If understood correctly even with the optimations some large blocks still take longer to verify and can cause some serious problems for miners/nodes. So isn’t a max tx size network rule inevitable? Especially with 8 mb blocks?

Dusty | July 9, 2015 at 11:28 pm

> “If you can mine one of those, you can keep competitors off your heels forever, and own the bitcoin network… Well, probably not.”

In fact not: if a block takes too long to be verified nobody builds on it and your block get orphaned (miners build only on blocks they’ve verified… or at least they should).

So you lose the time you hashed and your reward: next time you’ll probably learn the lesson and create a smaller block :)

Author comment by rusty | July 10, 2015 at 7:07 am

You’re right (as you say, ignoring SPV mining), but there’s a sweet spot where you can gain advantage, as per the 33% attack using withholding. If have to simulate it though to figure out the exact parameters.

Sergio Demian Lerner | July 10, 2015 at 1:34 pm

It can be much worse.
Check https://bitcointalk.org/?topic=140078

Author comment by rusty | July 10, 2015 at 4:17 pm

Aka CVE-2013-2292. Thanks, I didn’t know that was public; I’ve avoided actively looking for DoS attacks…

«

»

Find it!

Theme Design by devolux.org

Tag Cloud