From: Pieter Wuille <pieter.wuille@gmail•com>
To: Matthew Mitchell <matthewmitchell@godofgod•co.uk>
Cc: "bitcoin-development@lists•sourceforge.net"
<bitcoin-development@lists•sourceforge.net>
Subject: Re: [Bitcoin-development] Segmented Block Relaying BIP draft.
Date: Thu, 13 Sep 2012 20:59:02 +0200 [thread overview]
Message-ID: <20120913185900.GA393@vps7135.xlshosting.net> (raw)
In-Reply-To: <A1DC7DE8-F355-4B61-AF18-94F07DF6421E@godofgod.co.uk>
On Thu, Sep 13, 2012 at 06:49:49PM +0100, Matthew Mitchell wrote:
> 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):
> I hope that made sense.
I'm quite sure Gregory thoroughly understands how Merkle trees work and why they are useful.
His question was about the use case. Let me try to answer his question, by making some assumptions about your intentions. Correct me if I'm wrong - I haven't read all details.
You want to parallellize block downloads, while at the same time preventing re-download of transactions that are already known.
To do so, a requesting node would first request (for example) the 8 level-3 hashes, then start 8 parallel threads to download the
transactions from presumably 8 different peers. Each thread then fetches the transaction id's that correspond to its own 1/8th of
the block, and requests the transactions whose txid is not yet known.
Comparing this with Gregory's own suggestion (just fetch the entire txid list at first, and then (again as parallellized as needed)
fetch the unknown transactions from several peers), this does indeed have an advantage: you need to download (relatively) far less
data before the threaded part can start. If this is what you propose, it is certainly meaningful, but the gains aren't very large,
in my opinion.
However, my impression while reading your proposal was at times that you intend to process the different layers of the
Merkle tree iteratively after starting the initial parallel segments. I don't think that is useful, as you'll need the actual
txids anyway before deciding whether they need to be downloaded at all, it adds several round-trips, and once you have downloaded
the intermediate merkle hashes for about 8 levels, you've already transferred more data than the transactions themselves. I think
Gregory also assumed something like this, making him question why it's useful. Anyway, this whole paragraph is one assumption, so
if it's not the case, ignore me.
Can you clarify what you mean? Preferably by giving a concrete sequence of exchanged messages, with a given purpose?
PS: the reason Satoshi used a Merkle tree for the transactions in a block was to allow a short piece of data (the hashes along a
path in the tree) to prove a transaction belongs to it - I doubt he intended it for parallellizing downloads (though it certainly
opens some opportunities here).
--
Pieter
next prev parent reply other threads:[~2012-09-13 18:59 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
2012-09-13 18:59 ` Pieter Wuille [this message]
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=20120913185900.GA393@vps7135.xlshosting.net \
--to=pieter.wuille@gmail$(echo .)com \
--cc=bitcoin-development@lists$(echo .)sourceforge.net \
--cc=matthewmitchell@godofgod$(echo .)co.uk \
/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