Interesting. I wonder how a sat solver would do with this problem.
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"