6 ms·

Proofs of Useful Work [pdf]

99 points by pmuk 9y ago

thruflo22 9y ago
I love it when a plan comes together. https://news.ycombinator.com/item?id=14949971 https://news.ycombinator.com/item?id=14949971
Taek 9y ago
Useful work is not actually a good foundation for securing a decentralized cryptocurrency. The value of PoW in cryptocurrency is that I know for a fact that you have to burn $X million dollars if you want to double-spend my cryptocurrency. That has to be burned in electricity, and that burn can't be used for anything else. It's expensive for you to attack me. If suddenly we've got useful works, such that you can apply that $X million in electricity to solve problems that are actually not wasteful, and worth perhaps $X million dollars in solutions, then I don't actually have confidence that it costs you money to double-spend my transaction. You might be able to double-spend my transaction as a by-product of computation that you were going to do already. Further, useful PoW is a centralizing pressure, because not everyone is going to have equal access to people who are willing to pay for solutions of useful work. This unequal access to revenue means unequal ability to compete, favoring people who are able to sell solutions more effectively. For cryptocurrency, we like to remove these advantages as much as possible (granted, the existing system has a lot of room for improvement, but useful work moves things in the wrong direction).
- voidmain 9y ago
  The ideal would be useful work that is a public good - no one can profit from it individually (other than by using it as a PoW), but the world benefits from it in some way.
  - bsbechtel 9y ago
    Like carbon sequestration?
    - richdougherty 9y ago
      That's an interesting idea, but is there a way to prove carbon sequestration, except by providing me with some physical carbon?
      - bsbechtel 9y ago
        It was more of an off-handed comment, but I suppose you could rig some sort of carbon sensor that measures X amount of carbon pulled from the atmosphere. Of course any sort of sensor to the physical world can be rigged to produce a false signal.
  - richdougherty 9y ago
    That's a really interesting thought. Would you consider public information (e.g. the result of a mining computation) to already be a public good? E.g. see discussion of information goods here https://en.wikipedia.org/wiki/Public_good#Challenges_in_identifying_public_goods https://en.wikipedia.org/wiki/Public_good#Challenges_in_iden...
    - acheron9383 9y ago
      I wonder about some tasks that people already do for charity with their computers...like protein folding, finding super huge prime numbers. I don't know enough about the algorithms involved though to assert they satisfy the POW requirements. But some infrastructure already exists to distribute these problems.
    - 0wing 9y ago
      Satoshi style PoW algorithms are intended to waste as much energy as possible. PoW mining just raises the capital cost to control the network without ever improving the speed or functionality. It's a system that increases the waste as time progresses.
  - VMG 9y ago
    There is a market for public good: charities
    - nickpsecurity 9y ago
      You and I were thinking on similar lines. Since it's tech, my idea was the money went to FOSS nonprofits that focus on infrastructure like OS's, servers, crypto libraries, and so on. Even the GetRichCoin types building on that kind of foundation might do some incidental good for tech scene even if their plans don't work out.
  - kurthr 9y ago
    Like Protein folding, Search for ExtraTerestrials, Asteroids, etc... there are a lot of them, some of which structured properly could provide public benefit. https://en.wikipedia.org/wiki/List_of_distributed_computing_projects https://en.wikipedia.org/wiki/List_of_distributed_computing_...
    - microtherion 9y ago
      I'd like to suggest "AlienCoin": Proof of work consists of processing SETI@Home blocks, and mining rewards are paid out to whoever finds an alien civilization.
  - eat_veggies 9y ago
    Gridcoin [1] has been a thing for a while and you mine coins by participating in BOINC [2] projects like SETI@home. [1] http://www.gridcoin.us/ http://www.gridcoin.us/ [2] https://boinc.berkeley.edu/ https://boinc.berkeley.edu/
    - woah 9y ago
      This isn’t mining is it?
- web007 9y ago
  I think you're arguing the wrong way around. Useful PoW is totally fine for a cryptocurrency the same way useless PoW is - you have to solve a particular instance of some kind of problem, not just "computation that you were going to do already". I think Primecoin is a good example: the general problem that's being solved for mining happens to have a useful byproduct, but you still have to provide PoW on the particular instance that is on the chain. Even Bitcoin has provided useful work for a very weak definition: it has created incentives for MASSIVE research and development in cracking or otherwise breaking SHA-256. I don't know where I could find data, but I would bet that there's an inflection point in "crack speed" around 2009, and that further progress probably correlates pretty well with the USD-BTC exchange rate.
  - nosuchthingtm 9y ago
    Consider a situation in which the US government realises that primecoin's output is crucial to further quantum computer research. They pump 100s of billions into mining primecoin. Now, 99.9999% of hashpower and full nodes belong to the US government - an entity whose only interest in primecoin is as a minor return on some work to reduce costs. In this case, every assumption of trustlessness and censorship resistance has gone out the window. A consensus algorithm using proof of useful work will become a market of miners for whom the mining rewards and thus the integrity of the network are merely a secondary concern.
    - Retric 9y ago
      Mining inherently means whoever is most efficient ends up with 51% of the market. If companies X spends less than anyone else per hash they will end up at 51% unless they intentionally hold back. However, proof of useful work could be a public good. Though that makes coming up with an algorithm much harder.
  - tlrobinson 9y ago
    > Even Bitcoin has provided useful work for a very weak definition: it has created incentives for MASSIVE research and development in cracking or otherwise breaking SHA-256 And chip performance in general. It wouldn't surprise me if Bitcoin ASICs nudge the state of the art in chip design and fabrication forward. Another (very marginally) useful bit of work mining does: converting electricity to heat. I doubt many miners are currently using the heat, but it seems inevitable that eventually most miners would be located in areas where 1) electricity is very cheap, and 2) the heat produced by mining can be used productively
- hinkley 9y ago
  They could still be used for quid pro quo and rate limiting situations. I feed you a problem that is useful to my company and I provide you a free service in return. Because you have to have a PoW it’s more difficult for you to spam my service (you have to break other laws to do so), and even if you do I get reimbursed after a fashion anyway.
- homakov 9y ago
  On a side note: it's proven PoW is centralized and does not in fact secure the coin. Only guarantees work, not security. Just not being used to double spend yet.
  - icebraining 9y ago
    Can you elaborate? By whom and when was that proven?
    - homakov 9y ago
      Like every hashrate chart? https://medium.com/@homakov/stop-calling-bitcoin-decentralized-cb703d69dc27 https://medium.com/@homakov/stop-calling-bitcoin-decentraliz...
  - deleted 9y ago
    [deleted]
- TeMPOraL 9y ago
  If true (and I fear they are), then your arguments form a good reason to oppose cryptocurrencies as they exist today. They're wasting huge amounts of energy (and at this point significantly contributing to our energy and climate problems) for arguably little benefit coming from (IMO misguided) attempt at building a trustless system. Also, most participants seem to really be interested in them as get-rich-quick, fuck-authorities scheme, which makes cryptocurrencies an epitome of the concept of externality.
- bluesign 9y ago
  "if suddenly we've got useful works, such that you can apply that $X million in electricity to solve problems that are actually not wasteful, and worth perhaps $X million dollars in solutions" first if we ignore the part "not everyone is going to have equal access to people who are willing to pay for solutions of useful work" I think this can never happen. ---- People should think PoW as lottery. Every X minutes there is a prize draw giving you Y coins. But ticket price converges to market value of: ticket price = (Y coins)/(total tickets sold) So if you add a value to 'not winning ticket' by introducing 'useful work', you are changing ticket price to: ticket price = (Y coins)/(total tickets sold)-'work value' so you are just giving coins more value, means making 'new ticket' more expensive. new ticket = old ticket + work value In the end you will still 'waste' the same amount at equilibrium.
- wybiral 9y ago
  The thing being "spent" is no longer electricity but rather is the value of the work being completed. That means the value would change if new ways to solve the problems arise. But currently the value changes based on your electricity bill (new tech could disrupt that too).
- Boussac 9y ago
  Excellent reminder of why 'useful PoW' is a very bad idea. Furthermore, the value of 'useful' may vary over time to the point where it exceeds the value of mining. That is when a 'useful' corporation takes over mining and decides to kill the chain because 'useful inc.' is promoting its own corporate token (another bad idea: bad ideas generally lead to other bad ideas).
kruhft 9y ago
There's a better way using an obscure Coin algorithm.
deleted 9y ago
[deleted]
etaioinshrdlu 9y ago
Here's a little writeup of how I could imagine mathematical proofs as a useful proof-of-work: https://pastebin.com/raw/ZAys0mYp https://pastebin.com/raw/ZAys0mYp Note that it's more of a market for mathematical proofs, not a replacement for proof of work in a currency that needs a new block every 10 minutes. Still, "miners" (theorem provers) get rewarded for their efforts with tokens. My mathematician friends say such a genericized proof market should be possible using Model Theory.
jcoffland 9y ago
An important consideration that is missing in section 7 A Blockchain Scheme is that the PoW must also be tied to the miner's receive address otherwise anyone could claim the reward as soon as the PoW was broadcast onto the network. A simple solution is to also hash the miner's receive address along with the previous block and transaction hash. This seems like a pretty major omission on the part of the authors and cast some doubt on the rest of the paper.
- tromp 9y ago
  It's not so much missing, as it is implicit in the H(current block), since current block includes all transactions, includes the coinbase for the miner. (In reality, only the merkle root of the transaction tree is hashed, with similar effect).
  - jcoffland 9y ago
    Right, my mistake.
tromp 9y ago
This work is theoretically very interesting, but nowhere does the paper explore what parameter choices would make its use in e.g. bitcoin practical. In particular, would n be close to a million? How large would the problems (f,x) be? How large are the solutions? Both of these would need to be included in the block header which is currently only 80 bytes long. Any sizes substantially larger than a few KB would make this rather impractical. What are the best known implementations for these sizes? How many seconds does it take to solve and how many to verify a solution?

99 points by pmuk 9y ago

I love it when a plan comes together. https://news.ycombinator.com/item?id=14949971 https://news.ycombinator.com/item?id=14949971

Taek 9y ago

Useful work is not actually a good foundation for securing a decentralized cryptocurrency. The value of PoW in cryptocurrency is that I know for a fact that you have to burn $X million dollars if you want to double-spend my cryptocurrency. That has to be burned in electricity, and that burn can't be used for anything else. It's expensive for you to attack me. If suddenly we've got useful works, such that you can apply that $X million in electricity to solve problems that are actually not wasteful, and worth perhaps $X million dollars in solutions, then I don't actually have confidence that it costs you money to double-spend my transaction. You might be able to double-spend my transaction as a by-product of computation that you were going to do already. Further, useful PoW is a centralizing pressure, because not everyone is going to have equal access to people who are willing to pay for solutions of useful work. This unequal access to revenue means unequal ability to compete, favoring people who are able to sell solutions more effectively. For cryptocurrency, we like to remove these advantages as much as possible (granted, the existing system has a lot of room for improvement, but useful work moves things in the wrong direction).

voidmain 9y ago
The ideal would be useful work that is a public good - no one can profit from it individually (other than by using it as a PoW), but the world benefits from it in some way.
- bsbechtel 9y ago
  Like carbon sequestration?
  - richdougherty 9y ago
    That's an interesting idea, but is there a way to prove carbon sequestration, except by providing me with some physical carbon?
    - bsbechtel 9y ago
      It was more of an off-handed comment, but I suppose you could rig some sort of carbon sensor that measures X amount of carbon pulled from the atmosphere. Of course any sort of sensor to the physical world can be rigged to produce a false signal.
- richdougherty 9y ago
  That's a really interesting thought. Would you consider public information (e.g. the result of a mining computation) to already be a public good? E.g. see discussion of information goods here https://en.wikipedia.org/wiki/Public_good#Challenges_in_identifying_public_goods https://en.wikipedia.org/wiki/Public_good#Challenges_in_iden...
  - acheron9383 9y ago
    I wonder about some tasks that people already do for charity with their computers...like protein folding, finding super huge prime numbers. I don't know enough about the algorithms involved though to assert they satisfy the POW requirements. But some infrastructure already exists to distribute these problems.
  - 0wing 9y ago
    Satoshi style PoW algorithms are intended to waste as much energy as possible. PoW mining just raises the capital cost to control the network without ever improving the speed or functionality. It's a system that increases the waste as time progresses.
- VMG 9y ago
  There is a market for public good: charities
  - nickpsecurity 9y ago
    You and I were thinking on similar lines. Since it's tech, my idea was the money went to FOSS nonprofits that focus on infrastructure like OS's, servers, crypto libraries, and so on. Even the GetRichCoin types building on that kind of foundation might do some incidental good for tech scene even if their plans don't work out.
- kurthr 9y ago
  Like Protein folding, Search for ExtraTerestrials, Asteroids, etc... there are a lot of them, some of which structured properly could provide public benefit. https://en.wikipedia.org/wiki/List_of_distributed_computing_projects https://en.wikipedia.org/wiki/List_of_distributed_computing_...
  - microtherion 9y ago
    I'd like to suggest "AlienCoin": Proof of work consists of processing SETI@Home blocks, and mining rewards are paid out to whoever finds an alien civilization.
- eat_veggies 9y ago
  Gridcoin [1] has been a thing for a while and you mine coins by participating in BOINC [2] projects like SETI@home. [1] http://www.gridcoin.us/ http://www.gridcoin.us/ [2] https://boinc.berkeley.edu/ https://boinc.berkeley.edu/
  - woah 9y ago
    This isn’t mining is it?
web007 9y ago
I think you're arguing the wrong way around. Useful PoW is totally fine for a cryptocurrency the same way useless PoW is - you have to solve a particular instance of some kind of problem, not just "computation that you were going to do already". I think Primecoin is a good example: the general problem that's being solved for mining happens to have a useful byproduct, but you still have to provide PoW on the particular instance that is on the chain. Even Bitcoin has provided useful work for a very weak definition: it has created incentives for MASSIVE research and development in cracking or otherwise breaking SHA-256. I don't know where I could find data, but I would bet that there's an inflection point in "crack speed" around 2009, and that further progress probably correlates pretty well with the USD-BTC exchange rate.
- nosuchthingtm 9y ago
  Consider a situation in which the US government realises that primecoin's output is crucial to further quantum computer research. They pump 100s of billions into mining primecoin. Now, 99.9999% of hashpower and full nodes belong to the US government - an entity whose only interest in primecoin is as a minor return on some work to reduce costs. In this case, every assumption of trustlessness and censorship resistance has gone out the window. A consensus algorithm using proof of useful work will become a market of miners for whom the mining rewards and thus the integrity of the network are merely a secondary concern.
  - Retric 9y ago
    Mining inherently means whoever is most efficient ends up with 51% of the market. If companies X spends less than anyone else per hash they will end up at 51% unless they intentionally hold back. However, proof of useful work could be a public good. Though that makes coming up with an algorithm much harder.
- tlrobinson 9y ago
  > Even Bitcoin has provided useful work for a very weak definition: it has created incentives for MASSIVE research and development in cracking or otherwise breaking SHA-256 And chip performance in general. It wouldn't surprise me if Bitcoin ASICs nudge the state of the art in chip design and fabrication forward. Another (very marginally) useful bit of work mining does: converting electricity to heat. I doubt many miners are currently using the heat, but it seems inevitable that eventually most miners would be located in areas where 1) electricity is very cheap, and 2) the heat produced by mining can be used productively
hinkley 9y ago
They could still be used for quid pro quo and rate limiting situations. I feed you a problem that is useful to my company and I provide you a free service in return. Because you have to have a PoW it’s more difficult for you to spam my service (you have to break other laws to do so), and even if you do I get reimbursed after a fashion anyway.
homakov 9y ago
On a side note: it's proven PoW is centralized and does not in fact secure the coin. Only guarantees work, not security. Just not being used to double spend yet.
- icebraining 9y ago
  Can you elaborate? By whom and when was that proven?
  - homakov 9y ago
    Like every hashrate chart? https://medium.com/@homakov/stop-calling-bitcoin-decentralized-cb703d69dc27 https://medium.com/@homakov/stop-calling-bitcoin-decentraliz...
- deleted 9y ago
  [deleted]
TeMPOraL 9y ago
If true (and I fear they are), then your arguments form a good reason to oppose cryptocurrencies as they exist today. They're wasting huge amounts of energy (and at this point significantly contributing to our energy and climate problems) for arguably little benefit coming from (IMO misguided) attempt at building a trustless system. Also, most participants seem to really be interested in them as get-rich-quick, fuck-authorities scheme, which makes cryptocurrencies an epitome of the concept of externality.
bluesign 9y ago
"if suddenly we've got useful works, such that you can apply that $X million in electricity to solve problems that are actually not wasteful, and worth perhaps $X million dollars in solutions" first if we ignore the part "not everyone is going to have equal access to people who are willing to pay for solutions of useful work" I think this can never happen. ---- People should think PoW as lottery. Every X minutes there is a prize draw giving you Y coins. But ticket price converges to market value of: ticket price = (Y coins)/(total tickets sold) So if you add a value to 'not winning ticket' by introducing 'useful work', you are changing ticket price to: ticket price = (Y coins)/(total tickets sold)-'work value' so you are just giving coins more value, means making 'new ticket' more expensive. new ticket = old ticket + work value In the end you will still 'waste' the same amount at equilibrium.
wybiral 9y ago
The thing being "spent" is no longer electricity but rather is the value of the work being completed. That means the value would change if new ways to solve the problems arise. But currently the value changes based on your electricity bill (new tech could disrupt that too).
Boussac 9y ago
Excellent reminder of why 'useful PoW' is a very bad idea. Furthermore, the value of 'useful' may vary over time to the point where it exceeds the value of mining. That is when a 'useful' corporation takes over mining and decides to kill the chain because 'useful inc.' is promoting its own corporate token (another bad idea: bad ideas generally lead to other bad ideas).

kruhft 9y ago

There's a better way using an obscure Coin algorithm.

deleted 9y ago

[deleted]

etaioinshrdlu 9y ago

Here's a little writeup of how I could imagine mathematical proofs as a useful proof-of-work: https://pastebin.com/raw/ZAys0mYp https://pastebin.com/raw/ZAys0mYp Note that it's more of a market for mathematical proofs, not a replacement for proof of work in a currency that needs a new block every 10 minutes. Still, "miners" (theorem provers) get rewarded for their efforts with tokens. My mathematician friends say such a genericized proof market should be possible using Model Theory.

jcoffland 9y ago

An important consideration that is missing in section 7 A Blockchain Scheme is that the PoW must also be tied to the miner's receive address otherwise anyone could claim the reward as soon as the PoW was broadcast onto the network. A simple solution is to also hash the miner's receive address along with the previous block and transaction hash. This seems like a pretty major omission on the part of the authors and cast some doubt on the rest of the paper.

tromp 9y ago
It's not so much missing, as it is implicit in the H(current block), since current block includes all transactions, includes the coinbase for the miner. (In reality, only the merkle root of the transaction tree is hashed, with similar effect).
- jcoffland 9y ago
  Right, my mistake.

tromp 9y ago

This work is theoretically very interesting, but nowhere does the paper explore what parameter choices would make its use in e.g. bitcoin practical. In particular, would n be close to a million? How large would the problems (f,x) be? How large are the solutions? Both of these would need to be included in the block header which is currently only 80 bytes long. Any sizes substantially larger than a few KB would make this rather impractical. What are the best known implementations for these sizes? How many seconds does it take to solve and how many to verify a solution?