Elliptic Curve Operations

Libbitcoin provides all the necessary elliptic curve primitives and operations required for the generation and management of Bitcoin private keys, public keys and signatures of transactions and messages.

Bitcoin uses the secp256k1 elliptic curve y^2 = x^3 + 7 over the finite field Fp where:

p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1

Note that modulo prime number p is slightly less than the maximum value an unsigned 256 bit integer can hold. All subsequent operations involve either scalar members of the finite field Fp or valid points on the secp256k1 curve.

Scalar Operations in Finite Field Fp

A Bitcoin private key is simply a secret scalar value which is a the member of the finite field Fp.

A private key is randomly generated to prevent any external party from reconstructing it without any knowledge of the key derivation.

#include <bitcoin/bitcoin.hpp>
#include <string.h>
#include <iostream>

// Namespace
using namespace bc;

// We derive a new Bitcoin private key.

// Generate 256 bits of entropy.
data_chunk my_entropy(ec_secret_size); //256bits
pseudo_random_fill(my_entropy);

// Instantiate private key with 256 bits of entropy.
auto my_secret = to_array<ec_secret_size>(my_entropy);

// Not all possible 256bits are valid secret keys.
// Verify that my_secret is member of finite field Fp.
std::cout << verify(my_secret) << std::endl;

We can add and multiply scalar values in the finite field Fp. Both scalar operations are commutative and the resulting scalar values are naturally members of Fp.

auto my_scalar1 = base16_literal(
      "f3c8f9a6198cca98f481edde13bcc031b1470a81e367b838fe9e0a9db0f5993d");
auto my_scalar2 = base16_literal(
      "04c294ab836b61955e762547c561a45e4be88984dca06da959d47bf880fd92f4");

// Commutative ec addition:
ec_secret my_scalar_added1(my_scalar1);
ec_secret my_scalar_added2(my_scalar2);
// my_scalar1_added1 += my_scalar2 % p
ec_add(my_scalar_added1, my_scalar2);
// my_scalar2_added2 += my_scalar1 % p
ec_add(my_scalar_added2, my_scalar1);
std::cout << (my_scalar_added1 == my_scalar_added2) << std::endl;

// Commutative ec multiplication:
ec_secret my_scalar_multiplied1(my_scalar1);
ec_secret my_scalar_multiplied2(my_scalar2);
// my_scalar_multiplied1 *= my_scalar2 % p
ec_multiply(my_scalar_multiplied1, my_scalar2);
// my_scalar_multiplied2 *= my_scalar1 % p
ec_multiply(my_scalar_multiplied2, my_scalar1);
std::cout << (my_scalar_multiplied1 == my_scalar_multiplied2) << std::endl;

Point Operations on the Elliptic Curve

A Bitcoin public key is simply a point on the secp256k1 curve which generated by multiplying the secp256k1 generator point with the secret private key scalar value.

Note that there are two Bitcoin formats that represent points on the secp256k1 elliptic curve. The uncompressed point format has a single byte 04 prefix which is followed by the x- and y-coordinates, each represented by a sequence of 32 bytes.

Uncompressed elliptic curve point format

// Uncompressed EC point serialization
0428026f91e1c97db3f6453262484ef5f69f71d89474f10926aae24d3c3eeb5f00c41b6810b8b305a05de2b4448d7e2a079771d4c018b923a9ab860e4b0b4f86f6

// The above format consists of:
// The uncompressed EC point prefix.
04
// x-coordinate: 32 bytes.
28026f91e1c97db3f6453262484ef5f69f71d89474f10926aae24d3c3eeb5f00
// y-coordinate: 32 bytes.
c41b6810b8b305a05de2b4448d7e2a079771d4c018b923a9ab860e4b0b4f86f6

The compressed curve point format has a leading 02/03 byte followed by 32 bytes of the x-coordinate. The y-coordinate is omitted, yet implied by the x-coordinate and the prefix marker which indicates an even (02) or odd (03) y-coordinate.

Compressed elliptic curve point format

// Compressed EC point serialization
0228026f91e1c97db3f6453262484ef5f69f71d89474f10926aae24d3c3eeb5f00

// The above format consists of:
// The compressed EC point prefix for an even y-coordinate
02
// x-coordinate: byte 32 bytes
28026f91e1c97db3f6453262484ef5f69f71d89474f10926aae24d3c3eeb5f00

We will use the uncompressed format in our following examples to generate a Bitcoin public key curve point from a scalar private key.

// Private Key.
auto my_secret = base16_literal(
    "f3c8f9a6198cca98f481edde13bcc031b1470a81e367b838fe9e0a9db0f5993d");

// The secp256k1 Generator Point.
auto gen_point = base16_literal(
    "0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798");

// Manually generating the public key.
ec_compressed my_pubkey_compressed(gen_point);
ec_multiply(my_pubkey_compressed,my_secret);

// Better: Using helper fct to generate the public key.
ec_compressed my_alternative_pubkey_compressed;
secret_to_public(my_alternative_pubkey_compressed, my_secret);

std::cout << (my_pubkey_compressed == my_alternative_pubkey_compressed)
          << std::endl;

Associativity of EC operators
Point operations on the elliptic curve are associative, just like scalar operations in the finite field Fp.

( r1 + r2 ) * G = r1 * G + r2 * G

You can easily demonstrate this in the following example.

// Use any scalar values r1, r2 in Fp.

// r1 + r2
ec_secret my_scalar_result(my_scalar1);
ec_add(my_scalar_result, my_scalar2);
// (r1 + r2) * G
ec_compressed my_point_result1;
secret_to_public(my_point_result1, my_scalar_result);

// r1 * G
ec_compressed my_point1;
secret_to_public(my_point1, my_scalar1);
// r1 * G + r2 * G
ec_compressed my_point_result2(my_point1);
ec_add(my_point_result2, my_scalar2);

// (r1 + r2) * G = r1 * G + r2 * G
std::cout << (my_point_result1 == my_point_result2) << std::endl;

EC associativity is an important mathematical property used by extended public keys in HD Wallets.

The full example code from this chapter can be found here.