I feel the importance of low block interval times is overrated.

If a cheap multicore cpu like the http://hackaday.com/2012/09/28/massively-parallel-64-core-computer-costs-99/
can already saturate DRAM's latency, then there's not much point in developing an ASIC.

If you want to call Cuckoo Cycle a memory-only PoW rather than a CPU-only PoW,
that suits me fine.

Cuckoo is not suitable for very short block intervals (unless you shrink the memory requirement
below 1GB, but then you lose botnet resistance).
For a description of the algorithm, see the paper. It's not that long.

The problem of your PoW is the very fact that you have not published it...

I addressed your (mistaken) criticism in your thread.

The code will be easier to understand if you read the paper. try to get through the gruesome...
The algorithm repeatedly generates edges (u,v) and follows paths from u and v.
These paths are stored in arrays us[] and vs[], with nu and nv used as path length.
The edge is actually stored in us[0] (same as *us in c) and vs[0] (same as *vs).

Why don't you fork my repo and translate all the code into java as best as you can.
Then allow other people to contribute. When I have time, I'll look over your progress and
help fix it up...

You don't think what?

Bucketization is irrelevant to implementations of Cuckoo Cycle, which is *defined* based on plain cuckoo hashing.

Cuckoo Cycle lets you set whatever memory requirement you want.
If you think 4GB is too little, then just go for more.
Validation is instant in any case. Why do you bring up these point that were addressed already?

You haven't solved the major problem of your PoW yet.

Thanks!
I will write a Java version eventually, but it's pretty low on my list of priorities,
and I'm busy with many other things. Perhaps you can find some other Java programmer
to port it sooner. I will have more time in March...

Since yesterday, the implementation allows for multi-threading, and the README now says:

6) running time for the current implementation on high end x86 is under 24s/GB single-threaded,
   and under 3s/GB for 12 threads.

So 16GB would take well under a minute on a server.

In any case, I disagree that 16GB is needed to defeat botnets. Most machines in a botnet
have less than 4GB of *unused* memory, and running a 4GB cuckoo would send them into
swap-hell, not only making them useless for mining, but also alerting their owner.
So Cuckoo Cycle might actually help to shrink botnets...

With all the expertise on CPU oriented PoWs in this thread,
can anyone comment on my Cuckoo Cycle design, which is
focused entirely on main memory random access latency?

https://github.com/tromp/cuckoo has a whitepaper and implementation.

Feedback is most welcome.

I know:-(

Anyway, the misconception that a memory-hard PoW must be slow to verify appears
to be widespread, so I wanted to rectify it in case others stumble on this old thread.

The coin isn't there yet, but Cuckoo Cycle appears to be the proof of work that you want.

A Proof of work can be both requiring tons of memory, and be trivially verifiable.
See Cuckoo Cycle at https://github.com/tromp/cuckoo

You might want to read up on https://github.com/tromp/cuckoo

I vote Cuckoo Cycle:-)

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.

Bitcoin mining is all computation and no memory.

Litecoin mining requires 128KB of memory per scrypt instance but only 1024
random accesses, with negligable latency.

Primecoin mining has a sieving and a modular exponentiation component, the latter of
which is pure computation, while the former requires a few megabytes of memory
(with non-random access).

Protoshares mining with Momentum requires 512MB but performs at least one complex SHA512
computation for each memory access, with a choice of algorithms some of which avoid random access.

The memory requirements above are not absolute but allow a trade-off between time and memory.

Guess which proof-of-work system achieves the following:

1) it performs only one very cheap hash computation for several 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

Runtime is completely dominated by memory latency. It promotes the use
of commodity general-purpose hardware over custom designed single-purpose hardware,
making mining more sustainable.

(re-announcing since paper has been substantially improved, and the implementation changed hash function)

Cuckoo Cycle is the first proof of work that does little computation but lots of random accesses to RAM,
making it both CPU and power friendly.

Proofs, of size 42*4=168 byes, are trivially verifiable, using only 1/3 KB.

It can be made to require any desired amount of RAM, e.g. 4GB, which is 32x more than what fits on an ASIC,
and which will send nearly all botnet computers into swap-hell, alerting their owners.

A whitepaper and implementation is available at https://github.com/tromp/cuckoo

I just design the PoW. It's up to other people to launch new coins that use it:-)

They should go with a relatively long block interval though (10min), so they can increase the
memory requirement to 4GB or more (where running a single instance takes over a minute).

I'm also a proponent of fixed rewards, since the rate of lost coins is a probably a few percent,
so even a fixed reward coin can't remain inflationary for long.

Here's how Cuckoo Cycle at 2^{28} nodes compares:

It has the tiniest possible SHA256 component (one call), and a moderate siphash-2-4 component.
Each instance requires 1GB of memory to perform and hashes 1GB of data.
By contrast, the verification only requires 1/3 KB and takes less than one 10th of  a *micro* second.

Each instance has about a 5% probability of having a solution at the default setting.

Memory access in Cuckoo is maximally random, so it's constrained by memory latency
rather than bandwidth, and caches are irrelevant. The amount of computation is minimized
relative to memory access. See https://github.com/tromp/cuckoo for a paper and implementation.

You mean each CPU Coin with memory requirements below what the GPU has.
We just haven't seen any CPU coins yet that require, say, from 4GB to 32GB of memory,
but it's perfectly feasible to introduce such coins, that won't "fit" on a GPU (let alone ASIC).

I wouldn't base a PBKDF on Cuckoo, since you'd forego its best feature, namely trivial proof verifiabilty.

Are you preparing an entry for the Password Hashing Competition
at https://password-hashing.net/ ?
They also like candidates to have a limited amount of parallelizability, so that a multicore server
could use multiple cores to compute it. This is hard to arrange with Cuckoo.

Still, if you must use Cuckoo, you could use a size of 2^25, which uses 128MB,
and takes about 5s to run on a 3.2Ghz intel i5 with sha256 replaced by siphash
(which may well become permanent) and the default easiness setting.
The output could be sha256 applied to the sequence of all writes to the cuckoo array
(including the path reversals).