Homework problem on Blockchain and Merkle trees

Question

This is a question from a stanford course(http://cs251crypto.stanford.edu/18au-cs251/hw/hw1.pdf).

I think that Alice needs to send all the k blocks (containing the transactions) to Bob so that Bob can hash them one by one to ensure that next block is in chain. As the block Bob has, contains last transaction's hash, he can verify with that. But in that case, he can simply see the transaction, and merkle tree don't come into picture, so k data is not used and size of 1 block is also not provided in question. Am I missing something. Also, Alice can send the Merkle proof (the log(n) number of extra hashes along with hash of the transaction) to prove that the transaction is present in a block (comparing the net hash with Merkle root). But, the problem is that Bob contains only current block header, but the original transaction is in the chain n blocks back. Now if Alice provides only the header, bob can't know that they are not edited. Is there any other way, he can send some information which will ensure that Alice has not tampered with the info?

Answer 1

The question parameters restated:

• Bob only has latest header stored locally
• Alice's payment is k blocks before current head
• n tx's per block

Alice needs to prove two things:

• 1) Her payment is committed to header chain_height-k
• 2) Current header at chain_height builds on chain linked to header at chain_height-k

Merkle-Proof

You need to construct the payment TX merkle-proof (merkle path only) for the header block at height-k. This proves your transaction was confirmed in a block.

The merkle tree has a height of log2(256)=8. The size of this proof is (8*2+1)*32 Bytes.

Strong-Chain Proof

You also need to prove that miners performed POW on top of the block which contained your transaction. This can be proven by providing headers which are linked together, although the problem does not give you any figures on those header sizes.

You could assume Bitcoin headers of fixed size 80B, so (k+1)*80 Bytes.

Note that only the headers are required for this POW proof, because the light client cannot verify whether the TX's committed to these headers are valid or not.

This chain provides the proof that the strong-chain builds on the block which includes your transaction.