[XPM] [ANN] Primecoin Prerelease Announcement - Introducing Prime Proof-of-Work

[karsy]

• Pure proof-of-work, no proof-of-stake (unlike ppcoin), not energy efficient, but with additional potential scientific value derived from proof-of-work energy consumption (energy multiuse)

What kind of scientific value?

I believe he is referring to finding high number prime numbers. Which actually can be quite difficult. Since the spacing of each prime number increases exponentially.

[gatra]

• Pure proof-of-work, no proof-of-stake (unlike ppcoin), not energy efficient, but with additional potential scientific value derived from proof-of-work energy consumption (energy multiuse)

What kind of scientific value?

I believe he is referring to finding high number prime numbers. Which actually can be quite difficult. Since the spacing of each prime number increases exponentially.

I believe he is referring to finding high number prime numbers. Which actually can be quite difficult. Since the spacing of each prime number increases logarithmically.
FTFY

[learnmore]

I am curious as to why the innovative POW in Primecoin couldn't have been engineered into the the next version of PPcoin.  I feel that the chain is still young enough to allow for such major paradigm shifts even if there had to be some massive POS transaction into the new PP(Prime)Coin version.

[fenican]

Hard to get excited about a CPU proof of work coin.  How will you defend against botnets ?

[Boing7898]

Hard to get excited about a CPU proof of work coin.  How will you defend against botnets ?

Botnets can be used to mine with CPU as much as they can used to mine with GPUs.

[Boing7898]

Botnets can be used to mine with CPU as much as they can used to mine with GPUs.

Botnets are on computers of non-tech-savvy users, i.e. usually no or crappy GPU.

Botnet owners, most of the time, aim at gaming users, to get good GPUs.
Most "silent miners" offer GPU mining too nowadays.

[monocolor]

It would be great if we can integrate into the Mersenne prime search, which requires a lot computing powers. This way the miners will do something useful...
http://www.mersenne.org/

It can't use mersenne primes, unless you want only a block per year.

This is not true, one mersenne computation is broken down to many smaller pieces, can be perfectly integrated

[someone42]

for a POW algorithm to be useful for blockchain verification it must be

 - hard to derive (for transaction verifiers)
 - controllable difficulty (so as more nodes are added, the difficulty can rise)
 - easy to prove (for relaying nodes)

hash algorithms are good here.  An algorithm with primes sounds like it would be based around the factorising problem (e.g. as used in RSA) - but the question is how Sunny has designed it to be variable - perhaps the difficulty is set by the length of required prime in bits, and the POW is two primes and a factor that meet the difficulty.  This would be very very ASICable compared with scrypt, but I don't think any off the shelf ASIC cores would exist (unlike with SHA256)

Interested to see what Sunny has come up with here.

Will

Here is something which might work. It is based on Pratt certificates (see http://en.wikipedia.org/wiki/Pratt_certificate).

Mining process
The miner attempts to find a large prime n which has the following properties:

• The most significant 256 bits are equal to the merkle root
• The prime is large enough to meet the difficulty target

The miner can do this by trying random large integers (the least significant bits are the "nonce") and running many iterations of the Miller-Rabin test. With enough Miller-Rabin iterations, the miner can be quite confident that they actually have a prime.

Proof of work
To generate the proof of work, the miner generates a Pratt certificate for their large prime n. Generation of a Pratt certificate is very hard; it requires the factorisation of n - 1, which is requires exponential time in the size of n. Yet it is easy to verify a Pratt certificate; verification is polynomial time in the size of n. For example, factorisation of a 1024 bit integer is about 7 million times as difficult as a 512 bit integer (according to http://en.wikipedia.org/wiki/General_number_field_sieve), yet it is only 16 times as difficult to verify.

This meets the criteria for a useful proof-of-work: hard to generate, easy to verify, adjustable difficulty and incorporates the merkle root.

Mining pools are more complicated to implement, since integer factorisation is not as trivially parallellisable as hashcash. This might explain why the initial client is solo-mine only.

It also has the property of being sensitive to improvements in factorisation algorithms. This makes it somewhat resistant to ASICs, since algorithm improvements may invalidate ASIC designs, so ASIC developers may not wish to take on the risk.

(Edit: linear -> polynomial)

[mokimarket]

for a POW algorithm to be useful for blockchain verification it must be

 - hard to derive (for transaction verifiers)
 - controllable difficulty (so as more nodes are added, the difficulty can rise)
 - easy to prove (for relaying nodes)

hash algorithms are good here.  An algorithm with primes sounds like it would be based around the factorising problem (e.g. as used in RSA) - but the question is how Sunny has designed it to be variable - perhaps the difficulty is set by the length of required prime in bits, and the POW is two primes and a factor that meet the difficulty.  This would be very very ASICable compared with scrypt, but I don't think any off the shelf ASIC cores would exist (unlike with SHA256)

Interested to see what Sunny has come up with here.

Will

Here is something which might work. It is based on Pratt certificates (see http://en.wikipedia.org/wiki/Pratt_certificate).

Mining process
The miner attempts to find a large prime n which has the following properties:

• The most significant 256 bits are equal to the merkle root
• The prime is large enough to meet the difficulty target

The miner can do this by trying random large integers (the least significant bits are the "nonce") and running many iterations of the Miller-Rabin test. With enough Miller-Rabin iterations, the miner can be quite confident that they actually have a prime.

Proof of work
To generate the proof of work, the miner generates a Pratt certificate for their large prime n. Generation of a Pratt certificate is very hard; it requires the factorisation of n - 1, which is requires exponential time in the size of n. Yet it is easy to verify a Pratt certificate; verification is polynomial time in the size of n. For example, factorisation of a 1024 bit integer is about 7 million times as difficult as a 512 bit integer (according to http://en.wikipedia.org/wiki/General_number_field_sieve), yet it is only 16 times as difficult to verify.

This meets the criteria for a useful proof-of-work: hard to generate, easy to verify, adjustable difficulty and incorporates the merkle root.

Mining pools are more complicated to implement, since integer factorisation is not as trivially parallellisable as hashcash. This might explain why the initial client is solo-mine only.

It also has the property of being sensitive to improvements in factorisation algorithms. This makes it somewhat resistant to ASICs, since algorithm improvements may invalidate ASIC designs, so ASIC developers may not wish to take on the risk.

(Edit: linear -> polynomial)

I'm very excited about this coin. Finally something that will actually have real value.

[mokimarket]

Finally something that will actually have real value.

I wouldn't go that far.

I know not yet. But I would like to see a proof of work linked to something like finding new primes and this project is the closest I've seen.

[Charles999]

Can we use CGMIner for this coin??  And what version.. The CPU only or the GPU??

[ivanlabrie]

Not for now Charles...cpu only mining via wallet at launch.
Should be fairly interesting, I have high hopes in this and eMunies/Microcash.

[gatra]

Finally something that will actually have real value.

I wouldn't go that far.

I know not yet. But I would like to see a proof of work linked to something like finding new primes and this project is the closest I've seen.

but we haven't seen anything yet! please give more details on what this project is about

[fran2k]

So much expectation

[yaffare]

Why do you people waste your time with stuff like that?

If you spend all your time on improving bitcoin, that would really help.
What does a different proof of work change?
- it does not change that transactions have to be collected in a block
- it does not change that you have to wait for x confirmations
- it does not change that blocks have to broadcasted
- it does not change .. anything

[Tribex1301]

Well done Sunny, I am looking forward which results will bring this new step.

[Loktera]

Why do you people waste your time with stuff like that?

If you spend all your time on improving bitcoin, that would really help.
What does a different proof of work change?
- it does not change that transactions have to be collected in a block
- it does not change that you have to wait for x confirmations
- it does not change that blocks have to broadcasted
- it does not change .. anything

Traditional PoW methods are quite wasteful of our energy resources. We need a solution that either reduces energy consumption massively, or at least puts the energy to more use than just maintaining a blockchain.

[Lauda]

Well this is rather interesting time to use some supercomputers to fast mine all of this  

[Bigcheezit210]

Will be waiting for Primecoin to launch, I am definitely interested in this coin.

[romerun]

True, but is finding prime really important to the world if everyone keeps running this til the next century ? At the end, it's just another scheme of coin distribution. Prime might be cool in 1920, now it's quite yawn. If it's like trying to find new patterns in human gnome or something I would approve.

Why do you people waste your time with stuff like that?

If you spend all your time on improving bitcoin, that would really help.
What does a different proof of work change?
- it does not change that transactions have to be collected in a block
- it does not change that you have to wait for x confirmations
- it does not change that blocks have to broadcasted
- it does not change .. anything

Traditional PoW methods are quite wasteful of our energy resources. We need a solution that either reduces energy consumption massively, or at least puts the energy to more use than just maintaining a blockchain.