How a super computer could prevent future exchange hacks

Emin Gün Sirer published a paper this year [0] that described “Bitcoin vaults” [1] - a new mechanism for forcing coins to be locking up for a certain amount of time before they can be spent. The idea is for the owner to be able to recover coins during a designated clearing phase whose progress is made publicly visible on the blockchain. The owner could then recover coins from transactions [2] that he or she didn’t authorize even if their private keys were compromised. This idea is genuinely revolutionary [10] as currently owners have no way to reverse payments if they get hacked.

If something like this had of existed before the recent Bitfinex hack we might have had a chance to prevent it. Unfortunately, schemes like this rely on having to change Bitcoin’s consensus rules which is a task that’s notoriously difficult to do. Only certain changes to the code can be safely made and it requires the unanimous agreement of several experts well-versed in blockchains to change anything. Luckily, if we adapt my original idea for time-based wallets [3] we can implement something very close to Bitcoin vaults without having to change Bitcoin at all.

Poor man’s Bitcoin vaults #

There are already ways to lock coins up in Bitcoin: nlocktime [4], op_checksequenceverify [5], and op_checklocktimeverify [6], the problem is to time-lock coins in a transaction requires you to know ahead of time where the coins are going and the amount needed to be sent which you can’t know for withdrawals that haven’t happened yet.

At first I thought this point was a huge deal breaker but as it turns out if we borrow a little inspiration from ShapeShift and think of the exchange more like a vending machine that dispenses coins – the scheme becomes trivial.

Essentially, what you want to do is to start with a large number of coins to fill up your vending machine with. These coins will be what you’re going to dispense when a customer makes a withdrawal. Next, you’re going to want to split up these coins into a number of outputs. For simplicity, we’ll divide every Bitcoin into a separate 2 of 2 multi-sig address output [7][21].

This multi-sig addresses takes two keys: a hot key and a key that will end up being deleted. You’ll use the deletion key to sign a version of a transaction double-spending [8] each output to a special OP_CHECKSEQUENCEVERIFY output [22] for every possible customer’s public key and then you’ll delete the key. The signatures for these transactions are then saved into a database to be used together with signatures made by the hot key.

Now, when a customer needs to make a withdrawal they will specify a quantity of Bitcoins to withdraw and the exchange will broadcast as many transactions as needed to make this happen. The key difference with doing this is that the hot wallet can now only send Bitcoins to fixed addresses in specifically restricted time-locked transactions that allow coins to be recovered if fraud is detected. You could actually give an attacker full access to the exchange at this point and they wouldn’t be able to steal coins.

But doesn’t that require ton of transactions? #

Indeed, several billion, but as I’ll show – the scheme is still surprisingly practical. To borrow some numbers from Mtgox [9] – take the number of users (190,000) and multiply them by the coins lost (850,000 Bitcoins) to end up with roughly 162 BILLION transactions that would need to be time-locked [11]. You might be thinking, how on Earth could we ever generate such a substantial volume of transactions, not to mention index them efficiently in a database, but the problem is not as bad as it seems.

I did some basic tests and I can produce around 130 transaction signatures per second on a single core using a C-based library. Super computers like the Parallella board have 16 cores at 1 ghz per core and cost just $99 USD per board [12]. If we be conservative and assume 50 sigs per second, per core, it would cost around $124,000 USD to build a super computer that can process 850k worth of Bitcoins between 190k users in 2 days [26].

In reality, there’s no way that an exchange would need to provision that many Bitcoins for their hot wallet every week, nor do you need to repeat the work, so you could likely get away with using a cluster < one tenth the size and cost. It would all depend on the exchanges’ float, number of customers, withdrawal volumes, average trade sizes, and many other factors.

A few ways to reduce the number of transactions: #

• Increasing the amount of coins sent per output (by the way: only withdrawals that are factors of that number can be processed.)
• Optimizing output size based on typical withdrawal factors (e.g. maybe send to outputs in quantities of 1, 5, 10, etc with progressive rarity based on statistics and avoid small sizes.)
• Limiting transactions to only active users.
• Increasing the time window between withdrawals, doing the work over time (as new users join.)
• Reserving portions of coins for specific users [20] (good if you have a lot of float like ShapeShift.)
• If the exchange only processes enough coins to cover their weekly withdrawal volume between all prospective users this is likely to only take minutes to generate instead of days.

As for storing these transactions – I made a simple schema and calculated the worst case scenario using Mtgox as an example [24].

Under this schema you would need to spend a few thousand dollars extra on reliable RAID storage and backup space. So lets bump the total costs for this scheme up to 130k. That’s 130k to protect millions … potentially billions of dollars worth of Bitcoin, and for something like Bitfinex, if we assume a worst case scenario $130k is still a small price to pay to protect everyone.

It would end up costing you far more to hire a few security engineers for a year to protect a hot wallet that anyone can own at any time than it would using this super computer to protect the hot wallet for the lifetime of the company [13]. And like stated before – its likely that even a $10,000 super computer would be adequate for our purposes since most exchanges won’t need to use it to do all the work in only a 2 day period.

Other problems and drawbacks #

To utilize this scheme, the exchange needs to be able to float the expected withdrawal volume in advance, as well as to record customer’s withdrawal addresses. Exchanges like ShapeShift are ideally suited for this since they already function as a vending machine, but I argue that exchanges like Coinbase could also benefit since this scheme largely removes the need for a cold wallet and makes the hot wallet far more secure [27.]

There are a few drawbacks though. TX fees with this are notably increased (~0.02% lost) since you have to split your coins into so many separate outputs and the outputs are further increased if the divisions are smaller than 1 Bitcoin [14]. Another significant problem is what happens if all your future withdrawals are broadcast at once due to a hack? There would probably be a DoS scenario where every block would suddenly fill up and potentially prevent you from being able to use your recovery key (very bad.)

To prevent the DoS scenario: #

• Increase the lock-time window for recovery. This will slow down withdrawals but it might still be acceptable for traders who need to prioritize security over withdrawal time.
• Increase the lock-time amount among transactions to force them to be confirmed over different days.
• Only store access to a subset of time-locked transactions on the server at any given time (enough to cover your expected weekly withdrawals.)
• Hope that transactions per second in Bitcoin improves (we can hope.)

And how do you handle new user registrations? This scheme relies on allocating withdrawals to a certain address ahead of time so new users would have to be added to the processing queue each week [15] (this isn’t necessarily a deal breaker – you just have to educate your customers that they’ll need to wait at least a week for their first withdrawal. Traders can afford to wait and people who need their Bitcoins right away would probably be better served by using a decentralized exchange like BitSquare [28].)

Finally, there is also the issue of what happens when a person deposits a significantly large portion of coins and tries to make a withdrawal. Obviously the “hot wallet” isn’t provisioned for this so the client will have to wait while the new coins are worked into the withdrawal system.

Detecting fraud #

Now that there’s a way to prevent fraud what use is such a system if we can’t detect it? One simple idea is to use a smart contract - no, not the kind of smart contracts used in Bitcoin to create complex, enforcible financial agreements [16], but more the legal kind that formalizes trust relationships as described by Nick Sabzo in his original paper [17].

To utilize this idea: all actions that manipulate balances should be signed off on by both the server and the client. The client can use a browser-based signing program [18] to sign-off on actions which can then be published to a blockchain for public review. Every associated deposit and withdrawal therefore needs to be signed off on by the account owner which deducts coins from their balance as verified and backed by the ledger [23].

Under this scenario, if a huge number of withdrawals are detected without a cryptographically backed accounting record, 1 + 1 will not equal 2 and we can deduce that the withdrawal should be canceled before the funds clear. Customers will obviously still need to keep their private keys safe but at least you don’t have to sacrifice security by using a hot wallet.

What’s interesting about this is how this scheme might be applied to allow for the creation of decentralized fraud monitoring services. Essentially, anyone could monitor accounting records on the blockchain and write software to flag suspicious transactions to the owners. In fact, if there was a way to enforce that coins could only be sent to a recovery address you could outsource everything to a third-party without reducing security [19].

Tl; dr #

Bulk generating CSV-locked transactions [25] with a super computer would allow a centralized exchange to reduce theft from its hot wallets by forcing all withdrawals to require a public clearing phase before they can be spent. Coins that haven’t yet passed the clearing phase could be recovered with a fail-safe key, thereby removing the risk of handling hot wallet private keys. The scheme is further improved through the use of hardware wallets, and is compatible with all cryptocurrencies that support relative lock-times.

Credits #

The idea to use time-locked transactions has been brought up before by other people but I haven’t seen a detailed write up mentioned for hot wallet security, nor have I seen anyone mention how the brute force approach with a super computer might work (unless it was too obvious to mention.)

References & footnotes #

[0] http://fc16.ifca.ai/bitcoin/papers/MES16.pdf
[1] http://hackingdistributed.com/2016/02/26/how-to-implement-secure-bitcoin-vaults/
[2] At first this idea might seem like a contradiction to Bitcoin’s aim of having irrevocable payments but with this scheme payments are still final. The only difference is that you treat coins as final only after a certain number of confirmations have elapsed past the clearing phase.
[3] http://roberts.pm/timechain - “timed-matrix wallets”
[4] https://en.bitcoin.it/wiki/Protocol_documentation#tx
[5] https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki
[6] https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki
[7] The number you choose for divisions end up becoming the minimum quantity that the user can withdraw. The maximum quantity must be a factor or multiple of this number so if the number is too large it becomes awkward to process withdrawals, but if its too small then there’s too many transactions to sign. This will be a balance on many factors that very according to the exchange and customer-base.
[8] Yes, I did say double-spending. It doesn’t matter what transaction makes it to the blockchain since transactions can always be “reversed.”
[9] http://bitcoin.stackexchange.com/questions/40800/how-many-users-did-mt-gox-have
[10] Revolutionary for Bitcoin, sadly. The banking system has supported something similar for years.
[11] I divided the coins into groups of 1 Bitcoin but you could make them anything like 0.2 bitcoins or larger if you wish.
[12] https://www.parallella.org/board/
[13] Not to mention that the super computer could be put to use mining coins when its not being used to generate the hot wallet so its not like you’re buying a dead asset.
[14] The denominations don’t have to be too small if you set a minimum withdrawal size of say $50 or $100 USD worth of Bitcoins but its something to consider.
[15] You don’t have to do the processing each week. If you have enough float there’s no need to touch any of your “cold storage” funds for a long time. On the other hand, if you do things incrementally you can generate the new transactions however often you like. A week was used as an example.
[16] https://en.bitcoin.it/wiki/Contract
[17] http://szabo.best.vwh.net/formalize.html
[18] https://en.bitcoin.it/wiki/Browser-based_wallet#Hybrid_e-wallets
[19] The impact of a malicious fraud prevention service would then be either 1. failing to report a suspicious transaction or 2. canceling a legitimate transaction – both of which aren’t that bad.
[20] Or roughly how much the customer expects to trade on the exchange. You would also need to reserve slightly more to account for any gains during that week but these reservations could be made in the regular (double-spend) pool of funds.
[21] You could also add a third-party here like BitGo. The signature created by the deletion key (like the name implies) is deleted so that even if BitGo is hacked they can’t circumvent your transaction scheme as long as you properly handle and create transactions offline.
[22] The clock for OP_CHECKSEQUENCEVERIFY starts ticking the moment the TX is published but unlike other lock-time types – the lock-time is relative. If we were using something like OP_CHECKLOCKTIMEVERIFY the transactions would need to be deleted and resigned as the lock-time would start ticking the moment the TX was created which would be insecure.
[23] The transaction flow is like asking for permission. The first stage is to ask the hot wallet whether we can start processing the withdrawal. When that transaction is correct – the owner confirms that the withdrawal was initialized by them so that the fraud detection system doesn’t flag it.
[24] If you were really concerned about storage you could make the user store the sigs for their potential withdrawals. You also don’t need to save the full serialized transaction so that’s also a bonus.
[25] You could use a timechain to support this solution on cryptocurrencies that don’t support CSV / relative lock times – though this would end up using an insane amount of fees since you would constantly have to shuffle multi-sig outputs into new outputs if they weren’t spent otherwise the time-locked ECDSA key used in place of CSV for the time-locked transactions will have reached the point where the transaction could be broadcast with very little time left for the clearing phase. Most likely, you’re going to want to limit this scheme to CSV supported cryptocurrencies but I am noting you -could- do it with a timechain.
[26] I like cats.
[27] It’s hard to put a price on Coinbase’s hot wallet since we don’t know the volume but a typical exchange like Coinbase would have to constantly top up its hot wallet anyway, which would require handling key pairs (or secret shards) between people, thereby increasing the potential for theft, screw ups, insider jobs, etc – each time the keys are handled.
[28] I’m not a fan of collateral-based exchanges and think that the design pioneered by Coinffeine makes more sense but I have to commend them for not giving up. Decentralized exchange is a hard nut to crack.