Summary

On August 20th, 2023, one of our top 50 whitehats, Kayaba, identified a vulnerability in Threshold Network’s tBTC. This vulnerability was concerned with the inherent malleability of Bitcoin transactions, which, in combination with the Threshold Network’s SPV proof verifier, allowed arbitrary transactions to be included using feasible brute force.

In recognition of Kayaba’s discovery, he was rewarded with $50,000 worth of Threshold’s T tokens.

What is the Threshold network?

The Threshold Network is a collection of related decentralized services based on “threshold cryptography”, which is a type of consensus encryption/decryption protocol relying on the cooperation of multiple secret-keepers to decrypt or access a secret, similar to how multi-signature wallets work.

The “threshold” is a minimum number of signers or network participants who are needed to sign a transaction or approve a network action. This is an oversimplification of course, but it’ll work for understanding this vulnerability.

For the full exploration of threshold cryptography, it’s highly recommended that you check out this article by the Massachusetts Institute of Technology.

One of these services is tBTC, which provides an asset bridge from the Bitcoin blockchain to the Ethereum mainnet, allowing users to use their Bitcoin to access DeFi and other tools in the Ethereum ecosystem.

Bitcoin nodes participating in the Threshold Network use SPV, a more lightweight method that is popular with node operators as it is a less resource intensive way to verify Bitcoin transactions. However, the way that the Bitcoin Merkle root is constructed has some weaknesses, one of which allows for the inclusion of arbitrary transactions when verified by SPV clients.

How is the Merkle tree constructed?

Here’s a visualization of the Merkle tree:

Image source: https://iq.opengenus.org/merkle-trees-and-spvs-in-bitcoin/

Suppose we have four transactions A, B, C & D:

1. Initial Hashing (Leaves of the Tree)

• HashA = SHA256(SHA256(TxA))
• HashB = SHA256(SHA256(TxB))
• HashC = SHA256(SHA256(TxC))
• HashD = SHA256(SHA256(TxD))

2. Pairing and Hashing (Intermediate Nodes)

Pair and hash the hashes obtained in step 1:

• HashAB = SHA256(HashA + HashB)
• HashCD = SHA256(HashC + HashD)

3. Pairing and Hashing Again (Root of the Tree)

Pair and hash the intermediate hashes:

• MerkleRoot(HashABCD) = SHA256(HashAB + HashCD)

The resulting MerkleRoot is then included in the block header.

This structure allows any participant in the network to efficiently verify the inclusion of a transaction in the block without needing to download the entire block. They can validate the authenticity of a transaction by following the path from the transaction’s hash up to the Merkle root.

What is SPV?

SPV, or Simplified Payment Verification, is a method used by light Bitcoin clients to verify transactions without downloading the entire blockchain. Instead of storing the entire blockchain, SPV clients only download block headers, which contain essential information like the Merkle root and block hash.

When an SPV client needs to verify a transaction, it requests relevant information from full nodes in the Bitcoin network. These nodes provide the SPV client with a Merkle proof, a cryptographic method used to confirm the inclusion of a specific transaction within a block.

The proof is crafted by collecting every node along the path connecting the Merkle root to the transaction in question, bundling them together to form the proof.

The hash path is then checked against the Merkle root included in the block header. If the hashes match, it confirms that the transaction is indeed included in the block.

Image source: https://iq.opengenus.org/merkle-trees-and-spvs-in-bitcoin/

For example, to confirm the inclusion of transaction K in a block, a node can provide a path composed of four hashes: HL, HIJ, HMNOP, HABCDEFGH. Utilizing this path, an SPV can calculate four hashes, HKL, HIJKL, HIJKLMNOP and validate K’s presence in the block by comparing the Merkle root.

Vulnerability Analysis:

As mentioned above, SPV is a lightweight method of verifying transactions on the Bitcoin network using information from the block header and merkle proof.

However, since the block header does not contain the number of transactions, SPV clients are not initially aware of the total transactions within the block, and consequently, lack knowledge of the accurate tree depth.

In the merkle tree, the H( ) values consist of 32 bytes, while the T values, representing transactions or leaves of the Merkle tree, are 64 bytes long. To fit the transaction into our merkle tree which only accepts 32 byte values, we must hash the T value resulting in H(T). Now to get the parent node of two leaf nodes we simply concatenate them and hash them H( H(T) . H(T) ).

The hashing of two values within the merkle tree, H( H(T) . H(T) ), looks very similar to the hashing of a valid transaction to be included. If we take our 64 byte transaction and split it into two sides of 32 bytes, T₁ and T₂, we see the parent of T, H(T), can also be described as H( T₁ . T₂ ).

Within this transaction, the last 32 bytes, T₂, are less constrained compared to the first 32 bytes, T₁. This is because the last 32 bytes contain multiple values which are controllable by a transaction creator. This creates the possibility that in a valid 64-byte transaction, the last 32 bytes are intentionally manipulated to collide with the hash of an invalid transaction, F.

If this happens, a node could deceive an SPV client into believing that a non-existent transaction, F, exists in the block by offering a path leading to T, then considering T as a node within the tree structure.

This weakness of Bitcoin’s SPV clients is further discussed in section 3.2 at this linked article. The article also discusses other weaknesses of Bitcoin’s Merkle Root construction, which is a valuable read for any Blockchain/DLT bug hunters. Note that work must still be done to mine for a valid transaction T which collides with the invalid transaction by finding the correct combination of unconstrained values.

The Threshold Network was utilizing the ValidateSPV library, where the prove function first validated the transaction’s inclusion by checking its presence in the proof on line 37. Subsequently, it called the verifyHash256Merkle function, which iteratively computed the Merkle path using the provided proof hashes. It then compared the computed root hash with the expected root hash to ascertain the proof’s validity. However, this logic was vulnerable to explained malleability, where arbitrary transaction inclusion wasn’t effectively detected.

While the Threshold team was already aware of the issue before the report, their initial mitigation strategy did not fully resolve the issue.

The primary concern lies in the inclusion of 64-byte transactions. However, within the tBTC system, transactions deemed valid are consistently longer than 64 bytes. Additionally starting in Bitcoin Core 0.16.1, 64-byte transactions will no longer be accepted to the mempool. This invalidates the attack, since we cannot convince the system the leaf node, or the real transaction, is an intermediary node in the merkle tree since it cannot be split into equal 32 byte parts. Therefore, the vulnerability stemming from the Bitcoin Merkle Tree weakness cannot be exploited within the tBTC bridge contract.

However, there is still a way where an SPV proof can be forged through the use of a coinbase transaction.

The coinbase transaction is the first transaction in a block. It is a special type of transaction that creates new bitcoins and collects the transaction fees paid by users sending transactions. Miners include a coinbase transaction in the blocks they mine. The size of a coinbase transaction can vary but is generally limited to 100 bytes.

A malicious miner could produce a valid 64-byte coinbase transaction that would be accepted by the network. They would then need to prepare a fake transaction whose 32-byte ID fulfills the constraints of the second half of the coinbase transaction.

This inclusion of a valid 64-byte coinbase transaction contradicts the project’s assumptions and was highlighted in the report by the whitehat.

Vulnerability Fix:

Threshold team deployed the fix at this commit to also check for the coinbase transaction.

The fix had two aspects.

1. Length check of coinbase proof and merkle proof:

• As described above, in the Merkle tree, each level halves the number of hashes, forming parent nodes from pairs of hashes. And each transaction in a block is a leaf node. When proving a transaction’s inclusion, a series of hashes connects it to the root. The length of this proof matches the tree’s height, determined by the block’s transaction count.
• The length check ensures that the Merkle proof of the coinbase transaction (the first transaction in the block) has the same length as the proof of the transaction of interest. Since all transactions in a block are on the same level of the Merkle tree, their proofs should have the same length.
• So, by comparing the length on line 195, the code ensures that both transactions are on the same level of the Merkle tree and that no tampering has been done.

2. Validating the coinbase proof on line 222 ultimately ensures that the provided coinbase proof is valid.

function validateProof(
        BridgeState.Storage storage self,
        Info calldata txInfo,
        Proof calldata proof
    ) internal view returns (bytes32 txHash) {
        require(
            txInfo.inputVector.validateVin(),
            "Invalid input vector provided"
        );
        require(
            txInfo.outputVector.validateVout(),
            "Invalid output vector provided"
        );
        require(
            proof.merkleProof.length == proof.coinbaseProof.length,
            "Tx not on same level of merkle tree as coinbase"
        );

        txHash = abi
            .encodePacked(
                txInfo.version,
                txInfo.inputVector,
                txInfo.outputVector,
                txInfo.locktime
            )
            .hash256View();

        bytes32 root = proof.bitcoinHeaders.extractMerkleRootLE();

        require(
            txHash.prove(
                root,
                proof.merkleProof,
                proof.txIndexInBlock
            ),
            "Tx merkle proof is not valid for provided header and tx hash"
        );

        bytes32 coinbaseHash = sha256(abi.encodePacked(proof.coinbasePreimage));

        require(
            coinbaseHash.prove(
                root,
                proof.coinbaseProof,
                0
            ),
            "Coinbase merkle proof is not valid for provided header and hash"
        );

        evaluateProofDifficulty(self, proof.bitcoinHeaders);

        return txHash;
    }

Acknowledgments

We extend our gratitude to our elite whitehat, Kayaba, for their exceptional contribution in responsibly disclosing a vulnerability to the Threshold network. Special acknowledgments go to the Threshold network team for addressing the insufficiencies in mitigation, and effectively resolving the reported issue.

If you’re a developer or a whitehat considering a lucrative bug-hunting career in web3 — this message is for you. With 10–100x the rewards commonly found in web2, your efforts will pay off exponentially by switching to web3.

Check out the Web3 Security Library, and start earning rewards on Immunefi — the leading bug bounty platform for web3 with the world’s biggest payouts.