2.4-taptree.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import util\n",
    "from test_framework.address import program_to_witness\n",
    "from test_framework.key import ECPubKey, generate_bip340_key_pair\n",
    "from test_framework.messages import CTxInWitness, ser_string\n",
    "from test_framework.script import tagged_hash, Tapbranch, TapTree, TapLeaf, CScript, TaprootSignatureHash, OP_CHECKSIG, SIGHASH_ALL_TAPROOT"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2.4 TapTree\n",
    "\n",
    "In this chapter we consider how to commit multiple tapscripts to a taptweak. This can be achieved with a binary tree commitment structure. We will also introduce taproot descriptors, which are composed of tapscript descriptors and reflect the binary tree commitment structure of a taproot output.\n",
    "\n",
    "* **Part 1 - Constructing a taptree**\n",
    "    * Taptree commitments\n",
    "    * Taproot descriptors\n",
    "    * Taptree construction\n",
    "    \n",
    "In part 2, we consider spending the taproot output along the script path for taproot outputs with taptree commitments, which have more than 1 commited tapscript. This requires an inclusion proof for the tapscript being spent.\n",
    "\n",
    "* **Part 2 - Taproot script path**\n",
    "    * Script path spending for taptrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1: Constructing a taptree\n",
    "\n",
    "### Taptree binary tree commitments\n",
    "\n",
    "Committing multiple tapscripts requires a commitment structure resembling merkle tree construction.\n",
    "\n",
    "**The TapTree is different than the header merkle tree in the following ways:**\n",
    "\n",
    "* Tapleaves can be located at different heights.\n",
    "* Ordering of TapLeaves is determined lexicograpically.\n",
    "* Location of nodes are tagged (No ambiguity of node type).\n",
    " \n",
    "Internal nodes are called tapbranches, and are also computed with the `tagged_hash(\"Tag\", input_data)` function.\n",
    " \n",
    "Tagged hashes are particularly useful when building a taptree commitment. They prevent node height ambiguity currently found in the transaction merkle tree, which allows an attacker to create a node which can be reinterpreted as either a leaf or internal node. Tagged hashes ensure that a tapleaf cannot be misinterpreted as an internal node and vice versa."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![test](images/taptree0.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### _Programming Exercise 2.4.1:_ Compute a taptweak from a taptree\n",
    "\n",
    "In the cell below, we will commit three pay-to-pubkey scripts to a taptweak and then derive the bech32m address. We will use the same merkle tree structure as in the previous illustration.\n",
    "\n",
    "1. Compute TapLeaves A, B and C.\n",
    "2. Compute Internal TapBranch AB.\n",
    "3. Compute TapTweak\n",
    "4. Derive the bech32m address."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "TAPSCRIPT_VER = bytes([0xc0])  # See tapscript chapter for more details.\n",
    "internal_pubkey = ECPubKey()\n",
    "internal_pubkey.set(bytes.fromhex('03af455f4989d122e9185f8c351dbaecd13adca3eef8a9d38ef8ffed6867e342e3'))\n",
    "\n",
    "# Derive pay-to-pubkey scripts\n",
    "privkeyA, pubkeyA = generate_bip340_key_pair()\n",
    "privkeyB, pubkeyB = generate_bip340_key_pair()\n",
    "privkeyC, pubkeyC = generate_bip340_key_pair()\n",
    "scriptA = CScript([pubkeyA.get_bytes(), OP_CHECKSIG])\n",
    "scriptB = CScript([pubkeyB.get_bytes(), OP_CHECKSIG])\n",
    "scriptC = CScript([pubkeyC.get_bytes(), OP_CHECKSIG])\n",
    "\n",
    "# Method: Returns tapbranch hash. Child hashes are lexographically sorted and then concatenated.\n",
    "# l: tagged hash of left child\n",
    "# r: tagged hash of right child\n",
    "def tapbranch_hash(l, r):\n",
    "    return tagged_hash(\"TapBranch\", b''.join(sorted([l,r])))\n",
    "\n",
    "# 1) Compute TapLeaves A, B and C.\n",
    "# Method: ser_string(data) is a function which adds compactsize to input data.\n",
    "hash_inputA =  # TODO: implement\n",
    "hash_inputB =  # TODO: implement\n",
    "hash_inputC =  # TODO: implement\n",
    "taggedhash_leafA =  # TODO: implement\n",
    "taggedhash_leafB =  # TODO: implement\n",
    "taggedhash_leafC =  # TODO: implement\n",
    "\n",
    "# 2) Compute Internal node TapBranch AB.\n",
    "# Method: use tapbranch_hash() function\n",
    "internal_nodeAB = # TODO: implement\n",
    "\n",
    "# 3) Compute TapTweak.\n",
    "rootABC =  # TODO: implement\n",
    "taptweak =  # TODO: implement\n",
    "print(\"TapTweak:\", taptweak.hex())\n",
    "\n",
    "# 4) Derive the bech32m address.\n",
    "taproot_pubkey_b = internal_pubkey.tweak_add(taptweak).get_bytes()\n",
    "bech32m_address = program_to_witness(1, taproot_pubkey_b)\n",
    "print('Bech32m address:', bech32m_address)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2.4.2: Compute a taptweak with the TapTree class\n",
    "\n",
    "Run the cell below to validate your your taptree commitment in 2.4.1.\n",
    "\n",
    "* The `TapTree` class allows us to build a taptree structures from `TapLeaf` objects. It can be instantiated with an internal pubkey `key` and a taptree root `root`.\n",
    "    * `TapTree.root` is the root node of the merkle binary tree.\n",
    "    * `TapBranch` objects represents internal tapbranches, and have `Tapbranch.left` and `Tapbranch.right` members.\n",
    "    * `TapTree.construct()` returns the triple `segwit_v1_script`, `tweak`, `control_map`.\n",
    "        * `segwit_v1_script` - segwit v1 output script.\n",
    "        * `tweak` with the committed taptree.\n",
    "        * `control_map` stores Cscript - controlblock pairs for spending committed tapscripts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Construct tapleaves\n",
    "tapleafA = TapLeaf().construct_pk(pubkeyA)\n",
    "tapleafB = TapLeaf().construct_pk(pubkeyB)\n",
    "tapleafC = TapLeaf().construct_pk(pubkeyC)\n",
    "\n",
    "# Construct taptree nodes.\n",
    "tapbranchAB = Tapbranch(tapleafA, tapleafB)\n",
    "tapbranchABC = Tapbranch(tapbranchAB, tapleafC)\n",
    "\n",
    "# Construct the taptree.\n",
    "taptree = TapTree(key=internal_pubkey, root=tapbranchABC)\n",
    "\n",
    "segwit_v1_script, tweak, control_map = taptree.construct()\n",
    "print(\"Your taptweak computed in 2.4.1 is correct:\", tweak == taptweak)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Taproot descriptors\n",
    "\n",
    "For taproot, we propose a taproot descriptor expression which can be composed from its individual tapscripts. The structure of the taptree is not unique to set of tapscripts, and so must also be captured by the taproot descriptor. Consider the example below with 5 `ts(pk(key))` tapscripts."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![test](images/taptree1.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A taproot descriptor consist of:\n",
    "\n",
    "* `tp(internal_key, [tapscript, [tapscript', tapscript'']])`\n",
    "* `tp(internal_key, [tapscript])` for single tapscript commitments.\n",
    "* Each node is represented as a tuple of its children, and can be nested within other node expressions.\n",
    "* The left or right ordering of the children is not unique, since they are ultimately ordered lexicographically when computing the taptweak."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2.4.3 - Constructing a taptree from a descriptor."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![test](images/taptree2.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example, we will construct the taptree shown in the descriptor string above. This can be conveniently done by parsing the descriptor string.\n",
    "\n",
    "* **Class: `TapTree`**\n",
    "    * Construct from descriptor:\n",
    "        * `TapTree.from_desc(descriptor_string)`\n",
    "    * Serialize back to descriptor:\n",
    "        * `TapTree.desc`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generate internal key pairs\n",
    "privkey_internal, pubkey_internal = generate_bip340_key_pair()\n",
    "pk_hex = pubkey_internal.get_bytes().hex()\n",
    "\n",
    "# Construct descriptor string\n",
    "ts_desc_A = 'ts(pk({}))'.format(pubkeyA.get_bytes().hex())\n",
    "ts_desc_B = 'ts(pk({}))'.format(pubkeyB.get_bytes().hex())\n",
    "ts_desc_C = 'ts(pk({}))'.format(pubkeyC.get_bytes().hex())\n",
    "tp_desc = 'tp({},[[{},{}],{}])'.format(pk_hex,\n",
    "                                       ts_desc_A,\n",
    "                                       ts_desc_B,\n",
    "                                       ts_desc_C)\n",
    "print(\"Raw taproot descriptor: {}\\n\".format(tp_desc))\n",
    "\n",
    "# Generate taptree from descriptor\n",
    "taptree = TapTree()\n",
    "taptree.from_desc(tp_desc)\n",
    "\n",
    "# This should match the descriptor we built above\n",
    "assert taptree.desc == tp_desc\n",
    "\n",
    "# Compute taproot output\n",
    "taproot_script, tweak, control_map = taptree.construct()\n",
    "\n",
    "print(\"Taproot script hex (Segwit v1):\", taproot_script.hex())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Taptree construction with the Huffman constructor\n",
    "\n",
    "Huffman encoding can optimize the taptree structure, and thus potentially lower the size of revealed branches, by taking into account the estimated frequency by which each TapLeaf will occur. Since some spending scenarios are more likely to occur than others, ideally we would optimize the tree structure such that those spends appear closer to the root of the tree, and therefore require a smaller merkle proof when spending.\n",
    "\n",
    "For more details on how the Huffman encoder constructs the taptree, see optional chapter 2.5.\n",
    "\n",
    "#### Example 2.4.4 - Building a TapTree with the huffman constructor\n",
    "\n",
    "We reconstruct the same taptree from the above examples using the `huffman_constructor()`. That function takes a list of `(weight,tapleaf)` tuples, where `weight` is an `int` and `tapleaf` is a `TapLeaf` object. A higher weight:\n",
    "   \n",
    "* Indicates a higher likelihood of execution\n",
    "* Means the script will be placed closer to the root if possible\n",
    "* Results in a smaller inclusion proof and lower spending fees\n",
    "\n",
    "Note that the internal pubkey still needs to be provided when instantiating the `TapTree` object. `huffman_constructor()` only constructs the script tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "taptree3 = TapTree(key=pubkey_internal)\n",
    "taptree3.huffman_constructor([(1, tapleafA), (1, tapleafB), (2, tapleafC)])\n",
    "print(\"taptree3 descriptor: {}\\n\".format(taptree3.desc))\n",
    "\n",
    "# Compare the resulting taproot script with that from example 2.4.3.\n",
    "taproot_script3, tweak3, control_map3 = taptree3.construct()\n",
    "assert taproot_script3 == taproot_script\n",
    "print(\"Success!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2: Spending along the Script Path\n",
    "\n",
    "A Taproot output is spent along the script path with the following witness pattern:\n",
    "\n",
    "* Witness to spend TapScript_A:\n",
    "\n",
    "    * `[Stack element(s) satisfying TapScript_A]`\n",
    "    * `[TapScript_A]` \n",
    "    * `[Controlblock c]`\n",
    "\n",
    "Compared to the script spend path of a taproot with a single committed tapscript, the controlblock spending a taproot containing multiple tapscripts will also include a script inclusion proof.\n",
    "\n",
    "* Controlblock c contains:\n",
    "\n",
    "    * `[Tapscript Version]` \n",
    "        * `0xfe & c[0]`\n",
    "    * `[Parity bit (oddness of Q's y-coordinate)]`\n",
    "        * `0x01 & c[0]` \n",
    "    * `[Internal Public Key]` \n",
    "        * `c[1:33]`\n",
    "    * `[Script Inclusion Proof]` \n",
    "        * `n x 32Bytes`\n",
    "        \n",
    "Note that this script inclusion proof is a 32B multiple and its size will depend on the position of tapscript in the taptree structure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![test](images/taptree5.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Generating the Controlblock**\n",
    "\n",
    "We use the the taptree construct method to generate the taproot output, tweak and controlblocks for all tapscripts.\n",
    "\n",
    "**`TapTree.construct()` returns the tuple:**\n",
    "* `taproot_output_script`, `tweak`, `control_block_map`\n",
    "* `control_block_map` has key-value pairs: \n",
    "    * `tapscript.script` - `controlblock`        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### _Programming Exercise 2.4.5_ - Constructing a taproot output from a taptree\n",
    "\n",
    "In the following exercise, please construct the output and bech32m address for a taptree with 4 leaves using with the huffman taptree constructor, so that it results in a balanced tree. Please generate new keys for the internal key and pay-to-pubkey tapscripts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generate key pairs for internal pubkey and pay-to-pubkey tapscripts\n",
    "privkey_internal, pubkey_internal = generate_bip340_key_pair()\n",
    "\n",
    "privkeyA, pubkeyA = generate_bip340_key_pair()\n",
    "privkeyB, pubkeyB = generate_bip340_key_pair()\n",
    "privkeyC, pubkeyC = generate_bip340_key_pair()\n",
    "privkeyD, pubkeyD = generate_bip340_key_pair()\n",
    "\n",
    "# Construct pay-to-pubkey tapleaves and taptree\n",
    "TapLeafA =  # TODO: implement\n",
    "TapLeafB =  # TODO: implement\n",
    "TapLeafC =  # TODO: implement\n",
    "TapLeafD =  # TODO: implement\n",
    "\n",
    "# Create a taptree with tapleaves and huffman constructor\n",
    "# Method: TapTree.huffman_constructor(tuple_list)\n",
    "taptree =  # TODO: implement\n",
    "taptree.huffman_constructor(  # TODO: implement\n",
    "\n",
    "# Generate taproot tree with the `construct()` method, then use the taproot bytes to create a bech32m address\n",
    "taproot_script, tweak, control_map = taptree.construct()\n",
    "taproot_pubkey = pubkey_internal.tweak_add(tweak) \n",
    "program = taproot_pubkey.get_bytes()\n",
    "address = program_to_witness(1, program)\n",
    "print(\"Address: {}\".format(address))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise - Spending a taproot output along a script path\n",
    "\n",
    "In this exercise, we will send funds to the previously generated address in exercise 2.4.6, and spend this output along the `TapScript0` path."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2.4.6: Start Bitcoin Core node and send coins to the taproot address\n",
    "\n",
    "Only run setup once, or after a clean shutdown."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Start node\n",
    "test = util.TestWrapper()\n",
    "test.setup()\n",
    "node = test.nodes[0]\n",
    "\n",
    "# Generate coins and create an output\n",
    "tx = node.generate_and_send_coins(address)\n",
    "print(\"Transaction {}, output 0\\nsent to {}\\n\".format(tx.hash, address))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example 2.4.7: Construct `CTransaction` and populate fields\n",
    "\n",
    "We use the `create_spending_transaction(node, txid)` convenience function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create a spending transaction\n",
    "spending_tx = test.create_spending_transaction(tx.hash, version=2)\n",
    "\n",
    "print(\"Spending transaction:\\n{}\".format(spending_tx))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### _Programming Exercise 2.4.8:_ Sign the transaction for `TapLeafA` \n",
    "\n",
    "Note that we must pass the following arguments to `TaprootSignatureHash` for script path spending:\n",
    "* `scriptpath`: `True`\n",
    "* `script`: `Cscript` of tapscript"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generate the taproot signature hash for signing\n",
    "sighashA = TaprootSignatureHash(spending_tx,\n",
    "                               [tx.vout[0]],\n",
    "                               SIGHASH_ALL_TAPROOT,\n",
    "                               input_index=0,\n",
    "                               scriptpath=  # TODO: implement\n",
    "                               script=  # TODO: implement\n",
    "\n",
    "signatureA =  # TODO: implement\n",
    "\n",
    "print(\"Signature for TapLeafA: {}\\n\".format(signatureA.hex()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### _Programming Exercise  2.4.9:_ Construct the witness, add it to the transaction and verify mempool acceptance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add witness to transaction\n",
    "# Tip: Witness stack for script path - [satisfying elements for tapscript] [TapLeaf.script] [controlblock]\n",
    "# Tip: Controlblock for a tapscript in control_map[TapLeaf.script]\n",
    "witness_elements =  # TODO: implement\n",
    "spending_tx.wit.vtxinwit.append(CTxInWitness(witness_elements))\n",
    "\n",
    "# Test mempool acceptance\n",
    "assert node.test_transaction(spending_tx)\n",
    "print(\"Success!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Shutdown TestWrapper"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test.shutdown()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Congratulations!** In this chapter, you have:\n",
    "\n",
    "- Constructed a binary tree of individual tapscripts into a taptree.\n",
    "- Computed the hash commitment of that taptree and used it to tweak the internal taproot public key.\n",
    "- Used descriptors to specify and construct a taptree of scripts.\n",
    "- Sent coins to a segwit v1 output with a tweaked public key committing to a taptree, and later spent that output by using the script path to an individual tapscript."
   ]
  }
 ],
 "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
}