1.1-schnorr-signatures.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import util\n",
    "from test_framework.key import generate_key_pair, generate_bip340_key_pair, ECKey, ECPubKey, jacobi_symbol, SECP256K1_FIELD_SIZE, SECP256K1_ORDER\n",
    "from test_framework.messages import sha256\n",
    "from test_framework.script import tagged_hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1.1 Introduction to Schnorr Signatures\n",
    "\n",
    "* Part 1: Schnorr Signatures.\n",
    "* Part 2: Nonce Generation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1: Schnorr Signatures\n",
    "\n",
    "[BIP340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki) defines a signature/verifier scheme, as well as pubkey and signature encodings.\n",
    "\n",
    "The schnorr signature equation is the following:\n",
    "\n",
    "* `S = R + H(x(R)|x(P)|m) * P`\n",
    "\n",
    "Signing involves generating a secret nonce first.\n",
    "\n",
    "* Generate secret scalar `k`\n",
    "\n",
    "Then computing `s` from:\n",
    "\n",
    "* `s = k + H(x(R)|x(P)|m) * d`\n",
    "\n",
    "The resulting signature is:\n",
    "\n",
    "* `x(R), s`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![test](images/schnorr0.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Constraint on the public key, P, and public nonce point, R\n",
    "\n",
    "BIP340 defines a new way of encoding elliptic curve points. To make the encoding of a point as compact as possible only the x-coordinate of the point is used (ie: 32 bytes).\n",
    "\n",
    "For a given x-coordinate on the secp256k1 curve, there are two possible curve points:\n",
    "\n",
    "* `y^2 = x^3 + 7` (Two y-coordinate values for a given x-coordinate)\n",
    "    * For `x`, both `(x, y)` and `(x, -y)` are valid curve points (where `-y` is `SECP256K1_FIELD_SIZE - y` since all arithmetic involving coordinates is modulo `SECP256K1_FIELD_SIZE`).\n",
    "    * One of the y-coordinates is even, and the other is odd (since `SECP256K1_FIELD_SIZE` is odd).\n",
    "    * One of the y-coordinates is a quadratic residue (has a square root modulo the field size), and the other is not.\n",
    "\n",
    "BIP340 constrains private key points `k` such that the y-value of R is even. This means that from the `x` co-ordinate, the verifier can unambigiously determine `y`.\n",
    "\n",
    "* `k` and `SECP256K1_ORDER - k` have nonce points `R = (x, y)` and `R = (x, -y)` respectively.\n",
    "* Only one will have a y-coordinate which is even. If a randomly generated nonce `k` does not yield a valid nonce point `R`, then the signer can negate `k` to obtain a valid nonce.\n",
    "\n",
    "The same goes for private key `d` and its corresponding public key, P."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.1.1 Example: Calculating a valid nonce"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generate a random value and its assoctiated curve point. We can use the generate_key_pair convenience function.\n",
    "k, R = generate_key_pair()\n",
    "\n",
    "# Find y and -y\n",
    "y = R.get_y()\n",
    "minus_y = SECP256K1_FIELD_SIZE - y\n",
    "print(\"y = {}\".format(y))\n",
    "print(\"-y = {}\\n\".format(minus_y))\n",
    "\n",
    "# One of y and -y will be even and the other will be odd\n",
    "print(\"y is {}\".format(\"odd\" if y % 2 else \"even\"))\n",
    "print(\"-y is {}\\n\".format(\"odd\" if minus_y % 2 else \"even\"))\n",
    "\n",
    "print(\"k is {}a valid nonce\".format(\"\" if y % 2 == 0 else \"not \"))\n",
    "print(\"-k is {}a valid nonce\".format(\"\" if minus_y % 2 == 0 else \"not \"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.1.2 _Programming Exercise:_ Verify that inverse nonce values `k` and `-k` generate inverse points `R` and `-R`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generate a random scalar and its associated curve point\n",
    "k, R =  # TODO: implement\n",
    "\n",
    "# Find the x- and y-coordinates from R\n",
    "# Use the get_x() and get_y() methods\n",
    "R_x =  # TODO: implement\n",
    "R_y =  # TODO: implement\n",
    "\n",
    "print(\"R_x: {}\".format(R_x))\n",
    "print(\"R_y: {}\\n\".format(R_y))\n",
    "\n",
    "# Find k's inverse (SECP256K1_ORDER - k)\n",
    "# Extract the secret value from k using .secret\n",
    "minus_k =  # TODO: implement\n",
    "\n",
    "# Generate the key pair from minus_k using generate_key_pair() function with minus_k as an argument\n",
    "minus_k_key, minus_R =  # TODO: implement\n",
    "\n",
    "# Find the x- and y-coordinates from -R\n",
    "minus_R_x =  # TODO: implement\n",
    "minus_R_y =  # TODO: implement\n",
    "\n",
    "print(\"minus_R_x: {}\".format(minus_R_x))\n",
    "print(\"minus_R_y: {}\\n\".format(minus_R_y))\n",
    "\n",
    "assert R_x == minus_R_x\n",
    "assert SECP256K1_FIELD_SIZE - R_y == minus_R_y\n",
    "\n",
    "print(\"Success!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.1.3 _Programming Exercise:_ Sign a message with Schnorr\n",
    "\n",
    "* Sign the message with the provided key pair below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "msg = sha256(b'message')\n",
    "\n",
    "# Generate a private/public key pair\n",
    "d, P = generate_key_pair()\n",
    "\n",
    "# Check that public key point has an even Y-coordinate.\n",
    "# If not, negate d and P.\n",
    "if # TODO: implement\n",
    "    d.negate()\n",
    "    P.negate()\n",
    "\n",
    "# Generate a nonce scalar and associated nonce point\n",
    "k, R = generate_key_pair()\n",
    "\n",
    "# Check that nonce point has an even Y-coordinate.\n",
    "# If not, negate k\n",
    "if # TODO: implement\n",
    "    k.negate()\n",
    "# Note that there is no need to negate R, since we only use the x value of R below\n",
    "\n",
    "# Generate s = k + hash(R_x|P_x|msg) * d\n",
    "# Method: tagged_hash(\"BIP0340/challenge\", bytes) will give you the byte digest tagged hash of the challenge data.\n",
    "# Turn that digest into a ECKey object called h, and then set s = k + h * d\n",
    "# Note that ECPubKey.get_bytes() will return the bip340 encoding of a public key which is equivalent \n",
    "# to its x-coordinate\n",
    "R_x_bytes = R.get_bytes()\n",
    "P_bytes = P.get_bytes()\n",
    "h_bytes = # TODO: implement\n",
    "h = ECKey().set(h_bytes)\n",
    "s = k + h * d\n",
    "\n",
    "print(\"R: {}\".format(R))\n",
    "print(\"s: {}\\n\".format(s.get_bytes().hex()))\n",
    "\n",
    "# Generate sig = R_x|s\n",
    "# Method: get the x bytes from R and concatenate with the secret bytes from s\n",
    "sig = # TODO: implement\n",
    "\n",
    "print(\"Signature: {}\\n\".format(sig.hex()))\n",
    "\n",
    "# Verify the signature\n",
    "assert P.verify_schnorr(sig, msg)\n",
    "\n",
    "print(\"Success!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that a convenience function, `generate_bip340_key_pair`, is provided which will automatically check the evenness of a the generated public-key's y-coordinate and negate both the private and public key if needed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2: Generating Nonces for schnorr signatures\n",
    "\n",
    "So far we have used a random secret nonce for creating schnorr signatures. This has the disadvantage that the the user must rely on the robustness of the random generator for each signing rounds. If the nonce generator is compromised or even biased, the private key can be derived for a given signature and known nonce.\n",
    "\n",
    "For **single signer schnorr signatures**, BIP340 proposes the following nonce generation scheme:\n",
    "\n",
    "* Given private-public key pair `(d, P)`, message `m` and optional 32 byte random auxiliary data, `a`\n",
    "* Let `t` be the byte-wise `XOR` of `bytes(d)` and `tagged_hash(\"BIP0340/aux\", a)`\n",
    "* Let `rand = tagged_hash(\"BIP0340/nonce\", t || bytes(P) || m)`\n",
    "* `k = int(rand) mod n`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.1.4 _Programming Exercise:_ Signing schnorr with a BIP340 generated nonce\n",
    "\n",
    "* Create a Schnorr signature with BIP340's nonce scheme\n",
    "* Compare this signature to the private key class method `ECKey.sign_schnorr(msg, aux)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "msg = sha256(b'message')\n",
    "aux = sha256(b'random auxiliary data')\n",
    "\n",
    "# Generate a valid BIP340 priv-pub key pair using the convenience function `generate_bip340_key_pair`\n",
    "d, P = generate_bip340_key_pair()\n",
    "print(\"message = {}\".format(msg.hex()))\n",
    "print(\"pubkey = {}\\n\".format(P.get_bytes().hex()))\n",
    "\n",
    "# t is the byte-wise xor of bytes(d) and tagged_hash(\"BIP0340/aux\", aux)\n",
    "t = (d.secret ^ int.from_bytes(tagged_hash(\"BIP0340/aux\", aux), 'big')).to_bytes(32, 'big')\n",
    "rand = tagged_hash(\"BIP0340/nonce\", t + P.get_bytes() + msg)\n",
    "\n",
    "# Generate the nonce value k and get the nonce point R\n",
    "k, R = generate_key_pair(rand)\n",
    "\n",
    "# Check that nonce has an even y coordinate\n",
    "# If not, negate k\n",
    "if # TODO: implement\n",
    "    k.negate()\n",
    "\n",
    "print(\"nonce: {}\".format(k))\n",
    "print(\"nonce point: {}\\n\".format(R))\n",
    "\n",
    "# Generate s = k + tagged_hash(\"BIP0340/challenge\", R_x|P_x|msg) * d\n",
    "# Method: tagged_hash(\"BIP0340/challenge\", bytes) will give you the byte digest\n",
    "# Turn that digest into a ECKey object called h, and then set s = k + h * d\n",
    "R_x_bytes = R.get_bytes()\n",
    "P_bytes = P.get_bytes()\n",
    "h_bytes =  # TODO: implement\n",
    "h = ECKey().set(h_bytes)\n",
    "s = k + h * d\n",
    "\n",
    "print(\"R: {}\".format(R))\n",
    "print(\"s: {}\\n\".format(s.get_bytes().hex()))\n",
    "\n",
    "# Generate sig = R_x|s\n",
    "# Method: get the x bytes from R and concatenate with the secret bytes from s\n",
    "sig = # TODO: implement\n",
    "\n",
    "print(\"Signature: {}\\n\".format(sig.hex()))\n",
    "\n",
    "# Generate a signature using the ECKey.sign_schnorr(msg) method\n",
    "# This generates the nonce deterministically, so should return the same signature\n",
    "sig2 = d.sign_schnorr(msg, aux)\n",
    "\n",
    "# Verify and compare signature(s)\n",
    "assert P.verify_schnorr(sig, msg)\n",
    "assert P.verify_schnorr(sig2, msg)\n",
    "assert sig == sig2\n",
    "\n",
    "print(\"Success!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Congratulations!** In this chapter, you have:\n",
    "\n",
    "- Learned how to determine if a private key results in a valid BIP340 public key \n",
    "- Created and verified a valid schnorr signature for a public key P and message m\n",
    "- Generated a nonce using a hash digest of the public key, message and optional auxiliary data"
   ]
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}