Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Proofs of Useful Work [pdf]

eprint.iacr.org

Post reply on HN
Print view View original

21–30 of 41 posts

Re: Proofs of Useful Work [pdf]

#21

Post by SilasX »

web007 wrote: post #11
Taek wrote: post #3

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 appl…

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 particula…

Right, I agree that a useful PoW is possible in theory[1], but the requirements imposed (by needing to work as PoW for a blockchain cryptocurrency) are burdensome:

1) The difficulty must be adjustable so that you can make it harder or easier as computational power joins or leaves the network -- so it can't be some generically hard problem with no free parameter that affects the hardness.

2) The difficulty must be precisely predictable, so you know how much to adjust it for 1). That probably rules out NP-complete problems, where it's hard to generate random instances while ensuring you'll get one of the hard ones.

3) The problem must be capable of being arbitrarily generated from a random string, so that your work is associated with a specific ledger update (block), and so the work must have started after that node became aware of the block. This would require you to optimally "compress" the problem space so that a random string decompresses to a valid instance. But if you could compress the problem space that way, it wouldn't be hard!

Partial hash inversion (used in Bitcoin) satisfies those because:

1) You can adjust how many digits of a match are required.

2) There is no shortcut to guessing all the nonces, and each output is effectively a random number with predictable properties.

3) You can require the nonce to be prefixed by the Merkle root of the new block + previous Merkle root.

Edit: Primecoin was a good start, but it quickly exhausted all of the academically useful primes, and is unable to meet 1) while still being useful.

[1] At least, I don't know of a rigorous impossibility proof.

Re: Proofs of Useful Work [pdf]

#22

Post by hinkley »

Taek wrote: post #3

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 appl…

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.

Re: Proofs of Useful Work [pdf]

#23

Post by woah »

eat_veggies wrote: post #12
voidmain wrote: post #4

Earlier quoted context omitted.

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.

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/ [2] https://boinc.berkeley.edu/

This isn’t mining is it?

Re: Proofs of Useful Work [pdf]

#24

Post by homakov »

Taek wrote: post #3

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 appl…

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.

Re: Proofs of Useful Work [pdf]

#25

Post by TeMPOraL »

Taek wrote: post #3

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 appl…

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.

Re: Proofs of Useful Work [pdf]

#26

Post by icebraining »

homakov wrote: post #24
Taek wrote: post #3

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 appl…

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.

Can you elaborate? By whom and when was that proven?

Re: Proofs of Useful Work [pdf]

#27

Post by TeMPOraL »

tlrobinson wrote: post #18
web007 wrote: post #11

Earlier quoted context omitted.

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 particula…

> 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 min…

> Another (very marginally) useful bit of work mining does: converting electricity to heat.

In a stupidly wasteful way, though. Large-scale heat generation with electricity is better done with heat pumps, which have 400-500% efficiency.

Re: Proofs of Useful Work [pdf]

#28

Post by jcoffland »

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.

Re: Proofs of Useful Work [pdf]

#29

Post by Retric »

SilasX wrote: post #21
web007 wrote: post #11

Earlier quoted context omitted.

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 particula…

Right, I agree that a useful PoW is possible in theory[1], but the requirements imposed (by needing to work as PoW for a blockchain cryptocurrency) are burdensome: 1) The difficulty must be adjustable so that you can make it harder or easier as computational power joins or leaves the network -- so it can't be some generically hard problem with no free parameter that affects the hardness. 2) The difficulty must be pre…

Your list is missing verifiable. What makes hashing < vale is useful is you get a high probability that someone handing a solution actually did a lot of work. Someone getting lucky could find a solution within a second using a CPU miner today, they are not going to keep getting lucky for 100 blocks.

Re: Proofs of Useful Work [pdf]

#30

Post by Retric »

nosuchthingtm wrote: post #13
web007 wrote: post #11

Earlier quoted context omitted.

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 particula…

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…

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.

Post reply on HN