Algorithm - explanation

Marketplace Primecoin
1

Hello,
I would be appreciate if someone explain me algorithm primecoin uses.
I’ve red
http://primecoin.org/static/primecoin-paper.pdf

And I have several questions to this document:
"Another important property of proof-of-work for cryptocurrency is non-reusability. That is, the proof-of-work on a particular block should not be reusable for another block. To achieve this, the prime chain is linked to the block header hash by requiring that its origin be divisible by the block header hash. The quotient of the division then becomes the proof-of-work certificate. "

If i run “listprimerecords 11” I get numbers like:
244904970375722028798242559069071350723679913437376658289613677305863972540773149*29

73853903764168979088206401473739410396455001112581722569026969860983656346568919*151

351180085486160447415012448369256040681465106930437599802264494461674068970139256*107

etc.
I assume in that compositions first component is block header hash and second is a number serched by algorithm so a*b+/- 1 is prime and ten next cunningham primes as well.

What I’m curious about is why second component is so small. PrimeCoin has 1GH/sec I assume that it means it is capable of checking primarity of 1E9 primes per second. if It searches for 60 sec to find next chain. Why there is no numbers like:

351180085486160447415012448369256040681465106930437599802264494461674068970139256*[glow=red,2,300]48798379[/glow]
???

Thank you in advance for answer

2

I’m a newbie too, but i’ll try to answer. when you see that number 24490497037572202879824255906907135072367991343737665828961367730586397254077314929 in primorial form subdivision
you really see 24490497037572202879824255906907135072367991343737665828961367730586397254077314929# where 29# is 235*…*29

you may see also something like “primechain” : “1CC0b.0ca375” that meens that a chain of 1 kind. so if you’ll calculate i suppose you’ll find out that the origin for that chain is 244904970375722028798242559069071350723679913437376658289613677305863972540773149*29#-1

3

I was looking for something like this thread to explain the intricacies of this primecoin protocol.

Could some one please explain what the second term in this means - "“1CC0b.0ca375"”. As explained 1CC stands for chain of 1st type. What is the significance of the second term ‘0ca375’ ? Also the ‘0b’ after 1CC is mysterious .

Please can someone throw some light on this.

ta

4

I’ll try again :slight_smile:

0b means that the chain has 11 numbers length. 11 (dec) = 0b (hex).

what’s about the part 0ca375 i’m not shure, but think that this is a difficulty fractional part drived from Fermat test remainder of the 12th number (which is supposed to be a probable prime, but failed the Fermat test). imho.

5

Hello, thank You for your answer It clarifies a lot.

But it shows also that I have justified doubds.
if 29 stands for
2357111317192329 then this numbers should be even bigger (from * to *29 there is only 10 possibilities) Where is that 1 GHash/s hiding?

Cheers

Adam

6

Primecoin is far away from hashing. Found block and broadcasted transactions are only hashed.

Your goal is to find a prime to be an origin of a rather long chain. That origin should not appear to be very big number to make the block confirmation not very hard for network, not shure about down boundary.
using ax#-1 form of a number you guarantee, that number is not divisable by any number lower or equal x.So you really enlarge your chance that ax-1 is a prime (that can be an origin or a member of the chain).

P.s: not shure that I answered exactly your question :slight_smile:

7

Hi,
thank You for answering, but i still do not understand what GHash means if in comes to primecoin (while i understand quite ok with bitcoin).

"using a*x#-1 form of a number you guarantee, that number is not divisable by any number lower or equal x"

7*8-1 = 55 it is divisible by 5

8

I’ve never heard of the term GHash used in reference to Primecoin? Where are you getting that from?

9

Is there a way to test if a particular chain has already been used in a block before?

10

The chances of the origin of a chain being able to divide two different block header hashes is probably pretty small. I would imagine the chances of it occurring and the computation required to test if any of the other chains found could be used would probably be less efficient than just trying to find new chains. I could be wrong though, someone should try to figure it out exactly.

As for testing it should be pretty easy. Just check all of the blocks to see if any of them have the same origin and chain type as the one you are checking for.

11

is that test something which can be done with the client debug window with some command ?

also is there any way of submitting new chain without actually mining…basically directly via the debug window…?

12

Hi,
i found it here:
https://coinplorer.com/Charts/Difficulty/XPM

Is there anyone that could explain Me how this algorith works

It gets a base hash as input (let call it N) and desired chain length k (difficulty), then It tests specific kinds of numbers for primarity

i Guess they are AN-1 and AN+1 then (if it is pseudoprime) it checks if next k-1 numbers (2P+/-1) are prime as well.
if yes A is a proof of worl

My Question are:

  1. Is that correct
  2. Are there any requirements what A can be?

Thank you in adwance for answer.

13

I’d like to add some comments to my previous post. a*n#+/-1 form is not dividable by any of numbers configuring n# till ‘a’ is a product of that numbers.

As for an algorithm for finding Cunningham chains, the case is that there is no such an algorithm (nowdays), but the algorithm of findig other elements in a chain once you’ve found a prime is quiet easy: just p2=2p1-1, p3=2p2-1 for 1CC and + for 2cc. case pn is not a prime (proubable prime is enough for primecoin) so you’ve got a chain n-1 length.

14

[quote=“imbocoffee, post:13, topic:1422”]I’d like to add some comments to my previous post. a*n#+/-1 form is not dividable by any of numbers configuring n# till ‘a’ is a product of that numbers.

As for an algorithm for finding Cunningham chains, the case is that there is no such an algorithm (nowdays), but the algorithm of findig other elements in a chain once you’ve found a prime is quiet easy: just p2=2p1-1, p3=2p2-1 for 1CC and + for 2cc. case pn is not a prime (proubable prime is enough for primecoin) so you’ve got a chain n-1 length.[/quote]

Not to nitpick, but that is still an algorithm that finds Cunningham chains.

Hi,
i found it here:
https://coinplorer.com/Charts/Difficulty/XPM[/quote]

If I had to guess, that website uses the GHash label for all of the coins, reguardless if it is relevant. I think the value that it is displaying as GHash has something to do with the normalized speed the blocks are found vs. 1 block every 60 seconds. Although that still looks a little off, maybe it is the speed vs. the total average speed.

15

Ok, here’s my attempt to answer many of the questions in this thread. Let’s take our latest 13-chain from yesterday as an example:

{ "time" : "2014-01-20 11:57:59 UTC", "epoch" : 1390219079, "height" : 368051, "ismine" : false, "mineraddress" : "AeKNrjNjtSncLJjUrDnQbrfzMS1NEq95Ta", "primedigit" : 107, "primechain" : "1CC0d.c48332", "primeorigin" : "12512390300891276190682243916246636610000954402441740274147501230375694290702478259358177371388272647651840", "primorialform" : "106680560818292299253267832484567360951928953599522278361651385665522443588804123392*61#" }

This is a Cunningham chain of the first kind (1CC). Other possible types are the second kind (2CC) and BiTwin (TWN).
The numbers of a 1CC chain look like this:
origin * 2^i - 1

Here ‘i’ starts from zero. So the first prime in the chain is origin - 1, the second prime is origin * 2 - 1, and then origin * 4 - 1, etc.

In Primecoin mining the origin is composed like this:
origin = headerHash * primorial * candidateMultiplier

The header hash is an intermediate hash calculated from the block header (it is NOT the final block hash). It’s a 256-bit number that is required to be greater than 2^255.

The primorial p# is defined as the product of all primes up until ‘p’, which means that 61# = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47 * 53 * 59 * 61 = 117288381359406970983270.

The candidate multiplier is a number produced by sieve. It’s typically less than 1 million. The sieve uses an efficient algorithm to filter out a large number of prime factors. The sieve rejects all candidates x for which headerHash * primorial * x * 2^i - 1 is divisible by one of the first 8000 prime numbers.

Side note: The “extended” sieve algorithm considers multipliers of the form 2^j * x. So we are multiplying all the candidate numbers by powers of 2. It turns out that these new candidates can be checked efficiently because we are shifting the origin so that the second prime becomes the first prime and the third prime becomes the second prime etc.

I think many people are still wondering what “1CC0d.c48332” means. I already explained that 1CC is a Cunningham chain of the first kind. ‘0d’ is the length of the chain in hexadecimal (that is 13). ‘c48332’ is the 24-bit representation of the fractional length. We can convert it into the usual decimal notation:
0xc48332 / 0xffffff = 0.7676

So our example chain would meet a difficulty of 13.7676.

Ghashes are not applicable to Primecoin. I’m guessing some websites are trying to interpret the Primecoin difficulty like it would be Bitcoin/Litecoin difficulty, which doesn’t produce any sensible results. My Primecoin charts show the average prime chain rate for the network:
http://xpm.muuttuja.org/charts/

Right now it’s about 1.94 chains/min. So the total ‘chainsperday’ of the whole network would be about 2793 chains/day.

16

@mikaelh - excellent stuff and thanks a lot for the explanation…

please could you also elaborate on the significance of primorialform - as in why is it needed when primeorigin is already listed ?

also could you point anywhere to a resource which explains the algorithm (sieve, header hash etc) in a bit more detail…

again thanks a lot for your explanation

cheers,

17

It’s mainly a matter of convenience of not having to write down so many digits. If you look at the Wikipedia page for Cunningham chain, you can see records like 1249097877×6599# − 1. And that primorial there expands to about 2800 digits.

Well, the header hash can be defined like this:
blockHeaderHash = HASH(nVersion, hashPrevBlock, hashMerkleRoot, nTime, nBits, nNonce)

This is what Bitcoin would normally call the block hash. However, in Primecoin we calculate a second hash after we find a prime chain. This is used as the final hash for the block:
blockHash = HASH(nVersion, hashPrevBlock, hashMerkleRoot, nTime, nBits, nNonce, bnPrimeChainMultiplier)

The intermediate header hash makes sure that the prime chain is tied to the block’s content. The second hashing makes sure that the block hash depends on the prime chain solution.

The sieve isn’t easy to explain because it requires understanding modular arithmetic. So that will have to wait for another day.

18

@mikaelh thanks again for your wonderful support…

could I please ask you -

  1. If I have a Cunningham chain with me , is it possible to submit it via the client debug window ? I can see there is a debug command line utility to submit the record but it’s usage is not very clear.
  2. Before submitting the chain is there a way to quickly check if that has not already been used before…I know block will not get verified eventually if it has been used but will certainly make things easier to do that verification beforehand.

many thanks for your replies

Cheers,

19

You need more than any Cunningham chain to submit. The origin of the Cunningham Chain has to be divisible by the previous block header hash, which changes every minute, approximately. But yes, if you happened to find a Cunningham Chain that just happen to have an origin divisible by the last block header hash then you could probably use submitblock in the Primecoin wallet.

20

Yup, you can’t simply submit any chain to the client. In practice you need to submit a full block containing at least one transaction. Also, there’s no point in checking if a chain has been used already because every chain should be unique with a very high probability (since the header hash is essentially random).