99

One of the arguments made against Bitcoin's design choices is that it wastes resources authenticating transactions. In particular, finding small hashes is completely useless for the world.

Are there approaches (or other crypto-currencies) that use proof-of-work by working on some useful difficult problem? There are plenty of projects like SETI@home or Folding@home that distribute difficult but potentially useful calculations among different users, is there a way to use such useful calculations for building a proof-of-work system in a crypto-currency, or is there a fundamental reason (economic or computational) that a proof-of-work must involve useless work?

|improve this question|||||
  • 2
    This question is invalid; useless is arbitrary. What you are describing as useless is useful. The proof of work system in place allows for even distribution for bitcoins – Buckhead_Comp_Ser_Co Sep 1 '11 at 4:30
  • 15
    @user9704 I set up a clear criteria for what I mean by useful work. I.e. work that provides utility outside of simple authenticating interactions. – Artem Kaznatcheev Sep 1 '11 at 4:32
  • 4
    @Serith I disagree with your change of title to this question. There are a few users who are offended by my use of the word 'useless' but I really use it in the setting of computation that is useless for things except bitcoin. It would be better to edit my question to make this clear instead of making the question itself suggest that the current proof-of-work system is performing a useful computation and not just wasting cycles in order to authenticate. – Artem Kaznatcheev Sep 1 '11 at 14:35
  • 1
    NooShare is such a proposal - reddit.com/r/Bitcoin/comments/pve08/… – ripper234 Feb 25 '12 at 6:06
  • 2
    @ripper234 : Please consider putting this answer as a response, with a bit more detail. This is by far the best response, that answers correctly the question. It's a shame it is hidden in the comments. – Raphael Jolivet Apr 8 '13 at 19:37

12 Answers 12

Active Oldest Votes
36

I think the premise of the question is not correct. The work is not useless, it secures the transactions. The public hash chain ensures that Bitcoins can only be spent once. The mechanism piles computations on top of legitimate transactions so that the recipient knows that an attacker would need at least as much computing ability to "undo" the transaction.

There is currently no known way to make the work more useful. The problem is that the primary purpose of securing transactions imposes a number of requirements on the work done:

  1. The work must be much, much easier to verify than to do. So it pretty much has to consist of searching for something rare, doing billions of searches to test if an input has a particular characteristic. That way the verification simply requires confirming that the input you found has that characteristic.
  2. The work must in fact secure the transactions and not be severable from them. If I see that you sent me 10 Bitcoins and then billions of computations are piled on top of that, it must not be possible to remove that transaction and then pile those same computations on top of a conflicting transaction. So you can't use the result of an arbitrary chunk of work to prove work on the Bitcoin chain.

It's hard to imagine any additional useful work that could be accomplished while still meeting these requirements.

|improve this answer|||||
  • 7
    I think question title is a bit misleading and should be change to "Is there a way to set up proof-of-work systems so it would be even more useful?" – Serith Sep 1 '11 at 8:11
  • 3
    How about finding prime numbers? That should at least fullfil criteria 1. I do not know how useful it is, though. – David Jun 17 '13 at 10:02
  • @David: How is finding prime numbers attached to Bitcoin transactions useful? – David Schwartz Jun 19 '13 at 18:00
  • 6
    Finding prime numbers is the basis behind Primecoin. Finding primes is useful to some extent. – Tim S. May 27 '14 at 16:09
  • 2
    I'm not able to answer because I don't have enough reputation, but there's this paper on the topic: eprint.iacr.org/2017/203.pdf – Autumnsault Dec 14 '17 at 22:13
18

Primecoin is the first:

A new type of proof-of-work based on searching for prime numbers is introduced in peer-to-peer cryptocurrency designs. Three types of prime chains known as Cunningham chain of first kind, Cunningham chain of second kind and bi-twin chain are qualified as proof-of-work. Prime chain is linked to block hash to preserve the security property of Nakamoto’s Bitcoin, while a continuous difficulty evaluation scheme is designed to allow prime chain to act as adjustable-difficulty proof-of-work in a Bitcoin like cryptocurrency.

Check http://ppcoin.org/primecoin

One can question the use of knowing Cunningham chains of primes but it's arguably more useful than finding hashes with sequences of zeroes. And often with math the practical use is only found later. (There's even prize money involved: "$250,000 to the first individual or group who discovers a prime number with at least 1,000,000,000 decimal digits", from the EFF, no less, https://www.eff.org/awards/coop)

Here's an in-depth article about this question: Ask Ars: Why spend time and money finding new prime numbers?

Most of all, now that there's one mathematically useful coin more will probably follow.

Curecoin is another very interesting approach, with merged mining. 45% of new coins for SHA miners, for blockchain security, 45% for protein folding GPU/CPU power. 10% goes to development.

|improve this answer|||||
  • 2
    Why is it useful to know a Cunningham chain? – Nick ODell Jul 23 '13 at 22:54
  • @Nick, I agree with you totally. What's the point? I don't see how Cunningham chains are anymore useful than SHA256 hashes. – jcoffland Dec 17 '13 at 17:25
  • 3
    @NickODell Cunningham chains are now considered useful in cryptographic systems since "they provide two concurrent suitable settings for the ElGamal cryptosystem ... [which] can be implemented in any field where the discrete logarithm problem is difficult." en.wikipedia.org/wiki/Cunningham_chain – Janus Troelsen Feb 8 '14 at 0:40
  • @Janus Troelsen Exactly how many of these would be useful and what for? Would we use them to secure communication? Write interesting papers? I don't see a compelling argument here but I'm willing to listen to one. – jcoffland Mar 3 '14 at 20:26
  • A bit similar to Curecoin, there is also Gridcoin, using what they call "proof of research". In contrast to Curecoin, Gridcoin allows not only work on protein folding but on multiple tasks of the BOINC distributed computation project. – tanius Jul 1 '18 at 8:24
17

NooShare is an idea for:

a decentralised ledger similar to Bitcoin with the novel feature that its proofs of work are iterations of essentially arbitrary Markov-Chain Monte-Carlo (MCMC) chains, the scheduling of which can be purchased using the currency itself. It is a novel economic basis for sharing fallow computational resources.

I don't know if it moved passed the initial design phase, but it's worth a read.

|improve this answer|||||
  • 3
    That does sound interesting, but are MCMC chains useful? – Nick ODell Apr 22 '15 at 8:03
  • 3
    It looks like NooShare is insecure and never took off since I cannot find NooShare being used anywhere. NooShare was just an idea but it does not seem to have worked in practice. – Joseph Van Name May 26 '17 at 20:02
15

The problem is that no one has come up with a proof-of-work system based on useful work that also:

  • Generates easily verifiable solutions
  • Can have the difficulty of finding a solution adjusted

For example, if the system were searching for prime numbers, the solutions would take a long time to verify as being prime. The difficulty of finding the next prime also can't be controlled, it just continues increasing.

|improve this answer|||||
  • 5
    any NP-complete problem, by definition has an easy to verify solution. It is relatively easy to gradually increase the difficulty by increasing the input size. Further, useful NP-hard problem abound in science: say protein-folding, or circuit-layout optimization. – Artem Kaznatcheev Sep 1 '11 at 4:50
  • 13
    The problem with @Artem's suggestion is that you can pre-compute the solutions to a lot of problems. The blockchain makes block N+1 depend on block N, so it's impossible to calculate in advance. – ripper234 Sep 1 '11 at 6:52
  • 5
    @ripper234 my suggestion is definitely wrong, since otherwise it would be in use. However, the point of my comment was as a counterexample to what Chris suggested as an answer. However, people seem to like his answer. It would be nice if he explained how a general NP-hard problem does not qualify, though. As for my comment, it can be made to depend on previous blocks by making the input to the next problem to solve depend on the previous block (say there is a database of hard problem instances to solve, then hash of block N can be used to chose next problem to solve). – Artem Kaznatcheev Sep 1 '11 at 6:58
  • 6
    You would need as many problems as hashes. Otherwise, the proof of work doesn't actually prove work. (Someone can simply choose transactions to get the hash that selects the problem they already solved.) The proof of work must conclusively depend on at least the hash of the previous block and the transactions in it such that the proof of work is provably impractical to attach to any other work. – David Schwartz Sep 1 '11 at 8:18
  • 2
    Primecoin solves the prime number problem with Cunningham chains, where difficulty is controllable. – user5672 Dec 18 '13 at 19:26
9

Assume for a second that we found a proof of work algorithm that had all of the good properties of sha256, but was also useful for SETI and maintaining world peace.

Now suppose a group of miners collectively have more than 51% of the hashing power. In which of the following scenarios are they more likely to collude to double spend via a 51% attack:

A) When the proof of work algorithm is something like sha256 and is only useful for securing the bitcoin network

B) When the proof of work algorithm helps find aliens and maintain world peace in addition to securing the bitcoin network.

In Scenario B, if BTC lost all of its value due to a 51% attack/double spend, miners' hardware would still be valuable because although it couldn't mine bitcoin, it could still find aliens and maintain world peace.

In Scenario A, if BTC were to lose its value, miners' hardware would go down with it, due to said hardware's uselessness for anything other than mining bitcoin.

In short, having a "useless" proof of work algorithm (where "useless" just means being able to secure the bitcoin network and nothing else) is a plus (for the bitcoin network,) because miners will be less tempted to trash bitcoin, knowing that their hardware would be worthless if they were to do so.

|improve this answer|||||
  • 2
    Interesting. I don't think it was part of the original concept. But interesting. – Mayo Mar 16 '15 at 23:22
  • On the other hand, cryptocurrencies themselves will do a better job at maintaining world peace than their useful proof-of-work problems would do. Therefore any peaceloving person who mines BTC to maintain world peace will not want to attack BTC. youtube.com/watch?v=YDk62HApDa8 – Joseph Van Name Jun 27 '17 at 3:24
8

Some discussions around how to make it more useful

https://en.bitcoin.it/wiki/Intrinsic_worth_brainstorming

https://bitcointalk.org/index.php?topic=11834.0

|improve this answer|||||
4

"Merged Mining" (simultaneously mining on multiple block chains with the same amount of work) may not be useful in a "real-world" sense, but at least it also produces Namecoins or Solidcoins or what have you in the process of producing Bitcoins.

|improve this answer|||||
2

No, because there is a significant advantage in requiring that the work be done on the actual transaction record, and not on any arbitrary problem.

By making the problem include the transaction record data, it makes any changes to the transaction history require providing a new solution, and this prevents a party from slowly 'storing' solutions, and releasing them all at once, since there are always new blocks of transactions being added to the block-chain, which means the required solution keeps changing, depending what the last block of transactions is.

|improve this answer|||||
2

Here's one approach:

Least action principle as an alternative proof of work system

Succinct Computational Integrity and Privacy Research (SCIPR) is possibly another area.

|improve this answer|||||
0

I thought I would give the answer I know to this question, and that is an economic one.

One of the reasons for using proof-of-work (apart from the technical usefulness) is as a way to inherently give the currency value. If the currency value is too high, to the point that it costs less to buy the computing power to counterfeit currency than it does to buy the currency directly, then there is an economic incentive to counterfeit and stabilize the price.

If we use a problem that is not useless, then there is a chance that it will be more useful to some that to others. As an example, solving an instance of problem X might generate income of $Y for person N, and no income for person M. (Say we are folding proteins and person N is a pharmaceutics company that can use this to build a new drug, while person M is a random person). Then, if it costs $K to counterfeit the currency by buying computing time, then for person N it would cost $(K - Y) while for person M it would cost $K. This could lead to a destabilization of the value of the currency.

Thus, if there is a useful problem, it must be equally useful to ALL users of the currency.

|improve this answer|||||
  • could someone comment on the downvotes? Is it because of self-answering or did I state something false in my answer? – Artem Kaznatcheev Sep 1 '11 at 6:59
  • 1
    I didn't downvote, but your answer doesn't seem quite right to me. You can't actually counterfeit bitcoins. However, if you control a majority of the network's processing power you can pull off a double-spend attack. I'm not sure how this is connected to the cost of finding solutions though. Do miners who don't have to pay for electricity have more incentive to attack the network than those who do have to pay? – Chris Acheson Sep 1 '11 at 9:00
  • 1
    Miners who don't have to pay for electricity are more likely to continue mining even if it's unprofitable when the cost of electricity is factored in. For this reason, mining is likely to tend to remain slightly unprofitable for all but those who need to convert electricity to heat anyway or have excess electricity they have no way to store. – David Schwartz Sep 1 '11 at 10:24
  • @DavidSchwartz: How can miners don't have to pay for electricity? Are they stealing it? – Hans-Peter Stricker Sep 16 '19 at 11:17
0

Another excellent reason to select an algorithm that is not useful in any other context other than bitcoin alone is so that the infrastructure prepared for the purposes of securing bitcoin alone is only ever incentive-compatible with securing bitcoin.

Consider the recent introduction of numerous altcoins that share the same PoW algorithms, if the work that being done is meaningful in various contexts then miners will not be dedicated to securing bitcoin as there are economic considerations as to what the work should be spent to contribute to. For example, due to Bitcoin Cash and Bitcoin sharing the same SHA256d PoW algorithm, there's been greater volatility in hash-rate in both cryptocurrency which indirectly weakens security as some proportion of work has to be re-directed elsewhere and it also reduces usability experience to due greater variance in block inter-arrival times.

|improve this answer|||||
0

If you made the computation "useful" in some other sense, then in principle you could just sell that "useful" output, and thereby decrease the net economic expenditure securing the blockchain, making it less secured. So bitcoin's "useless" computation is useful, whether or not it has another use.

I recently answered this question on my blog, more details can be found here: https://blog.sldx.com/is-bitcoins-proof-of-work-useless-work-a411480d3eb3

|improve this answer|||||
  • content at the url is no longer available. – renlord Oct 30 '17 at 13:55
  • How do you feel about those who have mined salt, or gold? Salt/gold is useful outside of it being a source of liquidity (for flavoring food and keeping it from rotting, or making pretty things.) But they don't secure a blockchain... – Mark S Dec 14 '17 at 1:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.