Difference between revisions of "Elliptic Curve Digital Signature Algorithm"

 
(19 intermediate revisions by 3 users not shown)
Line 1: Line 1:
'''Elliptic Curve Digital Signature Algorithm''' or '''ECDSA''' is a cryptographic algorithm used by Bitcoin to ensure that funds can only be spent by their rightful owners.
+
'''Elliptic Curve Digital Signature Algorithm''' or '''ECDSA''' is a cryptographic algorithm used by Bitcoin to ensure the effective and secure control of ownership of funds.
  
 
A few concepts related to ECDSA:
 
A few concepts related to ECDSA:
* [[Private Keys|private key]]: A secret number, known only to the person that generated it.  A private key can be a randomly generated number but in 2019 most wallets use deterministic key schemes derived from [[BIP 0032]]. In Bitcoin, someone with the private key that corresponds to funds on the [[block chain]] can spend the funds.  In Bitcoin, a private key is a single unsigned 256 bit integer (32 bytes). This integer is used as a co-ordinate on an elliptic curve and used to find its own unique path through the math to the public key.
+
* [[Private Keys|private key]]: A secret number, known only to the person that generated it.  A private key can be a randomly generated number but in 2019 most wallets use deterministic key schemes derived from [https://github.com/bitcoin/bips/tree/master/bip-0032 BIP 0032]. In Bitcoin, someone who can prove ownership of unspent outputs can use the private key to spend the funds.  In Bitcoin, a private key is a single unsigned 256-bit integer (32 bytes).  
* public key: A number that corresponds to a private key, but does not need to be kept secret.  A public key can be calculated from a private key, but not vice versa.  A public key can be used to determine if a signature is genuine by using ECDSA to validate that a signature was generated by the private key that corresponds to the public key that has been proffered, without requiring the private key to be divulged.  In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called ''x''. Uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called ''x'' and ''y'' (2 * 32 bytes). The prefix of a compressed key allows for the ''y'' value to be derived from the ''x'' value.
+
* public key: A coordinate that corresponds to a private key but does not need to be kept secret.  A public key can be calculated from a private key, but not vice versa.  A public key can be used to determine if a signature is genuine by using ECDSA to validate that a signature was generated by the private key, that corresponds to the public key that has been proffered, without requiring the private key to be divulged.  In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called ''x''. Uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called ''x'' and ''y'' (2 * 32 bytes). The prefix of a compressed key allows for the ''y'' value to be derived from the ''x'' value.
* [[Protocol#Signatures|signatures]]: A string of bytes proving that a private key was used to sign a message. A signature is mathematically generated from a [[hash]] of the message being signed and a private key. The signature itself is two numbers known as ''r'' and ''s'' and the message being signed is the Bitcoin transaction (minus the signature data). With the public key, a mathematical algorithm (signature verification) can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. Signatures are either 73, 72, or 71 bytes long, with probabilities approximately 25%, 50% and 25% respectively, although sizes even smaller than that are possible with exponentially decreasing probability.
+
* [[Protocol#Signatures|signatures]]: A string of bytes proving that a private key was used to sign a message. A signature is mathematically generated from a [[SHA-256|hash]] of the message being signed and a private key. The signature itself is two numbers known as ''r'' and ''s'' and the message being signed is the Bitcoin transaction (minus the signature data). With the public key, a mathematical algorithm (signature verification) can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. Signatures are usually 71, 72, or 73 bytes long, with probabilities approximately 25%, 50% and 25% respectively.
 +
 
 +
In Bitcoin, elliptic curve signatures must sign a hash of a "transaction message" which can be reproduced easily by nodes validating the signature  during the process of validating transactions.
 +
The message that is hashed for the signature contains the following elements concatenated into a single string:
 +
# nVersion - Transaction version (4 bytes, little endian)
 +
# hashPrevouts - concatenation of input source / sources (32 byte hash)
 +
# hashSequence - concatenation of input nSequence value / values (32 byte hash)
 +
# outpoint - Outpoint for input being spent (TXID / Vout) (32 byte hash + 4 bytes, little endian)
 +
# scriptLen - Length of the input scriptPubKey for input being spent ([[VarInt| VarInt format]])
 +
# scriptPubKey = Script for input being spent  (scriptLen bytes)
 +
# value - Qty of satoshis being spent by input (8 bytes, little endian)
 +
# nSequence - Sequence value for input being spent (4 bytes, little endian)
 +
# hashOutputs - Hash of output/outputs being signed (32 byte hash)
 +
# nLocktime - Transaction locktime (4 bytes, Little Endian [[NLocktime_and_nSequence#NLocktime|locktime format]])
 +
# Sighash flag (4 bytes, XX000000 where XX is Sighash Flag)
 +
 
 +
==Variations based on [[Sighash flags]]==
 +
Depending on the Sighash flag that is set, the signature message can be tailored to include or exclude various elements of the transaction.
 +
 
 +
===hashPrevouts===
 +
If the ANYONECANPAY flag is *not* set, hashPrevouts is the double SHA256 of the serialization of all input outpoints.
 +
e.g. SHA256D(CAT(TXID1/Out1, TXID2/Out2, TXID3/Out3)
 +
 
 +
If the ANYONECANPAY flag is set, hashPrevouts is a uint256 of 0x0000......0000.
 +
 
 +
===hashSequence===
 +
If *none* of the ANYONECANPAY, SINGLE, NONE Sighash flags are set, hashSequence is the double SHA256 of the serialization of nSequence of all inputs.
 +
 
 +
e.g. SHA256D(CAT(input1.nSequence, input2.nSequence, input3.nSequence)
 +
 
 +
If one or more of the ANYONECANPAY, SINGLE or NONE Sighash flags are set, hashSequence is a uint256 of 0x0000......0000.
 +
 
 +
===hashOutputs===
 +
If the ALL Sighash flag is set, hashOutputs is the double SHA256 of the serialization of all outputs in [[Bitcoin_Transactions#Format_of_a_Transaction_Output|Output format]].
 +
e.g. SHA256D(CAT(value1/scriptLen1/scriptPubkey1, value2/scriptLen2/scriptPubkey2, value3/scriptLen3/scriptPubkey3)
 +
 
 +
If the SINGLE Sighash flag is set and the input index is smaller than the number of outputs, hashOutputs is the double SHA256 of the output of the same index as the input in [[Bitcoin_Transactions#Format_of_a_Transaction_Output|Output format]].
 +
 
 +
Otherwise, hashOutputs is a uint256 of 0x0000......0000.[7]
 +
 
 +
==Applying SIGHASH flags==
 +
 
 +
All signatures include [[SIGHASH flags]] which tell the transaction validator which parts of the message have been used in the construction of the message hash.
  
 
==See also==
 
==See also==
Line 11: Line 53:
 
==External Links==
 
==External Links==
 
* [https://en.wikipedia.org/wiki/Elliptic_Curve_DSA Elliptic Curve Digital Signature Algorithm - Wikipedia article]
 
* [https://en.wikipedia.org/wiki/Elliptic_Curve_DSA Elliptic Curve Digital Signature Algorithm - Wikipedia article]
 +
 +
==Attribution==
 +
This content is based on content sourced from https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_Algorithm under [https://creativecommons.org/licenses/by/3.0/ Creative Commons Attribution 3.0]. Although it may have been extensively revised and updated, we acknowledge the original authors.

Latest revision as of 23:39, 14 February 2023

Elliptic Curve Digital Signature Algorithm or ECDSA is a cryptographic algorithm used by Bitcoin to ensure the effective and secure control of ownership of funds.

A few concepts related to ECDSA:

  • private key: A secret number, known only to the person that generated it. A private key can be a randomly generated number but in 2019 most wallets use deterministic key schemes derived from BIP 0032. In Bitcoin, someone who can prove ownership of unspent outputs can use the private key to spend the funds. In Bitcoin, a private key is a single unsigned 256-bit integer (32 bytes).
  • public key: A coordinate that corresponds to a private key but does not need to be kept secret. A public key can be calculated from a private key, but not vice versa. A public key can be used to determine if a signature is genuine by using ECDSA to validate that a signature was generated by the private key, that corresponds to the public key that has been proffered, without requiring the private key to be divulged. In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called x. Uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called x and y (2 * 32 bytes). The prefix of a compressed key allows for the y value to be derived from the x value.
  • signatures: A string of bytes proving that a private key was used to sign a message. A signature is mathematically generated from a hash of the message being signed and a private key. The signature itself is two numbers known as r and s and the message being signed is the Bitcoin transaction (minus the signature data). With the public key, a mathematical algorithm (signature verification) can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. Signatures are usually 71, 72, or 73 bytes long, with probabilities approximately 25%, 50% and 25% respectively.

In Bitcoin, elliptic curve signatures must sign a hash of a "transaction message" which can be reproduced easily by nodes validating the signature during the process of validating transactions. The message that is hashed for the signature contains the following elements concatenated into a single string:

  1. nVersion - Transaction version (4 bytes, little endian)
  2. hashPrevouts - concatenation of input source / sources (32 byte hash)
  3. hashSequence - concatenation of input nSequence value / values (32 byte hash)
  4. outpoint - Outpoint for input being spent (TXID / Vout) (32 byte hash + 4 bytes, little endian)
  5. scriptLen - Length of the input scriptPubKey for input being spent ( VarInt format)
  6. scriptPubKey = Script for input being spent (scriptLen bytes)
  7. value - Qty of satoshis being spent by input (8 bytes, little endian)
  8. nSequence - Sequence value for input being spent (4 bytes, little endian)
  9. hashOutputs - Hash of output/outputs being signed (32 byte hash)
  10. nLocktime - Transaction locktime (4 bytes, Little Endian locktime format)
  11. Sighash flag (4 bytes, XX000000 where XX is Sighash Flag)

Variations based on Sighash flags

Depending on the Sighash flag that is set, the signature message can be tailored to include or exclude various elements of the transaction.

hashPrevouts

If the ANYONECANPAY flag is *not* set, hashPrevouts is the double SHA256 of the serialization of all input outpoints. e.g. SHA256D(CAT(TXID1/Out1, TXID2/Out2, TXID3/Out3)

If the ANYONECANPAY flag is set, hashPrevouts is a uint256 of 0x0000......0000.

hashSequence

If *none* of the ANYONECANPAY, SINGLE, NONE Sighash flags are set, hashSequence is the double SHA256 of the serialization of nSequence of all inputs.

e.g. SHA256D(CAT(input1.nSequence, input2.nSequence, input3.nSequence)

If one or more of the ANYONECANPAY, SINGLE or NONE Sighash flags are set, hashSequence is a uint256 of 0x0000......0000.

hashOutputs

If the ALL Sighash flag is set, hashOutputs is the double SHA256 of the serialization of all outputs in Output format. e.g. SHA256D(CAT(value1/scriptLen1/scriptPubkey1, value2/scriptLen2/scriptPubkey2, value3/scriptLen3/scriptPubkey3)

If the SINGLE Sighash flag is set and the input index is smaller than the number of outputs, hashOutputs is the double SHA256 of the output of the same index as the input in Output format.

Otherwise, hashOutputs is a uint256 of 0x0000......0000.[7]

Applying SIGHASH flags

All signatures include SIGHASH flags which tell the transaction validator which parts of the message have been used in the construction of the message hash.

See also

External Links

Attribution

This content is based on content sourced from https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_Algorithm under Creative Commons Attribution 3.0. Although it may have been extensively revised and updated, we acknowledge the original authors.