[p2p-hackers] [connellybarnes@yahoo.com: [i2p] Python filesharing Merkle hash tree magic]

[bert at web2peer.com]

Merkle trees [1] are a cryptographic approach to authenticity/integrity that have several properties that make them useful in p2p settings. Each leaf contains the hash of one file block/chunk, and the internal nodes are themselves hashes of the hashes represented by their children.  To support verification, the server needs to provide only lg(N) hashes with each chunk served, where N is the total number of chunks. These "auxiliary hashes" that must be returned with each chunk correspond to the tree nodes that are siblings of those nodes along the "authentication path" from leaf to root.

I've just returned from WWW-2005 where I was advocating the use of Merkle trees for use in authenticating HTTP responses: http://www.almaden.ibm.com/cs/people/bayardo/ps/www2005.pdf.  This provides an efficient means for authenticity guarantees even when using p2p (untrusted) web content caching & delivery networks. No rocket science here, but an idea that I believe whose time has come.

And as an aside, multi-file torrents need not require multiple root hashes. A single merkle tree (& hence root hash) would suffice for authenticating arbitrary chunks so long as you appropriately combined hashes. I think if you read the above-linked proposal for authenticating HTTP responses (which requires one root hash per multi-file repository), it should be clear how multi-file torrents could be supported.


[1] R. C. Merkle. Protocols for public key cryptosystems. In Symposium
on Security and Privacy, 122-134, 1980.

----- Original Message -----

From: "Nick Johnson" <arachnid at notdot.net>
To: "Peer-to-peer development." <p2p-hackers at zgp.org>
Subject: Re: [p2p-hackers] [connellybarnes at yahoo.com: [i2p] Python filesharing	Merkle hash tree magic]
Date: Sun, 15 May 2005 11:26:37 +1200

> 
> How does this work? You don't provide details here or in the .py file - does 
> each chunk include the hashes of all its siblings, and its parents' siblings, 
> etc?
> 
> -Nick Johnson
> 
> Eugen Leitl wrote:
> 
> > ----- Forwarded message from "C. Barnes" <connellybarnes at yahoo.com> -----
> >
> > From: "C. Barnes" <connellybarnes at yahoo.com>
> > Date: Thu, 12 May 2005 04:36:32 -0700 (PDT)
> > To: i2p at i2p.net
> > Subject: [i2p] Python filesharing Merkle hash tree magic
> >
> >
> > Topic: P2P filesharing ala BitTorrent.
> >
> > Presenting public domain module 'chunk.py':
> >
> >  http://oregonstate.edu/~barnesc/temp/chunk.py
> >
> > This module does some magic with Merkle hash trees.
> > It allows one to publish a 20 byte SHA-1 digest for
> > a file, and encode 'chunks' from the file with
> > minimal overhead, such that any given chunk can be
> > verified against the file's 20 byte digest.
> > Cryptographic hashing is used to verify each chunk,
> > so chunks can be transmitted in any order, and it is
> > impossible to save corrupt data to disk if one has
> > the correct file hash.
> >
> > One could use this module in any file sharing
> > application which divides files up into blocks.
> >
> > For example, in a BitTorrent-like project it might
> > be desirable to keep the .torrent files minimal in
> > size.  Using this module, one needs to only publish
> > a hash like DA39A3EE5E6B4B0D3255BFEF95601890AFD80709
> > instead of a digest of all blocks in the file.
> >
> > Pros:
> > - Smaller digest size.
> > - Can send chunks in any order.
> >
> > Cons:
> > - Each 'chunk' contains checksumming information.
> >   This overhead is less than 4% for files of size
> >   less than 1e20 bytes.
> >
> > - Connelly Barnes
> >
> >
> >
> > 		
> > __________________________________ Yahoo! Mail Mobile Take Yahoo! Mail with 
> > you! Check email on your mobile phone. http://mobile.yahoo.com/learn/mail 
> > _______________________________________________
> > i2p mailing list
> > i2p at i2p.net
> > http://i2p.dnsalias.net/mailman/listinfo/i2p
> >
> > ----- End forwarded message -----
> > _______________________________________________
> > p2p-hackers mailing list
> > p2p-hackers at zgp.org
> > http://zgp.org/mailman/listinfo/p2p-hackers
> > _______________________________________________
> > Here is a web page listing P2P Conferences:
> > http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences
> >
> > !DSPAM:4285c8e4292214151599692!
> >
> >
> >
> 
> _______________________________________________
> p2p-hackers mailing list
> p2p-hackers at zgp.org
> http://zgp.org/mailman/listinfo/p2p-hackers
> _______________________________________________
> Here is a web page listing P2P Conferences:
> http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences