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?

Improve this question

1 Answer 1

Reset to default
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.
Improve this answer
5
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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