For our first Q&A session, we will be hosting Mr. John Tromp — the creator of Cuckoo Cycle Proof-of-Work algorithm.

Time for the Q&A session will be 9:00 PM Amsterdam time (7:00 PM UTC / 3:00 PM EST / 12:00 PM PST) on 24.08.2017 and it will take place at r/aeternity.

If you have any questions about Cuckoo cycle and mining you are welcome to participate at the Q&A session.

The usual community rules will apply.

If you have questions but are unable to participate, please communicate them to any of the moderators in advance, and they will ask the questions for you.

Short introduction to John Tromp

Board Games and Artificial Intelligence, Algorithms, Complexity, Algorithmic Information Theory, Distributed Computing, Computational biology, and what not. Recently he has been designing a new Proof-of-Work (PoW) system called “Cuckoo Cycle”. John is currently advising the æternity team on the possible integration of the “Cuckoo Cycle” mining algorithm in æternity’s PoW. Some of his less recent research has focused on the Combinatorics of Go, specifically counting the number of legal positions. He has also been playing with a Lambda Calculus based on an utterly simple computer model. His Erdös number is 2, courtesy of Jeffrey Shallit, his favorite CS lecturer, who co-authored papers with both him and Erdös. A while ago, he also analyzed the complexity of OriMazes.

A Go addict and having learned the game at the age of 24, John has now reached the rank of 2 dan, hoping to one day make it to 3 dan. His personal Go page discusses logical rules and provides some tutorials. John used to be a Chess fan and is still occasionally tempted to play some blitz games. He also enjoys Risk even if it is difficult to find 2 or 3 playing partners.
When he was a PhD student under the supervision of Paul Vitányi, John thought of doing a thesis on the game of connect-4. Instead, he ended up working on distributed computing problems, and many other topics in PhD research, which resulted in this thesis.

He is fascinated by recumbent bikes since the early 90s. You can check out this picture of a Green Machine, a design concept that in 2005 was finally revived in a slightly different form. Since 2000, John is the proud owner of an Optima Condor and got himslef listed on Nederlandse Ligfietser Thuispagina’s.
He likes to think of cute algorithms (or take such created by other people) and write them in the absolute minimum amount of code, greatly obfuscating them in the process. See his programming pearls.

The Cuckoo Cycle

The most recent example of the new generation of PoW algorithms is Cuckoo Cycle PoW, which was presented at the BITCOIN’ 2015 workshop. The whitepaper can be found at GitHub, which also hosts various implementations, as well as bounties for improving on them.

In Cuckoo Cycle, proofs take the form of a length 42 cycle (loop) in a large random graph defined by some nonce. Imagine two countries, each with a billion cities, and imagine picking a billion border crossing roads that connect a random city in one country to a random city in the other country (the PoW actually uses a cheaply computed hash function to map the nonce, road number, and country to a city). We are asked if there is cycle of 42 roads visiting 42 different cities. If someone hands you a nonce and 42 road numbers, it is indeed easy to verify, requiring negligible time and memory.
But finding such a cycle is no easy task. Note however, that a city that connects to one road only cannot be part of the solution, nor can that road. David Andersen pointed out that such dead-end roads can be repeatedly eliminated, using one bit of memory per road to remember if that road is useful, and two bits per city to count if there are zero, one, or multiple useful roads to that city.

This process of computing counts for cities, and marking roads that lead to a city with count one as not useful, is the essence of Cuckoo Cycle mining and accounts for about 98% of the effort. It results in billions of random global memory accesses for reading and writing the counters. Consequently, about 2/3 of the runtime is memory latency, making this a low-power algorithm that keeps computers running cool.

After a sufficient number of counting and marking rounds, so few useful roads remain that another algorithm, inspired by Cuckoo Hashing, can quickly identify cycles (re-using the memory for the no longer needed counters). 
Cuckoo Cycle has some downsides as well. First, proofs are large and will roughly triple the size of block headers. Second, it is very slow, taking the better part of a minute on a high end CPU (or GPU, which offer roughly the same speed) to look for a cycle among a billion roads.

In order to give slower CPUs a (somewhat) fair chance to win, the block interval should be much longer than a single proof attempt, so the amount of memory Cuckoo Cycle can use is constrained by the choice of block interval length.

These seem like reasonable compromises for an instantly verifiable memory bound PoW that is unique in being dominated by latency rather than computation. In that sense, mining Cuckoo Cycle is a form of ASIC mining where DRAM chips serve the application of randomly reading and writing billions of bits.

When even phones charging overnight can mine without orders of magnitude loss in efficiency, not with a mindset of profitability but of playing the lottery, the mining hardware landscape will see vast expansion, benefiting adoption as well as decentralization.

More information

You can get more details on Cuckoo Cycle by reading the blog post below, prepared in collaboration with John.

https://blog.aeternity.com/cuckoo-cycle-memory-bandwidth-bound-pow-mining-9aa5695a4c94

You can look at the Q&A session at Reddit with John Tromp here:

Towards a more egalitarian PoW using Cuckoo cycle algorithm – Q&A session with John Tromp – creator of Cuckoo cycle
byu/snasps inAeternity

You can reach us in æternity’s communication channels:

GitHub | Reddit | Telegram | Twitter | Facebook | Mail