The Cuckoo Cycle algorithm only needs 128MB and a few seconds to solve this.
That's easy. You just need to design a combinational circuit that verifies that a particular list of nodes forms a cycle.
> How much memory would that take for a billion node graph?
Naively, a lot. Thinking about it, way too much memory to be in any way practical.
However, there may be a good way to solve it with an incremental solver or, instead of materialising the graph, you could encode the siphash function in the sat solver. Then it would use much less memory.
If that works well though, it would compromise the original goal of the project.
My best guess would be that the SAT-solver would be a lot slower, as this PoW system is mostly based on memory latency. From the paper: "Runtime is linear in graph size and dominated by random access latency"
I think someone suggested there already is a cryptocurrency like that.
If you're concerned about energy use and willing to trust a third party to verify the transactions, then why not use VISA?
(I looked at the CureCoin site and skimmed the FoldingCoin white paper [3], but I couldn't find any description of how they verify the folding work. Can someone point me at an explanation?)
[1] https://www.curecoin.net [2] http://foldingcoin.net [3] http://foldingcoin.net/the-coin/white-paper/
Well, that's my question.. They are already willing to trust the party that generated the code that they had legal access to their computer for this purpose. I think we would all be better off if they just required proof of monetary donation to some charity or something.
All that was accomplished here was shifting of trust on these individuals at some energy expense; it's insane.
It's nice theoretical exercise for sure, but I sincerely hope that anyone attempting to build yet another monetary system on waste of energy will seriously reconsider the idea.
[1] Actually it is probably more complicated, one entity, one vote, so that it can include companies and the like. This alone seems non-trivial, what exactly qualifies as a separate entity?
So you should be able to run this on a smartphone, while it's charging overnight.
For instance, to look for a 42 cycle on a billion node graph, the reference algorithm uses 128MB.
If you want to get by with only 32MB, then you can run that alternative algorithm, but it will take about 128/32*25=100 times longer. The penalty factor of about 25 is due to losing the ability to represent edges with a single bit.
You can also parallelize by having more cores share the same memory but this it only takes so many cores to saturate a memory bank.
That paper sadly misrepresent Cuckoo Cycle by focusing on an outdated version from the first half of 2014 (and incorrectly describes it as working on directed graphs).
Bitcoin mining could be more decentralized if it better resembled a lottery, where huge numbers of people play for an expected loss. In other words, the lack of people mining at a loss makes mining profitable and hence subject to forces of centralization.
There are several reasons why mining as a lottery substitute is rare, a major one being that commodity hardware is inefficient by many orders of magnitude, making even a botnet next to useless. Perhaps, if a proof of work, whose efficiency gap (with custom hardware) is at most an order of magnitude, were adopted (or slowly phased in), enough lottery players would arise to make mining unprofitable at scale.
Botnets should then just be welcomed as a modest increase in decentralization.
>These bounties are to expire at the end of 2016. They are admittedly modest in size, but then claiming them might only require one or two insightful tweaks to my existing implementations.
