Quote from: [mike] on February 13, 2011, 10:51:07 AM

I think he meant a merkle tree on top of the blocks, ....

Satoshi may have made a small oversight in suggesting this could be done without changing the protocol. He suggested we add BitDNS (or BitWhatever) as the root/branch/leaf/something of the merkle tree. However this will not work because the current BitCoin protocol requires clients to verify that every leaf of the bitcoin chain is a valid bitcoin transaction. A hash value is not a valid bitcoin transaction, so this move would break legacy clients confused by the merkle makeup of the newer blocks.

In any event, I have a good understanding of a handful of ways to do the multiple chains.

The question you are asking about is not related to the BitDNS discussion. To erase spent transactions would not require any type of change in structure of the merkle tree. Each client can get away with forgetting most merkle leaf transaction data. Here is what it has to remember:

- The hash of all blocks
- All prior transactions that contributed to the availability of your own wallet funds
- The block header data for all blocks to which those transactions belong
- The merkle tree non-leaf hashes for those blocks
- All merkle leaf transactions that are siblings to the above transactions in the merkle tree of the block to which they belong.

Now, we must assume all clients are forgetting things by this same algorithm, so when a client spends money he has to spell out all the supporting transaction data over the network to convince other nodes and the recipient that it's legitimate.

Over time as coins become more circulated the supporting data that needs to be sent to the network for every new transaction will become large. So this should be weighed against the status quo where all clients store all data. Other solutions have been made up for tackling the data storage problem separately from bitcoin.