[BitTorrent] Re: bt2 protocol features

Stephen Thomas flabdablet at yahoo.com
Tue Jun 8 13:49:04 EDT 2004


--- In BitTorrent at yahoogroups.com, Elliott Mitchell <ehem at m...> wrote:
> Until that time do you object to this remaining an idea to
> _try_ to put in place?

Personally I think the idea of retrieving blocks by their hash codes
is quite beautiful (I was throwing this idea around in here a month or
two ago, but my vast ignorance of things IP cost it all credibility).

It occurred to me several years ago that it ought to be possible to
construct an entire file system on top of that idea; that such a file
system would end up being absolutely content-addressable, and
therefore location-insensitive; and that that would be a Good Thing. 
Mind you, I was in the grip of psychosis at the time, so it probably
needs to be thought about carefully by more people.

The only reason I'm excited about it again is because I see it as such
a beautiful fit with Bram's cunning tit-for-tat bandwidth management
scheme.  If nobody here wants to play with it, that's fine; I'll
undoubtedly get around to it myself some day...

The basic idea is that each file could be stored with/as a tree of
hashes, only N-way instead of binary, with standard size blocks
throughout.  Let's assume 2 Kbyte blocks, and use SHA256 hashes to
make birthday paradox collisions less likely than alpha-particle
memory corruption.  A file's "true name", in this scheme, is just the
root hash of such a tree.

The basic mechanism underlying file-reads is a retrieval engine which,
when given a hash, returns the stored block matching that hash.  To
read a file, you pass the root hash to the retrieval engine and
examine the block it returns.  If it's marked "leaf", extract its
data; if not, it contains more hashes, whose blocks get retrieved in
the same way.

Effectively, the entire tree is retrieved breadth-first; the only data
the user is interested in are in the leaf nodes, but apart from being
marked as leaves internally there's nothing special about those from
the retriever's point of view.

Because you can fit upwards of 60 SHA256 hashes in a 2K block even
allowing a generous amount for assorted housekeeping info, the tree
fans out very quickly; the non-leaf nodes end up occupying under 2% of
the space the data does.

Olaf, your point about large blocks needing fewer hashes is well
taken; but is the difference between transferring 102% of the data and
101% really such a big deal?  I think not, especially having seen
upwards of 130% with BT on my slow dialup link due to redundant piece
requests getting cancelled too late.

There is no need for "all-the-way-to-the-root" stepwise Merkle
verification at any point, because each block is immediately
verifiable against the hash it was retrieved with.

A directory, in this scheme, is simply a dictionary file in some
convenient format that maps human-readable names and metadata to "true
name" hashes.  Directories could therefore be stored and retrieved
exactly like files.

Specialized retrieval engines - such as a Bit-Torrent-ish distributed
network - could used optimized requests and availability announcements
to save bandwidth.  One reasonably efficient possibility would be to
adapt Bram's existing bitfield idea, and use requests beginning with a
hash and followed by a bit string; each 1-bit in the string would
correspond to a requested node in a breadth-first serialization of
part of the subtree rooted at that hash, and a zero bit in any level
would elide an entire node's worth of bits in the next-most-leafward
level.

To limit upstream bandwidth, all an ISP would need would be the
block-retrieval engine and a big fat cache; no file-assembly logic at
all.  So a proxy would be simpler than a client, wouldn't need BGP
feeds or whatever, and would have plausible deniability for
responsibility for content.

Other interesting possibilities follow from allowing all nodes, rather
than just the last leaf node in a file, to be only part-full. 
Judiciously used, this could let patched files share substantial
storage with their unpatched cousins, or ISO packagings share storage
(and, of course, retrieval shareability) with the files they contain.

Anyway, enough of my obsession du jour.  Back to the proper BT
discussion.

Cheers
S




------------------------ 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