Quote from: Come-from-Beyond on December 21, 2015, 07:13:20 PM

Quote from: tromp on December 21, 2015, 07:03:41 PM

Cuckoo Cycle proofs are instantly verifiable, just like Bitcoin nonces.

Bitcoin nonces are not verifiable instantly, but they require only very little memory. How much memory is required to verify Cuckoo Cycle nonce?

336 bytes.

Quoting from https://github.com/tromp/cuckoo:

"Proofs take the form of a length 42 cycle in a bipartite graph with N nodes and N/2 edges, with N scalable from millions to billions and beyond.

This makes verification trivial: compute the 42x2 edge endpoints with one initialising sha256 and 84 very cheap siphash-2-4 hashes, check that each endpoint occurs twice, and that you come back to the starting point only after traversing 42 edges.
A final sha256 hash on the sorted 42 nonces can check whether the 42-cycle meets a difficulty target.

This is implemented in just 157 lines of C code (files src/cuckoo.h and src/cuckoo.c).

From this point of view, Cuckoo Cycle is a very simple PoW, requiring hardly any code, time, or memory to verify."

The verify() function uses 2*42 ints of memory.
For graph sizes up to 2^32, those can be 32-bit ints, so that's 336 bytes.