The malleability attack is creating a lot of trouble, we need a quick fix

[jl2012]

The malleability attack becomes a DOS attack. We need a quick fix. Before there is a better solution, the bitcoind should not report unconfirmed transactions. Account balance should be solely based on confirmed transactions. Before malleability is fixed (if ever), unconfirmed outputs should not be spent.

[1715115154]

1715115154

[1715115154]

1715115154

[1715115154]

1715115154

[thenoblebot]

I already have highlighted an attack scheme here (https://bitcointalk.org/index.php?topic=458608.0) for those entities using the txid to track payments.

People have been proposing using other means to track payments and rightly so. But my suggestion even in the above thread has been to at least issue an advisory for entities using txid to stop.

However, I do realise the consequences of such a step : 1) It has already been highlighted before that its not the correct way to do it. 2) Issuing an advisory at such a point might only give more legitimacy to claims by Gox (which is obviously a silly thing to do).

[buffett]

oh gosh this issue need to be fixed asap. it might be not a big issue for bitcoin enthusiast who understand how it works. but for common people, it is a very big concern! it's not common a tx id can be changed in any payment systems. if we transfer money with our bank, or paypal, the tx id wont change, forever. developers used to rely on tx id for any payment systems in the past.

[nmersulypnem]

The devs are notoriously slow...  They aren't even talking about it on the development mailing list today.

I guess that's what happens when you become rich...  well, they'll soon know what it's like to be poor again...

[bitbouillion]

So why not create own txids from the blockchain and compare them to the transmit log, to see if a tx went through?

[NanoAkron]

We need a quick fix.

Quick fixes are never the right answer. I'd rather they took their time and produced a good fix.

[NanoAkron]

The devs are notoriously slow...  They aren't even talking about it on the development mailing list today.

I guess that's what happens when you become rich...  well, they'll soon know what it's like to be poor again...

Are you kidding? They've been discussing it on github:

https://github.com/bitcoin/bitcoin/pull/3651

[nmersulypnem]

The devs are notoriously slow...  They aren't even talking about it on the development mailing list today.

I guess that's what happens when you become rich...  well, they'll soon know what it's like to be poor again...

Are you kidding? They've been discussing it on github:

https://github.com/bitcoin/bitcoin/pull/3651

ah, thanks. I'll retract my comment.  I was looking in the wrong place.

EDIT: sorry, looking at that pull request - it doesn't seem like it's going to fix the problem.  It'll just patch the wallet to not recognize the unconfirmed trandsactions.  Malleable transactions will still happen, we'll still be subject to the DDOS, and the exchanges will still need to make significant changes to their accounting software before re-opening withdrawals.

Let me know if I got anything wrong there.

[Peter Todd]

The devs are notoriously slow...  They aren't even talking about it on the development mailing list today.

I guess that's what happens when you become rich...  well, they'll soon know what it's like to be poor again...

Are you kidding? They've been discussing it on github:

https://github.com/bitcoin/bitcoin/pull/3651

ah, thanks. I'll retract my comment.  I was looking in the wrong place.

EDIT: sorry, looking at that pull request - it doesn't seem like it's going to fix the problem.  It'll just patch the wallet to not recognize the unconfirmed trandsactions.  Malleable transactions will still happen, we'll still be subject to the DDOS, and the exchanges will still need to make significant changes to their accounting software before re-opening withdrawals.

Let me know if I got anything wrong there.

You are. We're talking to those pools about how they can make use of that patch and others to make their accounting software work.

[thenoblebot]

You are. We're talking to those pools about how they can make use of that patch and others to make their accounting software work.

Hi Peter,

I believe to an extent there is some truth (about the delay). Check the mailing list, I believe you replied to me yesterday about the issue. I won't say any further about the concerned topic on the forums here. But yea it kind of a sad situation when the process could have been expedited. Ah nvm - lips sealed .

Cheers

[nmersulypnem]

You are. We're talking to those pools about how they can make use of that patch and others to make their accounting software work.

I see that now in some of the other github threads.  Just a question thoguh:  Does the Bitcoin Foundatoin have any type of PR person?  I mean, there are real merchant & consumers out there that are seeing their BTC jump up and down 20% every day.

Some sort of press release saying that the issue is known and is being worked on, would help a lot.  I mean, it was mentioned on the front page of the Wall Street journal this morning for Christ sake.

[tacotime]

This is what I would do; ignore txid itself, but instead use the output from 4.):
1.) For any incoming transaction generate a list of inputs and values from inputs, concatenate into a string; sort addresses alphanumerically before doing so
2.) Generate output hashes and values and concatenate into above string; sort addresses alphanumerically before doing so
3.) Concatenate the pubkeys from the inputs that are regenerated from the signatures (NOT the signatures themselves) into the above string; sort pubkeys alphanumerically before doing so
4.) Hash this big string and use it as the txid

Even if someone regenerates signatures at random for any tx, the above will never change.  Any duplicate tx that are mutated will come up the same using the above scheme.

Probably even more simply you can just skip step 1.) and put the values of the inputs after their respective pubkeys and then stick it into a string along with the outputs

This can be implemented quickly, probably in 30 min - 1 h.  Exchanges verifying that a tx went through need only look for the above alternative txid hash in the next block and then can verify its incorporation into the blockchain.

I'm tired and going to bed so I hope this is coherent, but verifying blockchain incorporation using this scheme should enable protection from tx malleability

Comments welcome

[thenoblebot]

This is what I would do; ignore txid itself, but instead use the output from 4.):
1.) For any incoming transaction generate a list of inputs and values from inputs, concatenate into a string; sort addresses alphanumerically before doing so
2.) Generate output hashes and values and concatenate into above string; sort addresses alphanumerically before doing so
3.) Concatenate the pubkeys from the inputs that are regenerated from the signatures (NOT the signatures themselves) into the above string; sort pubkeys alphanumerically before doing so
4.) Hash this big string and use it as the txid

Even if someone regenerates signatures at random for any tx, the above will never change.  Any duplicate tx that are mutated will come up the same using the above scheme.

Probably even more simply you can just skip step 1.) and put the values of the inputs after their respective pubkeys and then stick it into a string along with the outputs

This can be implemented quickly, probably in 30 min - 1 h.  Exchanges verifying that a tx went through need only look for the above alternative txid hash in the next block and then can verify its incorporation into the blockchain.

I'm tired and going to bed so I hope this is coherent, but verifying blockchain incorporation using this scheme should enable protection from tx malleability

Comments welcome

Hi tacotime,

Easier fix would be to track transactions using (add,amt,time) .... no ?

Btw your quite an inspiring character, read some of your posts when trying to mine initially. Thanks for all the work you have put it. Appreciate it a lot

Regards

[Lethn]

Quick fixes would be disastrous for Bitcoin, it's a very simple example but take Battlefield 4 as a perfect example of how not to fix code, if you rush out large patches very quickly that fix very little you'll not only piss off the people using the software you'll also create more problems in the process because you haven't checked the code and made sure the changes you've made haven't fucked something else up which is exactly what happened when DICE were rushing out patches when the game first came out.

Take the time to look at it properly, if anything if the situation gets worse it will become a lot more obvious what is wrong with the code because more and more people will be trying to abuse it.

[DeathAndTaxes]

Easier fix would be to track transactions using (add,amt,time) .... no ?

There are no timestamps in bitcoin transactions.

[thenoblebot]

Easier fix would be to track transactions using (add,amt,time) .... no ?

There are no timestamps in bitcoin transactions.

Try this in the console :

gettransaction 6baf826a0c5dcd22d28640233cae375cf8a3b37cf7251a93475986e3f42fa823-000

Output :

{
"amount" : 0.00016720,
"confirmations" : 16124,
"blockhash" : "000000000000000a0f90a320fd1adea3bfefee716fa98c9f10625021d8d4f29e",
"blockindex" : 655,
"blocktime" : 1383072371,
"txid" : "6baf826a0c5dcd22d28640233cae375cf8a3b37cf7251a93475986e3f42fa823",
"time" : 1383070892,
"timereceived" : 1383070892,
"details" : [
{
"account" : "Default",
"address" : "1rU2kc24GcRUjXLm3MZ8RQtjL1zpcsnK3",
"category" : "receive",
"amount" : 0.00016720
}
]
}

What are those "time" and "timereceived" ? Although again its kind of circular where we have to depend on txid :-( .. maybe another way to get those perhaps will do the trick.

[oakpacific]

Easier fix would be to track transactions using (add,amt,time) .... no ?

There are no timestamps in bitcoin transactions.

Try this in the console :

gettransaction 6baf826a0c5dcd22d28640233cae375cf8a3b37cf7251a93475986e3f42fa823-000

Output :

{
"amount" : 0.00016720,
"confirmations" : 16124,
"blockhash" : "000000000000000a0f90a320fd1adea3bfefee716fa98c9f10625021d8d4f29e",
"blockindex" : 655,
"blocktime" : 1383072371,
"txid" : "6baf826a0c5dcd22d28640233cae375cf8a3b37cf7251a93475986e3f42fa823",
"time" : 1383070892,
"timereceived" : 1383070892,
"details" : [
{
"account" : "Default",
"address" : "1rU2kc24GcRUjXLm3MZ8RQtjL1zpcsnK3",
"category" : "receive",
"amount" : 0.00016720
}
]
}

What are those "time" and "timereceived" ? Although again its kind of circular where we have to depend on txid :-( .. maybe another way to get those perhaps will do the trick.

There is no way you can verify independently whether these time datas are correct.

[thenoblebot]

There is no way you can verify independently whether these time datas are correct.

Hmmm. Are you referring to the median time that is used ? Or are you getting a different output ? Its from the blockchain so it should be consistent for all of us as long as there is no reorganisation .. isn't it ? This should work for confirmed transactions with a mutated txid as a check, isnt it ?

Please help me understand more.

[oakpacific]

There is no way you can verify independently whether these time datas are correct.

Hmmm. Are you referring to the median time that is used ? Or are you getting a different output ? Its from the blockchain so it should be consistent for all of us as long as there is no reorganisation .. isn't it ? This should work for confirmed transactions with a mutated txid as a check, isnt it ?

Please help me understand more.

Well, on second reading you've pointed out yourself that if you don't check the txid then the time datas can actually be tampered with by the relaying nodes before it's mined, I have nothing new to add.

[DeathAndTaxes]

There is no way you can verify independently whether these time datas are correct.

Hmmm. Are you referring to the median time that is used ? Or are you getting a different output ? Its from the blockchain so it should be consistent for all of us as long as there is no reorganisation .. isn't it ? This should work for confirmed transactions with a mutated txid as a check, isnt it ?

Please help me understand more.

It isn't from the blockchain it is from the client.   The time is not part of the transaction.  The wallet provides additional data beyond the actual transaction.  In your example does it seem likely that "account" = "Default" is also part of the transaction?


This is a bitcoin transaction.
https://en.bitcoin.it/w/images/en/e/e1/TxBinaryMap.png

There is no timestamp in the transaciton.   Relying on timestmamps is even less secure than relying of tx id.  It doesn't take any clever modification of the transaction to change the timestamp.

[thenoblebot]

It isn't from the blockchain it is from the client.   The time is not part of the transaction.  The wallet provides additional data beyond the actual transaction.  In your example does it seem likely that "account" = "Default" is also part of the transaction?


This is a bitcoin transaction.
https://en.bitcoin.it/w/images/en/e/e1/TxBinaryMap.png

There is no timestamp in the transaciton.   Relying on timestmamps is even less secure than relying of tx id.  It doesn't take any clever modification of the transaction to change the timestamp.

Hmmm I get the point. I got things mixed up in a rush... haven't slept properly (not making excuses though). Thanks I stand corrected.

Appreciate you stepping in to correct me.

[thenoblebot]

But having said that wouldn't it be good enough to check for a particular transaction , at least from the our own side ? I see it gives me the timestamps even after removing "Default" label.

I figure this should be good enough to track it .. aint it so ? Or am i sleep talking again ?

[DeathAndTaxes]

But having said that wouldn't it be good enough to check for a particular transaction , at least from the our own side ? I see it gives me the timestamps even after removing "Default" label.

I figure this should be good enough to track it .. aint it so ? Or am i sleep talking again ?

You should not rely on timestamps at all.

You have a tx A, it has a timestamp of 12:00:00.   Your broadcast it out.  I mutate the tx so it has a hash of B, I broadcast it out with a timestamp of 01:01:01.  Your node would see this as a different transactions.
If you are using this to track payments and I reported I didn't get paid you would find no transaction time a timestamp of 12:00:00 in a block.

Timestamps should never be trusted in Bitcoin for any reason.   They are only used by the protocol to adjust difficulty and that is because there is no way to do it without recording time.  Other nodes can feed you false timestamp data trivially.  Even if tx id were immutable timestamps should still never be trusted.

[thenoblebot]

But having said that wouldn't it be good enough to check for a particular transaction , at least from the our own side ? I see it gives me the timestamps even after removing "Default" label.

I figure this should be good enough to track it .. aint it so ? Or am i sleep talking again ?

You should not rely on timestamps at all.

You have a tx A, it has a timestamp of 12:00:00.   Your broadcast it out.  I mutate the tx so it has a hash of B, I broadcast it out with a timestamp of 01:01:01.  Your node would see this as a different transactions.
If you are using this to track payments and I reported I didn't get paid you would find no transaction time a timestamp of 12:00:00 in a block.

Timestamps should never be trusted in Bitcoin for any reason.   They are only used by the protocol to adjust difficulty and that is because there is no way to do it without recording time.  Other nodes can feed you false timestamp data trivially.  Even if tx id were immutable timestamps should still never be trusted.

Hmm i was thinking for argument sake how checking for timestamps within a certain range might work, but that too would run into problems clearly. Thanks again.

[phelix]

This is what I would do; ignore txid itself, but instead use the output from 4.):
1.) For any incoming transaction generate a list of inputs and values from inputs, concatenate into a string; sort addresses alphanumerically before doing so
2.) Generate output hashes and values and concatenate into above string; sort addresses alphanumerically before doing so
3.) Concatenate the pubkeys from the inputs that are regenerated from the signatures (NOT the signatures themselves) into the above string; sort pubkeys alphanumerically before doing so
4.) Hash this big string and use it as the txid

Even if someone regenerates signatures at random for any tx, the above will never change.  Any duplicate tx that are mutated will come up the same using the above scheme.

Probably even more simply you can just skip step 1.) and put the values of the inputs after their respective pubkeys and then stick it into a string along with the outputs

This can be implemented quickly, probably in 30 min - 1 h.  Exchanges verifying that a tx went through need only look for the above alternative txid hash in the next block and then can verify its incorporation into the blockchain.

I'm tired and going to bed so I hope this is coherent, but verifying blockchain incorporation using this scheme should enable protection from tx malleability

Comments welcome

this?

[peacefulmind]

This is what I would do; ignore txid itself, but instead use the output from 4.):
1.) For any incoming transaction generate a list of inputs and values from inputs, concatenate into a string; sort addresses alphanumerically before doing so
2.) Generate output hashes and values and concatenate into above string; sort addresses alphanumerically before doing so
3.) Concatenate the pubkeys from the inputs that are regenerated from the signatures (NOT the signatures themselves) into the above string; sort pubkeys alphanumerically before doing so
4.) Hash this big string and use it as the txid

Even if someone regenerates signatures at random for any tx, the above will never change.  Any duplicate tx that are mutated will come up the same using the above scheme.

Probably even more simply you can just skip step 1.) and put the values of the inputs after their respective pubkeys and then stick it into a string along with the outputs

This can be implemented quickly, probably in 30 min - 1 h.  Exchanges verifying that a tx went through need only look for the above alternative txid hash in the next block and then can verify its incorporation into the blockchain.

I'm tired and going to bed so I hope this is coherent, but verifying blockchain incorporation using this scheme should enable protection from tx malleability

Comments welcome

I have always thought taco was bright and did a lot for the community for little in return.  I remember following his mining guides over a year ago now when I was trying to figure out what this crypto thing was.  This seems it would work.  I do not know if it is overly complicated, but it seems this is much more urgent than the team led us to believe.  If bitstamp and BTC-E are also affected which they have indicated they are - something needs to be done ASAP, press hype and merchant adoption has done a lot for BTC - weeks of negative media carping could forever damage public perceptions.

I really, really, hope they are calling in the cavalry, Litecoin dev and Coinbase employee Charlie Lee, Fedora founder Warren Togami both from Litecoin team, maybe even a bounty, Sunny King from Peer and Primecoins, anyone that knows this really well should be invited to participate IMHO.  This is not the time for egos.  I have heard from non-technical friends who are freaked out and don't understand this.  A lot of non-computer people have bought in now, early adopters, if you will....

This is not an issue that can languish like the Mac wallet issue did IMHO or permanent damage could be done.  Time for all hands on deck so to speak, if the early adopters create a negative network effect by selling at a loss and influencing their peers, then Bitcoin has MAJOR problems.

Any thoughts on who is behind this attack?  A rival non-mined coin team like NXT or Ripple? A Mafia, a government?

[Amitabh S]

The malleability attack becomes a DOS attack. We need a quick fix. Before there is a better solution, the bitcoind should not report unconfirmed transactions. Account balance should be solely based on confirmed transactions. Before malleability is fixed (if ever), unconfirmed outputs should not be spent.

How does it become a DoS attack? Care to explain? The clients track unspent outputs before forwarding tx (or mining it). How does malleability cause a problem? I don't see any issue (non-gox) unless I missed something.

Why the quick fix? It does not seem urgent. Lets do it properly and thoughtfully.

[DeathAndTaxes]

The malleability attack becomes a DOS attack. We need a quick fix. Before there is a better solution, the bitcoind should not report unconfirmed transactions. Account balance should be solely based on confirmed transactions. Before malleability is fixed (if ever), unconfirmed outputs should not be spent.

How does it become a DoS attack? Care to explain? The clients track unspent outputs before forwarding tx (or mining it). How does malleability cause a problem? I don't see any issue (non-gox) unless I missed something.

Why the quick fix? It does not seem urgent. Lets do it properly and thoughtfully.

Most current wallets will attempt to spend unconfirmed change outputs.  If the tx id is mutated and the mutated versions ends up in a block then the spent change output becomes permanently invalid.   For a site like an exchange with a large amount of withdraws (spends) it is very likely they will spend using unconfirmed change outputs and thus end up with broken outgoing payments.

More info:
https://bitcointalk.org/index.php?topic=460944.0

The "quick fix" is to have clients deal with the possibility of tx being mutated before confirmation in a more consistent and expected way.
The improvement to immutable tx ids is a long complex process which will require extensive testing.  It won't be quick.

[tacotime]

The malleability attack becomes a DOS attack. We need a quick fix. Before there is a better solution, the bitcoind should not report unconfirmed transactions. Account balance should be solely based on confirmed transactions. Before malleability is fixed (if ever), unconfirmed outputs should not be spent.

How does it become a DoS attack? Care to explain? The clients track unspent outputs before forwarding tx (or mining it). How does malleability cause a problem? I don't see any issue (non-gox) unless I missed something.

Why the quick fix? It does not seem urgent. Lets do it properly and thoughtfully.

Most current wallets will attempt to spend unconfirmed change outputs.  If the tx id is mutated and the mutated versions ends up in a block then the spent change output becomes permanently invalid.   For a site like an exchange with a large amount of withdraws (spends) it is very likely they will spend using unconfirmed change outputs and thus end up with broken outgoing payments.

More info:
https://bitcointalk.org/index.php?topic=460944.0

The "quick fix" is to have clients deal with the possibility of tx being mutated before confirmation in a more consistent and expected way.
The improvement to immutable tx ids is a long complex process which will require extensive testing.  It won't be quick.

I didn't realize that spending unspent newly generated outputs used the txid.  That's actually a potentially serious design flaw, as the core dev knew these were mutable.

To fix this at the exchange level, you can just only send outputs to clients after a new block is received once and only once... just make huge tx with all of the inputs you need to use to pay your clients and all of the outputs to all of your clients withdrawing.  Then use my proposed txid system.

[jl2012]

The malleability attack becomes a DOS attack. We need a quick fix. Before there is a better solution, the bitcoind should not report unconfirmed transactions. Account balance should be solely based on confirmed transactions. Before malleability is fixed (if ever), unconfirmed outputs should not be spent.

How does it become a DoS attack? Care to explain? The clients track unspent outputs before forwarding tx (or mining it). How does malleability cause a problem? I don't see any issue (non-gox) unless I missed something.

Why the quick fix? It does not seem urgent. Lets do it properly and thoughtfully.

Most current wallets will attempt to spend unconfirmed change outputs.  If the tx id is mutated and the mutated versions ends up in a block then the spent change output becomes permanently invalid.   For a site like an exchange with a large amount of withdraws (spends) it is very likely they will spend using unconfirmed change outputs and thus end up with broken outgoing payments.

More info:
https://bitcointalk.org/index.php?topic=460944.0

The "quick fix" is to have clients deal with the possibility of tx being mutated before confirmation in a more consistent and expected way.
The improvement to immutable tx ids is a long complex process which will require extensive testing.  It won't be quick.

I didn't realize that spending unspent newly generated outputs used the txid.  That's actually a potentially serious design flaw, as the core dev knew these were mutable.

To fix this at the exchange level, you can just only send outputs to clients after a new block is received once and only once... just make huge tx with all of the inputs you need to use to pay your clients and all of the outputs to all of your clients withdrawing.  Then use my proposed txid system.

Exchange can still send bitcoin at any time, just don't try to spend unconfirmed change. Anyway, it is always a good idea to pay multiple clients in one transaction

[DeathAndTaxes]

jl2012 got it. 

The patched reference client will include a command to set the min # of confirmations before change is unlocked (spendable).   For those running a client which support coin control you can temporarily work around the issue by selecting only confirmed outputs.

It also is likely a good idea to keep more confirmed outputs (the # of discrete outputs not necessarily the number of BTC) in the hot wallet.  This will reduce the chance of "confirmed output exhaustion" where a wallet can't make payments because all the change outputs are waiting confirmations.   

Lastly any competence business should be paying the min mandatory fee even for high priority transactions.  Paying sufficient fees becomes even more important now.  If a tx is delayed a few blocks, then the change also becomes unspendable for a few blocks.

Obviously the long term fix is to have immutable transaction ids but that is a long term fix.  The patches being considered right now will at least make the clients are "little smarter" in dealing with the reality of an attacker actively spamming duplicates into the network. 

[tacotime]

Exchange can still send bitcoin at any time, just don't try to spend unconfirmed change. Anyway, it is always a good idea to pay multiple clients in one transaction

Yeah, but the issue (I would guess?) is that exchanges were paying one client, then using the unconfirmed txid with their unspent output to pay the next client, and so on and so on... if you have a lot of money paying one client (+ change to yourself) and then are waiting one at a time for a block to confirm your last client's tx is a bad idea, because you'll lock up lots of your coins and slow down your withdrawals to a crawl (one client per 10 minutes, ouch!).  You also don't want to split your coins into tons of different key pairs because then you're accumulating expensive tx fees.  So ideally you should be doing per block settlements (which most exchanges like btc-e already were, I think).

[DeathAndTaxes]

Exchange can still send bitcoin at any time, just don't try to spend unconfirmed change. Anyway, it is always a good idea to pay multiple clients in one transaction

Yeah, but the issue (I would guess?) is that exchanges were paying one client, then using the unconfirmed txid with their unspent output to pay the next client, and so on and so on... if you have a lot of money paying one client (+ change to yourself) and then are waiting one at a time for a block to confirm your last client's tx is a bad idea, because you'll lock up lots of your coins and slow down your withdrawals to a crawl (one client per 10 minutes, ouch!).  You also don't want to split your coins into tons of different key pairs because then you're accumulating expensive tx fees.  So ideally you should be doing per block settlements (which most exchanges like btc-e already were, I think).

The number of keypairs (unqiue addresses) holding the "funds" doesn't affect the size of the transaction.  The number of discrete inputs (and outputs).  Spending two outputs send to one address isn't any smaller than spending two outputs sent to two addresses.  An exchange is going to have one input in their wallet for each deposit.  Generally that means the exchange will have hundreds of confirmed outputs.  Now depending on the value of the outputs it may take more than one per withdraw but a properly setup exchange (or other service provider which make outbound payments) should be able to process a large number of withdraws using just confirmed outputs.

So it isn't one withdrawal per block.  It is multiple withdraws each using different confirmed outputs and then next block those new change outputs will become confirmed allowing more new transactions.

If a service provider is sending deposits to a cold wallet, and then making a single transaction from the cold wallet to the hot wallet they would end up with less available outputs however there is no requirement to make the funding transaction from cold wallet to hot wallet be a single output.   As an example instead of sending  1x500 BTC to the hotwallet send 10x50 BTC and once that confirms you can process 10 not 1 withdrawals (of up to 50 BTC each).  Outputs are relatively small so you can get ~4 outputs per KB making the cost per discrete output about $0.02 right now.  That is simply the cost of doing business.  A smart exchange will monitor the number and value of their unspent outputs and take action to ensure it isn't exhausted.  For example if a large rush of withdraws reduces the number of confirmed outputs, start creating transactions which produce an extra change output (payment + change + change).  If this sounds hard and complicated ... that is why the exchange is getting paid.  They are providing a service to abstract all this from the user so it just "works".

Start to expect more from your exchange, not give them excuses on why they can't do it.

[tacotime]

^^ yeah sorry, I realized stating key pairs could be confusing after posting. I meant key pairs owned by the exchange with corresponding outputs they could spend at some pubkey hash (address).

And yeah, that's another way of doing it that could allow for more than one instance of transfers per block -- either way should work, so exchanges should still be able to function okay.