[BitTorrent] BT2 & hash trees
Olaf van der Spek
OvdSpek at LIACS.NL
Tue Jul 20 04:36:18 EDT 2004
----- Original Message -----
From: "Elliott Mitchell" <ehem at m5p.com>
To: <BitTorrent at yahoogroups.com>
Sent: Tuesday, July 20, 2004 8:25 AM
Subject: Re: [BitTorrent] BT2 & hash trees
> >From: Olaf van der Spek <OvdSpek at LIACS.NL>
> > > > The block size that you use to create the leaf hashes is totally
> > independent of the piece
> > > > size used in the BT transfer. Your hashtree will look like this:
> > >
> > > True to a point, but not entirely so. If they're distinct the least
> > > common multiple defines the smallest block that you can retrieve and
> > > verify efficiently. This is more a factor of the degree of branching
> > > the internal nodes, than the leaves but it is still important. It is
> > > useful to be able to verify with 1KB granularity, but if the smallest
> > > protocol addressible block is 16KB why force someone to transfer
> > > data to do a verification?
> > Who's forcing who to transfer unneeded 'data for verification'
> With this scheme you'll transfer 1024 hashes in a block (reasonable),
> you'll then need to use 256 of them to verify a 256KB piece. If the worst
No, you don't. The minimum block size can be larger than the base segment
size of the tree, the only requirement is that it's a multiple.
So a 1 kb base segment size still allows blocks of 16 kb, 1 mb, 1 gb or 1
> > Other (future) hashing schemes.
> Given that handling a new one *will* require new code (what is the use of
> using a hash you can't verify?), and they all operate on an arbitrary
> number of bytes of input (future hashes are *certain* to follow this);
> how does using a branching factor of 1024 help the future?
Not using 1 kb is sure to not allow any compatibility.
I didn't mean new hash functions (my fault :( ), but new uses of existing
Linux distributions for example often publis md5 and sha1 sums. In the
future they could publish merkle-sha1, but that would only be useful if 'we'
'both' used the same base segment size.
> > Because if you only have the root hash and not the file size, you
> > be able to tell whether a certain node was internal or leaf (whether
> > data or hashes).
> I suppose so. Though this requires you to run the hash over the block
> twice (the SHA functions are fairly expensive). If you really want to use
If you have a block and don't know whether it's supposed to be data or
hashes, yes. But most of the time you do know and you can easily verify that
with just a single hash operation.
> this as an indicator, better to append the flag to the input; that way
> you can save the hash state at the end of the input and not have to run
> the hash over all of the input twice.
------------------------ Yahoo! Groups Sponsor --------------------~-->
Make a clean sweep of pop-up ads. Yahoo! Companion Toolbar.
Now with Pop-Up Blocker. Get it for free!
Yahoo! Groups Links
<*> To visit your group on the web, go to:
<*> To unsubscribe from this group, send an email to:
BitTorrent-unsubscribe at yahoogroups.com
<*> Your use of Yahoo! Groups is subject to:
More information about the BitTorrent