Bitcoin Forum
February 27, 2024, 06:57:20 AM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Using public key recovery by default?  (Read 284 times)
miner2251 (OP)
Jr. Member
*
Offline Offline

Activity: 34
Merit: 85


View Profile
March 22, 2021, 08:40:54 PM
 #1

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?
1709017040
Hero Member
*
Offline Offline

Posts: 1709017040

View Profile Personal Message (Offline)

Ignore
1709017040
Reply with quote  #2

1709017040
Report to moderator
1709017040
Hero Member
*
Offline Offline

Posts: 1709017040

View Profile Personal Message (Offline)

Ignore
1709017040
Reply with quote  #2

1709017040
Report to moderator
1709017040
Hero Member
*
Offline Offline

Posts: 1709017040

View Profile Personal Message (Offline)

Ignore
1709017040
Reply with quote  #2

1709017040
Report to moderator
The block chain is the main innovation of Bitcoin. It is the first distributed timestamping system.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1709017040
Hero Member
*
Offline Offline

Posts: 1709017040

View Profile Personal Message (Offline)

Ignore
1709017040
Reply with quote  #2

1709017040
Report to moderator
Charles-Tim
Legendary
*
Offline Offline

Activity: 1470
Merit: 4730



View Profile
March 22, 2021, 10:26:38 PM
 #2

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.

  BTC
.
BTC
.
 BTC
.
BTC
..JAMBLER.io..
██
██
██
██
██
██
██

██

██

██

██
YOUR OPPORTUNITY TO
HAVE BITCOIN BUSINESS

██
██
██
██
██
██
██

██

██

██

██
.
  BTC
. BTC
.
.
 
BTC
  BTC
pooya87
Legendary
*
Offline Offline

Activity: 3374
Merit: 10335



View Profile
March 23, 2021, 03:01:20 AM
Merited by gmaxwell (2), hosseinimr93 (1)
 #3

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 = (xR, yR) = u1G + u2QU where QU 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).

Quote
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.

  BTC
.
BTC
.
 BTC
.
BTC
..JAMBLER.io..
██
██
██
██
██
██
██

██

██

██

██
YOUR OPPORTUNITY TO
HAVE BITCOIN BUSINESS

██
██
██
██
██
██
██

██

██

██

██
.
  BTC
. BTC
.
.
 
BTC
  BTC
NotATether
Legendary
*
Offline Offline

Activity: 1526
Merit: 6444


bitmixlist.org


View Profile WWW
March 23, 2021, 03:46:13 AM
 #4

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).

  BTC
.
BTC
.
 BTC
.
BTC
..JAMBLER.io..
██
██
██
██
██
██
██

██

██

██

██
YOUR OPPORTUNITY TO
HAVE BITCOIN BUSINESS

██
██
██
██
██
██
██

██

██

██

██
.
  BTC
. BTC
.
.
 
BTC
  BTC
ranochigo
Legendary
*
Offline Offline

Activity: 2926
Merit: 4017



View Profile
March 23, 2021, 10:46:47 AM
 #5

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.

  BTC
.
BTC
.
 BTC
.
BTC
..JAMBLER.io..
██
██
██
██
██
██
██

██

██

██

██
YOUR OPPORTUNITY TO
HAVE BITCOIN BUSINESS

██
██
██
██
██
██
██

██

██

██

██
.
  BTC
. BTC
.
.
 
BTC
  BTC
pooya87
Legendary
*
Offline Offline

Activity: 3374
Merit: 10335



View Profile
March 24, 2021, 04:33:47 AM
 #6

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.

  BTC
.
BTC
.
 BTC
.
BTC
..JAMBLER.io..
██
██
██
██
██
██
██

██

██

██

██
YOUR OPPORTUNITY TO
HAVE BITCOIN BUSINESS

██
██
██
██
██
██
██

██

██

██

██
.
  BTC
. BTC
.
.
 
BTC
  BTC
NotATether
Legendary
*
Offline Offline

Activity: 1526
Merit: 6444


bitmixlist.org


View Profile WWW
March 24, 2021, 04:48:27 AM
 #7

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].

  BTC
.
BTC
.
 BTC
.
BTC
..JAMBLER.io..
██
██
██
██
██
██
██

██

██

██

██
YOUR OPPORTUNITY TO
HAVE BITCOIN BUSINESS

██
██
██
██
██
██
██

██

██

██

██
.
  BTC
. BTC
.
.
 
BTC
  BTC
ranochigo
Legendary
*
Offline Offline

Activity: 2926
Merit: 4017



View Profile
March 24, 2021, 05:29:50 PM
 #8

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.

  BTC
.
BTC
.
 BTC
.
BTC
..JAMBLER.io..
██
██
██
██
██
██
██

██

██

██

██
YOUR OPPORTUNITY TO
HAVE BITCOIN BUSINESS

██
██
██
██
██
██
██

██

██

██

██
.
  BTC
. BTC
.
.
 
BTC
  BTC
BlackHatCoiner
Legendary
*
Offline Offline

Activity: 1442
Merit: 6915


Farewell, Leo


View Profile
March 25, 2021, 10:34:51 AM
 #9

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)

  BTC
.
BTC
.
 BTC
.
BTC
..JAMBLER.io..
██
██
██
██
██
██
██

██

██

██

██
YOUR OPPORTUNITY TO
HAVE BITCOIN BUSINESS

██
██
██
██
██
██
██

██

██

██

██
.
  BTC
. BTC
.
.
 
BTC
  BTC
pooya87
Legendary
*
Offline Offline

Activity: 3374
Merit: 10335



View Profile
March 25, 2021, 03:41:52 PM
 #10

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.

  BTC
.
BTC
.
 BTC
.
BTC
..JAMBLER.io..
██
██
██
██
██
██
██

██

██

██

██
YOUR OPPORTUNITY TO
HAVE BITCOIN BUSINESS

██
██
██
██
██
██
██

██

██

██

██
.
  BTC
. BTC
.
.
 
BTC
  BTC
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4144
Merit: 8335



View Profile WWW
March 25, 2021, 08:43:11 PM
 #11

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
Legendary
*
Offline Offline

Activity: 3318
Merit: 4407



View Profile
March 26, 2021, 12:14:18 AM
Merited by gmaxwell (1)
 #12

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
Moderator
Legendary
*
expert
Offline Offline

Activity: 4144
Merit: 8335



View Profile WWW
March 26, 2021, 11:30:28 PM
 #13

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. Smiley
DannyHamilton
Legendary
*
Offline Offline

Activity: 3318
Merit: 4407



View Profile
March 28, 2021, 09:41:15 PM
 #14

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. Smiley

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.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!