<p>The question parameters restated:</p>

<ul>
<li>Bob only has latest header stored locally</li>
<li>Alice's payment is <code>k</code> blocks before current head</li>
<li><code>n</code> tx's per block</li>
</ul>

<p>Alice needs to prove two things:</p>

<ul>
<li>1) Her payment is committed to header <code>chain_height-k</code></li>
<li>2) Current header at <code>chain_height</code> builds on chain linked to header at <code>chain_height-k</code></li>
</ul>

<p><strong>Merkle-Proof</strong></p>

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

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

<p><strong>Strong-Chain Proof</strong></p>

<p>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. </p>

<blockquote>
  <p>You could assume Bitcoin headers of fixed size 80B, so <code>(k+1)*80 Bytes</code>.</p>
</blockquote>

<p>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.</p>

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

CC BY-SA 4.0
2019-02-12T14:31:48.600Z
But if only header of block is provided, how can Bob confirm that header are not modified, as there is no whole block, so he cannot find its hash to match it against the hash provided in next block.
BEWARB
CC BY-SA 4.0
2019-02-13T09:08:55.763Z
Also I think height of merkel tree will be log_2(256)=8, and why is the factor of 2 taken?
BEWARB
CC BY-SA 4.0
2019-02-13T09:28:39.117Z
Only the header at height n is committed to the next highest block (n+1). The transactions of that block are already committed to n, through the marke root.
James C.
CC BY-SA 4.0
2019-02-13T09:33:19.053Z
Apologies, sloppy math on my part, you are correct it is log_2(256). I have amended the answer.
James C.
CC BY-SA 4.0
2019-02-12T11:26:11.587Z
2019-02-13T09:34:51.493Z
2019-02-13T09:34:51.493Z
James C.
<p><a href="https://i.sstatic.net/RK7UL.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/RK7UL.png" alt="enter image description here"></a></p>

<p>This is a question from a stanford course(<a href="http://cs251crypto.stanford.edu/18au-cs251/hw/hw1.pdf" rel="nofollow noreferrer">http://cs251crypto.stanford.edu/18au-cs251/hw/hw1.pdf</a>).  </p>

<p>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?</p>

<blockchain>
Homework problem on Blockchain and Merkle trees
BEWARB
# Homework problem on Blockchain and Merkle trees

(Asked by: username_0 on 2019-02-12)

[![enter image description here](https://i.sstatic.net/RK7UL.png)](https://i.sstatic.net/RK7UL.png)

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?

**Tags:** blockchain


---

## 1 answers

### Answer by username_1 on 2019-02-12. Score: 0 | Accepted answer

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.

> **Comments:**
> **username_0**: But if only header of block is provided, how can Bob confirm that header are not modified, as there is no whole block, so he cannot find its hash to match it against the hash provided in next block.  
> **username_0**: Also I think height of merkel tree will be log_2(256)=8, and why is the factor of 2 taken?  
> **username_1**: Only the header at height n is committed to the next highest block (n+1). The transactions of that block are already committed to n, through the marke root.  
> **username_1**: Apologies, sloppy math on my part, you are correct it is log_2(256). I have amended the answer.  

---

