Table of Contents
The Elliptic Curve Digital Signature Algorithm (ECDSA) is based on Elliptic Curve Cryptography (ECC) and is used to generate keys, authenticate, sign, and verify messages. Signatures provide a means for authentication in blockchain technology, allowing operations, such as sending transactions, to be verified that they have originated from the intended signer. But, how do they work and how are they created?
This article will teach you the basics of cryptography to understand the mechanisms underpinning authentication in Ethereum: ECDSA signatures, why they are used, how they work, and the different uses for ECDSA in Ethereum.
Proof of ownership in Ethereum is achieved using public and private key pairs that are used to create digital signatures. Signatures are analogous to having to provide personal ID when withdrawing from the bank - the person needs to verify that they are the owner of the account.
This is known as public key cryptography (asymmetric encryption- more on this later) and is a cryptographic method that uses a key pair system:
It is difficult (for simplicity, can be assumed impossible) to calculate the private key from the public key, even for a computer (note that there is an exception to this assumption that will be discussed later). This means that knowledge of the private key grants access to the account whereas access to the public key does not.
These public and private key pairs define Ethereum externally owned accounts (EOAs) and provide a means for interacting with the blockchain by signing data and sending transactions, without others being able to access accounts they do not own. An Ethereum address is used as identification and is the last 20 bytes of the hash of the public key controlling the account.
Signatures provide a means of cryptographic authentication in blockchain technology, serving as a unique “fingerprint”, forming the backbone of blockchain transactions. They are used to validate computation performed off-chain and authorize transactions on behalf of a signer.
*This is important when considering replay attacks. To prevent replay, each signature is required to be unique. This is achieved by including a nonce, or “number used once”, as part of the message. The majority of the time, the creation of digital signatures is abstracted away from the user, for example when signing a transaction in MetaMask. However, when implementing signatures into a smart contract, extra data, including a nonce and chain ID, should be added to the message to prevent replay. For more information on preventing replay attacks, refer to this comprehensive guide.
The Elliptic Curve Digital Signature Algorithm (ECDSA) is a signature algorithm based on Elliptic Curve Cryptography (ECC). It is the cryptographic algorithm used to create keys and create and verify signatures used for authentication. It is useful to understand how it works on a high level in order to implement signature verification directly into smart contracts and understand how to ensure these smart contracts are secure.
The elliptic curve, secp256k1, is the specific curve used in ECDSA in Ethereum, chosen for its interoperability with Bitcoin, efficiency, and security. As with all elliptic curves, it is symmetrical about the x-axis. Therefore, for every (r,s,v) coordinate, more on what this means shortly, another coordinate exists that returns the same valid result. This means that two signatures exist for one signer at any point on the curve, allowing attackers to compute the second, valid signature without requiring the signer’s private key. This can lead to signature malleability which is a form of replay attack.
This curve can be visualized as:
Source: SECP256k1 curve
The secp256k1 curve has:
G is a specific point on the elliptic curve: (***x*** = 55066263022277343669578718895168534326250603453777594175500187360389116729240, ***y*** = 32670510020758816978083085130507043184471273380659243275938904335757337482424)n of the subgroup of elliptic curve points, generated by G, which defines the length of the private keys (e.g. 256 bits) and is a prime number: 115792089237316195423570985008687907852837564279074904382605163141518161494337It is not crucial to understand the meaning of these constants other than to understand that they exist and are used in subsequent calculations.
Ethereum ECDSA signatures contain three integers: r, s, and v. The signature can be notated as (r, s, v):
r (integer in the range [1...n-1]): represents the x-coordinate on the elliptic curve based on a random point R on the curve.s (integer ****in the range [1...n-1]): serves as proof of the signer’s knowledge of the private key p. s is calculated using a random unique nonce k, ensuring that the signature is unique every time.v is used to recover public keys from the value of r and represents the index of the point on the elliptic curve used for the signature. The recovery process generates multiple solutions for the possible value of R. The addition of v specifies which solution is required.— For more information on ECDSA signatures, visit the Practical Cryptography for Developers documentation.
In Ethereum, ECDSA is used for the following:
Let’s go through how each of these works in more detail:
An ECDSA key pair consists of the following:
p: generated as a random integer in the range [0…n-1]pubKey = p * GThe signature (r, s, v) secures the private key due to the complexity of the Elliptic Curve Discrete Logarithm Problem (ECDLP). This problem involves finding an integer p (the private key) such that
pG = Q
where G is the Generator point and Q is the public key.
Given the public key and the generator point, it is computationally infeasible to derive the private key, therefore providing security for the ECDSA. One way to understand this is by taking two prime numbers and multiplying them together e.g.
134669 * 2467 = 332228423
Given the result, it would be very difficult (practically impossible) to calculate the input prime numbers, even for a computer. The exception to the assumption that this calculation is quantum computing. Quantum computing provides a way of solving this problem, thus compromising the security of ECDSA signatures by being able to extract the private key from the public key.
The ECDSA signing algorithm takes a message and a private key and produces a signature, a pair of integers (r, s).
The ECDSA signing algorithm works by:
h = hash(msg)
R = k * G and take its x-coordinate: r = R.xs using the formula:s = k^-1 * (h + p * r) mod n
where p is the signer’s private key, and the order n
The ECDSA signature verification algorithm takes the signed message msg and the signature produced from the signing algorithm and the public key pubKey. The output is a boolean representing whether the signature is valid or invalid.
The ECDSA signature verification algorithm works by converting s back to R (R’) using the public key and message hash. The recovered R's x-coordinate r' is compared with r from the signature:
s1 of the signature proof:s1 = s^-1 (mod n)
R' = (h * s1) * G + (r * s1) * pubKey
r' from R': r' = R'.xr' == recrecover is the EVM precompile that enables the retrieval of the signer's address of a message that has been signed using their private key using ECDSA. It allows smart contracts to verify the integrity of the signature and retrieve the signer.
The article serves as a comprehensive guide to ECDSA, covering its role in authentication, signature creation, and verification. It delves into the intricacies of key generation and the security aspects of asymmetric encryption. Understanding these concepts is vital for grasping the significance of signatures in smart contract security.
