Minimalizing Witness weight for Taproot spend script paths with Huffman's Algorithm
Tags: bitcoin, taproot, javascript
Published: 2023-03-26 05:54:22

## TLDR
I implement a Huffman Taptree constructor in Typescript for Bitcoinjs-lib. Find the code [here](https://github.com/Eunovo/bitcoinjs-huffman-constructor).

## Introduction
Taproot is a recent upgrade to Bitcoin that enhances the privacy and efficiency of complex transactions by introducing a new type of output that can be spent either by providing a signature for the public key (keypath spend) or by satisfying a script contained within the hidden "script-tree". A script-tree is a kind of [Merkle tree](https://en.wikipedia.org/wiki/Merkle_tree) that encodes a hierarchy of scripts that represent different spending scenarios, each with a unique path from the root. Spending any of these scripts requires a proof that the script is present in the tree. The length of the proof depends on the position of the script in the tree. Longer proofs incur more transaction fees because they create larger transactions.

One way to reduce transaction fees is to arrange your script-tree such that the scripts that are more likely to be used for spending, require shorter proof. These scripts need to be closer to the root of the tree. We can use [Huffman's Algorithm](https://en.wikipedia.org/wiki/Huffman_coding) to arrange the script-tree so that the most likely or frequent spend paths are shorter and incur less transaction fees.

Bitcoinops' [Schnorr Taproot workshop](https://colab.research.google.com/github/bitcoinops/taproot-workshop/blob/Colab/2.5-huffman.ipynb#scrollTo=NQldp2NExVC3) has a great section on "Huffman TapTree Constructors". I'll show how to implement this in Typescript for bitcoinjs-lib. You can find the github repo for this article, [here](https://github.com/Eunovo/bitcoinjs-huffman-constructor).

What we are trying to minimize is the `Expected-witness-weight`:
```
Expected-witness-weight =
      Probability-of-A * Witness-weight-A
    + Probability-of-B * Witness-weight-B
    + Probability-of-C * Witness-weight-C
```
We can minimize the expected witness weight by putting those scripts with higher probability closer to the root of the tree.

## The Method
Suppose we have three spend scripts represented by A, B and C. We determine that B is twice as likely to be spent as A and C, so we assign the scripts the following weights:
`A: 1, B: 2, C: 1`

We want to arrange our script-tree such that B is much closer to the root than A and C. We will use Huffman's algorithm and take the following steps:

1. Sort the scripts A, B and C by weight in ascending order and put them in a queue.
2. Pick the first two nodes in the queue and create a new branch from the two of them. Set the weight of this new node to be the sum of the weights of its children. 
3. Put this new node back into the queue with sorting order maintained. That is, we must find the correct position for the new node given its weight and put it there.
4. Repeat steps 2 and 3 until there's only one node left in the queue. This node is the root node for the script-tree.

![Huffman taptree constructor example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/c1qq6ma5pc3aisbbjj8x.png)

## Implementation
Let's define types to be used in the implementation.
```Typescript
import { Tapleaf, Taptree } from "bitcoinjs-lib/src/types";

export type Inputs = { weight: number, leaf: Tapleaf }[];
export type Node = {
    weight: number,
    node: Taptree
}
```
We use bitcoinjs-lib's `Tapleaf` and `Taptree` because we want to be able to use our resulting script-tree with bitcoinjs-lib.

This is our function definition
```Typescript
function sortScriptsIntoTree(inputs: Inputs): Taptree | undefined {}
```
### Step 1
Create a sorted list of nodes from our inputs.
```Typescript
const nodes: Node[] = inputs
    .map((value) => ({
        weight: value.weight,
        node: value.leaf
    }));
    
const sortedNodes = new SortedList(
    nodes,
    (a, b) => a.weight - b.weight
); // Create a list sorted in ascending order of frequency
```
_I've created a `SortedList` class to handle creating and maintaining a sorted list. See the code, [here](https://github.com/Eunovo/bitcoinjs-huffman-constructor/blob/main/src/utils.ts)._

### Step 2
Pick the first two nodes in the queue and create a new branch from the two of them. Set the weight of this new node to be the sum of the weights of its children.
```Typescript
// Construct a new node from the two nodes with the least frequency
nodeA = sortedNodes.pop()!; // There will always be an element to pop
nodeB = sortedNodes.pop()!; // because loop ends when length <= 1
newNode = {
    weight: nodeA.weight + nodeB.weight,
    node: [nodeA.node, nodeB.node]
};
```

### Step 3
Put this new node back into the queue with sorting order maintained. That is, we must find the correct position for the new node given its weight and put it there.
```Typescript
sortedNodes.insert(newNode);
```
_The `SortedList` class will use binary search to find the correct index for the new node in the sorted list_

### Step 4
Repeat steps 2 and 3 until there's only one node left in the queue. This node is the root node for the script-tree.
```Typescript
let newNode: Node;
let nodeA: Node, nodeB: Node;
while (sortedNodes.length() > 1) {
    // Construct a new node from the two nodes with the least frequency
    nodeA = sortedNodes.pop()!; // There will always be an element to pop
    nodeB = sortedNodes.pop()!; // because loop ends when length <= 1
    newNode = {
        weight: nodeA.weight + nodeB.weight,
        node: [nodeA.node, nodeB.node]
    };
    // Place newNode back into sorted list
    sortedNodes.insert(newNode);
}

// Last node in sortedNodes is the root node
const root = sortedNodes.pop();
```

The complete `sortScriptsIntoTree` function looks like this:
```Typescript
export function sortScriptsIntoTree(inputs: Inputs): Taptree | undefined {
    const nodes: Node[] = inputs
        .map((value) => ({
            weight: value.weight,
            node: value.leaf
        }));
        
    const sortedNodes = new SortedList(
        nodes,
        (a, b) => a.weight - b.weight
    ); // Create a list sorted in ascending order of frequency

    let newNode: Node;
    let nodeA: Node, nodeB: Node;
    while (sortedNodes.length() > 1) {
        // Construct a new node from the two nodes with the least frequency
        nodeA = sortedNodes.pop()!; // There will always be an element to pop
        nodeB = sortedNodes.pop()!; // because loop ends when length <= 1
        newNode = {
            weight: nodeA.weight + nodeB.weight,
            node: [nodeA.node, nodeB.node]
        };
        // Place newNode back into sorted list
        sortedNodes.insert(newNode);
    }

    // Last node in sortedNodes is the root node
    const root = sortedNodes.pop();
    return root?.node;
}
```

## Testing
The [tests folder](https://github.com/Eunovo/bitcoinjs-huffman-constructor/tree/main/tests) contains tests for the huffman constructor and the SortedList class. I check that the huffman constructor works when scripts are provided with equal weights, negative weights, infinity etc. I encourage you to take a look as this is the only way you can tell that the huffman constructor is doing what you expect it to do.

## Conclusion
Thank you for reading, if you need help understanding how to spend taproot script paths, check out my article on [creating taproot scripts](https://dev.to/eunovo/a-guide-to-creating-taproot-scripts-with-bitcoinjs-lib-4oph).
You can find the github repo for this article, [here](https://github.com/Eunovo/bitcoinjs-huffman-constructor)