Primecoin v0.2 Proposal

[Sunny King]

Currently Primecoin protocol allows searching for a header hash of arbitrary factorization. In fact the reference miner currently finds a hash divisible by 210, instead of taking random hash values.

If a prime chain is pre-generated with highly abundant origins (abundant meaning large number of factors), in theory you could try to search for a block header hash that divides the abundant origin. This would defeat the non-reusability property of the proof-of-work. With current limit on prime size at 2000 bit this is still computationally not feasible, but I estimate that instead of 256 bit hard of the secure hash, it might be reduced to about 128 bit hard for such brute-force attacks.

Even though this is not considered a feasible attack vector right now, there is a simple adjustment of the protocol that eliminates this doubt completely. By requiring block header hash to meet Fermat test (thus basically prime), this attack vector is eliminated.

I will be testing a modified reference miner in the next couple weeks for this change. If there is no strong objection to this protocol adjustment, it will be implemented in a v0.2 release within a couple of months time. Before the protocol is implemented, there should be plenty of time for the miners on the market to adjust to this new protocol rule.

Note: this is a hard-fork change and would be implemented as mandatory upgrade with scheduled protocol switch. There is no impact to minting/transaction/wallet related functionality.

Feel free to discuss and comment here.

Update (August 16th): Reference miner update ready for review:
https://github.com/primecoin/primecoin/commit/22f02370d75be01ec7322914c35960cd123ea1b9

[jh00]

I don't see it as a feasible attack vector that we even need to worry about, but I understand that you want to eliminate the possibility completely. Considering it takes p tries to find a blockhash that is divisible by p, it seems unlikely to me that finding a block hash with many prime factors appearing all at once can be done in a amount of time that makes this attack possible or more attractive than the original algorithm. That being said, I still like the idea to force the block hash to be a prime. It's easy to implement and it makes numeric shortcuts impossible.

It would be nice if you can tell us a specific block height for the switch, so we can implement it in the miners early and stay with the current method up to the given block. If we would implement using prime hashes now as part of the general algorithm (as it is upward compatible) the miners would likely be slightly slower due to missing the 210 factor of the primorial which results in larger numbers to test. Therefore some people would refrain from using such a miner.

[mikaelh]

I agree that the attack does not seem feasible currently. Even if the security level of the hash was reduced to 128 bits, cracking it should still be harder than normal mining. I'm not sure if actually can be reduced that much. The proposed solution certainly does eliminate any possibility of it being even remotely possible.

I also agree with jh00 that it probably won't be possible to have an "upward compatible" miner with equal performance. But miners should presumably be able to check the block height and do the switch automatically when it will be scheduled to occur.

[Sunny King]

Since there is reasonable concensus that this is a good proposal, v0.2 Protocol update is in planning. Comments are still welcome.

Miner developers are encouraged to begin implementing v0.2 protocol compliant mining mode. This mode can be switched at protocol switch time (at least 2 months after v0.2 release) due to the impact on miner performance.

There are plenty of time for developers to add v0.2 protocol support still. I will first introduce a v0.2 check in CheckBlock() that throws a log message warning for testnet. Testnet will then be upgraded and switch to the new protocol. The actual v0.2 release is currently planned for first quarter of 2014. There will be at least another 2 months of upgrade window after release before v0.2 protocol is enforced in the network.