In recent years, the Bitcoin ecosystem has developed rapidly but still faces many technical challenges and bottlenecks. As the number of users and transaction volumes increase, issues related to the efficiency, privacy, and flexibility of the Bitcoin network have become more prominent. To address these issues, the Bitcoin community introduced Bitcoin Improvement Proposals (BIPs) to add new features and improvements to the Bitcoin network.

Taproot Technology and Its Principles

At the end of 2021, Bitcoin underwent the Taproot upgrade, aiming to significantly enhance Bitcoin's performance and user experience. The Taproot upgrade is a collection of three BIPs, including Schnorr Signatures (BIP 340), Taproot (BIP 341), and TapScript (BIP 342), collectively known as BIP Taproot.

• Schnorr Signatures (BIP 340): The key aggregation feature of Schnorr allows participants in a single multi-signature transaction to collaboratively combine their public keys and generate an aggregate signature valid for their combined public key. This saves block space, enhances privacy, and enables faster transaction verification.
• Taproot (BIP 341): Defines Pay-to-Taproot (P2TR), a new way of sending Bitcoin. P2TR combines the functionalities of Pay-to-Public-Key (P2PK) and Pay-to-Script-Hash (P2SH) scripts, offering users great flexibility and privacy advantages.
• TapScript (BIP 342): Updates the scripting language used to write BTC transaction parameters to accommodate users using Schnorr and Taproot technologies.

The principle of Taproot is to define an output and two spending paths. As illustrated above, with two participants, Alice and Bob, the Taproot operation process is as follows:

• Aggregate Alice and Bob's public keys: C = P_A + P_B.
• Add MerkleRoot, and aggregate the public key as: P = C + H(C||MerkleRoot)G, where H(C||MerkleRoot) represents the combined hash of C and MerkleRoot.
• Fill the aggregated public key P into the locking script, similar to Segwit format: [ver] [P]. Here, ver represents the version number, with ver=1 in Taproot.
• There are two spending paths, one of which can be chosen:
  • Signature Mode: Alice and Bob both sign to generate an aggregate signature, which is filled into the witness script. After verifying the signature against the aggregate public key P, the spending can be completed.
  • Script Mode: If one of Alice or Bob refuses to sign, the script mode can be used. If Alice wants to complete the spending, the witness script needs to include: execution data D that complies with Script 1, Script 1, C, and Hash 2. To verify the signature, first use Script 1 and Hash 2 to compute MerkleRoot, then verify if P == C + H(C||MerkleRoot)G holds, and finally construct the complete script D||Script 1 and execute it, verifying if the result is true. Once the above verification passes, the spending is completed.

When spending in signature mode, multiple participants and single participants appear indistinguishable on the blockchain, making many blockchain analyses ineffective and preserving privacy for all Taproot users. The script spending mode of Taproot provides a solution for cases where some signers cannot or refuse to sign, allowing participants to complete transactions through predefined conditions and script paths. This way, even if not all signers agree to the transaction, the remaining participants can still spend according to preset conditions.

Huffman Tree

The Huffman Tree, proposed by David Huffman in 1952, is an optimal binary tree used for data compression. Its main application is in the field of data compression, such as file compression and image compression. It achieves data compression by assigning shorter codes to frequently occurring characters and longer codes to less frequent characters.

The Huffman Tree is the tree with the shortest weighted path length, where nodes with larger weights are closer to the root, and nodes with smaller weights are farther from the root. Its construction process uses a greedy approach, selecting the two nodes with the smallest weights each time to combine into a new node, adding it to the original set, and repeating the process until completion. As illustrated above, with a weight set of (1, 2, 3, 4, 5), the Huffman Tree construction process is as follows:

• Select the nodes with the smallest weights, 1 and 2, and combine them into a node with a weight of 3, resulting in a set of (3, 3, 4, 5).
• Select the nodes with the smallest weights, 3 and 3, and combine them into a node with a weight of 6, resulting in a set of (4, 5, 6).
• Select the nodes with the smallest weights, 4 and 5, and combine them into a node with a weight of 9, resulting in a set of (6, 9).
• Select the nodes with the smallest weights, 6 and 9, and combine them into a node with a weight of 15, resulting in a set of (15), ending the construction process.

Application of Huffman Tree in Taproot

Compared to ECDSA (Elliptic Curve Digital Signature Algorithm), a major advantage of Taproot is that Schnorr aggregate signatures can compress multiple signature data into a single aggregate signature. After using aggregate signature technology, the byte size of the transaction script is significantly reduced, effectively lowering the transaction fees.

In signature mode, as the number of participants increases, the size of ECDSA transaction scripts grows linearly, while the size of Taproot transaction scripts remains unchanged. In script mode, as the number of scripts increases, the size of ECDSA transaction scripts grows linearly, while the size of Taproot transaction scripts grows logarithmically.

When spending in script mode, using the tree structure of MAST, the size of Taproot transaction scripts grows logarithmically with the number of scripts. However, by using the Huffman Tree, we can improve the construction process of MAST, helping to further reduce the byte size of witness scripts in script spending mode, ultimately achieving lower transaction fees.

As mentioned earlier, when spending in script mode with Taproot, proof of the script in MAST is required. As illustrated above, when we want to spend using script_A, the witness script needs to provide:

• Execution data D that complies with script_A
• script_A
• P
• TaggedHash(B), TaggedHash(C) TaggedHash represents a tagged hash, with a fixed length of 32 bytes. The purpose of using tagged hash is to reduce hash collisions.

Ignoring the byte size of the first two items, it can be seen that the byte size of the last item can be represented as 32*(d-1), where d=3 represents the height of script_A in MAST. In other words, the byte size of the last item is linearly related to the height of the script in MAST. Therefore, for scripts script_A, script_B, and script_C, we can assign weights based on their usage frequency and construct a Huffman Tree. This can place frequently used scripts at lower heights, reducing the byte size of witness scripts and ultimately lowering transaction fees.

In summary, transaction fees are closely related to the byte size of transaction scripts.

The introduction of Taproot marks an important step forward for the Bitcoin network in terms of efficiency, privacy, and flexibility. By adopting new technologies such as Schnorr signatures, MAST, and TapScript, Taproot not only significantly reduces the byte size of transaction scripts and lowers transaction fees but also enhances user privacy. The strategy of using Huffman Tree to optimize MAST construction further reduces the byte size of witness scripts in script spending mode, providing Bitcoin users with a more efficient transaction experience.

Bitcoin Layer 2 solution BEVM uses Taproot as one of the core architectures of its "Taproot Consensus" technology, bringing explosive growth to the Bitcoin ecosystem. As these improvements gradually become widespread, the Bitcoin network will be able to handle larger-scale users and transaction volumes, providing global users with more secure and convenient encryption services.