Stateless hash based public key cryptography? Merkle-Winternitz signatures based on fractal hash trees are an attractive alternative to other post-quantum cryptographic schemes, in particular since they are conceptually simple, the security properties are easily understood and they are easy to implement correctly.

However, all schemes based on Merkle trees appear to be stateful, in the sense that the signer must keep track of the number of signatures already generated, and because some optimizations make it significantly impractical to generate several signatures in parallel. This is a huge minus e.g. for server authentication, where the same key might have to be used for several connections in parallel.

Furthermore, stateful private keys are vulnerable to server crashes if the private key state is not immediately persisted (which further increases stalls from serialized signing). Randomized schemes (such as DSA/ECDSA), or schemes based on trap door functions rather than one way functions (such as RSA) do not have these problems.

Does there exist any public key scheme based solely on hash function that does not require a stateful private key?
You can build a gigantic, enormous tree that has capacity for up to $2^{80}$ one-time signatures (say).  Then, each time you want to sign something, you randomly pick a 80-bit value and use that to select which of the $2^{80}$ subtrees to use to sign the message.  As long as the number of messages you intend to sign is much less than $2^{40}$ messages, a collision is unlikely.

It takes some extra work to make this work.  In particular, if your tree used only hash functions, then to precompute the public key, you'd have to do $2^{80}$ work to populate the entire tree -- no good.  So, in fact we do a multi-level tree where the entries at one level are used to sign a subtree the next level down (signed, using Merkle-Winternitz signatures).

For more details on how to make this work, you can see, e.g.,  https://www.imperialviolet.org/2013/07/18/hashsig.html or https://www.cdc.informatik.tu-darmstadt.de/reports/reports/BDKOV07.pdf.

This does increase the size of signatures and the amount of computation needed a bit, but if you want a stateless scheme, it might be viable.