If both the public key and the private key are known ahead of time (public knowledge), and the goal is to choose a message/nonce that generates a signature with, for example, a certain number of leading zeroes, is this a similarly computationally challenging task to traditional proof of work in that it is "hard to find" but "(relatively) easy to verify?"
It seems like the answer should be "yes," because if the answer is "no" then (I think?) it would imply that signatures are not pseudorandomly uniform for different messages.
Put perhaps more succinctly, can a signature also itself serve to represent a targeted proof-of-work?
Lastly, do answers to any of the above change when the signature scheme used is Schnorr rather than ECSDA?