Interesting! I was actually inspired by some of your IRC comments.
I am thinking the problems would be produced by peers and assigned to one another using a provably random assignment scheme. When assigned a problem, each peer has the option to ignore or attempt to solve. If they choose ignore they are assigned another one. Each time this happens to a problem is treated by the network as evidence that the problem is a hard one. If someone solves a scored-as-hard problem, they get a better chance of winning the block. (This would be accomplished by appending the solution as a nonce in a bitcoin-like arrangement and setting the minimum difficulty based on the hardness ranking.)
Interesting! I was actually inspired by some of your IRC comments.
I am thinking the problems would be produced by peers and assigned to one another using a provably random assignment scheme. When assigned a problem, each peer has the option to ignore or attempt to solve. If they choose ignore they are assigned another one. Each time this happens to a problem is treated by the network as evidence that the problem is a hard one. If someone solves a scored-as-hard problem, they get a better chance of winning the block. (This would be accomplished by appending the solution as a nonce in a bitcoin-like arrangement and setting the minimum difficulty based on the hardness ranking.)
Hm. It never occurred to me that provable randomness might be useful… As stated, I don’t think your scheme works because of Sybil attacks:
I come up with some easy NP problem or one already solved offline
I pass it around my 10,000 fake IRC nodes who all sign it,
and present the solved solution to the network
$$$