Bitcoin has been popping up in conversations lately, mostly in the context of people urging me to invest (real money) in it. But being the sad academic that I am, this mainly makes me wonder if there is some more interesting research to be done on bitcoin. Actually, “bitcoin” almost sounds like something that could have been the name of a blog on computation and economics — so where better to discuss it than right here?
I found out a bit about bitcoin (no pun intended) through a great, detailed blog post by Michael Nielsen. Here are some of the points I found most interesting, very briefly summarized:
- Let’s say that Alice has a bitcoin. One worries that she would try to “double spend” it by giving it to Bob and Charlie. The way bitcoin deals with this is by letting the recipient broadcast the transaction, and getting other users to verify that it is legitimate.
- But now one may worry that Alice could manipulate the authorization process via a sybil attack, i.e., she could create a zillion copies that would certify her fraudulent transactions.
- To prevent sybil attacks, bitcoin uses a proof-of-work system. The idea is that if I want to validate a transaction, I need to solve a computationally hard puzzle — essentially inverting a cryptographic hash function. In more detail, the puzzle is to find a number (called the nonce) such that when the number is appended to the string representation of the transaction, and the resultant string is hashed using a specific hash function (SHA-256), the output is smaller than a given target value. The target value can be adjusted to make the puzzle easier or harder.
- Now that we’re validating transactions by making unrelated users solve useless puzzles, we need to incentivize users to participate. Currently this is done by creating bitcoins out of thin air and using them to reward successful validations. The rate at which new bitcoins are created decreases over time, and at some point users will have to offer a reward for validating their transactions.
Admittedly, I am almost completely ignorant of research papers on bitcoin (especially by the security community). However, I do know of a cool EC’12 paper, “On Bitcoin and Red Balloons”, by Moshe Babaioff, Shahar Dobzinski, Sigal Oren, and Aviv Zohar. In a nutshell, the need to validate transactions is propagated through the bitcoin network, but they argue that nodes have an incentive to keep the knowledge of a transaction to themselves, thereby increasing their own chance of successfully validating the transaction and getting a reward. Babaioff et al’s clever solution is based on the mechanism that helped the MIT team win the DARPA Network Challenge. The idea is to consider the chain of nodes on which the transaction validation request was propagated, and reward each node in the chain; the challenge is to set the rewards in a way that incentivizes propagation and achieves other desirable properties.
The source of the incentive problem is that a node is competing with other nodes to solve a computational puzzle. A node is indeed more likely to be rewarded if there are fewer nodes that know of a transaction. But perhaps it is possible to redesign the computational puzzle to avoid this?
- Question 1: Can the proof-of-work system be redesigned to be “Markovian”, in the (even stronger) sense that your chance of solving the puzzle at time t is independent of t? If so, assuming that (i) a node knows about at least one transaction that needs to be validated at any given time, and (ii) the probability that two nodes simultaneously validate a transaction is negligible, nodes would be indifferent to how many other nodes know about the transaction they are trying to validate.
More importantly, there must be a better way to prevent sybil attacks than turning millions of nodes into the computational equivalents of Sisyphus.
- Question 2: Is it possible to replace the useless work nodes are doing with useful work? This reminds me of the transition from CAPTCHA to reCAPTCHA: Under the former, people were solving useless visual puzzles, whereas reCAPTCHA uses some of this previously wasted brainpower to digitize books. The question is whether something similar can be done for puzzles that are meant to be solved by computers.
- Question 3: Even more ambitiously, can we do away with this whole proof-of-work thing? Or is it possible to prove that, in some sense, it is necessary? An impossiblity result might build on existing impossibilities for sybil-proofness; see, e.g., chapter 27 of the AGT book.
My research for this blog post did not extend to newer cryptocurrencies (such as Peercoin, Namecoin, and Primecoin), and it may well be the case that the preceding questions are already solved or just plain silly. But this space of problems, in my opinion, is quite compelling; it seems to me that the design of electronic cash systems could emerge as a new frontier for algorithmic economics.
Turing's Invisible Hand 