The average length of a prime gap with the starting
prime p, is log(p), which means that the average prime gap size
increases with lager primes.
Instead of the pure length, Gapcoin uses the merit of a prime gap,
which is the ratio of the gap's size to the average gap size.
Let p be the prime starting a prime gap, then m = gapsize/log(p)
will be the merit of this prime gap.
Also a pseudo random number is calculated from p to provide finer
difficulty adjustment.
Let rand(p) be a pseudo random function with
0 < rand(p) < 1
Then, for a prime gap starting at prime p with size s, the
difficulty will be s/log(p) + 2/log(p) ∗ rand(p), where 2/log(p)
is the average distance between a gap of size s and s + 2
(the next greater gap) in the proximity of p.
When it actually comes to mining, there are two additional fields
added to the Blockheader, named “shift” and “adder”.
We will calculate the prime p as sha256(Blockheader) ∗ 2^shift + adder.
As an additional criterion the adder has to be smaller
than 2^shift to avoid that the PoW could be reused.
For mining, PoWCore uses a basic prime sieve with some slightly improvements:
- Calculate the first n primes.
- In the actual sieve we skip all even numbers, so we want to only sieve the odd multiplies of each prime.
- So, create an additional set of primes and multiply each with two.
- Make sure the start–index of the sieve is divisible by two
- Now calculate for each prime the first odd number in the sieve, which is divisible by that prime (called pindex).
- For each prime p: mark the pindex as composite, add 2 ∗ p to pindex and mark it as composite, redo till we reach the end of the sieve.
- For each remaining prime candidate, check primality with the Fermat-pseudo-prime-test as it is faster than the Miller-Rabin-test (Fermat is not as accurate as the Miller-Rabin and maybe some valid sieve results will not be accepted, but this should be very rare)
- Now scan the remaining (pseudo) primes for a big prime gap.
- start–index can be hash ∗ 2^shift + [0, 2^shift)
- max sieve size depends on start index, and is limited by (hash + 2^shift) - start–index.
- shift can theoretically be in range [14, 2^16) but nodes can choose to only accept shifts till a given amount (e.g. 512)