Are you taking into account that there is no parallelism involved? There is no significant speed up, just as with the time capsule puzzle.

I mean a system with separate coins with no blockchain. The PoW is replaced by its hash, its hash etc forever. Yes, CPU is bad because many have slower clock speeds, that is why I looked for strongly memory-hard hashing like maybe a 40-bit-rc4 or so on SSD.

I didn't mean trusted timestamps, though I don't know what kinds of them exist.

The one with the most hash iterations has gotten it first. By "fair" I meant the same serial iteration h(h(h)))... speed, so parallelism doesn't help like it does with searching for preimages, it's bound like the time lock puzzles. E.g. both provers having a hasher that can do X single core instructions a second, one can prove to be ahead because he started earlier, and for the verifying he sends a keyed hash, so when the behind-clients have iterated to the same count, they see who was right / first and nobody could have catched up. You could prove being ahead in iterations forever and the hash tree would just be there so that you don't need many hashers, you only take in a new hash leaf, which itself proves its iteration count and the top hash iteration count is then added. So one could prove it for as many coins as they like.

(?)

(sorry for my problems with this board software)

For a new cryptomoney: If there was a very fair iterated hashing (maybe memory-bound to a big ssd?), might it be a good idea to keep one top-hash alive with it that proofs (with a keyed hash in order not to give anyone the chance to catch up) you were the first one to get something? When trying to receive a coin clients would always try to ask others in the network to make sure the real owner really has the longest running chain with a hash leaf for this coin. And if your ssd (or whatever hashing hardware) is a slow one or you have a power outage for a long time (maybe use batteries) you lose your money to potential double-spend-accepters.