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?