Is Merkle tree pruning described in the whitepaper feasible/useful? If not, would there be any alternative?

Question

When I was reading bitcoin-paper-errata-and-details.md written by David A. Harding, I realized that there's probably a common misunderstanding or over-simplification about Merkle tree pruning. What Nick ODell had said might be a live example:

• A leaf (transaction) can be pruned when all of its outputs have been spent.

This once seemed to be true for me, until I read what David had written:

there is currently no way in Bitcoin to prove that a transaction has not been spent

I'm not sure whether I have grasped it, so firstly I made a diagram to illustrate (part of) my understanding to this problem:

Still, I don't think merely this problem can kill the whole idea of Merkle tree pruning yet, I think it just means that "the reclaimable disk capacity is much lower than expectation". In other words, if I'm not mistaken, Nick ODell's claim could be "corrected" like:

• A leaf (transaction) can be pruned when all of its outputs have been spent, and all of its previous transactions have been pruned.

However, I then think that, even if the "corrected" claim is taken into consideration, the idea of Merkle tree pruning still doesn't seem to be feasible/useful:

1. Even if the problem mentioned above can be avoided by honest nodes, a malicious node can still deceive the new full node by hiding/picking some merkle branches. A malicious node can lie about the actual ownership of coins (spent/unspent state) without breaking the Merkle tree structure at all. In other words, a new full node joining the network still needs to download & verify everything, otherwise, it could be deceived by a malicious node.

2. If a full node needs to enable pruning to reduce disk space requirement for itself, directly reading/modifying the blockchain files seems to be much less efficient than the current implementation that the UTXO set is completely separated from the blockchain storage, so that a full node (no matter it's pruning or not) only needs to query and update the UTXO set database during the downloading & validation process. The blockchain itself doesn't need to be touched once again for validation purposes at all, which is the reason why the old blocks can be simply deleted when "pruning" (not Merkle tree pruning) is enabled.

However, I'm still not sure about this conclusion. Is this related to the idea of fraud proofs, in the sense that as long as there's still at least one honest full node, the new node would be able to spot which piece of data is the correct one? What if the UTXO set is also committed to the blockchain? What if some more commitments like the block height of previous transaction are also added to the blockchain?

Furthermore, I've heard that the Mimblewimble protocol enables secure blockchain pruning. I'm also curious how Mimblewimble could achieve this, and whether similar goal could be eventually achieved in Bitcoin?

Answer 1

You are right, completely discarding transactions whose outputs have been spent would not work. New full nodes would still need all data to be able to process the blockchain and build the current UTXO set. So, the Merkle tree pruning idea doesn't seem beneficial and maintaining the UTXO set separately in combination with pruning old blocks is more efficient.

Fraud Proofs are another thing that never has been implemented. They were meant as a way for full nodes to tell SPV clients when a blockchain tip is invalid. They are related in so far, that they suffer from the same issue: there is no good way how to prove the non-existence of a UTXO, yet. If someone just doublespent a UTXO it would be easy to point out where the UTXO was spent already, but if a block contains a transaction spending a UTXO that never was created, it's non-trivial to prove that—a full node can just tell because they calculated the complete UTXO set themselves, which in turn is hard to prove as well. It would get much easier, if we did commit to the UTXO set somewhere, but even then, the smallest proof might consist of a proof of absence in the last UTXO set commitment (which with a canonical ordered UTXO set could be as simple as the two neighboring UTXOs between which the UTXO should have appeared), and all the blocks since that commitment. Fraud proofs might be possible if we committed to the UTXO set in every block.

Furthermore, I've heard that the Mimblewimble protocol enables secure blockchain pruning. I'm also curious how Mimblewimble could achieve this, and whether similar goal could be eventually achieved in Bitcoin?

Mimblewimble transactions can be non-interactively aggregated. Any outputs that were spent by subsequent inputs cancel out at that point (which is referred to as transaction cut-through). The only data that cannot be pruned are the kernels which are a combination of signature and proof that no new funds were created. In effect, the whole Mimblewimble blockchain is a single large coinjoin transaction unless you observed/recorded the original transaction before it was aggregated. The approach cannot be ported to Bitcoin without vast redesign of the transaction format and consensus rules. In this context, it may be interesting to glance at Litecoin's Mimblewimble extension block protocol update.

Answer 2

From what I understand, a full node will download everything, verify everything first. Then only the pruning starts. Thus, the issue of inconsistent pruning does not arise. As off now, there is no common consensus on the UTXO sets. For example, up to block 500,000, the UTXO set is "XXXX". Just download "XXXX",it should be fine. I believe we will have this feature in the future. As off now, fullnode have to download everything, verify and then only prune.