# The Mining Algorithm

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 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's page which contains solo and pooled mining guides as well as more advanced ones.

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 $k$*, also called a *prime $k$-tuplet*, or *prime cluster*, is a sequence of $k$ prime numbers $({n}_{1},{n}_{2},...,{n}_{k})$, ${n}_{1}<{n}_{2}<...<{n}_{k}$, such that the diameter ${n}_{k}-{n}_{1}$, is in some sense the least possible^{[1]}.

Prime twins are notable examples of prime constellations, being consecutive prime numbers like $(3,5)$, $(17,19)$, or more generally $(n,n+2)$ with $k$ and $n+2$ being prime numbers.

For 3-tuplets, we could consider sequences of three consecutive prime numbers $(n,n+2,n+4)$, however only $(3,5,7)$ satisfies such criterion^{[2]}, making this sort of tuples uninteresting. However, we can find many prime tuples of the form $(n,n+2,n+6)$ and $(n,n+4,n+6)$, 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 $k$, there are only a few possible prime constellation *patterns*, like the two above for $k=3$.

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

While it is more a proof of concept that PoW can be used for useful scientific calculation than actually dedicated to these problems, Riecoin does 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, certain algorithms are way too slow, and Riecoin Core currently makes the checks with the GMP's `mpz_probab_prime_p`

and `reps = 32`

. 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

Highlighted terms below correspond to the different rieMiner options.

Starting from a given target number $T$, find a prime constellation of the form $(n+{o}_{1},n+{o}_{2},...,n+{o}_{k})$ with $n\ge T$ (and smaller than a certain limit specified by the Riecoin protocol). $T$ is a large number of currently hundreds of digits.

We call $n$ the base prime of the constellation and $({o}_{1},{o}_{2},...,{o}_{k})$ the __Constellation Pattern__ (or offsets). Currently, the constellation must have a length of 7, so it has to be a tuple of the form $n+(0,2,6,8,12,18,20)$ or $n+(0,2,8,12,14,18,20)$. Below, we will consider ${o}_{1}=0$ 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 $(c,c+{o}_{2},...,c+{o}_{k})$ for every $c$ starting from $T$. However, primality testing is costly, so we would like to quickly eliminate many numbers $c$ 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 $c$ 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 ${p}_{1}=2$, ${p}_{2}=3$, …, ${p}_{m}$, the pattern of eliminated numbers repeats every ${p}_{m}\mathrm{\#}={p}_{1}\times {p}_{2}\times ...\times {p}_{m}$ (${p}_{m}\mathrm{\#}$ is the $m$*th primorial*) starting from ${p}_{m}+1$. For example, let’s eliminate multiples of 2 and 3 ($m=2$), starting from a *non-zero* multiple of ${p}_{2}\mathrm{\#}=3\mathrm{\#}=6$:

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, $8={p}_{2}\mathrm{\#}\times 1+2$ 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 ${p}_{2}\mathrm{\#}$. This can be exploited, as we can just establish the pattern, consider multiples ${p}_{m}\mathrm{\#}\times f\ge T$ of ${p}_{m}\mathrm{\#}$, and only check the numbers of the form ${p}_{m}\mathrm{\#}\times f+o$, where $0\le o<{p}_{m}\mathrm{\#}$ corresponds to a "not eliminated" position in the pattern (for example, in the case $m=2$, $o$ can be 1 or 5). We call these $o$ __Primorial Offsets__. Any other value is divisible by at least one number $a\le {p}_{m}$.

### Example

Suppose that we want to find a prime triplet of the form $n+(0,2,6)$, and the target is $T=10000$. We choose in this example $m=3$. The first step is to find the offsets $o$ for this $m$, and we start with nothing eliminated yet:

012345678901234567890123456789 oooooooooooooooooooooooooooooo

For each of these 30 numbers $i$, we check not only if $i$ is divisible by ${p}_{1}=2$, ${p}_{2}=3$, or ${p}_{3}=5$, but also if $i+2$ and $i+6$ are too.

012345678901234567890123456789 xxxxxxxxxxxoxxxxxoxxxxxxxxxxxx

For example, 19 itself is not divisible by 2, 3 or 5, but $19+2$ 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 now calculate the first multiple of ${p}_{m}\mathrm{\#}$ after $T$, which is ${T}^{\prime}=T+{p}_{m}\mathrm{\#}-(T{modp}_{m}\mathrm{\#})=10020$, and start checking the candidates, which all have the form ${T}^{\prime}+{p}_{m}\mathrm{\#}\times f+o$.

We find out that $10020+30\times 10+11=10331$ 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 explode, and the current implementation does things a bit differently. We will like before choose an $m$, and call it the __Primorial Number__ (we will also note it $P$. However, rather than producing the whole sieve for this $m=P$, we will just consider a single __Primorial Offset__ $o$, 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 $P$th prime number ${p}_{P}$ is a valid choice).

Only numbers of the form of ${T}_{f}={T}^{\prime}+{p}_{P}\mathrm{\#}\times f+o>T$ are considered, with $f$ smaller than an arbitrary ${f}_{\mathrm{max}}$. 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 ${p}_{P+1}$, then multiple of ${p}_{P+2}$, 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 ${T}_{f}={T}^{\prime}+{p}_{P}\mathrm{\#}\times f+o$ is divisible by some prime number $p$ is relatively costly, and there are tricks to speed this up a lot.

One can notice that for any $p$, if there is an ${f}_{p}$ such that ${T}_{{f}_{p}}$ is divisible by $p$, then ${T}_{p\times i+{f}_{p}}$ will also be divisible by $p$ for every integer $i$. So we just have to find this ${f}_{p}$ and then eliminate factors of the form $p\times i+{f}_{p}$ without having to do the division check.

${f}_{p}$ is in fact a solution of the modular equation ${T}_{f}={T}^{\prime}+{p}_{P}\mathrm{\#}\times f+o\equiv 0\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}p)$ for $f$.

If we require $$, it is unique and given by ${f}_{p}=((p-(({T}^{\prime}+o)modp))\times {p}_{P}{\mathrm{\#}}^{-1})modp$.

${p}_{P}{\mathrm{\#}}^{-1}$ is the modular inverse of the primorial modulo p: ${p}_{P}{\mathrm{\#}}^{-1}\times {p}_{P}\mathrm{\#}=1\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}p)$.

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

### Primorial factors array size

The primorial factors $f$ are in practice represented by an array of booleans, corresponding to whether the $f$ 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 $o$. 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 $o$) 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

- A more precise definition can be found here: Wolfram MathWorld: Prime Constellation
- It is easy to show that one number has to be divisible by 3.
- It is however known that this is true for prime numbers, or $k=1$.