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

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

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

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

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 ${\displaystyle T}$, find a prime constellation of the form ${\displaystyle (n+o_{1},n+o_{2},...,n+o_{k})}$ with ${\displaystyle n\geq T}$ (and smaller than a certain limit specified by the Riecoin protocol). ${\displaystyle T}$ is a large number of currently hundreds of digits.

We call ${\displaystyle n}$ the base prime of the constellation and ${\displaystyle (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 ${\displaystyle n+(0,2,6,8,12,18,20)}$ or ${\displaystyle n+(0,2,8,12,14,18,20)}$. Below, we will consider ${\displaystyle 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 ${\displaystyle (c,c+o_{2},...,c+o_{k})}$ for every ${\displaystyle c}$ starting from ${\displaystyle T}$. However, primality testing is costly, so we would like to quickly eliminate many numbers ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle p_{1}=2}$, ${\displaystyle p_{2}=3}$, …, ${\displaystyle p_{m}}$, the pattern of eliminated numbers repeats every ${\displaystyle p_{m}\#=p_{1}\times p_{2}\times ...\times p_{m}}$ (${\displaystyle p_{m}\#}$ is the ${\displaystyle m}$th primorial) starting from ${\displaystyle p_{m}+1}$. For example, let’s eliminate multiples of 2 and 3 (${\displaystyle m=2}$), starting from a non-zero multiple of ${\displaystyle p_{2}\#=3\#=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, ${\displaystyle 8=p_{2}\#\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 ${\displaystyle p_{2}\#}$. This can be exploited, as we can just establish the pattern, consider multiples ${\displaystyle p_{m}\#\times f\geq T}$ of ${\displaystyle p_{m}\#}$, and only check the numbers of the form ${\displaystyle p_{m}\#\times f+o}$, where ${\displaystyle 0\leq o corresponds to a "not eliminated" position in the pattern (for example, in the case ${\displaystyle m=2}$, ${\displaystyle o}$ can be 1 or 5). We call these ${\displaystyle o}$ Primorial Offsets. Any other value is divisible by at least one number ${\displaystyle a\leq p_{m}}$.

### Example

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

012345678901234567890123456789
oooooooooooooooooooooooooooooo


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

012345678901234567890123456789
xxxxxxxxxxxoxxxxxoxxxxxxxxxxxx


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

We find out that ${\displaystyle 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 become huge, and the current implementation does things a bit differently. We will like before choose an ${\displaystyle m}$, and call it the Primorial Number (we will also note it ${\displaystyle P}$). However, rather than producing the whole sieve for this ${\displaystyle m=P}$, we will just consider a single Primorial Offset ${\displaystyle 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 ${\displaystyle P}$th prime number ${\displaystyle p_{P}}$ is a valid choice).

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

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

${\displaystyle f_{p}}$ is in fact a solution of the modular equation ${\displaystyle T_{f}=T'+p_{P}\#\times f+o\equiv 0{\pmod {p}}}$ for ${\displaystyle f}$.

If we require ${\displaystyle 0\leq f, it is unique and given by ${\displaystyle f_{p}=((p-((T'+o){\bmod {p}}))\times p_{P}\#^{-1}){\bmod {p}}}$.

${\displaystyle p_{P}\#^{-1}}$ is the modular inverse of the primorial modulo p: ${\displaystyle p_{P}\#^{-1}\times p_{P}\#=1{\pmod {p}}}$.

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

### Primorial factors array size

The primorial factors ${\displaystyle f}$ are in practice represented by an array of booleans, corresponding to whether the ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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

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 ${\displaystyle k=1}$