# While calculating merkle proof, where are the other hashes being stored?

Consider that I have a merkle root made up of transactions a,b,c,d,e,f,g,h.

The root is H( H(H(a)+H(b)) + H(H(b)+H(b)) ) + H( H(H(b)+H(b)) + H(H(b)+H(h)) ).

Now, I have to verify whether transaction C is part of this root (which it is).

I am supposed to get hash of c H(c), which I can using the one-way hash function.

But then, after that I must get hash of other values also: H(d), H(H(H(a)+(b))) and so on in order to verify that c is a part of the Merkle tree.... Where do these hash values come from? Are they stored somewhere? If not, how are they dynamically generated?

And if all hashes are stored, how do I know that my hash H(C) has to be paired with H(D) and not H(A). Similarly for other levels also. Doesn't storing all hashes defeat the purpose of optimizing space?

• It might be better to use lower-case letters to symbolize transactions, since you are using H() to indicate the hash function. – dbkeys Aug 1 '18 at 1:05

These are not stored anywhere, and are calculated by the node.

The order in which transactions are included in the tree is the same as the order in which they appear in the block, which answers your last questions. To calculate a tree, one simply traverses the block's tx list, including them in pairs of two (and duplicating the last one if needed) to build all of the leaf nodes.

When asked if a block contains a particular transactions, nodes will check that block's transaction list. If the transaction exists, they will calculate the hashes you mentioned above to produce a merkle path, which contains the minimum nodes required to verify the transaction against the merkle root.

Since SPV wallets are aware of the block headers, they can verify the merkle root of the merkle path matches the one in the block header.

The root is H( H(H(A)+H(B)) + H(H(C)+H(D)) ) + H( H(H(E)+H(F)) + H(H(G)+H(H)) ).

You forgot one more level of hashing, it should be:

`root = H( H( H(H(A)+H(B)) + H(H(C)+H(D)) ) + H( H(H(E)+H(F)) + H(H(G)+H(H)) ) )`

Where do these hash values come from? Are they stored somewhere? If not, how are they dynamically generated?

The blockchain is referenced to find the raw transactions, and those transactions are hashed to verify the validity of the block. This happens on the level of individual nodes, every time the node hears about a new block. The merkle root in the blockcheader must be correct, and it is a cryptographic proof of the transaction content of the block. The merkle tree is computed by each node, but it doesn't need to be explicitly stored.

The merkle root provides a convenient and trustless way for light wallets to verify the authenticity of a transaction. Light wallets store all the headers, so they can just request that a node sends one branch of the merkle tree to them (for the relevant transaction). They can verify the hashes from the transaction to the root, and thus know the transaction is indeed included in the blockchain.

Including the merkle root also has other benefits, check out this question for good info.

Doesn't storing all hashes defeat the purpose of optimizing space?

The benefits gained from storing the merkle root far outweigh the reduction in blockspace usable for transactions (32 bytes for the merkle root).