Author Topic: Algorithm - explanation  (Read 3126 times)

Offline jinx1984

  • Jr. Member
  • **
  • Posts: 7
  • Karma: +0/-0
  • Hello I'm new here
  • Referrals: 0
    • View Profile
Algorithm - explanation
« on: January 12, 2014, 05:04:41 pm »
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*48798379
?????

Thank you in advance for answer


« Last Edit: January 12, 2014, 10:14:23 pm by jinx1984 »

Offline imbocoffee

  • Jr. Member
  • **
  • Posts: 10
  • Karma: +0/-0
  • Hello I'm new here
  • Referrals: 0
    • View Profile
Re: Algorithm - explanation
« Reply #1 on: January 12, 2014, 06:21:03 pm »
I'm a newbie too, but i'll try to answer. when you see that number 244904970375722028798242559069071350723679913437376658289613677305863972540773149*29 in primorial form subdivision
you really see 244904970375722028798242559069071350723679913437376658289613677305863972540773149*29# where 29# is 2*3*5*...*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
Sorry for my bad English, i'll try to improve it. thx.

BTC: 1HB5MhZ3BTjAHTLKWS9yVD1HKXbFFEBMSE
XPM: AWJFYrUynSUeoK3uC1JoSwm1PCu9k9vm6t

Offline optimalPrime

  • Jr. Member
  • **
  • Posts: 10
  • Karma: +0/-0
  • Hello I'm new here
  • Referrals: 0
    • View Profile
Re: Algorithm - explanation
« Reply #2 on: January 12, 2014, 08:29:16 pm »
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

Offline imbocoffee

  • Jr. Member
  • **
  • Posts: 10
  • Karma: +0/-0
  • Hello I'm new here
  • Referrals: 0
    • View Profile
Re: Algorithm - explanation
« Reply #3 on: January 12, 2014, 09:36:49 pm »
I'll try again :)

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.
Sorry for my bad English, i'll try to improve it. thx.

BTC: 1HB5MhZ3BTjAHTLKWS9yVD1HKXbFFEBMSE
XPM: AWJFYrUynSUeoK3uC1JoSwm1PCu9k9vm6t

Offline jinx1984

  • Jr. Member
  • **
  • Posts: 7
  • Karma: +0/-0
  • Hello I'm new here
  • Referrals: 0
    • View Profile
Re: Algorithm - explanation
« Reply #4 on: January 12, 2014, 11:52:25 pm »
Hello, thank You for your answer It clarifies a lot.

But it shows also that I have justified doubds.
if *29 stands for
2*3*5*7*11*13*17*19*23*29 then this numbers should be even bigger (from * to *29 there is only 10 possibilities) Where is that 1 GHash/s hiding?


Cheers

Adam

Offline imbocoffee

  • Jr. Member
  • **
  • Posts: 10
  • Karma: +0/-0
  • Hello I'm new here
  • Referrals: 0
    • View Profile
Re: Algorithm - explanation
« Reply #5 on: January 13, 2014, 11:51:35 am »
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 a*x#-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 a*x-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 :) 
« Last Edit: January 13, 2014, 11:57:07 am by imbocoffee »
Sorry for my bad English, i'll try to improve it. thx.

BTC: 1HB5MhZ3BTjAHTLKWS9yVD1HKXbFFEBMSE
XPM: AWJFYrUynSUeoK3uC1JoSwm1PCu9k9vm6t

Offline jinx1984

  • Jr. Member
  • **
  • Posts: 7
  • Karma: +0/-0
  • Hello I'm new here
  • Referrals: 0
    • View Profile
Re: Algorithm - explanation
« Reply #6 on: January 18, 2014, 10:04:14 am »
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).

Quote
"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


Offline okzx

  • Sr. Member
  • ****
  • Posts: 112
  • Karma: +10/-4
  • Referrals: 0
    • View Profile
    • Personal Website
Re: Algorithm - explanation
« Reply #7 on: January 18, 2014, 05:15:25 pm »
I've never heard of the term GHash used in reference to Primecoin? Where are you getting that from?
XPM: AGq1NJUkh1pe5LWxTrD8aDVXARsfqwsAfX

Offline optimalPrime

  • Jr. Member
  • **
  • Posts: 10
  • Karma: +0/-0
  • Hello I'm new here
  • Referrals: 0
    • View Profile
Re: Algorithm - explanation
« Reply #8 on: January 18, 2014, 06:48:49 pm »
Is there a way to test if a particular chain has already been used in a block before?

Offline okzx

  • Sr. Member
  • ****
  • Posts: 112
  • Karma: +10/-4
  • Referrals: 0
    • View Profile
    • Personal Website
Re: Algorithm - explanation
« Reply #9 on: January 18, 2014, 11:17:02 pm »
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.
XPM: AGq1NJUkh1pe5LWxTrD8aDVXARsfqwsAfX

Offline optimalPrime

  • Jr. Member
  • **
  • Posts: 10
  • Karma: +0/-0
  • Hello I'm new here
  • Referrals: 0
    • View Profile
Re: Algorithm - explanation
« Reply #10 on: January 18, 2014, 11:32:07 pm »
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..?

Offline jinx1984

  • Jr. Member
  • **
  • Posts: 7
  • Karma: +0/-0
  • Hello I'm new here
  • Referrals: 0
    • View Profile
Re: Algorithm - explanation
« Reply #11 on: January 19, 2014, 12:07:10 am »
I've never heard of the term GHash used in reference to Primecoin? Where are you getting that from?

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 A*N-1  and A*N+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.






Offline imbocoffee

  • Jr. Member
  • **
  • Posts: 10
  • Karma: +0/-0
  • Hello I'm new here
  • Referrals: 0
    • View Profile
Re: Algorithm - explanation
« Reply #12 on: January 19, 2014, 12:29:02 am »
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.
Sorry for my bad English, i'll try to improve it. thx.

BTC: 1HB5MhZ3BTjAHTLKWS9yVD1HKXbFFEBMSE
XPM: AWJFYrUynSUeoK3uC1JoSwm1PCu9k9vm6t

Offline okzx

  • Sr. Member
  • ****
  • Posts: 112
  • Karma: +10/-4
  • Referrals: 0
    • View Profile
    • Personal Website
Re: Algorithm - explanation
« Reply #13 on: January 19, 2014, 03:14:40 pm »
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.

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

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

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

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.
« Last Edit: January 19, 2014, 03:22:43 pm by okzx »
XPM: AGq1NJUkh1pe5LWxTrD8aDVXARsfqwsAfX

Offline mikaelh

  • Jr. Member
  • **
  • Posts: 36
  • Karma: +17/-0
  • Referrals: 0
    • View Profile
Re: Algorithm - explanation
« Reply #14 on: January 21, 2014, 03:24:00 pm »
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:
Code: [Select]
    {
        "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.
BTC: 1MgDFUwZnnyGRHh1uUotKxpkNYX5Kx3SXr   XPM: AdmoBC4HiDiMQdJDmetTZLyyd8VCmkjCcz   PPC: PRJ5ejBxukDEpoK4rw4QcfQG4LSC14F6jA

 
Share this topic...
In a forum
(BBCode)
In a site/blog
(HTML)


Peercoin.net Official Peercoin Website