May 26, 2015

avatar

An empirical study of Namecoin and lessons for decentralized namespace design

[Let’s welcome to Freedom to Tinker first-year grad student Miles Carlsten, who, with fellow first-years Harry Kalodner and Paul Ellenbogen, worked on a neat study of Namecoin. — Arvind Narayanan]

Namecoin is a Bitcoin-like cryptocurrency that aims to create a secure decentralized namespace — that is, an online system that maps names to values, but without the need for a central authority to manage the mappings [1]. In particular, Namecoin focuses on establishing a censorship-resistant alternative to the current centralized Domain Name System (DNS).

In a new paper to be presented at WEIS 2015, we report the results of an empirical study of Namecoin. Our primary finding is that so far Namecoin hasn’t succeeded at this goal — out of about 200,000 registered names, only 28 represent non-squatted domains with non-trivial content. We argue that there’s a crucial game-theoretic component to namespaces that must be designed properly for such systems to be successful.

[Read more…]

avatar

The story behind the picture of Nick Szabo with other Bitcoin researchers and developers

Reddit seems to have discovered this picture of a group of 20 Bitcoin people having dinner, and the community seems intrigued by Nick Szabo’s public presence. It’s actually an old picture, from March 2014. I was the chief instigator of that event, so let me tell the story of how that amazing group of people happened to be assembled at Princeton’s Prospect House.

Photo credit: Matt Green

[Read more…]

avatar

Bitcoin faces a crossroads, needs an effective decision-making process

Joint post with Andrew Miller.

Virtually unknown outside the Bitcoin community, a debate is raging about whether or not to increase the maximum size of Bitcoin blocks. Blocks are created in Bitcoin roughly once every ten minutes and are currently limited to a size of 1 megabyte, putting a limit on the rate at which the network can handle transactions. At first sight this might seem like a technical decision for the developers to make and indeed it’s largely being treated that way. In reality, it has far-reaching consequences for the Bitcoin ecosystem as it is the first truly contentious decision the Bitcoin community has faced. In fact, the manner in which the community reaches — or fails to reach — consensus on this issue may set a crucial precedent for Bitcoin’s long-term ability to survive, adapt, grow, and govern itself. [1]


[Read more…]

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