On 13 Sep 2012, at 16:51, Gregory Maxwell <gmaxw...@gmail.com> wrote:
> I thoroughly understand the value of tree hashes. That wasn't what I
> was asking about.
>
> If you're validating a block you need all the transactions, once you
> have them or their hashes you can build the tree without transferring
> more, e.g. what a fully validating node needs. If you're checking a
> single transaction to need the path from the transaction to the root
> (what a SPV nodes need, for example).
>
> Can you spell out the 'end user'ish application for fetching a tree level?
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):
Level 0: *
/ \
/ \
/ \
/ \
/ \
/ \
/ \
Level 1: * *
/ \ / \
/ \ / \
/ \ / \
Level 2: * * * *
/ \ / \ / \ / \
Level 3: * * * * * * * *
When you look at any non-leaf node you can see a separate merkle tree where the
root can be found exactly the same as any other merkle tree. In 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 validate that
the root exists for any level. So you first check that the level 2 hashes do
indeed calculate 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 segment root was validated for the entire tree's root.
You validate 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 the entire
tree. This way you have downloaded 4 hashes instead of 8.
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 which case you ask for level 1 and download 2 hashes.
I hope that made sense.
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.------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development
