bitcoin-qt has a "signature verification" feature where you can verify a signed message. All it needs is the bitcoin address of the signer, the message and a short signature. From what I understand about digital signatures, you would need the public key in order to verify a signature. A bitcoin address is just a hash of the public key. The public key may be in the blockchain but that would only be the case if the address had already claimed at least one output. If they haven't claimed any outputs, how can the signature be verified?
The ECDSA public key can be recovered from the signature.
See this bitcointalk thread and the linked pdf for details.
The signatures produced in this process include more metadata than usual to assist in public key recovery. It includes recovery flags (an 8-bit integer), which encodes whether the public key was compressed, and a specific recovery ID.
As the Secg PDF http://www.secg.org/sec1-v2.pdf points out (page 47) - given (r, s) you can recover a set of probable public keys. The recovery ID makes this an explicit derivation of the correct public key.
Including whether the public key is compressed is also important. Bitcoin signatures are verified by an address, not a public key!
Your signature looks like this: [32 bytes of r] [32 bytes of s] [recoveryFlags], and is usually base64 encoded.
Given one of these signatures, and a bitcoin address, the verification works as follows:
- generating the public key
- encoding it correctly (compression)
- hashing the result
- compare the hash against the hash extracted from the supplied bitcoin address.