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 practical use of the Riecoin Proof of Work (how the target and solution are encoded, which metrics make sense and how to use them,...), read the Stella page. If you just want to know how to mine Riecoins, see Mining Guide.

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.

Prime twins are notable examples of prime constellations, being consecutive prime numbers like $(3,5)$, $(17,19)$, or more generally $(n,n+2)$ with $n$ 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, 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$, 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$.

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.

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 $T$, find a prime constellation of the form $(n+o_{1},n+o_{2},...,n+o_{k})$ with $n\geq 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}\#=p_{1}\times p_{2}\times ...\times p_{m}$ ($p_{m}\#$ 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}\#=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, $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 $p_{2}\#$. This can be exploited, as we can just establish the pattern, consider multiples $p_{m}\#\times f\geq T$ of $p_{m}\#$, and only check the numbers of the form $p_{m}\#\times f+o$, where $0\leq o<p_{m}\#$ 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 (note that they have nothing to do with the constellation offsets $o_{1}$, $o_{2}$, etc.). Any other value is divisible by at least one number $a\leq p_{m}$.

Once we do it for some $m$, we can apply the technique recursively for higher values of $m$ and determine the offsets for these $m$ by reusing the previous ones. If we take now $m=3$, we know that the pattern will be $p_{3}\#=30$ periodic, but we don’t have to redo the sieving for all these values. Only doing so for the ones of the form $p_{2}\#\times i+1$ and $p_{2}\#\times i+5$ is enough as we already know that the others will be eliminated. In this case, we need to check for 1, 5, 7, 11, 17, 19, 23, 25, and 29, where 5 and 25 are eliminated, yielding the pattern for $m=3$.

This process, called the wheel sieve, can be adapted in order to not only eliminate cases where the base prime $c$ is composite, but also if it is the case for $c+o_{2}$, $c+o_{3}$, etc.

Example

Suppose that we want to find a prime triplet of the form $n+(0,2,6)$, and the target is $T=10000$. We take 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.

Now, we can consider $m=4$ and do the process again, but only with 11, 17, $30+11$, $30+17$, $2\times 30+11$, ..., $6\times 30+17$, by checking if the $i$, $i+2$ and $i+6$ are divisible by 7. Doing so will yield eight offsets out of $p_{4}\#=210$ (3.8%). And so on.

If we stop here, then we calculate the first multiple of $p_{m}\#$ after $T$, which is $T'=T+p_{m}\#-(T{\bmod {p}}_{m}\#)=10080$, and start checking the candidates, which all have the form $T'+p_{m}\#\times f+o$.

We find out that $10080+210\times 1+41=10331$ is the base prime of a prime constellation that has the required form.

Basis of the current implementation

In practice, the number of offsets will quickly become huge, and the current implementation does things a bit differently. It will just use a fixed Primorial Number $P$ instead of an increasing $m$, and a single given Primorial Offset $o$ (which must not be eliminated by the first step above for this $P$).

Only numbers of the form of $T_{f}=T'+p_{P}\#\times f+o>T$ are considered, with $f$ smaller than an arbitrary $f_{max}$. Then, a basic sieve 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'+p_{P}\#\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'+p_{P}\#\times f+o\equiv 0{\pmod {p}}$ for $f$.

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

$p_{P}\#^{-1}$ is the modular inverse of the primorial modulo p: $p_{P}\#^{-1}\times p_{P}\#=1{\pmod {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.