Cuckoo Cycle
Proof of Work(PoW) is one of the most important components of Nakamoto consensus. Although there are many criticisms about its energy-inefficiency, its simplicity and robustness were enough to draw world-wide attention. Ever since the advent of Bitcoin, virtually all cryptocurrencies are still under the influence of PoW. Some emerging consensus algorithms are even naming their components after it, like PoS or PoA.
PoW provides lots of nice features, but it doesn’t mean it’s a silver bullet for everything. One of the most notable risk scenarios is the so-called 51% attack. For a long time it has been thought to be just a hypothesis, but the situation has changed over time. Bitcoin and most of its derivatives are using cryptographic hash functions as its building block. Since those functions could be easily solved if you had a specialized hardware, more and more people started using highly optimized ASICs for mining cryptocurrencies. This is how the 51% attack became a realistic threat, which brought people together to discuss topics that addressed ASIC proof algorithms.
Cuckoo cycle
Cuckoo cycle is one of the most promising ASIC-resistant frameworks. It generates random bipartite graphs from a provided message, and tries to find whether a subgraph with required property exists or not. As you noticed, Cuckoo cycle selects a cycle as a target, but the algorithm itself is independent of this selection. The number of vertices and edges are decided by predetermined constants, and are carefully designed to be large enough so that memory requirement exceeds the capacity of a single chip. The edges for the graph are generated from a message and from the indices in a specified range, and it’s believed to be almost impossible to predict the outcome.
Proving the work for Cuckoo cycle is quite different from other algorithms. Usually, a single integer nonce is the only required proof for work, but Cuckoo cycle uses two kinds of nonces. Macro nonce is the one that corresponds to nonce in other PoWs, and micro nonces are the seed values for graph edges. By providing both values, a verifier can fully determine whether the proof is correct, with just a tiny bit of resources compared to those required by a prover. It completely satisfies the desired property of a good PoW, summarized as “hard to prove, but easy to verify.”
Is it really ASIC proof?
Memory devices are slow. As an engineer, we’ve always wished for blazingly fast memory access, but typical products in the market are far from great, so we have no choice than to add optimizations to mitigate bottlenecks. The situation is not that different in the ASIC world where the interface latency is the most important factor in determining overall speed of resulting devices. Even with the state-of-art technologies, read/write memory speed is still slower than other computing operations by order of magnitudes.
The fact that the memory bound functions are slow is a pain to most of the engineers, but it could be perfect for solutions that need to intentionally suppress computation speeds. This led to the use of memory bound functions in PoW, and many recent formulations of ASIC proof algorithms make use of this aspect. Important thing to note here is that memory hard loop alone is not enough to slow down ASICs. Generally, to harden ASIC resistance, 1) memory access should be unpredictable, 2) required computation between two memory accesses should be close to zero.
Cuckoo cycle is designed to match all of these requirements. Memory usage of a single computation is too high that it can’t be embedded in a single chip. Graph edges are generated with siphash, which results in unpredictable graph access. Also, siphash is fast enough in most devices, so required computation between two memory operations is neglectable. The most remarkable thing is that by simply adjusting several parameters, it’s easy to get desired memory usage and difficulty. Several recommendations are listed on this whitepaper, but you’re free to choose any values you want!
Of course, some might argue that it’s not “proven” to be ASIC proof, and I agree with that. However, I am confident that people that question the technology will change their minds if they have a look at the main repository. It’s already being used by big players like MimbleWimble, and supported by famous mining parties like Genesis mining or Claymore. Also, there’s a large bounty for finding algorithms faster than the existing ones, though only few people have succeeded to provide them. It’s been over a year after the latest algorithm update, so it can be considered to be in a stable stage.
In CodeChain, we decided to include Cuckoo cycle based PoW as one of the built-in consensus rules. We reimplemented the algorithm from scratch, and the test results look quite good so far.
ASIC resistance is one of the hottest keywords in many blockchain communities. We always try to track fresh new issues as quick as possible, and introduce state-of-art technologies to deal with them. Cuckoo cycle is one of the cool technologies we are adopting in our project, but CodeChain has much more to offer. Feel free to look around our blog, and we hope our articles give you good insights for better products.
