Mining Algorithm

From Riecoin

This page will explain the current algorithm used in rieMiner to mine blocks. Knowing well the algorithm also allows one to understand what the advanced options for the miner configuration do. At the end of this page, you should have a fair understanding of the Riecoin mining algorithm, and be able to study[1] or even improve the miner’s code if you are experienced with C++.

If you rather want to learn about the Riecoin protocol aspects (how the target and solution are encoded), read the PoW implementation guide. For things like how to compute earnings or normalize performance, read the Stella page. If you just want to know how to mine Riecoins, you can read the rieMiner solo or pooled mining guides.

Riecoin currently uses prime constellations for its PoW, these are what miners are looking for in order to validate transactions.

Prime constellations

A prime constellation of length , also called a prime -tuplet, or prime cluster, is a sequence of prime numbers , , such that the diameter , is in some sense the least possible[2].

Prime twins are notable examples of prime constellations, being consecutive prime numbers like , , or more generally with and being prime numbers.

For 3-tuplets, we could consider sequences of three consecutive prime numbers , however only satisfies such criterion[3], making this sort of tuples uninteresting. However, we can find many prime tuples of the form and , which are prime constellations of length 3 or prime triplets (and it is in this sense that we say that the diameter 6 is the smallest possible, as we saw that 4 was not enough).

And so on. For each , there are only a few possible prime constellation patterns, like the two above for .

Are there infinitely many prime constellations? We don’t know for any [4], and this is a well known unsolved problem, especially for the simplest case . The Twin Prime Conjecture asserts that it is true for , while the first Hardy-Littlewood conjecture (or -tuple conjecture) implies more generally that it is true for any .

Riecoin provides ways to test these conjectures by finding large prime constellations or contributing to research by finding new ideas while improving the Riecoin mining software. One of the most important unsolved mathematical problem, if not the most, is the Riemann's Hypothesis, and solving prime number related conjectures like the Hardy-Littlewood conjectures would be a great contribution to the resolution of this problem, and also for mathematics in general.

Primality testing

Regardless how we are trying to find prime constellations, we need a way to test whether a number is prime. There are many known algorithms for this, some proving for sure the primality and others with very small chance of being wrong.

In practice, exact algorithms are way too slow, so the Riecoin protocol uses 32 iterations of the Miller-Rabin primality test, while the current miner implementation uses the Fermat primality test as it seems to be the most efficient way to test, with a negligible probability of false positives.

The problem to solve

Words underlined below correspond to the different rieMiner options.

Starting from a given target number , find a prime constellation of the form with (and smaller than a certain limit specified by the Riecoin protocol). is a large number of currently hundreds of digits.

We call the base prime of the constellation and the Constellation Pattern (or offsets). Currently, the constellation must have a length of 7, so it has to be a tuple of the form or . Below, we will consider and omit it.

Ideas behind the algorithm

The simplest way to look for prime constellations is to do a brute force search and check the primality of the elements of for every starting from . However, primality testing is costly, so we would like to quickly eliminate many numbers that have no chance of being the base prime of a constellation, before doing the primality tests only on the remaining candidates.

To eliminate many cases where is composite, we can use a well known process, the sieve of Eratosthenes, by eliminating even numbers, then multiples of 3, and so on for every prime number.

One can notice that after sieving out multiples of , , …, , the pattern of eliminated numbers repeats every ( is the th primorial) starting from . For example, let’s eliminate multiples of 2 and 3 (), starting from a non-zero multiple of :

p2#*f +    1           5 |     7          11 |    13          17 |    19...
        x  o  x  x  x  o |  x  o  x  x  x  o |  x  o  x  x  x  o |  x  o...
offset  0  1  2  3  4  5 |  0  1  2  3  4  5 |  0  1  2  3  4  5 |  0  1...

The x represent eliminated numbers (for example, is a multiple of 2, 9 a multiple of 3) while the o represent the ones not eliminated. We see that the pattern xoxxxo repeats every . This can be exploited, as we can just establish the pattern, consider multiples of , and only check the numbers of the form , where corresponds to a "not eliminated" position in the pattern (for example, in the case , can be 1 or 5). We call these Primorial Offsets. Any other value is divisible by at least one number .

Example

Suppose that we want to find a prime triplet of the form , and the target is . We choose in this example . The first step is to find the offsets for this , and we start with nothing eliminated yet:

012345678901234567890123456789
oooooooooooooooooooooooooooooo

For each of these 30 numbers , we check not only if is divisible by , , or , but also if and are too.

012345678901234567890123456789
xxxxxxxxxxxoxxxxxoxxxxxxxxxxxx

For example, 19 itself is not divisible by 2, 3 or 5, but is, so it is eliminated here. After this, we see that only two numbers (11 and 17, or 6.7%) out of 30 from the pattern are remaining.

We calculate now the first multiple of after , which is , and start checking the candidates, which all have the form .

We find out that is the base prime of a prime constellation that has the required form.

Basis of the current implementation

In practice, as the primorial increases, the number of offsets will quickly become huge, and the current implementation does things a bit differently. We will like before choose an , and call it the Primorial Number (we will also note it ). However, rather than producing the whole sieve for this , we will just consider a single Primorial Offset , which is given and must not be eliminated if we had done the full sieving (using the base prime of a small constellation higher than the th prime number is a valid choice).

Only numbers of the form of are considered, with smaller than an arbitrary . Then, a basic sieve similar to the Eratosthenes one is done to eliminate numbers (which can be seen here as eliminating factors) whose at least one member of the constellation would be multiple of , then multiple of , and so on until the Prime Table Limit (the table of prime numbers up to this limit has to be generated in the miner initialization, hence the name).

Once the sieve done, the remaining numbers (candidates) are tested whether they are the base prime of a prime constellation. If it is the case, a solution was found, else the process restarts with a new target.

Main optimizations

Presieving

Checking whether is divisible by some prime number is relatively costly, and there are tricks to speed this up a lot.

One can notice that for any , if there is an such that is divisible by , then will also be divisible by for every integer . So we just have to find this and then eliminate factors of the form without having to do the division check.

is in fact a solution of the modular equation for .

If we require , it is unique and given by .

is the modular inverse of the primorial modulo p: .

The inverses for every of the prime table can be precomputed during the miner’s initialization, allowing fast computation of the during a presieve phase before the actual sieving.

Primorial factors array size

The primorial factors are in practice represented by an array of booleans, corresponding to whether the was eliminated. The size of this table can affect performance as it might fit into the L3 cache during the sieving phase if it is small enough. The rieMiner’s SieveBits option corresponds to this size.

Additionally, the array is reused several times until a new target is requested by cycling the incrementation, allowing higher factors and to reuse the presieve computations. How many times it is reused can be modified with the SieveIterations option.

Parallelizing with multiple primorial offsets

Actually, multiple Primorial Offsets can be entered in rieMiner, so several threads can work on their own sieve fairly independently for different values of . This seems to be a better solution than methods like splitting the primorial factors or the primes across the different threads. The number of sieves (each with a different ) to do in parallel is set by the SieveWorkers parameter.

Ideally, there should be just one thread (1 Sieve Worker) doing the sieve and all the others the primality testing as there is a slight performance loss when increasing the number of Sieve Workers, as well as an increased memory usage. However, there are some situations where checking candidates is done faster than their generation, leading to the CPU Underuse problem where many threads often end up doing nothing because there are not enough candidates to check.

This can happen with large Prime Table Limits as more time is spent on sieving and less candidates are generated (they are however more probable to be good ones). Lower Difficulties as well as having many CPU threads can also cause underuse as the primality tests are much faster. In these cases, having more Sieve Workers helps to produce more candidates.

Other optimizations

Some parts other than the primorial factor array are slightly modified in order to benefit from caching. Some computations for the presieving and verification can be accelerated with assembly optimizations using SSE or AVX/AVX2/AVX512 if available.

Notes and references

  1. You might want to take a look at the Light branch as advanced optimizations are removed, making the code easier to read.
  2. A more precise definition can be found here: Wolfram MathWorld: Prime Constellation
  3. It is easy to show that one number has to be divisible by 3.
  4. It is however known that this is true for prime numbers, or