Ah, good point. So I guess you need a zero knowledge proof where it's not possible to prove that you submitted the proof! Now my head hurts :-P

On a somewhat unrelated note, I just went to a talk by Lane Rettig who was until recently an Ethereum core developer and left to work on a new project called SpaceMesh which has a pretty cool new consensus algorithm designed to address a number of the issues with traditional PoW. Just thought you might be interested.