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.
I tried asking your second question on the bitcoin stackexchange a while back, but that community is not very academic and more of a FAQ/advertisement for bitcoin (for example, the question title doesn’t reflect my original title at all, and was edited by the community because my title was not pro-bitcoin enough), so I didn’t really get any insightful responses. However, I haven’t checked in with that stackexchange in a long time, so I don’t know how the community is now. It might be worthwhile to ask some of your questions there.
The first questions that came to my mind when I heard about bitcoin was if the transactions could be made non-public but still kept decentralized, and I got an interesting answer on the crypto stackexchange. In hindsight, though, I wish I had bought some bitcoins instead of just thinking about them.
Huh, some of the answers to your version of Q2 are actually quite interesting. It seems that people have been thinking about it, but, as one person points out, there are two criteria that need to be satisfied: (i) solutions should be easy to verify, and (ii) the difficulty level should be easy to adjust. One vague approach I had in mind satisfies (i) but not (ii).
> Is it possible to replace the useless work nodes are doing with useful work?
My understanding is that work is “useless” by design. To perform fraud like double-spending you need to amass huge computational power(close to 50% of all network power, even with 20-30% your chances are still tiny). This makes attack very costly. Any extra value would lower the cost of computations, thus creating extra incentive for an attacker.
Also, Wei Dai in his bmoney proposal( http://www.weidai.com/bmoney.txt ) specifically states that “… the solution must otherwise have no
value, either practical or intellectual”. Maybe there is deeper reason of “useless” computations? Though probably not: bmoney is quite different from bitcoin in the aspect of money creation, and computations seem to have different purposes. Anyhow, I just wanted to share this link with you, it is good food for thought.
If the work has value to society, it doesn’t necessarily lower the cost of the attacker. For example, reCAPTCHA digitizes books, but that doesn’t make it easier for potential attackers to break CAPTCHAs.
Attacker could advertise this work as valuable to a lot of people, who are willing to spend their computational power on it, but don’t know about / don’t like bitcoin. This would increase attacker computational speed, bringing him close to 50% goal.
I would say that reCAPTCHA is still 99% useless work: not enough people care about small percentage of incorrectly recognized characters in obscure books. I can’t find any info on how recognized captchas are actually used. Does even google use them for its full-text search?
Concerning Q1, the proof of work is already Markovian in the sense that previous tries by either you or another miner do not influence your probability of successfully mining a block. I also believe that assumption (ii) does not consider the possibility that a miner might want to withhold publicizing a transaction in hopes of being the one to confirm it (and receive the transaction fees) at a later block. Or have I misunderstood your question?
Concerning Q2, Alex Coventry proposed nooshare (mit.edu/alex_c/www/nooshare.pdf) to make POWs useful, although from what I recall it did not address some of the concerns you voiced in your reply above.
Concerning Q3, the POW and thus the blockchain acts as a decentralized authenticated bulletin board. If one were able to recreate such a functionality in either a centralized or decentralized way, the POW might not be necessary, although some measures would have to be taken to limit spam. I was interested in exploring the proof-of-connectedness to the network concept but never got to it.
Thanks for these interesting points.
Q1 — As far as I understand, if I already unsuccessfully tried many nonces (is that the plural of nonce?), I am more likely to find a nonce that works. What I had in mind is a puzzle that “restarts” after every attempt. I don’t think assumption (ii) is susceptible to miners withholding transactions, perhaps you mean assumption (i)? If so, I agree, but I think it is reasonable to assume that assumption (i) would hold in equilibrium, when everyone is propagating transactions.
Q2 — This is a fascinating pointer. Gotta make time to read it…
My understanding of https://en.bitcoin.it/wiki/Transactions#Generation is that the number of possibilities for the effective nonce, that is comprised of nonce+extraNonce, is so large that with overwhelmingly large probability there is more than one solution within these possibilities. Whenever you try a nonce and fail, you are removing a point from that search space, but it does not influence the probability that your next nonce will succeed. This might be compared to trying to find a four-leaf clover within a large clover field, as picking up one clover and realizing it does not fit your criteria does not influence the likelihood that the next one will.
Very interesting! So bitcoin itself satisfies the assumptions in Q1. Then why is there an incentive problem? I asked the authors of the EC paper over email, and they explained that they are thinking of a future world where new bitcoins are no longer generated (this is part of the protocol); in that world the reward a node gets for validating a transaction is a fraction of the transaction, so larger transactions give a larger reward. In particular, a node can benefit by withholding information about large transactions.
As other commenters mentioned, the work performed as part of the POW should be “useless” to the one performing it. Benefitting everyone is a different story. The most recent attempt for creating a cryptocurrency with POW that benefits society is Primecoin (as you linked in the post) which uses the finding of long Cunningham chains for POW.
Reblogged this on Chestii RANDOM.
In some FB group, people said they use mining machines to heat up their apartments on cold days (unfortunately, also on hot days 🙂
Hurrah, that’s what I was exploring for, what a data! present here at this website, thanks admin of this web page.
The current financial system is one sick puppy everywhere you look.
The fundamentals are starting to show through all the smokescreens put up by the various central banks. The central banks are losing control and country after country is entering the ‘currency wars’ by devaluing their currencies in order to try and remain competitive and to stimulate growth in their economies.
We are already seeing the first wheels coming off the present system. Sure there will be some ‘rescue plans’ in the months to come but that is just patching over holes and or kicking the can down the road. The big reset is coming and I personally believe it will start to gather momentum during the first half of 2016.
If this is the case I think we will see many moving into bitcoin so yes, 2016 could well be the year for bitcoin.
La cotización del bitcoin es algo que está en constante auge, solo hay que ver que su mercado se trabaja cada segundo del día. Por esta característica, hay muchísima comunidad detrás.
How would you scale Bitcoin? Currently Bitcoin is very slow. And solutions built to scale Bitcoin has flaws. e.g. Lightning Network requires all parties to be online always.