user46: 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?

user7: 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.

user153: 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. 

user15529: 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

user238: "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.

user4125: 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

user13411: 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. 

user50: 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.

user78: 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.

user-1: 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. 

user85: 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:

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.
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.

46: <p>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. </p>

<p>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?</p>
 7: <p>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. </p>

<p>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.</p>
 153: <p>Here's one approach:</p>

<p><a href="http://bitcointalk.org/index.php?topic=108888.0" rel="nofollow">Least action principle as an alternative proof of work system</a></p>

<p><a href="http://www.scipr-lab.org" rel="nofollow">Succinct Computational Integrity and Privacy Research (SCIPR)</a> is possibly another area. </p>
 15529: <p>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.</p>

<p>I recently answered this question on my blog, more details can be found here: <a href="https://blog.sldx.com/is-bitcoins-proof-of-work-useless-work-a411480d3eb3" rel="nofollow noreferrer">https://blog.sldx.com/is-bitcoins-proof-of-work-useless-work-a411480d3eb3</a></p>
 238: <p>"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.</p>
 4125: <p>Some discussions around how to make it more useful</p>

<p><a href="https://en.bitcoin.it/wiki/Intrinsic_worth_brainstorming">https://en.bitcoin.it/wiki/Intrinsic_worth_brainstorming</a></p>

<p><a href="https://bitcointalk.org/index.php?topic=11834.0">https://bitcointalk.org/index.php?topic=11834.0</a></p>
 13411: <p>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.</p>

<p>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:</p>

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

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

<p>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.</p>

<p>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. </p>

<p>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. </p>
 50: <p>The problem is that no one has come up with a proof-of-work system based on useful work that also:</p>

<ul>
<li>Generates easily verifiable solutions</li>
<li>Can have the difficulty of finding a solution adjusted</li>
</ul>

<p>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.</p>
 78: <p><a href="http://www.reddit.com/r/Bitcoin/comments/pve08/btclike_cryptocurrency_with_arbitrary_tradeable/">NooShare</a> is an idea for:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>I don't know if it moved passed the initial design phase, but it's worth a read.</p>
 -1: <p><strong>Primecoin</strong> is the first:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>Check <a href="http://ppcoin.org/primecoin">http://ppcoin.org/primecoin</a></p>

<p>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, <a href="https://www.eff.org/awards/coop">https://www.eff.org/awards/coop</a>)</p>

<p>Here's an in-depth article about this question: <a href="http://arstechnica.com/science/2013/02/ask-ars-why-spend-time-and-money-finding-new-prime-numbers/">Ask Ars: Why spend time and money finding new prime numbers?</a> </p>

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

<p><strong><a href="http://coinwiki.info/en/Curecoin">Curecoin</a></strong> 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. </p>
 85: <p>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.</p>

<p>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:</p>

<ol>
<li>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.</li>
<li>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 <em>on</em> the Bitcoin chain.</li>
</ol>

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