Implement the Cuckoo Cycle PoW about aeternity HOT 8 CLOSED

Let's make sure we can mine in parallel with everything else.

from aeternity.

I am extracting code from the the main miner in the Cuckoo Cycle code of John Tomp (https://github.com/tromp/cuckoo) and build an Erlang interface using NIFs.

from aeternity.

Cuckoo Cycle takes a string (which can be the hash of the block) and a nonce and creates a pair of siphash keys. These, together with the nonce, are used to create paths. The algorithm looks for 42-long cycles in these paths.

An attempt with a specific nonce value takes roughly 6 seconds on my laptop and it succeeds with a 2.2% chance. It results in an array of 42 integers representing the cycle found. Tromp suggested adding a difficulty by calculating the SHA265 hash of the solution and discarding the solution unless the hash is below the difficulty, just like with SHA256 PoW. (N. B. the success rate can be tuned by changing the node/edge ratio (1/2 in the suggested implementation) but this is nonlinear).

There are two methods verifying a solution:

• We can redo the calculation from the block hash and nonce. This takes about 6 seconds as it includes re-generating the original solution.
• Using the actual solution (array of 42 numbers) we can verify the solution by simple checking if it forms a cycle, this takes only 50-100 microseconds on my laptop. Though this is much faster, it requires storing the solution for aiding later verification.

from aeternity.

Do you mean storing the solution in the block header, together with the hash and nonce? @sennui

from aeternity.

I think, that storing the solution was one of the ideas behind democratizing miners and giving a slack to cheap mobile phones. (Jumping 42 pointers is way cheaper even than computing sha256)

@wagerlabs Yes, I would add it to the block and respectively include it in a header.
It would be an equivalent of current solution for, say, bitcoin: hash is a solution and its public.

If we want to make it fixed 42 numbers, we can drive the difficulty in a way mentioned by @akorosmezey (or we can assume from the very beginning that the length of the array can grow, which is fine too)

from aeternity.

from aeternity.

@sennui raised the question where the output of printf calls in the NIF goes. Unfortunately it goes to the console. I can remove most of them (the ones from my code) but there are still others from the original code. In order to remove them I need to fork the repo or just include the sources.

(A simple solution would be to redirect stdout to /dev/null for the duration of the call but this may affect other processes running parallel and in case of a crash we do not have the chance of undo the redirection.)

from aeternity.

PR #84 created that adds a call with default values to the API. @wagerlabs supported this idea.

from aeternity.