Minimalizing Witness weight for Taproot spend script paths with Huffman's Algorithm

TLDR

I implement a Huffman Taptree constructor in Typescript for Bitcoinjs-lib. Find the code here.

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 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 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 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.

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.

Implementation

Let's define types to be used in the implementation.

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

function sortScriptsIntoTree(inputs: Inputs): Taptree | undefined {}

Step 1

Create a sorted list of nodes from our inputs.

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.

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.

// 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.

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.

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:

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 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.
You can find the github repo for this article, here