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.