Qitmeer Cuckoo Cycle Algorithm Overview

Cuckoo Cycle Algorithm Overview

  • Find a cycle with specific length in a bipartite graph with N nodes and M edges;
    • Bipartite graph uses hashtable for storage where one side is odd nodes and the other is even nodes;
    • Two important characters:
      • The difficulties of searching for the requested cycle increased when the graph size is bigger;
      • The probability of the cycle will increase when the ration of M/N increases.
    • The edges are computed by SIPHASH whose key is the header of the hash.
    • “Proof” is a set of nonces which is used to compute a 42-length cycle. The result of PoW can be easily verified by other nodes.

Edge Formation

1

  1. Assume that there is a graph with 64 nodes
  2. Form 32 edges randomly;
  3. U = SIPHASH(headerHash, 2 nonce) mod 31
    V = SIPHASH(headerHash, 2
    nonce+1) mod 31

Edge Trimming

2

  1. There’s one special edge we called leaf edges which is the node of degree one
  2. Leaf edges can never be part of a cycle;
  3. The complexity of finding cycle will decrease by edge trimming.

Find Cycle

3

  1. After edge trimming, we will be able to find the cycle which means end of cuckoo cycle computing;
  2. Do we complete PoW?

Difficulty control

4

  1. The ratio M/N determines a base level of difficulty. For crypto currencies, where difficulty must scale in precisely controlled manner across a large range, adjusting the number of edges is not suitable. The implementation of default M/N=1/2 gives a solution probability of roughly 2.2% while the average number of cycles found increases slowing with size.
  2. In practical, some will increase the difficulty akin to Bitcoin hash that the hash of cycle nonces shall be computed by hash function and then compared with the target difficulty.

Miner

PoW Mining Principle

Proof-of-work, by hash the transaction data and nonce, the result shall satisfy the target value. Once the result is computed, the node will broadcast to the whole network to create a new block transaction. All nodes in the network will received the block and start to verify immediately.

Target Hash
0001fd98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965

Header Data
hello qitmeer + nonce (change from 0,1<<32)

Find the nonce which can compute to the result that make blake2b (Header Data) is lower than the target hash


All Hash Functions have the same character which is any change to the block data (such as the nonce) will make the block hash completely different.

0001fd98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965

The number of times of trying to compute is hexadecimal with 64 bits where each number changes from (0-f) to make the value below the target. Therefore, the first three numbers are all 0. As the randomness of hash function, each number can be considered as independent event. The probability of the first 0 is 1/2^4, the second is 1/2^4, so as the third, which means that the probability of getting first three 0 at same time is 1/2^4* 1/2^4* 1/2^4 = 1/2^12. If the fourth number is 0, then we get the result that satisfy the requirement which probability will be 1/2^16.

Mining devices will hash 2^16 nonces to get the right answer depending on probability. The more times of computing, the higher of the probability

The speed of hash various from mining devices.Each device hashes at a different rate per second, which tells you how long this device needs to get the right answer based on the current difficulty. The difficulty will be adjusted according to the speed of producing new block.

Why GPU mining, not CPU mining – from a technical view

GPU is more suitable for mining. From the example of just the principle, the value of nonce is calculated from 0 to 1<<32 power, CPU calculation can open many threads, respectively from the calculation of different nonce segment, but the open thread is limited, and open thread cost resources, synchronization calculation is not so good.

The GPU is designed for parallel flow computing, for example: currently, most GPU has 256 working groups, each working group has nearly 2^27 power of the computing unit, which is equivalent to each time can be calculated at the same time 2^27 * 256 nonce, the time to get the answer is greatly reduced.

That is to say that CPU can mine but with low probabilities under the same invested cost compared with GPU.

However, Cuckoo mining adopts both GPU and CPU where GPU will produce lots of edges and trim leaf edges very fast and CPU will compute on the rest of edges to find the cycle by depth-first algorithm. Finally, hash the cycle nonce to verify the result.

Hence, it will costly to manufacture ASIC mining machine which should be equipped with the GPU parallel computing power and CPU computing power. GPU mining machine matches the requirements.

Qitmeer Miner Principles


According to above mentioned, input data will change the hash result. Miner can customize the setting if they don’t care about the configuration so that miners will not repeat work to ensure the fairness to a certain extent. If everyone uses the same software with the same header, then the probability will be extremely low compared with large computing power machine. However, the more times of hash, the higher of the probability.

Qitmeer Basic Principles

  1. Get one GPU device for mining
  2. Start the coroutine for monitoring the latest task, GBT
  3. Start the coroutine for monitoring the submission of tasks
  4. Start the coroutine for miners’ submission statistics
  5. Keep mining and try to find the nonce
  6. Invoke GPU for parallel computing with opencl sdk common interface to transmit data and computational logic.

Double blake2b kernel Code example
https://github.com/HalalChain/qitmeer-miner/blob/master/kernel/blake2bdkernel.go

Cuckaroo kernel Code example
https://github.com/HalalChain/qitmeer-miner/blob/master/kernel/blake2bdkernel.go

Cuckaroo kernel find cycle example
https://github.com/HalalChain/qitmeer-miner/blob/master/cuckoo/graph.go

Docker-test-qitmeer

Online AMA video: 腾讯视频

1 Like