12 ms·

Proof of work algorithm in Monero based on random code execution

65 points by maxfan8 6y ago

elcritch 6y ago
Does this enable using PoW to run something like Ethereum VM/contracts?
- xiphias2 6y ago
  The security of proof of work algorithm depends on the execution not having an economical value (and actually cost a mostly fixed amount of work).
  - elcritch 6y ago
    Good point. Does that consider that case where the economic value of running the PoW is part of the network itself, as say running an Ethereum app? For the miners the PoW wouldn't be valuable, but instead of burning computation time the byproduct could be useful part of the network.
    - xiphias2 6y ago
      With Ethereum contracts the cost of validation is expensive, and for proof of work you need a function that is expensive to run, but cheap to verify (the inverse of SHA-256 is such a function). The main concern against proof of stake is what you just described actually: it doesn't cost money to create, but as the value of staking is part of the cryptocurrency, a malicious party could get and stake of a lot of that cryptocurrency, create a leveraged short contract to protect itself, then reverse the transaction. Another example would be using protein folding for cancer research for example, which sounds a noble cause, but it creates an incentive for drug companies to be miners, and could lead to even bigger centralization of mining than what is already happening.
tromp 6y ago
This PoW is rather complex and takes nontrivial amounts of time and memory to verify. It accepts these downsides in an attempt to achieve "ASIC resistance", which means limiting the potential efficiency gains of custom chips to a small factor like 2x or 3x. This should make their design and manufacture economically unattractive, with long ROI times. And thus allow commodity hardware to remain competitive.
- blasrodri 6y ago
  > And thus allow commodity hardware to remain competitive. This would make the system more robust, at the expense of increasing the power consumption. Is that correct? Doesn't seem really eco-friendly.
  - Nursie 6y ago
    Everything about proof-of-work systems is not eco-friendly, and involves burning power 24/7, up to as much power as the produced cryptocurrency is worth. This seems perverse in a world where we're trying to cut down on energy use in almost every other area. (no doubt someone will be along in a minute to tell me that cryptocurrency mining somehow uses "spare" electricity and burning the same amount of power as a mid-sized country isn't actually a problem at all!)
    - a1369209993 6y ago
      Nope! The[0] blockchain necessarily has use on the order of half the (non-dedicated) power generation capability it's host civilization in order to achieve proper security; otherwise the other half of said power could used to mount a 51% attack. It's less in practice, both because it's not worth that much to attack, and because it's not fully secure, but in theory, a Kardashev 3 civilization would need a Kardashev 2.97 or so energy expenditure to secure it's blockchain. 0: and it is a definite article, like the internet. There by definition can't be more than one at any given time.
      - sparkie 6y ago
thesz 6y ago
I did an analysis of this PoW at my line of work and I would say that it is really complicated. Unnecessarily so, I have to add. I also have a comment about ASIC resistance. There are tools that allow to customize hardware upon programs it will execute, [1] is an example of one such tool, there are some others. [1] http://openasip.org/tta.html http://openasip.org/tta.html If you write a RandomX code generator and interpreter and customize the CPU hardware using tools like one above you will get an optimized version of the hardware. Take a look at [2] for a results of such codesign attempts for Fourier transform. The optimization in energy efficiency can be as high as 100+ times over general purpose processors and on par and exceeding ASIC implementation. [2] https://www.researchgate.net/publication/321700396_Codesign_case_study_on_transport-triggered_architectures https://www.researchgate.net/publication/321700396_Codesign_... One would duly note that RandomX employs floating point instructions in some parts of hashing process. I will respond that floating point operations can be expressed as operations on fixed point values and these hardware parts can (and will) be shared with other computations. Basically, the codesign tool will implement for you a split (FP)ALU. This will also increase energy efficiency over GPU and general purpose CPUs which have different paths for FP and integer computations and usually do not share ALU parts between these. To comclude, first, RandomX is needlessly complicated. Second, I think that ASIC version can be attained without writing everything in Verilog by hand, you may stick with C reference implementation for most of the work. And, last but not least, the gain in hashes per joule from ASIC implementation can be much higher than 2-5 times over CPU or GPU.
- deepnotderp 6y ago
  Comparing an FFT ASIC to a random code "ASIC" is.... well, just wrong.
  - hyc_symas 6y ago
    Yep. His comment completely misses the point, and everything he mentions about codesign tools is irrelevant.
    - deleted 6y ago
      [deleted]
hasa 6y ago
Proof of work is anyway bad idea (work for nothing), unless the work is something useful.
- dmos62 6y ago
  It's not work for nothing, because it gives you consensus and reliability. Maybe you meant to say that there's better solutions...
  - hasa 6y ago
    Ok it's wrong to say "nothing". But I don't really see consensus nor reliability in crypto currencies. Specially the consensus seems to be missing, if you look this phenomena far enough.
- sparkie 6y ago
  The work is useful. It randomly selects a participant out of potentially billions or more to commit the next block, but only the next block, and no others to the blockchain. This ensures the chain remains fair because any potentially malicious actor cannot sustain an attack involving malicious blocks for long - it costs them too much electricity. There is no known alternative system which is capable of randomly selecting a participant out of the entire pool of participants. Every other "solution" works by limiting the participation, because it is impossible for a network wide agreement at this scale to be done (would require every node communicating with every other node in the network and having a unanimous agreement on who has the legitimate authority to commit the next block). Any system which doesn't require work to be done to prove that the correct participant was selected is vulnerable to Sybil attacks, where people control more network nodes in attempt to gain more leverage over others. The idea of staking some money doesn't fix this either, because proof-of-stake has the "nothing at stake" problem where stakers aren't actually spending money because they're guaranteed to get it back for being honest. Running many nodes is also fairly cheap and has the "not much at stake" problem. Only proof-of-work has the "much at stake" problem because the irreversible spending of money on electricity happens prior to any reward which may be received, like a lottery. You might consider Bitcoin as a whole to be a bad idea. However, with recent "printing" in the tune of trillions of dollars, and with Bitcoin providing an inviolable fix for inflation, I think it might just be worth the effort - at least for anybody sensible who wants to save money for the future. In terms of Monero, which doesn't fix inflation, it is useful for evading unwarranted financial surveillance. I suspect this will be fine for some time to come, but there will be eventually be enough privacy features on Bitcoin to make it unnecessary. For now: save in Bitcoin, spend in Monero.
lvs 6y ago
We should reject PoW algorithms as generally destructive. When I say destructive, I mean they cause more global harm than they purport to alleviate. PoW should have been set aside as soon as it was generally understood that the network's energy consumption might be unbounded.
- sparkie 6y ago
  > We should reject Who is "we"? You can't "set aside" something which a free market has chosen to accept. If you're upset about PoW, invent a superior replacement which the market would prefer over PoW. However, I suspect you cannot. I'm doubtful that such thing can exist. Bitcoin is now an essential commodity because there is no replacement for it when it comes to saving money or evading warrantless (illegal) surveillance. The central banks and governments around the world caused this, and they aren't capable of reversing it.
  - david_draco 6y ago
    > Who is "we"? Presumably society. > You can't "set aside" something which a free market has chosen to accept. We have set aside CFCs even though they were accepted by the free market. They were harmful to the environment, creating the ozone hole. Similarly, PoW mining has an enormous and well-documented ecological cost. > If you're upset about PoW, invent a superior replacement which the market would prefer over PoW. > However, I suspect you cannot. I'm doubtful that such thing can exist. PoS exist. > Bitcoin is now an essential commodity because there is no replacement for it when it comes to saving money or evading warrantless (illegal) surveillance. All transactions and account balances in Bitcoin are public. From meta data and corresponding networks one can figure out where and who the people are (NSA does this too). It is not very private at all. > The central banks and governments around the world caused this, and they aren't capable of reversing it. I doubt that it is a essential commodity and suspect you are overestimating the economic importance of Bitcoin.
    - sparkie 6y ago
      > Presumably society. Which society? > We have set aside CFCs even though they were accepted by the free market. They were harmful to the environment, creating the ozone hole. Some regulations can be enforced. It's going to be a different story attempting to regulate something which can be hidden trivially with encryption, has no physical presence, and can be stored in ones head to prevent seizure. > All transactions and account balances in Bitcoin are public. From meta data and corresponding networks one can figure out where and who the people are (NSA does this too). It is not very private at all. This is true for plain use of Bitcoin, but there are ways of evading chain analysis, and you can also swap out your Bitcoin for Monero for spending. > I doubt that it is a essential commodity and suspect you are overestimating the economic importance of Bitcoin. It may not be essential to you, but there are plenty who consider it so, and these will only grow as people further distrust their governments and central banks.
polytely 6y ago
Total sidenote but someone should start a cryptocurrency that is proof of Storage-space(does that exist?), where you have to allocate space to mirror the content of the Internet Archive. Is there a way that could work? (I know almost nothing about cryptocurrency)
- jeffrallen 6y ago
  Filecoin certainly needs that. I'm not sure if Filecoin has it yet.
- DarthGhandi 6y ago
  There's a half dozen of those in existence for a good while now.
- chemmail 6y ago
  There are a ton of them. THey don't pay enough for people to take seriously though. Amazon does it way better right now.
  - Lewton 6y ago
    There's a ton of filecoins mirroring the internet archive?
cryptica 6y ago
Someone should make a PoW algorithm based on useful things like game theory; for example a chess bot competing against other chess bots, the top winner forges the block and gets the rewards. This is still not extremely useful, but better than just hashing useless strings. Ideally, PoW algorithms should be focused on real science and/or economic problems.
- david_draco 6y ago
  see https://gridcoin.us/ https://gridcoin.us/
- polytely 6y ago
  Or do a PoW on training AI, you get both buzzwords in one (infinite money), and it actually accomplishes something.
- kolinko 6y ago
  There is already a PoW that helps with protein folding. As for „should” - you may not be aware of this, but telling someone they „should” do something if you don’t plan to help is a bit offensive.
  - cryptica 6y ago
    >> but telling someone they „should” do something if you don’t plan to help is a bit offensive. I disagree with this very strongly. How is sharing good ideas offensive? Even if some people already knew about this, not everyone did and sharing these ideas could only help society. That would be like telling Elon Musk to shut up when he came up with the idea for the Hyperloop but didn't implement himself... Elon just didn't have the time. I'm no Elon but I also don't have the time because I'm working on a DEX which I think is a better use of my skills. The fact that I'm no Elon gives me even more incentive to share my ideas. I don't have many followers, so if I implement my idea, nobody will use it (no matter how good it is); I won't be able to generate enough hype. On the other hand, if some rich person from HN sees my idea and implements it, then it will be more likely to succeed (just because of network effects). I can contribute more to society by giving my idea to someone else than implementing it myself. You severely underestimate the power of network effects and capital. I don't have much capital so even the best ideas in my own hands are essentially worthless. If I implement it, even if it's very good and the best of its kind, I guarantee almost 100% that nobody will be interested in it. Nobody will accept that it's the best of its kind. The media ignore it, companies will not encourage their employees to discus it with each other, etc...

65 points by maxfan8 6y ago

elcritch 6y ago

Does this enable using PoW to run something like Ethereum VM/contracts?

xiphias2 6y ago
The security of proof of work algorithm depends on the execution not having an economical value (and actually cost a mostly fixed amount of work).
- elcritch 6y ago
  Good point. Does that consider that case where the economic value of running the PoW is part of the network itself, as say running an Ethereum app? For the miners the PoW wouldn't be valuable, but instead of burning computation time the byproduct could be useful part of the network.
  - xiphias2 6y ago
    With Ethereum contracts the cost of validation is expensive, and for proof of work you need a function that is expensive to run, but cheap to verify (the inverse of SHA-256 is such a function). The main concern against proof of stake is what you just described actually: it doesn't cost money to create, but as the value of staking is part of the cryptocurrency, a malicious party could get and stake of a lot of that cryptocurrency, create a leveraged short contract to protect itself, then reverse the transaction. Another example would be using protein folding for cancer research for example, which sounds a noble cause, but it creates an incentive for drug companies to be miners, and could lead to even bigger centralization of mining than what is already happening.

tromp 6y ago

This PoW is rather complex and takes nontrivial amounts of time and memory to verify. It accepts these downsides in an attempt to achieve "ASIC resistance", which means limiting the potential efficiency gains of custom chips to a small factor like 2x or 3x. This should make their design and manufacture economically unattractive, with long ROI times. And thus allow commodity hardware to remain competitive.

blasrodri 6y ago
> And thus allow commodity hardware to remain competitive. This would make the system more robust, at the expense of increasing the power consumption. Is that correct? Doesn't seem really eco-friendly.
- Nursie 6y ago
  Everything about proof-of-work systems is not eco-friendly, and involves burning power 24/7, up to as much power as the produced cryptocurrency is worth. This seems perverse in a world where we're trying to cut down on energy use in almost every other area. (no doubt someone will be along in a minute to tell me that cryptocurrency mining somehow uses "spare" electricity and burning the same amount of power as a mid-sized country isn't actually a problem at all!)
  - a1369209993 6y ago
    Nope! The[0] blockchain necessarily has use on the order of half the (non-dedicated) power generation capability it's host civilization in order to achieve proper security; otherwise the other half of said power could used to mount a 51% attack. It's less in practice, both because it's not worth that much to attack, and because it's not fully secure, but in theory, a Kardashev 3 civilization would need a Kardashev 2.97 or so energy expenditure to secure it's blockchain. 0: and it is a definite article, like the internet. There by definition can't be more than one at any given time.
    - sparkie 6y ago

thesz 6y ago

I did an analysis of this PoW at my line of work and I would say that it is really complicated. Unnecessarily so, I have to add. I also have a comment about ASIC resistance. There are tools that allow to customize hardware upon programs it will execute, [1] is an example of one such tool, there are some others. [1] http://openasip.org/tta.html http://openasip.org/tta.html If you write a RandomX code generator and interpreter and customize the CPU hardware using tools like one above you will get an optimized version of the hardware. Take a look at [2] for a results of such codesign attempts for Fourier transform. The optimization in energy efficiency can be as high as 100+ times over general purpose processors and on par and exceeding ASIC implementation. [2] https://www.researchgate.net/publication/321700396_Codesign_case_study_on_transport-triggered_architectures https://www.researchgate.net/publication/321700396_Codesign_... One would duly note that RandomX employs floating point instructions in some parts of hashing process. I will respond that floating point operations can be expressed as operations on fixed point values and these hardware parts can (and will) be shared with other computations. Basically, the codesign tool will implement for you a split (FP)ALU. This will also increase energy efficiency over GPU and general purpose CPUs which have different paths for FP and integer computations and usually do not share ALU parts between these. To comclude, first, RandomX is needlessly complicated. Second, I think that ASIC version can be attained without writing everything in Verilog by hand, you may stick with C reference implementation for most of the work. And, last but not least, the gain in hashes per joule from ASIC implementation can be much higher than 2-5 times over CPU or GPU.

deepnotderp 6y ago
Comparing an FFT ASIC to a random code "ASIC" is.... well, just wrong.
- hyc_symas 6y ago
  Yep. His comment completely misses the point, and everything he mentions about codesign tools is irrelevant.
  - deleted 6y ago
    [deleted]

hasa 6y ago

Proof of work is anyway bad idea (work for nothing), unless the work is something useful.

dmos62 6y ago
It's not work for nothing, because it gives you consensus and reliability. Maybe you meant to say that there's better solutions...
- hasa 6y ago
  Ok it's wrong to say "nothing". But I don't really see consensus nor reliability in crypto currencies. Specially the consensus seems to be missing, if you look this phenomena far enough.
sparkie 6y ago
The work is useful. It randomly selects a participant out of potentially billions or more to commit the next block, but only the next block, and no others to the blockchain. This ensures the chain remains fair because any potentially malicious actor cannot sustain an attack involving malicious blocks for long - it costs them too much electricity. There is no known alternative system which is capable of randomly selecting a participant out of the entire pool of participants. Every other "solution" works by limiting the participation, because it is impossible for a network wide agreement at this scale to be done (would require every node communicating with every other node in the network and having a unanimous agreement on who has the legitimate authority to commit the next block). Any system which doesn't require work to be done to prove that the correct participant was selected is vulnerable to Sybil attacks, where people control more network nodes in attempt to gain more leverage over others. The idea of staking some money doesn't fix this either, because proof-of-stake has the "nothing at stake" problem where stakers aren't actually spending money because they're guaranteed to get it back for being honest. Running many nodes is also fairly cheap and has the "not much at stake" problem. Only proof-of-work has the "much at stake" problem because the irreversible spending of money on electricity happens prior to any reward which may be received, like a lottery. You might consider Bitcoin as a whole to be a bad idea. However, with recent "printing" in the tune of trillions of dollars, and with Bitcoin providing an inviolable fix for inflation, I think it might just be worth the effort - at least for anybody sensible who wants to save money for the future. In terms of Monero, which doesn't fix inflation, it is useful for evading unwarranted financial surveillance. I suspect this will be fine for some time to come, but there will be eventually be enough privacy features on Bitcoin to make it unnecessary. For now: save in Bitcoin, spend in Monero.

lvs 6y ago

We should reject PoW algorithms as generally destructive. When I say destructive, I mean they cause more global harm than they purport to alleviate. PoW should have been set aside as soon as it was generally understood that the network's energy consumption might be unbounded.

sparkie 6y ago
> We should reject Who is "we"? You can't "set aside" something which a free market has chosen to accept. If you're upset about PoW, invent a superior replacement which the market would prefer over PoW. However, I suspect you cannot. I'm doubtful that such thing can exist. Bitcoin is now an essential commodity because there is no replacement for it when it comes to saving money or evading warrantless (illegal) surveillance. The central banks and governments around the world caused this, and they aren't capable of reversing it.
- david_draco 6y ago
  > Who is "we"? Presumably society. > You can't "set aside" something which a free market has chosen to accept. We have set aside CFCs even though they were accepted by the free market. They were harmful to the environment, creating the ozone hole. Similarly, PoW mining has an enormous and well-documented ecological cost. > If you're upset about PoW, invent a superior replacement which the market would prefer over PoW. > However, I suspect you cannot. I'm doubtful that such thing can exist. PoS exist. > Bitcoin is now an essential commodity because there is no replacement for it when it comes to saving money or evading warrantless (illegal) surveillance. All transactions and account balances in Bitcoin are public. From meta data and corresponding networks one can figure out where and who the people are (NSA does this too). It is not very private at all. > The central banks and governments around the world caused this, and they aren't capable of reversing it. I doubt that it is a essential commodity and suspect you are overestimating the economic importance of Bitcoin.
  - sparkie 6y ago
    > Presumably society. Which society? > We have set aside CFCs even though they were accepted by the free market. They were harmful to the environment, creating the ozone hole. Some regulations can be enforced. It's going to be a different story attempting to regulate something which can be hidden trivially with encryption, has no physical presence, and can be stored in ones head to prevent seizure. > All transactions and account balances in Bitcoin are public. From meta data and corresponding networks one can figure out where and who the people are (NSA does this too). It is not very private at all. This is true for plain use of Bitcoin, but there are ways of evading chain analysis, and you can also swap out your Bitcoin for Monero for spending. > I doubt that it is a essential commodity and suspect you are overestimating the economic importance of Bitcoin. It may not be essential to you, but there are plenty who consider it so, and these will only grow as people further distrust their governments and central banks.

polytely 6y ago

Total sidenote but someone should start a cryptocurrency that is proof of Storage-space(does that exist?), where you have to allocate space to mirror the content of the Internet Archive. Is there a way that could work? (I know almost nothing about cryptocurrency)

jeffrallen 6y ago
Filecoin certainly needs that. I'm not sure if Filecoin has it yet.
DarthGhandi 6y ago
There's a half dozen of those in existence for a good while now.
chemmail 6y ago
There are a ton of them. THey don't pay enough for people to take seriously though. Amazon does it way better right now.
- Lewton 6y ago
  There's a ton of filecoins mirroring the internet archive?

cryptica 6y ago

Someone should make a PoW algorithm based on useful things like game theory; for example a chess bot competing against other chess bots, the top winner forges the block and gets the rewards. This is still not extremely useful, but better than just hashing useless strings. Ideally, PoW algorithms should be focused on real science and/or economic problems.

david_draco 6y ago
see https://gridcoin.us/ https://gridcoin.us/
polytely 6y ago
Or do a PoW on training AI, you get both buzzwords in one (infinite money), and it actually accomplishes something.
kolinko 6y ago
There is already a PoW that helps with protein folding. As for „should” - you may not be aware of this, but telling someone they „should” do something if you don’t plan to help is a bit offensive.
- cryptica 6y ago
  >> but telling someone they „should” do something if you don’t plan to help is a bit offensive. I disagree with this very strongly. How is sharing good ideas offensive? Even if some people already knew about this, not everyone did and sharing these ideas could only help society. That would be like telling Elon Musk to shut up when he came up with the idea for the Hyperloop but didn't implement himself... Elon just didn't have the time. I'm no Elon but I also don't have the time because I'm working on a DEX which I think is a better use of my skills. The fact that I'm no Elon gives me even more incentive to share my ideas. I don't have many followers, so if I implement my idea, nobody will use it (no matter how good it is); I won't be able to generate enough hype. On the other hand, if some rich person from HN sees my idea and implements it, then it will be more likely to succeed (just because of network effects). I can contribute more to society by giving my idea to someone else than implementing it myself. You severely underestimate the power of network effects and capital. I don't have much capital so even the best ideas in my own hands are essentially worthless. If I implement it, even if it's very good and the best of its kind, I guarantee almost 100% that nobody will be interested in it. Nobody will accept that it's the best of its kind. The media ignore it, companies will not encourage their employees to discus it with each other, etc...