BitDNS is a different matter.. with DNS there is something that can be delivered electronically where the thing itself is stored in the blockchain. This would work.. but you don't really need the whole proof of work thing. If all you want is a first-come-first-served name grabbing model that is basically just a simple distributed database where the p2p swarm stores the zonefile and accepts updates from keyholders and allows new registrations where the name doesn't already exist. I don't see a role for proof-of-works here. Double spending doesn't really exist.. I guess the analogy would be if you tried to transfer (sign away to a new controlling private key) the same domain name to two different new owners.. how much of a problem would that be? Is it really worth doing proofs of work to stop it? Maybe.. but I'm not really convinced. With coins you can doublespend them to anyone.. with a domain name you'd have to find two people who wanted to buy the exact same domain from you at the same time. The motivation for fraud is significantly lower.