[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
of
> > > 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
unneeded
> > > data to do a verification?
> >
> > Who's forcing who to transfer unneeded 'data for verification'
(hashes?)?
>
> 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
tb.

> >
> > 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
hash functions.
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
wouldn't
> > be able to tell whether a certain node was internal or leaf (whether
it's
> > 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!
http://us.click.yahoo.com/L5YrjA/eSIIAA/yQLSAA/dkFolB/TM
--------------------------------------------------------------------~-> 

 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
 



More information about the BitTorrent mailing list