Introduce secp256k1 module with field and group classes to test framework #26222

[rajarshimaitra]

Session Details

• Date: 08-06-2023
• Time: IST 20:00 (UTC 14:30)
• PR: Introduce secp256k1 module with field and group classes to test framework bitcoin/bitcoin#26222
• Context: [Crypto]
• Difficulty: Beginer
• Language: [python]

Learning

• Elliptic Curve Cryptography.
• Fields and Groups.
• Public Keys, Private Keys, Signature, Verification.
• Python Implementation of basic crypto.
• Testing cryptographic primitives.
• Functional test framework.

Note: Drop your PR and review related questions below

Summary

This PR redefines the cryptographic primitives used in the Bitcoin core's functional testing framework. And adds a new module in the python framework as secp256k1.py. This module includes all the cryptographic primitives. So the way to review this PR is to understand some fun basic crypto maths.

To start with, Cover the first 3 chapters of the Programming Bitcoin Book.
If you haven't done programming Bitcoin already, skim through the concepts and skip the exercises.

A free PDF is available here

Cover the below concepts from the book

• Modulo arithmatic and finite fields
• Groups and group operations
• Elliptic Curve Operations
• Public Key and Private Key

Theory

Bitcoin uses secp256k1 elliptic curve for all its cryptographic operations like key/address generation, digital signatures etc. See curve specifications for the full curve details.

Mathematically:

• Elliptic curves are groups.
• A Public key is denoted by a point (x, y coordinate) in the curve, and they are theoretically group elements.
• A point is constructed by two coordinates, x and y, and these are field elements.
• A Private Key is another field element from which a curve point on the elliptic curve is generated.
• A Generator Point is a predefined point (group element) on the elliptic curve, which is used to "generate" the public key, from the private key.

Questions

In the questions below, GE = group element and FE = field element

1. Did you review the PR? Concept ACK, approach ACK, tested ACK, or NACK? What was your review approach?
2. Write a test using class FE for basic field element operations - addition, multiplication.
3. Verify Fermat's little theorem using class FE.
4. class GE represents infinity explicitly. what is point at infinity in an elliptic curve? Why do we need this point? Where are regions in the code where we need to handle infinity scenarios properly?
5. What's a generator point in an elliptic curve?
6. Are there any downsides to rewriting the elliptic curve logic using fields/groups?

[stratospher]

Summary

Elliptic curve operations can be implemented without introducing field and group logic. This was how elliptic curve operations were done in the test framework before this PR. Fields and groups are just powerful tools that can be used to generalize and study elliptic curves. Rewriting elliptic curve operations using these tools makes the code much more intuitive to understand and easier to read. Field logic needs to be introduced in the test framework to implement algorithms like Elligator Swift to transmit public keys securely. Using field/group logic for all the elliptic curve operations improves code consistency.

1. Did you review the PR? Concept ACK, approach ACK, tested ACK, or NACK? What was your review approach?

Concept/tested ACK by the participants, who found the code much more intuitive.

2. Diophantus from Ancient Greece in his famous work "Arithmetica" discovered a way to find another rational point on an elliptic curve. Modern cryptography, which uses these elliptic curves is a very recent 21st century phenomenon. Pretty sure Diophantus didn't in his wildest dreams imagine that elliptic curves would find such widespread use in cryptography/magic internet money :) How did something which was discovered 1800 years ago out of curiosity(maybe) end up being used in modern cryptography?

Let's into the evolution of elliptic curves, abstract algebra and modern cryptography over time:

1. Elliptic curves
   • 1800 years ago, Diophantus from Ancient Greece (the Father of Algebra) was interested in solving a problem to find another rational point on an elliptic curve.
   • Only 6 of his original 13 books survived. The rest were destroyed when the library of Alexandria was burned down.
   • 4 of his books somehow made it to the Vatican library, where they stayed untouched for another 1000 years until someone came in the 1500s and translated them into Latin which mathematicians could understand. That's how classical number theory was born.
2. Abstract algebra (which deals with studying algebraic structures like fields/groups)
   • in 1800s, they could solve equations of degree 1-4 but not equations with higher degree
   • A French Mathematician, Évariste Galois(1811 - 1832) solved this problem by using something called a group
   • Groups evolved as a general tool that could solve problems in different fields in Math (geometry, number theory, topology, algebra). The full power of this tool is studied in Abstract Algebra.
   • As more work went into this field, new algebraic structures like fields emerged.
3. Elliptic curve cryptography
   • Modern cryptography emerged in 1976 with the creation of Diffie-Hellman key exchange
   • In 1977, an implementation of public cryptography using RSA was published
   • The security of RSA relies on the practical difficulty of factoring the product of two large prime numbers.
   • In 1985, another approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields, called Elliptic curve cryptography (ECC) was suggested.
   • The security of ECC relies on the hardness of the elliptic curve discrete log problem.
   • a 256 bit private key in ECC can provide comparable security to a 3072 bit RSA private key.
   • Elliptic curve cryptography algorithms entered wide use in 2004–2005.

3. What is a Group?

• loosely speaking, if you can add + perform additive inverse (that is, subtract), we're dealing with a Group.
• Terms:
  • An element is a set of objects
  • An operation is a way to combine any 2 elements to get another element in this set of objects. We can define an operation like ‘+’ as anything. It doesn't necessarily have to be integer addition.
• Properties of a Group:

1. Closure - when you combine 2 elements in the group using the operation, we should get another element in our set of possible objects.
2. Identity - There should exist an element which has no effect when combined with other elements in the group
3. Inverse - For every element in our set of possible objects, an opposite element should exist. An element combined with its inverse using the operation should yield the Identity element.
4. Associative - If there are 3 elements, combining them in any order should yield the same result.
   P + (Q + R) = (P + Q) + R. This is an underrated property. Life would be so much more difficult if we had to specify the order every time.

4. What is a Field?

• loosely speaking, if you can add + perform additive inverse (that is, subtract) and multiply + perform multiplicative inverse (that is, divide), we're dealing with a Field. In addition, the 2 operations are commutative - meaning combining 2 elements in any order should yield the same result. A + B = B + A
• Terms:
  • An element is a set of objects
  • An operation is a way to combine any 2 elements to get another element in this set of objects. We can define an operation like ‘+’ as anything. It doesn't necessarily have to be integer addition.
  • Defining a field requires 2 operations to exist (ex: + and *)
• Properties of Field:

1. needs to be a commutative group under +. This means all the properties of groups need to be satisfied.
2. needs to be a commutative group under * (without 0).
3. the operations + and * need to be connected through distributive property. A * (B + C) = AB + AC.

5. Write a test using class FE for basic field element operations - addition, multiplication.

file name: test/functional/test_framework/secp256k1.py
run using: python3 -m unittest functional/test_framework/secp256k1.py

import unittest
...
...
...
class TestFrameworkFE(unittest.TestCase):
     def test_FE(self):
	a = FE(2*FE.SIZE + 12)
	b = FE(100)
	print(a + b)
	print(a * b)

6. Verify Fermat's little theorem using class FE.

file name: test/functional/test_framework/secp256k1.py
run using: python3 -m unittest functional/test_framework/secp256k1.py

import unittest
...
...
...
class TestFrameworkFE(unittest.TestCase):
     def test_fermat(self):
        a = FE(45)
	assert a**(FE.SIZE - 1) == 1

7. Elliptic curve point addition of 2 points P and Q is defined geometrically by drawing a line between 2 points P and Q. This line will intersect the elliptic curve at one more point called R. However, we don't say the result of point addition is this point R! We still need to reflect point R about the x axis to get the result of our point addition. Why do this reflection? What would happen if we defined point addition without reflection?

Because we reflect about x axis, performing P + (Q + R) = (P + Q) + R and we can just write it as P + Q + R. Reflection is needed to ensure associative property in elliptic curve groups.

8. class GE represents infinity explicitly. What is the point at infinity in an elliptic curve? Why do we need this point? Where are regions in the code where we need to handle infinity scenarios properly?

Geometrically, when we add an elliptic curve point P with its inverse -P, it will not intersect the curve again at a 3rd point. So we introduce an artificial point called point at infinity. This point helps the elliptic curve behave as a group and serves as the identity element. We need to distinguish scenarios where infinity is returned from cases where none (which happens due to errors) is returned in the code.

9. What's a generator point in an elliptic curve?

Generator point is the point using which we can generate all possible elliptic curve points on the curve by multiplying it with integers in the range [1...n], where n is the order of the curve (total number of points on the curve including infinity point).

Watch this video for understanding how the generator point for secp256k1 might have been picked.

10. Are there any downsides to rewriting the elliptic curve logic using fields/groups?

The elliptic curve operations were slower. Using a multiplication table in the second commit helped speed things up. There's still a lag caused by the need to assert if every curve point is valid when initializing group elements.

References

1. ECC wiki
2. RSA wiki
3. Cryptography: From Mathematical Magic to Secure Communication
4. Abstract Algebra
5. How is the generator point G chosen in secp256k1 curve used in bitcoin