<p>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.</p>

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

<p>Rearranging this equation you get <em>rP = sR - mG</em>, or <em>P = (s/r)R - (m/r)G</em>. 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 <em>R</em> for which <em>R.x mod n = r</em> (in practice, the number is almost always 2).</p>

<p>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.</p>

<p>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 (<a href="https://github.com/bitcoin/bips/blob/master/bip-0322.mediawiki" rel="nofollow noreferrer">BIP 322</a>) 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.</p>

CC BY-SA 4.0
2018-11-25T23:33:15.450Z
Is this related to the second equation located below [**here**](https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch06.asciidoc#ecdsa-math) ?  

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
CC BY-SA 4.0
2018-11-26T08:00:48.537Z
@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
CC BY-SA 4.0
2021-05-12T18:24:37.120Z
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
CC BY-SA 4.0
2021-05-12T18:33:21.943Z
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
CC BY-SA 4.0
2023-04-10T08:16:01.090Z
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
CC BY-SA 4.0
2018-11-21T03:37:47.750Z
2019-04-11T01:37:04.570Z
2019-04-11T01:37:04.570Z
Pieter Wuille
<p>I'm under the impression that a public key is revealed when you sign a message.</p>

<p>Given these 3 inputs.
P2PKH Address, Digital Signature, Message.</p>

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

<p>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)?</p>

<p>Thanks!</p>

<signature><message-signing><bech32-address><p2pkh>
How is Public Key extracted from (message, digital signature, address)
Michael Tidwell
# How is Public Key extracted from (message, digital signature, address)

(Asked by: username_0 on 2018-11-21)

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!

**Tags:** signature, message-signing, bech32-address, p2pkh


---

## 1 answers

### Answer by username_1 on 2018-11-21. Score: 10 | Accepted answer

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](https://github.com/bitcoin/bips/blob/master/bip-0322.mediawiki)) 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.

> **Comments:**
> **username_2**: Is this related to the second equation located below [**here**](https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch06.asciidoc#ecdsa-math) ?    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 )  
> **username_1**: @username_2 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.  
> **username_3**: 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?  
> **username_1**: 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.  
> **username_4**: 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 username_1 says the number of public keys in practice is almost always 2.  

---

