3

In Merkle tree, leaves are actual transactions and internal nodes are hash of their childrens. In the Bitcoin paper, Satoshi talks about pruning branches in the Merkle tree to save storage space.

Under what conditions can be the branches pruned? I understand that the Merkle root is used in finding POF for the block. Are there any situations where all nodes in the Merkle tree are pruned except the root?

6

Sure:

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

However, Bitcoin Core doesn't implement this kind of pruning. It was built on the assumption that you download and validate all blocks. Because of this, it operates in one of two modes:

  • No pruning (the default)
  • Don't keep old blocks or old merkle trees at all, and only track unspent outputs and their scriptPubKeys. This mode doesn't allow you to help new nodes synchronize.
  • who does this pruning? Is there any data structure which tracks whether particular output has been spent or not? Or do we have to traverse entire block chain to identify the unspent output? – Curious Feb 18 '15 at 4:06
  • @Curious Nobody, to my knowledge. But, hypothetically, if it were done, it would be done by individual nodes. – Nick ODell Feb 18 '15 at 4:06
  • Is there any data structure which tracks whether particular output has been spent or not? Or do we have to traverse entire block chain to identify the unspent output? – Curious Feb 18 '15 at 6:38
  • @Curious Yes. Originally it tracked only the block a particular transaction was in, but it now tracks each output individually, so that the full block data doesn't need to be consulted. However, this is getting out of the scope of your question; you should ask a new question if you want to know more about this. – Nick ODell Feb 18 '15 at 6:42
  • Bitcoin core doesn't implement this yet. Pruning is likely to be implemented in 0.11 (the next version). – Jannes Feb 18 '15 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.