No, from its private key! The same key that's used to sign outgoing content, authenticating to the Tor network.

Edit: I'm wrong. It's based on the hash of the public key.

How can anyone verify a hash of the private key without having it? Anyway, see https://trac.torproject.org/projects/tor/wiki/doc/HiddenServ...

I don't know the details. But basically, a Tor relay provides some token to the onion server. The onion server signs that token with its private key, and returns the output to the Tor relay. Then the Tor relay verifies that the token was signed by the private key corresponding to the onion hostname.