The PoW Implementation

This page will explain how the Riecoin's Proof of Work Stella is implemented.

Generalities

A block is solved by finding a result that satisfies criteria defined by the PoW version. As of the second hard fork, the current version is 1, detailed below. For now, the PoW results are prime constellations, but nothing prevents the project from switching to or supporting something else in the future in order to contribute to other areas of mathematics or even other sciences.

Initially, a miner is given the block header (or the information to reconstruct it) of the current block to solve. It has a length of 112 bytes and contains various fields (see the Protocol page), in particular the difficulty (32 bits, often called nBits) and the result (256 bits, often called nOffset) fields. The miner has to fill the result field with the PoW solution.

The previous version was -1 (also Prime Constellations, similar to 1 but without some enhancements and with some caveats like unnecessary bit swaps), and the Riecoin Core source code may be inspected for details.

PoW Version 1

PoW Problem, Target

Given the target $T=2^{\lfloor <!--\; \lfloor \; -->D\rfloor <!--\; \rfloor \; -->}+L\times <!--\; \times \; -->2^{\lfloor <!--\; \lfloor \; -->D\rfloor <!--\; \rfloor \; -->-<!--\; -\; -->8}+H\times <!--\; \times \; -->2^{\lfloor <!--\; \lfloor \; -->D\rfloor <!--\; \rfloor \; -->-<!--\; -\; -->264}$, find an $X<2^{\lfloor <!--\; \lfloor \; -->D\rfloor <!--\; \rfloor \; -->-<!--\; -\; -->264}$ such that $T+X$ is the base number of a prime constellation of length 7 (or 5 in Testnet).

$D$ is the difficulty and is encoded in the nBits field of the block header. It can take $\frac{1}{256}$ fractions. $2^D$ approximates the target, which then has $\lfloor <!--\; \lfloor \; -->D\rfloor <!--\; \rfloor \; -->+1$ bits, so do the prime numbers. The minimum difficulty is 600.

The nBits field is using a simple fixed point number consisting in 24 bits before the decimal points and 8 after. This allows difficulties $D$ up to $2^{24}$ (about ${10}^{39}$ times harder to solve such blocks than the ones as of 2024 with the current algorithm), with constant $\frac{1}{256}$ precision.

The Target $T$ can be contructed as follows.

T = 1 . L (8 bits) . H (256 bits) . 00 ... 0 (padding with D - 264 zeros)

It starts with the leading one. The next 8 bits $L$ are such that $T\approx <!--\; \approx \; -->2^D$ after padding the appropriate number of zeros after $H$. If $D_f=\text{nBits}mod256$, these bits (if we view them as an 8 bits integer) are given by

$$L=\text{round}(2^{8+\frac{D_f}{2^8}}-<!--\; -\; -->2^8)$$

To avoid possible issues with floating point numbers, this formula is implemented as a third degree polynomial that gives the same values $L$ for every possible $D_f$,

$$L=\lfloor <!--\; \lfloor \; -->\frac{10{D_f}^3+7383{D_f}^2+5840720D_f+3997440}{2^{23}}\rfloor <!--\; \rfloor \; -->$$

$H$ is the Sha256² hash of the block header, without the nOffset, interpreted as a 256 bits number. This is to ensure that every prime constellation is unique and in a lesser extent to prevent someone from precalculating Prime Constellations in order to solve Blocks instantly later (for a third Hard Fork, it would be nice to debate whether the hash could be securely cut to something like 128 bits to allow larger Primorial Numbers). Finally, $D-264$ trailing zeros are added so $T\approx <!--\; \approx \; -->2^D$.

PoW Solution

The nOffset field uses an encoding suitable to the current algorithm. Rather than just storing the offset $X$ in raw, it is encoded in three parts, the Primorial Number $P$, the Primorial Factor $f$, and the Primorial Offset $o$, and computed as follows:

$$X=p_P\mathrm{\#<!--\; \#\; -->}-<!--\; -\; -->(T{modp}_P\mathrm{\#<!--\; \#\; -->})+f\times <!--\; \times \; -->p_P\mathrm{\#<!--\; \#\; -->}+o$$

$p_P\mathrm{\#<!--\; \#\; -->}$ is the product of the first $P$ primes (primorial), the $P$th included. For example, $p_3\mathrm{\#<!--\; \#\; -->}=2\times <!--\; \times \; -->3\times <!--\; \times \; -->5=30$.

Respectively 16, 128 and 96 bits are used to encode them. The latest bit is always set to 0 (in order to distinguish from version -1 results, which always had 1 as the latest bit), and the remaining 15 bits can currently be considered as the encoding of the PoW Version 1, though this may change in the future, and must be set to 0 except the latest one to 1. In summary, the nOffset decomposes as

 n  |   Bits  |  Bytes  |
16  | 240-255 | [30-31] | Primorial Number
128 | 112-239 | [14-29] | Primorial Factor
96  |  16-111 |  [2-13] | Primorial Offset
15  |   1- 15 |  [0- 1] | Reserved/Version (for now, 000000000000001)
1   |   0     |  [0]    | Always 0

Reading the page explaining the mining algorithm will also help making sense of this encoding.

Solution Check

The Riecoin protocol does not formally check the numbers with true primality testing algorithms since it would be too slow, but rather use probabilistic tests, that should nevertheless be good enough in practice. Riecoin Core currently makes the checks with the GMP's mpz_probab_prime_p and reps = 32. An interesting question would be whether a probabilistic test could actually turn out to be a definite one when we are testing Prime Constellations (for example if for a given pattern or even any, there are bases in the Fermat or Miller-Rabin Tests in which it is impossible to have a "constellation" of strong pseudoprimes)...