I really wonder if the authors of this paper actually understand how Proof of Work works. The game theory behind PoW requires it to be wasteful in order to create strong incentives for constructing valid blocks. If the work is useful, then there is no incentive as there is no potential loss for attacking the network. The security of the network comes intrinsically from the waste.
I would argue that only some fraction x of the work should be wasteful. If the work would cost c on the market, it cost (1 + x)c on the network. Then if 51% attack total cost = (1 + x)c then only (x c) is wasted while c is recovered from the market. But just having (x c) is not enough to attack since you have to gain access to (loan) c which is an additional entry barrier.
I also think "wastefull" is the wrong word. It simply has to not benefit the miner MORE than everyone else.
For example, if there was a pure public good project that could provide random input / output, then it would still work.
Primecoin is an example of that. While finding those specific primes is of extremely minimal value, it would still work even if solving those primes had considerable value - because it would be equally valuable to all.
Primecoin in particular turns out not to be a proof-of-useful-work system because the creators manually reward people for their work (the work isn't directly a form of mining on the chain).
And keep in mind, even for bitcoin, some of the work is useful, since the computer chips it uses will heat up, and that has value for HVAC. It’s certainly not as cheap per unit of heating as you can get with equipment built for that purpose, but there is still a positive value c there.
This is equivalent to burning the cost of interest for that loan as wasted PoW. Any sophisticated attacker will have effectively unlimited capital at prevailing interest rates.
That would be the whole gain: set of attackers would be filtered down to sophisticated ones. That would be advantageous for the network since the more centralized potential attackers are, the easier it is to deal with them.
> the more centralized potential attackers are, the easier it is to deal with them.
The opposite of this is true, as you are talking about "centralised" in the context of "a smaller group of people" and not "a smaller cluster of attacking machines". The most sophisticated adversaries are the hardest to deal with.
I would argue against the PoW having to be wasteful. It has to be difficult (in terms of compute power and time) but not wasteful. I'm not affiliated in any way with this, but there is one project that uses PoW to search for large primes.
Which only works because there those primes have no economic value.
The issue is economic, not technical. If I can sell the “useful” side effect of mining, then I can subsidize any attack I perform. The actual security of the network is only the work that has non-reimburseable costs.
It doesnt matter. As long as the value is Equal for everyone, it doesn't benefit that specific miner more than everyone else who didnt mine, then it still works because everyone has the same incentive and same immediate benefit.
Finding primes aren't a great example. ... but unfortunately, they are the best example we have so far.
Agreed, the issue is economic. That's one of the things that I find fascinating about Byzantine Fault Tolerant state machine replication. You can view cryptocurrencies as a method of payment for the economic incentive of playing fair. I think the big story here is that we can have a BFT distributed consensus!
a) it is economically rational to mine on the correct chain
b) there are substantial economic net costs to mining on a wrong fork of the chain (and these are high enough that it is prohibitively expensive to mount an attack which would fool people as to what chain is correct)
It actually has to be costly, not difficult. And not wasteful.
To see this, note that all POW and POS chains have "difficulty" functions that are actually just cost functions in external markets (hashpower or capital). What secures the difficulty of the attack in all casds is the supply curve of some block production factor in an external market.
But that is the conundrum. If the "work" is not really worth anything to other people, then the work isn't useful. If it is useful, it makes attacking the blockchain free. The security is because the work can't be used for anything except securing the network.
As long as the work is as useful to everyone equally (regardless of who mines), then it still works.
For example, if it were solving an incredibly complex mathematical or scientific problem that benefits all of mankind - then the incentive is equal for everyone.
If the useful product is intellectual, and proving work involves publishing the product freely, how do you monetize it? Selling support contracts a la FLOSS?
It also happens that both these conditions (intellectual product + must be published freely) are the typical approach of PoW blockchains.
It strikes me that is can still be useful, it just has to produce a good whose value cannot be internalized. It would need to be a perfect public good. Can’t think of any examples though.
Just as a heads up, Saito has a quantifiable cost of attack (for attackers) while still paying for a form of useful work (tx routing / fee collection) so waste and security are not intrinsically related.
The approach works exactly because money is guaranteed to be pulled away from the block producer. Given that it always costs more money to produce blocks than attackers can earn from them, only honest nodes (who spend other people's money) have am incentive to do so. Cost of attack is the money attackers cannot get back if they spend their own money to censor the network. Check it out!
It doesn't have to be wasteful but the computation must be asymmetric. That is it must be much more difficult to compute than to verify. The SHA-256 nonce discovery computation used by Bitcoin has this property, but is not really useful.
Others have given the example of PrimeCoin which is asymmetric, but somewhat useful as it discovers prime numbers.
A great metaphor for this is a Sudoku puzzle. It is much harder to solve than it is to check the solution.
Somebody comes up with a "useful proof of work" a few times a year, and so far there has always been a reason why the proposed mechanism is infeasible. In this example, the reasons are (1) the ML tasks require large amounts of data, which makes them infeasible for a blockchain POW algo and (2) in their proposed scheme, there is no way for a regular node to validate the blockchain, because it has to trust a separate node they call a "verifier".
(but I only glanced at the paper quickly, if someone has the time to do a thorough analysis, please feel free to explain why I'm wrong)
I'd like to add to this list: The related work section closes with "Our PoUW facilitates better AI through decentralisation, enhanced security and the right incentives.".
Decentralisation: Their own paper states in 7.2 that "distributed solution will never be as efficient as running the whole training on a local machine". What incentive for buying into this would I have here then? I occasionally use cloud training if what I'm doing exceeds the capability I have locally. As a client I don't particularly care about the internal infrastructure of whoever I pay to do that (with small exceptions like the next point).
Enhanced security: Security that's only required because of me using a blockchain solution? 7.3 starts out with "We assume that the majority of participants is honest.". That's an assumption I can make today with the cloud providers I pay for my training time, without any blockchain overhead. Nothing in that section seems to be related to real world security concerns, e.g. trusting random mining worker nodes with my - potentially proprietary - training data and intermittent results. 3.4, the outline of a task definition, also specifies that I basically provide the full model and really convenient formats to steal all of that away from me. I think the major risk factor of using the idea outlined in the paper doesn't have anything to do with a revolution of cryptocurrencies, but one of the corporate espionage in the ML world it would enable.
Right incentives: For me, as a client, a theoretical 30% savings doesn't outweigh the above (and all the ancillary considerations like infrastructure, ...). If any of their economical analysis is off, they just generate more people going back to bitcoin mining on the other side of the equation. Not sure what the right incentive is supposed to be here. This might be a good system to proove useful work but somehow I don't see the text convincing the reader that the system itself is useful, maybe I missed it.
assuming the participants are honest is useful because someone else can prove how to participate in a trust-less fashion, e.g. via homomorphic encryption
That kind of sounds too "move fast and break things" for something that's essentially a systems description with an actual implementation they likely want to sell. At any rate, it might be useful for the Blockchain part of the system I don't care too much about. My comment was meant to address the actual work part of the system. It relies on client trust w.r.t. not only the network but also the models and data they put in, which I don't even see mentioned in the document. I don't see how the architecture described in there would be able to even attempt to break down training processes enough to prevent a malicious actor from extracting substantial parts of the system without crippling performance.
Being cheap to verify is one of the defining characteristics of a good PoW. Only PoW verification allows you to identify the chain with the most work. Which is needed to identify how much money the verifiers have at stake. So trusting verifiers to help you identify the most worked chain has no solid footing.
Any "search"-like problem can become cheap to verify simply by augmenting the solution with a verification certificate. It's quite likely that many ML training tasks are "search"-like in this sense, hence cheap to verify as well.
(1) Not all ML needs massive amounts of data. For instance Leela Zero and LCZero want a bunch of horsepower instead. So a task that features a simple set of rules but tries to find the best way to do it should work just fine here.
(2) Having a 'verifier' is how mining pools work already, so it's not adding complexity or anything else.
That said, I didn't read the paper either, but I would say thinking about how to harness the massive resources being used to mine crypto these days is nowhere near a wasted effort. At some point, someone is going to look at all the things that have been proposed and the way some network is set up and it will click.
> Ten verifiers are automatically selected based on the mined block hash (as a random seed).
Congrats you've reinvented proof-of-work in an obfuscated form.
This paper repeats the errors of all previous proof of "useful work" papers from the past. I'd recommend that people actually take a look at discussions on bitcointalk, IRC channels like #bitcoin-wizards, and Bitcoin mailing lists to learn about what has already been figured out for all these things.
For people submitting tasks, it seems like this would be hard to make cheaper than, say, spinning up an AWS instance or similar. Is that assessment correct? If so, would there still be an incentive to use this setup?
Edit: I see they address this, claiming 30% cheaper than cloud services and better ROI for miners than Bitcoin. That said, wouldn't it still be more efficient to skip the blockchain stuff and just have a marketplace where people with tasks can rent time from participating devices and pay with whatever currency?
Wouldn't it waste even less energy to not use a PoW scheme at all though? Just set up a webpage that connects people with tasks to people with hardware.
On another note, digging in closer, the proposed training scheme (Section 4.3) sounds like it would be incredibly inefficient for any large neural models - you're computing your own updates via gradient descent, but also getting compressed updates from peers on the network, and then broadcasting your own updates out. For reference, at work I might be training a model with, say, 30M parameters, and I get about 4.5 training iterations per second on a GTX 1080. What would that drop to with peer broadcasting added in?
They mention only sending weight updates that under/over-flow a certain value, is that enough to avoid, e.g., a 5x drop in training speed? Given that training time is already a big bottleneck for ML work, this seems critical. Section 7.2 seems to address this, referencing Supplementary Materials (Appendix F). The numbers there don't look great - with the optimizations they mention, for GPU timing in Figure F.3 it looks like local training ops account for about 21ms, and the protocol overhead is something like 100ms. I also don't see an apples-to-apples comparison of "here's how long this example takes to train locally vs. with this protocol", which isn't a good sign.
Webpage is also centralized. The whole point in creating PoW is to create a task that would be more expensive on the network than on the market. ie some of it would be "wasteful" - used only to secure decentralized network (see my other post)
Right, I understand that. I'm saying from the point of view of the task submitters, the PoW approach is unnecessary and adds time and cost overhead to what is ostensibly the main goal of their participation: getting an ML model trained.
Yes, then the overhead(+ incentive) should be subsidized by Peers - normal users that just use the network eg. for transactions. As a tx fee or inflation.
Something I'm confused about: the entire dataset (train+test) is submitted to the blockchain (in the PAY_FOR_TASK transaction), right? So what's to stop miners from using data from the validation set in training?
Edit: I think I understand now; training is deterministic given the nonce and the winning entry is verifiable based on that. You don't have to verify the other entries, because there is no incentive to cheat if you don't win.
If your algorithm uses reduce-like ops for float values and is run on a GPU, your results won't be deterministic even with controlled RNG seeds, since floating point addition is non-commutative.
If the order were deterministic that would be true, but I haven't found any solutions to control GPU task scheduling at that level. Maybe one exists? I don't know enough about low-level GPU coding to say.
I think there are a few candidate computational problem domains that fit the (useful work / fast verification) conundrum. My idea for solving some of the problems of a useful work approach:
1) To make it distributed
Have a set of institutional (eg. Ivy League University Labs) generators that publically post their "Work Units" on their websites and miners attack these problems in round robin fashion.
2) To prevent pre-computation attacks
Have a problem space that is so vast it would be worse than lottery ticket level foolish to try to precompute a solution. Then use a secure hash algorithm seeded with data from the last block to randomly select the "Work Unit" on a particular lab website to work on.
3) Uneven work cost / solution convergence
Have a set of objective pseudo metrics for distributing rewards. I'm trying not to be too coy but there are definitely computational problem domains where you could 'bernoulli' control reward frequency and still make useful work progress.
A move in the right direction. In terms of more low-tech cryptocurrency waste reduction ideas, a few years back there were some companies making water boilers powered by mining units. I wonder how well this idea works at different scales.
Bitcoin mining does generate a lot of heat but I’m not sure it’s hot enough to boil significant amounts of water. There are a few companies who specialize in mining rigs that run on waste produced by oil and gas mining though, which is fuel/energy that otherwise is vented straight into the atmosphere.
Creative, but clearly motivated by a false premise and lack of understanding the security and game theory behind PoW. PoW is about physics and game theory. Bitcoin is minted from energy, the fundamental commodity of the universe. What the authors claim is waste is actually security.
Other comments have already addressed why it's an unstable strategy to integrate two independent pieces of value to PoW but it bears repeating:
All Proof of Work is useful to those who pay for it. Proof of Work does not reward "the most wasteful" producer, if that were true a bitcoin miner [A] with an inefficient HVAC system, who leaves the lights on, and has chips with copious amounts of Joule heating would be rewarded more than a [b] lean PUE, capitally-efficient miner which we all know is not the case.
Producing digital "fraud armor" is valued by systems that can only rely on digital verification in Sybil-attack prone networks (aka the entire real-world environment where one needs to interact with entities outside of a trust circle). Be wary of old, dated, reductive, "small game" arguments that laundering the fraud/security costs of vetting to other systems and then exclude those vetting costs; they don't count as "being more efficient".
You likely encounter fraud Proof of Work but that you have no option but to trade your valuable brain time. A Captcha is a fraud and congestion control mechanism. PoW critics claim that since they push all of the verification costs from the center to the clients that it's an efficient solution (when likely most would use reusable value to avoid the captcha -- say a money).
reply