As I pointed out in my last post on the topic, light clients have some serious issues right now. Reduced security compared to full nodes is just the beginning. Currently available light clients also have poor financial privacy guarantees, rely on trusted sources for fee estimation, and will follow invalid, high-work chains in the case of a 51% or eclipse attack.
In many cases, light clients are missing important data that is available to full nodes. They could be improved significantly if they were able to download compact summaries of the block contents. Consider if clients could simply see the fee rate of the cheapest transaction in each block. With that one data point, they could make far better fee estimates. So how can we enable clients to get these block summaries without trusting the source of information? A powerful and often discussed technique is committing to them in the block header. In fact, this very type of commitment was proposed by Charlie Lee as a change to Litecoin.
Imagine we could change the Bitcoin protocol and add new fields to the block header, such as the minimum transaction fee rate. Clients already download all block headers, which are authenticated with proofs of work, so they would have access to the new fields as reported by the miners. The fields could contain cryptographic commitments to the block content summaries, and a new consensus rule could enforce that the commitments are computed correctly. In the case of the minimum fee rate commitment, this means all nodes would verify that the header field is actually equal to the minimum fee rate of all transactions in the block, to keep the miner honest.
Where to commit?
Soft-forking commitments
There’s a problem though: adding header fields is a hard-forking change and is incompatible with mining hardware. Instead, we would like a way to add these commitments to the block bodies in a backwards-compatible way that can still be authenticated by clients with minimal overhead. The coinbase transaction is a good candidate because it is crafted by the miner and can be authenticated against the block header with a Merkle branch. Commitments can either go in OP_RETURN outputs on the transaction or the special witness reserved value. These fields can be overwritten by miners freely, meaning a soft-fork could restrict them to deterministically computed values.
Putting commitments in the coinbase transaction, however, means that in addition to the headers, the client would need to download the coinbase transaction and Merkle branch. That is an extra ~0.5 KiB per block, just to get the 32-byte commitments. One alternative proposed by Tier Nolan is to put the commitments in OP_RETURN outputs on a new, special transaction at the end of the block. This reduces the data overhead in part because the transaction can be made smaller, but primarily because the Merkle branch for the last transaction in a block is shorter than for the first. For certain block configurations, the branch could be just one hash. On the other hand, creating a special case transaction comes with a lot of complexity that may very well outweigh the bandwidth benefits.
Hard-forking commitments
An even more compact solution is possible with a hard fork. This design extends the block structure itself with a vector of commitments and repurposes the Merkle field in the block header. The field currently contains the root of the transaction Merkle tree, but with a protocol change, it could be the root of a Merkle tree over the commitment vector. The transaction root would then move to the first entry in the commitment vector. If the size of the commitment vector is left flexible, future additions could be soft-forked in later.
What to commit?
Block filters
One idea I am very excited about is committing a compact filter of transaction data in each block. This enables an alternative light client mode to BIP 37 and Electrum style SPV with significantly better privacy properties. The basic idea is that instead of clients telling nodes which addresses they are watching for, as they do today, nodes send clients summaries of which addresses send or receive funds in each block and let them decide whether to download the full block or not. Since block data can be fetched from multiple sources and checked against the already-known headers, no single peer gets a clear picture of which transactions the client is interested in.
The summaries take the form of probabilistic filters that match included objects with probability 1 and reports false positives with low probability. One possible construction is a Bloom filter, though a more efficient one is specified in BIP 158 based on compression techniques. A light client protocol using committed filters has advantages over SPV other than just the privacy gains. They also have increased protection against malicious peers and impose less of a resource burden on full nodes. For a more detailed comparison, see the previous post on Bitcoin client modes.
Fee commitments
The best strategy light clients have currently for pricing a transaction is to send with a low fee and bump it periodically using Replace-by-Fee until the transaction confirms. One can think of this process as bidding for block space and increasing the bid with each passing block until it becomes competitive. You can see how the Litecoin proposal that I mentioned above would help determine a reasonable starting bid.
Committing the lowest fee rate in each block is a nice start, but wallets may want to use a more sophisticated starting rate. Sia lead developer David Vorick has, for example, written that the median 90th percentile fee rate of the past 11 blocks is a better heuristic. Fortunately, Charlie’s proposal for Litecoin could be easily extended to compactly provide the entire distribution of fees in a block to varying degrees of precision.
The solution is, surprise!, a Merkle tree. First, we’ll take all of the transactions in a block (excluding the coinbase) and sort them by the fee rate. We define each leaf of the tree as a tuple containing the transaction’s fee, weight, and hash. Each intermediate node in the tree is also a tuple, containing the sum of the two child fees, the sum of the child weights, and the hash of the two child nodes concatenated. The block commitment is then the hash of the root node. This type of commitment would allow a client to request and verify a proof of the blocks fee rate at any percentile of weight. A full node could simply identify the transaction at that percentile and provide a branch linking it to the block commitment. A proof could even be created for multiple percentiles at once.
TXO commitments
Another issue light clients have is that they are unable to easily determine if a transaction output is unspent in the current state of the chain. This prevents them from fully validating individual transactions in the mempool, and has consequences for more sophisticated applications. In the Lightning protocol, for example, channels are identified by their funding output, and the channel is closed once that output is spent. Lightning Network nodes would benefit from a way to determine if a channel is still open without a trusted connection to a full node and without rescanning the chain.
Block commitments present a possible solution to this problem as well. There have been many ideas over the years on ways to commit to the UTXO set in each block in a way that allows compact proofs of inclusion and exclusion. A naive solution is to rebuild a Merkle tree with each block over all entries in the UTXO set. The issue here is that, given the size of the UTXO set, constructing the Merkle tree would be far too slow. Some of the more viable proposals include Peter Todd’s Merkle Mountain Range based commitments and Bram Cohen’s TXO bitfields, which I will not even try to summarize here.
Conclusion
Block commitments are a very powerful tool for enhancing the utility of light clients under the SPV security model. However, they come at a considerable cost since each commitment requires a consensus change. Deploying soft forks requires substantial time and effort, and if the design of the commitment is flawed or sub-optimal, the change is very difficult to revert. Furthermore, computing the committed value increases the time to validate and, more importantly, assemble new blocks.
My next post discusses an alternative type of commitment that strikes a different tradeoff between agility and security.
