Access Blockchain Data from Bitcoin Smart Contracts: Part 4
The total number of transactions in a block is an important piece of information. We show how to obtain it without a trusted third party, which is considered impossible previously.
Range
Let us denote the length of a Merkle path as n. The number of leaves, i.e., number of transactions in a block, is between 2^(n-1) + 1 and 2^n. To see this, a perfect binary tree¹ of height n has exactly 2^n leaves. The length of a Merkle path is the same as the height of the Merkle tree.
Exact Number
Find the Last Transaction
In the last post, we accessed the first coinbase transaction in a block. If we could also access the last transaction, we can deduce the total number of transactions. We can identify the first/leftmost transaction by verifying all the nodes on its Merkle path are on the right branch. It is tempting to find the last/rightmost transaction similarly by requiring all Merkle path nodes to be on the left branch. Unfortunately, this may not be always true.
If we have a perfect Merkle tree, all nodes on the Merkle path of the last transaction are indeed on the left branch, as shown below.
However, this is not the case when the tree is not perfect. For instance, the following tree has 5 leaves and the Merkle path for the last transaction consists of all nodes colored orange. Two of them lie on the right branch, only the top one on the left.
To overcome this issue, we notice that when there is an odd number of nodes in any single layer of the Merkle tree, the last node is duplicated. That implies, if any node on the Merkle path of the last transaction is on the right branch, it must be copied from the current left branch, as the graph below shows.
The following code implements the algorithm directly.
From Merkle Path to Transaction Index
To derive a transaction’s index, we follow its Merkle path from root to the leaf representing it. When a node on the path is on the left branch, we go right (i.e., binary 1); otherwise, we go left (binary 0). It is easy to see that we can get a binary representation of its index this way. In the example below, we apply this rule to the last transaction, and we go all the way to the right and get 111 in binary, which is exactly its index 7 in decimal.
This code is shown below:
Get the Exact Transaction Count
Finally we can combine the two functions into blockTxCount(), which returns the exact number of transactions in a block.
Summary
Once we can access the number of transactions in a block, we can use it to build smart contracts deemed impossible before. We list only a few examples below:
- Place a bounty contract that only pays out when a block contains over 1 million transactions, to sponsor a stress test.
- Combining with timing information obtained before, either timestamp in a block header or block height, transactions per second (TPS) can be calculated faithfully and used inside a contract. For example, a contract that only unlocks if TPS reaches 100,000.
We look forward to seeing what kinds of exciting new contracts you can come up with.
Acknowledgements
This article is inspired by shilch’s work.
[1] A perfect binary tree is a tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level.
