Using public key recovery by default?

[miner2251]

For now, we have public key hashes as outputs and then it is needed to reveal public key and signature in inputs. But the properties of ECDSA allows us to skip this public key and by having some address and some signature, it is possible to verify it (in exactly the same way as we can type some address and signature and verify any message, not necessary being a transaction). Then, why storing public keys in the blockchain is needed if they can be safely skipped and calculated from signature and address?

[Charles-Tim]

The output is the public key hash which is the address, the input is the public key. To spend, your wallet need to provide the public key and digital signature. In this regard, the public key and private key does not go beyond wallet, but are used in spending which makes the public key still very important. 

Then, why storing public keys in the blockchain is needed if they can be safely skipped and calculated from signature and address?

The public key does not go beyond the wallet. The private key can generate the public key, but the public key that has been generated will be used for spending while in such process, private key only produces digital signature to spend.

[pooya87]

But the properties of ECDSA allows us to skip this public key and by having some address and some signature, it is possible to verify it

To verify an ECDSA signature you do need the public key (R = (x_R, y_R) = u₁G + u₂Q_U where Q_U is the public key).
In fact you need 3 things: signature (r,s), the public key and the message that was signed (ie. the tx).

Then, why storing public keys in the blockchain is needed if they can be safely skipped and calculated from signature and address?

Because:
1. In ECDSA we can recover public key from signature + message but we may end up with more than one possible pubkey (up to 4 for secp256k1 with h=1). So we may have to verify the signature multiple times to see which pubkey is valid and that wastes a lot of time since the verification is an expensive process.
2. Recovering possible public keys is an even more expensive process that would slow down verification of blocks if pubkeys weren't present.

[NotATether]

Part of the reason why it's not done is because of the question of what to put in the message text.

Although the message text is hashed, you wouldn't want the text to be static such as an empty string or a 1KB long paragraph and you'd want it to be different for each signed transaction, because there may be a private-key-exposing flaw in using the same message text (this has not been confirmed yet).

[ranochigo]

Although the message text is hashed, you wouldn't want the text to be static such as an empty string or a 1KB long paragraph and you'd want it to be different for each signed transaction, because there may be a private-key-exposing flaw in using the same message text (this has not been confirmed yet).

Signing the same message results in the same signature, provided that the r value is deterministic. Even if it's not, it is fine as long as the r value is not reused. I don't think signing the same message would expose you to any risk.

[pooya87]

Although the message text is hashed, you wouldn't want the text to be static such as an empty string or a 1KB long paragraph and you'd want it to be different for each signed transaction, because there may be a private-key-exposing flaw in using the same message text (this has not been confirmed yet).

There is nothing secretive the message, it is already revealed and knowing it and its hash isn't changing anything about security of the signature that is produced.
The only thing about message that user should worry about is that it should be clear what it is meant for with a timestamp so that it could not be abused by someone else pretending to be that user.

[NotATether]

The only thing about message that user should worry about is that it should be clear what it is meant for with a timestamp so that it could not be abused by someone else pretending to be that user.

If only the message really did have the timestamp autoinserted into the text then we wouldn't have this problem. Alternatively there could be another input field after the message text called something like "timestamp" where this info is filled in by the wallet and put on the last line of message text by itself and also under the address after the ===BEGIN SIGNATURE=== line. Just like we have an input field specifically for the address [which I know its public key is used in the signing so the question of where to put it in the message is moot].

[ranochigo]

If only the message really did have the timestamp autoinserted into the text then we wouldn't have this problem. Alternatively there could be another input field after the message text called something like "timestamp" where this info is filled in by the wallet and put on the last line of message text by itself and also under the address after the ===BEGIN SIGNATURE=== line. Just like we have an input field specifically for the address [which I know its public key is used in the signing so the question of where to put it in the message is moot].

Probably. Does any wallet still use that format right now?

Timestamp can help to a certain extent but the proper use of signed message is to have a clear purpose being outlined within the message itself by the user. When I've signed message in the past, I've tried my best to make it as unambiguous as possible to prevent someone else from using it. Timestamp can serve to prevent misuse in the further future but making the message valid for a certain purpose would solve the problem in its entirety.

[BlackHatCoiner]

1. In ECDSA we can recover public key from signature + message but we may end up with more than one possible pubkey (up to 4 for secp256k1 with h=1).

Can you explain this further? Why can you end up with up to 4 public keys for secp256k1 with h=1? (I guess with h you mean hash of the message)

[pooya87]

1. In ECDSA we can recover public key from signature + message but we may end up with more than one possible pubkey (up to 4 for secp256k1 with h=1).

Can you explain this further? Why can you end up with up to 4 public keys for secp256k1 with h=1? (I guess with h you mean hash of the message)

No h is an elliptic curve domain parameter known as cofactor and for different curves it has a different value. For NIST curves including secp256k1 it is equal to 1.
The reason why more than one public key can be recovered is because of how the equation works. You should refer to 4.1.6 Public Key Recovery Operation from Standards for Efficient Cryptography (SEC 1: Elliptic Curve Cryptography). The formula is something like this:

Code:

for j from 0 to h
  x = r + jn
  for k from 1 to 2
    Q = r^−1(sR − eG)

With h=1 we get 4 values for Q, most of the times the same value but it can be different too. So up to 4 valid pubkeys.

[gmaxwell]

Then, why storing public keys in the blockchain is needed if they can be safely skipped and calculated from signature and address?

It requires a couple bits of auxiliary data to do this, it slows down validation (by about 20%), it's incompatible with batch validation (ECDSA itself is too, but if you were going to add aux data you could batch validate and get a 2x speedup instead of a 20% slowdown), and there is a patent claim on the technique.

It also only saves 12 bytes compared to just using the public key, and that 12 byte savings comes from using a 160-bit hash instead of a 256-bit hash which reduces security to only 80-bits in cases where collision attacks matter (e.g. when multiple parties collaborate to generate a key).  If you use a 256-bit address hash to preserve ~128-bit security then there is no space savings at all vs using the public key directly.

[DannyHamilton]

Then, why storing public keys in the blockchain is needed if they can be safely skipped and calculated from signature and address?

It requires a couple bits of auxiliary data to do this, it slows down validation (by about 20%), it's incompatible with batch validation (ECDSA itself is too, but if you were going to add aux data you could batch validate and get a 2x speedup instead of a 20% slowdown), and there is a patent claim on the technique.

It also only saves 12 bytes compared to just using the public key, and that 12 byte savings comes from using a 160-bit hash instead of a 256-bit hash which reduces security to only 80-bits in cases where collision attacks matter (e.g. when multiple parties collaborate to generate a key).  If you use a 256-bit address hash to preserve ~128-bit security then there is no space savings at all vs using the public key directly.

I asked a similar question in the past, and got a similar response from gmaxwell.  I've been searching for that response for 3 days so that I could link to it.  Looks like now I won't have to.

[gmaxwell]

I asked a similar question in the past, and got a similar response from gmaxwell.  I've been searching for that response for 3 days so that I could link to it.  Looks like now I won't have to.

Ironically, I also thought I wrote a similar reply... searched for it, couldn't find it... so just wrote it again.

[DannyHamilton]

I asked a similar question in the past, and got a similar response from gmaxwell.  I've been searching for that response for 3 days so that I could link to it.  Looks like now I won't have to.

Ironically, I also thought I wrote a similar reply... searched for it, couldn't find it... so just wrote it again.

IIRC, Mine wasn't asking "why doesn't the code do this?"  Instead, I vaguely recall including it with other "examples" of why it's silly to think of Satoshi as a "cryptography expert".  Essentially my post was a rebuttal to all those that seem to want to worship Satoshi's original code as immutable and the definition of what bitcoin "IS".

Anyhow, it's lost now to time in the lake of spam and sig ad nonsense.