Bitcoin Forum
October 15, 2019, 08:03:48 AM *
News: Latest Bitcoin Core release: 0.18.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Do all elliptic curves support recovering the public key from a signature?  (Read 190 times)
Coin-1
Hero Member
*****
Offline Offline

Activity: 784
Merit: 721



View Profile
September 10, 2019, 05:15:55 PM
Merited by bones261 (2), Foxpup (1), ETFbitcoin (1), psycodad (1), Coding Enthusiast (1)
 #1

As far as I know, the secp256k1 elliptic curve used in Bitcoin supports extracting the public key from an ECDSA signature (i.e. from the r and s values). The recovery flag, which is a binary number from 28 to 35 (inclusive), is used to uniquely extract the public key.

The coordinates of the point lying on the secp256k1 elliptic curve are calculated by the following formula:
y2 = x3 + 7

It is possible to derive two public keys from an ECDSA signature if you know the parameters of this elliptic curve, the hash algorithm and the text of the signed message:
Q1 = r−1 * (sR − zG)
Q2 = r−1 * (sR' − zG)

where R and R' are two points that have the X coordinate equal to the r value.

But only one of these public keys really corresponds to the private key that was used to sign the message. As I understand, it is needed to consequently check the four variants for the recovery flag when signing a message in order to avoid such a discrepancy. If it is possible to uniquely extract the public key from the ECDSA signature, such a recovery flag will be added to the r and s values.

See also here.



But I'm curious whether all the elliptic curves support recovering the public key from a signature or not.

For example, the coordinates of the point lying on the ed25519 elliptic curve, which is used in some well-known alternative cryptocurrencies, are calculated by the following formula:
y2 = x3 + 486662 * x2 + x

Does this curve support extracting the public key from an ECDSA signature? Which of the elliptic curves do not support such a function?


▄▄▄███████▄▄▄
▄▄█████▀▀''`▀▀█████▄▄
▄███P'            `YY██▄
▄██P'                  `Y██▄
███'                      `███
███'                         ███
▄██'   ▄█████▄▄  ,▄▄▄▄▄▄▄▄▄▄p   ███
▄██▀  ,████▀P▀███.`██████████P   ▀██▄
███[ ,████ __. ███.   ,▄████▀    ███
███[ ]████████████[  ▄████▀       ███
███[ `████   ,oo2 ▄████▀'       ,███
▀██▄  `████▄▄█████d███████████   ▄██▀
▀██.   `▀▀▀▀▀▀"  Y▀▀▀▀▀▀▀▀▀▀▀  ,██▀
███.                        ,███
▀██▄                      ▄██▀
▀███▄_                 ,███▀
▀███▄▄_          _▄▄███▀
▀▀████▄▄ooo▄▄█████▀
▀▀███████▀▀'

365

TM

EZ365 is a digital ecosystem that combines
the best aspects of online gaming, cryptocurrency
trading
and blockchain education. ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀

..WHITEPAPER..    ..INVESTOR PITCH..

.Telegram     Twitter   Facebook

                       .'M████▀▀██  ██
                      W█Ws'V██  ██▄▄███▀▀█
                     i█████m.~M████▀▀██  ███
                     d███████Ws'V██  ██████
                     ****M██████m.~███f~~__mW█
          ██▀▀▀████████=  Y██▀▀██W ,gm███████
      g█████▄▄▄██   █A~`_WW Y█  ██!,████████
   g▀▀▀███   ████▀▀`_m████i!████P W███  ██
 _███▄▄▄██▀▀▀███Af`_m███   █W ███A ]███  ██
__ ~~~▀▀▀▀▄▄▄█*f_m██████   ██i!██!i███████
Y█████▄▄▄▄__. i██▀▀▀██████████ █!,██████
 8█  █▀▀█████.!██   ██████████i! █████
 '█  █  █   █W M█▄▄▄██████   ██ !██
  !███▄▄█   ██i'██████████   ██
   Y███████████.]██████████████
   █   ███████b ███   ██████
   Y   █   █▀▀█i!██   ████
    V███   █  █W Y█████
      ~~▀███▄▄▄█['███
            ~~*██

Play

            │
    │      ███
    │      ███
    │      ███
    │   │  ███
   ███  │  ███
   ███ ███ ███
 │  ███ ███ ███
███ ███ ███ ███
███ ███  │   │
███ ███  │   │
 │   │
 │

Trade

           __▄▄████▄▄
     __▄▄███████████████▄▄▄
 _▄▄█████████▀▀~`,▄████████████▄▄▄
 ~▀▀████▀▀~`,_▄▄███████████████▀▀▀
   d█~  =▀███████████████▀▀
   ]█! m▄▄ '~▀▀▀████▀▀~~ ,_▄▄
  ,W█. *████▄▄__ '  __▄▄█████
  !██P  █████████████████████
   W█. - ██████████████████▀
  i██[   ~ ▀▀█████████▀▀▀
 g███!
Y███

Learn
1571126628
Hero Member
*
Offline Offline

Posts: 1571126628

View Profile Personal Message (Offline)

Ignore
1571126628
Reply with quote  #2

1571126628
Report to moderator
1571126628
Hero Member
*
Offline Offline

Posts: 1571126628

View Profile Personal Message (Offline)

Ignore
1571126628
Reply with quote  #2

1571126628
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
achow101
Moderator
Legendary
*
expert
Offline Offline

Activity: 1918
Merit: 2833


bc1qshxkrpe4arppq89fpzm6c0tpdvx5cfkve2c8kl


View Profile WWW
September 10, 2019, 05:51:30 PM
Merited by Foxpup (3), bones261 (2), ETFbitcoin (1), Coin-1 (1), Coding Enthusiast (1)
 #2

Public key recovery is a function of ECDSA and is not restricted to any particular curves. It is a property of the signature algorithm (ECDSA), not of the curve. So yes, you can do public key recovery with any curve if they are using ECDSA.

The Schnorr signature scheme that is described in the proposed Schnorr BIP doesn't allow for public key recovery even though it uses the same secp256k1 curve that is currently used by Bitcoin.

Coding Enthusiast
Hero Member
*****
Offline Offline

Activity: 690
Merit: 1095


Novice C♯ Coder


View Profile WWW
September 11, 2019, 05:56:56 AM
Merited by achow101 (3), bones261 (2), ETFbitcoin (1), Coin-1 (1)
 #3

Note that the formula is longer than that, you are missing the first steps for calculating x1. For secp256k1 curve (and all the Koblitz curves over Fp defined by SEC-2) since the cofactor of the curve (or h) is equal to 1, you may only recover up to 4 possible public keys from the ECDSA signature. But cofactor of other curves may not be the same. For instance curve25519 cofactor is 8 and if you were doing ECDSA on this curve2 then the number of possible recovered public keys would have been 16.

1. Refer to page 47 of Standards for Efficient Cryptography 1, section 4.1.6 Public Key Recovery Operation https://www.secg.org/sec1-v2.pdf
2. Technically you could implement ECDSA algorithm on edwards curve but it is not going to be the standard defined by ANSI X9.62

Projects List+Suggestion box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

Coin-1
Hero Member
*****
Offline Offline

Activity: 784
Merit: 721



View Profile
September 12, 2019, 02:33:54 PM
 #4

Public key recovery is a function of ECDSA and is not restricted to any particular curves. It is a property of the signature algorithm (ECDSA), not of the curve.

Thanks for the correction. Of course, I asked about the recovery function supported by the ECDSA scheme.



Note that the formula is longer than that, you are missing the first steps for calculating x1. For secp256k1 curve (and all the Koblitz curves over Fp defined by SEC-2) since the cofactor of the curve (or h) is equal to 1, you may only recover up to 4 possible public keys from the ECDSA signature.

Yes, I looked into the source code that implements the signing of the Bitcoin message, and noticed that it uses the cycle for iterating over the 4 variants for the recovery flag.

But cofactor of other curves may not be the same. For instance curve25519 cofactor is 8 and if you were doing ECDSA on this curve2 then the number of possible recovered public keys would have been 16.

As far as I understand, the elliptic curve cofactor is calculated by the following formula:
h = n / r
If h is equal to 1, then the subgroup is a whole elliptic curve.

I know that curve25519 is one of the fastest elliptic curves widely used in the Diffie-Hellman key agreement protocol. Some anonymous alternative cryptocurrencies use this curve. But it seems that curve25519 has a disadvantage compared to secp256k1, because checking 16 variants for the recovery flag when signing a message consumes additional computational resources.


▄▄▄███████▄▄▄
▄▄█████▀▀''`▀▀█████▄▄
▄███P'            `YY██▄
▄██P'                  `Y██▄
███'                      `███
███'                         ███
▄██'   ▄█████▄▄  ,▄▄▄▄▄▄▄▄▄▄p   ███
▄██▀  ,████▀P▀███.`██████████P   ▀██▄
███[ ,████ __. ███.   ,▄████▀    ███
███[ ]████████████[  ▄████▀       ███
███[ `████   ,oo2 ▄████▀'       ,███
▀██▄  `████▄▄█████d███████████   ▄██▀
▀██.   `▀▀▀▀▀▀"  Y▀▀▀▀▀▀▀▀▀▀▀  ,██▀
███.                        ,███
▀██▄                      ▄██▀
▀███▄_                 ,███▀
▀███▄▄_          _▄▄███▀
▀▀████▄▄ooo▄▄█████▀
▀▀███████▀▀'

365

TM

EZ365 is a digital ecosystem that combines
the best aspects of online gaming, cryptocurrency
trading
and blockchain education. ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀

..WHITEPAPER..    ..INVESTOR PITCH..

.Telegram     Twitter   Facebook

                       .'M████▀▀██  ██
                      W█Ws'V██  ██▄▄███▀▀█
                     i█████m.~M████▀▀██  ███
                     d███████Ws'V██  ██████
                     ****M██████m.~███f~~__mW█
          ██▀▀▀████████=  Y██▀▀██W ,gm███████
      g█████▄▄▄██   █A~`_WW Y█  ██!,████████
   g▀▀▀███   ████▀▀`_m████i!████P W███  ██
 _███▄▄▄██▀▀▀███Af`_m███   █W ███A ]███  ██
__ ~~~▀▀▀▀▄▄▄█*f_m██████   ██i!██!i███████
Y█████▄▄▄▄__. i██▀▀▀██████████ █!,██████
 8█  █▀▀█████.!██   ██████████i! █████
 '█  █  █   █W M█▄▄▄██████   ██ !██
  !███▄▄█   ██i'██████████   ██
   Y███████████.]██████████████
   █   ███████b ███   ██████
   Y   █   █▀▀█i!██   ████
    V███   █  █W Y█████
      ~~▀███▄▄▄█['███
            ~~*██

Play

            │
    │      ███
    │      ███
    │      ███
    │   │  ███
   ███  │  ███
   ███ ███ ███
 │  ███ ███ ███
███ ███ ███ ███
███ ███  │   │
███ ███  │   │
 │   │
 │

Trade

           __▄▄████▄▄
     __▄▄███████████████▄▄▄
 _▄▄█████████▀▀~`,▄████████████▄▄▄
 ~▀▀████▀▀~`,_▄▄███████████████▀▀▀
   d█~  =▀███████████████▀▀
   ]█! m▄▄ '~▀▀▀████▀▀~~ ,_▄▄
  ,W█. *████▄▄__ '  __▄▄█████
  !██P  █████████████████████
   W█. - ██████████████████▀
  i██[   ~ ▀▀█████████▀▀▀
 g███!
Y███

Learn
Coding Enthusiast
Hero Member
*****
Offline Offline

Activity: 690
Merit: 1095


Novice C♯ Coder


View Profile WWW
September 12, 2019, 03:53:24 PM
 #5

I know that curve25519 is one of the fastest elliptic curves widely used in the Diffie-Hellman key agreement protocol. Some anonymous alternative cryptocurrencies use this curve.

Generally the speed is about the Digital Signature Algorithm (DSA) not the curve itself. This means in case of Curve25519, Edwards variant of DSA (or EDDSA) is used which is fast and makes the whole thing faster. Similarly using a curve like Secp256k1 with EC-DSA (what bitcoin has been using so far) is slower than using it with ECS-DSA (Schnorr algorithm).
Although I believe in case of these curves (Edwards curves) the form of the curve is contributing to the speed ups.

But it seems that curve25519 has a disadvantage compared to secp256k1, because checking 16 variants for the recovery flag when signing a message consumes additional computational resources.

Public key recovery is not something that we really need to perform. All transactions include the public key so there is no need to recover it. The only time such functions are called is for message signature verification, and such operation is only performed once so it doesn't matter if it takes 1 milisecond or 10!
Also remember that public key recovery is not possible on EDDSA in first place, I only mentioned it above as a hypothetical example for ECDSA case with h>1.

Projects List+Suggestion box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

Coin-1
Hero Member
*****
Offline Offline

Activity: 784
Merit: 721



View Profile
September 18, 2019, 06:44:06 PM
 #6

Public key recovery is not something that we really need to perform. All transactions include the public key so there is no need to recover it. The only time such functions are called is for message signature verification, and such operation is only performed once so it doesn't matter if it takes 1 milisecond or 10!

You're right. There is almost no difference between the time spent checking 4 or 16 variants. In any case, I wonder why such a helpful function as recovering the public key from a signature is [/u]not[/u] used in Bitcoin transactions?



I suggest introducing a new OP_RECOVER-PUBKEY-FROM-SIG instruction which will extract the public key (that is, the X and Y coordinates of the point lying on the secp256k1 elliptic curve) from an ECDSA signature using the recovery flag and will replace the top stack item.


Thus, the "scriptPubKey" output script for P2PK will have the following format:

Code:
OP_RECOVER-PUBKEY-FROM-SIG OP_DUP OP_HASH160 <pubKeyHash>
OP_EQUALVERIFY OP_CHECKSIG

By the way, the first three instructions can be combined into one OP_P2PK-USING-RECOVERY-FLAG.


Accordingly, the "scriptSig" input script used to redeem coins will look like this:

Code:
<sig> <recoveryFlag>


Obviously, the size of the <recoveryFlag> component is one byte, so its value is much smaller than the size of the <pubKey> component. Hence, the size of transactions will be significantly reduced, and as a result, the total number of transactions included in one Bitcoin block can be increased.


▄▄▄███████▄▄▄
▄▄█████▀▀''`▀▀█████▄▄
▄███P'            `YY██▄
▄██P'                  `Y██▄
███'                      `███
███'                         ███
▄██'   ▄█████▄▄  ,▄▄▄▄▄▄▄▄▄▄p   ███
▄██▀  ,████▀P▀███.`██████████P   ▀██▄
███[ ,████ __. ███.   ,▄████▀    ███
███[ ]████████████[  ▄████▀       ███
███[ `████   ,oo2 ▄████▀'       ,███
▀██▄  `████▄▄█████d███████████   ▄██▀
▀██.   `▀▀▀▀▀▀"  Y▀▀▀▀▀▀▀▀▀▀▀  ,██▀
███.                        ,███
▀██▄                      ▄██▀
▀███▄_                 ,███▀
▀███▄▄_          _▄▄███▀
▀▀████▄▄ooo▄▄█████▀
▀▀███████▀▀'

365

TM

EZ365 is a digital ecosystem that combines
the best aspects of online gaming, cryptocurrency
trading
and blockchain education. ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀

..WHITEPAPER..    ..INVESTOR PITCH..

.Telegram     Twitter   Facebook

                       .'M████▀▀██  ██
                      W█Ws'V██  ██▄▄███▀▀█
                     i█████m.~M████▀▀██  ███
                     d███████Ws'V██  ██████
                     ****M██████m.~███f~~__mW█
          ██▀▀▀████████=  Y██▀▀██W ,gm███████
      g█████▄▄▄██   █A~`_WW Y█  ██!,████████
   g▀▀▀███   ████▀▀`_m████i!████P W███  ██
 _███▄▄▄██▀▀▀███Af`_m███   █W ███A ]███  ██
__ ~~~▀▀▀▀▄▄▄█*f_m██████   ██i!██!i███████
Y█████▄▄▄▄__. i██▀▀▀██████████ █!,██████
 8█  █▀▀█████.!██   ██████████i! █████
 '█  █  █   █W M█▄▄▄██████   ██ !██
  !███▄▄█   ██i'██████████   ██
   Y███████████.]██████████████
   █   ███████b ███   ██████
   Y   █   █▀▀█i!██   ████
    V███   █  █W Y█████
      ~~▀███▄▄▄█['███
            ~~*██

Play

            │
    │      ███
    │      ███
    │      ███
    │   │  ███
   ███  │  ███
   ███ ███ ███
 │  ███ ███ ███
███ ███ ███ ███
███ ███  │   │
███ ███  │   │
 │   │
 │

Trade

           __▄▄████▄▄
     __▄▄███████████████▄▄▄
 _▄▄█████████▀▀~`,▄████████████▄▄▄
 ~▀▀████▀▀~`,_▄▄███████████████▀▀▀
   d█~  =▀███████████████▀▀
   ]█! m▄▄ '~▀▀▀████▀▀~~ ,_▄▄
  ,W█. *████▄▄__ '  __▄▄█████
  !██P  █████████████████████
   W█. - ██████████████████▀
  i██[   ~ ▀▀█████████▀▀▀
 g███!
Y███

Learn
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2842
Merit: 2513



View Profile
September 18, 2019, 10:28:02 PM
 #7

If you actually cared about size you'd drop the hash entirely-- the result is much smaller still.  Recovery is pretty slow, unbatchable (which means another 2x slowdown), and has a complicated patent situation.
Coin-1
Hero Member
*****
Offline Offline

Activity: 784
Merit: 721



View Profile
October 01, 2019, 10:51:31 AM
 #8

If you actually cared about size you'd drop the hash entirely-- the result is much smaller still.

As far as I know, the standard P2PKH transaction has an input ScriptSig that contains 107 bytes:
1) OP_PUSH (1 byte)
2) <sig> (72 bytes)
3) OP_PUSH (1 byte)
4) <compressedPubKey> (33 bytes)

If <recoveryFlag> (1 byte) is used instead of <compressedPubKey>, the ScriptSig will contain only 75 bytes, so the size of the input script will be reduced by about 30%. If a transaction has many inputs, the total result will be significant.


Recovery is pretty slow, unbatchable (which means another 2x slowdown),

As Coding Enthusiast said:
it doesn't matter if it takes 1 milisecond or 10!

In any case, OP_RECOVER-PUBKEY-FROM-SIG can be optional and will not greatly affect node performance.


and has a complicated patent situation.

If the public key recovery function from an ECDSA signature is covered by a patent, this is a problem. I am surprised why didn't the patent owners restrict services such as Brainwalletx which sign Bitcoin messages using the recovery flag.


▄▄▄███████▄▄▄
▄▄█████▀▀''`▀▀█████▄▄
▄███P'            `YY██▄
▄██P'                  `Y██▄
███'                      `███
███'                         ███
▄██'   ▄█████▄▄  ,▄▄▄▄▄▄▄▄▄▄p   ███
▄██▀  ,████▀P▀███.`██████████P   ▀██▄
███[ ,████ __. ███.   ,▄████▀    ███
███[ ]████████████[  ▄████▀       ███
███[ `████   ,oo2 ▄████▀'       ,███
▀██▄  `████▄▄█████d███████████   ▄██▀
▀██.   `▀▀▀▀▀▀"  Y▀▀▀▀▀▀▀▀▀▀▀  ,██▀
███.                        ,███
▀██▄                      ▄██▀
▀███▄_                 ,███▀
▀███▄▄_          _▄▄███▀
▀▀████▄▄ooo▄▄█████▀
▀▀███████▀▀'

365

TM

EZ365 is a digital ecosystem that combines
the best aspects of online gaming, cryptocurrency
trading
and blockchain education. ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀

..WHITEPAPER..    ..INVESTOR PITCH..

.Telegram     Twitter   Facebook

                       .'M████▀▀██  ██
                      W█Ws'V██  ██▄▄███▀▀█
                     i█████m.~M████▀▀██  ███
                     d███████Ws'V██  ██████
                     ****M██████m.~███f~~__mW█
          ██▀▀▀████████=  Y██▀▀██W ,gm███████
      g█████▄▄▄██   █A~`_WW Y█  ██!,████████
   g▀▀▀███   ████▀▀`_m████i!████P W███  ██
 _███▄▄▄██▀▀▀███Af`_m███   █W ███A ]███  ██
__ ~~~▀▀▀▀▄▄▄█*f_m██████   ██i!██!i███████
Y█████▄▄▄▄__. i██▀▀▀██████████ █!,██████
 8█  █▀▀█████.!██   ██████████i! █████
 '█  █  █   █W M█▄▄▄██████   ██ !██
  !███▄▄█   ██i'██████████   ██
   Y███████████.]██████████████
   █   ███████b ███   ██████
   Y   █   █▀▀█i!██   ████
    V███   █  █W Y█████
      ~~▀███▄▄▄█['███
            ~~*██

Play

            │
    │      ███
    │      ███
    │      ███
    │   │  ███
   ███  │  ███
   ███ ███ ███
 │  ███ ███ ███
███ ███ ███ ███
███ ███  │   │
███ ███  │   │
 │   │
 │

Trade

           __▄▄████▄▄
     __▄▄███████████████▄▄▄
 _▄▄█████████▀▀~`,▄████████████▄▄▄
 ~▀▀████▀▀~`,_▄▄███████████████▀▀▀
   d█~  =▀███████████████▀▀
   ]█! m▄▄ '~▀▀▀████▀▀~~ ,_▄▄
  ,W█. *████▄▄__ '  __▄▄█████
  !██P  █████████████████████
   W█. - ██████████████████▀
  i██[   ~ ▀▀█████████▀▀▀
 g███!
Y███

Learn
Coding Enthusiast
Hero Member
*****
Offline Offline

Activity: 690
Merit: 1095


Novice C♯ Coder


View Profile WWW
October 01, 2019, 11:15:12 AM
 #9

As Coding Enthusiast said:
it doesn't matter if it takes 1 milisecond or 10!

It doesn't matter when you are verifying a signed message (eg. proof of ownership), that would be a 1 time call to recover function. So that function being slow doesn't affect anything.
But when you are verifying transaction signatures, most of the times you are doing it hundreds of thousands of times (eg. a new block that contains 2000-3000 transactions or syncing your node and downloading ~600k blocks). In this case the slowness of that function is very important. And it is indeed quite slow:
2x square root (which a ModPow for secp256k1 curve with 256 bit numbers)
6x check point on curve
4x modular multiplicative inverse
6x point multiplication
2x point addition

In comparison the signature verification is:
1x modular multiplicative inverse
2x point multiplication
1x point addition
2x simple integer multiplication

Projects List+Suggestion box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!