Bitcoin and Theoretical Computer Science (guest post by Eli Ben-Sasson)

[This is a guest post by Eli Ben-Sasson, mentioning only some of the fascinating TCS connections to crypto-currencies. If you’re interested in more then you should check out the TheoryFest talks that Eli mentions. –Boaz]

What is Bitcoin? Why should TCS care?

Eli Ben-Sasson

In Crypto We Trust

You probably heard of Bitcoin, the crypto-currency invented in 2008 by an unidentified person (or persons) under the pseudonym Satoshi Nakamoto. When I started working on this blog post, Bitcoin’s market cap was around 30B USD. Now, a month later, it exceeds 40B USD. Although its long-term price stability is debatable, it has already spawned hundreds of similar crypto-currencies and a flourishing startup econony. It is also the method of payment preferred by certain ransomewares.

I got involved with crypto-currencies when I attended the Bitcoin Conference in San Jose in May 2013, to talk about how implemented cryptographic proof systems, like PCPs and ZK, could benefit Bitcoin. This led to my involvement in Zerocash (academic paper), and ZCash (its implementation as a crypto-currency); but that’s a topic for a different blog post. That conference was, by far, the most electrifying I have ever attended. The atmosphere was manic and there were lines of people waiting to get autographs from Bitcoin core developers (!). The excitement wasn’t just because Bitcoin’s price recently soared (though that certainly helped) but because people sincerely felt that they were “writing History”.

Time will tell if Bitcoin is a disruptive technology or just a modern Tulip Mania. But Bitcoin did already achieve something quite amazing. It showed for the first time (to the best of my knowledge) that cryptographic protocols over a decentralized network can practically replace functions that, so we thought, can only be managed by a Central Trusted Party (CTP). In the case of Bitcoin, this function is Fiat Money (explained below). Bitcoin’s moto, “In Crypto We Trust”, says it all. I admit that this revelation, that Money can be created “out of thin air” in this manner, and that people all over the world will attach economic value to it, has surprised me even more than the success of Wikipedia. Like Wikipedia, I never would have guessed it to be possible.

Fiat Money: Way back, Money was associated with physical resources whose amount is limited by Nature, like seashells or gold. Money still takes this form, of physical limited resources, in closed micro-societies like prisons (cigarettes) and elementary schools (bubble gum wrappers, in mine). Fiat means in Latin “it shall be”; Fiat Money is a resource made limited by decision and, prior to Bitcoin, this decision laid in the hands of CTPs like Central Banks, whose Monetary Policy determines how much money is minted (or removed from circulation) and who gets it.

Bitcoin’s protocol has set in stone an ingeniously simple monetary policy that incentivizes participants to reach consensus regarding Bitcoin’s decentralized payment-ledger, called the blockchain. If you haven’t heard yet about mining and blockchain, you should spend a few minutes and watch one of these excellent introductory videos [1, 2], or read one of these short explanations [1, 2].
My brief redux of it appears at the end of this post.

Bitcoin and theoretical computer science

The connections between Bitcion and TCS and old and strong. Bitcoin’s reliance on moderately hard functions goes back to the fundamental TCS work of Dwork and Naor on combatting spam-mail. The consensus mechanism that Bitcoin uses addresses in a novel way the Byzantine agreement problem, a cornerstone of distributed computation dating back to the 1980 work of Pease, Shostak and Lamport, and understanding the exact nature of this solution is a matter of ongoing research [cf. 1, 2, 3].

As a theoretician who happens to talk to Bitcoin (and other crypto-currency) developers, I am constantly impressed by how deeply they care about our research, and how passionate they are about learning it. This is a gratifying experience that I have not had in prior areas of theory that I have worked in. I believe this feeling is shared by other theoreticians working in this space.

But most importantly for theoreticians, Bitcoin’s core innovation, the creation of economic value from protocols and algorithms, makes you wonder. Human societies have used various ways to reach consensus and govern pooled resources. Fiat Money is just one case, and things like Law, Politics and Government loom behind. Could some other concoction of crypto and economic incentives lead to the practice of new forms of Governance?

You can hear more next week at the Theory Fest in Montreal:
+ Monday, June 19: Aviv Zohar will give a tutorial on Decentralized Cryptocurrencies

• Friday, June 23: a half-day workshop on Probabilistically checkable and interactive proofs (PCP/IP): between theory and practice.

Appendix – Bitcoin’s mining protocol

The ideal functionality that Bitcoin attempts to simulate is that of an append-only ledger, or sequence, of transactions (like “Alice pays Bob 10 coins”) that are individually valid (Alice has 10 coins in her disposal before paying Bob). The real-world model in which Bitcoin tries to simulate this is a decentralized and dynamically evolving network of nodes, or miners; each miner is assumed to be anonymous, rational, and selfish. Bitcoin suggests a simple protocol that ensures that a sufficient majority of honest nodes agrees on a valid prefix of the transaction ledger, and furthermore is incentivized to accept new transactions. Transactions fees suffice to incentivize miners to add new transactions to the ledger. Reaching consensus is the tricky part. Bitcoin’s protocol incentivizes miners to reach consensus by paying a reward of C new coins to the first miner that manages to extend the blockchain by a new valid block. The miner reward is part of that block, and this is how new money is printed. All miners record (their view of) the whole blockchain, and will reject a block if it contains even a single invalid transaction; this incentivizes miners to report only valid blocks (recall the miner’s reward is part of her reported block).

The reward is a hefty sum (at time of writing, more than 35,000$), so miners compete to win it. The winner is the first miner that solves a moderately hard problem (MHP) P(B,b) that is specified by the blockchain state B and the new block b that the miner is attempting to append to B. While the problem is moderately hard to solve, verifying correct solutions for P(B,b) is easy. Satoshi’s protocol says that miners should always attempt to extend the longest valid blockchain. If Alice announces her solution first, most likely (up to network delays) most honest miners will accept the solution, and consequently will try to extend the new, longer, blockchain B’=B||b. As long as a majority of mining computation power is honest, an attacker has low probability of success in rewriting the blockchain history because the “honest history” will grow longer much faster than his “dishonest” version of it. Thus, the much needed stability property is achieved in Bitcoin.