Cuckoo Cycle replaces the hash with a 42 edge cycle in a bipartite graph

A proof of work where the work is finding a cycle

Cuckoo Cycle is presented in the README as the first graph-theoretic proof of work, and the most memory bound, yet with instant verification. The contrast it draws is with Hashcash, and the property it claims on top is immunity from the quantum speedup that Grover's search would give a hash-based scheme.

The mechanism is a graph search rather than a hash. A proof of work normally asks a miner to find a value whose hash meets a target. Here, the graph is defined by a keyed hash function, siphash-2-4, mapping an edge index and a partition side, either 0 or 1, to the edge endpoint on that side, and the miner has to find a cycle of a particular length in that graph. The header of the block supplies the key, so the graph changes for every block, and the proof is the cycle itself.

The specific shape is a node-pair cycle in a bipartite graph with N plus N nodes and N edges, where N is 2 to the n and n ranges from 10 up to 64. The term node-pair is the detail that makes the graph unusual. Consecutive edges are not incident on a single node as in an ordinary graph, they are incident on a node-pair, which is two nodes differing in the last bit only. Wherever the README says cycle, it means that node-pair cycle.

The Cuckatoo Cycle variation exists to simplify hardware. The README describes it as reducing ternary counters to plain bits, which removes a class of logic from the ASIC, and the result is described as the simplest known proof of work, with a 42 line complete specification in C and a 13 line mathematical description, less than half the size of the SHA256, Blake2b or SHA3 pseudocode used by Bitcoin, Equihash and ethash.

The repository is C++ with a `src/` directory, a `doc/` directory holding the specification, the mathematical description, the simplified solver write-up and the whitepaper, a `GPU.md` and a `GPU_tuning.md` for the GPU path, and a `private/` directory.

Verification costs 84 hashes

The asymmetry between finding and checking is the point of the design, and the README states the check as a short procedure.

You hash the header to derive the siphash key, then compute the 42 by 2 edge endpoints with 84 siphashes, and you are done if you come back to the starting edge only after traversing 42 node-pairs.

That is the entire verification. There is no scan of a large data structure, no lookup in a table that has to be reconstructed, and no memory access proportional to the graph size. A verifier holds the header, the key and a little state, and the cost of checking a proof is independent of how much work the miner did.

Finding is the opposite. The README is blunt that while trivially verifiable, finding a 42-cycle is far from trivial, requiring considerable resources and some luck, and it gives the probability: the odds of a random cuckoo graph having a cycle of length L are approximately one in L.

That one in 42 figure is the number a miner is actually working against, and it explains why the graph has to be large. A proof attempt on a small graph is cheap to check and cheap to find, so the graph size is what carries the difficulty, which is also why the section on dynamic sizing exists and why n ranges from 10 to 64 in the first place.

The README also makes the point that the work has to be real. A proof that could be found in sub-linear time would be worthless, because you could only compute a fraction of all edges, and the odds of all 42 edges of a cycle occurring in that fraction are astronomically small. So the algorithm is allowed to be slow, but it is not allowed to be lazy.

Lean mining and mean mining are two different bottlenecks

The repository ships two solvers, and the README describes them as a deliberate trade-off rather than as a fast one and a slow one.

The lean miner uses one bit per edge and one bit per node in one partition, or one bit per 2 to the k nodes with a linear slowdown. The README says the core of it, where more than 99 percent of the time is spent, is relatively simple, and that the miner is bottlenecked by accessing node bits completely at random, which makes it memory latency bound.

The mean miner is roughly four times faster and latency avoiding. It uses 33 bits per edge and is bottlenecked by bucket sorting, which makes it memory bandwidth bound.

The two bottlenecks are different in kind, and that matters for hardware. A latency bound workload punishes poor access patterns, and a bandwidth bound workload punishes insufficient throughput. The lean solver is the one that runs in a small amount of memory, the mean solver is the one that runs fast.

The cycle finding algorithm itself is described in the README, and the description is a lesson in where the cost is. The most efficient known way to find cycles in random bipartite graphs is to start by eliminating edges that are not part of any cycle, which is over 99.9 percent of edges, and this preprocessing phase is called edge trimming and actually takes the vast majority of the runtime. The lean implementation runs in time linear in N and keeps an N bit edge bitmap of potential cycle edges plus an N bit node bitmap of nodes with incident edges. The mean implementation instead maintains bucket sorted bins of edges in slightly more than N words and uses tiny node bitmaps within a bin to trim edges. After trimming, a standard backtracking graph traversal recognises the cycles and reports the ones of the right length.

The trade-off is explicit in the file names, `lean_miner.hpp` and `mean_miner.hpp`, with a GPU variant in `mean_miner.cu`.

The published timings, and the claim attached to them

The README states specific numbers, and a project that publishes numbers usually attaches a condition to them, so both are worth reading.

For a graph with 2 to the 29 edges on a 4GHz i7-4790K, a single proof attempt takes 10.5 seconds with the single threaded mean solver and uses 2200MB, or 3200MB with faster solution recovery. That reduces to 3.5 seconds with four threads, described as a three times speedup.

Using an order of magnitude less memory, 128MB, the lean solver takes 32.8 seconds per proof attempt. Its multi-threading performance is described as less impressive, with two threads still taking 25.6 seconds and four taking 20.5 seconds.

The author then makes four claims, and the phrasing is careful. That siphash-2-4 is a safe choice of underlying hash function, that these implementations are reasonably optimal, that trading off less memory for more running time incurs at least one order of magnitude extra slowdown, and that `mean_miner.cu` is a reasonably optimal GPU miner. The last one is stated as running about ten times faster on an NVIDIA 1080Ti than the CPU version.

The conditions are attached to the bounties rather than to the numbers. The bounties require n ranging over 27, 29 and 31, and thread counts of 1, 2, 4 and 8, and they assume a high end Intel Core i7 or Xeon and a recent gcc compiler with the flags used in the project's Makefile.

That is a useful thing to know before reading the timings. The figures describe one machine, one compiler and one flag set, and the machine named is an i7-4790K, which is not a current part.

Dynamic sizing turns the difficulty into a soft fork

The most interesting part of the design is the section on dynamic sizing, because it addresses a problem that hash-based proof of work handles badly.

Instead of fixing n, a proof of work system could allow miners to work on any graph size they like above a certain minimum, and the README notes that cycles in larger graphs are more valued as they take more effort to find. The proposed difficulty scaling for a graph with N equal to 2 to the n edges is 2 to the n plus one times n, which is the number of bits of siphash output that define the graph.

The upgrade argument then follows directly. Raising the minimum allowed graph size makes the set of new valid blocks a subset of the old valid blocks, so it is not a hard fork but a soft fork, and the README says it is easily deployed with majority miner support. The incentive is stated as well: miner manufacturers are motivated to support larger sizes because it is more future proof.

There is also an automatic trigger. A raise in the minimum graph size could be triggered automatically if, over the last so many blocks, on the scale of months, less than a certain fraction, a minority like a third or a quarter, were solved at that minimum size. The README says this locks in a new minimum which then activates within so many blocks, on the scale of weeks.

So the difficulty adjustment is a policy expressed in the protocol rather than a number in a configuration file, and it is designed so that a chain split on a parameter change is not possible in the way it would be for a hard fork.

The hardware angle follows too. The more efficient lean mining requires a lot of SRAM, which CPUs and GPUs lack and which is easy to implement in ASICs, either on a single chip or, for even larger graph sizes, across several chips, with the README noting that cuckatoo33 requires 1 GB of SRAM.

A bounty as an open research question

The README ends its argument with money, and the mechanism is unusual enough to describe.

There is a Linear Time-Memory Trade-Off Bounty of 10000 dollars for an open source implementation that uses at most N divided by k bits while finding 42-cycles up to ten k times slower, for any k of at least two. The framing is a negative result requirement, in other words, you are paid to show that the memory bound cannot be improved by more than a constant factor, and you have to publish the code.

The README then records that on April 11, 2025 the author received a submission from Stephan Theisgen to claim the bounty, and the passage describing the terms of the submission continues beyond what is quoted here.

That is a real and unusual pattern for a proof of work repository. Rather than asserting that the memory requirement is necessary, the author defines the claim precisely enough to be falsified, sets the conditions under which the claim is tested, and puts a sum behind it. The parameters are the ones already described, with n in 27, 29 and 31 and thread counts of 1, 2, 4 and 8, so a submission has to be evaluated on a defined grid rather than on a favourable machine.

The repository topics carry the same framing, with bounties, cuckoo-cycle, graph, proof-of-work and solver among the tags, and the README points to a blog article explaining Cuckoo Cycle, with an archived copy in case the original site is down, plus a whitepaper in the repository and a set of conference talks from 2019.

The licence is a custom one that GitHub cannot classify, with the terms in the `LICENSE.txt` file, and the repository has no GitHub releases.

Editorial conclusion

cuckoo fits a researcher or a protocol designer evaluating memory-hard proof of work who wants the specification, the reference solvers and the performance claims in one place, and who is prepared to read the C source to check them. Skip it if you need a drop-in mining binary, since the repository documents no build or run commands, or if your chain has already fixed its proof of work. Verify first the licence terms in the LICENSE file, since the project carries a custom one, and reproduce the published timings on your own hardware before relying on them.

Frequently asked questions

Official sources

1. Issues
2. README
3. tromp/cuckoo on GitHub