November 30, 2015


Provisions: how Bitcoin exchanges can prove their solvency

Millions of Bitcoin users store their bitcoins with online exchanges (e.g. Coinbase, Kraken) which store bitcoins on their customers’ behalf. They present an interface that looks somewhat like an online bank, allowing users to log in and request payments to other users or withdrawals. For many users this approach makes a lot more sense than the traditional approach of storing private keys on your laptop or phone and interacting with the Bitcoin network directly. Online exchanges require no software installation, enable a familiar password-based authentication model, and can guard against the risk of losing funds with a stolen laptop. Online exchanges can also improve the scalability and efficiency of Bitcoin by settling many logical transactions between users without actually moving funds on the block chain.

Of course, users must trust these exchanges not to get hacked or simply abscond with their money, both of which happened frequently in the early days of Bitcoin (nearly half of exchanges studied in a 2013 research paper failed). Famously, Mt. Gox was the largest online exchange until 2014 when it lost most of its customers’ funds under murky circumstances.

It has long been a goal of the Bitcoin community for exchanges to be able to cryptographically prove solvency—that is, to prove that they still control enough bitcoins to cover all of their customers’ accounts. Greg Maxwell first proposed an approach using Merkle trees in 2013, but this requires revealing (at a minimum) the total value of the exchange’s assets and which addresses the exchange controls. Exchanges have specifically cited these privacy risks as a reason they have not deployed proofs of solvency, relying on trusted audit instead.

In a new paper presented this month at CCS (co-authored with Gaby G. Dagher, Benedikt Bünz, Jeremy Clark and Dan Boneh), we present Provisions, the first cryptographic proof-of-solvency with strong privacy guarantees. Our protocol is suitable for Bitcoin but would work for most other cryptocurrencies (e.g. Litecoin, Ethereum). Our protocol hides the total assets and liabilities of the exchange, proving only that assets are strictly greater than liabilities. If desired, the value of this surplus can be proven. Provisions also hides all customer balances and hides which Bitcoin addresses the bank controls within a configurable anonymity set of other addresses on the block chain. The proofs are large, but reasonable to compute on a daily basis (in the tens of GB for a large exchange, computable in about an hour). Best of all, it is very simple and fast for each user to verify that they have been correctly included. We can even extend the protocol to prevent collusion between exchanges. The details are in the paper, the full version of which is now online.

While our Provisions protocol removes the privacy concerns of performing a cryptographic proof-of-solvency, there are still some practical deployment questions because the proof requires the exchange to compute using its private keys. Exchanges rightly go to great lengths to protect these keys, often keeping them offline and/or in hardware security modules. Performing a regular solvency proof requires careful thinking about the right internal procedure for accessing these keys.

These deployment questions can be solved. We hope that cryptographic proofs of solvency will soon be expected of upstanding exchanges. Incidents like that of Mt. Gox have greatly damaged public perception of the entire Bitcoin ecosystem. While solvency proofs can’t prevent exchange compromises, they would have made Mt. Gox’s troubles public earlier and more clearly. They would also shore up confidence in today’s exchanges which are (presumably) solvent.

Taking a step back, solvency proofs are yet another example where we can replace an  expensive and trust-laden process in the offline world (financial inspection by a trusted auditor) with a “trustless” cryptographic protocol. It’s always exciting to take a new step in that direction. There remain limits as to what cryptography can do though. Critically, solvency proofs do not create a binding obligation to pay. A malicious exchange could complete a Provisions proof and then immediately abscond with all of the money. For this reason, some form of government regulation of online exchanges makes sense. Though regulation is dreaded by many in the Bitcoin community, it appears to be on the horizon. Bills have been proposed in several states, largely aimed at exchanges. Interestingly, the model regulatory framework proposed by the Conference of State Bank Supervisors in September already mentions cryptographic solvency proofs as a means of demonstrating solvency. We hope this recommendation is enacted in law and solvency proofs are a tool to avoid the cost of the heavyweight auditing requirements traditionally demanded of banks, while simultaneously increasing transparency for exchange customers.


Be wary of one-time pads and other crypto unicorns

Yesterday, a new messaging app called Zendo got some very favorable coverage from Tech Crunch. At the core of their sales pitch is the fact that they use one-time pads for encryption. With a few strong assumptions, namely that the pads are truly random and are only used once, it’s true that this scheme is “unbreakable” or more precisely that it offers information-theoretic guarantees that no eavesdropper can learn anything about the encrypted message. Zendo’s founder calls it a “crypto unicorn” and claims it is a game-changer in terms of security.

It isn’t. In this post I’ll explain why we don’t need (and shouldn’t want) to use one-time pads for a consumer secure-messaging app and why we should generally be wary of products like Zendo making grandiose claims about solving security problems through magic crypto. [Read more…]


Why ASICs may be good for Bitcoin

Bitcoin mining is now almost exclusively performed by Bitcoin-specific ASICs (application-specific integrated circuits). These chips are made by a few startup manufacturers and cannot be used for anything else besides mining Bitcoin or closely related cryptocurrencies [1]. Because they are somewhere between a thousand and a million times more efficient at mining Bitcoin than a general-purpose computer that you can buy for the same price, they have quickly become the only game in town.

Many have lamented the rise of ASICs, feeling it departs from the democratic “one computer, one vote” vision laid out by Satoshi Nakamoto in the original Bitcoin design. There is also significant concern that mining is now too centralized, driven by ASICs as well as the rise of mining pools. Because of this, there have been many efforts to design “ASIC-resistant” mining puzzles. One of the earliest alternatives to Bitcoin, Litecoin, chose the memory-hard scrypt instead of SHA-256 in the hope of preventing ASIC mining. Despite this, there are now ASICs for mining Litecoin and their speedup over general-purpose computers may be even greater than that of Bitcoin ASICs. Litecoin’s developers themselves have essentially given up on the principle of ASIC-resistance. Subsequent efforts have included X11, which combines eleven hash functions to attempt to make ASICs difficult to build, but it’s probably only a matter of time before X11 ASICs arise as well. It’s been convincingly argued that ASIC-resistance is probably impossible in the long-term, so we should all accept that ASICs are inevitable in a successful cryptocurrency.

I would like to expand on the argument  here though by positing that ASICs may actually make Bitcoin (and similar cryptocurrencies) more stable by ensuring that miners have a large sunk cost and depend on future mining revenues to recoup it. Even if it were technically possible to design a perfectly ASIC-resistant mining puzzle which ensured that mining was efficient on general-purpose computers, this might be a bad idea if it meant you could obtain a lot of computational capacity and use it in a destructive attack on Bitcoin without significantly devaluing your computational resources’ value. [Read more…]


Bitcoin mining is NP-hard

This post is (mostly) a theoretical curiosity, but a discussion last week at CITP during our new course on Bitcoin led us to realize that being an optimal Bitcoin miner is in fact NP-hard. NP-hardness is a complexity classification used in computer science to describe many optimization problems for which we believe there is no algorithm which can always solve such problems efficiently. We’re not talking about the well-known hash puzzle portion of Bitcoin mining here in which miners race to find a block with an unusually low hash value-that’s hard by design. Before hashing anything miners first have to assemble a candidate block by choosing which transactions to include from the set of all pending transactions. As it turns out, this requires solving two optimization problems, both of which are NP-hard!

[Read more…]


POODLE and the fundamental market failure of browser security

Last week saw the public disclosure of the POODLE vulnerability, a practical attack allowing a network attacker to steal plaintext from HTTPS connections. In particular, this attack can be used to steal authentication cookies. It’s a bad vulnerability, and it particularly hurts because it should have been fixed long ago. It only affects the ancient SSL v3 protocol, which was marked deprecated 15 years ago with the introduction of TLS v1.0.

Support for SSL should have been disabled long ago, but as has been pointed out, browser vendors delayed because they didn’t want users to lose access to outdated servers. Unfortunately, even now that we know of the POODLE bug making SSLv3 highly insecure against a competent network attacker, Firefox is the only major browser which has announced definitive plans to kill SSLv3 for good. [Read more…]


Guessing passwords with Apple’s full-device encryption

With the recently-introduced iOS 8, Apple has switched to a encrypting a much larger amount of user data by default. Matt Green has provided an excellent initial look at a technical level and big-picture level and Apple has recently released a slightly more detailed specification document and an admirable promise never to include backdoors. This move, and Google’s prompt promise to follow suit with Android, are big news. They’ve even garnered criticism from the director of the FBI and re-kindled debate about mandatory key escrow, which, as has been pointed out, is a debate the tech community seriously discussed for the last time while listening to Vanilla Ice on a cassette player in the early 90s.

It’s now 2014 and we have ample experience demonstrating that intentional backdoors are unacceptably risky and vulnerability-prone. More encryption without backdoors is a good thing and Apple should be commended for continuing to have their users’ backs. However, I’d like to sound an important note of caution though about the strength of Apple’s encryption against a determined (read: governmental) attacker:

Security is only as good as your device password is.

Encryption makes security into a matter of key management, and since iOS keys are solely derived from a password, iOS encryption makes security all about your password.

This will be a lengthy technical post, but the essential point is that security still relies on passwords, which often aren’t very good. Built-in hardware support can limit the number of guesses somebody who’s taken your phone can attempt to try to recover your data, which is a fundamental improvement over purely software encryption. Unfortunately, recent research on passwords suggests that Apple has set this rate-limiting too low, likely leaving a substantial proportion of users still at risk.

[Read more…]


On Decentralizing Prediction Markets and Order Books

In a new paper to be presented next week at WEIS by Jeremy Clark, we discuss the challenges in designing truly decentralized prediction markets and order books. Prediction markets allow market participants to trade shares in future events (such as “Will the USA advance to the knockout stage of the 2014 World Cup?”) and turn a profit from accurate predictions. Prediction markets have undergone extensive study by economists and have significant social value by providing accurate forecasts of future events.

Prediction markets have been traditionally run by centralized entities that holds all of their users’ funds and shares in escrow, don’t generally allow trades to be routed through different exchange services, and make many important decisions: which events to open a market for, what the correct outcome is, and how to match buyers with sellers. Our work examines the extent to which these tasks can be decentralized to reduce trust in single entities and increase transparency, fault-tolerance, and flexibility. Bitcoin’s success as a decentralized ledger of financial transactions suggests a decentralized prediction market may be within reach. [Read more…]


Heartbleed and passwords: don’t panic

The Heartbleed bug has captured public attention this week like few security vulnerabilities before it. This is a good thing, as indeed this is a catastrophic flaw. Many people have focused on its impact on passwords with headlines like “Security Flaw Exposes Millions Of Passwords” and “Change these passwords right now.” Heartbleed certainly could have been used to steal millions of passwords. However, while Heartbleed gives the security community plenty of new problems to worry about, it doesn’t introduce any problems for passwords that haven’t existed for a long time and I’d discourage widespread panic about passwords. [Read more…]