7

I'm under the impression that a public key is revealed when you sign a message.

Given these 3 inputs. P2PKH Address, Digital Signature, Message.

Is the public key exposed? If so, how do you extract the public key from these 3 inputs?

Also, I'm still a little confused on why no applications do this with bech32 addresses. (I've heard it's because derivation path isn't defined... but will it ever be)?

Thanks!

Improve this question

1 Answer 1

Reset to default
10

An algorithm called Public Key Recovery exists for ECDSA, which lets you construct the public keys for which a given pair of message and signature would be valid.

To explain the algorithm, remember that ECDSA signatures are pairs (r,s) for which sR = mG + rP. In this equation m is the message hash (which must be a hash of a known message), P is the public key (an elliptic curve point), G is the curve generator point, and R is a point for which R.x mod n = r. n is the curve order.

Rearranging this equation you get rP = sR - mG, or P = (s/r)R - (m/r)G. Thus, it seems we can just compute the public key from the message and the signature. Unfortunately, there can be up to 4 different points R for which R.x mod n = r (in practice, the number is almost always 2).

This technique is used in the message signing, allowing the signature to be verified against just an address, rather than a public key. The verifier in this case recomputes the public key from the message and the signature, converts it to an address, and then compares with the provided address. The address input is still required to prevent people from just giving a signature and message, and then seeing an address and thinking this implies the signature was valid. It must be compared against the expected public key or address to be the case.

The reason this isn't implemented for P2SH or BIP173 addresses is because the "standard" was never extended to incorporate those address styles. There is a proposed new standard (BIP 322) which would cover all types of addresses and more, but isn't widely implemented or used yet. BIP 322 also doesn't use pubkey recovery anymore; it simply uses the Script language and encapsulates a scriptSig/witness to verify against the script that corresponds with the address.

Improve this answer
5
  • Is this related to the second equation located below here ? P = Inverse(S) * Hash(m) * G + Inverse(S) * R * Qa : ( where R and S are the signature values; Qa is Alice’s public key; m is the transaction data that was signed; G is the elliptic curve generator point )
    – skaht
    Nov 25, 2018 at 23:33
  • @skaht Yes, that's the same equation written in a different form, and using different symbols. What I'm explaining above is how to compute Qa given R,S, and m.
    – Pieter Wuille
    Nov 26, 2018 at 8:00
  • BIP340 mentions that its schnorr signatures don't support public key recovery because its "generally incompatible" with batch verification. Are they actually incompatible, or is it simply an unsolved problem that might be solved in the future? And why was it decided that batch verification was more important than public key recovery?
    – B T
    May 12, 2021 at 18:24
  • It is fundamentally incompatible. Public key recovery has as output a public key. (Batch) validation takes as input the public key(s). You can't do both, except to a very limited extent (you could in theory recover 1 public from a batch, but that's rather pointless, and not usable in the context of Bitcoin script). Why batch verification more important: BIP341 no longer uses public key hashes as commitment, but the public keys themselves, so there isn't anything to recover - the verifier receives the key already.
    – Pieter Wuille
    May 12, 2021 at 18:33
  • 1
    For those curious about the above comment "Unfortunately, there can be up to 4 different points R for which R.x mod n = r (in practice, the number is almost always 2)." I believe it's because R is a point on the finite field bounded between 0 and P-1, whereas r is bounded between 0 and n. Hence R.x mod n = r gives 2 possible x values for 0<=R.x<p-n-1 and n<=R.x<p-1, thus 4 possible public keys. The probability of this ambiguity occurring is about 2*(p-n)/p or 7x10^-39, thus why Pieter says the number of public keys in practice is almost always 2.
    – Peter
    Apr 10 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.