Protocol/Proof of Work

This page will explain how the Riecoin's Proof of Work is implemented. You might also want to read the explanation of the mining algorithm, and the Stella page.

Generalities

A block is solved by finding a result that satisfies criteria defined by the PoW version. As of the second hard fork, two versions exist, -1 and 1, explained 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.

Version -1

The original PoW Version. The problem to solve is

Given the target $T=2^{D-1}+H'\times 2^{D-265}$, find an $X<2^{D-265}$ such that $T+X$ is the base number of a prime constellation of length 6 (or 4 in Testnet).

$D$ is the difficulty and is encoded in the nBits field of the block header. It uses the Bitcoin’s Compact encoding, which is a custom floating point number format allowing difficulties up to $2^{224}$. $D$ represents the number of digits of a prime number in base 2. The minimum difficulty is 304 and always an integer (the fractional part of the decoded Compact is discarded and negative values are rejected).

The hash of the block header is computed, without the nOffset. Note that due to programming errors, the nBits and nTime fields must be swapped before hashing, and the bit order is inverted (not just the endianness). Then the hash is interpreted as a 256 bits integer $H'$.

The target can be constructed in binary as follows (the dot being here the concatenation operator).

T = 1 . 00000000 (8 zeros) . H' (256 bits) . 00 ... 0 (padding with D - 265 zeros)

Once a miner found an $X$, it encodes it in the nOffset field, which is simply $X$ in binary. This means that $X$ must also be less than $2^{256}$.

The Riecoin protocol uses 32 iterations of the Miller-Rabin primality test to check the numbers of a prime constellation. A composite number has ${\frac {1}{2^{64}}}$ chance to pass the test, but this is only for one Riecoin node and such block will certainly be orphaned by the next node as it would have to pass again the test with different seeds, and so on.

Version 1

The PoW Version after the second hard fork. The problem to solve is essentially the same as version -1, but the implementation differs vastly.

Given the target $T=2^{\lfloor D\rfloor }+L\times 2^{\lfloor D\rfloor -8}+H\times 2^{\lfloor D\rfloor -264}$, find an $X<2^{\lfloor D\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 again encoded in the nBits field of the block header. However, the encoding is different, and $D$ can now take ${\frac {1}{256}}$ fractions. $2^{D}$ approximates the target (before, it was actually $2^{D-1}$), and the number of digits of a prime number is given by $\lfloor D\rfloor +1$ and not $\lfloor D\rfloor$. The minimum difficulty is now 600.

The nBits field is now 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}$ with constant ${\frac {1}{256}}$ precision, which might seem little when comparing with $2^{224}$, but should nonetheless be enough as it is still about $10^{40}$ times more difficult to find such blocks than the ones as of 2020, so there is plenty of time to anticipate a new PoW upgrade if needed. Rational difficulties are needed to support small changes for a difficulty adjustment algorithm that updates every block, and they also make the targets more diverse (rather than always having something starting with 100000000).

The construction of the Target $T$ is done similarly to the binary construction from PoW Version -1, with some differences. Instead of having the 8 zeros between the leading 1 and the hash, it will be filled with 8 leading bits such that $T\approx 2^{D}$. If $D_{f}={\text{nBits}}{\bmod {2}}56$, these bits (if we view them as an 8 bits integer $L$) 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 {\frac {10{D_{f}}^{3}+7383{D_{f}}^{2}+5840720D_{f}+3997440}{2^{23}}}\rfloor$

In addition to this change,

• The nBits and nTime fields must no longer be swapped before hashing;
• The hash bit order must no longer be inverted when constructing the target.

With $L$ and the hash interpreted as a number $H$, the target can be constructed in binary as follows:

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

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

$X=p_{P}\#-(T{\bmod {p}}_{P}\#)+f\times p_{P}\#+o$

$p_{P}\#$ is the product of the first $P$ primes (primorial), the $P$th included. For example, $p_{3}\#=2\times 3\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 have 1 as the latest bit), and the remaining 15 bits are for now unused, but must be set to 0 except the latest one to 1. In summary, the nOffset decomposes as

16 - Primorial Number
128 - Primorial Factor
96 - Primorial Offset
15 - Reserved (for now, 000000000000001)
1 - Always 0

Encoding this way both removes the $X<2^{256}$ restriction and allows more efficient mining. Reading the page explaining the mining algorithm will also help making sense of this encoding.

The Riecoin protocol still uses 32 iterations of the Miller-Rabin primality test for the checks.