Implement Merkle Trees

[lancekrogers]

We need to implement merkle trees built from transaction hashes and add the merkle root to each block. This can be used to verify the transactions in a block. This is a fundamental concept of blockchain and is needed to build a trustworthy blockchain.

[jcopley]

Agreed, but is the merkle root strictly necessary if we hash the entire block? IIRC, correctly, what gets hashed in bitcoin's proof of work algorithm is the block header, not the entire block. In that case, a merkle root is essential to make sure the transaction data is verified.

Either way, this brings up another issue: our transactions have no Id, which is necessary in order to reference previous transactions.

[lancekrogers]

My understanding is that the hashing of the block header is used as a seed for the proof of work algorithm so that the same nonce cant be used to generate blocks every time. If this is the case we could hash the entire block of transactions and use that value instead of the merkle root but each client will have to store all the transaction hashes in memory in order to validate each transaction. I have a feeling that this may bog down the nodes so I think itd be best to use the merkle root since it was chosen in bitcoin to solve this problem.

And youre right, I will go ahead and create an issue to add transaction hash ids as well.

[itsromiljain]

This means we should be hashing only the Block header not the complete Block. In that case Block consists of two parts - Block header and rest of Block content. And Block header will have the merkle root of all the transactions in that block. I hope i got this conversation correct.