October 18, 2017 at 11:04Mathematical Foundations of Bitcoin Blockchain
Today, Bitcoin continues to gain popularity, and the industry develops new applications for working with cryptocurrency. One of the reasons for this popularity is the strict mathematical base on which Bitcoin is built.
Thanks to this, the system operates in conditions of a complete lack of trust between network participants, excluding the impact of the human factor.
Therefore, in today's article we would like to talk about the mathematical foundations of the Bitcoin blockchain - elliptic curves, ECDSA and keys. / Image Hernán Piñera CC BY The fundamental part of bitcoin is cryptographic algorithms. In particular, the ECDSA algorithm is the Elliptic Curve Digital Signature Algorithm, which uses elliptic curves (
curve elliptic ) and finite fields ( Finite field ) for signature data to a third party to verify the authenticity of the signature, excluding the possibility of its counterfeiting. ECDSA uses different procedures for signing and verification, consisting of several arithmetic operations.
An elliptic curve over a field K is a cubic curve over the algebraic closure of a field K defined by an equation of the third degree with coefficients from the field K and a “point at infinity”. One form of elliptic curves is the Weierstrass curves.
y² = x³ + ax + b
For the coefficients a = 0 and b = 7 (used in bitcoin), the function graph takes the following form:
Elliptic curve
Elliptic curves have several interesting properties, for example, a non-vertical line intersecting two non-tangent points on a curve intersects third point on the curve. The sum of two points on the curve P + Q is called the point R, which is the reflection of the point -R (constructed by continuing the straight line (P; Q) to the intersection with the curve) relative to the X axis.
The sum of two points on the curve ( source )
If you draw a straight line through two points having coordinates of the form P (a, b) and Q (a, -b), then it will be parallel to the ordinate axis. In this case, there will be no third intersection point. To solve this problem, the so-called point of infinity is introduced, denoted as O. Therefore, if there is no intersection, the equation takes the following form P + Q = O.
If we want to add the point to itself (double it), then in this case the tangent to the Q point is simply drawn. The obtained intersection point is reflected symmetrically with respect to the X axis.
Doubling the point ( source )
These operations allow scalar multiplication of the point R = k * P, adding the point P to itself k times. However, note that to work with large numbers, faster methods are used.
In elliptical cryptography (ECC), the same curve is used, only considered over some finite field. The final field in the context of ECC can be represented as a predefined set of positive numbers in which the result of each calculation should appear.
y² = x³ + ax + b (mod p)
For example, 9 mod 7 = 2. Here we have a finite field from 0 to 6, and all operations modulo 7, no matter what number they are carried out, will give a result that falls into this range.
All the above properties (addition, multiplication, point at infinity) for such a function remain valid, although the graph of this curve will not resemble an elliptic curve. The bitcoin elliptic curve, y² = x³ + 7, defined on a finite field modulo 67, is as follows:
Bitcoin elliptic curve defined on a finite field modulo 67 ( source )
This is the set of points at which all x and y values are integers between 0 and 66. The straight lines drawn on this graph will now “wrap” around fields, as soon as they reach barrier 67, and continue from its other end, maintaining the same slope, but with a shift. For example, the addition of points (2, 22) and (6, 25) in this particular case looks like this:
Addition of points (2, 22) and (6, 25) ( source )
If you want to see how other elliptic curves look, then experiment possible on this site .
The Bitcoin protocol contains a set of parameters for the elliptic curve and its final field, so that each user uses a strictly defined set of equations. Among the fixed parameters, the equation of the curve (equation), the value of the field modulus (prime modulo), the base point on the curve (base point) and the order of the base point (order) are distinguished. You can read about calculating the order of the base point here . This parameter is specially selected and is a very large prime number.
In the case of bitcoin , the following values are used:
Elliptic curve equation: y² = x³ + 7
Simple module: 2 256 - 2 32 - 2 9 - 2 8 - 2 7- 2 6 - 2 4 - 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
Base point:
04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
bold coordinate X in hexadecimal notation. It immediately follows the Y coordinate.
Order: FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
This set of parameters for an elliptic curve is known as secp256k1 and is part of the SEC (Standards for Efficient Cryptography) family of standards proposed for use in cryptography. In bitcoin, the secp256k1 curve is used in conjunction with the ECDSA (elliptic curve digital signature algorithm). In ECDSA, a secret key is a random number between a unit and an order value. The public key is formed on the basis of the secret: the latter is multiplied by the value of the base point. The equation is as follows:
Public key = secret key * G
This shows that the maximum number of secret keys (therefore, bitcoin addresses) is, of course, equal to the order. However, the order is an incredibly large number, so it’s unrealistic to randomly or intentionally pick up another user's secret key.
The calculation of the public key is performed using the same operations of doubling and adding points. This is a trivial task that an ordinary personal computer or smartphone can solve in milliseconds. But the inverse problem (obtaining a secret key from the public) is a discrete logarithm problem , which is considered computationally complex (although there is no rigorous proof of this fact). The best known algorithms for solving it, like Ro Pollardhave exponential complexity. For secp256k1, to solve the problem, you need about 2,128 operations, which will require computing time on a regular computer, comparable to the lifetime of the Universe.
When a secret / public key pair is received, it can be used to sign data. This data can be of any length. Usually, the first step is to hash the data in order to obtain a unique value with the number of bits equal to the bit order of the curve (256). After hashing, the z data signing algorithm is as follows. Here, G is the base point, n is the order, and d is the secret key.
After receiving the data and signing it, a third party, knowing the public key, can verify it. The steps to verify the signature are as follows (Q is the public key):
In fact,
uG + vQ = u + vdG = (u + vd) G = (zs -1 + rds -1 ) G = (z + rd) s -1 G = kG
The last equality uses the definition of s at the stage of signature creation .
ECDSA security is related to the complexity of the secret key search task described above. In addition, the security of the original scheme depends on the "randomness" of the choice of k when creating the signature. If you use the same value of k more than once, then you can extract the secret key from the signatures, which happened with the PlayStation 3. Therefore, modern ECDSA implementations, including those used in most bitcoin wallets, generate k deterministically based on the secret key and Signed message.
PS Bitfury Group Russia in Vk and Fb .
Thanks to this, the system operates in conditions of a complete lack of trust between network participants, excluding the impact of the human factor.
Therefore, in today's article we would like to talk about the mathematical foundations of the Bitcoin blockchain - elliptic curves, ECDSA and keys. / Image Hernán Piñera CC BY The fundamental part of bitcoin is cryptographic algorithms. In particular, the ECDSA algorithm is the Elliptic Curve Digital Signature Algorithm, which uses elliptic curves (
curve elliptic ) and finite fields ( Finite field ) for signature data to a third party to verify the authenticity of the signature, excluding the possibility of its counterfeiting. ECDSA uses different procedures for signing and verification, consisting of several arithmetic operations.
Elliptical curves
An elliptic curve over a field K is a cubic curve over the algebraic closure of a field K defined by an equation of the third degree with coefficients from the field K and a “point at infinity”. One form of elliptic curves is the Weierstrass curves.
y² = x³ + ax + b
For the coefficients a = 0 and b = 7 (used in bitcoin), the function graph takes the following form:
Elliptic curve
Elliptic curves have several interesting properties, for example, a non-vertical line intersecting two non-tangent points on a curve intersects third point on the curve. The sum of two points on the curve P + Q is called the point R, which is the reflection of the point -R (constructed by continuing the straight line (P; Q) to the intersection with the curve) relative to the X axis.
The sum of two points on the curve ( source )
If you draw a straight line through two points having coordinates of the form P (a, b) and Q (a, -b), then it will be parallel to the ordinate axis. In this case, there will be no third intersection point. To solve this problem, the so-called point of infinity is introduced, denoted as O. Therefore, if there is no intersection, the equation takes the following form P + Q = O.
If we want to add the point to itself (double it), then in this case the tangent to the Q point is simply drawn. The obtained intersection point is reflected symmetrically with respect to the X axis.
Doubling the point ( source )
These operations allow scalar multiplication of the point R = k * P, adding the point P to itself k times. However, note that to work with large numbers, faster methods are used.
Elliptic curve over a finite field
In elliptical cryptography (ECC), the same curve is used, only considered over some finite field. The final field in the context of ECC can be represented as a predefined set of positive numbers in which the result of each calculation should appear.
y² = x³ + ax + b (mod p)
For example, 9 mod 7 = 2. Here we have a finite field from 0 to 6, and all operations modulo 7, no matter what number they are carried out, will give a result that falls into this range.
All the above properties (addition, multiplication, point at infinity) for such a function remain valid, although the graph of this curve will not resemble an elliptic curve. The bitcoin elliptic curve, y² = x³ + 7, defined on a finite field modulo 67, is as follows:
Bitcoin elliptic curve defined on a finite field modulo 67 ( source )
This is the set of points at which all x and y values are integers between 0 and 66. The straight lines drawn on this graph will now “wrap” around fields, as soon as they reach barrier 67, and continue from its other end, maintaining the same slope, but with a shift. For example, the addition of points (2, 22) and (6, 25) in this particular case looks like this:
Addition of points (2, 22) and (6, 25) ( source )
If you want to see how other elliptic curves look, then experiment possible on this site .
ECDSA in Bitcoin
The Bitcoin protocol contains a set of parameters for the elliptic curve and its final field, so that each user uses a strictly defined set of equations. Among the fixed parameters, the equation of the curve (equation), the value of the field modulus (prime modulo), the base point on the curve (base point) and the order of the base point (order) are distinguished. You can read about calculating the order of the base point here . This parameter is specially selected and is a very large prime number.
In the case of bitcoin , the following values are used:
Elliptic curve equation: y² = x³ + 7
Simple module: 2 256 - 2 32 - 2 9 - 2 8 - 2 7- 2 6 - 2 4 - 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
Base point:
04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
bold coordinate X in hexadecimal notation. It immediately follows the Y coordinate.
Order: FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
This set of parameters for an elliptic curve is known as secp256k1 and is part of the SEC (Standards for Efficient Cryptography) family of standards proposed for use in cryptography. In bitcoin, the secp256k1 curve is used in conjunction with the ECDSA (elliptic curve digital signature algorithm). In ECDSA, a secret key is a random number between a unit and an order value. The public key is formed on the basis of the secret: the latter is multiplied by the value of the base point. The equation is as follows:
Public key = secret key * G
This shows that the maximum number of secret keys (therefore, bitcoin addresses) is, of course, equal to the order. However, the order is an incredibly large number, so it’s unrealistic to randomly or intentionally pick up another user's secret key.
The calculation of the public key is performed using the same operations of doubling and adding points. This is a trivial task that an ordinary personal computer or smartphone can solve in milliseconds. But the inverse problem (obtaining a secret key from the public) is a discrete logarithm problem , which is considered computationally complex (although there is no rigorous proof of this fact). The best known algorithms for solving it, like Ro Pollardhave exponential complexity. For secp256k1, to solve the problem, you need about 2,128 operations, which will require computing time on a regular computer, comparable to the lifetime of the Universe.
When a secret / public key pair is received, it can be used to sign data. This data can be of any length. Usually, the first step is to hash the data in order to obtain a unique value with the number of bits equal to the bit order of the curve (256). After hashing, the z data signing algorithm is as follows. Here, G is the base point, n is the order, and d is the secret key.
- Selects an integer k ranging from 1 to n-1
- The point (x, y) = k * G is calculated using scalar multiplication
- Find r = x mod n. If r = 0, then return to step 1
- Find s = (z + r * d) / k mod n. If s = 0, then return to step 1
- The resulting pair (r, s) is our signature
After receiving the data and signing it, a third party, knowing the public key, can verify it. The steps to verify the signature are as follows (Q is the public key):
- Verify that both r and s are in the range 1 to n-1
- Calculates w = s -1 mod n
- Calculates u = z * w mod n
- Calculates v = r * w mod n
- The point (x, y) = uG + vQ is calculated
- If r = x mod n, then the signature is correct, otherwise it is invalid
In fact,
uG + vQ = u + vdG = (u + vd) G = (zs -1 + rds -1 ) G = (z + rd) s -1 G = kG
The last equality uses the definition of s at the stage of signature creation .
ECDSA security is related to the complexity of the secret key search task described above. In addition, the security of the original scheme depends on the "randomness" of the choice of k when creating the signature. If you use the same value of k more than once, then you can extract the secret key from the signatures, which happened with the PlayStation 3. Therefore, modern ECDSA implementations, including those used in most bitcoin wallets, generate k deterministically based on the secret key and Signed message.
PS Bitfury Group Russia in Vk and Fb .