cuckoo VS Atomic

Asymmetric PoW algorithms, such as Cuckoo Cycle [1] or the poorly named Equihash [2] (which is not a hash function) do not lend themselves to password hashing, since a given instance can have 0 or 1 or many solutions.

[1] https://github.com/tromp/cuckoo

[2] https://en.wikipedia.org/wiki/Equihash

The full technical report describing the LOCKSS forerunner to bitcoin may be downloaded at [1]. Interestingly, LOCKSS used a memory bound Proof-of-Work, where both prover and verifier perform a random walk in a 1GB table. But the prover had to do this many times, to obtain some final hash with many leading zeroes. This was before the invention of asymmetric PoW systems like Cuckoo Cycle [2] where the PoW can be verified with no memory use.

[1] https://www.researchgate.net/publication/31869581_Preserving...

[2] https://github.com/tromp/cuckoo

A non-hashcash-style PoW scheme is Cuck(at)ooCycle.

The use of scrypt as underlying hash function is a rather poor choice though, as scrypt's memory hardness makes PoW verification unnecessarily expensive.

It's perfectly possible to make a memory hard PoW that's instantly verifiable, by using something other than hashcash. Examples include Cuckoo Cycle [1], and Equihash [2].

[1] https://github.com/tromp/cuckoo

[2] https://en.wikipedia.org/wiki/Equihash

Non-Solution #8: Cuckoo Cycle https://github.com/tromp/cuckoo Why: At least a few people have looked at it, and any attacker is far more likely to directly attack the blockchain itself, than my server (which doesn't get involved with the blockchain) Why not: The "mathematical specification" https://github.com/tromp/cuckoo/blob/master/doc/mathspec is woefully inadequate, their "C spec" focuses more on ASCII art than actual readability https://github.com/tromp/cuckoo/blob/master/doc/spec and as https://handshake.org/files/handshake.txt points out, cannot be easily adjusted in difficulty. Also, I would need to implement it from scratch, but I guess I'll have to do that anyway.

The hashcash proof-of-work scheme that bitcoin uses is vulnerable to Grover's quantum search algorithm, that can find a solution in the 2^76 search space for the current target difficulty in roughly sqrt(2^76) = 2^38 quantum hashing steps, for a 2^38 factor speedup.

Other proof-of-work schemes (e.g. finding cycles in graphs [1]) are not vulnerable to quantum speedup.

[1] https://github.com/tromp/cuckoo

[1] https://github.com/tromp/cuckoo

Non-Solution #10: Busy Beaver (64kb random instructions) https://denisbider.blogspot.com/2015/05/busybeaver-key-derivation-function.html Why: Has a public JS implementation, neat! Why not: Not well-documented, only available as a zip, or I could rip it out of this (abandoned?) repo https://github.com/denisbider/Atomic , apparently hasn't really been cross-checked by anyone it seems.