Author: Jameson Lopp 2016-05-17 14:03:22
Published on: 2016-05-17T14:03:22+00:00
Bitcoin's long-term decentralisation is a serious concern due to the growth of Unspent Transaction Output (UTXO). Currently, the maximum size of the UTXO set is unbounded and the UTXO growth is driven by factors including lost coins, dust outputs that cannot be economically spent, and non-Bitcoin-value-transfer "blockchain" use-cases such as anti-replay oracles and timestamping. To combat UTXO growth, Merkle Tree committing to the state of all transaction outputs can provide mechanisms for compactly proving the current state of an output. The proposed Merkle Mountain Range (MMR) is a type of deterministic, indexable, insertion ordered merkle tree, which allows new items to be cheaply appended to the tree with minimal storage requirements.The article explores the technical details of the TXO MMR scheme for Bitcoin, which allows for efficient storage and retrieval of unspent transaction outputs (UTXOs). The TXO MMR is a perfect binary tree structure that enables the reuse of data from previous states in subsequent states. When a state is committed to the blockchain, only the minimal amount of data required to append new UTXOs is retained, resulting in significant storage savings. Pruning behavior is consensus-critical, as missing data due to premature pruning can cause a full node to fall out of consensus, while failing to include a merkle proof required by the consensus creates an invalid block. However, many full nodes retain more data than strictly necessary for consensus, enabling them to help wallets make transactions spending old coins.The article discusses the implementation of TXO (Transaction Output) commitments in Bitcoin and its impact on the security model. TXO commitments raise issues with Bitcoin's security model by allowing miners to profitably mine transactions without validating prior history. Therefore, it is essential to determine how old is "sufficiently old" to validate the chain. A longer-than-technically-necessary TXO commitment delay may help ensure that full node software actually validates some minimum number of blocks out-of-the-box. This can be achieved in a variety of ways such as fraud proofs or even a PoW with an inner loop dependent on blockchain data.The proposed high-performance/low-latency delayed commitment full-node implementation needs to store four things: the UTXO set, STXO set, TXO journal, and TXO MMR list. Each block B_i commits to the TXO set state as of block B_{i-n}. In a low-priority background task, the TXO journal is flushed, recording the outputs spent by each block in the TXO MMR, and hashing MMR data to obtain the TXO commitment digest. Since everything is committed via cryptographic hash, it is guaranteed that regardless of where we get the data, after unpruning we'll have the right data.The article also details the storage overheads associated with the TXO commitments scheme, highlighting the log2(n) merkle path overhead as the only significant storage overhead when compared to the status quo. The first challenge of handling transactions spending archived txouts is obtaining up-to-date TXO commitment proofs which can be handled by specialized archival nodes. However, updating those proofs as blocks are mined is a challenge for relay nodes as well as miners. On the other hand, full proofs need to be stored for archived txout spends which are limited by the blocksize limit but expected to be relatively uncommon.The article suggests further work such as optimizing the TXO commitment scheme to be used directly without a commitment delay, using a metric other than age, and fixing the problem to encourage/legitimize blockchain use-cases other than BTC value transfer. Additionally, it suggests using a different miner fairness/decentralization metric/incentive instead of counting TXO commitment proofs towards the blocksize limit. Finally, it discusses the interaction of fraud proofs with TXO commitments and references Peter Todd's work on Merkle Mountain Ranges, Do we really need a mempool?, and Segregated witnesses and validationless mining.
Updated on: 2023-06-11T05:25:58.587176+00:00