Quote from: someone42 on July 03, 2013, 04:53:04 PM

Quote from: willphase on July 02, 2013, 12:01:31 AM

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.