3.1-degrading-multisig-case-study.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from io import BytesIO\n",
    "import random\n",
    "\n",
    "import util\n",
    "from test_framework.key import generate_key_pair, generate_bip340_key_pair, generate_schnorr_nonce, ECKey, ECPubKey, SECP256K1_FIELD_SIZE, SECP256K1, SECP256K1_ORDER\n",
    "from test_framework.musig import aggregate_musig_signatures, aggregate_schnorr_nonces, generate_musig_key, musig_digest, sign_musig\n",
    "from test_framework.script import TapLeaf, TapTree, TaprootSignatureHash, SIGHASH_ALL_TAPROOT\n",
    "from test_framework.address import program_to_witness\n",
    "from test_framework.messages import CTransaction, COutPoint, CTxIn, CTxOut, CTxInWitness\n",
    "from test_framework.util import assert_equal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.1 Degrading Multisig Output\n",
    "\n",
    "In this case study, we consider a degrading multisig output, which provides recovery spending paths if the main wallet keys are lost or cannot sign. This output is expected to spent soon after being created. \n",
    "The recovery spending paths include delays in case the back-up keys are compromised."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![test](images/degrading_multisig0.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Locking conditions\n",
    "\n",
    "* **multisig( 3/3 main wallet key )** - spendable immediately; or\n",
    "* **multisig( 2/3 main wallet keys + 1/2 backup keys )** - spendable after 3 days; or\n",
    "* **multisig( 1/3 main wallet keys + 2/2 backup keys )** - spendable after 10 days.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Signers\n",
    "\n",
    "* **Main wallet keys** - Keys A, B, C\n",
    "* **Backup keys** - Keys D, E\n",
    "\n",
    "#### Privacy Requirements\n",
    "\n",
    "No unused public keys should be revealed during spending.\n",
    "\n",
    "#### Other considerations\n",
    "\n",
    "Since the backup keys are stored on simple HSMs, they are not able to interactively co-sign MuSig aggregate signatures."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### _Exercise 3.1.1:_ Determine different signing scenarios and their likelihoods\n",
    "\n",
    "**(This is not a coding exercise)**\n",
    "\n",
    "Before we construct the Taptree, sketch out different signing scenarios and their likelihoods."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Spending paths\n",
    "\n",
    "_TODO: List spending paths in order of likelihood_\n",
    "\n",
    "##### Sketch out Taproot Descriptors\n",
    "\n",
    "_TODO: Sketch out taproot descriptors_\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 3.1.2: Set up keys for the taproot output\n",
    "\n",
    "Here we prepare key pairs for all participants, and create an aggregate MuSig pubkey."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generate main wallet key pairs\n",
    "main_privkeyA, main_pubkeyA = generate_bip340_key_pair()\n",
    "main_privkeyB, main_pubkeyB = generate_bip340_key_pair()\n",
    "main_privkeyC, main_pubkeyC = generate_bip340_key_pair()\n",
    "main_pubkeys = [main_pubkeyA.get_bytes().hex(),\n",
    "                main_pubkeyB.get_bytes().hex(), \n",
    "                main_pubkeyC.get_bytes().hex()]\n",
    "\n",
    "print(\"Main pubkeys: {}\\n\".format(main_pubkeys))\n",
    "\n",
    "# Generate back-up wallet key pairs\n",
    "backup_privkeyD, backup_pubkeyD = generate_bip340_key_pair()\n",
    "backup_privkeyE, backup_pubkeyE = generate_bip340_key_pair()\n",
    "backup_pubkeys = [backup_pubkeyD.get_bytes().hex(),\n",
    "                  backup_pubkeyE.get_bytes().hex()]\n",
    "\n",
    "print(\"Backup pubkeys: {}\\n\".format(backup_pubkeys))\n",
    "\n",
    "# 3-of-3 main key (MuSig public key)\n",
    "c_map, musig_ABC = generate_musig_key([main_pubkeyA, main_pubkeyB, main_pubkeyC])\n",
    "main_privkeyA_c = main_privkeyA.mul(c_map[main_pubkeyA])\n",
    "main_privkeyB_c = main_privkeyB.mul(c_map[main_pubkeyB])\n",
    "main_privkeyC_c = main_privkeyC.mul(c_map[main_pubkeyC])\n",
    "main_pubkeyA_c = main_pubkeyA.mul(c_map[main_pubkeyA])\n",
    "main_pubkeyB_c = main_pubkeyA.mul(c_map[main_pubkeyB])\n",
    "main_pubkeyC_c = main_pubkeyA.mul(c_map[main_pubkeyC])\n",
    "\n",
    "if musig_ABC.get_y()%2 != 0:\n",
    "    musig_ABC.negate()\n",
    "    main_privkeyA_c.negate()\n",
    "    main_privkeyB_c.negate()\n",
    "    main_privkeyC_c.negate()\n",
    "    main_pubkeyA_c.negate()\n",
    "    main_pubkeyB_c.negate()\n",
    "    main_pubkeyC_c.negate()\n",
    "\n",
    "print(\"MuSig pubkey: {}\".format(musig_ABC.get_bytes().hex()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### _Programming Exercise 3.1.3:_ Build a taproot output\n",
    "\n",
    "In this exercise, we'll build a taptree according to the spending paths and their likelihoods, and then derive the segwit address for the taproot."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Tapscripts - 2 main keys & 1 backup key\n",
    "# Use construct_csa_delay() to construct the tapscript\n",
    "delay =  # TODO: implement\n",
    "tapscript_2a =  # TODO: implement\n",
    "tapscript_2b =  # TODO: implement\n",
    "...  # TODO: implement\n",
    "\n",
    "# Tapscripts - 1 main keys & 2 backup keys\n",
    "long_delay =  # TODO: implement\n",
    "tapscript_3a =  # TODO: implement\n",
    "tapscript_3b =  # TODO: implement\n",
    "...  # TODO: implement\n",
    "\n",
    "# Set list of backup tapscripts\n",
    "# Suggestion: Include tapscripts with 3d timelocks first, then those with 10d timelocks\n",
    "backup_tapscripts =  # TODO: implement\n",
    "                                \n",
    "assert len(backup_tapscripts) == 9\n",
    "\n",
    "# Construct taptree with huffman constructor\n",
    "tapscript_weights =  # TODO: implement\n",
    "                                \n",
    "multisig_taproot = TapTree(key=musig_ABC)\n",
    "multisig_taproot.huffman_constructor(tapscript_weights)\n",
    "\n",
    "print(\"Taproot descriptor {}\\n\".format(multisig_taproot.desc))\n",
    "\n",
    "# Derive segwit v1 address\n",
    "tapscript, taptweak, control_map = multisig_taproot.construct()\n",
    "taptweak = int.from_bytes(taptweak, 'big')\n",
    "output_pubkey = musig_ABC.tweak_add(taptweak)\n",
    "output_pubkey_b = output_pubkey.get_bytes()\n",
    "segwit_address =  # TODO: implement\n",
    "print(\"Segwit Address:\", segwit_address)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Start TestNodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test = util.TestWrapper()\n",
    "test.setup()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Generate Wallet Balance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test.nodes[0].generate(101)\n",
    "balance = test.nodes[0].getbalance()\n",
    "print(\"Balance: {}\".format(balance))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Send funds from the Bitcoin Core wallet to the taproot output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Send funds to taproot output.\n",
    "txid = test.nodes[0].sendtoaddress(address=segwit_address, amount=0.5, fee_rate=25)\n",
    "print(\"Funding tx:\", txid)\n",
    "\n",
    "# Deserialize wallet transaction.\n",
    "tx = CTransaction()\n",
    "tx_hex = test.nodes[0].getrawtransaction(txid)\n",
    "tx.deserialize(BytesIO(bytes.fromhex(tx_hex)))\n",
    "tx.rehash()\n",
    "\n",
    "print(tapscript.hex())\n",
    "\n",
    "print(tx.vout)\n",
    "\n",
    "# The wallet randomizes the change output index for privacy\n",
    "# Loop through the outputs and return the first where the scriptPubKey matches the segwit v1 output\n",
    "output_index, output = next(out for out in enumerate(tx.vout) if out[1].scriptPubKey == tapscript)\n",
    "output_value = output.nValue\n",
    "\n",
    "print(\"Segwit v1 output is {}\".format(output))\n",
    "print(\"Segwit v1 output value is {}\".format(output_value))\n",
    "print(\"Segwit v1 output index is {}\".format(output_index))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test spending paths of the taproot\n",
    "\n",
    "In the next section exercise, we'll construct three taproot spends:\n",
    "\n",
    "- one using the 3-of-3 musig key spending path (exercise)\n",
    "- one using one of the 3-of-5 short delay backup script spending path (example)\n",
    "- one using one of the 3-of-5 long delay backup script spending path (exercise)\n",
    "\n",
    "In each case we'll test the tx validity with the `testmempoolaccept()`, and verify that the timelock requirements work as intended. We'll also compute the weight of each spending transaction and compare."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Construct a spending transaction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Construct transaction\n",
    "spending_tx = CTransaction()\n",
    "\n",
    "# Populate the transaction version\n",
    "spending_tx.nVersion = 1\n",
    "\n",
    "# Populate the locktime\n",
    "spending_tx.nLockTime = 0\n",
    "\n",
    "# Populate the transaction inputs\n",
    "outpoint = COutPoint(tx.sha256, output_index)\n",
    "spending_tx_in = CTxIn(outpoint = outpoint)\n",
    "spending_tx.vin = [spending_tx_in]\n",
    "\n",
    "print(\"Spending transaction:\\n{}\".format(spending_tx))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Populate outputs\n",
    "\n",
    "We'll generate an output address in the Bitcoin Core wallet to send the funds to, determine the fee, and then populate the spending_tx with an output to that address."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generate new Bitcoin Core wallet address\n",
    "dest_addr = test.nodes[0].getnewaddress(address_type=\"bech32\")\n",
    "scriptpubkey = bytes.fromhex(test.nodes[0].getaddressinfo(dest_addr)['scriptPubKey'])\n",
    "\n",
    "# Determine minimum fee required for mempool acceptance\n",
    "min_fee = int(test.nodes[0].getmempoolinfo()['mempoolminfee'] * 100000000)\n",
    "\n",
    "# Complete output which returns funds to Bitcoin Core wallet\n",
    "dest_output = CTxOut(nValue=output_value - min_fee, scriptPubKey=scriptpubkey)\n",
    "spending_tx.vout = [dest_output]\n",
    "\n",
    "print(\"Spending transaction:\\n{}\".format(spending_tx))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.1.4 _Programming Exercise:_ Create a valid key path output\n",
    "\n",
    "In this exercise, we'll spend the taproot output using the key path. Since the key path is used, there is no control block to indicate whether or not the public key (Q) has an even or odd y-coordinate and so it is assumed that the y-coordinate is odd. Therefore, if Q needs to be negated, then so do all the private keys as well as the tweak."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Negate keys if necessary\n",
    "output_keyPath = output_pubkey\n",
    "privKeyA_keyPath = main_privkeyA_c\n",
    "privKeyB_keyPath = main_privkeyB_c\n",
    "privKeyC_keyPath = main_privkeyC_c\n",
    "tweak_keyPath = taptweak\n",
    "\n",
    "if output_keyPath.get_y()%2 != 0:\n",
    "    output_keyPath.negate()\n",
    "    privKeyA_keyPath.negate()\n",
    "    privKeyB_keyPath.negate()\n",
    "    privKeyC_keyPath.negate()\n",
    "    tweak_keyPath = SECP256K1_ORDER - taptweak\n",
    "\n",
    "# Create sighash for ALL\n",
    "sighash_musig =  # TODO: implement\n",
    " \n",
    "# Generate individual nonces for participants and an aggregate nonce point\n",
    "# Remember to negate the individual nonces if necessary\n",
    "R_agg =  # TODO: implement\n",
    "\n",
    "# Create an aggregate signature.\n",
    "# Remember to add a factor for the tweak\n",
    "sig_agg =  # TODO: implement\n",
    "print(\"Aggregate signature is {}\\n\".format(sig_agg.hex()))\n",
    "\n",
    "assert output_keyPath.verify_schnorr(sig_agg, sighash_musig)\n",
    "\n",
    "# Construct transaction witness\n",
    "spending_tx.wit.vtxinwit.append(  # TODO: implement\n",
    " \n",
    "print(\"spending_tx: {}\\n\".format(spending_tx))\n",
    "\n",
    "# Test mempool acceptance\n",
    "spending_tx_str = spending_tx.serialize().hex() \n",
    "assert test.nodes[0].testmempoolaccept([spending_tx_str])[0]['allowed']\n",
    "\n",
    "print(\"Key path spending transaction weight: {}\".format(test.nodes[0].decoderawtransaction(spending_tx_str)['weight']))\n",
    "\n",
    "print(\"Success!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.1.5 Example: Create a valid script path output for a short delay script\n",
    "\n",
    "In this example, we'll spend the output using a script path for the short delay script. This will not be accepted to the mempool initially, because the locktime has not been reached."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Construct transaction\n",
    "spending_tx = CTransaction()\n",
    "\n",
    "spending_tx.nVersion = 2\n",
    "spending_tx.nLockTime = 0\n",
    "outpoint = COutPoint(tx.sha256, output_index)\n",
    "spending_tx_in = CTxIn(outpoint=outpoint, nSequence=delay)\n",
    "spending_tx.vin = [spending_tx_in]\n",
    "spending_tx.vout = [dest_output]\n",
    "\n",
    "sighash = TaprootSignatureHash(spending_tx, [output], SIGHASH_ALL_TAPROOT, 0, scriptpath=True, script=tapscript_2a.script)\n",
    "\n",
    "witness_elements = []\n",
    "\n",
    "# Add signatures to the witness\n",
    "# Remember to reverse the order of signatures\n",
    "sigA = main_privkeyA.sign_schnorr(sighash)\n",
    "sigB = main_privkeyB.sign_schnorr(sighash)\n",
    "sigD = backup_privkeyD.sign_schnorr(sighash)\n",
    "\n",
    "# Add witness to transaction\n",
    "witness_elements = [sigD, sigB, sigA, tapscript_2a.script, control_map[tapscript_2a.script]]\n",
    "spending_tx.wit.vtxinwit.append(CTxInWitness(witness_elements))\n",
    "spending_tx_str = spending_tx.serialize().hex()\n",
    "\n",
    "# Test timelock\n",
    "assert_equal(\n",
    "    [{'txid': spending_tx.rehash(), 'allowed': False, 'reject-reason': 'non-BIP68-final'}],\n",
    "    test.nodes[0].testmempoolaccept([spending_tx_str])\n",
    ")\n",
    "\n",
    "print(\"Short delay script path spending transaction weight: {}\".format(test.nodes[0].decoderawtransaction(spending_tx_str)['weight']))\n",
    "\n",
    "print(\"Success!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Generate enough blocks to satisfy timelock and retest mempool acceptance\n",
    "\n",
    "Do not do this until you have completed the exercise above!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test.nodes[0].generate(delay - 1)\n",
    "\n",
    "# Timelock not satisfied - transaction not accepted\n",
    "assert not test.nodes[0].testmempoolaccept([spending_tx.serialize().hex()])[0]['allowed']\n",
    "\n",
    "test.nodes[0].generate(1)\n",
    "\n",
    "# Transaction should be accepted now that the timelock is satisfied\n",
    "assert test.nodes[0].testmempoolaccept([spending_tx.serialize().hex()])[0]['allowed']\n",
    "\n",
    "print(\"Success!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3.1.6 _Programming Exercise:_ Create a valid script path output for a long delay script\n",
    "\n",
    "In this exercise, we'll spend the output using a script path for the long delay script. This will not be accepted to the mempool initially, because the locktime has not been reached."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Construct transaction\n",
    "spending_tx = CTransaction()\n",
    "\n",
    "spending_tx.nVersion = 2\n",
    "spending_tx.nLockTime = 0\n",
    "outpoint = COutPoint(tx.sha256, output_index)\n",
    "spending_tx_in = CTxIn(outpoint=outpoint, nSequence=long_delay)\n",
    "spending_tx.vin = [spending_tx_in]\n",
    "spending_tx.vout = [dest_output]\n",
    "\n",
    "# Derive the sighash. Use tapscript_3a.\n",
    "sighash =  # TODO: implement\n",
    "\n",
    "witness_elements = []\n",
    "\n",
    "# Add signatures to the witness\n",
    "# Remember to reverse the order of signatures\n",
    "witness_elements =  # TODO: implement\n",
    "\n",
    "# Construct transaction witness\n",
    "spending_tx.wit.vtxinwit.append(CTxInWitness(witness_elements))\n",
    "spending_tx_str = spending_tx.serialize().hex()\n",
    "\n",
    "# Test timelock\n",
    "assert_equal(\n",
    "    [{'txid': spending_tx.rehash(), 'allowed': False, 'reject-reason': 'non-BIP68-final'}],\n",
    "    test.nodes[0].testmempoolaccept([spending_tx_str])\n",
    ")\n",
    "\n",
    "print(\"Long delay script path spending transaction weight: {}\".format(test.nodes[0].decoderawtransaction(spending_tx_str)['weight']))\n",
    "\n",
    "print(\"Success!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Generate enough blocks to satisfy timelock and retest mempool acceptance\n",
    "\n",
    "Do not do this until you have completed the exercise above!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test.nodes[0].generate(long_delay - delay - 1)\n",
    "\n",
    "# Timelock not satisfied - transaction not accepted\n",
    "assert not test.nodes[0].testmempoolaccept([spending_tx.serialize().hex()])[0]['allowed'] \n",
    "\n",
    "test.nodes[0].generate(1)\n",
    "\n",
    "# Transaction should be accepted now that the timelock is satisfied\n",
    "assert test.nodes[0].testmempoolaccept([spending_tx.serialize().hex()])[0]['allowed']\n",
    "\n",
    "print(\"Success!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Shutdown"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test.shutdown()"
   ]
  }
 ],
 "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
}