From: Matthew Mitchell <matthewmitchell@godofgod•co.uk>
To: Gregory Maxwell <gmaxwell@gmail•com>,
"bitcoin-development@lists•sourceforge.net"
<bitcoin-development@lists•sourceforge.net>
Subject: Re: [Bitcoin-development] Segmented Block Relaying BIP draft.
Date: Thu, 13 Sep 2012 18:49:49 +0100 [thread overview]
Message-ID: <A1DC7DE8-F355-4B61-AF18-94F07DF6421E@godofgod.co.uk> (raw)
In-Reply-To: <CAAS2fgQi8QFwU2M=wLiDodt3SmO48vUV5Sp3YCb1OmGJ5m=E7Q@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 3213 bytes --]
On 13 Sep 2012, at 16:51, Gregory Maxwell <gmaxwell@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.
[-- Attachment #2: Type: text/html, Size: 5996 bytes --]
next prev parent reply other threads:[~2012-09-13 17:50 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-09-11 19:07 Matthew Mitchell
2012-09-11 19:42 ` Gregory Maxwell
2012-09-11 21:48 ` Matthew Mitchell
2012-09-11 23:22 ` Gregory Maxwell
2012-09-13 8:42 ` Mike Hearn
2012-09-13 14:05 ` Matthew Mitchell
2012-09-13 15:16 ` Gregory Maxwell
[not found] ` <2B95CF41-4304-4D2A-9ABF-198D97B7449B@godofgod.co.uk>
2012-09-13 15:46 ` Matthew Mitchell
[not found] ` <CAAS2fgQi8QFwU2M=wLiDodt3SmO48vUV5Sp3YCb1OmGJ5m=E7Q@mail.gmail.com>
2012-09-13 17:49 ` Matthew Mitchell [this message]
2012-09-13 18:59 ` Pieter Wuille
2012-09-13 20:24 ` Matthew Mitchell
-- strict thread matches above, loose matches on Subject: below --
2012-09-10 15:07 Matthew Mitchell
2012-09-10 15:14 ` Gregory Maxwell
2012-09-10 16:29 ` Matt Corallo
2012-09-10 18:59 ` Luke-Jr
2012-09-10 19:34 ` Matthew Mitchell
2012-09-10 19:53 ` Matt Corallo
2012-09-10 20:00 ` Gregory Maxwell
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=A1DC7DE8-F355-4B61-AF18-94F07DF6421E@godofgod.co.uk \
--to=matthewmitchell@godofgod$(echo .)co.uk \
--cc=bitcoin-development@lists$(echo .)sourceforge.net \
--cc=gmaxwell@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox