3 ms·
The problem of finding cycles in (pseudo randomly generated) graphs is actually one of the first examples of an asymmetric Proof-of-Work puzzle [1]. Asymmetry m
by tromp 2y ago
The problem of finding cycles in (pseudo randomly generated) graphs is actually one of the first examples of an asymmetric Proof-of-Work puzzle [1]. Asymmetry means that while finding a cycle takes a lot of memory and effort, a solution can be verified instantly.
Several of the suggested algorithms were in fact implemented in the various Cuckoo Cycle solvers [2]. But by maintaining directed paths, my union-find based algorithm did identify the entire cycle and not just the cycle completing edge [1] (implemented in [3]).
This algorithm suffers from three problems though. One, it only finds one among a set of interconnected cycles. Second, it's rather slow, being latency bound by the random memory accesses. Third, it uses much more memory than needed.
So repeatedly trimming edges with only one endpoint is a much faster approach. And for the random graphs that the PoW generates, it can be done using only 1 bit per edge to record if it's been trimmed.
Once sufficiently trimmed, a loop tracing algorithm (like [4] for the Cuckatoo Cycle variant) can find all remaining (simple) cycles.
[1] https://www.semanticscholar.org/paper/Cuckoo-Cycle%3A-A-Memory-Bound-Graph-Theoretic-Tromp/cce6bb06d77da858c547955a4336ced1de1a1091 https://www.semanticscholar.org/paper/Cuckoo-Cycle%3A-A-Memo...
[2] https://github.com/tromp/cuckoo https://github.com/tromp/cuckoo
[3] https://github.com/tromp/cuckoo/blob/master/src/cuckoo/cyclebase.hpp https://github.com/tromp/cuckoo/blob/master/src/cuckoo/cycle...
[4] https://github.com/tromp/cuckoo/blob/master/src/cuckatoo/graph.hpp https://github.com/tromp/cuckoo/blob/master/src/cuckatoo/gra...
- pxeger1 2y agoI initially took issue with "first asymmetric proof of work", thinking that in practice any NP-complete problem would surely be fine, even if we can’t prove that it can’t be solved quickly. But is it difficult to find NP-complete problems which can't also be quickly approximated? And I suppose it might also be hard to find NP-complete problems in a "Goldilocks zone" of difficulty to make for practical proofs of work, since their complexity increases so sharply.
- JohnKemeny 2y agoApproximation doesn't help, since you can require optimal solutions, but yes, it's very difficult to come up with hard instances. After all, you need to know the correct answer, so you can't just randomly generate instances. In addition, SAT solvers are ridiculously good these days.
- tromp 2y agoFor Proof-of-Work applications, at least in blockchains, you need puzzles that * can be pseudo randomly generated from a seed (usually the hash of a partial blockchain header) * have a known optimal solution method with a (nearly) constant running time that's at most about one second (for progress freeness this should be a small fraction of the target block time) NP-hard problems rarely satisfy both these constraints. Finding fixed length cycles in random (bipartite) graphs with billions of edges does.
- JohnKemeny 2y agoAfter trimming, you can also branch on edges: either it is in a cycle, in which you find one, otherwise you can remove it and further reduce the instance by trimming more edges.
- deleted 2y ago[deleted]