<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><font face="Courier New"><br></font><div><div><font face="Courier New">On 13 Sep 2012, at 16:51, Gregory Maxwell &lt;<a href="mailto:gmaxwell@gmail.com">gmaxwell@gmail.com</a>&gt; wrote:</font></div><font face="Courier New"><br></font><blockquote type="cite"><font face="Courier New">I thoroughly understand the value of tree hashes. That wasn't what I<br>was asking about.<br><br>If you're validating a block you need all the transactions, once you<br>have them or their hashes you can build the tree without transferring<br>more, e.g. what a fully validating node needs. If you're checking a<br>single transaction to need the path from the transaction to the root<br>(what a SPV nodes need, for example).<br><br>Can you spell out the 'end user'ish application for fetching a tree level?<br></font></blockquote></div><font face="Courier New"><br></font><div><font face="Courier New">A merkle tree root is found by hashing the two children together and those children are found the same way until you get to the greatest level down the tree. This means you can validate children as being correct as long as they hash together to form the root. This means you do not need all the transaction hashes to validate segments of the block, you only need the root hashes for all the segments you want. Let's say there are 8 transactions and you want to verify 4 segments (2 transactions each), The merkle tree looks like this (Might not work depending on the font):</font></div><div><font face="Courier New"><br></font></div><div><font face="Courier New">Level 0: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; *</font></div><div><font face="Courier New">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; / \</font></div><div><font face="Courier New">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;/ &nbsp; \</font></div><div><font face="Courier New">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; / &nbsp; &nbsp; \</font></div><div><font face="Courier New">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;/ &nbsp; &nbsp; &nbsp; \</font></div><div><font face="Courier New">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; / &nbsp; &nbsp; &nbsp; &nbsp; \</font></div><div><font face="Courier New">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;/ &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; \</font></div><div><font face="Courier New">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; / &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; \</font></div><div><font face="Courier New">Level 1: &nbsp; &nbsp; &nbsp; * &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; *</font></div><div><font face="Courier New">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; / \ &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; / \</font></div><div><font face="Courier New">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;/ &nbsp; \ &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; / &nbsp; \</font></div><div><font face="Courier New">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; / &nbsp; &nbsp; \ &nbsp; &nbsp; &nbsp; &nbsp; / &nbsp; &nbsp; \</font></div><div><font face="Courier New">Level 2: &nbsp; * &nbsp; &nbsp; &nbsp; * &nbsp; &nbsp; &nbsp; * &nbsp; &nbsp; &nbsp; *</font></div><div><font face="Courier New">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; / \ &nbsp; &nbsp;</font><span style="font-family: 'Courier New'; ">&nbsp;/ \ &nbsp; &nbsp;</span><span style="font-family: 'Courier New'; ">&nbsp;/ \ &nbsp; &nbsp;</span><span style="font-family: 'Courier New'; ">&nbsp;/ \</span></div><div><font face="Courier New">Level 3: * &nbsp; * &nbsp;&nbsp;</font><span style="font-family: 'Courier New'; ">* &nbsp; * &nbsp;&nbsp;</span><font face="Courier New">* &nbsp; * &nbsp;&nbsp;</font><span style="font-family: 'Courier New'; ">* &nbsp; *</span></div><div><font face="Courier New"><br></font></div><div><font face="Courier New">When you look at any non-leaf node you can see a&nbsp;separate&nbsp;merkle tree where the root can be found exactly the same as any other merkle tree. In&nbsp;this example you want four segments, so you ask for level 2. Now imagine a tree without level 3, you can validate the root with level 2. In fact you can&nbsp;validate that&nbsp;the root exists for any level. So you first check that the level 2 hashes do indeed&nbsp;calculate&nbsp;to the root. Once this is done you can now use these hashes to validate the segments. When you receive a segment, you check that segment against the segment's root. So you've validated the segment transactions for the segment root and the&nbsp;segment&nbsp;root was validated for the entire tree's root. You&nbsp;validate&nbsp;the segments for each segment root and this way you know all the transactions are valid for the four segments and thus are valid for&nbsp;the entire tree. This way you have downloaded 4 hashes instead of 8.&nbsp;</font></div><div><font face="Courier New"><br></font></div><div><font face="Courier New">Downloading the transactions hashes are therefore not necessary only the level for the segment roots. You might for instance want to divide the block into two segments in&nbsp;which case you ask&nbsp;for level 1 and download 2 hashes.</font></div><div><font face="Courier New"><br></font></div><div><font face="Courier New">I hope that made sense.</font></div><div><font face="Courier New"><br></font></div><div><font face="Courier New">And yes the merkle tree is particularly useful for validating a single transaction exists in a block as that saves a large proportion of the data required. The redundant data removed in the proposal here is smaller as a proportion of the total data (Because most of the data is the actual transactions themselves), so you might argue it's not worth it but it's simple to implement.</font></div></body></html>