8 ms·

A Proof of Useful Work for Artificial Intelligence on the Blockchain

71 points by lelf 7y ago

heyitsguay 7y ago
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?
- gglon 7y ago
  As I understand the whole point is to create decentralized marketplace without wasting energy on useless tasks (aside for proving energy use)
  - heyitsguay 7y ago
    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.
    - gglon 7y ago
      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)
      - heyitsguay 7y ago
        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.
        gglon 7y ago
        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.
dmos62 7y ago
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.
- thinkmassive 7y ago
  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.
- Double_a_92 7y ago
  I remember seeing little electical heaters, that used some ASIC instead of a coil to produce the heat.
drcode 7y ago
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)
- tastroder 7y ago
  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.
Proven 7y ago
That is a hammer looking for a nail.
paulgb 7y ago
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.
- heyitsguay 7y ago
  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.
  - paulgb 7y ago
    As long as the order of non-commutative operations is deterministic, this isn't a problem though, right?
    - heyitsguay 7y ago
      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.
lalaland1125 7y ago
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.
- tzumby 7y ago
  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.
  - garmaine 7y ago
    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.
    - tzumby 7y ago
      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! Also, I think those large primes do have economic value (https://en.wikipedia.org/wiki/Largest_known_prime_number#Prizes https://en.wikipedia.org/wiki/Largest_known_prime_number#Pri...). I'm not sure if that's the purpose of PrimeCoin or who would get the prize, but they nonetheless have some economic value.
    - Double_a_92 7y ago
      It could work if you can't decide who the benefited person is. I.e. solving problems out of a random pool of them or so.
coinward 7y ago
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.
marcinjachymiak 7y ago
> 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.
- drcode 7y ago
  More likely, I think they'll realize the verifiers will need to post a bond in order for their scheme to work... reinventing proof-of-stake, instead.
- yodsanklai 7y ago
  Is there an academic reference that summarizes these things?
  - Anon84 7y ago
    This might be useful: https://queue.acm.org/detail.cfm?id=3136559 https://queue.acm.org/detail.cfm?id=3136559
DINKDINK 7y ago
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).
zelly 7y ago
Suppose I wanted to attack this network and my business had a use for some trained models. 1. Rent a million T/GPUs. 2. Send a request to the network for the jobs. 3. Solve my own business problem. 4. Reorganize the blockchain to double spend my coins on an exchange. Sounds like a clear win/win. Nobody could prosecute me either because it's not legal tender.
grizzles 7y ago
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.

71 points by lelf 7y ago

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?

gglon 7y ago
As I understand the whole point is to create decentralized marketplace without wasting energy on useless tasks (aside for proving energy use)
- heyitsguay 7y ago
  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.
  - gglon 7y ago
    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)
    - heyitsguay 7y ago
      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.
      - gglon 7y ago
        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.

dmos62 7y ago

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.

thinkmassive 7y ago
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.
Double_a_92 7y ago
I remember seeing little electical heaters, that used some ASIC instead of a coil to produce the heat.

drcode 7y ago

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)

tastroder 7y ago
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.

Proven 7y ago

That is a hammer looking for a nail.

paulgb 7y ago

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.

heyitsguay 7y ago
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.
- paulgb 7y ago
  As long as the order of non-commutative operations is deterministic, this isn't a problem though, right?
  - heyitsguay 7y ago
    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.

lalaland1125 7y ago

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.

tzumby 7y ago
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.
- garmaine 7y ago
  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.
  - tzumby 7y ago
    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! Also, I think those large primes do have economic value (https://en.wikipedia.org/wiki/Largest_known_prime_number#Prizes https://en.wikipedia.org/wiki/Largest_known_prime_number#Pri...). I'm not sure if that's the purpose of PrimeCoin or who would get the prize, but they nonetheless have some economic value.
  - Double_a_92 7y ago
    It could work if you can't decide who the benefited person is. I.e. solving problems out of a random pool of them or so.

coinward 7y ago

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.

marcinjachymiak 7y ago

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

drcode 7y ago
More likely, I think they'll realize the verifiers will need to post a bond in order for their scheme to work... reinventing proof-of-stake, instead.
yodsanklai 7y ago
Is there an academic reference that summarizes these things?
- Anon84 7y ago
  This might be useful: https://queue.acm.org/detail.cfm?id=3136559 https://queue.acm.org/detail.cfm?id=3136559

DINKDINK 7y ago

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

zelly 7y ago

Suppose I wanted to attack this network and my business had a use for some trained models. 1. Rent a million T/GPUs. 2. Send a request to the network for the jobs. 3. Solve my own business problem. 4. Reorganize the blockchain to double spend my coins on an exchange. Sounds like a clear win/win. Nobody could prosecute me either because it's not legal tender.

grizzles 7y ago

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.