appendix/elliptic-curve-math-review.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3ca0e780",
   "metadata": {},
   "source": [
    "## Setup \n",
    "\n",
    "### Requirements\n",
    "For this exercise we'll need Bitcoin Core. This notebook has been tested with [v24.0.1](https://github.com/bitcoin/bitcoin/releases/tag/v24.0.1).\n",
    "\n",
    "Below, set the paths for:\n",
    "1. The bitcoin core functional test framework directory.\n",
    "2. The directory containing bitcoin-tx-tutorial.\n",
    "\n",
    "**You'll need to edit these next two lines for your local setup.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "752d005e",
   "metadata": {},
   "outputs": [],
   "source": [
    "path_to_bitcoin_functional_test = \"/Users/dariuscognac/bitcoin/test/functional\"\n",
    "path_to_bitcoin_tx_tutorial = \"/Users/dariuscognac/Documents/Github/bitcoin-tx-tutorial\"\n",
    "\n",
    "import sys\n",
    "\n",
    "# Add the functional test framework to our PATH\n",
    "sys.path.insert(0, path_to_bitcoin_functional_test)\n",
    "from test_framework.test_shell import TestShell\n",
    "\n",
    "# Add the bitcoin-tx-tutorial functions to our PATH\n",
    "sys.path.insert(0, path_to_bitcoin_tx_tutorial)\n",
    "from functions import *\n",
    "from functions.bip_0340_reference import *"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24b84d23",
   "metadata": {},
   "source": [
    "# Elliptic Curve Math Review\n",
    "\n",
    "Elliptic Curve math involves scalars and points.\n",
    "\n",
    "* A scalar is a positive integer which is smaller than the group order.\n",
    "* A point lies on the curve and is denoted by a pair of co-ordinates (eg `(x,y)`).\n",
    "\n",
    "In Bitcoin, key pair generation and signing is performed over the secp256k1 curve. All scalars are modulo the group order `SECP256K1_ORDER`, which is a very large number\n",
    "\n",
    "![test](../images/taproot-workshop/ec_math0.jpg)\n",
    "\n",
    "_An overview of all operations of scalars and points over elliptic curves._"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "041a1edc",
   "metadata": {},
   "source": [
    "## Elliptic curve math in python\n",
    "\n",
    "**`Scalars`:** All Scalar operations over secp256k1 can be performed with python integers and the modulo `%` operator. \n",
    "\n",
    "Scalar addition, subtraction, multiplication and division over secp256k1 are modulo a large prime number SECP256K1_ORDER.\n",
    "\n",
    "* All scalar operations are performed modulo `SECP256K1_ORDER`.\n",
    "* Addition: `(a + b) % SECP256K1_ORDER`\n",
    "* Subtraction: `-a = SECP256K1_ORDER - a`\n",
    "* Multiplication: `(a * b) % SECP256K1_ORDER`\n",
    "* Division (see [Fermat's little theorem](https://en.wikipedia.org/wiki/Fermat%27s_little_theorem)): `1/b = b ** (SECP256K1_ORDER-2) % SECP256K1_ORDER`\n",
    "\n",
    "**`Points`:** The [BIP340 reference code](https://github.com/bitcoin/bips/blob/master/bip-0340/reference.py) provides a `Point` class for and some helpful functions for performing point addition (e.g. for adding two pubkeys together) and multiplication (e.g. multiplying the generator point by a private key to get a pubkey).\n",
    "\n",
    "```\n",
    "Point = Tuple[int, int]\n",
    "```\n",
    "\n",
    "* Addition: `point_add(P1: Optional[Point], P2: Optional[Point]) -> Optional[Point]`\n",
    "* Multiplication: `point_mul(P: Optional[Point], n: int) -> Optional[Point]`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c0c086ab",
   "metadata": {},
   "source": [
    "## Elliptic Curves in Bitcoin\n",
    "\n",
    "### Sekp256k1\n",
    "Secp256k1 refers to the set of parameters used in Bitcoin's elliptic curve cryptography. A full list of the parameters can be found [here](https://en.bitcoin.it/wiki/Secp256k1). Two parameters which we will use in a few places (in particular for constructing taproot outputs) are the order, SECP256K1, and the generator point, G.\n",
    "\n",
    "### Private keys\n",
    "Private keys in Bitcoin are 32 bytes scalars. Note that private keys must be a value between 1 and SECP256K1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "2f212482",
   "metadata": {},
   "outputs": [],
   "source": [
    "privkey = bytes.fromhex(\"0000000000000000000000000000000000000000000000000000000000000001\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5789a337",
   "metadata": {},
   "source": [
    "### Public keys\n",
    "Public keys are points on the elliptic curve and have an x and y coordinate. A public key is generated by multiplying the generator point by the private key. We can use the BIP340 function `point_mul` for this operation. Note that it expects the private key to be an integer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "54b533fc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pubkey:  (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)\n"
     ]
    }
   ],
   "source": [
    "privkey_int = int_from_bytes(privkey)\n",
    "pubkey = point_mul(G, privkey_int)\n",
    "print(\"pubkey: \", pubkey)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e136081",
   "metadata": {},
   "source": [
    "**Exercise**: You'll notice the pubkey has two integers representing an x and y coordinate on the elliptic curve. Try converting these values to hex (you can use `bytes_from_int()`) and compare it to the generator point (G) listed above. What do you notice, and why is this the case?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a2e9bbd4",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "0edf529c",
   "metadata": {},
   "source": [
    "**Answer**: \n",
    "```\n",
    "bytes_from_int(pubkey[0]).hex()\n",
    "bytes_from_int(pubkey[1]).hex()\n",
    "```\n",
    "The pubkey is the same as the generator point because we chose a private key of 1, so when we multiply them together to get the public key (G\\*1=G) we end up with the same value."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "928d2ed4",
   "metadata": {},
   "source": [
    "#### Uncompressed/Compressed public keys\n",
    "Before taproot, Bitcoin used either 65-byte uncompressed, or 33-byte compressed public keys. Interestingly, the only reason uncompressed public keys were more common in the earlier days (~2012) was because because compressed public keys were poorly documented in OpenSSL.\n",
    "- Uncompressed public keys: `0x04` followed by two 256-bit integers for the x and y-coordinates\n",
    "- Compressed public keys: a prefix of either `0x02` or `0x03` depending on whether the y-coordinate was even or odd, respectively, followed by a 256-bit integer for the x coordinate. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "468b6795",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Uncompressed pubkey:  0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8\n",
      "Compressed pubkey:  0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798\n"
     ]
    }
   ],
   "source": [
    "# using the same privkey value from above\n",
    "pubkey = point_mul(G, privkey_int)\n",
    "\n",
    "# constant `04` prefix followed by x and y coordinates \n",
    "uncompressed = b\"\\x04\" + bytes_from_int(pubkey[0]) + bytes_from_int(pubkey[1])\n",
    "print(\"Uncompressed pubkey: \", uncompressed.hex())\n",
    "\n",
    "# prefix of 0x02 or 0x03 depending on the evenness of y coordinate, followed by x coordinate\n",
    "x_coord, y_coord = pubkey[0], pubkey[1]\n",
    "prefix = b\"\\x02\" if y_coord % 2 == 0 else b\"\\x03\"\n",
    "compressed = prefix + bytes_from_int(x_coord)\n",
    "print(\"Compressed pubkey: \", compressed.hex())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9337b00",
   "metadata": {},
   "source": [
    "#### Taproot x-only public keys\n",
    "Since taproot, a further step has been made to reduce the on-chain size of public keys by removing the `0x02`/`0x03` prefix from the public key and instead assuming that the y-coordinate has an even value. This is the equivalent to assuming all public keys would have had the `0x02` prefix, which means we do not need to include it and therefore just use the 32-byte x coordinate. For a detailed explanation see [Jonas Nick's blog post](https://medium.com/blockstream/reducing-bitcoin-transaction-sizes-with-x-only-pubkeys-f86476af05d7) explaining it.\n",
    "\n",
    "#### Negating secret keys\n",
    "Having the requirement that the y-coordinate must have even value leads to the question of what we do with secret keys that generate a pubkey with an odd y-coordinate. Do we just not use those secret keys? Fortunately, we can take advantage of the properties of Secp256k1 to give us a new secret key that has a corresponding public key with the same x-coordinate but an even y-coordinate. We do this by negating the secret key:\n",
    "\n",
    "`(SECP256K1 - privkey_int) % SECP256K1` \n",
    "\n",
    "Here's an example of negating a private key so that we end up with a public key with the same x-coordinate but an even y-coordinate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a56fe6dc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "original_pubkey:  (115780575977492633039504758427830329241728645270042306223540962614150928364886, 78735063515800386211891312544505775871260717697865196436804966483607426560663)\n",
      "y coordinate is odd\n",
      "\n",
      "Negating the private key..\n",
      "new_pubkey:  (115780575977492633039504758427830329241728645270042306223540962614150928364886, 37057025721515809211679672464182131982009266967775367602652617524301408111000)\n",
      "y coordinate is even\n"
     ]
    }
   ],
   "source": [
    "# This private key has been chosen as it'll produce a public key with an odd y-coordinate\n",
    "original_privkey = bytes.fromhex(\"0000000000000000000000000000000000000000000000000000000000000006\")\n",
    "original_privkey_int = int_from_bytes(original_privkey)\n",
    "\n",
    "original_pubkey = point_mul(G, original_privkey_int)\n",
    "print(\"original_pubkey: \", original_pubkey)\n",
    "odd_or_even = \"even\" if original_pubkey[1] % 2 == 0 else \"odd\"\n",
    "print(f\"y coordinate is {odd_or_even}\\n\")\n",
    "\n",
    "print(\"Negating the private key..\")\n",
    "negated_privkey_int = (SECP256K1_ORDER - original_privkey_int) % SECP256K1_ORDER\n",
    "new_pubkey = point_mul(G, negated_privkey_int)\n",
    "print(\"new_pubkey: \", new_pubkey)\n",
    "odd_or_even = \"even\" if new_pubkey[1] % 2 == 0 else \"odd\"\n",
    "print(f\"y coordinate is {odd_or_even}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d247e2f",
   "metadata": {},
   "source": [
    "## Linear property of elliptic curves: \n",
    "\n",
    "Understanding this simple concept will make a lot of the taproot features much easier to understand.\n",
    "\n",
    "> The sum of private keys generates the same public key that is the sum of public keys.\n",
    "\n",
    "For example, given two private keys, d<sub>A</sub> and d<sub>B</sub>, and their corresponding public keys, P<sub>A</sub> and P<sub>B</sub>:<br>\n",
    "G\\*d<sub>A</sub> = P<sub>A</sub><br>\n",
    "G\\*d<sub>B</sub> = P<sub>B</sub>\n",
    "\n",
    "Summing the private keys and producing a public key produces the same result as summing their public keys:\n",
    "\n",
    "(d<sub>A</sub>+d<sub>B</sub>)\\*G = P<sub>A+B</sub>\n",
    "\n",
    "This property has used in various places in bitcoin including:\n",
    "- Deriving public keys with an extended pubkey.\n",
    "- Securely using a pool to generate a custom vanity addresses ([video explanation](https://www.youtube.com/watch?v=6u1XEucEJ_A&t=322s) by Andreas Antonopoulos).\n",
    "- TapTweaks (Chapter XX)\n",
    "- Musig"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c7cd1861",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pubkey generated from summing private keys:  (112711660439710606056748659173929673102114977341539408544630613555209775888121, 25583027980570883691656905877401976406448868254816295069919888960541586679410)\n",
      "Pubkey generated from summing public keys:  (112711660439710606056748659173929673102114977341539408544630613555209775888121, 25583027980570883691656905877401976406448868254816295069919888960541586679410)\n",
      "Success!\n"
     ]
    }
   ],
   "source": [
    "# Define private keys and convert to int\n",
    "privkey_a = bytes.fromhex(\"0000000000000000000000000000000000000000000000000000000000000001\")\n",
    "privkey_b = bytes.fromhex(\"0000000000000000000000000000000000000000000000000000000000000002\")\n",
    "privkey_a_int = int_from_bytes(privkey_a)\n",
    "privkey_b_int = int_from_bytes(privkey_b)\n",
    "\n",
    "privkey_ab_int = (privkey_a_int + privkey_b_int) % SECP256K1_ORDER\n",
    "pubkey_ab = point_mul(G, privkey_ab_int)\n",
    "print(\"Pubkey generated from summing private keys: \", pubkey_ab)\n",
    "\n",
    "pubkey_a = point_mul(G, privkey_a_int)\n",
    "pubkey_b = point_mul(G, privkey_b_int)\n",
    "\n",
    "pubkey2 = point_add(pubkey_a, pubkey_b)\n",
    "print(\"Pubkey generated from summing public keys: \", pubkey2)\n",
    "\n",
    "assert(pubkey_ab == pubkey2)\n",
    "print(\"Success!\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}