August 29, 2016

Arvind Narayanan is an Assistant Professor of Computer Science at Princeton, and an affiliated faculty member at the Center for Information Technology Policy. He was previously a post-doctoral fellow at the Stanford Computer Science department and a Junior Affiliate Scholar at the Stanford Law School Center for Internet and Society. He studies privacy from a multidisciplinary perspective, focusing on the intersection between technology, law and policy. His research has shown that data anonymization is broken in fundamental ways, for which he jointly received the 2008 Privacy Enhancing Technologies Award. He is one of the researchers behind the "Do Not Track" proposal. You can follow Arvind on Twitter at @random_walker and on Google+ here.

avatar

Language necessarily contains human biases, and so will machines trained on language corpora

I have a new draft paper with Aylin Caliskan-Islam and Joanna Bryson titled Semantics derived automatically from language corpora necessarily contain human biases. We show empirically that natural language necessarily contains human biases, and the paradigm of training machine learning on language corpora means that AI will inevitably imbibe these biases as well.

Specifically, we look at “word embeddings”, a state-of-the-art language representation used in machine learning. Each word is mapped to a point in a 300-dimensional vector space so that semantically similar words map to nearby points.

We show that a wide variety of results from psychology on human bias can be replicated using nothing but these word embeddings. We primarily look at the Implicit Association Test (IAT), a widely used and accepted test of implicit bias. The IAT asks subjects to pair concepts together (e.g., white/black-sounding names with pleasant or unpleasant words) and measures reaction times as an indicator of bias. In place of reaction times, we use the semantic closeness between pairs of words.

In short, we were able to replicate every single result that we tested, with high effect sizes and low p-values.

These include innocuous, universal associations (flowers are associated with pleasantness and insects with unpleasantness), racial prejudice (European-American names are associated with pleasantness and African-American names with unpleasantness), and a variety of gender stereotypes (for example, career words are associated with male names and family words with female names).

But we go further. We show that information about the real world is recoverable from word embeddings to a striking degree. The figure below shows that for 50 occupation words (doctor, engineer, …), we can accurately predict the percentage of U.S. workers in that occupation who are women using nothing but the semantic closeness of the occupation word to feminine words!

These results simultaneously show that the biases in question are embedded in human language, and that word embeddings are picking up the biases.

Our finding of pervasive, human-like bias in AI may be surprising, but we consider it inevitable. We mean “bias” in a morally neutral sense. Some biases are prejudices, which society deems unacceptable. Others are facts about the real world (such as gender gaps in occupations), even if they reflect historical injustices that we wish to mitigate. Yet others are perfectly innocuous.

Algorithms don’t have a good way of telling these apart. If AI learns language sufficiently well, it will also learn cultural associations that are offensive, objectionable, or harmful. At a high level, bias is meaning. “Debiasing” these machine models, while intriguing and technically interesting, necessarily harms meaning.

Instead, we suggest that mitigating prejudice should be a separate component of an AI system. Rather than altering AI’s representation of language, we should alter how or whether it acts on that knowledge, just as humans are able to learn not to act on our implicit biases. This requires a long-term research program that includes ethicists and domain experts, rather than formulating ethics as just another technical constraint in a learning system.

Finally, our results have implications for human prejudice. Given how deeply bias is embedded in language, to what extent does the influence of language explain prejudiced behavior? And could transmission of language explain transmission of prejudices? These explanations are simplistic, but that is precisely our point: in the future, we should treat these as “null hypotheses’’ to be eliminated before we turn to more complex accounts of bias in humans.

avatar

Can Facebook really make ads unblockable?

[This is a joint post with Grant Storey, a Princeton undergraduate who is working with me on a tool to help users understand Facebook’s targeted advertising.]

Facebook announced two days ago that it would make its ads indistinguishable from regular posts, and hence impossible to block. But within hours, the developers of Adblock Plus released an update which enabled the tool to continue blocking Facebook ads. The ball is now back in Facebook’s court. So far, all it’s done is issue a rather petulant statement. The burning question is this: can Facebook really make ads indistinguishable from content? Who ultimately has the upper hand in the ad blocking wars?

There are two reasons — one technical, one legal — why we don’t think Facebook will succeed in making its ads unblockable, if a user really wants to block them.

The technical reason is that the web is an open platform. When you visit facebook.com, Facebook’s server sends your browser the page content along with instructions on how to render them on the screen, but it is entirely up to your browser to follow those instructions. The browser ultimately acts on behalf of the user, and gives you — through extensions — an extraordinary degree of control over its behavior, and in particular, over what gets displayed on the screen. This is what enables the ecosystem of ad-blocking and tracker-blocking extensions to exist, along with extensions for customizing web pages in various other interesting ways.

Indeed, the change that Adblock Plus made in order to block the new, supposedly unblockable ads is just a single line in the tool’s default blocklist:

facebook.com##div[id^="substream_"] div[id^="hyperfeed_story_id_"][data-xt]

What’s happening here is that Facebook’s HTML code for ads has slight differences from the code for regular posts, so that Facebook can keep things straight for its own internal purposes. But because of the open nature of the web, Facebook is forced to expose these differences to the browser and to extensions such as Adblock Plus. The line of code above allows Adblock Plus to distinguish the two categories by exploiting those differences.

Facebook engineers could try harder to obfuscate the differences. For example, they could use non-human-readable element IDs to make it harder to figure out what’s going on, or even randomize the IDs on every page load. We’re surprised they’re not already doing this, given the grandiose announcement of the company’s intent to bypass ad blockers. But there’s a limit to what Facebook can do. Ultimately, Facebook’s human users have to be able to tell ads apart, because failure to clearly distinguish ads from regular posts would run headlong into the Federal Trade Commission’s rules against misleading advertising — rules that the commission enforces vigorously. [1, 2] And that’s the second reason why we think Facebook is barking up the wrong tree.

Facebook does allow human users to easily recognize ads: currently, ads say “Sponsored” and have a drop-down with various ad-related functions, including a link to the Ad Preferences page. And that means someone could create an ad-blocking tool that looks at exactly the information that a human user would look at. Such a tool would be mostly immune to Facebook’s attempts to make the HTML code of ads and non-ads indistinguishable. Again, the open nature of the web means that blocking tools will always have the ability to scan posts for text suggestive of ads, links to Ad Preferences pages, and other markers.

But don’t take our word for it: take our code for it instead. We’ve created a prototype tool that detects Facebook ads without relying on hidden HTML code to distinguish them. [Update: the source code is here.] The extension examines each post in the user’s news feed and marks those with the “Sponsored” link as ads. This is a simple proof of concept, but the detection method could easily be made much more robust without incurring a performance penalty. Since our tool is for demonstration purposes, it doesn’t block ads but instead marks them as shown in the image below.  

All of this must be utterly obvious to the smart engineers at Facebook, so the whole “unblockable ads” PR push seems likely to be a big bluff. But why? One possibility is that it’s part of a plan to make ad blockers look like the bad guys. Hand in hand, the company seems to be making a good-faith effort to make ads more relevant and give users more control over them. Facebook also points out, correctly, that its ads don’t contain active code and aren’t delivered from third-party servers, and therefore aren’t as susceptible to malware.

Facebook does deserve kudos for trying to clean up and improve the ad experience. If there is any hope for a peaceful resolution to the ad blocking wars, it is that ads won’t be so annoying as to push people to install ad blockers, and will be actually useful at least some of the time. If anyone can pull this off, it is Facebook, with the depth of data it has about its users. But is Facebook’s move too little, too late? On most of the rest of the web, ads continue to be creepy malware-ridden performance hogs, which means people will continue to install ad blockers, and as long as it is technically feasible for ad blockers to block Facebook ads, they’re going to continue to do so. Let’s hope there’s a way out of this spiral.

[1] Obligatory disclaimer: we’re not lawyers.

[2] Facebook claims that Adblock Plus’s updates “don’t just block ads but also posts from friends and Pages”. What they’re most likely referring to that Adblock Plus blocks ads that are triggered by one of your friends Liking the advertiser’s page. But these are still ads: somebody paid for them to appear in your feed. Facebook is trying to blur the distinction in its press statement, but it can’t do that in its user interface, because that is exactly what the FTC prohibits.

avatar

The workshop on Data and Algorithmic Transparency

From online advertising to Uber to predictive policing, algorithmic systems powered by personal data affect more and more of our lives. As our society begins to grapple with the consequences of this shift, empirical investigation of these systems has proved vital to understand the potential for discrimination, privacy breaches, and vulnerability to manipulation.

This emerging field of research, which we’re calling Data and Algorithmic Transparency, seems poised to grow dramatically. But it faces a number of methodological challenges which can only be solved by bringing together expertise from a variety of disciplines. That is why Alan Mislove and I are organizing the first workshop on Data and Algorithmic Transparency at Columbia University on Nov 19, 2016.

Here are three reasons you should participate in this workshop.

  1. Start of a new, interdisciplinary community. The set of disciplines represented on the Program Committee is strikingly diverse: Internet measurement, information privacy/security, computer systems, human-computer interaction, law, and media studies. Industrial research and government are also represented. We expect the workshop itself to have a similar mix of participants, and that is exactly what is needed to make transparency research a success. Alan and I (and others including Nikolaos Laoutaris) are committed to growing and nurturing this community over the next several years.
  1. Co-located with two other exciting events: the Data Transparency Lab conference (DTL ‘16) and the Fairness, Accountability, and Transparency in Machine Learning workshop (FAT-ML ‘16). DTL shares many of the goals of the DAT workshop, but is non-academic. FAT-ML has a complementary relationship with the goals of DAT: it seeks to develop machine learning techniques for developers of algorithmic systems to improve fairness and accountability, whereas DAT seeks to analyze existing systems, typically “from the outside”. The events are consecutive and non-overlapping, and participants of each event are encouraged to attend the others.
  1. A format that makes the most of everyone’s time. At most computer science conferences, each speaker mumbles through their slides while the audience is a sea of laptops, awaiting their turn. DAT will be the opposite. We plan to have paper discussions instead of paper presentations, with commenters and participants, rather than authors, doing most of the speaking about each paper. This first edition of DAT will be non-archival (but peer-reviewed), and one goal of the discussions is to help authors improve their papers for later publication. We are also soliciting talk proposals about already published work; groups of accepted talks will be organized into panels.

See you in New York City!

avatar

The Princeton Bitcoin textbook is now freely available

The first complete draft of the Princeton Bitcoin textbook is now freely available. We’re very happy with how the book turned out: it’s comprehensive, at over 300 pages, but has a conversational style that keeps it readable.

If you’re looking to truly understand how Bitcoin works at a technical level and have a basic familiarity with computer science and programming, this book is for you. Researchers and advanced students will find the book useful as well — starting around Chapter 5, most chapters have novel intellectual contributions.

Princeton University Press is publishing the official, peer-reviewed, polished, and professionally done version of this book. It will be out this summer. If you’d like to be notified when it comes out, you should sign up here.

Several courses have already used an earlier draft of the book in their classes, including Stanford’s CS 251. If you’re an instructor looking to use the book in your class, we welcome you to , and we’d be happy to share additional teaching materials with you.

Online course and supplementary materials. The Coursera course accompanying this book had 30,000 students in its first version, and it was a success based on engagement and end-of-course feedback. 

We plan to offer a version with some improvements shortly. Specifically, we’ll be integrating the programming assignments developed for the Stanford course with our own, with Dan Boneh’s gracious permission. We also have tenative plans to record a lecture on Ethereum (we’ve added a discussion of Ethereum to the book in Chapter 10).

Finally, graduate students at Princeton have been leading the charge on several exciting research projects in this space. Watch this blog or my Twitter for updates.

avatar

“Private blockchain” is just a confusing name for a shared database

Banks and financial institutions seem to be all over the blockchain. It seems they agree with the Bitcoin community that the technology behind Bitcoin can provide an efficient platform for settlement and for issuing digital assets. Curiously, though, they seem to shy away from Bitcoin itself. Instead, they want something they have more control over and doesn’t require exposing transactions publicly. Besides, Bitcoin has too much of an association in the media with theft, crime, and smut — no place for serious, upstanding bankers. As a result, the buzz in the financial industry is about “private blockchains.”

But here’s the thing — “private blockchain” is just a confusing name for a shared database.

The key to Bitcoin’s security (and success) is its decentralization which comes from its innovative use of proof-of-work mining. However, if you have a blockchain where only a few companies are allowed to participate, proof-of-work doesn’t make sense any more. You’re left with a system where a set of identified (rather than pseudonymous) parties maintain a shared ledger, keeping tabs on each other so that no single party controls the database. What is it about a blockchain that makes this any better than using a regular replicated database?

Supporters argue that the blockchain’s crypto, including signatures and hash pointers, is what distinguishes a private blockchain from a vanilla shared database. The crypto makes the system harder to tamper with and easier to audit. But these aspects of the blockchain weren’t Bitcoin’s innovation! In fact, Satoshi tweaked them only slightly from the earlier research that he cites in his whitepaper research by Haber and Stornetta going all the way back to 1991!

Here’s my take on what’s going on:

  • It is true that adding signatures and hash pointers makes a shared database a bit more secure. However, it’s qualitatively different from the level of security, irreversibility, and censorship-resistance you get with the public blockchain.
  • The use of these crypto techniques for building a tamper-resistant database has been known for 25 years. At first there wasn’t much impetus for Wall Street to pay attention, but gradually there has arisen a great opportunity in moving some types of financial infrastructure to an automated, cryptographically secured model.
  • For banks to go this route, they must learn about the technology, get everyone to the same table, and develop and deploy a standard. The blockchain conveniently solves these problems due to the hype around it. In my view, it’s not the novelty of blockchain technology but rather its mindshare that has gotten Wall Street to converge on it, driven by the fear of missing out. It’s acted as a focal point for standardization.
  • To build these private blockchains, banks start with the Bitcoin Core code and rip out all the parts they don’t need. It’s a bit like hammering in a thumb tack, but if a hammer is readily available and no one’s told you that thumb tacks can be pushed in by hand, there’s nothing particularly wrong with it.

Thanks to participants at the Bitcoin Pacifica gathering for helping me think through this question. 

avatar

Bitcoin course available on Coursera; textbook is now official

Earlier this year we made our online course on Bitcoin publicly available 11 video lectures and draft chapters of our textbook-in-progress, including exercises. The response has been very positive: numerous students have sent us thanks, comments, feedback, and a few error corrections. We’ve heard that our materials are being used in courses at a few universities. Some students have even translated the chapters to other languages.

Coursera. I’m very happy to announce that the course is now available as a Princeton University online course on Coursera. The first iteration starts next Friday, September 4. The Coursera version offers embedded quizzes to test your understanding; you’ll also be part of a community of students to discuss the lectures with (about 10,000 15,000 have already signed up). We’ve also fixed all the errors we found thanks to the video editing skillz of the Princeton Broadcast Center folks. Sign up now, it’s free!

We’re closely watching ongoing developments in the cryptocurrency world such as Ethereum. Whenever a body of scientific knowledge develops around a new area, we will record additional lectures. The Coursera class already includes one additional lecture: it’s on the history of cryptocurrencies by Jeremy Clark. Jeremy is the ideal person to give this lecture for many reasons, including the fact that he worked with David Chaum for many years.

Jeremy Clark lecturing on the history of cryptocurrencies

Textbook. We’re finishing the draft of the textbook; Chapter 8 was released today and the rest will be coming out in the next few weeks. The textbook closely follows the structure of the lectures, but the textual format has allowed us to refine and polish the explanations, making them much clearer in many places, in my opinion.

I’m excited to announce that we’ll be publishing the textbook with Princeton University Press. The draft chapters will continue to be available free of charge, but you should buy the book it will be peer reviewed, professionally edited and typeset, and the graphics will be re-done professionally.

Finally, if you’re an educator interested in teaching Bitcoin, write to us and we’ll be happy to share with you some educational materials that aren’t yet public.

avatar

Analyzing the 2013 Bitcoin fork: centralized decision-making saved the day

On March 11, 2013, Bitcoin experienced a technical crisis. Versions 0.7 and 0.8 of the software diverged from each other in behavior due to a bug, causing the block chain to “fork” into two. Considering how catastrophic a hard fork can be, the crisis was resolved quickly with remarkably little damage owing to the exemplary competence of the developers in charge. The event gives us a never-before-never-again look into Bitcoin’s inner workings. In this post, I’ll do a play-by-play analysis of the dramatic minutes, and draw many surprising lessons. For a summary of the event, see here.

First of all, the incident shows the necessity of an effective consensus process for the human actors in the Bitcoin ecosystem. The chronology of events was like this: it took about an hour after the fork started for enough evidence to accumulate that a fork was afoot. Once that was understood, things unfolded with remarkable speed and efficiency. The optimal course of action (and, in retrospect, the only one that avoided serious risks to the system) was first proposed and justified 16 minutes later, and the developers reached consensus on it a mere 20–25 minutes after that. Shortly thereafter — barely an hour after the discovery of the fork — the crisis response had effectively and successfully concluded. It took a few hours more for the fork to heal based on the course of action the developers initiated, but the outcome wasn’t in doubt.

More surprisingly, it also shows the effectiveness of strong central leadership. That’s because the commonsense solution to the fork — as well as the one programmed into the software itself — was to encourage miners running old versions to upgrade. As it turns out, the correct response was exactly the opposite. Even a delay of a few hours in adopting the downgrade solution would have been very risky, as I’ll argue, with potentially devastating consequences. Without the central co-ordination of the Bitcoin Core developers and the strong trust that the community places in them, it is inconceivable that adopting this counterintuitive solution could have been successfully accomplished.

Further, two more aspects of centralization proved very useful, although perhaps not as essential. The first is the ability of a few developers who possess a cryptographic key to broadcast alert messages to every client, which in this case was used to urge them to downgrade. The second is the fact that the operator of BTC Guild, a large mining pool at the time, was able to singlehandedly shift the balance of mining power to the old branch by downgrading. If it weren’t for this, it would have resulted in a messy “coordination problem” among miners, and we can imagine each one hesitating, waiting for someone else to take the leap.

Since most of the discussion and decision-making happened on the #bitcoin-dev IRC channel, it remains publicly archived and offers a remarkable window into the Core developers’ leadership and consensus process. Consensus operated at remarkable speed, in this instance faster than consensus happens in the Bitcoin network itself. The two levels of consensus are intricately connected.

Let’s now dive into the play-by-play analysis of the fork and the reaction to it. I’ve annotated the transcript of selected, key events from the IRC log of that fateful night. I’ve made minor edits to make the log easier to read — mainly replacing the nicknames of prominent community members with their real names, since their identities are salient to the discussion.

Signs of trouble

The first signs that something is wrong come from a miner with nickname thermoman, as well as Jouke Hofman, a Dutch exchange operator, who report strange behavior from their Bitcoin clients. Bitcoin core developer Pieter Wuille helps them debug these problems, but at this point everyone assumes these are problems local to the two users, rather than something on the network. But around 23:00, a variety of other services showing strange behavior are noticed (blockchain.info, blockexplorer.com, and the IRC bot that reports the status of the network), making it obvious that something’s wrong on the network. Luke Dashjr, a prominent developer, spells out the unthinkable:

  23:06  Luke Dashjr		so??? yay accidental hardfork? :x
  23:06  Jouke Hofman		Holy crap

Over the next few minutes people convince themselves that there’s a fork and that nodes running the 0.8 and the 0.7 versions are on different sides of it. Things progress rapidly from here. A mere five minutes later the first measure to mitigate the damage is taken by Mark Karpeles, founder of Mt. Gox:

  23:11  Mark Karpeles		I've disabled the import of bitcoin blocks for now
				until this is sorted out
  23:13  Luke Dashjr		I'm trying to contact poolops [mining pool operators]

It’s pretty obvious at this point that the best short-term fix is to get everyone on one side of the fork. But which one?

Up or down? The critical decision

At 23:18, Pieter Wuille sends a message to the bitcoin-dev mailing list, informing them of the problem. But he hasn’t fully grasped the nature of the fork yet, stating “We risk having (several) forked chains with smaller blocks” and suggests upgrading as the solution. This is unfortunate, but it’s the correct thing to do given his understanding of the fork. This email will stay uncorrected for 45 minutes, and is arguably the only slight misstep in the developer response.

  23:21  Luke Dashjr		at least 38% [of hashpower] is on 0.8 right now
				otoh, that 38% is actively reachable

Dashjr seems to suggest that the 0.8 0.7 downgrade is better because the operators of newly upgraded nodes are more likely to be reachable by the developers to convince them to downgrade. This is a tempting argument. Indeed, when I describe the fork in class and ask my students why the developers picked the downgrade rather than the upgrade, this is the explanation they always come up with. When I push them to think harder, a few figure out the right answer, which Dashjr points out right afterward:

  23:22  Gavin Andresen		the 0.8 fork is longer, yes? So majority hashpower is 0.8....
  23:22  Luke Dashjr		Gavin Andresen: but 0.8 fork is not compatible
				earlier will be accepted by all versions

Indeed! The behavior of the two versions is not symmetric. Upgrading will mean that the fork will persist essentially indefinitely, while downgrading will end it relatively quickly.

(Lead developer) Gavin Andresen still protests, but Wuille also accepts Dashjr’s explanation:

  23:23  Gavin Andresen		first rule of bitcoin: majority hashpower wins
  23:23  Luke Dashjr		if we go with 0.8, we are hardforking
  23:23  Pieter Wuille		the forking action is a too large block
				if we ask miners to switch temporarily to smaller blocks again,
				we should get to a single chain soon
				with a majority of miners on small blocks, there is no risk
  23:24  Luke Dashjr		so it's either 1) lose 6 blocks, or 2) hardfork for no benefit
  23:25  BTC Guild		We'll lose more than 6

BTC Guild was a large pool at the time, and its operator happened to be online. They are correct — the 0.8 branch had 6 blocks at the time, but was growing much faster than the 0.7 branch and would continue to grow until the latter gradually caught up. Eventually 24 blocks would be lost. BTC Guild will turn out to be a key player, as we will soon see.

More explanation for why downgrade is the right approach:

  23:25  Pieter Wuille		all old miners will stick to their own chain
				regardless of the mining power behind the other
  23:25  Luke Dashjr		and the sooner we decide on #1, the fewer it loses
  23:26  Pieter Wuille		even with 90% of mining power on 0.8
				all merchants on an old client will be vulnerable
  23:26  Luke Dashjr		if we hardfork, all Bitcoin service providers have an emergency situation
  23:30  Pieter Wuille		and we _cannot_ get every bitcoin user in the world
				to now instantly switch to 0.8
				so no, we need to rollback to the 0.7 chain

Achtung!

Many Bitcoin users are not aware of the centralized ability in Bitcoin for a few developers to send out alert messages. Not only does it exist, it becomes crucial here, as Core developer Jeff Garzik and another user point out:

  23:31  Jeff Garzik		alert is definitely needed
  23:31  jrmithdobbs		also, if this isn't an alert message scenario 
				I don't know what is, where's that at? :)

A bit of a comic interlude from the operator of ozcoin, another mining pool:

  23:31  Graet			ozcoin wont even get looked at for an hour or so
  23:31  Graet			no-one is avalable and i need to take kids to school

The situation is urgent (the more clients upgrade, the harder it will be to convince everyone to downgrade):

  23:32  phantomcircuit		0.7 clients are already displaying a big scary warning
				Warning: Displayed transactions may not be correct!
				You may need to upgrade, or other nodes may need to upgrade.
				unfortunately i suspect that warning will get people to upgrade

Other complications due to custom behavior of some miners’ software:

  23:35  lianj			oh, damn. anyhow please keep us guys updated which code change is made 
				to solve the problem. our custom node does .8 behavior

Gavin Andresen and Jeff Garzik still aren’t convinced (they seem to be thinking about getting 0.8 nodes to switch to the other branch, rather than the more blunt solution of asking miners to downgrade the client)

  23:34  Jeff Garzik		and how to tell bitcoind "mine on $this old fork"
  23:35  Gavin Andresen		exactly. Even if we want to roll back to the 0.7-compatible chain, 
				I don't see an easy way to do that.

This shows the usefulness of the developers having direct channels to the pool operators, another benefit of central co-ordination:

  23:38  Luke Dashjr		FWIW, Josh (EclipseMC) has to be on a plane in 20 minutes,
				so he needs this decided before then :/

As time goes on the solution only gets harder, as illustrated by a new user wading into the channel.

  23:39  senseless		So whats the issue?
				I got the warning you need to upgrade. So I upgraded.

Gavin Andresen, notable for his cautious approach, brings up a potential problem:

  23:40  Gavin Andresen		If we go back to 0.7, then we risk some other block 
				triggering the same condition.

Happily, as others pointed out, there’s nothing to worry about — once majority hashpower is on 0.7, other blocks that have the same condition will be harmless one-block forks instead of a hard fork.

The BTC guild operator offers to basically end the fork:

  23:43  BTC Guild		I can single handedly put 0.7 back to the majority hash power
				I just need confirmation that thats what should be done
  23:44  Pieter Wuille		BTC Guild: imho, that is was you should do,
				but we should have consensus first

So much for decentralization! The fact that BTC Guild can tip the scales here is crucial. (The hash power distribution at that time appears to be roughly 2/3 vs 1/3 in favor of the 0.8 branch, and BTC Guild controlled somewhere between 20% and 30% of total hash power.) By switching, BTC Guild loses the work they’ve done on 0.8 since the fork started. On the other hand, they are more or less assured that the 0.7 branch will win and the fork will end, so at least their post-downgrade mining power won’t be wasted.

If mining power were instead distributed among thousands of small independent miners, it’s far from clear that coordinating them would be possible at all. More likely, each miner on the 0.8 branch would wait for the 0.7 branch to gain the majority hash power, or at least for things to start heading clearly in that direction, before deciding to downgrade. Meanwhile, some miners in the 0.7 branch, seeing the warning in their clients and unaware of the developer recommendation, would in fact upgrade. The 0.8 branch would pull ahead faster and faster, and pretty soon the window of opportunity would be lost. In fact, if the developers had delayed their decision by even a few hours, it’s possible that enough miners would have upgraded from 0.7 to 0.8 that no single miner or pool operator would be able to reverse it singlehandedly, and then it’s anybody’s guess as to whether the downgrade solution would have worked at all.

Back to our story: we’re nearing the critical moment.

  23:44  Jeff Garzik		ACK on preferring 0.7 chain, for the moment
  23:45  Gavin Andresen		BTC Guild: if you can cleanly get us back on the 0.7 chain,
				ACK from here, too

Consensus is reached!

Time for action

Right away, developers start giving out advice to downgrade:

  23:49  Luke Dashjr		surge_: downgrade to 0.7 if you mine, or just wait
  23:50  Pieter Wuille		doublec: do you operate a pool?
  23:50  doublec		yes
  23:50  Pieter Wuille		doublec: then please downgrade now

BTC Guild gets going immediately…

  23:51  BTC Guild		BTC Guild is going back to full default block settings and 0.7 soon.
  00:01  BTC Guild		Almost got one stratum node moved

… even at significant monetary cost.

  23:57  BTC Guild		I've lost way too much money in the last 24 hours
				from 0.8

One way to look at this is that BTC Guild sacrificed revenues for the good of the network. But these actions can also be justified from a revenue-maximizing perspective. If the BTC Guild operator believed that the 0.7 branch would win anyway (perhaps the developers would be able to convince another large pool operator), then moving first is relatively best, since delaying would only take BTC Guild further down the doomed branch. Either way, the key factor enabling BTC Guild to confidently downgrade is that by doing so, they can ensure that the 0.7 branch will win.

Now that the decision has been taken, it’s time to broadcast an alert to all nodes:

  00:07  Gavin Andresen		alert params set to relay for 15 minutes, expire after 4 hours

The alert in question is a model of brevity: “URGENT: chain fork, stop mining on version 0.8”

At this point people start flooding the channel and chaos reigns. However, the work is done, and only one final step remains.

At 00:29, Pieter Wuille posts to bitcointalk. This essentially concludes the crisis response. The post said, in its entirety:

Hello everyone,

there is an emergency right now: the block chain has split between 0.7+earlier and 0.8 nodes. I’ll explain the reasons in a minute, but this is what you need to know now:

  • After a discussion on #bitcoin-dev, it seems trying to get everyone on the old chain again is the least risky solution.
  • If you’re a miner, please do not mine on 0.8 code. Stop, or switch back to 0.7. BTCGuild is switching to 0.7, so the old chain will get a majority hash rate soon.
  • If you’re a merchant: please stop processing transactions until the chains converge.
  • If you’re on 0.7 or older, the client will likely tell you that you need to upgrade. Do not follow this advise – the warning should go away as soon as the old chain catches up
  • If you are not a merchant or a miner, don’t worry.

Crucially, note that he was able to declare that the 0.7 branch was going to win due to BTC Guild switching to it. This made the downgrade decision the only rational one for everyone else, and from here things were only a matter of time.

What would have happened if the developers had done nothing?

Throughout the text I’ve emphasized that the downgrade option was the correct one and that speed of developer response was of the essence. Let’s examine this claim further by thinking about what would have happened if the developers had simply let things take their course. Vitalik Buterin thinks everything would have been just fine: “if the developers had done nothing, then Bitcoin would have carried on nonetheless, only causing inconvenience to those bitcoind and BitcoinQt users who were on 0.7 and would have had to upgrade.”

Obviously, I disagree. We can’t know for sure what would have happened, but we can make informed guesses. First of all, the fork would have gone on for far longer — essentially until every last miner running version 0.7 or lower either shut down or upgraded their software. Given that many miners leave their setups unattended and others have custom setups that aren’t easy to upgrade quickly, the fork would have lasted days. This would have several effects. Most obviously, the psychological impact of an ongoing fork would have been serious. In contrast, as events actually turned out, the event happened overnight in the US and had been resolved the next morning, and media coverage praised the developers for their effective action. The price of Bitcoin dropped by 25% during the incident but recovered immediately to almost its previous value.

Another adverse impact is that exchanges or payment services that took too long to upgrade their clients (or disable transactions) might find themselves victims of large double-spend attacks. As it happened, OKPay suffered a $10,000 double spend. This was done by a user trying to prove a point and who revealed the details publicly; they got lucky in that their payment to OKPay was confirmed by the 0.8 branch but not 0.7. A longer-running fork would likely have exacerbated the problem and allowed malicious attackers to figure out a systematic way to create double-spend transactions. [1]

Worse, it is possible, even if not likely, that the 0.7 branch might have continued indefinitely. Obviously, if this did happen, it would be devastating for Bitcoin, resulting in a fork of the currency itself. One reason the fork might keep going is because of a “Goldfinger attacker” interested in de-stabilizing Bitcoin: they might not have the resources to execute a 51% attack, but the fork might give them just the opportunity they need: they could simply invest resources into keeping the 0.7 fork alive instead of launching an attack from scratch.

There’s another reason why the fork might have never ended. Miners who postponed their decision to switch from 0.7 to 0.8 by, say, a week would face the distasteful prospect of forgoing a week’s worth of mining revenue. They might instead gamble and continue to operate on the 0.7 branch as a big fish in a small pond. If the 0.7 branch had, say, 10% of the mining power of the 0.8 branch, the miner’s revenue would be multiplied tenfold by mining on the 0.7 branch. Of course, the currency they’d earn would be “Bitcoin v0.7”, which would fork into a different currency from “Bitcoin v0.8”, and would be worth much less, the latter being considered the legitimate Bitcoin. We analyze this type of situation in Chapter 7, “Community, Politics, and Regulation” of our Bitcoin textbook-in-progress or the corresponding sections of the video lecture.

While the exact course of events that would have resulted from inaction is debatable, it is clear that the downgrade solution is by far the less risky one, and the speed and clearheadedness of the developers’ response is commendable.

All this is in stark contrast to the dysfunctional state of the consensus process on the block size issue. Why is consensus on that issue failing? The main reason is that unlike the fork, there is no correct solution to the block size issue; instead there are various parties with differing goals that aren’t mutually aligned. Further, in the case of the fork, the developers had a well-honed process for coming to consensus on technical questions including bugs. For example, it was obvious to everyone that the discussion of the fork should take place on the #bitcoin-dev IRC channel; this didn’t even need to be said. On the other hand, there is no clear process for debating the block size issue, and the discussion is highly fragmented between different channels. Finally, once the developers had reached consensus about the fork, the community went with that decision because they trusted the developers’ technical competence. On the other hand, there is no single entity that the Bitcoin community trusts to make decisions that have economic implications.

Conclusion

In summary, we have a lot to learn from looking back at the fork. Bitcoin had a really close call, and another bug might well lead to a different outcome. Contrary to the view of the consensus protocol as fixed in stone by Satoshi, it is under active human stewardship, and the quality of that stewardship is essential to its security. [2] Centralized decision-making saved the day here, and for the most part it’s not in conflict with the decentralized nature of the network itself. The human element becomes crucial when the code fails or needs to adapt over time (e.g., the block size debate). We should accept and embrace the need for a strong leadership and governance structure instead of treating decentralization as a magic bullet.

[1] This gets into a subtle technical point: it’s not obvious how to get a transaction to get into one branch but not the other. By default any transaction that’s broadcast will just get included in both branches, but there are several ways to try to subvert this. But given access to even one transaction that’s been successfully double-spent, an attacker can amplify it to gradually cause an arbitrary amount of divergence between the two branches.

[2] To underscore how far the protocol is from being fixed for all time by a specification, the source code of the reference implementation is the only correct documentation of the protocol. Even creating and maintaining a compatible implementation has proved to be near-infeasible.

Thanks to Andrew Miller for comments on a draft.

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