1.2-musig.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import util\n",
    "from test_framework.key import ECKey, ECPubKey, generate_key_pair, generate_schnorr_nonce\n",
    "from test_framework.messages import sha256\n",
    "from test_framework.musig import aggregate_musig_signatures, aggregate_schnorr_nonces, generate_musig_key, jacobi_symbol, SECP256K1_FIELD_SIZE, sign_musig"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1.2 Introduction to n-of-n MuSig\n",
    "\n",
    "* Public Key Generation\n",
    "* Signing\n",
    "    * Nonce Aggregation\n",
    "    * Signature Aggregation\n",
    "\n",
    "In this chapter, we introduce the interactive [MuSig protocol](https://eprint.iacr.org/2018/068.pdf) which allows n-of-n participants to jointly create and spend taproot or tapscript outputs using aggregated schnorr signatures. \n",
    "\n",
    "Using a signature aggregation scheme like MuSig has two significant advantages over using Script's `OP_CHECKMULTISIG` and tapscript's `OP_CHECKSIGADD` opcodes:\n",
    "\n",
    "* **Transaction Size/Fees**: an aggregate MuSig pubkey and signature is indistinguishable from a single-key pubkey and signature, meaning that the transaction size (and required fee) for a multi-key output are the same as for a single-key output.\n",
    "* **Privacy and Fungibility**: an aggregate MuSig pubkey and signature is indistinguishable from a single-key pubkey and signature, making it impossible for anyone to use the public block chain data to identify where a multi-key scheme has been used.\n",
    "\n",
    "The MuSig protocol covers both the initial setup (generating an aggregate pubkey for all participants), and the signing protocol (creating a valid signature for the aggregate pubkey). The signing requires multiple rounds of communication between the individual signers.\n",
    "\n",
    "Bip-schnorr is linear in the nonce points and public keys, which means that public keys, nonces and signatures can be aggregated. A very naive multiparty signature scheme could be achieved by simply summing the individual pubkeys to generate an aggregate pubkey, each participant signing with a shared nonce, and then summing the signatures. Such a scheme would be vulnerable to both the [key cancellation attack](https://tlu.tarilabs.com/cryptography/digital_signatures/introduction_schnorr_signatures.html#key-cancellation-attack) and private key extraction by exploiting weak or known nonces. Countering these attacks is what adds some complexity to the MuSig protocol."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![test](images/musig_intro_0.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Public Key Generation\n",
    "\n",
    "To counter the key cancellation attack, each participant's pubkey is _tweaked_ by a _challenge factor,_ which is generated by hashing all the participants' pubkeys together. Doing this ensures that no individual participant (or group of participants) is able to create a pubkey that cancels out other participants' pubkeys.\n",
    "\n",
    "The challenge factor is unique for each participant, but all challenge factors are based on a hash of all participants' pubkeys.\n",
    "\n",
    "No interactive round-trips are required in this step. As long as everyone can get all the public keys involved (through communication, a coordinator or offline) then they can compute the challenge factors and the aggregate public key locally."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![test](images/musig_intro_1.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.2.1 _Programming Exercise:_ Compute 3-of-3 MuSig public key\n",
    "\n",
    "In this exercise, we'll use the `generate_musig_key(pubkey_list)` function to generate challenge factors for each participant and an aggregate MuSig pubkey.\n",
    "\n",
    "`generate_musig_key(pubkey_list)` takes a list of the participants' public keys `generate_musig_key([ECPubKey0, ECPubKey1, ...])` and returns a challenge map and the aggregate pubkey:\n",
    "* The challenge map contains `ECPubKey_i, challenge_data_i` key - value pairs.\n",
    "* The aggregate pubkey is an `ECPubKey` object."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Compute key pairs\n",
    "privkey1, pubkey1 = generate_key_pair(sha256(b'key0'))\n",
    "privkey2, pubkey2 = generate_key_pair(sha256(b'key1'))\n",
    "privkey3, pubkey3 = generate_key_pair(sha256(b'key2'))\n",
    "pubkeys = [pubkey1, pubkey2, pubkey3]\n",
    "\n",
    "# Compute key challenges\n",
    "# Method: use generate_musig_key() on the list of pubkeys.\n",
    "# generate_musig_key() returns a challenge map and the aggregate public key.\n",
    "c_map, pubkey_agg =  # TODO: implement\n",
    "print(\"Aggregated Public Key is {}\\n\".format(pubkey_agg.get_bytes().hex()))\n",
    "\n",
    "# Multiply key pairs by challenge factor\n",
    "privkey1_c =  # TODO: implement\n",
    "privkey2_c =  # TODO: implement\n",
    "privkey3_c =  # TODO: implement\n",
    "pubkey1_c =  # TODO: implement\n",
    "pubkey2_c =  # TODO: implement\n",
    "pubkey3_c =  # TODO: implement\n",
    "\n",
    "print(\"Tweaked privkey1 is {}\".format(privkey1_c))\n",
    "print(\"Tweaked privkey2 is {}\".format(privkey2_c))\n",
    "print(\"Tweaked privkey3 is {}\".format(privkey3_c))\n",
    "\n",
    "assert privkey1_c.secret == 104717570570407299858230629579807834166658508605015363884161538594382975780625\n",
    "assert privkey2_c.secret == 65554880484297966965546994775376394861215085064604177497808278620612854069980\n",
    "assert privkey3_c.secret == 106998690642216524894360365246223287721822845133760006050846956016514597569168\n",
    "\n",
    "print(\"\\nSuccess!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Signing \n",
    "\n",
    "### Nonce generation\n",
    "\n",
    "The first step of creating a MuSig signature requires each signer to generate their own nonce and nonce point. The participants then exchange those nonces points and an aggregate nonce point is derived by summing all the nonce points.\n",
    "\n",
    "The security proof for MuSig requires that nonces are randomly generated and are independent of each other. To ensure that no individual participant (or group of participants) can create their nonce as a function of the other nonces or individually control what the aggregate nonce point will be, there is an initial round of exchanging hash commitments to the individual nonce points.\n",
    "\n",
    "Individual participants should only exchange their nonce point when they have received all commitments, and only proceed with signing if all nonce points match their commitments.\n",
    "\n",
    "Finally, if the aggregate nonce is not a quadratic residue, then it is negated and all individual nonces are also negated."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![test](images/musig_intro_2.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.2.2 _Programming Exercise:_ Compute 3-of-3 MuSig nonce\n",
    "\n",
    "In this exercise, we'll generate nonces for individual participants, calculate the nonce point commitments, and then generate an aggregate nonce point."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generate nonces and nonce points\n",
    "# We set the nonces manually here for testing purposes, but usually we'll call generate_schnorr_nonce()\n",
    "# to generate a random nonce point\n",
    "# Method: generate_schnorr_nonce() with no argument generates a random nonce\n",
    "k1 = ECKey().set(101)\n",
    "k2 = ECKey().set(222)\n",
    "k3 = ECKey().set(333)\n",
    "test_k1 = ECKey().set(k1.secret)\n",
    "test_k2 = ECKey().set(k2.secret)\n",
    "test_k3 = ECKey().set(k3.secret)\n",
    "\n",
    "# Method: use get_pubkey() to get the associated nonce point.\n",
    "R1 =  # TODO: implement\n",
    "R2 =  # TODO: implement\n",
    "R3 =  # TODO: implement\n",
    "\n",
    "# Round 1: Generate nonce point commitments and exchange them\n",
    "# Method: use sha256() on the nonce point. sha256() takes a bytes object, so extract the bytes from the nonce point.\n",
    "R1_digest =  # TODO: implement\n",
    "R2_digest =  # TODO: implement\n",
    "R3_digest =  # TODO: implement\n",
    "\n",
    "# Round 2: Exchange the nonce points. Each participant verifies that the nonce point commitment matches the nonce point.\n",
    "assert R1_digest.hex() == \"aa5d4a40c1843456534d75f7246b9cbf0f825a36113102e76193f80e6c652c72\"\n",
    "assert R2_digest.hex() == \"6a78f2c6ca3bf1364f0575a02ef334d176df2051084c0e3062ec2af79b5b406a\"\n",
    "assert R3_digest.hex() == \"bc2c379a7b6ad82b40a7cf280697505ccc039370e50eb155324dcac3b5faa6a5\"\n",
    "\n",
    "# Aggregate nonces\n",
    "# Tip: Add the individual nonce points together. If the aggregated nonce is not a quadratic residue\n",
    "# then negate the aggregate nonce and individual nonce scalars.\n",
    "R_agg =  # TODO: implement\n",
    "if  # TODO: implement\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "print(\"Individual nonce scalars:\\n\\t{}, \\n\\t{}, \\n\\t{}.\\n\".format(k1, k2, k3))\n",
    "print(\"Aggregate nonce point: {}\\n\".format(R_agg))\n",
    "\n",
    "# Test your solution against the aggregate_schnorr_nonces() helper function.\n",
    "# aggregate_schnorr_nonces() aggregates the nonces and returns whether the individual nonces need to be negated.\n",
    "test_R_agg, negated = aggregate_schnorr_nonces([R1, R2, R3])\n",
    "if negated:\n",
    "    test_k1.negate()\n",
    "    test_k2.negate()\n",
    "    test_k3.negate()\n",
    "\n",
    "assert R_agg == test_R_agg\n",
    "assert k1 == test_k1\n",
    "assert k2 == test_k2\n",
    "assert k3 == test_k3\n",
    "\n",
    "print(\"Success!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Signature Aggregation\n",
    "\n",
    "Once all participants have their individual nonces and the aggregate nonce point, then can all sign individually. \n",
    "\n",
    "The partial `s` values are then exchanged and summed together. The aggregate `s` value and aggregate nonce point `R` form a valid bip-schnorr signature for the aggregate pubkey.\n",
    "\n",
    "Notice that the hash expressions are identical in all signatures, which makes aggregation possible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![test](images/musig_intro_3.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.2.3 _Programming exercise:_ Compute aggregated MuSig signature\n",
    "\n",
    "In this exercise, we'll create partial signatures and then aggregate them to create a valid signature.\n",
    "\n",
    "Use the `sign_musig()` function to create partial signatures. `sign_musig()` takes:\n",
    "  - the individual participant's challenge-factor-modified private key (an `ECKey` object)\n",
    "  - the invididual participant's nonce scalar (an `ECKey` object)\n",
    "  - the aggregate nonce point (an `ECPubKey` object)\n",
    "  - the aggregate pubkey (an `ECPubKey` object)\n",
    "  - the message (a 32 byte `bytes` object)\n",
    "\n",
    "and returns a partial signature (an int containing the partial `s` value).\n",
    "\n",
    "Use `aggregate_musig_signatures()` to aggregate the partial signatures. `aggregate_musig_signatures()` takes a list of partial signatures, and the aggregate nonce point and returns the final signature.\n",
    "\n",
    "Use `ECPubKey.verify_schnorr(sig, msg)` to verify that the signature is valid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "msg = sha256(b'transaction')\n",
    "\n",
    "# Generate partial signatures\n",
    "# Method: use sign_musig() with:\n",
    "#     - individual (tweaked) privkey\n",
    "#     - individual nonce scalar\n",
    "#     - aggregate nonce point\n",
    "#     - aggregate pubkey\n",
    "#     - msg\n",
    "s1 =  # TODO: implement\n",
    "s2 =  # TODO: implement\n",
    "s3 =  # TODO: implement\n",
    "\n",
    "print(\"Partial signatures:\\n\\t{}\\n\\t{}\\n\\t{}\\n\".format(s1, s2, s3))\n",
    "\n",
    "# Aggregate signatures\n",
    "# Method: use aggregate_musig_signatures with list of individual signatures\n",
    "sig_agg =  # TODO: implement\n",
    "print(\"Aggregate signature:\\n\\t{}\\n\".format(sig_agg.hex()))\n",
    "\n",
    "# Verify signature against aggregate public key\n",
    "assert pubkey_agg.verify_schnorr(sig_agg, msg)\n",
    "print(\"Success! Signature verifies against aggregate pubkey\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Congratulations!** In this chapter, you have:\n",
    "\n",
    "- Learned about the MuSig multi-signature scheme.\n",
    "- Computed an aggregate public key that multiplies individual public keys by _challenge factors_ to counter the rogue key attack.\n",
    "- Exchanged nonce point commitments, and then the nonce points themselves, and generated an aggregate nonce point.\n",
    "- Signed individually and then aggregated individual `s` values to create a valid signature for the aggregate public key."
   ]
  }
 ],
 "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
}