cuckoo

New proof-of-work schemes in crypto-currencies should ideally have optimized implementations from day 0, to prevent the situation described in the article where some people can mine much more efficiently than others. To this end, I offer several bounties for my Cuckoo Cycle proof-of-work scheme, which David has helped refine, and which has yet to be deployed by any coin. See https://github.com/tromp/cuckoo for details and a whitepaper.

"MapGraph is up to two orders of magnitude faster than parallel CPU implementations on up 24 CPU cores and has performance comparable to a state-of-the-art manually optimized GPU implementation." That doesn't bode well for my $1000 GPU Speed Parity Bounty at https://github.com/tromp/cuckoo based on my belief that the Cuckoo Cycle graph-theoretic proof-of-work algorithm is more suited to CPUs.

The way to achieve ASIC,FPGA and even GPU resistance is to require many GB of memory. Better yet, random access to many GB of memory. Then your performance is limited by memory latency. This is what I designed Cuckoo Cycle (https://github.com/tromp/cuckoo) for.

Yes, why not a PoW that's all of ASIC resistant GPU resistant botnet resistant My Cuckoo Cycle PoW (https://github.com/tromp/cuckoo) configured to require for instance 7GB of memory, is all of the above. And is very power friendly, since only 5% of the runtime is computation and 95% is waiting for main memory random access latency...

While they haven't yet figured out how to make a proof-of-work do useful work, one can make a relatively low-power one that mostly (95%) substitutes memory latency for computation, as in my https://github.com/tromp/cuckoo

From the README of my "Cuckoo Cycle" Proof-of-Work at https://github.com/tromp/cuckoo : Mining is generally considered to be inherently power hungry but it need not be. It’s a consequence of making the proof of work computationally intensive. If computation is minimized in favor of random access to gigabytes of memory (incurring long latencies), then mining will require large investments in RAM but relatively little power. Cuckoo Cycle represents a breakthrough in three important ways: 1) it performs only one very cheap siphash computation for about 3.3 random accesses to memory, 2) its memory requirement can be set arbitrarily and doesn't allow for any time-memory trade-off. 3) verification of the proof of work is instant, requiring 1 sha256 and 42 siphash computations. Runtime in Cuckoo Cycle is completely dominated by memory latency. I

Cuckoo Cycle at https://github.com/tromp/cuckoo seems like a better proof-of-work system and comes with a full implementation. It has the following features: 1) proofs take the form of a length 42 cycle in the Cuckoo graph, so that verification only requires computing 42 hashes. 2) the graph size (number of nodes) can scale from 1x2^10 to 7x2^29 with 4 bytes needed per node, so memory use scales from 4KB to 14GB. Use of 4GB+ should make it somewhat resistent to botnets. 3) running time is roughly linear in memory, at under 1min/GB for the current implementation on high end x86. 4) no time-memory trade-off (TMTO) is known, and memory access patterns are the worst possible, making the algorithm constrained by memory latency. 5) it has a natural notion of difficulty, namely the number of edges in the graph; above about 60% of size, a 42-cycl

Dagger appears to be inferior to the Cuckoo Cycle proof of work system I recently developed; see https://github.com/tromp/cuckoo Cuckoo Cycle is a new proof of work system with the following features 1) proofs take the form of a length 42 cycle in the Cuckoo graph, so that verification only requires computing 42 hashes. 2) the graph size (number of nodes) can scale from 1x2^10 to 7x2^29 with 4 bytes needed per node, so memory use scales from 4KB to 14GB 3) running time is roughly linear in memory, at under 1s/4MB 4) there is no time-memory trade-off, and memory access patterns are the worst possible, making the algorithm constrained by memory latency 5) it has a natural notion of difficulty, namely the number of edges in the graph; above about 60% of size, a 42-cycle is almost guaranteed, but below 50% the probability starts to fall sharp