[dozzie]

The thing is, finding a nonce that with given payload gives a hash ending with predefined number of zero bits has only one purpose: so everybody is very slow in computing it, but everybody is very fast in verifying. You can trade it for any other difficult problem that's easy to verify (anything NP-complete will do, assuming P != NP), you just need to find encoding that maps a payload into a problem instance.

In other words, you could replace proof of work with finding the largest clique in a graph, and try doing that in ASIC.