Merkle tree

[Gdns8476]

Hi, here are my questions:
1. Does Bitcoin use Merkle tree for data verification?
2. If answer to #1 is "yes" - if Bitcoin keeps Merkle tree in-memory?
3. If answer to #1 is "no", than what for Merkle tree is used for? 

[aliashraf]

Hi, here are my questions:
1. Does Bitcoin use Merkle tree for data verification?
2. If answer to #1 is "yes" - if Bitcoin keeps Merkle tree in-memory?
3. If answer to #1 is "no", than what for Merkle tree is used for?  

1: Yes.
2: No.
3: Most importantly, in Bitcoin client, it is used for checking the integrity of the block in the sense that whether the header's Merkle Root field is correctly pointing to the block body. Also, SPV wallets extensively use Merkle Path for verifying membership of a specific transaction in a block without having an obligation to download/access to the whole block body, just the necessary hashes for building the path from the specified leaf to the root.

[Gdns8476]

Thanks aliashraf, can you elaborate a little about #3 please. In which case Bitcoin client (I assume wallet) have to deal with the block? Is it a special api something like audit?
And how is it possible to work with tree which is not in-memory?

[pooya87]

Thanks aliashraf, can you elaborate a little about #3 please. In which case Bitcoin client (I assume wallet) have to deal with the block? Is it a special api something like audit?
And how is it possible to work with tree which is not in-memory?

Bitcoin full nodes have to download and verify every block to make sure it is valid.
When a miner mines a block, they don't hash the whole structure. Instead they build a merkle tree and compute its root hash and include that hash in another smaller fixed size structure called "block header" and hash that.
When a node verifies a block they too have to create that merkle tree and only compute its root hash (discarding the tree as they go since it is not needed for anything else). This ensures that the transactions included in that block can not change (can't: add new tx, remove tx, change position,...).

[NotATether]

Thanks aliashraf, can you elaborate a little about #3 please. In which case Bitcoin client (I assume wallet) have to deal with the block? Is it a special api something like audit?
And how is it possible to work with tree which is not in-memory?

The merkle tree is computed dynamically by full nodes connected to SPV servers and is not cached. The tree is made* when the block itself is fetched.


*Only the leaves of the merkle tree, which are the transactions, are passed as input, and then it computes the hashes of each adjacent pair of transactions, and then the hashes of each adjacent pair of those hashes, until only one hash is left, which is called the root hash.

At any point, there is only one layer of the merkle tree stored in memory, whether it be the set of transactions in a block, an intermediate row of hashes that is made inside ComputeMerkleRoot() or just the root hash itself.

[ymgve2]

Note that if there are segwit transactions in a block, then there is a second Merke tree which covers the witness data. Check out BIP0141 for info.