April 25, 2015

avatar

Bitcoin is a game within a game

In this series on Bitcoin and game theory, I’ve argued that Bitcoin’s stability is fundamentally a game-theoretic proposition and shown how we’ve had blind spots for years in our theoretical understanding of mining strategy. In this post, I’ll get to the question of the discrepancy between theory and practice. As I pointed out, even though there are many theoretical weaknesses in Bitcoin’s consensus mechanism, none of these ever appear to have been exploited. [Read more…]

avatar

Bitcoin and game theory: we’re still scratching the surface

In an earlier post I argued why Bitcoin’s stability is fundamentally a game-theoretic proposition, and ended with some questions:

Can we effectively model the system with all its interacting components in the language of strategies and payoff-maximization? Is the resulting model tractable — can we analyze it mathematically or using simulations? And most importantly, do its predictions match what we observe in practice?

Let’s look at those questions in the context of a “block withholding attack” between mining pools.

Recall that mining pools are groups of individual miners who pool their computing power as well as their rewards. Suppose two mining pools — let’s call them blue and red — are both seeking to maximize their mining rewards.  Let’s say the manager of the red pool decides to infiltrate the blue pool and decrease their efficiency using some of the mining power that red (directly or indirectly) controls. This can be done by submitting shares (partial proofs of work) to earn a share of rewards, but withholding any valid blocks which are found and therefore not contributing any productive work to the blue pool. At first sight this seems like cutting off your nose to spite your face — sure, blue’s efficiency will be hurt, but red is wasting hash power as well.

[Read more…]

avatar

Threshold signatures for Bitcoin wallets are finally here

Today we are pleased to release our paper presenting a new ECDSA threshold signature scheme that is particularly well-suited for securing Bitcoin wallets. We teamed up with cryptographer Rosario Gennaro to build this scheme. Threshold signatures can be thought of as “stealth multi-signatures.” [Read more…]

avatar

Sign up now for the Bitcoin and cryptocurrency technologies online course

At Princeton I taught a course on Bitcoin and cryptocurrency technologies during the semester that just ended. Joe Bonneau unofficially co-taught it with me. Based on student feedback and what we accomplished in the course, it was extremely successful. Next week I’ll post videos of all the final project presentations.

The course was based on a series of video lectures. We’re now offering these lectures free to the public, online, together with homeworks, programming assignments, and a textbook. We’ve heard from computer science students at various institutions as well as the Bitcoin community about the need for structured educational materials, and we’re excited to fill this need.

We’re using Piazza as our platform. Here’s the course page. To sign up, please fill out this (very short) form.

The first several book chapters are already available. The course starts February 16, and we’ll start making the videos available closer to that date (you’ll need to sign up to watch the videos Edit: we’ve changed this policy; the lectures are also publicly available). Each week there will be a Google hangout with that week’s lecturer. We’ll also answer questions on Piazza.

[Read more…]

avatar

Consensus in Bitcoin: One system, many models

At a technical level, the Bitcoin protocol is a clever solution to the consensus problem in computer science. The idea of consensus is very general — a number of participants together execute a computation to come to agreement about the state of the world, or a subset of it that they’re interested in.

Because of this generality, there are different methods for analyzing and proving things about such consensus protocols, coming from different areas of applied math and computer science. These methods use different languages and terminology and embody different assumptions and views. As a result, they’re not always consistent with each other. This is a recipe for confusion; often people disagree because they’ve implicitly assumed one world-view or another. In this post I’ll explain the two main sets of models that are used to analyze the security of consensus in Bitcoin.

[Read more…]

avatar

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…]

avatar

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…]

avatar

It’s time to bring Bitcoin and cryptocurrencies into the computer science curriculum

In the privacy technologies grad seminar that I taught last semester, Bitcoin proved to be the most popular topic among students. Two groups did very different and equally interesting final projects on Bitcoin and cryptocurrencies; more on that below.

More broadly, we’re seeing a huge demand for learning the computer science underlying Bitcoin, both at Princeton and elsewhere. But research papers on Bitcoin don’t make for great teaching materials. Identifying the core ideas, building them up in logical progression, and connecting them to other areas of computer science is a challenging task.

Over the summer, I teamed up with Joe Bonneau, Ed Felten, and Andrew Miller to do just that. We’ve produced a lecture series which will start going online soon. While we spend some time in the lectures on the specifics of Bitcoin, much of our discussion is about the underlying principles which apply to cryptocurrencies in general. Steven Goldfeder and other students are working with us to produce homeworks, programming assignments, and a textbook, which will together comprise a complete online course. We’ll announce it here when it launches.
[Read more…]

avatar

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…]

avatar

Bitcoin Mining Now Dominated by One Pool

The big news in the Bitcoin world, is that one entity, called GHash, seems to be in control of more than half of all of the mining power. A part of Bitcoin’s appeal has been its distributed nature: the idea that no one party is in control but the system operates through the cooperative action of a large community. The worry now is that GHash has too much power and that this could destabilize the Bitcoin system. Today I want to explain what has happened, why it provokes worry, and how I see the situation.
[Read more…]